高级语言程序设计：第6章 数组

第6章数组高级语言程序设计本章主要内容：1.介绍数组的数据结构2。理解怎样声明一维数组、二维数组和字符数组、初始化数组和引用数组的单个元素。3。理解基本排序方法4。掌握如何给函数传递数组5。能够声明和操作多维数组。本章需掌握的基本算法：统计每一个级别出现的频率。2。数组的排序（冒泡法和选择法）3。数组查找（线性查找和二分查找）4。矩阵的相加、相减及相乘。5。字符串的

strcpy(s1,s2)、拷贝strcat(s1,s2)、追加strcmp(s1,s2).比较6。十进制数与二进制、八进制、十六进制的相互转换。本章有趣的程序设计题：1。航空预约系统的设计（书P1966。21）2。海龟作图（书P1966.22)3.骑士漫游（书P1976.24）4。八皇后问题（书P2006.26)通过这两节课的学习，希望同学们能理解和掌握一维数组的定义、初始化和引用。熟练掌握利用一维数组实现数据的排序、查找及进制的转化。1.数组的引入

在前面的程序设计中，所涉及和处理的数据都非常简单，对这些数据采用C语言的基本类型（整型、实型、字符型）来描述就行，但在实际应用中，需要处理的数据往往是复杂多样的。问题的提出：输入集美大学2009计算机工程学院200名学生的C语言成绩，按成绩从高分到低分排序，输出平均成绩及高于平均成绩的学生成绩。如何编程呢？Ｃ语言提供了用户自定义数据的描述方法，即构造类型：由若干基本类型数据按一定的规则构成复杂数据对象。如数组，结构、联合及枚举类型。构造数据类型的引入，使我们能较方便地解决上面的问题。6.1一维数组一维数组的定义(declareanarray)

存储类型数据类型数组名[常量表达式]；

数组（array):是一组相关的存储单元，表现在：这些存储单元具有相同的名字和数据类型表示元素个数下标从0开始例

inta[6];a[0]0145a[1]a[2]a[3]a[4]a[5]23a编译时分配连续内存内存字节数=数组维数*sizeof(元素数据类型)数组名表示该连续存储单元的首地址，是地址常量合法标识符int,long,char,float,doubleauto,static,extern例1:P6_1.cvoidmain(){inta[6];

printf("%d\n",sizeof(a));

printf("%x\n",a);printf("%p\n",a+1);}结果：12ffc4ffc6上例中若执行语句：prinyf(“%x\n”,a+5);其结果为多小？输出结果：ffce5*2=10得到的是十进制,先转换为十六进制，得到a.再进行ffc4+a=ffce设数组的首地址为：ffc4a[0]0145a[1]a[2]a[3]a[4]a[5]23a一维数组的引用数组必须先定义，后使用只能逐个引用数组元素，不能一次引用整个数组,数组元素表示形式：数组名[下标]其中：下标可以是常量或整型表达式例inti=15;

intdata[i];(不能用变量定义数组维数)#defineN15intdata[N];如何希望动态开辟存储空间，应如何实现？思考题:动态开辟存储空间范围多大?静态开辟存储空间的范围多大?注意：1。C语言对数组不作越界检查，理解“数组的第5个元素“与”下标为5的数组元素“的区别。例intdata[5];data[5]=10;2。只能逐个引用数组元素，不能一次引用整个数组例inta[10];

printf(“%d”,a);()必须

for(j=0;j<10;j++)

printf(“%d\t”,a[j]);()一维数组的初始化

inta[5]={1,2,3,4,5};等价于：a[0]=1;a[1]=2;a[2]=3;a[3]=4;a[4]=5;说明：数组不初始化，其元素值为随机数对static数组元素不赋初值，系统会自动赋以0值。如

inta[5]={6,2,3};

等价于：a[0]=6;a[1]=2;a[2]=3;a[3]=0;a[4]=0;如

inta[3]={6,2,3,5,1};()staticinta[5];等价于：a[0]=0;a[1]=0;a[2]=0;a[3]=0;a[4]=0;

