北京交通大学C语言课件第6章下

1C语言编程是一项技艺，需要多年的历练才能达到较为完善的境界！

----摘自《ExpertCProgramming》高级语言程序设计主讲教师：丁丁计算机与信息技术学院dding@3第六章数组4要点回顾一维数组的重要操作排序查找插入删除元素交换字符数组的如何定义，如何初始化？字符数组的有效长度和字符数组？常用的字符串处理函数有哪些？5例，找出（标准输入）文本中最长行并输出保存已读最长行以输出，数组maxline，按字符串形式。

数组line保存新行，更长时转存maxline。假定行长不超过1022字符，用符号常量定义数组大小。函数getline读入一行，存入参数数组并返回行长。需防止越界，用参数limit控制实参数组长度。intgetline(intlimit,charline[]);基本处理框架：

while(还有新行输入)if(新行比已记录的最长行更长)

记录新行及其长度;

输出记录下来的最长行;6行总有字符(空行有换行符)，返回值>0。文件结束时返回0。设MAXLEN表示数组长度，大循环可写为：while(getline(MAXLEN,line)!=0)..intmain(){intn,max=0;/*记录当前行和最长行长度*/charline[MAXLEN],maxline[MAXLEN];while((n=getline(MAXLEN,line))>0){if(n>max){/*新行更长，保存*/strcpy(maxline,line);max=n;}if(max>0)printf(”Len:%d\n%s\n",max,maxline);return0;}7整个程序：#include<stdio.h>#include<string.h>enum{MAXLEN=1024};intgetline(intlimit,charline[]);intmain(){……}intgetline(intlimit,charline[]){intc,i=0;while(i<limit-2&&(c=getchar())!=EOF&&c!='\n'){line[i]=c;++i;}

if(c=='\n'){line[i]=c;++i;}line[i]='\0';

returni;}8#include<stdio.h>enum{MAXLEN=1024};intgetline(void);charline[MAXLEN],maxline[MAXLEN];intmain(){intn,max=0;/*当前行和最长行长*/while((n=getline())>0)if(n>max){max=n;strcpy(maxline,line);}if(max>0)printf("%s\n",maxline);return0;}另一种写法：把两个数组作为外部变量，各函数里直接访问，不再作为参数传递。9intgetline(void){intc,i=0;while(i<MAXLEN-2&&(c=getchar())!=EOF&&c!='\n'){line[i]=c;++i;}if(c=='\n'){line[i]=c;++i;}line[i]='\0';returni;}优点：可简化函数定义和参数描述。缺点：数组名写在函数定义里，造成函数对全局数据的依赖。10程序的缺点：1）固定数组限制了能读入的最长行；2）出现超长行时出现截断，且长度统计错误。长度统计错误问题易解决：数组满后继续读字符计数，但字符不存入line。最后得到实际最长行的长度，及该行中不超过1022个实际字符。人们倾向于把程序里大型、唯一、许多函数公用的数据（如大数组）定义为外部变量。一般数据用参数传递。对于具体问题应怎样处理，要考虑软件系统实现各方面的问题，如方便、清晰、数据安全等因素。怎么办？2023/2/6高级语言程序设计11主要内容：数组6.1数组的概念、定义和使用6.2数组处理程序实例6.3数组作为函数参数6.4字符数组与字符6.5两维和多维数组6.6编程实例12一维数组有一个下标，元素线性排列。需要处理更复杂的结构，如数值应用中的矩阵。矩阵为两维，元素通过两个下标指定。如何表示？例：计算两个8×8的矩阵的和及乘积计算三维空间中的一系列点的中心。13二维数组的定义定义方式：

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

inta[3,4];()行数列数元素个数=行数*列数

二维和多维数组称a为3×4的int（二维）数组，b为2×5的double（二维）数组等，c为2×3×4的int（三维）数组14数组元素的存放顺序原因:内存是一维的二维数组：按行序优先多维数组：最右下标变化最快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]intc[2][3][4]01234567………...20212223c[0][0][0]c[0][0][1]c[0][0][2]c[0][0][3]c[0][1][0]c[0][1][1]c[0][1][2]c[0][1][3]c[0][2][0]c[0][2][1]c[0][2][2]c[0][2][3]c[1][0][0]c[1][0][1]c[1][0][2]c[1][0][3]c[1][1][0]c[1][1][1]c[1][1][2]c[1][1][3]c[1][2][0]c[1][2][1]c[1][2][2]c[1][2][3]

二维和多维数组15例inta[3][4];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[i]由包含4个元素的一维数组组成二维数组a是由3个元素组成a[0]a[1]a[2]行名014523a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[0][0]a[1][3]a[2][0]a[2][1]a[2][2]a[2][3]a[1][2]67101189a[0]a[1]a[2]二维数组理解a是开始位置（数组a的首地址）也是a[0]的开始位置，也是a[0][0]的位置16二维数组元素的初始化分行初始化：

例inta[2][3]={{1,2,3},{4,5,6}};a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]123456全部初始化

