第六章 构造型数据类型.

Presentation on theme: "第六章 构造型数据类型."— Presentation transcript:

1 第六章 构造型数据类型

2 构造型数据类型 第二章我们学习了Pascal语言的四种标准数据类 型(Standard Data Type)
在解决实际问题时所涉及的数据远非上述四种标准数 据类型能够表达，需要除标准数据类型之外的其它数 据类型来表示数据 Pascal语言具有构造新的数据类型的能力

3 构造型数据类型 在Pascal语言构造新的数据类型，称为构造型数 据类型(Structured Data Type)，又称为用户自定 义的数据类型(User-defined Data Type)： 枚举类型、子界类型、数组类型、集合类型、记录类 型，其中 枚举类型和子界类型属于纯量类型（标量类型） 数组类型、集合类型和记录类型3种属于结构类型 （复合类型） 四种标准的数据类型也属于纯量类型

4 第六章 构造型数据类型 6.1 枚举类型 6.2 子界类型 6.3 数组类型 6.4 集合类型 6.5 记录类型

5 6.1枚举类型 在程序设计中，我们发现用四种标准数据类型很难 来描述我们所要处理的数据或者描述起来很不自然
例如，在设计模拟扑克牌的游戏程序中，扑克牌的四种花 样（梅花、方块、红桃、黑桃） 可用整型数1、2、3、4表示，也可用字符型数据 ‘A’、‘B’、‘C’、‘D’表示 若用club、diamond、heart、spade四个字符串常量 表示，则程序实现起来很不方便 Pascal语言中提供了一种用户自定义的数据类型——枚举 类型(Enumerated type) 枚举类型的引入还增加了程序的可读性，节约存储空间

6 6.1.2 枚举类型及其变量说明 1、枚举类型说明 语法 例如：type color = (red, blue, green, grey, orange); 类型标识符 = （ 标识符 ） ; , 枚举类型说明

7 6.1.2 枚举类型及其变量说明 语义：定义一个枚举类型 type cards=(club, diamond, heart, spade);
例如： type cards=(club, diamond, heart, spade); 定义一个含有4个枚举值(枚举字面量)的名字为cards的枚举 类型

8 6.1.2 枚举类型及其变量说明 2、枚举类型的变量说明 语法 例如：var col1,col2: color;
mycards: cards; 枚举类型变量说明 标识符 , : 枚举类型标识符 ;

9 6.1.2 枚举类型及其变量说明 枚举类型说明与枚举类型的变量说明可以合并
例如，以上的枚举类型说明与枚举类型变量说明的例 子可以合并为： var col1，col2: (red, blue, green, grey, orange); mycards: (club, diamond, heart, spade);

10 6.1.3 枚举类型数据的运算 赋值运算 允许将枚举类型的数据值赋给同类型的枚举类型的变 量 例如，
col1:=blue; col2:=orange; mycards:=heart; 关系运算 同一枚举类型的数据可以进行关系运算，运算的结果 是布尔类型的数据 例如，有赋值语句： 关系表达式: col1<>col2 的值为true col1>col2的值为false

11 6.1.4 说明 枚举值标识符可以在内层的过程或函数中重新说明， 不过重新说明后该枚举值的语义发生了变化，是重新 定义的语义
这里包含了多态(Polymorphic)的思想 多态是指同一个标识符同时具有多种语义 多态是面向对象程序设计语言的核心概念之一

12 6.1.4 说明 枚举类型说明中的枚举值的规定 枚举类型说明中的枚举值（枚举字面量或枚举常量）必须 是标识符
例如，下面枚举类型说明是错误的： type days = (1, 2, 3, 4, 5, 6, 7); operator = (+, -, *, / ); 正确的写法： type days = (Monday, Tuesday, Wednsday, Thursday, Friday, Saturday, Sunday); operator = (plus, minus, times ,divide ); 枚举类型说明中的枚举值（常量）的定义采用了穷举方法

13 6.1.4 说明 枚举类型的字面量标识符的使用规定 枚举类型的字面量标识符不能重复出现在枚举类型说 明中 不能与常量说明中的常量标识符同名
例如，下面枚举类型说明是错误的： const apple=ˊfruitˊ; type fruit=(apple, orange, tomato, lemon); vegetable=(tomato, pea, potato, carrot);

14 6.1.4 说明 枚举类型字面常量的次序规定 枚举类型字面常量是有序的，这是枚举类型的数据进 行关系运算的基础
Pascal语言规定枚举类型的常量的序号从0开始，按照 定义时排列的先后为序，逐个增加1 枚举类型的数据可作为标准函数pred、succ和ord的自 变量 例如：succ(plus)=minus, pred(minus)=plus, ord(minus)=1

15 6.1.4 说明 标准Pascal语言中输入输出语句的使用规定 枚举类型是不同值的有序数据表
例如，下面语句是错误的： read(col1); read(mycards); 下面的输出语句也是错误的： write(col1，mycards); 枚举类型是不同值的有序数据表

16 6.1.5 程序设计举例 例1 组合问题。求从红、橙、黄、绿、蓝五种颜色 的球中，取三种颜色的球的可能的取法。 分析
该问题属于组合数学中的组合问题。根据我们在组合 数学中解决组合问题的方法，程序设计的方法可用穷 举方法 先引入一个表示红、橙、黄、绿、蓝五种颜色球的枚 举类型，用变量i,j,k分别表示五种颜色的球中的一种。 该问题的穷举方法如下

17 6.1.5 程序设计举例 算法 ① 计数器置初值：n←0; ② 循环：i从red 到 blue，步长为1，做
循环：j从i 到 blue，步长为1，做 若i≠j,则 循环：k从j 到 blue，步长为1，做 若i≠k且k≠j，则 [ 输出一种取法； n←n+1; {取法计数一次}； ] ③输出所有取法的数目n

18 源程序 Program Permutation(input,output);
Type colour=(red,orange,yellow,green,blue); Var i,j,k,pri:colour; loop,n:integer; Begin n:=0; for i:=red to blue do for j:=i to blue do if (i<>j) then for k:=j to blue do if (i<>k) and (k<>j) then begin n:=n+1;

19 {使用间接输出法，输出一种选择} for loop:=1 to 3 do begin case loop of 1:pri:=i; 2:pri:=j; 3:pri:=k end; case pri of red: write(‘red’); orange: write(‘ orange’); yellow: write(‘yellow ‘); green: write(‘green ‘); blue: write(‘blue ‘) writeln; end; {for loop} writeln(‘total number:’, n) End.

20 附注 该问题属于“组合数学”中的组合问题 该类问题的常用算法设计策略是穷举策略 具体实现时的程序结构为循环结构
比穷举策略更好的回溯策略将在算法设计与分析课 程中学习 由于标准Pascal语言中不允许用输入/输出语句直接读/ 写枚举变量的值，所以枚举变量的值的输入/输出只能 利用间接的方法进行 本例给出了枚举变量的值的输出的间接方法

21 6.1.5 程序设计举例 例2 源程序文件的注释删除问题。写一个程序，把某 一输入Pascal源程序文件中的全部注释删除，并输 出删除注释后的源程序。 分析 程序中的注释是用“{”和“}”括起来的部分。它用来 供用户阅读和理解程序时用，无语法意义，编译时会被 删掉 为了处理的方便，我们在程序中定义一个状态变量 action，它是一个枚举类型的数据，枚举字面量为：复 制状态copyiny和删除注释状态decomment。在不同的 状态下进行不同的处理

22 复制状态copyiny（作为程序的初始状态）: 字符 从输入文件input复制到输出文件output。当程序读 到“{”时，注释开始，应转入注释状态 decomment
注释状态decomment: 从输入文件input读入的字 符不复制到输出文件output中，一直读到“}”时， 注释段结束，程序转入复制状态 为了控制输入文件的结束，处理回车换行，还需要两 个标准函数eof和eoln 文件结束函数eof(f): 参数f代表文件名。当文件f结 束时，该函数值为true，否则为false 行结束函数eoln(f): 参数f代表文件名。当文件f的 行结束时，该函数值为true，否则为false