inta[]={1,2,3,4,5,6};编译系统根据初值个数确定数组维数程序举例例1：读10个整数存入数组，找出其中最大值和最小值p6_4.c#include<stdio.h>#defineSIZE10main(){intx[SIZE],i,max,min;

printf("Enter10integers:\n");

for(i=0;i<SIZE;i++){

printf(“a[%d]=",i);

scanf("%d",&x[i]);}

max=min=x[0];

for(i=1;i<SIZE;i++){if(x[i]>max)max=x[i];if(x[i]<min)min=x[i];}

printf("Maximumvalueis%d\n",max);

printf("Minimumvalueis%d\n",min);}例2：读10个整数存入数组，求均值,及高于平均值的数

p6_5.c例2:20个学生被邀请来给自助餐厅的食品打分，分数分为从1~10的10个等级（1最低分，10最高分）在整数数组中设置这20个值，然后统计调查结果。p6_4.c这是一个典型的数组应用问题，目的是统计每一个级别（1~10）出现的次数，我们用11个元素的数组b计算每一等级出现的频率。#include<stdio.h>/*例：P6_6.c*/#defineN20voidmain(){inti;

inta[N]={8,9,6,4,8,6,7,9,5,6,4,3,6,7,9,6,2,3,7,6};

intb[11]={0};for(i=0;i<N;i++)

++b[a[i]];

printf("等级\t频率\n");for(i=1;i<11;i++)

printf("%d\t%d\n",i,b[i]);}若改为：inta[N]={8,13,6,4,8,6,7,9,5,6,4,3,6,7,9,6,2,3,7,6};会出现什么问题？如何解决？(P6_6_1.c)0b[1]0b[2]0b[3]0b[4]0b[5]0b[6]0b[7]0b[8]0b[9]0b[10]11112212132142351336思考题1。模仿该例，如何实现统计一篇文章中26个英文字母(不分大小写)出现的频率。p6_7.c2。统计各分数段人数,统计原则:60分以下为一段,60到69为一段,70到79为一段,80到89为一段,90到99为一段，100为一段,共6段。P6_7_3.c#include<stdio.h>#include<ctype.h>#defineN10voidmain(){charch;

inti,a[26]={0};

while((ch=getchar())!=EOF){

if(isalpha(ch))/*判断是不是为字符*/

++a[toupper(ch)-65];}for(i=0;i<26;i++){printf("%c|%c--->%d\t",i+65,i+97,a[i]);if((i+1)%4==0)printf("\n");}}#defineN5voidmain(){int

i,a[N];

intb[6]={0};/*分别存放6个分段统计结果*/

chars[6][10]={"0~59","60~69","70~79","80~89","90~99","100"};

printf("enterthescore:\n");for(i=0;i<N;i++){do{

printf("a[%d]=",i);

scanf("%d",&a[i]);}while(a[i]<0||a[i]>100);switch(a[i]/10){case6:b[1]++;break;case7:b[2]++;break;case8:b[3]++;break;case9:b[4]++;break;case10:b[5]++;break;default:b[0]++;}}for(i=0;i<6;i++)printf("%6s-->%d\n",s[i],b[i]);}

if(a[i]<60)k=0;elsek=a[i]/10-5;++b[k];

if(a[i]<60)k=0;elsek=a[i]/10-5;++b[k];例3:把从键盘上输入的十进制数(long型)以二进制形式输出p6_8.c