例inta[2][3]={{1,2},{4}};a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]120400部分初始化

例inta[][3]={{1},{4,5}};a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]100450第一维长度省略初始化17二维数组元素的初始化按元素排列顺序初始化：

例inta[2][3]={1,2,3,4,5,6};a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]123456全部初始化

例inta[2][3]={1,2,4};a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]124000部分初始化

例inta[][3]={1,2,3,4,5};a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]123450第一维长度省略初始化18设有数组定义：doublea[3][2];intb[4][4]; a表示整个数组，a[0]、a[1]和a[2]表示成员数组。a[0][1]表示a的0成员数组中下标1的元素。例：a[2][1]=a[0][1]+a[1][1];二维（多维）数组的表示和使用for(i=0;i<4;++i)for(j=0;j<4;++j)b[i][j]=i+j;19例：向一个二维数组输入并输出其全部元素#include<stdio.h>intmain(){inti,j;intb[3][2];printf(“输入数据：\n”);for(i=0;i<3;i++)for(j=0;j<2;j++)scanf(“%d”,&b[i][j]);

for(i=0;i<3;i++)for(j=0;j<2;j++)printf(\nb[%d][%d]=%d”,i,j,b[i][j]);printf(“\n”);return0;}20for(i=0;i<N;++i)for(j=0;j<N;++j){x=0.0;for(k=0;k<N;++k)x+=A[i][k]*B[k][j];C[i][j]=x;}for(i=0;i<N;++i)for(j=0;j<N;++j)printf("%f%c",C[i][j],j==N-1?'\n':'');例：写程序段求出由两维数组A、B表示的5×5矩阵的乘积，存入两维数组C（设A，B已有值）并输出。21例：将5个同学的姓名从小到大排序并输出#include<stdio.h>#include<string.h>voidmain(){ charname[5][20],temp[20]; inti,j; printf("请输入学生姓名:\n"); for(i=0;i<5;i++) gets(name[i]); for(i=0;i<5;i++) for(j=0;j<4-i;j++) if(strcmp(name[j],name[j+1])>0) { strcpy(temp,name[j]); strcpy(name[j],name[j+1]); strcpy(name[j+1],temp); } printf("学生排序名单为：\n"); for(i=0;i<5;i++) printf("%s\n",name[i]);}22二维（多维）数组作为函数参数下面函数求出n×5数组中数据均值（n是参数）：doubleaavg(intn,doublea[][5]){inti,j;doublesum=0.0;

for(i=0;i<n;++i)for(j=0;j<5;++j)sum+=a[i][j];returnsum/(5*n);}可用于任何n×5的数组，但不能用于例如4×7的数组下章将介绍一种定义通用函数的方法。作为函数参数时不必给出最左一维长度，但要求给出除最左一维外其他各维的长度。23例：有一个3*4的矩阵,求出其中的最大元素的值.#include<stdio.h>intmax_value(int,int[][4]);intmax_value(intn,intarray[][4]){inti,j,max=array[0][0];for(i=0;i<n;i++)for(j=0;j<4;j++)if(array[i][j]>max) max=array[i][j];returnmax;}intmain(){staticinta[3][4]={1,3,5,7,2,4,6,8,15,17,34,12};printf(“maxvalueis%d\n”,max_value(3,a));return0;}2023/2/6高级语言程序设计24主要内容：数组6.1数组的概念、定义和使用6.2数组处理程序实例6.3数组作为函数参数6.4字符数组与字符串6.5两维和多维数组6.6编程实例25本节讨论一些基于数组的编程实例。一个具体问题可写出许多不同的程序。从问题到程序的工作过程中，许多地方需要编程者做出选择。有些选择涉及对问题的不同考虑或认识，可能引起程序间的显著差异。26例1：成绩直方图文件里保存着一批学生成绩，写程序读入这些成绩，产生其平均值M和标准差S，并做直方图。有定义：程序中需要反复使用学生成绩，应存入数组(double型)。程序工作比较多，考虑将主要工作划分为若干函数。程序工作分为三步（第一层分解）：输入，计算并输出统计量，计算并输出直方图。27enum{NUM=200,HISTOHIGH=60};doublescores[NUM];intreadscores(intlim,doubletb[]);voidstatistics(intnum,doubletb[]);voidhistogram(intnum,doubletb[],inthigh);

