李晶第4章数据组织数组演示教学

《李晶第4章数据组织数组演示教学》由会员分享，可在线阅读，更多相关《李晶第4章数据组织数组演示教学（51页珍藏版）》请在金锄头文库上搜索。

1、第4章 数据组织,4.1 数组,数组是一组同类型数据的有序集合。数组在内存中占有一片连续的存储空间，但可以随机地访问数组中的任意一个元素，即数组是顺序存放、随机访问的。 在一片连续的内存空间中，每一个元素占用的空间大小相同(字节数相同)，只要知道这片空间的起始地址就可以取得任何一个元素的地址，也就很容易取或存某个元素的值。,4.1.1 一维数组,一维数组与内存空间的组织形式一样，是线性排列的，每一个数据元素用一个下标索引。 【例4-1】 输入10个整数，再逆序存放，最后输出。,数组,下标,图4.1(a) 连续存放数据,图4.1(b) 用变量i, j分别指向要交换的两个元素, 交换结束i增1,

2、j减1,i=0,j=9,【说明】 整体定义 数组是一种构造类型的数据，在使用数组之前必须先定义。 一维数组的定义格式： 数据类型 数组名数组长度 数组中每一个元素的数据类型是一样的； 数组名必须符合程序设计语言的标识符的命名规则； 数组长度是数组中数据元素的个数，只能是常量表达式。 数组在内存中占有一片连续的存储空间，数组名就是这一片空间的首地址。,单个使用 在使用数组时，不能使用数组的整体，只能使用数组中的个体，即数组中的每个元素，数组元素的性质和使用方法与简单变量一样。,通过下标 使用数组元素是通过使用下标来完成的，如程序中ai，下标是整数表达式，是可以变化的。 下标是从0开始的， 最大的

3、下标是 “数组长度”1，, 初始化： 在定义数组时，也可以同时对数组进行初始化，初始值依次写在中,用逗号隔开。 如 int X100=100,102，0，105,102 说明了数组X的前5个元素X0、X1、X2、X3、X4依次为100、102、0、105、102，而其它元素均为0。 如果要把数组X的全部元素都初始化为0，则在定义时写成int X100=0。,程序中定义了int aN=4,3,8,10,5,2,9,6,13,7就意味着分配了一片连续的内存空间存放N个元素(注意：定义数组时，长度必须是常数；如果不给长度，则长度是初始数据个数)：, 如果程序中不是用初始化的方法得到数据，而需要用键盘