voidmain(){intc[32],i=0;longnum;

printf("enteranumber:\n");

scanf("%ld",&num);do{

c[i]=num%2;num=num/2;i++;}while(num!=0);

printf(“transmitenewbase:\n");for(i=i-1;i>=0;i--)

printf("%d",c[i]);}例4:把从键盘上输入的十进制数(long型)以二到十六进制形式输出p6_9.c

voidmain(){

charb[16]="0123456789abcdef";

intc[32],i=0,base;longn;

printf("enteranumber:\n");

scanf("%ld",&n);

printf("enternewbase:\n");

scanf("%d",&base);do{

c[i]=n%base;n=n/base;i++;}while(n!=0);

printf("transmitenewbase:\n");for(i=i-1;i>=0;i--)

printf("%c",b[c[i]]);}数组排序对于数据处理工作，排序是其最基本的运算之一。为了提高计算机的工作效率，人们提出了各种各样的排序方法和算法。所谓排序是，就是整理表中的记录，使之按关键字递增（或递减）次序排列起来。常用的排序算法有：冒泡法、选择法、插入法、快速排序法、堆排序法、归并排序法等。本节主要介绍冒泡法和选择法。举例：选择法排序：设有5个数a[0],a[1],a[2],a[3],a[4]第一个数与后面所有数比较数a[0]a[1]a[0]a[2]a[0]a[3]a[0]a[4]

a[0]最大a[1]a[2]a[1]a[3]a[1]a[4]a[2]a[3]a[2]a[4]a[3]a[4]ij01~412~423~434~4

j=i+1~4a[i]<a[j]for(i=0;i<4;i++){for(j=i+1;j<=4;j++)if(a[i]<a[j]){temp=a[i];a[i]=a[j];a[j]=temp;}}例用改进选择法对n个数排序排序过程：（1）首先通过n-1次比较，从n个数中找出最小的，将它与第一个数交换—第一趟选择排序，结果最小的数被安置在第一个元素位置上（2）再通过n-2次比较，从剩余的n-1个数中找出关键字次小的记录，将它与第二个数交换—第二趟选择排序（3）重复上述过程，共经过n-1趟排序后，排序结束改进的选择法#defineN10voidmain(){inta[N],i,j,k,temp;

printf("Input10numbers:\n");for(i=0;i<N;i++)

scanf("%d",&a[i]);

for(i=0;i<N-1;i++){

k=i;for(j=i+1;j<=N-1;j++)if(a[j]>a[k])k=j;if(i!=k){temp=a[i];a[i]=a[k];a[k]=temp;}}

printf("Thesortednumbers:\n");for(i=0;i<N;i++)

printf("%d",a[i]);}选择法：#include<stdio.h>#defineN10voidmain(){

inta[N],i,j,temp;

printf("Input10numbers:\n");for(i=0;i<N;i++)

scanf("%d",&a[i]);for(i=0;i<N-1;i++){for(j=i+1;j<=N-1;j++)if(a[i]<a[j]){temp=a[i];a[i]=a[j];a[j]=temp;}}

printf("Thesortednumbers:\n");for(i=0;i<N;i++)

printf("%d",a[i]);}例3用冒泡法对n个数排序排序过程：（1）比较第一个数与第二个数，若为逆序a[0]>a[1]，则交换；然后比较第二个数与第三个数；依次类推，直至第n-1个数和第n个数比较为止——第一趟冒泡排序，结果最大的数被安置在最后一个元素位置上（2）对前n-1个数进行第二趟冒泡排序，结果使次大的数被安置在第n-1个元素位置（3）重复上述过程，共经过n-1趟冒泡排序后，排序结束举例：将5个整数按从大到小排序冒泡法排序：设有5个数a[0],a[1],a[2],a[3],a[4]比较相邻两个数a[0]a[1]a[1]a[2]a[2]a[3]a[3]a[4]

a[4]存放最大数a[0]a[1]a[1]a[2]a[2]a[3]a[3]存放第二大数a[0]a[1]a[1]a[2]a[0]a[1]ij10~320~230~140~0j=0~4-i外循环控制比较的轮次i=1~4内循环比较相邻两个元素：if(a[j]<a[j+1])

交换a[j],a[j+1]#include<stdio.h>#defineN10voidmain(){

inta[N],i,j,temp;

printf("Input10numbers:\n");

for(i=0;i<N;i++)

scanf("%d",&a[i]);for(i=1;i<=N-1;i++)for(j=0;j<=N-1-i;j++)if(a[j]>a[j+1]){temp=a[j];

a[j]=a[j+1];a[j+1]=temp;}