intmain(void){intn=readscores(NUM,scores);statistics(n,scores);histogram(n,scores,HISTOHIGH);return0;}程序主体结构函数原型28intreadscores(intlim,doubletb[]){inti=0;while(i<lim&&scanf("%lf",&tb[i])==1)++i;returni;}输入成绩函数29voidstatistics(intn,doubletb[]){inti;doubles,sum,avr;if(n<2)

{/*项数小于2时的处理*/printf("Datatoofew.\n");return;}

for(sum=0.0,i=0;i<n;++i)sum+=tb[i];avr=sum/n;

for(sum=0.0,i=0;i<n;++i)sum+=(tb[i]-avr)*(tb[i]-avr);s=sqrt(sum/(n-1));printf("Totalstudents:%d\n",n);printf("Averagescore:%f\n",avr);printf("Stddeviation:%f\n\n",s);}计算并输出统计值函数如果需要保留avr和s？30直方图生成（用横向的直方图）：每个成绩段输出一组字符，选H作为基本字符。voidprtHH(intn){inti;for(i=0;i<n;++i)putchar('H');}分段长度可用符号常量SEGLEN表示，根据它可算出分段数HISTONUM

。enum{SEGLEN=5,HISTONUM=(100/SEGLEN)+1};31分段成绩数统计：用数组统计各分段成绩人数，将数组命名为segs，其中应有HISTONUM个计数器。处理的是等长分段，存在从成绩得到计数器下标的简便方法。segs[((int)scores[i])/SEGLEN]++;将成绩强制转到int后除以分段长度得到计数器下标。

下面考虑用如下形式输出直方图行：<80:23|HHHHHHHHHHHHHH

为使直方图规范化，最长行HISTOHIGH个字符。32voidhistogram(intn,doubletb[],inthigh){inti,mx;intsegs[HISTONUM];if(n==0)return;for(i=0;i<HISTONUM;++i)segs[i]=0;for(i=0;i<n;++i)/*统计分段人数*/segs[(int)tb[i]/SEGLEN]++;for(mx=1,i=0;i<HISTONUM;++i)if(segs[i]>mx)mx=segs[i];/*找最大值*/for(i=0;i<HISTONUM;++i){/*输出*/printf("<%3d:%4d|",(i+1)*SEGLEN,segs[i]);prtHH(segs[i]*high/mx);putchar('\n');}}33分析和改进若文件中都是0到100的数值，程序能得到正确结果。出现不法数据呢？如混入一个178，程序会怎么样？实际软件应正确处理合法输入，还应在输入有错时合理处置。如果编译程序遇到不合法程序就垮台，还可能破坏操作系统，还有人愿意用它吗？程序抵御不合法数据破坏的能力称为强健性。修改后的readscores如下首先需要检查每个输入项，只将合法数据存入数组。有关数据是否处理完的情况只能在循环结束后检查。

34intreadscores(intlimit,doubletb[]){inti=0,line=1;doublex;for(;i<limit&&scanf("%lf",&x)==1;++line){

if(0.0<=x&&x<=100.0){tb[i]=x;++i;}elseprintf("Error,line%d\n",line);}

if(i==limit&&scanf("%lf",&x)==1){/*还有数据*/printf("Toomanydata.Outputwrong.\n");return0;/*可以用!feof(stdin)判断*/}returni;}还可考虑其他改进。35例2“计算”数组的大小例：求2.38、3.142、5.64、8.27、6.44的平均值。#include<stdio.h>doublea[5]={2.38,3.142,5.64,8.27,6.44};intmain(){intn;doublesum=0.0;for(n=0;n<5;++n)sum+=a[n];printf("Average:%f\n",sum/5);return0;}缺点：改一组数据（不是5个）就要改程序（程序里的三个5都要改）。36运算符sizeof求类型或变量占内存量。sizeof(a)求出a大小，sizeof(a[0])求出a元素大小。(sizeof(a)/sizeof(a[0]))

求出数组a的元素个数。#include<stdio.h>#defineNUM(x)(sizeof(x)/sizeof(x[0]))doublea[]={2.38,3.142,5.64,8.27,6.44};intmain(){intn;doublesum=0.0;for(n=0;n<NUM(a);++n)sum+=a[n];printf("Average:%f\n",sum/NUM(a));return0;}/*更改数组数据时只需添入新数据*/37#defineNUM(x)(sizeof(x)/sizeof(x[0]))doubleavg(doublea[]){doublex=0.0;inti,len=NUM(a);for(i=0;i<len;++i)x+=a[i];returnx/len;}这样不行：sizeof是静态处理的运算符，数组参数实际上不是数组（是指针，sizeof(a)求出一个指针的大小（通常等于一个int的大小），详见第7章）。38例3：数组的划分6.2.3节要求分段输出学生成绩。一种可能方式是调整成绩排列，把不及格成绩移到左边，及格成绩移到右边，而后顺序输出按照某种标准把数组里的数据分段称为“划分”考虑一种划分算法：用两个下标变量，逐步从两端向中间移，保证下图所示的不变关系：循环开始时令i=0，j=n-1，关系成立到i<=j不成立时，划分完成39划分循环：for(i=0,j=n-1;i<j;){while(i<=j&&scores[i]<PASS)++i;while(i<=j&&scores[j]>=PASS)--j;if(i<j){x=scores[i];scores[i]=scores[j];scores[j]=x;++i;--j;

}}

