李晶第4章数据组织数组

1、第4章 数据组织 4.1 数组数组 数组是一组同类型数据的有序集合。数组在内数组是一组同类型数据的有序集合。数组在内存中占有一片连续的存储空间，但可以随机地存中占有一片连续的存储空间，但可以随机地访问数组中的任意一个元素，即数组是顺序存访问数组中的任意一个元素，即数组是顺序存放、随机访问的。放、随机访问的。在一片连续的内存空间中，每一个元素占用的在一片连续的内存空间中，每一个元素占用的空间大小相同空间大小相同(字节数相同字节数相同)，只要知道这片空，只要知道这片空间的起始地址就可以取得任何一个元素的地址，间的起始地址就可以取得任何一个元素的地址，也就很容易取或存某个元素的值。也就很容易取或存某

2、个元素的值。4.1.1 一维数组一维数组 n一维数组与内存空间的组织形式一样，是线性排列一维数组与内存空间的组织形式一样，是线性排列的，每一个数据元素用一个下标索引。的，每一个数据元素用一个下标索引。 n【例【例4-1】 输入输入10个整数，再逆序存放，最后输出。个整数，再逆序存放，最后输出。4381052961370123456789数组数组下标下标图图4.1(a) 连续存放数据连续存放数据43810529613712345678i=0j=9图图4.1(b) 用变量用变量i, j分别指向要交换的两个元素分别指向要交换的两个元素, 交换结束交换结束i增增1, j减减1图图4.1 数据存放和逆序

3、操作数据存放和逆序操作438105296137数组数组下标下标0123456789图图4.1(a) 连续存放数据连续存放数据图图4.1(b) 用变量用变量i, j分别指向要交换的两个元素分别指向要交换的两个元素, 交换结束交换结束i增增1, j减减14381052961370123456789i=0j=9【说明】【说明】 整体定义整体定义数组是一种构造类型的数据，在使用数组之前必须先数组是一种构造类型的数据，在使用数组之前必须先定义。定义。 一维数组的定义格式：一维数组的定义格式： 数据类型数据类型 数组名数组名数组长度数组长度n数组中每一个元素的数据类型是一样的；数组中每一个元素的数据类型是

4、一样的；n数组名必须符合程序设计语言的标识符的命名规则；数组名必须符合程序设计语言的标识符的命名规则；n数组长度是数组中数据元素的个数，只能是常量表数组长度是数组中数据元素的个数，只能是常量表达式。达式。n数组在内存中占有一片连续的存储空间，数组名就数组在内存中占有一片连续的存储空间，数组名就是这一片空间的首地址。是这一片空间的首地址。单个使用单个使用 在使用数组时，不能使用数组的整体，只能使在使用数组时，不能使用数组的整体，只能使用数组中的个体，即数组中的每个元素，数组用数组中的个体，即数组中的每个元素，数组元素的性质和使用方法与简单变量一样。元素的性质和使用方法与简单变量一样。通过下标通过

5、下标 使用数组元素是通过使用下标来完成的，如程序中使用数组元素是通过使用下标来完成的，如程序中ai，下标是整数表达式，是可以变化的。下标是整数表达式，是可以变化的。下标是从下标是从0开始的，开始的，最大的下标是最大的下标是 “数组长度数组长度”1， 初始化初始化：在定义数组时，也可以同时对数组进行初始化，在定义数组时，也可以同时对数组进行初始化，初始值依次写在初始值依次写在中中,用逗号隔开。用逗号隔开。如如 int x100=100,102，0，105,102 说明了说明了数组数组x的前的前5个元素个元素x0、x1、x2、x3、x4依次为依次为100、102、0、105、102，而其，而其它元

6、素均为它元素均为0。如果要把数组如果要把数组x的全部元素都初始化为的全部元素都初始化为0，则在，则在定义时写成定义时写成int x100=0。n程序中定义了程序中定义了int an=4,3,8,10,5,2,9,6,13,7就意就意味着分配了一片连续的内存空间存放味着分配了一片连续的内存空间存放n个元素个元素(注意：注意：定义数组时，长度必须是常数；如果不给长度，则定义数组时，长度必须是常数；如果不给长度，则长度是初始数据个数长度是初始数据个数)：4381052961370123456789数组数组a图图4.2 数组数组a的存储与初始化的存储与初始化 如果程序中不是用初始化的方法得到数据，而需