printf("Thesortednumbers:\n");for(i=0;i<N;i++)

printf("%d",a[i]);}ij10~320~230~140~0j=0~4-iP6_6.c思考题冒泡法除了从上到下相邻两个元素的比较外，还可以从下到上相邻两个元素的比较。模仿该例，给出从下到上相邻两个元素的比较的冒泡算法。冒泡法排序：设有5个数

a[0],a[1],a[2],a[3],a[4]a[4]a[3]a[3]a[2]a[2]a[1]a[1]a[0]a[4]a[3]a[3]a[2]a[2]a[1]a[4]a[3]a[3]a[2]a[4]a[3]ij14~124~234~344~4j=4~i外循环控制比较的轮次i=1~4内循环比较相邻两个元素：if(a[j]>a[j-1])交换a[j],a[j+1]p6_7.c#include<stdio.h>#defineN10voidmain(){inta[N],i,j,temp;

printf("Input10numbers:\n");

for(i=0;i<N;i++)

scanf("%d",&a[i]);for(i=1;i<=N-1;i++)for(j=4;j>=i;j--)if(a[j]>a[j-1]){temp=a[j];

a[j]=a[j-1];a[j-1]=temp;}

printf("Thesortednumbers:\n");for(i=0;i<N;i++)

printf("%d",a[i]);}ij10~320~230~140~0j=0~4-iP6_7.c查找算法顺序查找特例：求最大值，求最小值折半查找顺序查找int

Search(longa[],intn,longx)

{

inti;for(i=0;i<n;i++){if(a[i]==x){return(i);}}return(-1);}二分（折半）查找数组下标01234第一次循环：9901199013990159901799019

①查找值x=99017lowmidhighx>a[mid],low=mid+1第二次循环：9901199013990159901799019

low=midhighx=a[mid]，找到数组下标01234第一次循环：9901199013990159901799019

②查找值x=99016lowmidhighx>a[mid],low=mid+1第二次循环：9901199013990159901799019

low=midhighx<a[mid],high=mid-1第三次循环：9901199013990159901799019

highlow不满足low<=high,循环结束,未找到

二分查找法：(书P185)#include<stdio.h>voidmain(){

inta[10]={11,12,13,14,15,16,17,18,19,20};

intx,index;

int

search(int[],int,int);

printf("请输入要查找的数：");

scanf("%d",&x);

index=BinarySearch(a,10,x); if(index==-1)

printf("notfound"); else

printf("%d在第%d个位置",x,index+1);}int

BinarySearch(int

a[],int

n,intx){

int

low,j,mid; low=0;high=9;

while(low<=high){mid=(low+high)/2;

if(x>a[mid])low=mid+1;elseif(x<a[mid])high=mid-1;elsereturnmid; } return-1;}6.5数组名作为函数参数传递数组的首地址函数定义时，形式参数以如下形式声明：

类型说明符数组名[]

int

a[10];

……

myFunction(a,10);……

void

myFuction(int

myArray[],int

arraySize){……}数组名作为实参数组作为形参函数调用时，只需要给出数组名即可数组名作为实参传递的是它所代表的数组的起始地址，即将数组名所对应的数组的起始地址复制给对应的形参被调函数通过形参知道数组的存储位置在被调用函数中可以通过形参访问并修改数组中的任一数组元素6.5数组名作为函数参数函数原型声明

void

myFuction(int

myArray[],int

arraySize);或省略函数原型中的参数名

void

myFuction(int[],int);例:求学生的平均成绩10个学生成绩，放在一维数组score中。

#include<stdio.h>

floataverage(int

stu[],intn);voidmain(){intscore[10],i;floatav;

printf("Input10scores：\n");for(i=0;i<10;i++)

scanf("%d",&score[i]);

av=average(score,10);

printf("Averageis：%.2f",av);}floataverage(int

stu[],intn){inti;floatav,total=0;for(i=0;i<n;i++)total+=stu[i];

av=total/n;returnav;}实参用数组名形参用数组定义,int

