7-第七章 数组.ppt

1、第七章 数 组 71 数据结构与数组的概念 影响程序设计的因素除算法外还有数据结构。 数据结构概念 编写一个程序除了重视算法的设计外，还需重视数据类型的选择，即选择合适的数据类型来存放要处理的数据。在程序设计中，数据类型就称为数据结构，选择合适的数据类型实际上就是进行数据结构的设计。,在程序设计中有格言： 数据结构+算法=程序 说明数据结构与算法同等重要，算法依赖于数据结构，对于同一个问题的求解，可以采用不同的数据结构和不同的算法，对不同的数据结构有不同的算法，其复杂程度也会不同，选择合适的数据结构，可以降低算法的复杂程度。因此，在程序设计中应重视数据结构的设计。,例：求任意100个数中的最大

2、值。 void main() int i,a,max; max=-32768 for(i=1;imax) max=a; printf(“n max=%d”,max); ,用一个简单变量作为数据结构，合理，算法简单,对于三个数的排序： void main() int a,b,c,t; scanf(“%d,%d,%d”, 对于很多个数的排序用变量会很复杂而用数组会使算法很简单。,仍可用变量作为数据结构,数组的概念 int a10 a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 一组具有同样类型的数据的集合 统一用一个名字代表-数组名（代表一组数）,数组元素,下标,数组名,数组中的各成员

3、称数组元素，由数组名加下标唯一地确定。 将一组数用一个名字代表，便于管理。 只有一个下标的数组称为一维数组； 可有二维数组、三维数组、七维数组。,72 一维数组的定义和引用 定义 一般形式： 类型符 数组名常量表达式； int a10; float b10； 类型符 数组名 长度 作用：分配一组连续的内存单元,说明： 数组必须先定义后使用。 数组名的命名规则与变量相同。 常量表达式表示元素的个数（长度），下标 从0开始。 常量表达式不能包含变量，即不允许作动态定义。,引用 逐个引用其元素，不能进行整体引用。 引用的一般形式： 数组名下标 如：a0=50; a1=100; a2=a0+a1; 与

4、 a2=a0+a1有根本性的区别：下标可变。,例：从键盘输入10个数。 用变量：(不方便) scanf(“%d%d%d%d%d%d%d%d%d%d”， 用循环控制输入个数和下标的变化。 注意下标的变化范围。,初始化 在定义数组的同时给数组赋初值。 int a10=0,1,2,3,4,5,6,7,8,9; int a10=0,1,2,3,4; int a=0,1,2,3,4;,应用举例 （1）对100个学生的分数统计最高分、最低分和平均分。 两种方法： 用变量作为存放初始数据的数据结构 用数组作为存放初始数据的数据结构,void main() int i,a,max,min; float ave

5、r=0; max=0; min=100; for(i=0;imax) max=a; if(amin) min=a; aver+=a; aver/=100; printf(“n %d,%d,%f”,max,min,aver); ,用变量,void main() int i,a100,max,min; float aver=0; for(i=0;imax) max=ai; if(aimin) min=ai; aver+=ai; aver/=100; printf(“n %d,%d,%f”,max,min,aver)； ,用数组,找最大最小的位置？,max=0; min=0;,if(aiamax)

6、max=i; if(aiamin) min=i;,（2）统计高于平均分的人数。,void main() int i,a,n; float aver=0; for(i=0;i100;i+) scanf(“%d”,n=0; for(i=0;iaver)n+; printf(“n %d”,n); ,用变量,数据结构不合理,void main() int i,a100,n; float aver=0; for(i=0;iaver)n+; printf(“n %d”,n); ,用数组,1（3）对100个学生的分数统计出每分一档人数。 0 ？ 1 ？ 2 ？ 3 ？ 4 ？ 99 ？ 100 ？,void

7、 main() int i,a; for(i=1;i=100;i+) scanf(“%d”, 输出 ,int i,a,n101; for(i=0;i101;i+) ni=0;,na+;,完整程序： void main() int i,a,n101; for(i=0;i=0;i-) printf(“n %3d:%3d”,i,ni); ,体会数组作为存放结果的数据结构时的优越性。,按10分一档统计？ void main() int i,a,n101; for(i=0;i101;i+)ni=0; for(i=1;i=100;i+) scanf(“%d”, ,int i,a,n11; for(i=0;

8、i11;i+)ni=0;,na/10+;,（4）对10个学生的分数按从小到大的顺序排序后输出。 两种典型的排序算法：选择法和起泡法。 选择法基本思想： 首先选择最小的数放在0位置，再在剩下的数中选择最小的数放在下一位置，依次类推，共进行9次选择。 5 8 7 4 3 9 0 1 2 6,每次选择都要与其后的所有数进行比较换位。 5 8 7 4 3 9 0 1 2 6,i,j,void main() int a10,i,j,t; for(i=0;iaj) t=ai; ai=aj; aj=t; for(j=0;j10;j+) printf(“%3d”,aj); ,5 8 7 4 3 9 0 1 2

9、 6,5 8 7 4 3 9 0 1 2 6,i,j,先找最小值所在的位置，最后再换位: void main() inta10,i,j,t,k; for(i=0;i10;i+)scanf(“%d”, ,起泡法基本思想： 首先将所有数中的最大值“冒泡”到最后位置，再将剩下的数中的最大值“冒泡”到上一位置，依次类推，共进行9次“冒泡”。 每次“冒泡”都是一种翻滚过程，即相邻两个数进行比较换位。 5 8 7 4 3 9 0 1 2 6,void main() int a10,i,j,t; for(i=0;iai+1) t= ai; ai= ai+1; ai+1=t; for(j=0;j10;j+)

10、printf(“%3d”,aj); 要特别注意两个循环的范围。,(5) 循环移位 对一数列中的每个数向后移3个位置，最后3个数移到最前面。 5 8 7 4 3 9 0 1 2 6 1 2 6 5 8 7 4 3 9 0,用循环移位实现： 5 8 7 4 3 9 0 1 2 6 void main() int i,j,k,a10; for(i=0;i10;i+)scanf(“%d”, ,for(i=1;i10;i+)ai=ai-1;,for(i=9;i0;i-)ai=ai-1;,k=a9;,a0=k;,for(j=1;j=3;j+) k=a9;,(6)狐狸找兔子问题 围绕着山顶有10个洞，一只兔

11、子和一只狐狸分别住在洞里，狐狸总想吃掉兔子；一天，兔子对狐狸说：你想吃掉我有一个条件，先把洞顺序编号，你从最后一个洞出发，第一次先到第一个洞找我，第二次隔一个洞找，第三次隔两个洞找，依次类推，寻找次数不限，我躲在一个洞里不动，只要找到我你就可以饱餐一顿。狐狸一想只有10个洞，寻找次数又不限，那有找不到的呢？马上答应了条件，结果狐狸跑断了腿也没找到，请问兔子躲在哪个洞里？,1,2,3,4,6,7,8,9,10,5,算法思想： 开辟数组，每个元素代表一个洞，并赋初值0，表示各个洞都还未找，然后按规律找，每找一个洞，对应的数组元素就赋值1，表示已找过，最后根据数组元素值1与0来识别各洞是否已找过。,

12、void main() int i, k=10; int a10=0,0,0,0,0,0,0,0,0,0; for(i=1;i=10000;i+) k=(k+i)%10; if(k=0) k=10; ak-1=1; for(i=0;i10;i+) if(ai=0) printf(“%3d”,i+1); ,73 二维数组的定义和引用 定义 一般形式： 类型符 数组名常量表达式 常量表达式； int a34; float b510; 行 列,二维数组的逻辑结构就如同一张表格： a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23 存放形式：按行存放。,a0

13、,a1,a2,二维数组可以看作是一个特殊的一维数组，它的元素又是一个一维数组。C语言这样的处理方法在很多情况下显得很方便。 与一维数组相比，二维数组的定义多一个长度，其元素多一个下标。 在应用中，如果要处理的数据如同一数列，则可定义一维数组来存放；而如果要处理的数据如同一张表格，则应定义二维数组来存放。,引用 引用形式：数组名下标下标 如：a03=a12+a23; 其元素有两个下标。 例：从键盘输入12个数到二维数组中。 int a34,i,j; for(i=0;i3;i+) for(j=0;j4;j+) scanf(“%d”, 需要用两重循环来控制两个下标的变化。,如果键盘输入的数据是：1

14、2 3 4 5 6 7 8 9 10 11 12, 则在数组中如何存放？两个循环换位呢？两个下标换位呢？ int a34,i,j; for(i=0;i3;i+) for(j=0;j4;j+) scanf(“%d”,for(j=0;j4;j+) for(i=0;i3;i+) scanf(“%d”,for(i=0;i3;i+) for(j=0;j4;j+) scanf(“%d”,例：输入一个表格的数据到二维数组中，并找最 大值所在的位置 void main() int a34,i,j,i1,j1; for(i=0;iai1j1)i1=i; j1=j; printf(“n %d,%d”,i1,j1)

15、; ,初始化 对二维数组赋初值的几种方法： int a34= 1,2,3,4,5,6,7,8,9,10,11,12; int a34=1,2,3,4,5,6,7,8,9,10,11,12; int a34=1,5,9; int a34=1,0,6,0,0,11; int a4=1,2,3,4,5,6,7,8,9,10,11,12; int a4=0,0,3,9,10;, 举例 （1）矩阵的基本操作 二维数组的逻辑结构就如同一个矩阵，因此，矩阵操作都可用二维数组实现。,a11 a12 a13 a1n a21 a22 a23 a2n a31 a32 a33 a3n am1 am2 am3 amn,

16、A=,假定M=3，N=4,求和： void main() int a44,i,j,s=0; for(i=0;i4;i+) for(j=0;j4;j+) s+=aij; 上三角？下三角？主对角线？,for(i=0;i4;i+) for(j=i;j4;j+) s+=aij;,for(i=0;i4;i+) for(j=0;j=i;j+) s+=aij;,for(i=0;i4;i+) for(j=i;j=i;j+) s+=aij;,for(i=0;i4;i+) s+=aii;,1 2 3 4 5 6 7 8 10 11 12 13 14 15 16,非方阵转置：aijbji void main() i

17、nt a34,b43,i,j; for(i=0;i3;i+) for(j=0;j4;j+) bji=aij; ,1 2 3 4 5 6 7 8 9 10 11 12,1 5 9 2 6 10 3 7 11 4 8 12,方阵转置：aijaji void main() int a33,i,j,t; for(i=0; i3; i+) for(j=0; j3; j+) t=aij; aij=aji; aji=t; ,1 2 3 4 5 6 7 8 9,for(j=i+1; j3; j+),将矩阵中和值为最大的那一行元素与首行对换。 void main() int a34,i,j,t,s,smax=-

18、32768,row; for(i=0;ismax) smax=s; row=i; for(j=0;j4;j+) t=a0j;a0j=arowj; arowj=t; ,1 5 3 8 4 6 1 7 9 2 5 6,74 字符数组 用于存放字符的数组称字符数组。 字符数组的每一个元素存放一个字符。 字符数组的独特之处： （1）字符数组可以看作字符串变量。 （2）对字符数组可以进行某些整体操作。 （3）有专用的字符串处理函数。,1、将字符数组作为字符串变量 char c10; 给c分配10个字节的内存单元。 把c看作数组时，按数组元素的形式访问： c0=a; c1=b; c2=c; c3=d; a

19、 b c d char c10=a,b,c,d ; 也属于字符赋初值的形式。,如果把字符序列看作一个整体（字符串），则c就可看作是存放这个字符串的串变量；但必须在字符序列后加上“字符串结束标志”后，才能成为完整的字符串。 如：c4=0; 或 c4=0; a b c d 0 也可以按字符串形式初始化： char c10=”abcd”; char c=”abcd”; 分配5个字节,对于输入： for(i=0;i10;i+) scanf(“%c”, 不允许,对于二维字符数组，可以看作是一维的字符串数组。 例：从键盘输入10个人的名字到计算机： main() int i; char name1020;

20、 10个元素的一维字符串数组 for(i=0;i10;i+) scanf(“%s”,namei); 只给一个下标,3、字符串处理函数 c语言的函数库中提供了一系列专用于字符串处理的函数，需要时可直接调用。 （1）puts(字符串) 用于输出字符串。 其中字符串可以是字符串常量，也可以是字符数组。 例： char str=”China”; puts(str); puts(”China”); 两个输出等效,（2）gets(字符数组) 用于从键盘输入一个字符串到字符数组中。 函数返回字符数组的起始地址。 例： char str10; gets(str); 执行该函数调用时，计算机等待输入字符串,（3

21、）strcat(字符数组,字符串) 用于将字符串连接到字符数组的后面。 其中字符串可以是字符串常量，也可以是字符数组。 例： char a10=”abcd”, b10=”xyz”; strcat(a,b); 与strcat(a,”xyz”)等效 puts(a); 输出结果是：abcdxyz,（4） strcpy(字符数组,字符串） 用于将字符串拷贝到字符数组中。 其中字符串可以是字符串常量，也可以是字符数组。 例： char a10, b10=”abcdef”; strcpy(a,b); 与strcpy(a,”abcdef”)等效 不能用a=b 赋值 puts(a); 输出结果是：abcdef,（5） strcmp(字符串1，字符串2) 用于比较两个字符串的大小。 比较结果通过函数的返回值体现： 字符串1=字符串2时：返回0。 字符串1字符串2时：返回一正整数。 字符串1字符串2时：返回一负整数。,两个字符串之间谁大谁小取决于最先有差异的两个字符的ASCII代码的大小。 如： strcmp(“abcde”,”abcde”); 返回0 strcmp(“abcdefgh”,”abcxyz”)；返回负整数 strcmp(“a”,”ABCD”)； 返回正