if(i==j&&scores[i]<PASS)++i;循环结束时，scores里下标0到i-1是小于60分的成绩，下标i到n-1是不小于60的成绩，i是不及格人数。40划分函数：intpartition(intnum,doublea[],doublecut){doublex;inti=0,j=num-1;while(i<=j){while(i<=j&&a[i]<cut)++i;while(i<=j&&a[j]>=cut)--j;if(i<j){x=a[i];a[i]=a[j];a[j]=x;++i;--j;}}returni;}

例4：m个猴子选大王，报n的出列。m=8,n=3算法思路：数组a[m]:数组元素下标代表1m只猴子

数组元素内容代表下一只要报数的猴子整数p:正在报数的猴子整数q:前一个报数的猴子整数t:p所指猴子所报的数初值18765432a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]qpt=0constintm=8;n=3;inta[]={0,2,3,4,5,6,7,8,1};intq=m,p=a[m],t=0;或for(i=1;i<m;i++)a[i]=i+1;a[m]=1;q=m;p=a[m];t=0;0a[0]a[0]不用Josephus问题18765432a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]qpt=0报数开始，直到剩下一只猴子do{}while下一个要报数的猴子将成为现在报数的猴子(p!=a[q]);确定现在报数的猴子，报数p=a[q];t=t+1;if((t%n)!=0)如果t不是n的倍数yes：no：当前报数的猴子p成为前一个报数的猴子qq=p;else当前猴子退出，调整报数次序当前报数猴子的内容a[p]赋给前一个报数猴子q的内容a[q]a[q]=a[p];q43#include<stdio.h>intmain(){ intm=8,n=3; inta[]={0,2,3,4,5,6,7,8,1}; intq,p,t; q=m; t=0; do{ p=a[q]; t=t+1; if((t%n)!=0) q=p; else a[q]=a[p]; }while(p!=a[q]); printf("Thekingis%dth\n",p); return0;}如何用函数改写？pt=1猴子选大王过程do{p=a[q];t=t+1;If((t%n)!=0)

q=p;elsea[q]=a[p];}while(p!=a[q])do{p=a[q];t=t+1;If((t%n)!=0)

q=p;elsea[q]=a[p];}while(p!=a[q])初值:q=m=5;n=2t=0;qa[1]a[2]a[3]a[4]a[5]15432a[1]a[2]a[3]a[4]a[5]15432pqpt=2猴子选大王过程do{p=a[q];t=t+1;If((t%n)!=0)

q=p;elsea[q]=a[p];while(p!=a[q])do{p=a[q];t=t+1;If((t%n)!=0) q=p;else a[q]=a[p];while(p!=a[q])m=5;n=2;qa[1]a[2]a[3]a[4]a[5]15432pa[1]a[2]a[3]a[4]a[5]15432q3pt=3猴子选大王过程do{p=a[q];t=t+1;If((t%n)!=0)

q=p;

elsea[q]=a[p];}while(p!=a[q])do{p=a[q];t=t+1;If((t%n)!=0)

q=p;elsea[q]=a[p];}while(p!=a[q])m=5;n=2;qpa[1]a[2]a[3]a[4]a[5]154323qa[1]a[2]a[3]a[4]a[5]154323pt=4猴子选大王过程do{p=a[q];t=t+1;If((t%n)!=0)

q=p;

elsea[q]=a[p];}while(p!=a[q])do{p=a[q];t=t+1;If((t%n)!=0)

q=p;elsea[q]=a[p];}while(p!=a[q])m=5;n=2;qpa[1]a[2]a[3]a[4]a[5]154323qa[1]a[2]a[3]a[4]a[5]1543235pt=5猴子选大王过程do{p=a[q];t=t+1;If((t%n)!=0)

q=p;elsea[q]=a[p];}while(p!=a[q])do{p=a[q];t=t+1;If((t%n)!=0)

q=p;elsea[q]=a[p];}while(p!=a[q])m=5;n=2;qpa[1]a[2]a[3]a[4]a[5]1543235qa[1]a[2]a[3]a[4]a[5]1543235pt=6猴子选大王过程do{p=a[q];t=t+