stu[]stuscore959..........872561780数组元素与数组名作函数参数比较12a调用前a[0]a[1]x12a调用后a[0]a[1]12y21xy交换12a返回#include<stdio.h>voidswap2(int

x,int

y){intz;z=x;x=y;y=z;}voidmain(){inta[2]={1,2};

swap2(a[0],a[1]);printf("a[0]=%d,a[1]=%d\n",a[0],a[1]);}值传递12a调用前12ax调用后21ax交换21a返回#include<stdio.h>voidswap2(intx[]){intz;z=x[0];x[0]=x[1];x[1]=z;}voidmain(){inta[2]={1,2};

swap2(a);printf("a[0]=%d\na[1]=%d\n",a[0],a[1]);}地址传递例对数组中的10个数按从小到大的顺序排序void

Sort(intarray[],intn){inti,j,k,t;for(i=0;i<n-1;i++)

{

k=i;for(j=i+1;j<n;j++)if(array[j]<array[k])k=j;if(k!=i)

{

t=array[k]; array[k]=array[i]; array[i]=t; }

}}#include<stdio.h>voidSort(int[],int);voidmain(){

inta[10],i;for(i=0;i<10;i++)

scanf("%d",&a[i]);

Sort(a,10);for(i=0;i<10;i++)

printf("%d",a[i]);

printf("\n");}void

sort(intarray[],intn){inti,j,k,t;

for(i=0;i<n-1;i++){k=i;

for(j=i+1;j<n;j++)

if(array[j]<array[k])k=j;

if(k!=i){t=array[k]; array[k]=array[i]; array[i]=t;}}}kj32463825781796645326a0123456789array主函数中：sort(a,10);i=0jjkjjjkjjjjj1732i=1kj2546ki=2k2638字符数组和字符串（书P169)HelloBoyBoy字符串:一串以'\0'结尾的字符在C语言中被看作字符串用双引号括起的一串字符是字符串常量，C语言自动为其添加'\0'终结符C语言并没有为字符串提供任何专门的表示法，完全使用字符数组和字符指针来处理字符数组:每个元素都是字符类型的数组charstring[80];字符数组的初始化用字符型数据对数组进行初始化charstr[6]={'C','h','i','n','a','\0'};用字符串常量直接对数组初始化charstr[6]={"China"};charstr[6]="China";例输出一个字符串#include<stdio.h>main(){charc[10]={'I','','a','m','','a','','b','o','y'};

inti;for(i=0;i<10;i++)

printf("%c",c[i]);

printf("\n");}Iamaboy0123456789字符串字符串及其结束标志无字符串变量，用字符数组处理字符串字符串结束标志：‘\0’例“hello”共5个字符，在内存占6个字节，字符串长度5

hello\01041011081081110内存存放字符ASCII码字符串的输入输出逐个字符I/O：%c整个字符串I/O：%s例用%cvoidmain(){charstr[5];

inti;

for(i=0;i<5;i++)

scanf(“%c”,&str[i]);

for(i=0;i<5;i++)

printf(“%c”,str[i]);}例用%smain(){charstr[5];

scanf(“%s”,str);

printf(“%s”,str);}用字符数组名,不要加&输入串长度<数组维数遇空格或回车结束自动加‘\0’例用gets函数

main(){charstr[5];gets(str);

puts(str);}

字符串处理函数复制字符串函数strcpy和strncpy：strcpy(字符数组1,字符数组2)charstr1[10]="",str2[]={"China"};strcpy(str1,str2);str1str1="China";str1=str2;两个语句都非法，产生错误求字符串长度函数strlen：strlen(字符串)charstr[10]={"China"};printf("%d",strlen(str));答案：5

字符串处理函数字符串比较函数：strcmp(字符串1，字符串2)字符串按字典序比较大小，如：

“abc”<“abcd”

“abc”<“abd”

“xyz”=“xyz”函数返回比较结果：字符串1=字符串2，返回0；字符串1>字符串2，返回正整数；字符串1<字符串2，返回负整数。

