北京交通大學(xué)C語言課件第6章下

1C語言編程是一項(xiàng)技藝，需要多年的歷練才能達(dá)到較為完善的境界！

----摘自《ExpertCProgramming》高級語言程序設(shè)計主講教師：丁丁計算機(jī)與信息技術(shù)學(xué)院dding@3第六章數(shù)組4要點(diǎn)回顧一維數(shù)組的重要操作排序查找插入刪除元素交換字符數(shù)組的如何定義，如何初始化？字符數(shù)組的有效長度和字符數(shù)組？常用的字符串處理函數(shù)有哪些？5例，找出（標(biāo)準(zhǔn)輸入）文本中最長行并輸出保存已讀最長行以輸出，數(shù)組maxline，按字符串形式。

數(shù)組line保存新行，更長時轉(zhuǎn)存maxline。假定行長不超過1022字符，用符號常量定義數(shù)組大小。函數(shù)getline讀入一行，存入?yún)?shù)數(shù)組并返回行長。需防止越界，用參數(shù)limit控制實(shí)參數(shù)組長度。intgetline(intlimit,charline[]);基本處理框架：

while(還有新行輸入)if(新行比已記錄的最長行更長)

記錄新行及其長度;

輸出記錄下來的最長行;6行總有字符(空行有換行符)，返回值>0。文件結(jié)束時返回0。設(shè)MAXLEN表示數(shù)組長度，大循環(huán)可寫為：while(getline(MAXLEN,line)!=0)..intmain(){intn,max=0;/*記錄當(dāng)前行和最長行長度*/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;/*當(dāng)前行和最長行長*/while((n=getline())>0)if(n>max){max=n;strcpy(maxline,line);}if(max>0)printf("%s\n",maxline);return0;}另一種寫法：把兩個數(shù)組作為外部變量，各函數(shù)里直接訪問，不再作為參數(shù)傳遞。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;}優(yōu)點(diǎn)：可簡化函數(shù)定義和參數(shù)描述。缺點(diǎn)：數(shù)組名寫在函數(shù)定義里，造成函數(shù)對全局?jǐn)?shù)據(jù)的依賴。10程序的缺點(diǎn)：1）固定數(shù)組限制了能讀入的最長行；2）出現(xiàn)超長行時出現(xiàn)截斷，且長度統(tǒng)計錯誤。長度統(tǒng)計錯誤問題易解決：數(shù)組滿后繼續(xù)讀字符計數(shù)，但字符不存入line。最后得到實(shí)際最長行的長度，及該行中不超過1022個實(shí)際字符。人們傾向于把程序里大型、唯一、許多函數(shù)公用的數(shù)據(jù)（如大數(shù)組）定義為外部變量。一般數(shù)據(jù)用參數(shù)傳遞。對于具體問題應(yīng)怎樣處理，要考慮軟件系統(tǒng)實(shí)現(xiàn)各方面的問題，如方便、清晰、數(shù)據(jù)安全等因素。怎么辦？2023/2/6高級語言程序設(shè)計11主要內(nèi)容：數(shù)組6.1數(shù)組的概念、定義和使用6.2數(shù)組處理程序?qū)嵗?.3數(shù)組作為函數(shù)參數(shù)6.4字符數(shù)組與字符6.5兩維和多維數(shù)組6.6編程實(shí)例12一維數(shù)組有一個下標(biāo)，元素線性排列。需要處理更復(fù)雜的結(jié)構(gòu)，如數(shù)值應(yīng)用中的矩陣。矩陣為兩維，元素通過兩個下標(biāo)指定。如何表示？例：計算兩個8×8的矩陣的和及乘積計算三維空間中的一系列點(diǎn)的中心。13二維數(shù)組的定義定義方式：

數(shù)據(jù)類型數(shù)組名[常量表達(dá)式][常量表達(dá)式]；例inta[3][4];doubleb[2][5];intc[2][3][4];

inta[3,4];()行數(shù)列數(shù)元素個數(shù)=行數(shù)*列數(shù)

