第4章 数据组织

1、第第4章章 数据组织数据组织高级语言程序设计高级语言程序设计本章内容本章内容高级语言程序设计高级语言程序设计提示：提示： 数组：把相同类型的一批数据放在连续的一片空间；数组：把相同类型的一批数据放在连续的一片空间； 字符串：特殊的数组字符串：特殊的数组字符类型、结束标志。字符类型、结束标志。 结构体：把不同类型的数据放在一起，作为一个数据结构体：把不同类型的数据放在一起，作为一个数据单位。单位。重点：重点： 构造数据类型的定义、引用构造数据类型的定义、引用数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；举例：对输入的

2、举例：对输入的5个整数排序。个整数排序。 用用5个简单变量。个简单变量。 用数组。用数组。数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；说明：说明： “类型类型”可以是任何类型；可以是任何类型； “数组名字数组名字”是标识符；是标识符； “长度长度”是元素个数，也就是同是元素个数，也就是同“类型类型”的数的数据个数；据个数； “长度长度”必须是常数！必须是常数！数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-1 输入输入10个数，

3、再逆序存放。个数，再逆序存放。4381052961370123456789数组数组下标下标数组，数组，就是放的一组数据，每个数据是一个元素。就是放的一组数据，每个数据是一个元素。下标，下标，就是元素在数组中的位置，从就是元素在数组中的位置，从0开始连续编号。开始连续编号。引用，引用，实际上是使用元素，而元素是由下标决定的。实际上是使用元素，而元素是由下标决定的。数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-1 输入输入10个数，再逆序存放。个数，再逆序存放。4381052961370123456789数组数

4、组下标下标逆序，逆序，只需要最前一个元素与最后一个元素交换；只需要最前一个元素与最后一个元素交换； 再次前与次后的元素交换再次前与次后的元素交换数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-1 输入输入10个数，再逆序存放。个数，再逆序存放。4381052961370123456789数组数组下标下标如果数组名为如果数组名为a, 长度为长度为N，下标，下标i初值为初值为0，下标，下标j初值为初值为N-1,则则 重复做重复做： (重复的条件是什么？不能永远重复吧？！重复的条件是什么？不能永远重复吧？！) ai

5、与与aj交换，然后交换，然后+i, -j数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-1 输入输入10个数，再逆序存放。个数，再逆序存放。4381052961370123456789数组数组下标下标定义数组的长度必须是常数，那么定义数组的长度必须是常数，那么元素的下标可以不是常数吗？元素的下标可以不是常数吗？元素的下标可以是表达式吗？元素的下标可以是表达式吗？数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-1 输入输入10

6、个数，再逆序存放。个数，再逆序存放。4381052961370123456789数组数组下标下标定义数组并初始化，例如：定义数组并初始化，例如：int a10=4,3,8,10,5,2,9,6,13,7;数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-1 输入输入10个数，再逆序存放。个数，再逆序存放。4381052961370123456789数组数组下标下标int a10=4,3,8,10,5,2,9,6;这这10个数据是什么呢？个数据是什么呢？数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形

7、式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-1 输入输入10个数，再逆序存放。个数，再逆序存放。00000000000123456789数组数组下标下标想让所有的元素的初值都为想让所有的元素的初值都为0，怎么做？，怎么做？数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-1 输入输入10个数，再逆序存放。个数，再逆序存放。4381052961370123456789数组数组下标下标输入一个数组怎么做？输入一个数组怎么做？输出一个数组怎么做？输出一个数组怎么做？数组数组高级语言程序设

8、计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-1 输入输入10个数，再逆序存放。个数，再逆序存放。4381052961370123456789数组数组下标下标输入一个数组怎么做？输入一个数组怎么做？输出一个数组怎么做？输出一个数组怎么做？其实，每个数组其实，每个数组元素就是一个简单变量元素就是一个简单变量。数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-3 随机产生随机产生10个元素，从小到大排序。个元素，从小到大排序。常用的两种排序方法：常用

9、的两种排序方法： 选择排序选择排序 冒泡排序冒泡排序数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-3 随机产生随机产生10个元素，从小到大排序。个元素，从小到大排序。常用的两种排序方法：常用的两种排序方法： 选择排序选择排序 程序程序数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-3 随机产生随机产生10个元素，从小到大排序。个元素，从小到大排序。常用的两种排序方法：常用的两种排序方法： 冒泡排序冒泡排序438105296