字符串处理函数字符串连接函数strcat()

char*strcat(chars1[80],chars2[40]);

功能：将s2字符串添加到s1字符串的后面，然后返回s1的地址值。eg.char*strcat(chars1[],chars2[]){

intn=0,j=0;while(s1[n]!=‘\0’)n++;while(s1[n++]=s2[j++]);returns1;}

字符串处理函数例题

从键盘任意输入5个学生的姓名，编程找出并输出按字典顺序排在最前面的学生姓名。等价于求最小字符串

#include<stdio.h>#include<string.h>#defineN80voidmain(){

intn,num;

charstr[N],min[N]; printf("Pleaseenterfivenames:\n");

gets(str); strcpy(min,str);

for(n=1;n<5;n++) { gets(str);

if(strcmp(str,min)<0) {

strcpy(min,str);

} } printf("Theminis:");

puts(min);

}6.9多维数组(P189)二维数组的定义:

数据类型数组名[常量表达式][常量表达式]例inta[3][4];floatb[2][5];

inta[3,4];()inta[3][2]a[0][1]a[1][0]a[1][1]a[2][0]a[2][1]014523a[0][0]a[0][0]a[0][1]a[1][0]a[1][1]a[2][0]a[2][1]二维数组的存储结构intb[2][3]；b[0]b[1]b[1][0]b[1][1]b[1][2]b[0][0]b[0][1]b[0][2]

存放顺序：按行存放，先顺序存放第一行的元素，再存放第二行的元素二维数组b是由2个元素组成每个元素b[i]由包含3个元素的一维数组组成程序举例例将二维数组行列元素互换，存到另一个数组中a=123456b=142536#include<stdio.h>main(){inta[2][3]={{1,2,3},{4,5,6}};

intb[3][2],i,j;

printf("arraya:\n");for(i=0;i<=1;i++){for(j=0;j<=2;j++) {printf("%5d",a[i][j]); b[j][i]=a[i][j]; }

printf("\n");}printf("arrayb:\n");for(i=0;i<=2;i++){

for(j=0;j<=1;j++) printf("%5d",b[i][j]);

printf("\n");}}例求二维数组中最大元素值及其行列号max=a[0][0]fori=0to2forj=0to3a[i][j]>max真假max=a[i][j]row=icolum=j输出：max和row,colum#include<stdio.h>main(){inta[3][4]={{1,2,3,4},{9,8,7,6},{-10,10,-5,2}};

inti,j,row=0,colum=0,max;max=a[0][0];

for(i=0;i<=2;i++)for(j=0;j<=3;j++)

if(a[i][j]>max)

{max=a[i][j]; row=i;

colum=j; }

printf("max=%d,row=%d,\colum=%d\n",max,row,colum);}例读入下表中值到数组，分别求各行、各列及表中所有数之和12461579

8233

2517124622157931

823334

251724373935111#include<stdio.h>main(){intx[5][4],i,j;

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

scanf("%d",&x[i][j]);

for(i=0;i<3;i++)x[4][i]=0;for(j=0;j<5;j++)x[j][3]=0;

for(i=0;i<4;i++)for(j=0;j<3;j++){x[i][3]+=x[i][j];x[4][j]+=x[i][j];x[4][3]+=x[i][j];}for(i=0;i<5;i++){for(j=0;j<4;j++)printf("%5d\t",x[i][j]);

printf("\n");}}

例求二维数组中各行元素之和Get_sum_row(intx[][3],intresult[],introw,int

col){inti,j;for(i=0;i<row;i++){result[i]=0; for(j=0;j<col;j++) result[i]+=x[i][j];}}voidmain(){inta[2][3]={3,6,9,1,4,7};

intsum_row[2],row=2,col=3,i;

Get_sum_row(a,sum_row,row,col);for(i=0;i<row;i++)

printf("Thesumofrow[%d]=%d\n",i+1,sum_row[i]);}314679asum_rowxresult1812从键盘上输入的十进制数(long型)以二到十六进制形式输出