4、输入，那么应该一个一个的数据输入。在数组中，用循环实现： for(i=0; iN; i+) scanf(%d, 对每一个元素ai就如同前面章节中使用的简单变量一样。 注意：scanf(%d, 定义的同时给全部或部分元素赋初值 int b5=2,5,6,1,0; float x100=1.2 , 2.6 , 3.14 , 4; 定义的同时给全部元素赋初值可以省略数组长度 char digit=a , b , c , d , e , f , g ;,数组的访问 只能访问每个元素 用下标访问每个元素 下标从0数组长度1 循环是常用控制结构,【例4-2】交换两块数据。 如图4.3，把前4个元素与后6个

5、元素整体交换。 【分析】 解题方法很多，如再设一个同样大小的数组作为过渡。 本例题的做法是：先将两块数据分别逆序(例4-1)，再将它们整体逆序即可。这样做有两个好处：一是不需要额外增加存储空间，二是反复使用三次“逆序”。因此，我们将逆序操作定义成一个函数，调用三次即可完成。,【说明】 本程序是交换两块数据很好的方法。 比较printf中使用的格式%3d和%-3d的区别。 程序中调用了三次函数invert，每次调用改变了部分参数即可，这也是函数的优点之一。 已经看到，无论是输出还是逆序数组元素，都必须对数组元素一个一个的处理。处理这些数据最关键的问题是确定元素的下标。,【例4-4】将无符号的整型

6、数据转换为二进制表示。 【分析】 例如无符号整数8的二进制数为1000，无符号整数14二进制数为1110，采用除2取余法,上面的计算过程有一点要特别注意，就是得到的余数不能马上输出，而要等到商为0时才倒过来输出前面的余数。 因此，计算过程把所得到的余数先存起来，最后再输出。可以用足够大的一维数组存放这些余数(一般用不完这个数组的空间)，但必须记住真正占用了多少个数组元素。,一个无符号整数x，用一维数组a存余数,变量n记余数的个数，算法表述为： n = -1; 当x不等于0时，反复做： +n; an = x % 2; x = x/2; 当n0，反复做： 输出an; - - n; 计数器n的初值为

7、什么设为-1呢?有两个好处：如果初值为0，最后n的值比真正的二进制位数多1，或者下标为0的数组元素不能使用；其次是方便第步的输出循环条件。,【说明】 数组a用char型为了节约每个元素占用的空间，因为本例只需要存0或1，而char型的取值范围为-128127，是占用空间最小的数据类型。 数组的名字实际就是这一片空间的首地址(多维数组也一样)，本例也可用指针方式解决。指针就是地址 (参看2.5.2节)，因此，用*a能取到a0的值，*(a+1)就是a1, 当然*(a+i)就是ai。 尽管a是数组的首地址，但一旦定义了数组a，a就固定不变了(如果a可以变的话，找不到这片空间的开始位置，将是什么后果呢

8、?) 用一个指针变量p来跟着数组元素的位置变化，将p的初值设为a, 则*p就是a0，而+p就指向了下一个元素，当然-p就指向了前一个元素。, 以无符号整数8为例，计算结果在内存中的存储形式可以表示为： 指针变量p开始时与a指向同一个地方(就是a0)；上图是处理结束时指针变量p指向了二进制数的最后一个元素；而第0个元素之所以不用，是因为输出的时候p倒过来遇到了a作为结束条件。, 用指针遍历数组比用下标速度快。本例主要目的是让读者再次理解指针概念，因为指针是C语言的精华。 思考：*p- - 与(*p)- - 各是什么含义 ?,【例4-3】随机产生10个整数，用冒泡排序法从小到大排序。 【分析】 随

9、机产生数据(例3-15)相当于输入数据，是为处理(排序)作准备的。为了检验排序的结果，把原始数据和排序后的数据都显示出来。 首先，用数组存储N个数据，一个一个地存入数组元素，元素下标用变量(如i)从0变化到N-1； 其次，一个一个地显示(仿例4-1)； 再其次，排序； 最后，再一次显示。 本题的核心工作是“排序”。用冒泡法将这N个数据从小到大存储，即按升序排序。,所谓冒泡法是：相邻两个数据进行比较，较小的数交换到前面。 例如，10个数据：4，3，8，10，5，2，9，6，13，7 第0趟扫描(红色的两个数正在比较)：,3 4 8 5 2 9 6 10 7 13,第0趟：01 12 23 34

10、45 56 67 78 89 第1趟：01 12 23 34 45 56 67 78 第2趟：01 12 23 34 45 56 67 第8趟：01 i从0到N11（8）做9趟： 每一趟内： j从0到N1i1做：如果ajaj1则交换,每一趟扫描“沉”下一个最大者，下一趟扫描就不用扫描到最后一个数了。第i趟扫描只需要到N-i-1就可以了(i=0,1,N-1)； 两两比较：第j个与第j+1个元素比较(j=0,1,N-i-1). 总共需要N-1趟扫描，每一趟都比上一趟少扫描一个，因为每一趟扫描都往下“沉”了一个最大的数，这个数已经排在了合适的位置上，不再需要扫描.,冒泡排序的PAD图描述如图4.4所

11、示：,【说明】 本程序分出了三块：产生数组(GenRnd)、排序(Sort)、输出数组(output)，定义了三个子函数，在主函数中显得逻辑更清晰。 数组在函数中作为参数，定义时可以不要长度(如写成a )。其实，子函数只需要知道数组的类型和开始位置(数组名就是数组的起始地址)。 调用函数的实际参数，只需要将数组的起始地址告诉子函数，如Sort(a)。 思考：如果要从大到小(降序)排序，如何修改程序?, 排序的方法很多，常用的还用选择排序：每一个数据都与其后面的所有数据比较，大小不合适就交换。 例如：从小到大排4， 3， 8， 10， 5， 2， 9， 6， 13， 7 第0趟扫描(红色的两个数

12、比较)：,2 4 8 10 5 3 9 6 13 7,第0趟：01 02 03 04 05 06 07 08 09 第1趟： 12 13 14 15 16 17 18 19 第2趟： 23 24 25 26 27 28 29 第8趟： 89 i从0到N11（8）做9趟： 每一趟内： j从i1到N1做：如果aiaj则交换,排序中“每一个数据”是指数据位置，如上面第0趟扫描就是第0个数据位置(比较过程可能交换数据，数据发生了变化，但后面的比较仍然是与第0个数据比较)。一趟扫描得到一个最小者放到了最前面。 第i趟扫描就是第i个元素与所有第j个元素比较(j=i+1，i+2，N-1)，可能需要交换。 数

13、组的名字与下标决定了数组的所有元素。建议读者反复练习冒泡排序与选择排序，上机实现并理解排序思想，画图理解数据在内存中的存储形式与变化过程。,选择排序的PAD图描述如图4.5所示：,ai a j ,写一个程序，输入一串十六进制数据，输出其十进制数。 【分析】 用数组存储输入的十六进制数据，边输入边存储，并记录数据长度； 设一个变量digit10存放结果，初值为0，从数组读出一个数字字符c,做digit10 digit10 *16+c对应的数值，最后的S就是想要的结果； 注意到十六进制数中有数字字符09，还有字母af和AF，c对应的数值要相应处理。,4.1.2 二维数组,二维数组在逻辑上组成一个阵

14、列(象线性代数里的矩阵)，但在物理上，占用的内存仍然是一片连续的空间，每一行开头紧接上一行的末尾，每一个数据元素用两个下标索引。在定义二维数组时，规定了行数和每行的列数，所以系统知道在什么位置切分每一行。,【例4-5】打印出以下的杨辉三角: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1,【分析】 如果把杨辉三角存成如下形式： 则很容易看出其变化规律：每行第0列的值都为1，对角线上的元素也都为1；其它元素为上一行的同列和左列元素之和。,如果把这一片存储空间取个名字叫a, 那么这个规律可以表达为： ai0=aii=1 (i=0，1，2，N-1) aij=a

15、i-1,j+ai-1,j-1 (i=2，3，N-1； j=1，2， i-1) C语言提供了二维数组(所谓二维就是用行号和列号才能定位一个数据)。上面的表达式用C表达为： ai0=aii=1 aij=ai-1j + ai-1j-1 对于i,j的变化可用for循环实现。,上面用两个括号表达了二维数组a的元素下标，在引用这些元素之前，必须先定义才能得到这样一片空间(杨辉三角几乎浪费了一半的空间，但处理方便)。 这些数据都是整数，定义为int aNN就可以了。注意N一定是常数。 算法： 生成第0列和对角线元素； 生成其它元素； 输出。,【说明】 定义二维数组有三个要素：数组类型、数组名、数组每一维的长

16、度。行长度(行数)和列长度(列数)都必须是常数(或常数表达式)，但行数和列数不一定相等。 二维数组的定义格式： 数据类型 数组名行数列数 规定行下标和列下标都从0开始。如本例的下标取值范围从0到N-1. 引用二维数组的元素时，两维的下标可以是表达式，但取值范围千万不能超界。, 二维数组元素在内存中仍然是顺序存放的，元素排列的顺序是按行存放。 如，数组int X34 的12个元素的存放顺序是： X00、X01、X02、X03 X10、X11、X12、X13 X20、X21、X22、X23,内存单元, 数组首地址, 初始化： 二维数组初始化可以像一维数组一样依照存放顺序依次赋值，如： 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,22,23 同样，初始化时也可以只给部分元素赋值，如