10、137348105296137348529610713438105296137348510296137348521096137348529106137348529610137数组数组高级语言程序设计高级语言程序设计一维数组定义的一般形式：一维数组定义的一般形式： 类型类型 数组名字数组名字长度长度；例例4-3 随机产生随机产生10个元素，从小到大排序。个元素，从小到大排序。常用的两种排序方法：常用的两种排序方法： 冒泡排序冒泡排序 程序程序数组数组高级语言程序设计高级语言程序设计小结：小结： 数组占用连续的一片空间；数组占用连续的一片空间； 数组名字就是这片空间的起始地址；数组名字就是这片空间

11、的起始地址； 数组元素由下标引用；数组元素由下标引用； 逐个访问数组元素；逐个访问数组元素； 数组通常有利于循环处理。数组通常有利于循环处理。作业：作业：4.2, 4.4一维数组一维数组高级语言程序设计高级语言程序设计回顾：回顾： 一维数组：只有一个下标；一维数组：只有一个下标； 数组的特征：连续存放、类型相同；数组的特征：连续存放、类型相同； 数组起始地址：数组名；数组起始地址：数组名； 数组元素由下标引用，下标从数组元素由下标引用，下标从0开始。开始。 一维数组一维数组高级语言程序设计高级语言程序设计本课内容提示：本课内容提示： 数组下标不能超界；数组下标不能超界； 数组与循环联合；数组与

12、循环联合； 数组的输入、输出；数组的输入、输出； 输入：随机数产生大批量数据；输入：随机数产生大批量数据； 数组名作为函数参数。数组名作为函数参数。 一维数组一维数组高级语言程序设计高级语言程序设计习题习题4.2：插入排序。：插入排序。 算法思想算法思想: (1)找新数据插入位置；找新数据插入位置；找位置条件：当a j x时停止此时的j就是插入x的位置。for( j=0; j x ) break; 136915a4x一维数组一维数组高级语言程序设计高级语言程序设计习题习题4.2：插入排序。：插入排序。 算法思想：算法思想：(1)找新数据插入位置；找新数据插入位置；(2)移动数据，腾出空间；移动

13、数据，腾出空间；for( j=0; j x ) break; 136915a4x 1596for( k=i; kj; k-) a k = a k-1;ji一维数组一维数组高级语言程序设计高级语言程序设计习题习题4.2：插入排序。：插入排序。 算法思想：算法思想：(1)新数据找插入位置；新数据找插入位置；(2)移动数据，腾出空间；移动数据，腾出空间；(3)插入数据插入数据for( j=0; j x ) break; 136a4x 1596for( k=i; kj; k-) a k = a k-1;ja j = x;44一维数组一维数组高级语言程序设计高级语言程序设计习题习题4.2：插入排序。：插

14、入排序。 算法思想：算法思想：for(i=0; iN; i+) 输入一个输入一个x (1) 新数据找插入位置；新数据找插入位置； (2) 移动数据，腾出空间；移动数据，腾出空间； (3) 插入数据插入数据for(i=0; iN; i+) scanf(“%d”, &x); for( j=0; j x ) break; for( k=i; kj; k-) a k = a k-1; aj = x; 输入第输入第0个数据能正常处理吗？个数据能正常处理吗？一维数组一维数组高级语言程序设计高级语言程序设计习题题习题题4.4：杨辉三角。：杨辉三角。11 11 2 11 3 3 11 4 6 4 1规

15、律规律：第：第0列、对角线都为列、对角线都为1 其它地方：上面其它地方：上面+左上左上一维数组一维数组高级语言程序设计高级语言程序设计习题题习题题4.4：杨辉三角。：杨辉三角。11 11 2 11 3 3 11 4 6 4 1第第i行：行：a0 = ai = 1;for(j=1; j0; j-) a j = a j + a j-1; 一维数组一维数组高级语言程序设计高级语言程序设计例题例题4-2：交换数组两块数据。：交换数组两块数据。 算法思想。算法思想。 一维数组一维数组高级语言程序设计高级语言程序设计例题例题4-2：交换数组两块数据。：交换数组两块数据。 数组名作为函数参数，数组名作为函数

16、参数， 就是把数组起始地址传给函数。就是把数组起始地址传给函数。 关心关心: 地址。地址。 一维数组一维数组高级语言程序设计高级语言程序设计例题例题4-2：交换数组两块数据。：交换数组两块数据。 引申习题引申习题4.1 一维数组一维数组高级语言程序设计高级语言程序设计例题例题4-3：冒泡排序。：冒泡排序。 数据已经有序了，数据已经有序了， 能不能提前结束排序工作？能不能提前结束排序工作？ for( i=0; iN-1; i+) /扫描趟数扫描趟数 for( j=0; jN-i-1; j+) /其中一趟其中一趟 if( a j 与与 a j+1 反序反序 ) 交换；交换；一维数组一维数组高级语言

