第七章-数组数据结构与数组的概念-影响程序设计的因素优秀文档

第七章数组

7．1数据结构与数组的概念

影响程序设计的因素除算法外还有数据结构。■数据结构概念

编写一个程序除了重视算法的设计外，还需重视数据类型的选择，即选择合适的数据类型来存放要处理的数据。在程序设计中，数据类型就称为数据结构，选择合适的数据类型实际上就是进行数据结构的设计。在程序设计中有格言：

数据结构+算法=程序说明数据结构与算法同等重要，算法依赖于数据结构，对于同一个问题的求解，可以采用不同的数据结构和不同的算法，对不同的数据结构有不同的算法，其复杂程度也会不同，选择合适的数据结构，可以降低算法的复杂程度。因此，在程序设计中应重视数据结构的设计。例：求任意100个数中的最大值。main(){inti,a,max;max=-32768for(i=1;i<=100;i++){scanf(“%d”,&a);if(a>max)max=a;}printf(“\nmax=%d”,max);}用一个简单变量作为数据结构，合理，算法简单

对于三个数的排序：main(){inta,b,c,t;scanf(“%d,%d,%d”,&a,&b,&c);

if(a<b){t=a;a=b;b=t;}if(a<c){t=a;a=c;c=t;}if(b<c){t=b;b=c;c=t;}printf(“\n%d,%d,%d”,a,b,c);}对于很多个数的排序用变量会很复杂而用数组会使算法很简单。仍可用变量作为数据结构■数组的概念inta[10]a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]

一组具有同样类型的数据的集合统一用一个名字代表---数组名（代表一组数）数组元素下标数组名

数组中的各成员称数组元素，由数组名加下标唯一地确定。

将一组数用一个名字代表，便于管理。只有一个下标的数组称为一维数组；可有二维数组、三维数组、…、七维数组。7．2一维数组的定义和引用

■定义

一般形式：类型符数组名[常量表达式]；

int

a[10];floatb[10]；

类型符数组名长度

作用：分配一组连续的内存单元说明：

●数组必须先定义后使用。

●数组名的命名规则与变量相同。

●常量表达式表示元素的个数（长度），下标从0开始。

●常量表达式不能包含变量，即不允许作动态定义。■引用

逐个引用其元素，不能进行整体引用。

引用的一般形式：

数组名[下标]

如：a[0]=50;a[1]=100;a[2]=a[0]+a[1];