7、要如果程序中不是用初始化的方法得到数据，而需要用键盘输入，那么应该一个一个的数据输入。在数用键盘输入，那么应该一个一个的数据输入。在数组中，用循环实现：组中，用循环实现：for(i=0; iaj1则交换则交换每一趟扫描每一趟扫描“沉沉”下一个最大者，下一趟扫描下一个最大者，下一趟扫描就不用扫描到最后一个数了。第就不用扫描到最后一个数了。第i趟扫描只需趟扫描只需要到要到n-i-1就可以了就可以了(i=0,1,n-1)； 两两比较：两两比较：第第j个与第个与第j+1个元素比较个元素比较(j=0,1,n-i-1).总共需要总共需要n-1趟扫描，每一趟都比上一趟少扫描趟扫描，每一趟都比上一趟少扫描一个

8、，因为每一趟扫描都往下一个，因为每一趟扫描都往下“沉沉”了一个最了一个最大的数，这个数已经排在了合适的位置上，不大的数，这个数已经排在了合适的位置上，不再需要扫描再需要扫描.n冒泡排序的冒泡排序的pad图描述如图图描述如图4.4所示：所示：图图4.4 “冒泡排序冒泡排序”的的pad图图ajaj+1i=0in-1i+void sort(int a )j=0jaj则交换则交换排序中排序中“每一个数据每一个数据”是指数据位置，如上面是指数据位置，如上面第第0趟扫描就是第趟扫描就是第0个数据位置个数据位置(比较过程可能比较过程可能交换数据，数据发生了变化，但后面的比较仍交换数据，数据发生了变化，但后面

9、的比较仍然是与第然是与第0个数据比较个数据比较)。一趟扫描得到一个最。一趟扫描得到一个最小者放到了最前面。小者放到了最前面。第第i趟扫描就是第趟扫描就是第i个元素与所有第个元素与所有第j个元素比较个元素比较(j=i+1，i+2，n-1)，可能需要交换。，可能需要交换。数组的名字与下标决定了数组的所有元素。建数组的名字与下标决定了数组的所有元素。建议读者反复练习冒泡排序与选择排序，上机实议读者反复练习冒泡排序与选择排序，上机实现并理解排序思想，画图理解数据在内存中的现并理解排序思想，画图理解数据在内存中的存储形式与变化过程。存储形式与变化过程。选择排序的选择排序的pad图描述如图图描述如图4.5

10、所示：所示：图图4.5 “选择排序选择排序”的的pad图图i=0in-1i+j=i+1j a j 写一个程序，输入一串十六进制数据，输出其写一个程序，输入一串十六进制数据，输出其十进制数。十进制数。【分析】【分析】 n用数组存储输入的十六进制数据，边输入边存用数组存储输入的十六进制数据，边输入边存储，并记录数据长度；储，并记录数据长度；n设一个变量设一个变量digit10存放结果，初值为存放结果，初值为0，从数，从数组读出一个数字字符组读出一个数字字符c,做做digit10 digit10 *16+c对应的数值，对应的数值，最后的最后的s就是想要的结果；就是想要的结果；n注意到十六进制数中有数

11、字字符注意到十六进制数中有数字字符09，还有字母还有字母af和和af，c对应的数对应的数值要相应处理。值要相应处理。4.1.2 二维数组二维数组n二维数组在逻辑上组成一个阵列二维数组在逻辑上组成一个阵列(象线性代数象线性代数里的矩阵里的矩阵)，但在物理上，占用的内存仍然是，但在物理上，占用的内存仍然是一片连续的空间，每一行开头紧接上一行的末一片连续的空间，每一行开头紧接上一行的末尾，每一个数据元素用两个下标索引。在定义尾，每一个数据元素用两个下标索引。在定义二维数组时，规定了行数和每行的列数，所以二维数组时，规定了行数和每行的列数，所以系统知道在什么位置切分每一行。系统知道在什么位置切分每一行

12、。【例【例4-5】打印出以下的杨辉三角】打印出以下的杨辉三角: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 11 5 10 10 5 1【分析】【分析】如果把杨辉三角存成如下形式：如果把杨辉三角存成如下形式：则很容易看出其变化规律：每行第则很容易看出其变化规律：每行第0列的值都为列的值都为1，对角线上，对角线上的元素也都为的元素也都为1；其它元素为上一行的同列和左列元素之和。；其它元素为上一行的同列和左列元素之和。第第0列列第第1列列第第2列列第第0行行第第1行行第第2行行图图4.7 二维数组的存储形式二维数组的存储形式11112113311464115101051如果把这一片存储

13、空间取个名字叫如果把这一片存储空间取个名字叫a, 那么这个那么这个规律可以表达为：规律可以表达为：ai0=aii=1 (i=0，1，2，n-1)aij=ai-1,j+ai-1,j-1 (i=2，3，n-1； j=1，2， i-1)c语言提供了二维数组语言提供了二维数组(所谓二维就是用行号和所谓二维就是用行号和列号才能定位一个数据列号才能定位一个数据)。上面的表达式用。上面的表达式用c表表达为：达为：ai0=aii=1aij=ai-1j + ai-1j-1对于对于i,j的变化可用的变化可用for循环实现。循环实现。上面用两个括号表达了二维数组上面用两个括号表达了二维数组a的元素下标，的元素下标，

14、在引用这些元素之前，必须先定义才能得到这在引用这些元素之前，必须先定义才能得到这样一片空间样一片空间(杨辉三角几乎浪费了一半的空间，杨辉三角几乎浪费了一半的空间，但处理方便但处理方便)。这些数据都是整数，定义为这些数据都是整数，定义为int ann就可以就可以了。注意了。注意n一定是常数。一定是常数。算法：算法： 生成第生成第0列和对角线元素；列和对角线元素； 生成其它元素；生成其它元素； 输出。输出。【说明】【说明】 定义二维数组有三个要素：数组类型、数组定义二维数组有三个要素：数组类型、数组名、数组每一维的长度。行长度名、数组每一维的长度。行长度(行数行数)和列长和列长度度(列数列数)都必

15、须是常数都必须是常数(或常数表达式或常数表达式)，但行，但行数和列数不一定相等。数和列数不一定相等。二维数组的定义格式：二维数组的定义格式：数据类型数据类型 数组名数组名行数行数列数列数 规定行下标和列下标都从规定行下标和列下标都从0开始。如本例的下开始。如本例的下标取值范围从标取值范围从0到到n-1. 引用二维数组的元素时，两维的下标可以是引用二维数组的元素时，两维的下标可以是表达式，但取值范围千万不能超界。表达式，但取值范围千万不能超界。 二维数组元素在内存中仍然是顺序存放的，二维数组元素在内存中仍然是顺序存放的，元素排列的顺序是按行存放。元素排列的顺序是按行存放。 如，数组如，数组int

16、 x34 的的12个元素的存放顺个元素的存放顺序是：序是： x00、x01、x02、x03 x10、x11、x12、x13 x20、x21、x22、x23 3141592653580 1 2 3 列列012行行141362958535内存单元内存单元数组首地址数组首地址 初始化：初始化：二维数组初始化可以像一维数组一样依照存放顺序依二维数组初始化可以像一维数组一样依照存放顺序依次赋值，如：次赋值，如： int x34=0,1,2,3,10,11,12,13,20,21,22,23也可以按行进行赋值，如：也可以按行进行赋值，如： int x34=0,1,2,3,10,11,12,13,20,21

17、,22,23同样，初始化时也可以只给部分元素赋值，如同样，初始化时也可以只给部分元素赋值，如 int x34=1,2 , 0,11,0,13,0,0,0,23甚至，甚至，int x34=0把所有元素的值全部初始化成把所有元素的值全部初始化成0了了!如果初始化时给出了数组的全部初值，可以不指定二如果初始化时给出了数组的全部初值，可以不指定二维数组的行数，但列数在任何情况下都不能省略。维数组的行数，但列数在任何情况下都不能省略。在内存中，数据的物理存储象一条直线一样顺序存放，在内存中，数据的物理存储象一条直线一样顺序存放，如果不告知每一行的列数，那么计算机就不知道从如果不告知每一行的列数，那么计算

18、机就不知道从什么地方一行一行的切分。因此，二维数组什么地方一行一行的切分。因此，二维数组(甚至更甚至更多维的数组多维的数组)实际是逻辑上的划分，在物理上都是一实际是逻辑上的划分，在物理上都是一维的。维的。 再次看到，数组不仅表达数据方便，而且更方便使再次看到，数组不仅表达数据方便，而且更方便使用循环控制。用循环控制。 思考：将本例的结果显示成思考：将本例的结果显示成“等腰三角形等腰三角形”形式，形式，如何修改如何修改?例例 有一个有一个34的矩阵，求出其中最大的元素值的矩阵，求出其中最大的元素值以及所在的行列号以及所在的行列号【分析】用三行四列的二维数组存储矩阵，求【分析】用三行四列的二维数组

19、存储矩阵，求最大元素的过程与求一维数组内最大元素类似，最大元素的过程与求一维数组内最大元素类似，但需要逐行逐列扫描二维数组，而且在记下最但需要逐行逐列扫描二维数组，而且在记下最大元素值的同时要记录其行列号。大元素值的同时要记录其行列号。maxa00row0column0i0i3i+i0imaxmaxaijrowicolumnj输出输出max，i，j【例【例4-6】魔方。在】魔方。在nn方阵里填入数字方阵里填入数字1n2(这里这里n为奇数为奇数)，使每行之和、每列之和、对角线之和都相，使每行之和、每列之和、对角线之和都相等。等。【分析】【分析】图图4.8是是n=5的魔方：的魔方：图图4.8 5x

20、5魔方阵魔方阵15 8124 1716 14 752322 20 13 64321 19 12 109225 18 11把把1,2,3,，25分别找一个合适的位置分别找一个合适的位置放入。其放法如下：放入。其放法如下： 把把1放入第放入第0行中间位置，这个位置行中间位置，这个位置记为记为(0,2) 然后移向左上角位置：如果超出上然后移向左上角位置：如果超出上界但不超左界界但不超左界, 则放在左边一列最下则放在左边一列最下一行。一行。2放在了放在了(4, 1)。 继续向左上角移动：继续向左上角移动：3放在放在(3,0)。 再向左上角移动：如果超出左边界，再向左上角移动：如果超出左边界，但不超上界

21、，则放在上一行的最右但不超上界，则放在上一行的最右一列。一列。4放在了放在了(2,4). 再向左上角移动：如果左上角已经再向左上角移动：如果左上角已经存了数，则放在正下方。存了数，则放在正下方。6放在了放在了5的下方。的下方。 如果向左上角移动，既超上界又超如果向左上角移动，既超上界又超边界，则放在正下方。边界，则放在正下方。16放在了放在了15的下方。的下方。图图4.8 5x5魔方阵魔方阵15 8124 1716 14 752322 20 13 64321 19 12 109225 18 11总结起来，用总结起来，用k从从1n2，确定，确定k的位置的位置(i,j)，初，初始始(i,j)=(0

22、,n/2)。每一个数。每一个数k放入以后，下一个放入以后，下一个数的位置向左上角移动，有下列五种情况之一：数的位置向左上角移动，有下列五种情况之一： 既超上界又超左界，下一个位置应该是既超上界又超左界，下一个位置应该是(i+1,j)； 只超上界，下一个位置应该是只超上界，下一个位置应该是(n-1,j-1)； 只超左界，下一个位置应该是只超左界，下一个位置应该是(i-1,n-1)； 不超界但左上角位置已经填过数了，下一个不超界但左上角位置已经填过数了，下一个位置应该是位置应该是(i+1,j)； 正常情况，下一个位置应该是正常情况，下一个位置应该是(i-1,j-1)。第第种情况，如何知道已经填过数呢种情况，如何知道已经填过数呢? 如果事先如果事先将数组所有元素都初始化为将数组所有元素都初始化为0，那么只要不为，那么只要不为0了则表示已填过了。了则表示已填过了。上面的移动理解为，当超上界时可以理解为上上面的移动理解为，当超上界时可以理解为上下边界是连在一起的；当超左界时可以理解为下边界是连在一起的；当超左界时可以理解为左右边界是连在一起的。这样看图形就很容易左右边界是连在一起的。这样看图形就很容易理解下一个位置的行号与列号了。理解下一个位置的行号与列号了。算法：算法： i=0, j=n/2; k从从1