二維和多維數(shù)組稱a為3×4的int（二維）數(shù)組，b為2×5的double（二維）數(shù)組等，c為2×3×4的int（三維）數(shù)組14數(shù)組元素的存放順序原因:內(nèi)存是一維的二維數(shù)組：按行序優(yōu)先多維數(shù)組：最右下標(biāo)變化最快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]

二維和多維數(shù)組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個元素的一維數(shù)組組成二維數(shù)組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]二維數(shù)組理解a是開始位置（數(shù)組a的首地址）也是a[0]的開始位置，也是a[0][0]的位置16二維數(shù)組元素的初始化分行初始化：

例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二維數(shù)組元素的初始化按元素排列順序初始化：

例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設(shè)有數(shù)組定義：doublea[3][2];intb[4][4]; a表示整個數(shù)組，a[0]、a[1]和a[2]表示成員數(shù)組。a[0][1]表示a的0成員數(shù)組中下標(biāo)1的元素。例：a[2][1]=a[0][1]+a[1][1];二維（多維）數(shù)組的表示和使用for(i=0;i<4;++i)for(j=0;j<4;++j)b[i][j]=i+j;19例：向一個二維數(shù)組輸入并輸出其全部元素#include<stdio.h>intmain(){inti,j;intb[3][2];printf(“輸入數(shù)據(jù)：\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':'');例：寫程序段求出由兩維數(shù)組A、B表示的5×5矩陣的乘積，存入兩維數(shù)組C（設(shè)A，B已有值）并輸出。21例：將5個同學(xué)的姓名從小到大排序并輸出#include<stdio.h>#include<string.h>voidmain(){ charname[5][20],temp[20]; inti,j; printf("請輸入學(xué)生姓名:\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("學(xué)生排序名單為：\n"); for(i=0;i<5;i++) printf("%s\n",name[i]);}22二維（多維）數(shù)組作為函數(shù)參數(shù)下面函數(shù)求出n×5數(shù)組中數(shù)據(jù)均值（n是參數(shù)）：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的數(shù)組，但不能用于例如4×7的數(shù)組下章將介紹一種定義通用函數(shù)的方法。作為函數(shù)參數(shù)時不必給出最左一維長度，但要求給出除最左一維外其他各維的長度。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高級語言程序設(shè)計24主要內(nèi)容：數(shù)組6.1數(shù)組的概念、定義和使用6.2數(shù)組處理程序?qū)嵗?.3數(shù)組作為函數(shù)參數(shù)6.4字符數(shù)組與字符串6.5兩維和多維數(shù)組6.6編程實(shí)例25本節(jié)討論一些基于數(shù)組的編程實(shí)例。一個具體問題可寫出許多不同的程序。從問題到程序的工作過程中，許多地方需要編程者做出選擇。有些選擇涉及對問題的不同考慮或認(rèn)識，可能引起程序間的顯著差異。26例1：成績直方圖文件里保存著一批學(xué)生成績，寫程序讀入這些成績，產(chǎn)生其平均值M和標(biāo)準(zhǔn)差S，并做直方圖。有定義：程序中需要反復(fù)使用學(xué)生成績，應(yīng)存入數(shù)組(double型)。程序工作比較多，考慮將主要工作劃分為若干函數(shù)。程序工作分為三步（第一層分解）：輸入，計算并輸出統(tǒng)計量，計算并輸出直方圖。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;}程序主體結(jié)構(gòu)函數(shù)原型28intreadscores(intlim,doubletb[]){inti=0;while(i<lim&&scanf("%lf",&tb[i])==1)++i;returni;}輸入成績函數(shù)29voidstatistics(intn,doubletb[]){inti;doubles,sum,avr;if(n<2)