与a2=a0+a1有根本性的区别：下标可变。用数组作为存放初始数据的数据结构0？{inti,a,n[101];0？if(s>smax){smax=s;row=i;}for(j=0;j<4;j++)for(i=1;i<=100;i++)printf(“\n%3d:%3d”,i,n[i]);{inta[3][4],i,j,t,s,smax=-32768,row;存放形式：按行存放。字符串1=字符串2时：返回0。printf(“\n%3d:%3d”,i,n[i]);scanf(“%s”,a);例：从键盘输入10个数。用变量：(不方便)scanf(“%d%d%d%d%d%d%d%d%d%d”，&a0,&a1,&a2,&a3,&a4,&a5,&a6,&a7,&a8,&a9);用数组：(灵活方便)for(i=0;i<10;i++)scanf(“%d”,&a[i]);

用循环控制输入个数和下标的变化。

注意下标的变化范围。■初始化

在定义数组的同时给数组赋初值。inta[10]={0,1,2,3,4,5,6,7,8,9};inta[10]={0,1,2,3,4};inta[]={0,1,2,3,4};■应用举例（1）对100个学生的分数统计最高分、最低分和平均分。

两种方法：用变量作为存放初始数据的数据结构用数组作为存放初始数据的数据结构main(){inti,a,max,min;floataver=0;max=0;min=100;for(i=0;i<100;i++){scanf(“%d”,&a);if(a>max)max=a;if(a<min)min=a;aver+=a;}aver/=100;printf(“\n%d,%d,%f”,max,min,aver);}用变量

main(){inti,a[100],max,min;floataver=0;for(i=0;i<100;i++)scanf(“%d”,&a[i]);max=a[0];min=a[0];for(i=0;i<100;i++){if(a[i]>max)max=a[i];if(a[i]<min)min=a[i];aver+=a[i];}aver/=100;printf(“\n%d,%d,%f”,max,min,aver)；}用数组找最大最小的位置？max=0;min=0;if(a[i]>a[max])max=i;if(a[i]<a[min])min=i;

（2）统计高于平均分的人数。main(){inti,a,n;floataver=0;for(i=0;i<100;i++){scanf(“%d”,&a);aver+=a;}aver/=100;

n=0;for(i=0;i<100;i++){scanf(“%d”,&a);if(a>aver)n++;}printf(“\n%d”,n);}用变量数据结构不合理main(){inti,a[100],n;floataver=0;for(i=0;i<100;i++)scanf(“%d”,&a[i]);for(i=0;i<100;i++)aver+=a[i];aver/=100;n=0;for(i=0;i<100;i++)if(a[i]>aver)n++;printf(“\n%d”,n);}

用数组1（3）对100个学生的分数统计出每分一档人数。0？1？2

？

3

？

4

？┇┇99？100？main(){inti,a;

for(i=1;i<=100;i++){scanf(“%d”,&a);

}

输出}inti,a,n[101];for(i=0;i<101;i++)n[i]=0;n[a]++;完整程序：main(){inti,a,n[101];for(i=0;i<101;i++)n[i]=0;

for(i=1;i<=100;i++){scanf(“%d”,&a);n[a]++;

}for(i=100;i>=0;i--)printf(“\n%3d:%3d”,i,n[i]);}体会数组作为存放结果的数据结构时的优越性。按10分一档统计？main(){inti,a,n[101];for(i=0;i<101;i++)n[i]=0;

for(i=1;i<=100;i++){scanf(“%d”,&a);n[a]++;

}}inti,a,n[11];for(i=0;i<11;i++)n[i]=0;n[a/10]++;（4）对10个学生的分数按从小到大的顺序排序后输出。

两种典型的排序算法：选择法和起泡法。选择法基本思想：首先选择最小的数放在0位置，再在剩下的数中选择最小的数放在下一位置，┈┈，依次类推，共进行9次选择。

5874390126每次选择都要与其后的所有数进行比较换位。

5874390126

ijmain(){inta[10],i,j,t;for(i=0;i<10;i++)scanf(“%d”,&a[i]);for(i=0;i<9;i++)for(j=i+1;j<10;j++)if(a[i]>a[j]){t=a[i];a[i]=a[j];a[j]=t;}for(j=0;j<10;j++)printf(“%3d”,a[j]);}5874390126

5874390126

ij

先找最小值所在的位置，最后再换位:main(){inta[10],i,j,t,k;for(i=0;i<10;i++)scanf(“%d”,&a[i]);for(i=0;i<9;i++){k=i;for(j=i+1;j<10;j++)if(a[j]<a[k])k=j;t=a[i];a[i]=a[k];a[k]=t;}for(j=0;j<10;j++)printf(“%3d”,a[j]);}起泡法基本思想：

首先将所有数中的最大值“冒泡”到最后位置，再将剩下的数中的最大值“冒泡”到上一位置，┈┈，依次类推，共进行9次“冒泡”。每次“冒泡”都是一种翻滚过程，即相邻两个数进行比较换位。5874390126main(){inta[10],i,j,t;for(i=0;i<10;i++)scanf(“%d”,&a[i]);for(j=1;j<=9;j++)for(i=0;i<10-j;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}for(j=0;j<10;j++)printf(“%3d”,a[j]);}要特别注意两个循环的范围。

（(5)循环移位

对一数列中的每个数向后移3个位置，最后3个数移到最前面。5874390126

1265874390用循环移位实现：5874390126main(){inti,j,k,a[10];for(i=0;i<10;i++)scanf(“%d”,&a[i]);

for(i=0;i<10;i++)printf(“%3d”,a[i]);}for(i=1;i<10;i++)a[i]=a[i-1];for(i=9;i>0;i--)a[i]=a[i-1];k=a[9];a[0]=k;for(j=1;j<=3;j++){k=a[9];}

(6)狐狸找兔子问题绕围绕着山顶有10个洞，一只兔子和一只狐狸分别住在洞里，狐狸总想吃掉兔子；一天，兔子对狐狸说：你想吃掉我有一个条件，先把洞顺序编号，你从最后一个洞出发，第一次先到第一个洞找我，第二次隔一个洞找，第三次隔两个洞找，┈，依次类推，寻找次数不限，我躲在一个洞里不动，只要找到我你就可以饱餐一顿。狐狸一想只有10个洞，寻找次数又不限，那有找不到的呢？马上答应了条件，结果狐狸跑断了腿也没找到，请问兔子躲在哪个洞里？12346789105用于输出字符串。{chara[50];而如果要处理的数据如同一张表格，则应定义二维数组来存放。…………{inta[3][4],b[4][3],i,j;max=a[0];min=a[0];aver/=100;a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]（1）对100个学生的分数统计最高分、最低分和平均分。要特别注意两个循环的范围。scanf(“%d%d%d%d%d%d%d%d%d%d”，for(i=1;i<=100;i++)for(i=0;a[i];i++){s=0;for(j=0;j<4;j++)s+=a[i][j];if(a[i]==0)printf(“%3d”,i+1);与a2=a0+a1有根本性的区别：下标可变。对数组元素操作算法思想：

开辟数组，每个元素代表一个洞，并赋初值0，表示各个洞都还未找，然后按规律找，每找一个洞，对应的数组元素就赋值1，表示已找过，┈┈，最后根据数组元素值1与0来识别各洞是否已找过。main(){inti,k=10;inta[10]={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;

a[k-1]=1;

}for(i=0;i<10;i++)if(a[i]==0)printf(“%3d”,i+1);}7．3二维数组的定义和引用■定义

一般形式：类型符数组名[常量表达式][常量表达式]；inta[3][4];floatb[5][10];

行列

二维数组的逻辑结构就如同一张表格：

a[0][0]a[0][1]a[0][2]a[0][3]

a[1][0]a[1][1]a[1][2]a[1][3]

a[2][0]a[2][1]a[2][2]a[2][3]

存放形式：按行存放。a[0]a[1]a[2]

二维数组可以看作是一个特殊的一维数组，它的元素又是一个一维数组。C语言这样的处理方法在很多情况下显得很方便。

与一维数组相比，二维数组的定义多一个长度，其元素多一个下标。在应用中，如果要处理的数据如同一数列，则可定义一维数组来存放；而如果要处理的数据如同一张表格，则应定义二维数组来存放。■引用

引用形式：数组名[下标][下标]如：a[0][3]=a[1][2]+a[2][3];

其元素有两个下标。

例：从键盘输入12个数到二维数组中。inta[3][4],i,j;for(i=0;i<3;i++)for(j=0;j<4;j++)scanf(“%d”,&a[i][j]);需要用两重循环来控制两个下标的变化。

如果键盘输入的数据是：123456789101112,则在数组中如何存放？两个循环换位呢？两个下标换位呢？

inta[3][4],i,j;for(i=0;i<3;i++)for(j=0;j<4;j++)scanf(“%d”,&a[i][j]);

for(j=0;j<4;j++)for(i=0;i<3;i++)scanf(“%d”,&a[i][j]);for(i=0;i<3;i++)for(j=0;j<4;j++)scanf(“%d”,&a[j][i]);例：输入一个表格的数据到二维数组中，并找最大值所在的位置main(){inta[3][4],i,j,i1,j1;for(i=0;i<3;i++)for(j=0;j<4;j++)scanf(“%d”,&a[i][j]);

i1=0;j1=0;for(i=0;i<3;i++)for(j=0;j<4;j++)

if(a[i][j]>a[i1][j1]){i1=i;j1=j;}printf(“\n%d,%d”,i1,j1);}■初始化

对二维数组赋初值的几种方法：

inta[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};

inta[3][4]={1,2,3,4,5,6,7,8,9,10,11,12};

inta[3][4]={{1},{5},{9}};

inta[3][4]={{1},{0,6},{0,0,11}};

inta[][4]={1,2,3,4,5,6,7,8,9,10,11,12};

inta[][4]={{0,0,3},{},{9,10}};■举例（1）矩阵的基本操作二维数组的逻辑结构就如同一个矩阵，因此，矩阵操作都可用二维数组实现。a11a12a13

…a1na21a22a23

…

a2na31a32a33

…

a3n

…………am1am2am3

…amnA=假定M=3，N=4

求和：main(){inta[4][4],i,j,s=0;┈┈┈for(i=0;i<4;i++)for(j=0;j<4;j++)s+=a[i][j];┈┈┈}上三角？下三角？主对角线？for(i=0;i<4;i++)for(j=i;j<4;j++)s+=a[i][j];for(i=0;i<4;i++)for(j=0;j<=i;j++)s+=a[i][j];for(i=0;i<4;i++)for(j=i;j<=i;j++)s+=a[i][j];for(i=0;i<4;i++)s+=a[i][i];1234567810111213141516非方阵转置：aij→bjimain(){inta[3][4],b[4][3],i,j;┈┈┈for(i=0;i<3;i++)for(j=0;j<4;j++)b[j][i]=a[i][j];┈┈┈}123456789101112159261037114812方阵转置：aij∽ajimain(){inta[3][3],i,j,t;┈┈┈for(i=0;i<3;i++)for(j=0;j<3;j++){t=a[i][j];a[i][j]=a[j][i];a[j][i]=t;}┈┈┈}123456789for(j=i+1;j<3;j++)将矩阵中和值为最大的那一行元素与首行对换。main(){inta[3][4],i,j,t,s,smax=-32768,row;┈┈┈for(i=0;i<3;i++){s=0;for(j=0;j<4;j++)s+=a[i][j];if(s>smax){smax=s;row=i;}}for(j=0;j<4;j++){t=a[0][j];a[0][j]=a[row][j];a[row][j]=t;}┈┈┈}1538461792567．4字符数组

用于存放字符的数组称字符数组。字符数组的每一个元素存放一个字符。

字符数组的独特之处：（1）字符数组可以看作字符串变量。（2）对字符数组可以进行某些整体操作。（3）有专用的字符串处理函数。

1、将字符数组作为字符串变量charc[10];给c分配10个字节的内存单元。把c看作数组时，按数组元素的形式访问：

c[0]=’a’;c[1]=’b’;c[2]=’c’;c[3]=’d’;

abcdcharc[10]={‘a’,’b’,’c’,’d’};也属于字符赋初值的形式。如果把字符序列看作一个整体（字符串），则c就可看作是存放这个字符串的串变量；但必须在字符序列后加上“字符串结束标志”后，才能成为完整的字符串。

如：c[4]=’\0’;或c[4]=0;

abcd\0也可以按字符串形式初始化：charc[10]=”abcd”;charc[]=”abcd”;分配5个字节2、对字符数组的整体操作对字符数组的有些操作可以整体进行，如输入输出。

for(i=0;i<10;i++)printf(“%c”,c[i]);

对数组元素操作

printf(“%s”,c);

整体操作注意以上两种操作有区别。

可将前者改为：for(i=0;c[i]!=’\0’;i++)printf(“%c”,c[i]);对于输入：

for(i=0;i<10;i++)scanf(“%c”,&c[i]);

对数组元素操作

scanf(“%s”,c);

整体操作对字符数组输入输出可以整体进行，但不允许整体赋值：

charc[10]=”abcd”,x[10];x=c;

不允许对于二维字符数组，可以看作是一维的字符串数组。例：从键盘输入10个人的名字到计算机：main(){inti;charname[10][20];10个元素的一维字符串数组for(i=0;i<10;i++)scanf(“%s”,name[i]);…}

只给一个下标将矩阵中和值为最大的那一行元素与首行对换。{chara[50],b[50];5874390126（5）strcmp(字符串1，字符串2)for(i=1;i<=100;i++)printf(“\n%3d:%3d”,i,n[i]);for(i=0;i<3;i++)for(j=i+1;j<10;j++)if(a[j]<a[k])k=j;inti,a,n[101];if(b<c){t=b;b=c;c=t;}注意下标的变化范围。用数组：(灵活方便)影响程序设计的因素除算法外还有数据结构。首先选择最小的数放在0位置，再在剩下的数中选择最小的数放在下一位置，┈┈，依次类推，共进行9次选择。scanf(“%s”,a);{scanf(“%d”,&a);3、字符串处理函数

c语言的函数库中提供了一系列专用于字符串处理的函数，需要时可直接调用。（1）puts(字符串)用于输出字符串。其中字符串可以是字符串常量，也可以是字符数组。

例：charstr[]=”China”;puts(str);puts(”China”);两个输出等效（2）gets(字符数组)用于从键盘输入一个字符串到字符数组中。函数返回字符数组的起始地址。例：charstr[10];gets(str);

执行该函数调用时，计算机等待输入字符串（3）strcat(字符数组,字符串)用于将字符串连接到字符数组的后面。其中字符串可以是字符串常量，也可以是字符数组。例：chara[10]=”abcd”,b[10]=”xyz”;strcat(a,b);与strcat(a,”xyz”)等效puts(a);

输出结果是：abcdxyz（4）strcpy(字符数组,字符串）用于将字符串拷贝到字符数组中。其中字符串可以是字符串常量，也可以是字符数组。

例：chara[10],b[10]=”abcdef”;strcpy(a,b);与strcpy(a,”abcdef