17、程序设计高级语言程序设计例题例题4-3：冒泡排序。：冒泡排序。 数据已经有序了，数据已经有序了， 能不能提前结束排序工作？能不能提前结束排序工作？ for( i=0; iN-1; i+) /扫描趟数扫描趟数 for( j=0; jN-i-1; j+) /其中一趟其中一趟 if( a j 与与 a j+1 反序反序 ) 交换；交换； 如果这一趟没有交换过，则退出排序；如果这一趟没有交换过，则退出排序；一维数组一维数组高级语言程序设计高级语言程序设计例题例题4-3：冒泡排序。：冒泡排序。for( i=0; iN-1; i+) /扫描趟数扫描趟数 for( j=0; jaML=0LM+1一维数组一维

18、数组高级语言程序设计高级语言程序设计习题习题4.3：折半查找：折半查找(二分查找二分查找)。速度最快速度最快的查找！的查找！查找条件是：数据查找条件是：数据必须有序必须有序！75xR=9M=7100201312423534645756857918989aL=5一维数组一维数组高级语言程序设计高级语言程序设计习题习题4.3：折半查找：折半查找(二分查找二分查找)。速度最快速度最快的查找！的查找！查找条件是：数据查找条件是：数据必须有序必须有序！75xR=9M=7100201312423534645756857918989aL=5xaMRM-1一维数组一维数组高级语言程序设计高级语言程序设计习题习

19、题4.3：折半查找：折半查找(二分查找二分查找)。速度最快速度最快的查找！的查找！查找条件是：数据查找条件是：数据必须有序必须有序！75xR=6M=7100201312423534645756857918989aL=5xaMLM+1一维数组一维数组高级语言程序设计高级语言程序设计习题习题4.3：折半查找：折半查找(二分查找二分查找)。速度最快速度最快的查找！的查找！查找条件是：数据查找条件是：数据必须有序必须有序！75xR=6M=6100201312423534645756857918989aL=6x=aM返回返回M（6）一维数组一维数组高级语言程序设计高级语言程序设计习题习题4.3：折半查找

20、：折半查找(二分查找二分查找)。算法算法: (假设数据不减有序假设数据不减有序) (1) 当当LR, 重复做：重复做： 求求M=(L+R)/2; 如果如果x=aM, 则返回则返回M; 如果如果xaM, 则则R=M-1; 否则否则 L=M+1; (2) 返回返回-1(表示查找失败表示查找失败)一维数组一维数组高级语言程序设计高级语言程序设计小结：小结： 一维数组的特性？一维数组的特性？ 下标范围？下标范围？ 定义数组并初始化？数组的长度必须是常数！定义数组并初始化？数组的长度必须是常数！ 数组作为函数参数数组作为函数参数 数组的起始地址数组的起始地址 二维数组二维数组高级语言程序设计高级语言程序

21、设计 与一维数组有相同的特征！与一维数组有相同的特征！ 有两个下标，下标都是从有两个下标，下标都是从0开始开始 定义二维数组：定义二维数组： 类型类型 名字名字长度长度长度长度; 二维数组二维数组高级语言程序设计高级语言程序设计例如：例如： int a32;在内存中排列为在内存中排列为: (一条线一条线) a00, a01,a10,a11,a20, a21在逻辑上，视为在逻辑上，视为3行行2列列: (一张表一张表) a00, a01, a10, a11, a20, a21 二维数组二维数组高级语言程序设计高级语言程序设计例题例题4-5：杨辉三角：杨辉三角： 111121133114641151

22、0 10 51第第0行行第第1行行第第2行行第第3行行第第4行行第第5行行第第0列列第第1列列第第2列列第第3列列第第4列列第第5列列二维数组二维数组高级语言程序设计高级语言程序设计例题例题4-5：杨辉三角：杨辉三角(1)生成一张表；生成一张表；(2)输出。输出。 生成一张表生成一张表a:第第i行：行：i从从0到到N-1 ai0 = aii = 1; 第第j列：列：j从从?到到？ a i j = a i-1 j + a i-1 j-1;第第0行能正确处理吗？行能正确处理吗？第第0列能正确处理吗？列能正确处理吗？其它元素需要初始化吗？其它元素需要初始化吗？二维数组二维数组高级语言程序设计高级语言

23、程序设计例题例题4-6：魔方：魔方(1)填数填数(2)输出输出 二维数组二维数组高级语言程序设计高级语言程序设计小结：小结： 二维数组存储的二维数组存储的物理形式物理形式、逻辑形式逻辑形式。作业：作业： 习题习题4.5, 4.6二维数组二维数组高级语言程序设计高级语言程序设计回顾：回顾： 1、二维数组的定义：、二维数组的定义： 类型类型 数组名数组名行数行数列数列数; 行数、列数必须是常数！行数、列数必须是常数！ 2、二维数组存储的形式。、二维数组存储的形式。 3、定义二维数组中的、定义二维数组中的“列数列数”更重要！更重要！ 4、二维数组的元素有两个下标。、二维数组的元素有两个下标。二维数组

24、二维数组高级语言程序设计高级语言程序设计例题例题4-6 魔方魔方 填二维数组；填二维数组； 输出二维数组。输出二维数组。输出二维数组输出二维数组a （假设（假设N行行N列）：列）：for ( i=0; iN; i+) for ( j=0; jN; j+) printf ( “%4d”, a i j ); printf (“n”); 二维数组二维数组高级语言程序设计高级语言程序设计例题例题4-6 魔方魔方 填二维数组；填二维数组； 输出二维数组。输出二维数组。填二维数组填二维数组a ：(向向右上右上方向方向)(1) i = 0; / 准备填数的准备填数的行号行号 j = N/2; / 准备填数的

25、准备填数的列号列号 k = 1; / 准备填数准备填数k(2)当当k=N*N时，循环做：时，循环做： a i j k; 确定下一个确定下一个i, j17241815235714164613202210121921311182529 二维数组二维数组高级语言程序设计高级语言程序设计例题例题4-6 魔方魔方 填二维数组；填二维数组； 输出二维数组。输出二维数组。填二维数组填二维数组a ：(向向右上右上方向方向)(1) i = 0; / 准备填数的准备填数的行号行号 j = N/2; / 准备填数的准备填数的列号列号 k = 1; / 准备填数准备填数k(2)当当k=N*N时，循环做：时，循环做：

26、a i j k; 确定下一个确定下一个i, j确定下一个确定下一个i, j: 如果如果i-1 N-1 /超上界、右界超上界、右界 则则 +i; 18155714164613101231129 二维数组二维数组高级语言程序设计高级语言程序设计例题例题4-6 魔方魔方 填二维数组；填二维数组； 输出二维数组。输出二维数组。填二维数组填二维数组a ：(向向右上右上方向方向)(1) i = 0; / 准备填数的准备填数的行号行号 j = N/2; / 准备填数的准备填数的列号列号 k = 1; / 准备填数准备填数k(2)当当k=N*N时，循环做：时，循环做： a i j k; 确定下一个确定下一个i

27、, j确定下一个确定下一个i, j: 如果如果i-1 N-1 /超上界、右界超上界、右界 则则 +i; 否则否则 如果如果i-10 /只超上界只超上界 则则 i=N-1; +j； 17181557141646131012 3111829 二维数组二维数组高级语言程序设计高级语言程序设计例题例题4-6 魔方魔方 填二维数组；填二维数组； 输出二维数组。输出二维数组。填二维数组填二维数组a ：(向向右上右上方向方向)(1) i = 0; / 准备填数的准备填数的行号行号 j = N/2; / 准备填数的准备填数的列号列号 k = 1; / 准备填数准备填数k(2)当当k=N*N时，循环做：时，循环

28、做： a i j k; 确定下一个确定下一个i, j确定下一个确定下一个i, j: 如果如果i-1 N-1 /超上界、右界超上界、右界 则则 +i; 否则否则 如果如果i-1N-1 /只超右界只超右界 则则 -i; j=0; 17181557141646131012 31129 二维数组二维数组高级语言程序设计高级语言程序设计例题例题4-6 魔方魔方 填二维数组；填二维数组； 输出二维数组。输出二维数组。填二维数组填二维数组a ：(向向右上右上方向方向)(1) i = 0; / 准备填数的准备填数的行号行号 j = N/2; / 准备填数的准备填数的列号列号 k = 1; / 准备填数准备填数

29、k(2)当当k=N*N时，循环做：时，循环做： a i j k; 确定下一个确定下一个i, j确定下一个确定下一个i, j: 如果如果i-1 N-1 /超上界、右界超上界、右界 则则 +i; 否则否则 如果如果i-1N-1 /只超右界只超右界 则则 -i; j=0; 否则否则 如果如果ai-1j+1已有数已有数 则则+i;17181557141646132010121921 3111829 二维数组二维数组高级语言程序设计高级语言程序设计例题例题4-6 魔方魔方 填二维数组；填二维数组； 输出二维数组。输出二维数组。填二维数组填二维数组a ：(向向右上右上方向方向)(1) i = 0; / 准

30、备填数的准备填数的行号行号 j = N/2; / 准备填数的准备填数的列号列号 k = 1; / 准备填数准备填数k(2)当当k=N*N时，循环做：时，循环做： a i j k; 确定下一个确定下一个i, j确定下一个确定下一个i, j: 如果如果i-1 N-1 /超上界、右界超上界、右界 则则 +i; 否则否则 如果如果i-1N-1 /只超右界只超右界 则则 -i; j=0; 否则否则 如果如果ai-1j+1已有数已有数 则则+i; 否则否则 -i; +j;171815571416461320101219 3111829 二维数组二维数组高级语言程序设计高级语言程序设计例题例题4-6 魔方魔

31、方 填二维数组；填二维数组； 输出二维数组。输出二维数组。填二维数组填二维数组a ：(向向右上右上方向方向)(1) i = 0; / 准备填数的准备填数的行号行号 j = N/2; / 准备填数的准备填数的列号列号 k = 1; / 准备填数准备填数k(2)当当k=N*N时，循环做：时，循环做： a i j k; 确定下一个确定下一个i, j确定下一个确定下一个i, j: 如果如果i-1 N-1 /超上界、右界超上界、右界 则则 +i; 否则否则 如果如果i-1N-1 /只超右界只超右界 则则 -i; j=0; 否则否则 如果如果ai-1j+1已有数已有数 则则+i; 否则否则 -i; +j;

32、 +k;17241815235714164613202210121921 311182529二维数组二维数组高级语言程序设计高级语言程序设计例题例题4-6 魔方魔方 填二维数组；填二维数组； 输出二维数组。输出二维数组。填二维数组填二维数组a ：(向向右上右上方向方向)(1) i = 0; / 准备填数的准备填数的行号行号 j = N/2; / 准备填数的准备填数的列号列号 k = 1; / 准备填数准备填数k(2)当当k=N*N时，循环做：时，循环做： a i j k; 确定下一个确定下一个i, j确定下一个确定下一个i, j: 如果如果i-1 N-1 /超上界、右界超上界、右界 则则 +i

33、; 否则否则 如果如果i-1N-1 /只超右界只超右界 则则 -i; j=0; 否则否则 如果如果ai-1j+1已有数已有数 则则+i; 否则否则 -i; +j; +k;17241815235714164613202210121921 311182529为什么要先判断为什么要先判断既超上界又超右界的情况？既超上界又超右界的情况？二维数组二维数组高级语言程序设计高级语言程序设计例题例题4-6 魔方魔方 填二维数组；填二维数组； 输出二维数组。输出二维数组。填二维数组填二维数组a ：(向向右上右上方向方向)(1) i = 0; / 准备填数的准备填数的行号行号 j = N/2; / 准备填数的准备

34、填数的列号列号 k = 1; / 准备填数准备填数k(2)当当k=N*N时，循环做：时，循环做： a i j k; 确定下一个确定下一个i, j确定下一个确定下一个i, j: 如果如果i-1 N-1 /超上界、右界超上界、右界 则则 +i; 否则否则 如果如果i-1N-1 /只超右界只超右界 则则 -i; j=0; 否则否则 如果如果ai-1j+1已有数已有数 则则+i; 否则否则 -i; +j; +k;17241815235714164613202210121921 311182529为什么要先判断为什么要先判断既超上界又超右界的情况？既超上界又超右界的情况？如何表达如何表达“已有数已有数”

35、？二维数组二维数组高级语言程序设计高级语言程序设计习题习题4.6 找鞍点找鞍点 （1）输入一个二维数组；）输入一个二维数组； （2）对每一行）对每一行i 找该行的最小值，保留其列下标找该行的最小值，保留其列下标j； 找第找第j列中最大值列中最大值x 如果如果x=aij, 则输出则输出(i,j,x)注意：同一行中可能有几个最小值！注意：同一行中可能有几个最小值！问题：需要考虑同一列中多个最大值吗？问题：需要考虑同一列中多个最大值吗？二维数组二维数组高级语言程序设计高级语言程序设计例题例题 二维数组行排序二维数组行排序 行与行的大小：行与行的大小：从左向右对应数比较，第一对不相从左向右对应数比较，第一对不相