程序设计基础 教学课件 ppt 作者 C语言 7-10章 第7章

第7章 数 组,7.1 一维数组 7.2 函数间一维数组的传递 7.3 二维数组 7.4 函数间二维数组的传递 习题,7.1 一 维 数 组 7.1.1 数组概述 通过前面的学习，我们知道，如果在程序中需要暂时存放几个数据，就需要定义几个变量。但是，这种方法在处理大批量的同类型的数据的时候，就显得不是很方便了。例如，某个班级有45名同学，在“程序设计基础”这门课程考试结束后，要编写一个程序，统计一下成绩高于平均分的人数。针对这个问题，可以设计出如下算法： 依次接受并暂存45个成绩； 计算总分和平均分；, 置计数器为0； 对每一个成绩，若它大于平均分，则计数器累加1； 输出计数器的值。 按照以上算法的要求，如果在程序中定义45个变量去暂存这45个成绩，显然是一种比较笨拙的办法。 那么，有没有更好的办法呢？其实，针对这种大批量数据的存储问题，C语言中提供了数组这种数据类型来解决。,数组的实质是内存中一段连续的存储空间，例如内存中连续的20个字节的存储空间就可以称为一个数组。这个数组如果用来存放int型的数据，则可以存放10个(若每个int型的数据需要两个字节的存储空间)。此时每两个字节构成数组中一个存储单元，称为数组元素或数组分量；当然，这个数组也可以用于存放5个float型的数据(若每个float型的数据需要4个字节的存储空间)，此时，每4个字节构成一个数组分量。在程序中，数组用一个名字来表示，数组中分量用编号来区分。采用这种方式，不但解决了大批量同类型数据的存储问题，而且方便用循环的方式来对这些数据进行运算和处理。,存放在数组中的多个数据，从逻辑上可以看做是按一个方向排列的，也可以看做是按两个方向排列的。例如20个整数可以看做是按一个方向排列的，在C语言中称为一维数组；这20个整数也可以分为4组，每组5个，在C语言中就称为二维数组。这种情况下，通常仿照数学中行列式的形式，称这20个数构成4行5列的二维数组。当然，一组数也可以看做是按多个方向排列的，这在C语言中就称为多维数组了。,7.1.2 一维数组的定义和初始化 一维数组的定义形式如下： 数据类型 数组名分量个数； 数组名和变量名一样，是C语言中的标识符，必须符合标示符的命名规则。分量个数必须是一个整型数，通常是常量或常量表达式。分量个数表示的数组中存储单元的个数，也就是这个数组中可以最多存放的数据的个数。数据类型用来指定数组中可以存放的数据的类型。例如： int array10;,以上语句，定义array是一个数组，这个数组是用来存放int型数据的，最多可以存放10个int型的数据。 定义了数组之后，如果这个数组是外部数组，则数组中每个分量中存放的都是0，也就是说，每个数组元素的值都是0；如果这个数组是内部数组，则数组中元素的值是随机值。定义数组时，可以把特定的值存放在数组中，这种情况称为数组的初始化，例如： int array10 = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10;,以上语句，定义array是一个有10个元素的int型数组，同时把1，2，3，10这10个数依次存放在数组的10个元素中。当然，也可以对数组进行部分初始化，例如： int array10 = 1, 2, 3; 以上语句，在定义数组的同时，把1、2、3依次存放在数组的第1、第2和第3个元素中，此时，数组中其余元素自动被初始化为0。,7.1.3 一维数组元素的引用 数组在使用中，通常不会做整体的引用，更多的是引用数组中某一个分量中存放的数据。一维数组中的每一个分量都对应一个编号。需要特别注意的是分量的编号是从0开始的，即数组中第一个分量的编号为0，第二个分量的编号为1，依此类推。在程序中，引用数组分量的形式为“数组名编号”，这里的编号为一个取值为int型的表达式。例如，对如下定义的数组： int array10;,如果要将其中的第1个分量赋值为5，则表达为如下语句： array0 = 5; 再例如要将数组array中第3个分量和第4个分量中存放的值求和后，存放在数组的第5个分量中，可使用如下语句： array4 = array2 + array3; 在对数组中存放的数据进行运算和处理时，通常采用循环的方式，例如对于前面提到的成绩统计的问题，可以编写出如下的源程序：,/*源程序7-1*/ #include“stdio.h“ main() float score45, sum, avg; int i, counter; for(i=0; i45; i+) printf(“Palease input score%d:“, i); scanf(“%d“, , sum = 0; for(i=0; i avg) counter +; printf(“counter=%dn“, counter); ,7.1.4 简单排序算法 排序问题是计算机编程中的一个常见问题。在日常的数据处理中，面对大量的数据，也许有成百上千种的处理要求，而这些处理往往是以排序作为前提的。例如查找，在有序的数据中进行查找，当然比在无序的数据中进行查找要容易得多。在计算机发展的历史中，前人为我们留下了很多经典的排序算法，它们都是智慧的结晶。下面就讨论其中比较简单的两种排序算法。首先把排序的问题具体化：假如有10个整数，按照任意次序存放在计算机的一段连续内存(为了描述方便，把这一段连续内存看做是有10个分量的一维数组array)中，我们要做的就是将array数组中的这10个数的存放位置调整为由大到小。,下面先看第一种简单排序方法，选择排序法。 针对前面所描述的问题，可以采用如下算法来解决： (1) 从array0至array9中找出一个最大的数，假如这个数在arraymax_index中，把它交换到数组的第一个位置，即arraymax_index与array0交换； (2) 从array1至array9中找出一个最大的数，假如这个数在arraymax_index中，把它交换到数组的第一个位置，即arraymax_index与array1交换； (3) 从array2至array9中找出一个最大的数，假如这个数在arraymax_index中，把它交换到数组的第一个位置，即arraymax_index与array2交换； ,(9) 从array8至array9中找出一个最大的数，假如这个数在arraymax_index中，把它交换到数组的第一个位置，即arraymax_index与array8交换。 以上的算法，用伪代码的形式描述如下： for ( i=0; i=9; i+) 从arrayi至array9中找出一个最大的数，假如这个数在arraymax_index中， 把它交换到数组的第一个位置，即arraymax_ index与arrayi交换； 我们再把从arrayi至array9中找最大数的算法和交换的算法细化，得到如下算法描述：,for ( i=0; iarraymax_index) max_index = j; if(max_index != i) t = arrayi; arrayi = arraymax_index; arraymax_index = t; ,下面给出一个完整的源程序，程序中的10个数是调用随机函数生成的100以内的数。 /*源程序7-2*/ #include“stdio.h“ #include“stdlib.h“ main() int array10, i, j, t, max_index; for(i=0; i=9; i+) arrayi = rand() % 100;,printf(“Before sorting:n“); for(i=0; iarraymax_index) max_index = j; if(max_index != i),t = arrayi; arrayi = arraymax_index; arraymax_index = t; printf(“nAfter sorting:n“); for(i=0; i=9; i+) printf(“%dt“, arrayi); ,程序运行结果如下： 上面的程序中，每一次都是通过比较先找到最大数所在位置的编号max_index，然后再进行交换。还可以把比较的过程和最后的交换结合起来，也就是在比较的过程中完成交换，这样，源程序可以修改成如下形式：,/*源程序7-3*/ #include“stdio.h“ #include“stdlib.h“ main() int array10, i, j, t; for(i=0; i=9; i+) arrayi = rand() % 100; printf(“Before sorting:n“); for(i=0; i=9; i+) printf(“%dt“, arrayi);,for ( i=0; iarrayi) t = arrayi; arrayi = arrayj; arrayj = t; printf(“nAfter sorting:n“); for(i=0; i=9; i+) printf(“%dt“, arrayi); ,选择排序法之所以叫做选择排序法，就是因为这种方法每次选出一个合适的数，放到合适的位置上。很容易就可以推知，对n个数进行排序，共需要n-1次这样的选择。 下面再来看另一种简单排序算法，这种排序算法有一个非常有趣的名字，叫做冒泡排序。为什么叫做冒泡排序呢？还是以前面给出的问题为例来说明。 要对数组array中存放的10个整数排序，首先对array数组做一遍这样的处理： 从array0至array9，相邻的两个数依次比较，即array0与array1比较，array1与array2比较，array8与array9比较，在比较的过程中，如果前面的数小于后面的数，则交换两个数的位置。,通过这样一遍处理，虽然整个数组还是没有顺序的，但是最小的一个数在比较的过程中被逐渐的后移，最终被交换到最后一个位置了。这个过程有点像水里的气泡从水底逐渐地浮到水面的过程，所以这种排序算法叫做冒泡排序法。然后，使用同样的方法，依次对array0至array8、array0至array7、array0至array1做同样的处理。前后共做9次这样的处理，就可以得到由大到小的次序。这个过程用伪代码描述为： for(i=9; i=1; i-) 从array0至arrayi，相邻的两个数依次比较，如果前面的数小于后面的数，则交换两个数的位置。 ,对相邻两个数比较并交换的算法进行细化，得到如下算法描述： for(i=9; i=1; i-) for(j=0; j=i-1; j+) 若arrayjarrayj+1，则交换arrayj与arrayj+1； 下面，给出完整的源程序：,/*源程序7-4*/ #include“stdio.h“ #include“stdlib.h“ main() int array10, i, j, t; for(i=0; i=9; i+) arrayi = rand() % 100; printf(“