23 算法 ① 设置初始状态为复制； ② 循环：当文件未结束，做 [ 循环：当行未结束，做 [ 输入ch;
] 换行处理;

24 源程序 Program removecomments(input, output);
Type states=(copyiny, decomment); Var action: states; ch: char; Begin action:=copying; while not eof(input) do begin while not eoln(input) do read(ch); case action of copying: if ch=‘{‘ then action:=decomment else write(ch); decomment: if ch=‘}’ then action:=copying end; readln; writeln; End.

25 源程序文件的注释删除问题 附注 本题是一个典型的非数值计算问题
源程序文件中注释的删除程序是预处理器（Preprocessor） 的一个组成部分。预处理器是在源程序真正翻译前由编 译器调用的独立程序

26 6.2 子界类型 在解决实际问题中，有些数据的变化范围只在某 一数据类型数据的值域的某一区域内
例如，某学校某一个班的学生人数和学生年龄。它们 虽然都是整数，但仅在整数类型数据值域的部分范围 内变化 Pascal语言中，对只取某一定义的有序类型数据的值域 的某一范围的问题，专门引入了子界类型（又称子域 类型） 采用子界类型(Subrange type) 可更接近实际，增加程 序的可读性，有助于程序检查

27 6.2.2 子界类型及其变量说明 1、子界类型说明 语法 例如：type age=15..30; 类型标识符 = 常量1 .. 常量2 ;
例如：type age=15..30; 类型标识符 = 常量1 .. 常量2 ; 子界类型说明

28 6.2.2 子界类型及其变量说明 语义:定义了一个从常量1到常量2的子界类型
例如，下面的类型说明定义了一个从ˊAˊ到ˊZˊ的子界类 型letter: type letter=ˊAˊ..ˊZˊ; {这是哪个类型的子界？}

29 6.2.2 子界类型及其变量说明 附注 子界类型说明的语法中，常量1称为子界类型的下界 (Lowerbound)，常量2称为子界类型的上界(Upperbound)， 它们必须属于同一个有序类型(Ordinal Type)，即整型、 布尔型、字符型或同一枚举型，但不能是实型 子界类型的上界和下界规定了子界类型的数据的取值 范围 下界必须小于上界 常量1和常量2所属的类型称为子界类型的基类型(Base Type)或宿主类型 子界类型是有序类型，其元素的序号是该元素在基类型 中的序号

30 6.2.2 子界类型及其变量说明 子界类型的变量说明 例如：有说明：type age=15..30; var age1,age2: age;
子界类型说明与子界类型的变量说明可以合并 例如，以上的子界类型说明与子界类型的变量说明的例子可以合并为： var age1,age2:15..30; 标识符 ; : , 类型标识符 子界类型的变量说明

31 6.2.3 子界类型数据允许进行的运算 子界类型的数据允许进行的运算取决于其基类型， 可做基类型的数据允许进行的一切运算
子界类型继承了其基类型所允许进行的运算 继承(Inheritance)是面向对象程序设计语言的重要 概念 例如，基类型为整数类型时，允许进行的运算是算术 运算和关系运算。

32 6.3 数组类型 6.3.1 数组的概念 6.3.2 数组类型及其变量说明 6.3.3 数组元素的访问及存储 6.3.4 数组类型数据的运算
6.3 数组类型 6.3.1 数组的概念 6.3.2 数组类型及其变量说明 6.3.3 数组元素的访问及存储 6.3.4 数组类型数据的运算 6.3.5 数组的输入与输出 6.3.6 压缩数组 6.3.7 程序设计举例

33 6.3.1 数组的概念 1、为什么要引入数组 从下面的问题的解决，我们可以看出引入数组 (Array)的必要性
问题：从键盘任意输入50个实数，按照相反的次序输出 这些数 解决的方法：为了解决该问题需要引入50个实型变量 x1, x2, ···, x50，用来存放从键盘任意输入的50个实数， 然后按照x50, x49, ··· , x1顺序输出即可

34 6.3.1 数组的概念 算法： 输入x1; 输入x2; …… 输入x50; 输出x50; 输出x49; 输出x1;

35 6.3.1 数组的概念 实现上述算法时，要用50个输入语句和50个输出语句 如果输入的数据为100，1000，……？
Pascal语言中，对具有一定数目的相同数据类型的数据按照一定的顺序排列的问题，专门引入了数组类型 例如，对于上述问题，可以定义一个名字为x含有50个元素的数组，其元素x[1]、x[2]、……、x[50] 分别存放输入的50个数据，它们分别对应x1,x2,···,x50 变量 可用下面的一段程序描述问题 for i:=1 to 50 do read(x[i]); for i:=50 downto 1 do write(x[i]);

36 6.3.1 数组的概念 数学上，我们常用一个向量(Vector)表示一些相关数据 组成的序列(Sequence)，用矩阵(Matrix)表示具有行、 列结构的数据表格 Pascal语言中，引入数组类型(Array Type) 来表示向 量和矩阵等 数组类型是Pascal语言中最常见的构造型数据类型 数组是数据项的有序表，这些数据项称为数组元素

37 6.3.1 数组的概念 2、数组的特点 Pascal的数组有以下特点： 数组的每个元素均为同一类型，称为数组类型的基类型；
数组元素个数一经确定后保持不变，称为数组的长度； 数组元素用数组名和下标表示。标识数组元素的下标的 个数称为该数组的维数(Dimension)。有一个下标的数组 称为一维数组，有二个下标的数组称为二维数组 数组中每个元素还允许是数组类型，由此产生二维数组、 多维数组(Multi-dimensional Array)

38 6.3.1 数组的概念 3、数组类型的数学基础 数组类型的数学基础是集合论中函数（映射）的 概念
一个数组可以看作从一个下标的有限集合到数组元素 的有限集合的一个映射

39 6.3.2 数组类型及其变量说明 1、数组类型说明 语法 例如：type score1=array [1..30] of real;
类型标识符 = ; array [ ] of 下标类型 基类型 ， 数组类型说明

40 6.3.2 数组类型及其变量说明 语义:定义一个或多个数组类型
例如，上例定义了一个一维数组类型score1 ，一个二 维数组类型score2，一个三维数组类型score3

41 6.3.2 数组类型及其变量说明 说明 数组类型定义有三个方面的内容： 类型名字 维数表，说明数组的下标个数、类型和上下界 数组元素的类型
数组下标的类型必须是有序类型（整型、布尔型、字符型、 枚举型、子界型等），不能是实型或其它构造型数据类型 下标的上界和下界规定了下标的取值范围，下界≤上界 数组的下标可以是一个表达式 数组元素的类型（基类型或宿主类型）是除文件类型之外 的任何类型

42 6.3.2 数组类型及其变量说明 2、数组类型的变量说明 语法 例如： var sc11, sc12: score1;
定义sc11, sc12为score1型的一维数组变量，sc21, sc22为 score2型的二维数组变量，sc31，sc32为score3型的三维数 组变量 数组类型标识符 标识符 : ; 数组类型的变量说明

43 6.3.2 数组类型及其变量说明 数组类型说明与数组类型的变量说明可以合并 上面的数组类型说明与数组类型的变量说明的例子 可以合并为：
var sc11, sc12: array [1..30] of real; sc21, sc22: array [1..30,1..10] of real; sc31, sc32: array [1..30,1..10,1..10] of real;

44 6.3.3 数组元素的访问及存储 1、数组元素的访问 对数组的访问通过访问数组元素进行。数组元素 的表示格式：
数组名[下标表达式1, 下标表达式2, ··· , 下标表达式n] 其中，n为数组的维数 下标表达式的类型必须与数组类型定义中的下标类型 一致，当且仅当下标表达式的值不超过下标类型定义 的取值范围，才可以确定一个对应的数组元素

45 6.3.3 数组元素的访问及存储 1、数组元素的访问 数组访问的方法有顺序访问和随机访问两种
顺序访问：对数组的所有元素进行处理，通常从数组 的第一个元素开始，依次处理数组的每个元素，直到 最后一个元素 随机访问：根据需要直接访问数组中某个元素

46 6.3.3 数组元素的访问及存储 2、数组的存储 数组在机器内存中以数组元素为单位顺序存放， 一维数组，占用内存中一段连续的区域；
二维数组，数组元素按行序的优先存放在内存的一段 连续的区域中

47 6.3.3 数组元素的访问及存储 一维数组a1 二维数组a2 例如，var a1: array [1..6] of real;
两个数组经过编译后，其在内存中的存放如下图 一维数组a 二维数组a2 a1[1] a1[2] a1[3] a1[4] a1[5] a1[6] a2[1,1] a2[1,2] a2[1,3] a2[2,1] a2[2,2] a2[2,3]

48 6.3.4 数组类型数据的运算 标准Pascal语言中，对数组整体的运算仅有三种 对于数组的应用处理一般通过数组元素进行
相同类型的数组可以进行赋值（此时将赋值看作运算） 紧缩字符数组可以进行关系运算 数组作为过程或函数的参数 对于数组的应用处理一般通过数组元素进行 数组元素能参与什么运算，取决于数组元素的类型 数组类型继承其元素类型（基类型）所允许进行的 运算 例如，整型数组可以参加算术运算、关系运算和赋 值运算

49 6.3.5 数组的输入与输出 数组类型数据不能直接用read、write语句进行输 入输出，只能对其元素进行输入与输出

50 例3 数组元素的类型为枚举类型数组的输入。 program Enumread(input,output);
例3 数组元素的类型为枚举类型数组的输入。 program Enumread(input,output); type week=(sun, mon, tue, wed, thu, fri, sat); weekarray=array [0..6] of week; var w1: weekarray; i: integer; Begin read(i); case i of 0:w1[i]:=sun; 1:w1[i]:=mon; 2:w1[i]:=tue; 3:w1[i]:=wed; 4:w1[i]:=thu; 5:w1[i]:=fri; 6:w1[i]:=sat end; End.

51 6.3.6 压缩数组 1、压缩数组的概念 数组在计算机内存中是以数组元素为单位顺序存放的，所需要的存储空间与数组元素的类型和机器的字长有关
在16位字长的机器里，每个数组元素所占用的存储空间分别是：整型占用2字节，实型占用4字节，字符型占用2字节，布尔型占用2个字节 若有如下变量说明： var a: array [1..50] of char; 数组a共占用100个字节的空间

52 6.3.6 压缩数组 一个字符型数组元素占用2字节的空间是浪费，其实仅用一字节空间存储一个字符型数组元素就足够了
若一个字符型数组元素占用2个字节的空间，则其空间的利用率只用50% 为了节约计算机的内存空间，Pascal语言中提供了压缩数组类型(Packed Array Type) 把同类型的数组元素压缩存储，使其占用的空间缩小 压缩数组类型的说明只需要在数组类型的说明中保留字array的前面加保留字packed 例如，var a: packed array [1..50] of char; 压缩数组a的每个元素仅占1字节，压缩数组a比非压缩数组a节约了一半的存储空间

53 6.3.6 压缩数组 2、标准过程pack和unpack
引入压缩数组，可以提高存储器的利用率。但是，访问压缩数组元素的时间会增加，同时引起指令代码的增多 我们可以采用下面的方法进行处理： 在处理之前先把压缩数组解压成非压缩数组，在频繁使用之后再把它还原成压缩数组 标准的Pascal语言中提供了两个标准过程pack和unpack 设有变量说明: var a: array [b1..b2] of T; pa: packed array [pb1..pb2] of T; a和pa的下标i的界b1,b2,pb1,pb2必须满足： b1≤ i ≤b2-(pb2-pb1)

54 6.3.6 压缩数组 (1)标准过程pack 语法：pack(a,i,pa);
功能：把一个非压缩数组a从下标i开始的数组元素顺序放到压缩数组pa中，直到把数组pa放满为止 若a和pa的下标类型都是整型的子界类型，则pack过程等价于下面的语句： for j:=pb1 to pb2 do pa[j]:=a[j-pb1+i];

55 6.3.6 压缩数组 (2)标准过程unpack 语法：unpack(pa,a,i);
若a和pa的下标类型都是整型的子界类型，则unpack过 程等价于下面的语句： for j:=pb1 to pb2 do a[j-pb1+i]:=pa[j];

56 6.3.6 压缩数组 压缩数组的使用，节约了存储空间，但是增加了 程序运行的时间。 存储空间的节约，是通过牺牲运行时间而换取的
这是一种典型的采用时间换取空间的技术，它是计算 机科学与技术中的一种典型技术 我国计算机科学家洪加威教授提出了对偶性原理 (Principle of Duality)，深刻地揭示了计算机科学中时 间复杂性（Time Complexity）与空间复杂性（Space Complexity）之间的关系，他指出： 计算的时间复杂性和空间复杂性可以互换

57 6.3.6 压缩数组 3、字符串类型 在处理非数值计算问题中，常常需要对字符串(String)进行处理
下标类型是以1为下界的子界类型，元素类型为字符型的压缩数组类型，称为字符串类型 字符串（简称串）是指由字符组成的序列 由单引号括起来的字符序列被称为字符串常量。字符串中字母的大小写不同 例如，字符串常量：ˊnew centuryˊ是合法的 字符串变量的定义例： var st1: packed array [1..11] of char;

58 6.3.6 压缩数组 字符串类型是压缩的字符数组类型，它与其它的数 组类型有区别 字符串类型的使用，注意：
允许把字符串类型的常量和变量写到output文件 字符串类型的变量可以直接使用write语句 标准Pascal中，不能直接用read语句读入字符串类型 的变量 允许对字符串类型的变量进行赋值，但赋值时要保持左 部和右部属于同类型（串长度相等）。 允许同类型的字符串类型的常量与变量进行六种关系运 算（<、<=、>、>=、<>、=）

59 6.3.6 压缩数组 若两个字符串全部由大写字母或小写字母组成时， 则其字典顺序就是字符串的顺序
例如，ˊABCˊ<ˊABCDˊ<ˊABCDAˊ 若两个字符串不全由大写字母或小写字母组成时， 则其顺序基于类型char的值的顺序，因而与Pascal 在具体机器上的实现有关 例如：采用ASCII码的机器： ˊAB1ˊ<ˊABCˊ<ˊAbcˊ 采用EBCDIC码的机器： ˊABcˊ<ˊABCˊ<ˊAB1ˊ

60 6.3.7 程序设计举例 例4 查找问题。从键盘任意输入n个学生的身高，查找其中身高最大值并打印。 分析
我们查看聚集在一起的全班学生，找出身高最高的学生的过程是一个穷举比较的过程，这个过程实际上可用擂台赛的方法 为表示n个学生的身高，引入数组heigh

61 查找(Searching)问题 算法 ①输入学生身高的数组heigh； ②将max←heigh [1]；
③将max与heigh [2]到heigh [n]中的数据一一进行比较， 找出身高的最大值max； ④ 输出身高的最大值max

62 C、源程序 Program serch(input,output); Const n=50;
Type stuheigh=array [1..n] of real; Var heigh:stuheigh; i:integer; max:real; Begin for i:=1 to n do read(heigh[i]); max:=heigh[1]; for i:=2 to n do if max<heigh[i] then max:=heigh[i]; writeln(′max=′,max); End.

63 查找(Searching)问题 附注 在给定的数据集合中查找最小数或最大数问题的生活原 型是擂台赛问题
武术的擂台赛过程生动地说明了查找的过程 该过程是一个穷举比较的过程，程序中用循环实现， 而循环中的“比较”使用条件语句实现 对于该问题，我们可以使用分治方法设计出比穷举 方法好的算法 将该问题进一步推广可以得到一般的查找问题：给定一 个数据集合，在其中查找满足某一特定条件的数据

64 查找(Searching)问题 附注 查找（Searching）问题是计算机科学与技术学科的典型 问题之一
查找是计算机程序设计中的一个重要的运算，在数据 处理中有普遍的应用 到目前为止，人类已经发现了许多查找算法，如顺序 查找(Sequential Search)、二分查找(Binary Search)、 分块查找(Block Search)，等等，这些查找算法在数据 结构课程中学习

65 排序(Sorting)问题 例5 排序(Sorting)问题。写一个程序，从键盘任意输入10个整数，按照升序（或正序）将它们排列。 分析
要解决该问题，需将题目中给出的数据聚集到一起，可以利用数组实现 如何实现10个数据的排序呢？最容易想到的是被称为选择排序(Selection Sort)的方法 选择排序的基本思想： 从待排序的数中选择最小的数，将它放在第一个位置上 从剩下的数中选择最小数并将它放在第二个位置上 如此下去，直到最后从剩余的两个数中选择较大的数放在倒数第二个位置上，剩下的一个数放在最后位置上

66 排序(Sorting)问题 算法 ①将10个数输入到数组a中； ②循环：i从1到9，步长为1，做 {数组a从小到大排序}
循环：j从i+1到10，步长为1，做 若a[i]>a[j] 用k记下j位置 交换a[i]和a[k]两个元素; ③ 输出排序后的数组a

67 1 8 1 2 3 4 5 6 7 8 9 10 下标= a 6 k:=1; for j:= 1 +1 to 10 do if a[k]>a[j] then k:=j; temp:=a[1]; a[1]:=a[k]; a[k]:=temp;

68 2 9 1 2 3 4 5 6 7 8 9 10 下标= a 4 k:= 2 ; for j:= 2+1 to 10 do if a[k]>a[j] k:=j; temp:=a[2]; a[2]:=a[k]; a[k]:=temp;

69 3 10 1 2 3 4 5 6 7 8 9 10 下标= a 8 k:= 2 ; for j:= 2 +1 to 10 do if a[k]>a[j] k:=j; 3 3 temp:=a[3]; a[3]:=a[k]; a[k]:=temp;

70 4 9 1 2 3 9 5 8 7 10 4 6 a 8 for to do begin end i:=1 9 或k+1 i k:=3 ;
1 2 3 4 5 6 7 8 9 下标= 9 a 8 for to do begin end i:= 或k+1 i k:=3 ; for j:= 3 +1 to do if a[k]>a[j] k:=j; i temp:=a[ 3 ]; a[ 3 ]:=a[k]; a[k]:=temp; i i

71 源程序 Program selectsort(input,output); Const n=10;
Type data=array [1..n] of integer; Var a:data; i,j,temp:integer; Begin for i:=1 to n do read(a[i]); for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do if a[i]<a[j] then k:=j; if i<>k then begin temp:= a[i];a[i]:=a[j]; a[j]:=temp end; for i:=1 to n do write(a[i]); End.

72 排序(Sorting)问题 附注 排序（分类）问题是计算机科学与技术学科的典型问题之一
排序是计算机程序设计中的一个重要的运算，在数据处理中有普遍应用 据统计，一些商用计算机系统中，15%-17%的CPU时间花费在排序上 到目前为止，人类已经发现了许多排序算法，如快速排序(Quick Sort)、希尔排序(Shell Sort)、归并排序(Merging Sort)，等等，这些排序算法在数据结构课程中学习 正是因为排序算法的有着极为重要的意义，因此排序算法至今仍然是计算机科学工作者的研究方向，在学术期刊上不时地有新的排序算法的问世

73 矩阵乘法 例6 矩阵乘法。求矩阵Am×p和Bp×n的乘积Cm×n。 分析
由高等代数的知识，我们知道C=A×B，其中C的每个 元素C[i,j](1≤i≤m,1≤j≤n)定义为： C[i,j]= A[i,1]×B[1,j]+ A[i,2]×B[2,j]+…+ A[m,p]×B[p,n]

74 矩阵乘法 算法 ①输入矩阵Am×p和Bp×n； ② 循环：i从1到m，步长为1，做 循环：j从1到n，步长为1，做 计算C[i,j];
③输出矩阵Cm×n

75 源程序 Program matricmultiplication(input,output); Const m=5;n=5;p=4;
Var A:array [1..m,1..p] of real; B:array [1..p,1..n] of real; C: array [1..m,1..n] of real; i,j,k:integer; Begin writeln(′Input matrix A:′); for i:=1 to m do for j:=1 to p do read(A[i,j]); writeln(′Input matrix B:′); for i:=1 to p do for j:=1 to n do read(B[i,j]);

76 for i:=1 to m do for j:=1 to n do begin C[i,j]:=0; for k:=1 to p do
C[i,j]:=C[i,j]+A[i,k]*B[k,j]; end; writeln(′Output matrix C:′); wrtie(C[i,j]); writeln; end Bnd.

77 矩阵乘法 附注 矩阵相乘是一个典型的数值计算问题，也是计算机科学 与技术学科的典型问题之一
它是数值计算问题的基础，也是许多非数值计算问题 的基础 例如，求图的最短路径、图的传递闭包、图的连通分 量等非数值计算问题均借助矩阵相乘将问题转化为数 值计算问题加以解决 这些问题是将图论问题转化为代数问题的典型实例 说明数值计算问题和非数值计算问题的统一

78 矩阵乘法 附注 矩阵相乘问题在算法设计与分析、计算复杂性课程中占 有极为重要的地位
自60年代发明矩阵相乘的高效算法以来，至今还有许 多人对该问题进行深入研究

79 回文问题 例7 回文问题。当一个字符串从左到右的排列顺序与从右到左排列顺序相同，则称该字符串为回文字符串，简称为回文。例如‘abcdcba’ 写一个程序判断从键盘输入的字符串是否为回文。 分析 根据题意，可采用下列方进行法判定： 引入两个指针i和j，分别指向字符串的第一个字符和最后一个字符 若i和j所指字符相同，则指针i向右移动一个位置，而指针j向左移动一个位置 继续比较两个指针所指的字符是否相同，若相同，则移动指针，直到指针i超过指针j为止，说明该串为回文 在比较过程中，若两个指针所指字符不同，则停止比较，说明该串不是回文

80 回文问题 算法 输入字符串t； i←1; {判定字符串t是否为回文} j←n; 循环：当t[i]=t[j]且i≤j，做 [ i←i+1;
j←j-1; ]; 若字符串t是为回文，则 输出yes，否则 输出no

81 Program symmetry(input,output);
源程序 Program symmetry(input,output); Const n=100; Type str=packed array [1..n] of char; Var i,j,k:integer; ch:char; t:str; Begin writeln(′Input a string:′); read(ch); n:=0; while ch<> ′.′ do begin n:=n+1; t[n]:=ch; read(ch); end; {输入字符串} i:=1; j:=n; {断定} while (t[i]=t[j]) and (i<=j) do begin i:=i+1; j:=j-1; end; {比较字符，相同则移动指针 if i<j then writeln(′no′) else writeln(′yes′); Bnd.

82 附注 回文反映出对称性，富有美学价值 回文现象广泛地出现在不同科学、文学和艺术之中。在音乐中，著名的音乐大师巴赫的著名作品《音乐的奉献》之中，有一段专为两把小提琴而写的一支被称为《螃蟹卡农》的曲子，这支曲子正着演奏和倒着演奏听起来一模一样，这就是音乐中著名的一支回文曲子 在文学中，回文现象不胜枚举 我国有一个著名的古典回文： 叶落天落叶 厦门鼓浪屿欲腹浦有一副回文对联： 雾锁山头山锁雾，天连水尾水连天。 唐代大诗人苏东坡的回文诗——七律《题金山寺》： 潮随暗浪雪山倾，远浦渔舟钓月明。 桥对寺门松径小，巷当泉眼石波清。 迢迢远树江天晓，蔼蔼红霞晚日晴。 遥望四山云节水，碧峰千点数鸥轻。

83 附注 宋朝著名文学家王安在的回文诗《泊雁》
泊雁鸣深渚，收霞落晚川。 柝随风敛阵，楼映月底弦。 漠漠汀帆转，幽幽岸火然。 壑危通细路，沟曲绕平田。 从这些回文现象中我们能体会到在不同的学科之间，科学与艺术之间，科学与文学之间在更高的层面上是相通的 艺术对科学的创新的作用 埃舍尔的著图画——瀑布

84 6.3.7 程序设计举例 例8 Josephus(约瑟夫)问题。 据说著名犹太历史学家 Josephus有过以下的故事：

85 6.3.7 程序设计举例 然而Josephus 认为这样的死毫无价值和意义。于是他将自己和他的一个好朋友安排在了一个合适的位置，从而避免了这场死亡游戏。

86 Josephus问题是以韦拉维奥·约瑟夫斯命名的

87 另一个故事： 17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

88 约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里将问题一般化，并给出一种实现方法。

89 6.3.7 程序设计举例 例8 Josephus(约瑟夫)问题。
一般形式：设有n个人围坐在成一个圆圈，从某个位置编号为1, 2, 3, ···, n，编号为1的位置上的人从1开始报数，数到m的人便出圈；下一个人（第m+1个）又从1开始报数，数到m的人便是第二个出圈的人。如此不息，直到最后一个人出圈为止，于是便得到一个出圈顺序。写一个程序，输出这个出圈顺序。

90 Josephus(约瑟夫)问题 分析 问题 的输入 和输出 问题的本质：循 环遍历 数据结构
查找 删除 数据结构 为了便于报数，我们引入a[1..n]数组，其元素初始值均为1，它表示对应下标i位置上有人，当a[i]=0时，表示对应下标i位置上的人已经出圈

91 Josephus(约瑟夫)问题 引入计数器变量s，用于报数
引入另一个计数器变量p, 来记录出圈的人数，若p=n，则表示圈中已无人，全部出圈完毕 该问题的解决方法 从数组a[1..n]的第一个元素开始，依次取数组元素相加，当其和为m时，输出该元素的下标i 将该元素清0 (a[i]←0)，以表示出圈，和s也清0 (s←0)，以准备继续往下报数 从下一个元素开始，依次取数组元素相加，当其和为m时，输出该元素的下标i，如此下去，直到输出n个值(p=n) 时结束

92 Josephus(约瑟夫)问题 算法 给数组a[1..n]赋初值1，表示每个人已经围好，准备报数； 循环: 当还有人未出列时（p≠n），做：
循环: i从1到n, 步长为1，做 { n围坐的人数} [ 报数并计数； { 1-m报数} 若数到m，则 [ 计数器s重新计数； 位置i上的人出列； 人数计数器p加1； 输出出列人数p及位置号i； 若出列人数为n，则程序结束； ]

93 源程序 Program Josephus1( input,output); Const n=13; m=5;
Type peno=array [1..n] of integer; Var a: peno; s, p, i: integer; {s , p 分别记录报数数，出列的人数} flag: boolean; {是否全部出列的标志} Begin for i:=1 to n do a[i]:=1; {置“在圈中”的标志} s:=0; p:=0; flag:=true; while flag do for i:=1 to n do begin s:=s+a[i]; if s=m then begin s:=0; a[i]:=0; p:=p+1; writeln(′p=′, p, i:4); if p=n then flag:=false; end; Bnd.

94 Josephus(约瑟夫)问题 算法 给数组a[1..n]赋初值1，表示每个人已经坐好，准备报数； i1
循环: 当还有人未出列时（p<n），做：{ n围坐的人数} [ 报数并计数； { 1-m报数} i i mod n +1 若数到m，则 [ 计数器s重新计数； 位置i上的人出列； 人数计数器p加1； 输出出列人数p及位置号i； 若出列人数为n，则程序结束； ]

95 源程序 Program Josephus1( input,output); const n=13; m=5;
type peno=array [1..n] of integer; var a: peno; s, p, i: integer; {s , p 分别记录报数数，出列的人数} flag: boolean; {是否全部出列的标志} Begin for i:=1 to n do a[i]:=1; {置“在圈中”的标志} s:=0; p:=0; i:=0; while p<n do begin while s<m do; i:=i mod n +1; if a[i]=1 then s:=s+1 end; s:=0; a[i]:=0; p:=p+1; writeln(′p=′, p, i:4); Bnd.

96 Josephus(约瑟夫)问题 附注 该问题是由古罗马著名史学家Josephus提出的，后人称它为Josephus问题
第八章例1将给出借助指针的算法

97 6.3.7 程序设计举例 例9 鞍点问题。在一个m×n的矩阵中，元素a[i,j]满足下述条件：a[i,j]既是第i行元素中的严格最小值，又是第j列元素中的严格最大值，则称a[i,j]为矩阵a的一个鞍点。编写一个程序求出a中所有的鞍点。若不存在鞍点，则给出相应信息。 分析 根据题意可知，该问题是在矩阵中查找鞍点 为了简单起见，假设矩阵中没有相同的元素

98 鞍点问题 算法 输入m×n矩阵a; i←1； 循环：当i≤m且没找到鞍点，做 [ 找第i行上最大元素max，并记下它所在的列号c；
在第c列上，把max与该列上的其它元素比较，判断在c列上max是否是最小的元素。只要发现有1个元素≤max，则说明在c列上不是最小元素； 若max是第c列上的最小元素，则找到鞍点，输出其值，然后退出循环; i←i+1 ]

99 源程序 Program saddlepoint(input,output); const m=10;n=12;
type mat=array [1..m ,1..n] of integer; var a:mat; i,j,k,r,c:integer; find:boolean; Begin writeln(‘Input’,m, ‘*’, n, ‘array:’); for i:=1 to m do begin for j:=1 to n do read(a[i,j]); {按行读入矩阵的数据 } readln; end; find:=false; i:=1;

100 while (i<=m) and (not find) do
begin max:=a[i,1]; c:=1; {找第i行的最大值 ，并用c记录所在列} for j:=2 to n do if max<a[i,j] then c:=j; find:=true; k:=1; while (k<=m) and find do if k<>i then if a[k,c]<=max then writeln(‘There is no saddle point in’, i , ‘row’ find:=false; {第i行无鞍点} end; k:=k+1;

101 if find then begin writeln(′The saddle point is′); writeln(′a[′,i:1, ′,′,c:1, ′]=′,a[i,c]:3) end; i:=i+1 if (not find) then writeln(′not be found!′); Bnd.

102 鞍点问题 附注 请总结一下鞍点问题属于哪一类问题，采用的是什么求解策略 鞍点问题是计算机科学中的典型问题，有广泛的应用背景

103 6.4集合类型 6.4.1 引言 6.4.2 集合类型及其变量说明 6.4.3 集合类型的数据允许进行的运算
6.4.4 集合类型的进一步说明 6.4.5 程序设计举例

104 6.4.1 引言 集合(Set)是数学中的一个最基本但又是最难精确定义的概念。常采用描述的方法定义。
把一组对象（个体）看成一个整体来考虑时，这个整体便称为一个集合 其中，每个对象（个体）称为集合元素(Element) 集合具有元素的无序性和互异性 Pascal语言是第一个引入集合数据类型的程序设计语言 集合类型(Set Type)的数学基础是集合论 Pascal语言的集合与集合论中的集合有区别 Pascal语言中的集合是有限集合，不能是无限集合； Pascal语言中的集合的元素必须是同一种数据类型，且且只能是有序类型

105 6.4.2 集合类型及其变量说明 1、集合类型说明 语法： 例如：type letters=set of ˊaˊ .. ˊzˊ;
例如：type letters=set of ˊaˊ .. ˊzˊ; numbers=set of ˊ0ˊ .. ˊ9ˊ; 集合类型标识符 = set of 基类型 ; 集合类型说明

106 语义：定义一个集合类型 说明 基类型可以是字符型、布尔型、枚举型、子界型等类型，不能是整型、实型或其它构造类型
集合类型的常量是一个具体的集合。其语法表示如下图 [ ] 集合元素 , 集合表示

107 集合的表示是在方括号中列举(穷举)出集合中的所 有元素，各个元素之间用逗号分开。空集合用[ ]表 示
集合的表示仍然保持了集合元素的无序性和互异性。 例如，集合L1=[a,b,c], L2=[1,2,3,4,5]；[a,b,c]与 [b,a,c]是同一集合。 若集合由值的一个整体或一部分组成时，集合的表 示可以用缩写形式。例如，[1,2,3,4,5] 可以缩写为 [1..5]。 集合的表示采用了计算机科学与技术学科的典型方 法——外延方法。

108 集合类型的数据的值域是由其基类型的值域所决定的。 一般地说，若基类型具有个n值，与它相联系的集合类 型就有2n个值。即集合类型的数据的值集（域）为其 基类型集合的幂集(Powerset)
例如，若有集合类型说明：type M=set of 1..3; 则M 由下列8个集合组成： [ ], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]

109 由于Pascal语言中的集合的基类型（元素的类型）只能是 有序类型，而整型是有序类型，但为什么整型不能作为集 合类型的基类型呢？
一般地，集合的元素个数在16-256之间 Pascal语言中整型数据的值域超过了集合类型中集合允 许的最多元素个数。因此，整型不能作为集合类型的 基类型 当实际问题所需要的集合元素的个数大于Pascal语言所 规定的集合的最大元素个数时，可以用布尔数组来取 代集合类型

110 2、集合类型的变量说明 语法 例如：有变量说明：var letter1,letter2: letters;
number1,number2: numbers; 集合类型说明与集合类型的变量说明可以合并 var letter1,letter2: set of ˊaˊ..ˊzˊ; number1,number2: set of ˊ0ˊ..ˊ9ˊ; , ; : 集合类型标识符 标识符 集合类型的变量说明

111 6.4.3 集合类型数据允许的运算 集合类型数据允许进行的运算有赋值运算、关系 运算和集合运算 关系运算和集合运算具有集合论的意义
由集合运算符将集合类型的数据连接成集合表达式

112 6.4.3 集合类型数据允许的运算 1、赋值运算 集合类型的变量只有赋值运算之后才有具体的值，但赋值运算要遵守赋值相容的原则。
例如，若有如下变量说明： var se1,se2: set of 1..10; x: set of 1..5; y: set of ˊ1ˊ..ˊ5ˊ; 则下面的赋值是正确的： x:=[ ]; x:=[1..5]; se1:=[1,3,5,7,9]; se2:=[2,4,6,8,10]； se2:=se1; 下面的赋值是错误的： x:=se1; y:=x;

113 两个集合通过关系运算进行比较，结果为布尔型数据(true或false)
2、关系运算 两个集合通过关系运算进行比较，结果为布尔型数据(true或false) 集合的关系运算符有5种：=，<>,>=,<=,in 运算符“=”和“<>”用于检查两个集合的相等和不等关系 运算符“>=”和“<=”用于检查两个集合的包含关系。 in是集合类型中特有的关系运算，是判断元素是否属于某集合。相当于集合论中的∈ 例如: [1,2,3]=[2,1,3] [1,2,3]<>[2,4,3] [1]<=[1,2,3] [1,2,3,4]>=[1,2,3] 1 in [1,2,3]

114 3、集合运算 在Pascal语言中，对集合类型还提供了并、交、 差三种集合运算，分别用+、*、-三个运算符表 示。运算的规则与集合论中集合的并、交、差三 种运算相同。 例如： ①[1,2,3]+[3,4,5]=[1,2,3,4,5] ②[1,2,3]*[3,4,5]=[3] ③[1,2,3]-[3,4,5]=[1,2]

115 6.4.4 集合类型的进一步说明 关于集合，还要注意以下几点： 集合中的元素不能作为常量加以定义 例如，程序中有下面的常量说明：
const m=1; 而程序中有出现集合n的值为[1,2,3]，则不能认为 此时集合n的值为[m,2,3]

116 6.4.4 集合类型的进一步说明 集合类型的变量不能进行算术运算，也不允许用读/写 语句直接对集合进行输入/输出
Pascal语言没有提供专门的语句对集合进行输入和 输出，要实现集合的输入与输出，只能采用间接转 换的方法 由于集合的元素具有无序性，因此ord、pred、succ三 个标准函数对集合类型来说是无效的 Pascal语言表达式中的运算符是重载的。例如，运算 符“+”可以是整数加，也可以是实数加，又可以是集 合加。只有从与运算符相关联的左右两个运算对象(量) 的类型才能确定究竟是哪一种操作

117 6.4.5 程序设计举例 例10 集合的建立与输出。已知两个集合s1为[2,3,5,10]，s2为[12,7,15,9,1,5]，求s3=s1∪s2，并输出。 分析 由于Pascal语言不允许用读/写语句直接对集合进行输入/输出，因此要实现集合的输入与输出，只能采用间接的方法 算法 初始化s1和s2； 求s3←s1∪s2； 输出s

118 Program setfoundout(input,output);
源程序 Program setfoundout(input,output); type s=set of 1..15; var s1,s2,s3:s; i:1..15; Begin s1:=[2,3,5,10]; s2:=[12,7,15,9,1,5]; s3:=s1+s2; write(ˊ[ˊ); {开始输出数字集合s3} for i:=1 to 15 do if i in s3 then write(i:5); writeln(ˊ]ˊ); End.

119 集合的建立与输出 附注 本程序说明了集合的建立和输出方法： (1) 集合的建立常采用的方法
第一种方法是利用集合的赋值语句 第二种方法是先将集合初始化后，通过集合的运算形成新 的集合 (2) 对于元素为数字或字母的集合的输出，常采用 的本程序的方法

120 6.4.5 程序设计举例 例11 Eratost-henes(埃拉托色尼)筛法求素数。求2到 n之间的素数 分析
在第五章例1中介绍了试商法寻找素数，算法效率不高 下面介绍公元前3世纪希腊学者Eratosthenes（曾兼任亚 历山大图书馆馆长）提出来的筛法求素数的方法，其基 本思想： 对于一个整数x，只要知道不超过x的平方根的所有 素数p，删除所有的倍数2p，3p，… ，剩下的整数 就是不超过x的全部素数 算法被称为“希腊人的筛子”

121 筛法求素数 算法 用筛法求2到100之间的所有素数的算法如下： ①建立[2 .. 100]的集合（筛子）； ②循环：
找出当前集合中的最小素数；{初始为2，以后取下一个} 输出该最小素数； 从集合中去掉该素数的所有倍数；{用加本身来实现} 直到集合为空为止

122 源程序 Program prime(input,output); const n=100; var sieve: set of 1..n;
next, mul: integer; {next: 最小素数，mul: next的所有倍数} Begin sieve:=[2..n]; next:=2; repeat writeln(next); mul:=next; while mul<=n do begin sieve:=sieve-[mul]; mul:=mul+next end; until sieve=[ ]; Bnd. while not (next in sieve) do next:=next+1;

123 6.4.5 程序设计举例 例12 分类统计问题。从键盘任意输入一串字符，该串以句点结束，标识符和无符号整数以适当的空格间隔。该串中有标识符、无符号整数和其它字符，写一个程序能够统计出该串字符中标识符、无符号整数的个数。

124 6.4.5 程序设计举例 分析 该问题实质上是在输入的字符串中查找标识符、无符号整数的个数问题，属于查找问题。因此，程序设计的策略仍然采用穷举策略。 我们采用边输入边统计的方法 标识符是以字母开头的字母数字串，因此读入第一个字母后，一直要读到空格才表明标识符读完（这里不考虑标识符的长度） 无符号整数是以数字组成的，因此，读入第一个数字之后，一直要读到非数字字符为止 读入第一个非字母数字字符表明是其它符号，一直读到空格，表明下面读入的可能是标识符或无符号整数或其它符号 为了便于判断输入的串是标识符还是无符号整数，我们引入字母字符集合Letterset和数字字符集合Numberset

125 分类统计问题 算法 ① 初始化数据（建立字母和数字集合），并输入第一个字符ch； ② 循环：当ch≠ˊ.ˊ时，做 [
过滤第一个字符前的所有空格； 若输入为标识符，则对标识符计数； 否则， 若输入的为无符号整数，则对无符号整数计数； 否则，读完剩余的字符直到ch=ˊ.ˊ； ] ③ 输出统计出来的标识符和无符号整数的个数。

126 Program statistics(input,output);
源程序 Program statistics(input,output); type character=set of char; var letterset, numberset: character ; ch:char; idcounter, intcounter: integer; Begin letterset:=[ ˊaˊ..ˊzˊ, ˊAˊ..ˊZˊ]; numberset:= [ ˊ0ˊ..ˊ9ˊ]; idcounter:=0; intcounter:=0; read(ch); while ch<> ˊ.ˊ do begin while ch= ˊ ˊ do read(ch);

127 if ch in letterset then {输入为标识符时的处理} begin repeat read(ch); until not (ch in letterset+numberset); idcounter:=idcounter+1; end else if ch in numberset then {输入为无符号整数时的处理} repeat read(ch); until not (ch in numberset); intcounter:=intcounter+1; else while (ch<>ˊ ˊ) and (ch<>ˊ.ˊ) do read(ch) end; writeln(ˊThe number of identifier isˊ, idcounter); writeln(ˊThe number of integer isˊ, intcounter); Bnd.

128 6.4.5 程序设计举例 附注 分类统计问题是基础程序设计中常见的一类问题。这类 问题本质上属于查找并计数问题。因此，程序设计的策 略仍然采用穷举策略。 计数在程序中是利用形如： intcounter:=intcounter+1； 的赋值语句实现的，我们常把这个赋值语句称为计数器， 变量intcounter被称为计数变量

129 6.5 记录类型 6.5.1 引言 6.5.2 记录类型及变量说明 6.5.3 记录成分（域）的引用 6.5.4 记录类型数据允许进行的运算
6.5.5 记录类型数据的输入与输出 6.5.6 记录数组 6.5.7 变体记录 6.5.8 程序设计举例

130 6.5.1 引言 在前面的课程中我们学习了一种非常有用的构造型数 据类型——数组 一个数组是由具有固定数目的、类型相同的元素组成
由于数组元素具有相同的类型，限制了数组的应用， 只能解决同类型数据聚集的问题

131 6.5.1 引言 在实际问题中常常遇到另一类情况，数据由性质各不相 同的成份(或成员)组成，数据的各个成份(Component) 可 能具有不同的数据类型。例如，某学校一个班的学生档案 登记表有下列表目： 学号 姓名 性别 年龄 住址 奖学金 备注 其中，成份 “姓名”、“年龄”和“奖学金”的数据 类型分别是字符串类型、整数类型和实型 用数组类型描述这样的数据不方便

132 6.5.1 引言 Pascal语言中，对不同类型的数据聚集(Aggregate)的 问题，专门引入了记录类型（Record type）来描述。 在记录类型中，成份(或分量)又被称为域或字段(field) 在一个记录中，域的数目是一定的 记录类型最早出现在COBOL语言之中 记录类型的数学基础是集合论中的笛卡尔积 (Cartesian Product)

133 6.5.2 记录类型及其变量说明 1、记录类型说明 在使用一个记录之前，首先要说明它的类型
在类型说明中指出记录类型的名字和记录的每一 个分量的名字和类型

134 6.5.2 记录类型及其变量说明 语法 例如，定义一个含有三个固定域：姓名，性别，年龄的某班学生的记录类型如下：
type student=record Name: packed array [1..20] of char; Sex: (female, male); Age: integer end; 标识符 = record 域表 end ; 记录类型 ; 固定部分 变体部分 域表 ， ： 类型 ; 域名 固定部分

135 语义:定义一个记录类型 说明 ①记录类型数据的值域是其每一个域的值域的笛卡尔积 ②记录类型域的类型也可以是记录类型，这就是记录类 型的嵌套
嵌套时，同一层的域标识符不能同名，但不同层的域标识符可以同名，也可以与记录所在程序体内说明的其它标识符同名。例如： type re1=record a: char; e: real; end; re2=record a: integer; b: rea1; c: 1..10;

136 6.5.2 记录类型及其变量说明 ③ 若同一记录的各域有类型相同者，可以合在一起说明 ④ 记录中的域是无序的

137 6.5.2 记录类型及其变量说明 2、记录类型的变量说明 语法 例如：有变量说明：var st1,st2:student;
标识符 记录类型标识符 : , ; 记录类型变量

138 6.5.2 记录类型及其变量说明 记录类型说明与记录类型的变量说明可以合并 var st1, st2: record
name:packed array [1..20] of char; sex:(female,male); age:integer end; 说明记录类型的变量的内存分配方式：以记录变量的 域为单位分配存储单元 由于记录类型变量各个域的类型可能不同，所以每 个域分配到的存储单元的数目可能不同 记录类型变量的相邻域在内存中也是相邻的

139 6.5.3 记录成分的引用 1、访问记录的特定域：点域法
在多数情况下，我们按一个特定条件处理一个记 录的每一个域。Pascal语言规定，用点域法来访 问记录的某个域： 记录名.域名 例如：st1.age st2.sex 域变量又被称为成分变量。域变量的使用与一般 变量的使用相同

140 6.5.3 记录成分的引用 2、with语句 当每一次访问记录的域时，都要写出其记录名，显得很烦琐。Pascal语言提供With语句（开域语句），可以简化程序的书写，使程序更加清晰易读，提高了程序的效率 with语句的语法 , do 记录标识符 语句 with ; with语句

141 6.5.3 记录成分的引用 例如，若有下面的变量说明： var r1,r2:record a:integer; b:real;
end; 利用点域法给r1赋值： r1.a:=10; r1.b:=0.01; r1.c:=20; 利用with语句给r1赋值为： with r1 do begin a:=10; b:=0.01; c:=20

142 6.5.3 记录成分的引用 with语句的几点说明： ①with语句是构造型语句，保留字do之后的语句通常叫做限定语句。限定语句不得改变已开域的记录 例如with语句: with r do 语句S； 执行时，语句S不能影响r。下面的with语句是错误的： with a[i] do begin … i:=i+1; end; 因为i:=i+1;语句改变了a[i]，所以程序不能正常运行

143 6.5.3 记录成分的引用 ②with语句可以嵌套，但嵌套的层次是有限制的，不同的Pascal语言的版本有不同的规定
with r1 do with r2 do … with rn do 语句S； 其等价形式为： with r1,r2, …,rn do

144 6.5.4 记录类型数据允许进行的运算 1、记录类型数据的整体运算
记录类型的数据整体允许进行赋值运算，可以作 为过程或函数的参数进行传递，其它运算都不允 许

145 允许将一个记录类型变量整体赋给另一个同类型的记录变量，这一操作被称为记录拷贝
例如，若有下面的变量说明： var r1,r2: record a:integer; b:real; c:1..10; end; 假设r1已经被赋值，则下面的记录拷贝是正确的： r2:=r1; 作为参数进行传递 记录可以作为过程或函数的参数进行传递，传递时实在参数与形式参数必须是同一记录类型

146 6.5.4 记录类型数据允许进行的运算 2、记录的成分（域）数据允许进行的运算
记录类型的数据是由其成分类型的数据构造而成的， 因此一般是讨论其成分（域）数据所允许进行的运 算，亦即，一般是对成分施加运算 域能进行其数据类型所允许进行的运算 记录类型继承了其域类型所允许进行的运算

147 6.5.5 记录类型的数据的输入与输出 记录类型数据不能直接用read、write语句进行输 入输出，只能对其域进行输入与输出（枚举型域除 外） 例如：var st1,st2: record name:packed array [1..20] of char; sex:(female,male); age:integer end; 语句read(st1.age)是合法的，而write(st2.sex)是不合法的， 因为枚举类型的变量不能直接进行输入与输出

148 6.5.6 记录数组 当数组类型的基类型是记录类型时，我们称该数组类型为记录数组类型(Record Array Type)
记录数组类型说明及其变量说明与数组类型相同 数组类型的基类型——记录类型的说明要先于数组类型 数组类型元素的访问方法是数组元素和记录域的访问方法的结合

149 例13 假设某班共30个学生，每一个学生的信息可以用（name, sex, age）描述，写一个程序，求该班学生的平均年龄
分析 欲解决该问题，则必须将题目中的数据描述如下： 每个学生的信息可以用一个记录类型数据(student)表示，整个班的30名学生的信息可以利用数组(Class)实现聚集 type student=record name:packed array [1..20] of char; sex:(female,male); age:integer end; class=array [1..30] of student; 该问题已知30个学生的年龄，求其平均年龄。显然只要求出 30个学生年龄的总和，该问题就很容易得到解决了。“求30 个学生年龄的总和”是一个求和问题，按照求和问题进行程 序设计即可

150 6.5.6 记录数组 算法 根据题意，该问题的算法如下： ① 输入30个学生的年龄 ② 求30个学生年龄的总和 ③ 求30个学生平均年龄
④ 输出平均年龄

151 源程序 Program AverageAge(input, output); Type student=record
name:packed array [1..20] of char; sex:(female,male); age:integer end; class=array [1..30] of student; Var cl: class; sumage,aveage: real; i,j: integer; Begin for i:=1 to 30 do read(cl [i].age); sumage:=0; for j:=1 to 30 do sumage:=sumage+cl [j].age; aveage:=sumage/30; write(′the average age is :′,aveage); Bnd.

152 6.5.7 变体记录 1、引言 前面我们看到记录类型变量在程序运行期间，记录域的个数及每个域的数据类型都是固定不变的
即对变量各域的访问方式及变量的内存分配都是不变的 但实际的数据对象常常有这样的情况：记录变量的一部分域是固定的。而另一部分域则是随情况的不同而有选择地变化 为了描述这样的数据对象，Pascal语言提供了变体记录(Variant Record) 变体记录类型的数学基础是集合论中分离并集 (Discriminated Union)的概念

153 6.5.7 变体记录 2、变体记录类型说明 语法 case 标志域名 标志域类型 of : 常量 （ , ; ） 域表 变体部分

154 6.5.7 变体记录 语义：定义一个变体记录类型 例如：定义一个某厂职工的记录类型：固定部分含有2个域：姓名，性别；一个变体部分：婚姻状况变体记录。 婚姻状况由婚否这一项决定。若已婚则要定义其结婚年龄和有否小孩，否则定义该职工的年龄 name sex married yes: marriedage , havechild no: age Li F 5 yes1 Wang M 23

155 6.5.7 变体记录 该厂职工的记录类型定义: Type mt=(yes, no); child=(yes1, no1);
staff=record name: packed array [1..20] of char; sex: (female, male); case married : mt of yes: (marriedage:integer; havechild:child); no: (age:integer) end;

156 6.5.7 变体记录 附注 ①在一记录中可以只有固定部分，或只有变体部分，也可 以两者都有 若两者都有，则须先说明固定部分，再说明变体部分
变体部分须放在整个记录的最后，且只能有一个 ②变体标志域只能是枚举型、字符型、整型等有序类型 ③变体域表必须括在一对圆括号中，若变体域表为空，则 表示没有域，但空括号不能去掉 ④由case开始的变体部分不要求有单独的end与其匹配， 变体部分最后的end实际上就是record的end

157 6.5.7 变体记录 3、变体记录类型的变量说明 变体记录类型的变量由变体记录标识符说明
例如：有变量说明：var st1,st2:staff; 变体记录类型的说明与变体记录类型的变量说明可以合并。上例可以合并为： var st1, st2: record name:packed array [1..20] of char; sex:(female,male); case married :mt of yes1:(marriedage:integer;havechild:child); no1: (age:integer) end;

158 6.5.7 变体记录 4、数据访问的方法 变体记录数据的访问是指变体域的访问。常借助 case语句实现对变体域的访问
例14是一个读含变体的记录类型的数据的实例 例15给出了一个输出含变体的记录类型数据的实例

159 6.5.7 变体记录 例14 读staff变体记录类型的数据的过程

160 Procedure readstaff(var st1:staff); var ch, ch1,ch2,ch3:char; begin readln(st1.name); readln(ch1); case ch1 of ˊfˊ: st1.sex:=female; ˊmˊ: st1.sex:=male; end; with st1 do read(ch2); case ch2 of ˊyˊ: married:=yes; ˊnˊ: married:=no; case married of yes: begin readln(marriedage); {marriedage是整型，直接读} readln(ch3); {havechild 是枚举型 ，间接读} case ch3 of ˊyˊ:havechild:=yes1; ˊnˊ:havechild:=no1; no:readln(Age); read( ch); while ord(ch)<>10 do begin st1.name[i]:=ch; read(ch) end;

161 6.5.8 程序设计举例 例15 选美比赛。在选美大奖赛的半决赛现场，有一批选手参加比赛，比赛的规则是：最后得分越高，名次越低。当半决赛结束时，要在现场按照选手的出场次序宣布最后得分和最后名次，获得相同分数的选手具有相同的名次，名次连续编号，不用考虑同名次的选手人数。例如： 选手序号： 1，2，3，4，5，6，7 选手得分： 5，3，4，7，3，5，6 输出名次为：3，1，2，5，1，3，4 请写一个程序帮助大奖赛组委会完成半决赛的评分排名工作

162 分析 本题实质上是已知每个选手的序号和得分，求每个选手的名次
要求得分相同的选手，名次相同。每个选手有三个方面的 信息：序号、 得分和名次。引入记录数组sebeauty来表示 每个选手的信息，每个元素含上述有三个域 该问题的计算过程: 记录数组sebeauty初始化（每个元素的“名次”域的值 先为0，表示该元素名次未处理） 计算每个元素的名次，最后输出其结果 计算名次的方法: 从头开始扫描记录数组，对没有处理名次的元素进行处理：查 找未处理名次的得分最小的元素记录其下标，同时查找与该元 素得分相等的元素，记录其下标，处理这些元素的名次 如此继续，直到将记录数组的每个元素的名次全部处理完为止

163 例15 选美比赛 算法 ① 输入记录数组sebeauty的每个元素的序号 和得分域值;
④ 输出记录数组sebeauty。将记录数组sebeauty按照序号 域排列

164 第③步可以细化如下 rank:=1; {名次计数器初始化} for i:=1 to n do {扫描整个数组，每次处理一个名次} if sebeauty[i].place=0 then {找尚未处理名次的元素} begin smallest:=sebeauty[i].score; equalnum:=[i]; {对记录同名次元素的集合初始化} for j:=1 to n do {查找得分最小元素及得分相同的元素} if sebeauty[i].place=0 and j<>i then if sebeauty[j].score<smallest then begin smallest:=sebeauty[j].score; equalnum:=[j] {对记录同名次元素集合重新初始化} end else if sebeauty[j].score=smallest then equalnum:=equalnum+[j]; {记录得分相同元素的下标} for k:=1 to n do {对同名次元素赋名次值} if k in equalnum then sebeauty[k].place:=rank; rank:=rank+1; {名次加1} end;

165 例15 选美比赛 源程序 Program selectbeauty(input,output); const n=10;
type beauty=record no:integer; score:integer; place:integer end; beauties=array [1..n] of beauty; eqplamun=set of [1..n]; var sebeauty: beauties; equalnum: eqplamun; i,j,k,rank: integer;

166 Begin for i:=1 to n do begin read(sebeauty[i]. no, sebeauty[i]
Begin for i:=1 to n do begin read(sebeauty[i].no, sebeauty[i].score); sebeauty[i].place:=0 end; rank:=1; if sebeauty[i].place=0 then smallest:=sebeauty[i].score; equalnum:=[i]; for j:=i+1 to n do if sebeauty[j].score<smallest then smallest:=sebeauty[j].score; equalnum:=[j] end else if sebeauty[j].score=smallest then equalnum:=equalnum+[j];

167 例15 选美比赛 for k:=1 to n do if k in equalnum then sebeauty[k].place:=rank; rank:=rank+1; end; for i:=1 to n do writeln(sebeauty[i].no,sebeauty[i].score, sebeauty[i].place); End.

168 6.5.8 程序设计举例 例16 分房问题。按房间容量从小到大的次序输入20个房间号及房间容量，组成记录数组。再输入若干班号及各班人数，当输入的班号为0结束输入。对于每个班，依输入次序按人数分配最合适的房间。输出班级，人数，有无房间分配给该班，及分配房间号，容量（人数）。注意，一个房间只能分配给一个班，一个班也只能分配一个房间。

169 例16 分房问题 分析 根据题意可知，该问题属于查找问题，因此该问题的程序设计策略为穷举策略 为了解决该问题，如何组织数据呢？
可以定义两个记录数组 第一个记录数组的每一个记录应该包括房间号、容量及该房间是否已经分配三个域 第二个记录数组的每一个记录应该包括班号、人数及有无房间分配给该班、及分配房间号、容量几个域，而且该记录中应该有固定部分和变体部分

170 例16 分房问题 算法 ①输入房号及房间容量； ②输入班号及人数； ③ 循环：i从1到n,做 [ j←1；
循环：当(第j个房间容量<第i班人数)或第j个房间已分配，同时j<20,做 j←j+1； 若(第j个房间容量≥第i班人数且第j个房间未分配,则将 第j个房间分配给第i班; 否则 无房间可分； ] ④ 输出分配结果

171 源程序 Program allocationroom(input,output); Const m=20; Type room=record
num,size:integer; allot:boolean end; state=(yes,no); class=record cn, person: integer; case have: state of yes:(rn:integer; rs:integer;); no:( ); Var rooma:array [1..m] of room; classb:array [1..m] of class; i,j,n:integer;

172 Begin writeln(‘input’, m, ‘rooms num, size’); for i:=1 to m do with rooma[i] do begin readln(num,size); allot:=true end; writeln(‘input class cn,person (it’s end ,while cn=0)’); n:=0; repeat n:=n+1; with b[n] do readln(cn, person); until b[n].cn=0; n:=n-1;

173 for i:=1 to n do with classb[i] do begin j:=1; while ((rooma[j]
for i:=1 to n do with classb[i] do begin j:=1; while ((rooma[j].size<person) or (rooma[j].allot=false) and (j<20)) do j:=j+1; with rooma[j] do if (size>=person) and (allot=true) then have:=yes; rn:=num; rs:=size; allot:=false end else have:=no end;

174 for i:=1 to m do with rooma[i] do writeln(num, size, allot); for i:=1 to n do {含变体的记录类型的数据的输出} with classb[i] do begin write(cn,person); case have of yes:writeln(′yes′, rn, rs); no:writeln(′no′) end End.

175 6.6*核心概念讨论之四——聚集概念  任何高级程序设计语言都提供了利用语言用已经 具有的基本数据对象合成复杂数据对象的机制， 这种机制称为聚集(Aggregate)，又称聚合或汇集， 还被称为集成(Integration)，它是分解的逆过程。 聚集是命令-过程型语言的主要特征之一，也是计算机 科学与技术学科的核心概念。 Pascal语言中提供了下列聚集的方法：数组方法、集合 方法、记录方法、递归方法、文件方法，等等 这些聚集方法都有坚实的数学基础

176 6.6*核心概念讨论之四——聚集概念 我们可以根据实际问题的具体情况以及每一种聚集方法的特点，选择相应的聚集方法，来解决实际问题
数组方法: 将相同数据类型的有限数据对象有序的聚集方法 集合方法: 将相同数据类型的有限数据对象无序的聚集方法 记录方法: 将相同或不同数据类型的有限数据对象无序的聚集方法 递归方法: 以有穷聚集无穷的方法，这个聚集的大小是任意增加的 文件方法: 相同数据类型的数据对象的有序的聚集，被聚集的数据对象可以是无限的 我们可以根据实际问题的具体情况以及每一种聚集方法的特点，选择相应的聚集方法，来解决实际问题

177 本章小结 在第二章我们学习了Pascal语言为用户提供的基 本数据类型，在本章我们又学习了Pascal语言所 具有的类型化机制：利用已有的基本数据类型定 义（构造）复合数据类型 Pascal语言允许用户在程序中根据需要定义（构造）枚 举类型、子界类型、数组类型、集合类型和记录类型

178 与数据类型十分密切的另外一个概念是数据结构。
数据结构反映了整个数据内部的构成 一个数据整体由哪些成分数据构成 以什么方式构成 呈现出什么结构 由于程序设计语言中提供的数据类型是由机器硬件或编译系统已经实现，所以可以将数据类型视为语言中已经实现了的数据结构

179 由于Pascal语言提供的较为丰富的基本数据类型和构造数据类型，使得这种语言具有较强的表达能力，这充分地说明了若语言中数据类型越丰富，则其表达能力就越强
但是每一种高级语言不可能穷尽所有的数据类型，因此只有在语言中提供最基本的数据类型，然后在程序层面上根据需求由用户设计并实现出高级语言中所没有的数据类型 这种新构造的类型就是抽象数据类型。从方法论角度来说，这种扩充数据类型的方法是一种内涵方法 关于抽象数据类型的知识，在后续的数据结构和形式语义学中有深入的介绍，这里仅给出其直观的解释。