{/*項(xiàng)數(shù)小于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);}計算并輸出統(tǒng)計值函數(shù)如果需要保留avr和s？30直方圖生成（用橫向的直方圖）：每個成績段輸出一組字符，選H作為基本字符。voidprtHH(intn){inti;for(i=0;i<n;++i)putchar('H');}分段長度可用符號常量SEGLEN表示，根據(jù)它可算出分段數(shù)HISTONUM

。enum{SEGLEN=5,HISTONUM=(100/SEGLEN)+1};31分段成績數(shù)統(tǒng)計：用數(shù)組統(tǒng)計各分段成績?nèi)藬?shù)，將數(shù)組命名為segs，其中應(yīng)有HISTONUM個計數(shù)器。處理的是等長分段，存在從成績得到計數(shù)器下標(biāo)的簡便方法。segs[((int)scores[i])/SEGLEN]++;將成績強(qiáng)制轉(zhuǎn)到int后除以分段長度得到計數(shù)器下標(biāo)。

下面考慮用如下形式輸出直方圖行：<80:23|HHHHHHHHHHHHHH

為使直方圖規(guī)范化，最長行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)/*統(tǒng)計分段人數(shù)*/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分析和改進(jìn)若文件中都是0到100的數(shù)值，程序能得到正確結(jié)果。出現(xiàn)不法數(shù)據(jù)呢？如混入一個178，程序會怎么樣？實(shí)際軟件應(yīng)正確處理合法輸入，還應(yīng)在輸入有錯時合理處置。如果編譯程序遇到不合法程序就垮臺，還可能破壞操作系統(tǒng)，還有人愿意用它嗎？程序抵御不合法數(shù)據(jù)破壞的能力稱為強(qiáng)健性。修改后的readscores如下首先需要檢查每個輸入項(xiàng)，只將合法數(shù)據(jù)存入數(shù)組。有關(guān)數(shù)據(jù)是否處理完的情況只能在循環(huán)結(jié)束后檢查。

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){/*還有數(shù)據(jù)*/printf("Toomanydata.Outputwrong.\n");return0;/*可以用!feof(stdin)判斷*/}returni;}還可考慮其他改進(jìn)。35例2“計算”數(shù)組的大小例：求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;}缺點(diǎn)：改一組數(shù)據(jù)（不是5個）就要改程序（程序里的三個5都要改）。36運(yùn)算符sizeof求類型或變量占內(nèi)存量。sizeof(a)求出a大小，sizeof(a[0])求出a元素大小。(sizeof(a)/sizeof(a[0]))

求出數(shù)組a的元素個數(shù)。#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;}/*更改數(shù)組數(shù)據(jù)時只需添入新數(shù)據(jù)*/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是靜態(tài)處理的運(yùn)算符，數(shù)組參數(shù)實(shí)際上不是數(shù)組（是指針，sizeof(a)求出一個指針的大?。ㄍǔ５扔谝粋€int的大?。?，詳見第7章）。38例3：數(shù)組的劃分6.2.3節(jié)要求分段輸出學(xué)生成績。一種可能方式是調(diào)整成績排列，把不及格成績移到左邊，及格成績移到右邊，而后順序輸出按照某種標(biāo)準(zhǔn)把數(shù)組里的數(shù)據(jù)分段稱為“劃分”考慮一種劃分算法：用兩個下標(biāo)變量，逐步從兩端向中間移，保證下圖所示的不變關(guān)系：循環(huán)開始時令i=0，j=n-1，關(guān)系成立到i<=j不成立時，劃分完成39劃分循環(huán)：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;循環(huán)結(jié)束時，scores里下標(biāo)0到i-1是小于60分的成績，下標(biāo)i到n-1是不小于60的成績，i是不及格人數(shù)。40劃分函數(shù)：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算法思路：數(shù)組a[m]:數(shù)組元素下標(biāo)代表1m只猴子

數(shù)組元素內(nèi)容代表下一只要報數(shù)的猴子整數(shù)p:正在報數(shù)的猴子整數(shù)q:前一個報數(shù)的猴子整數(shù)t:p所指猴子所報的數(shù)初值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報數(shù)開始，直到剩下一只猴子do{}while下一個要報數(shù)的猴子將成為現(xiàn)在報數(shù)的猴子(p!=a[q]);確定現(xiàn)在報數(shù)的猴子，報數(shù)p=a[q];t=t+1;if((t%n)!=0)如果t不是n的倍數(shù)yes：no：當(dāng)前報數(shù)的猴子p成為前一個報數(shù)的猴子qq=p;else當(dāng)前猴子退出，調(diào)整報數(shù)次序當(dāng)前報數(shù)猴子的內(nèi)容a[p]賦給前一個報數(shù)猴子q的內(nèi)容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;}如何用函數(shù)改寫？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+