第3章数组及其应用.ppt

程序设计技术,C语言数据描述和C程序设计初步 结构化程序设计基础和C语言的控制结构 数组及其应用 函数与C程序结构 指针与函数 指针与数组 字符串及其应用 结构体类型和联合体类型 C语言的文件处理及其应用 位运算与枚举类型,数组及其应用,3.1 一维数组3.1.1 一维数组的定义和初始化3.1.2 一维数组元素的引用方法3.2 二维数组和多维数组3.2.1 二维数组和多维数组的定义3.2.2 二维数组和多维数组元素引用方法3.3 数组的简单应用3.3.1 数组元素值的随机生成3.3.2 常用排序方法3.3.3 常用查找方法,一维数组,数组是有序数据的集合。一维数组是一组按线性排列有序且个数有限的同类型变量构成的数据集合。每个数组有一个名称-数组名，数组中的每个数据元素有一个编号-下标,下标从0开始,是正整数。一维数组在存储时需要占用连续的内存空间，其每一个数据元素所占用的字节长度与它们的数据类型相关。,3.1.1 一维数组的定义和初始化,一维数组的定义 存储类型 数据类型 数组名常量表达式;存储类型：auto、static、extern 数据类型：数组元素的数据类型(基本,构造,指针）常量表达式：指定数组的元素个数,也称数组长度。例如：int s30;/*定义了1个整型数组s*/把30个学生的成绩放在一维数组s中，数组中每个元素表示一个学生的某科成绩，如s5表示序号为5的学生成绩73。因序号从0开始，所以没有S30元素。,3.1.1 一维数组的定义和初始化,一维数组的初始化 数据类型 数组名n=常量列表；其中：常量列表：可是逗号分隔的常量或常量表达式。n：数组长度，常量列表个数不能超过数组长度。例如：int a10=1,2,3,4,5,6,7,8,9,10;/*常量*/int b3=1,3*5,4*3-2;/*常量表达式*/int d5=1,2,3,4,5,6;/*超过数组长度*/注意：数组名代表数组存储区的首地址，即第一个数组元素的存储地址。即a等价于&a0。,3.1.1 一维数组的定义和初始化,数组元素初始化的几种形式 在数组初始化时，既可以对全部数组元素赋初始值，也可只对部分数组元素赋初始值，没有初始化的元素值为0（字符数组为0）；char s110=a,b,c,d,e;/*其余元素为0*/如果数组长度没有指定，以初始化数值个数作为数组的长度，或者说数据的个数是确定的，可以不指定数组的长度。float a1=10,20,30.9,40,50;/*数组长度为5*/将数组全部元素初始化为0值的简写形式 例如：int a10=0；int a5=0*10;不能给数组整体赋值 例如，inta5=1,1,1,1,1 inta5=1;,3.1.2 一维数组元素的引用,C语言规定：只能逐个引用数组元素而不能一次引用整个数组。数组元素(下标变量)表示形式：数组名下标下标：整型常量或整型表达式，实型下标自动取整。例：int b10;(定义数组b)b10=100;(下标越界）b=100;(整体操作数组)常将数组和循环配合使用。通过改变数组的下标值来访问数组的各个元素。举例如下：double a10;for(i=0;i10;i+)scanf(“%lf”,/*将a数组第6个元素(序号5)赋值为300*/,3.1.2 一维数组元素的引用,例3-1 将一个整型数组中所有元素值在同一个数组中按逆序重新存放并输出。程序一次运行情况如下所示：Input ten value of Array:21 23 25 27 29 30 32 34 36 3838 36 34 32 30 29 27 25 23 21,Arr0,Arr9,3.1.2 一维数组元素的引用,例3-4 打印杨辉三角形的前10行（用一维数组处理）杨辉三角形的数列特点：即一行中某列的数是上一行该列上前两位数之和。比如第4行第2列的3等于第3行第1、2列的数1+2。每行第1列和最后1列都为1，行数=列数。,解题思路：利用数组具有保存数据的特点，将第1列初始化为1，第n行从第n列开始，从后往前计算该行中各列的值，在数组中已经保留了上一行的各列数据，利用此数据，可以计算新行的各列数据,然后输出。,3.1.2 一维数组元素的引用,对每一行杨辉三角形值的具体处理方法为：首先用表达式yhrow=1将该行最后一个元素值置1，然后从后向前循环执行表达式:yhcol=yhcol+yhcol-1。即将一维数组 yh上一行当前位置元素值与其前面一个位置的元素值相加作为本行当前位置上的元素值。row=1：yh1=1;利用它可将每行的第1列置为1。row=2：yh2=1;row=3：yh3=1;yh2=yh2+yh1=2;row=4：yh4=1;yh3=yh3+yh2=3;yh2=yh2+yh1=3;row=5：yh5=1;yh4=yh4+yh3=4;yh3=yh3+yh2=6;yh2=yh2+yh1=4;,3.1.2 一维数组元素的引用,对每一行杨辉三角形值的具体处理方法为：首先用表达式yhrow=1将该行最后一个元素值置1，然后从后向前循环执行表达式:yhcol=yhcol+yhcol-1。即将一维数组 yh上一行当前位置元素值与其前面一个位置的元素值相加作为本行当前位置上的元素值。row=1：yh1=1;row=2：yh2=1;row=3：yh3=1;yh2=yh2+yh1=2;row=4：yh4=1;yh3=yh3+yh2=3;yh2=yh2+yh1=3;row=5：yh5=1;yh4=yh4+yh3=4;yh3=yh3+yh2=6;yh2=yh2+yh1=4;,各行的第1列都置为1,各行的最后1列都置为1,倒数第2列开始处理,1 yh11 1 yh1 yh21 2 1 yh1 yh2 yh31 3 3 1 yh1 yh2 yh3 yh4,数组及其应用,3.1 一维数组3.1.1 一维数组的定义和初始化3.1.2 一维数组元素的引用方法3.2 二维数组和多维数组3.2.1 二维数组和多维数组的定义3.2.2 二维数组和多维数组元素引用方法3.3 数组的简单应用3.3.1 数组元素值的随机生成3.3.2 常用排序方法3.3.3 常用查找方法,3.2 二维数组和多维数组,在程序设计中如果需要处理诸如矩阵、平面的或立体的图形等数据信息，使用一维数组显然不够，可以使用二维、三维以至更多维的数组。一维数组存储线性关系的数据，二维数组则可以存储平面关系的数据，三维数组可以存储立体信息，依次类推可以合理地使用更高维数的数组。,数组的几个实例,用二维数组做字模 手机屏幕采用的字体称为“点阵”字体，如果不支持中文，则最小只需7*7点阵；程序要在屏幕上打出“A”时，则只需遍历该数组，然后在元素值为0的地方，打出空格，在元素值为1的地方，打出小点即可。对于这样一个点阵，对应的一个二维数组为：,数组的几个实例,多个班级的成绩管理 如：某年级有4个班，每个班最多不超过40人。则该成绩数据对应于一个二维数组：int cj440;提问：2班24号的成绩是哪个数组元素？答案是：cj123;注意：C语言中的数组下标从0开始，所以2班24号对应数组元素的下标是1和23。,数组的几个实例,多个年级的成绩管理 设有：年级总数为6；每个年级的班级数为4；每个班级的学生人数为40。利用三维数组实现多个年级的成绩管理 int cj6440;将三年级、2班、20号学生的成绩赋值为78 cj2119=78;,二维数组和多维数组的定义一个二维数组可以分解为多个一维数组，可以推论多维数组：n维数组的每个元素由n-1维数组构成。二维数组定义的一般形式为：数据类型 数组名常量表达式常量表达式；多维数组定义的一般形式为：数据类型 数组名常量表达式常量表达式；例如：int a34,ma1010;/*二维数组*/float b333;/*三维数组*/a由3行4列共12个元素组成；ma由1010共100个元素组成。b是一个333共27个元素构成的三维数组。,行数,列数,3.2.1 二维数组和多维数组的定义,C语言中规定数组按“行”存储，由于计算机系统内存是一个线性排列的存储单元集合，所以当需要存储二维或多维数组到内存时，必须进行二维空间或多维空间向一维空间的投影。例如：int a122,a2222;则数组a1和a2在内存的存放形式如图3.4和3.5所示。,3.2.1 二维数组和多维数组的定义,根据多维数组在存储器中按行存储规则和行列顺序,计算多维数组元素在连续内存中的单元序号(以0开头)。设有mn(m行n列)的二维数组a，则二维数组元素aij在连续存储区域的单元序号计算公式为：in+j；（行号列数+列号）例如：int a22;则数组元素a11的序号为：12+1=3 即二维空间中1行1列元素是一维空间中的3号元素 三维数组部分省略，参看第3章要点。,3.2.1 二维数组和多维数组的定义,3.2.1 二维数组和多维数组的定义,二维和多维数组的初始化 分行赋值初始化方式例如：int a23=1,1,1,2,2,2;int a1020=0;int a4=1,2,3,4,5,6,7,8,9,10,11,12;系统根据12个元素,二维长度为4,自动测算出一维长度3。单行赋值初始化方式例如：int a34=1,2,3,4,5,6,7,8,9,10,11,12;对部分数组元素赋初值例如：int a34=1,0,6，0，0，11;,二维数组元素的下标表示法 数组名下标下标；数组元素也称为下标变量，其用法与一般变量相同。例：double a55,y;a23=300;/*将a的2行3列元素赋值300*/y=500;/*将变量y赋值500*/a55=200；（下标越界)在程序设计中，二维数组不能作为一个整体进行处理，通常用双重for循环来逐个访问二维数组元素:外循环控制行、内循环控制列；外循环控制列，内循环控制行。例如：int a510,i,j;则a数组的输入输出基本形式如图3.8所示,3.2.1 二维数组和多维数组的引用,3.2.2 二维数组和多维数组元素引用,例3-5 在二维数组a34中依次选出各行最大元素值存入一维数组b3对应元素中。程序运行结果：array a:3 16 87 65 4 32 11 108 10 25 12 27 array b:87 108 27,数组及其应用,3.1 一维数组3.1.1 一维数组的定义和初始化3.1.2 一维数组元素的引用方法3.2 二维数组和多维数组3.2.1 二维数组和多维数组的定义3.2.2 二维数组和多维数组元素引用方法3.3 数组的简单应用3.3.1 数组元素值的随机生成3.3.2 常用排序方法3.3.3 常用查找方法,3.3.1 数组元素值的随机生成,计算机自动生成“随机数”是一种较好的模拟数据法 为在程序中产生随机数，需要使用标准库函数srand、rand和time，并将对应头文件包含到程序中。Srand函数是初始化随机数(即种子)发生器，种子可以当前的系统时间产生，函数原型在stdlib.h中声明。void srand(unsigned int seed);rand函数是随机产生一个0到RAND_MAX(0 x7fff)之间的正整数，函数原型在stdlib.h中声明。int rand(void);time函数是获取系统时间。函数原型在time.h中声明如下：time_t time(time_t*timer);,3.3.1 数组元素值的随机生成,例3-7 随机生成20个3位以内的整数序列存放在一维数组中，然后按每行5个数输出所有数组元素。程序一次运行结果为：659 100 184 135 876348 934 293 587 338179 243 523 799 653234 657 439 776 297 例3-8 编程序实现如图3.10所示的矩阵转置功能，即将NM矩阵转换为MN矩阵；要求被处理的二维数组元素值（2位数以内）随机产生。,冒泡排序从待排数据序列中第一个位置开始，依次比较相邻两个位置上的数据，若是逆序则交换，一趟扫描后，关键字值最大（或最小）的数则交换到了最右边(或最下面)；不考虑已排好序的数据，将剩下的数作为待排序列；重复、两步直到排序完成；n个数据的排序最多进行n-1趟比较，在第1趟比较中要进行n-1次两两比较，在第i趟比较中要进行n-i次的两两比较。例3-9 编程实现冒泡排序算法，对随机生成的20个整数按升序排序并输出。,3.3.2 数组的常用排序方法,将6个数进行冒泡排序 第一趟比较中,进行了5次比较:(最大数下沉)5 5 5 5 5 5 6 6 2 2 2 2 2 2 6 6 6 6 9 9 9 9 9 9 10 10 10 10 10 3 3 3 3 3 3 10 1次 2次 3次 4次 5次 结果,3.3.2 数组的常用排序方法,余下5个数进行排序 第二趟比较中,进行了4次比较:(次大数下沉)5 2 2 2 2 2 5 5 5 5 6 6 6 6 6 9 9 9 9 3 3 3 3 3 9 1次 2次 3次 4次 结果,3.3.2 数组的常用排序方法,3.3.2 数组的常用排序方法,选择排序（交换排序的优化）假设具有n个元素的数组a中用a0存放最小(或最大)的数，将此数与后面所有的数比较并用下标变量k记录最小(或最大)数所在位置。一趟比较完成后，将a0与ak交换。在剩下的N-1个数据(即a1到an-1的元素)中使用相同的方法寻找最大（或最小）的数，并将a1与ak交换；以此类推,直到将整个待排数据集合处理完。,例3-10 编程序实现选择排序算法，对随机生成的20个整数按升序进行排序并输出。,将6个数进行选择排序 在a0到a5数组元素中找最小数a0 a1 a2 a3 a4 a5 5 6 2 9 10 3,3.3.2 数组的常用排序方法,记下小数下标为2,将a0与a2交换 在余下a1到a5数组元素中又找最小数 a1 a2 a3 a4 a5 6 5 9 10 3将a1与a5交换,小数下标为2,修改小数下标为5,3.3.3 数组的常用查找方法,顺序查找（线性查找）从数组首元素或最后一个元素开始，往后或往前顺序比较每一个数组元素值是否等于查找关键字；如果找到相符合的元素值，则查找成功，否则,查找失败。顺序查找适应于被查找集合无序的场合。例3-11 编程序实现顺序查找算法，在随机生成的20个整数中查找指定值，要求程序能够显示出查找进行比较的次数以及本次查找成功与否。,3.3.3 数组的常用查找方法,折半查找（二分查找）该算法要求在一个对查找关键字而言有序的序列上进行，其基本思想是：逐步缩小查找目标可能存在的范围，具体描述如下：选取表中中间位置的记录作为基准，将表分为两个子表；当基准位置的关键字值与查找关键字值相符合时，返回基准记录位置，算法结束；当基准位置的关键字值与查找的关键字值不符合时，在处理的两个子表中选取一个子表，重复执行、，直到被处理的子表中没有记录为止。,3.3.3 数组的常用查找方法,图3.11是在一有序序列中实现对key=21进行折半查找。low=0，high=22，middle=11(数组下标从0开始)low=12,high=22，middle=17(数组下标从12开始)low=18,high=22，middle=20(数组下标从18开始)例3-12a 编程实现折半查找。在有序数组a的23个元素中查找关键字21，并输出查找比较次数以及查找成功与否的信息。,