計(jì)算機(jī)與信息技術(shù)學(xué)院大一上c語(yǔ)言13-1數(shù)組ianme

1課程內(nèi)容第一章程序設(shè)計(jì)和C語(yǔ)言第二章數(shù)據(jù)對(duì)象與計(jì)算第三章變量、函數(shù)和控制結(jié)構(gòu)第四章基本程序設(shè)計(jì)技術(shù)第五章C程序結(jié)構(gòu)（函數(shù)）第六章數(shù)組第七章指針第八章文件和輸入輸出第九章結(jié)構(gòu)和其它數(shù)據(jù)機(jī)制第十章程序開發(fā)技術(shù)第十一章標(biāo)準(zhǔn)庫(kù)2第十三部分?jǐn)?shù)組3語(yǔ)言需要提供一套數(shù)據(jù)機(jī)制，描述與數(shù)據(jù)有關(guān)的問題：必須足夠豐富，以滿足需要；不能過(guò)龐雜，臃腫難用；也不能太低級(jí)，使描述過(guò)于煩瑣。高級(jí)語(yǔ)言的數(shù)據(jù)機(jī)制：把數(shù)據(jù)分為類型，每個(gè)類型是一個(gè)數(shù)據(jù)集。提供一組基本數(shù)據(jù)類型；確定其書寫方式；為各類型提供一組基本操作。提供一組由簡(jiǎn)單數(shù)據(jù)類型或?qū)ο髽?gòu)造復(fù)合數(shù)據(jù)類型或?qū)ο蟮臋C(jī)制。組合的數(shù)據(jù)對(duì)象稱為復(fù)合數(shù)據(jù)對(duì)象。由所有“同類的”復(fù)合對(duì)象形成的類型稱為復(fù)合數(shù)據(jù)類型，組成部分稱為成分/成員/元素。4基本類型構(gòu)造類型指針類型空類型void定義類型typedef數(shù)值類型字符類型char

8位枚舉類型enum整型浮點(diǎn)型單精度型float

32位雙精度型double

64位短整型short

16位長(zhǎng)整型long

32位整型int

16位數(shù)組結(jié)構(gòu)體struct共用體unionC數(shù)據(jù)類型由基本類型數(shù)據(jù)按一定規(guī)則組成的，也稱為“導(dǎo)出類型”數(shù)組5問題:輸入學(xué)生的學(xué)號(hào),成績(jī),

計(jì)算平均成績(jī),

計(jì)算每個(gè)學(xué)生的成績(jī)與平均成績(jī)的差,

差>=10成績(jī)等級(jí)A0<=差<10成績(jī)等級(jí)B

其它成績(jī)等級(jí)C

設(shè):學(xué)號(hào)doublen1,n2,n3,n4,…,n30;

成績(jī)doubles1,s2,s3,s4,…,s30;能否:一個(gè)變量名對(duì)應(yīng)多個(gè)連續(xù)的存儲(chǔ)單元:數(shù)組數(shù)組是程序中最常用的結(jié)構(gòu)數(shù)據(jù)類型，用來(lái)描述由固定數(shù)目的同一類型的元素組成的數(shù)據(jù)結(jié)構(gòu)6數(shù)組的概念、定義和使用數(shù)組程序?qū)嵗龜?shù)組作為函數(shù)參數(shù)字符數(shù)組和字符串兩維和多維數(shù)組編程實(shí)例主要內(nèi)容71數(shù)組的概念、定義和使用數(shù)組（array）:是多個(gè)同類型數(shù)據(jù)對(duì)象的組合。一個(gè)數(shù)組匯集了多個(gè)數(shù)據(jù)項(xiàng)，數(shù)組元素?？蓮臄?shù)組出發(fā)處理各元素，以統(tǒng)一方式處理一批/所有元素，是數(shù)組和一組獨(dú)立變量的主要區(qū)別。為此需要：數(shù)組描述，數(shù)組變量定義，初值化數(shù)組使用，包括通過(guò)數(shù)組變量使用其元素?cái)?shù)組實(shí)現(xiàn)，數(shù)組的存儲(chǔ)方式8數(shù)組變量定義定義數(shù)組變量（定義數(shù)組）時(shí)需說(shuō)明：數(shù)組元素類型數(shù)組（變量）名數(shù)組（變量）的元素個(gè)數(shù)（也稱數(shù)組大小或長(zhǎng)度）定義方式：

數(shù)據(jù)類型數(shù)組名[常量表達(dá)式]；

例，定義兩個(gè)數(shù)組：

inta[10];

doublea1[100];數(shù)組定義可以與其他變量定義寫在一起，如：

inta2[16],n,a3[25],m;方括號(hào)內(nèi)整型表達(dá)式說(shuō)明元素個(gè)數(shù)，表達(dá)式應(yīng)能靜態(tài)確定值，可用字面量或枚舉常量9可定義外部數(shù)組和局部數(shù)組，包括局部靜態(tài)數(shù)組（用static）,作用域與存在期與簡(jiǎn)單變量相同。數(shù)組的外部說(shuō)明不必描述數(shù)組大小。例：

externinta[];externdoublea1[];下面函數(shù)里數(shù)組定義不合法：voidf(intm,intn){

intb[n];/*非法，編譯時(shí)無(wú)法確定大小*/....} 新C99標(biāo)準(zhǔn)支持這種定義，滿足C99的編譯器很少10基本操作是元素訪問。元素順序編號(hào)，首元素序號(hào)0，其余順序編號(hào)。n元數(shù)組元素編號(hào)是0到n-1。定義：

intb[100];元素編號(hào)為0、1、2、…、99。稱為下標(biāo)或指標(biāo)。元素訪問通過(guò)[]運(yùn)算符，優(yōu)先級(jí)最高，運(yùn)算對(duì)象是數(shù)組名和括號(hào)里表示下標(biāo)的表達(dá)式。表達(dá)式、語(yǔ)句里的b[3]稱為下標(biāo)表達(dá)式或帶下標(biāo)的變量。例：有上面定義后，可寫：

b[0]=1;b[1]=1; b[2]=b[0]+b[1]; b[3]=b[1]+b[2];數(shù)組的使用11數(shù)組的真正意義在于能以統(tǒng)一方式描述對(duì)一組數(shù)據(jù)的處理。下標(biāo)表達(dá)式可用一般的整型表達(dá)式。如：

b[i]=b[i-1]+b[i-2];訪問哪個(gè)元素由i值確定。同一語(yǔ)句可訪問不同元素，可用在循環(huán)里訪問一批元素。for(i=0;i<100;++i){

b[i]+=a1[i]*a2[i];}/*假設(shè)數(shù)組都有定義*/循環(huán)中涉及到300個(gè)基本數(shù)據(jù)對(duì)象。12#include<stdio.h>intmain(){longfib[30];intn;fib[0]=1;fib[1]=1;for(n=2;n<30;++n)fib[n]=fib[n-1]+fib[n-2];

for(n=0;n<30;++n)

{printf("%d",fib[n]);putchar(n%6==5?'\n':'');}/*6個(gè)數(shù)輸出一行*/return0;}例：寫程序創(chuàng)建包含前30個(gè)Fibonacci數(shù)的數(shù)組，然后打印數(shù)組中所有的數(shù)。13對(duì)數(shù)組的多個(gè)或全部元素操作，常用for語(yǔ)句。令循環(huán)變量遍歷數(shù)組下標(biāo)：

for(n=0;n<數(shù)組長(zhǎng)度;++n)...問題：fib是30個(gè)元素的數(shù)組，假設(shè)程序里寫：

for(n=2;n<=30;++n) fib[n]=fib[n-1]+fib[n-2];循環(huán)中試圖訪問fib[30]，實(shí)際無(wú)此元素。用超范圍的下標(biāo)訪問稱為越界訪問，是數(shù)組使用中最常見的錯(cuò)誤。下標(biāo)值超范圍是運(yùn)行中的問題。C不檢查數(shù)組元素訪問的合法性，運(yùn)行中出現(xiàn)越界不會(huì)報(bào)錯(cuò)。超范圍訪問是嚴(yán)重錯(cuò)誤，后果無(wú)法預(yù)料。14數(shù)組的負(fù)數(shù)下標(biāo)C語(yǔ)言只規(guī)定數(shù)組的下標(biāo)必須是整型數(shù)據(jù)，因此負(fù)數(shù)下標(biāo)也合法，但是語(yǔ)義上是否正確，取決于用負(fù)數(shù)下標(biāo)訪問時(shí)是否越界?！璦[-1]a[-2]…a[0]a[2]a[3]a[1]…內(nèi)存空間例給定數(shù)組、函數(shù)及其調(diào)用inta[10];intfunc(intarr[],intn);func(&a[2],8);則在func內(nèi)部，對(duì)arr[-2]和arr[-1]的訪問分別對(duì)應(yīng)于a[0]和a[1]，是合法的，并沒有產(chǎn)生實(shí)際的越界，在arr[-3]就不一定能保證語(yǔ)義正確性了。1516數(shù)組的實(shí)現(xiàn)數(shù)組占據(jù)一片連續(xù)存儲(chǔ)區(qū)，元素順序排列，0號(hào)元素在最前面，各元素占相同空間。如有：

inta[8];a的存儲(chǔ)恰好能存放8個(gè)整型數(shù)據(jù)，情況如圖：a至少相當(dāng)于8個(gè)int變量，a[0]~a[7]可以看作“變量名”。保證元素排在一起，能以統(tǒng)一方式使用。數(shù)組名表示內(nèi)存首地址，是地址常量編譯時(shí)分配連續(xù)內(nèi)存內(nèi)存字節(jié)數(shù)=數(shù)組元素個(gè)數(shù)*

sizeof(元素?cái)?shù)據(jù)類型)17在一些系統(tǒng)里越界訪問可能導(dǎo)致動(dòng)態(tài)錯(cuò)，系統(tǒng)強(qiáng)行終止出錯(cuò)的程序。越界可能破壞本程序的數(shù)據(jù)/程序本身/其他軟件，甚至是整個(gè)系統(tǒng)。編程者要保證數(shù)組下標(biāo)值的合法性，保證不越界。數(shù)組初始化定義數(shù)組時(shí)可直接初始化。外部、局部靜態(tài)或自動(dòng)數(shù)組都可在定義時(shí)進(jìn)行初始化。方法一：定義時(shí)直接初始化intb[4]={1,1,2,3};doubleax[6]={1.3,2.24,5.11,8.37,6.5};

初值表達(dá)式必須是常量表達(dá)式。外部和靜態(tài)數(shù)組在程序開始執(zhí)行前建立并初始化，局部自動(dòng)數(shù)組在程序執(zhí)行進(jìn)入相應(yīng)函數(shù)或復(fù)合語(yǔ)句體時(shí)建立和初始化18這種寫法只能用于數(shù)組初始化，不能用在語(yǔ)句里。若定義時(shí)未初始化，外部和局部靜態(tài)數(shù)組的元素自動(dòng)初始化為0；自動(dòng)數(shù)組處在不明確的狀態(tài)。方法二：只為部分元素提供初值，其余元素將自動(dòng)置0。初始化表元素個(gè)數(shù)不得超過(guò)數(shù)組元素個(gè)數(shù)。例：

intb1[4]={1,2};b1[2]、b1[3]將給初值0。方法三：若給了所有元素的初值，可以不寫數(shù)組大小而只寫方括號(hào)，元素個(gè)數(shù)由初值個(gè)數(shù)確定。例：intfib[]={1,1,2,3,5,8,13,21,34,55};這種寫法能減少維護(hù)負(fù)擔(dān)，有利于程序修改。在語(yǔ)句中對(duì)數(shù)據(jù)元素賦值的方法？19說(shuō)明：數(shù)組必須先定義，后使用只能逐個(gè)引用數(shù)組元素，不能一次引用整個(gè)數(shù)組數(shù)組元素表示形式：數(shù)組名[下標(biāo)]其中：下標(biāo)可以是常量或整型表達(dá)式//順序輸入輸出數(shù)組元素#include<stdio.h>voidmain()

{ inti,a[10]; for(i=0;i<10;i++) a[i]=i; for(i=0;i<=9;i++) printf(“%4d”,a[i]);}//將數(shù)組元素逆序輸出#include<stdio.h>voidmain()

{ inti,a[10]; for(i=0;i<10;i++) a[i]=i; for(i=9;i<=0;i--) printf(“%4d”,a[i]);}例一維數(shù)組的輸入與輸出。20數(shù)組的概念、定義和使用數(shù)組程序?qū)嵗龜?shù)組作為函數(shù)參數(shù)字符數(shù)組和字符串兩維和多維數(shù)組編程實(shí)例主要內(nèi)容212數(shù)組處理程序?qū)嵗簭淖址较聵?biāo)（整數(shù)）寫程序統(tǒng)計(jì)由標(biāo)準(zhǔn)輸入得到的文件中數(shù)字字符的個(gè)數(shù)。

可定義10個(gè)計(jì)數(shù)變量，用if或switch區(qū)分情況，遇數(shù)字字符（isdigit）時(shí)對(duì)應(yīng)計(jì)數(shù)器加1。不需要數(shù)組。將字符看作整數(shù)可得到另一解法。常見字符集里數(shù)字順序排列，ASCII字符集里0到9的編碼是48到57。利用這個(gè)事實(shí)，用10個(gè)元素的計(jì)數(shù)器數(shù)組可以更方便地完成對(duì)數(shù)字出現(xiàn)的統(tǒng)計(jì)。22intcs[10];用cs[0]記錄'0'出現(xiàn)次數(shù)，余類推。若c是數(shù)字，對(duì)應(yīng)計(jì)數(shù)器加1可以寫成：++cs[c-'0'];/*c-'0'正是對(duì)應(yīng)計(jì)數(shù)器的下標(biāo)*/#include<stdio.h>#include<ctype.h>intcs[10]={0,0,0,0,0,0,0,0,0,0};intmain(){

intc,i;while((c=getchar())!=EOF)if(isdigit(c))++cs[c-'0'];for(i=0;i<10;++i)printf("Digit%d:%d\n",i,cs[i]);return0;}23例：篩法求素?cái)?shù)篩法是求素?cái)?shù)的著名方法：用空間換時(shí)間，1億以內(nèi)的素?cái)?shù)只需要十幾秒的時(shí)間(如不考慮輸出)具體算法：取2開始的整數(shù)序列：令n等于2，它是素?cái)?shù)；劃掉序列中所有n的倍數(shù)；令n等于下一未劃元素（它是素?cái)?shù)），回到步驟2。用數(shù)組表示整數(shù)序列，以元素下標(biāo)表示對(duì)應(yīng)整數(shù)。數(shù)組an，an[0]代表0，an[i]代表i。每個(gè)數(shù)只需表示劃掉或未劃掉，用0/1表示。開始時(shí)元素置1（即假設(shè)所有元素都是素?cái)?shù)），而后不斷將元素置0，直到確定了給定范圍里的所有素?cái)?shù)。

24假設(shè)NUM是給定范圍：/*建數(shù)組an，元素初始化1，將an[0]和an[1]置0（它們不是素?cái)?shù)）*/for(inti=2;i值不大于某個(gè)數(shù);++i)if(an[i]==1)//i是素?cái)?shù)

for(intj=i*2;j<NUM;j+=i)an[j]=0;/*i的倍數(shù)都不是素?cái)?shù)*/外層循環(huán)何時(shí)結(jié)束？可用NUM作為界限。檢驗(yàn)一個(gè)數(shù)是不是素?cái)?shù)，只要看比它的平方根小的素?cái)?shù)是不是能整除它

，因此只要i超過(guò)NUM的平方根，就可以劃掉到既定范圍內(nèi)的所有合數(shù)。123456789101112131415161718192021222324251不算遍歷一遍，劃掉2的倍數(shù)：得235791113151719212325遍歷一遍，劃掉3的倍數(shù)：得2357111317192325遍歷一遍，劃掉5的倍數(shù)：得2357111317192325#include<stdio.h>enum{NUM=200};intan[NUM+1];intmain(void){inti,j;an[0]=an[1]=0;/*建立初始向量*/for(i=2;i<=NUM;++i)an[i]=1;for(i=2;i*i<=NUM;++i)

if(an[i]==1)for(j=i*2;j<=NUM;j+=i)an[j]=0;for(i=2,j=0;i<=NUM;++i)if(an[i]!=0)printf("%d",i);putchar('\n');return0;}26例：成績(jī)分類寫程序輸入一批學(xué)生成績(jī)（≤200）。先輸出不及格成績(jī)，再輸出及格成績(jī)，最后輸出不及格和及格的人數(shù)。

無(wú)法在輸入過(guò)程中完成(除非輸入兩遍)。用數(shù)組記錄學(xué)生成績(jī)，輸入記入數(shù)組，而后輸出，可避免重復(fù)輸入

數(shù)據(jù)裝入數(shù)組后有許多可能處理方法。最簡(jiǎn)單的是兩次掃描數(shù)組，第一次輸出不及格成績(jī)，第二次輸出及格的成績(jī)。統(tǒng)計(jì)工作可在某次掃描中完成（也可在輸入中完成），兩部分人數(shù)之和就是總?cè)藬?shù)，統(tǒng)計(jì)一部分就夠了。27enum{NUM=200};constdoublePASS=60.0;doublescores[NUM];intmain(){inti,n=0,fail;

while(n<NUM&&scanf("%lf",&scores[n])==1)++n;

/*輸入時(shí)需要判斷不越界*/

for(fail=0,i=0;i<n;++i)if(scores[i]<PASS)

{printf("%f\n",scores[i]);++fail;}

for(i=0;i<n;++i)if(scores[i]>=PASS)printf("%f\n",scores[i]);printf("Fail:%d\nPass:%d\n",fail,n-fail);return0;}28例：多項(xiàng)式求值設(shè)數(shù)組p中存放下列多項(xiàng)式的系數(shù)，其中p[i]存放寫程序求p表示的多項(xiàng)式在指定點(diǎn)的值。方法1：求出各項(xiàng)值累加。假設(shè)指定點(diǎn)值存于x：for(sum=0.0,n=0;n<TERMS;++n){for(t=p[n],i=1;i<=n;++i)t*=x;sum+=t;}循環(huán)體內(nèi)可以改寫為（先算x的冪）：

for(t=1.0,i=1;i<=n;++i)t*=x;sum+=t*p[n];可發(fā)現(xiàn)有大量重復(fù)計(jì)算。29通過(guò)保存前次的t值：for(sum=0.0,t=1.0,n=0;n<TERMS;++n){sum+=t*p[n];t*=x;}方法2：多項(xiàng)式可以變形為Horner范式：按照這個(gè)公式，求值循環(huán)可寫為：for(sum=0.0,n=TERMS-1;n>=0;--n)sum=sum*x+p[n];從計(jì)算量上比較它們：需要多少次加法，多少次乘法。30定義數(shù)組的問題如果數(shù)組表示的是全局?jǐn)?shù)據(jù)集合，需要在多個(gè)函數(shù)里使用，那么可考慮定義為外部數(shù)組。大的數(shù)組應(yīng)定義為外部，以免占大量運(yùn)行?？臻g。一般系統(tǒng)不允許在函數(shù)內(nèi)定義特別大的數(shù)組。若數(shù)組保存著遞歸定義函數(shù)的局部數(shù)據(jù)，就必須定義為自動(dòng)數(shù)組。因?yàn)檫f歸調(diào)用時(shí)需要數(shù)組的多份拷貝。其他情況可以根據(jù)需要自由選擇。31數(shù)組的概念、定義和使用數(shù)組程序?qū)嵗龜?shù)組作為函數(shù)參數(shù)字符數(shù)組和字符串兩維和多維數(shù)組編程實(shí)例主要內(nèi)容323數(shù)組作為函數(shù)參數(shù)

數(shù)組可以作為函數(shù)的參數(shù)，但是在向函數(shù)傳遞數(shù)組時(shí)通常有兩種方法：即：

“地址”的傳遞

“值”的傳遞

33方法一：

用數(shù)組名作為實(shí)際參數(shù)，給函數(shù)傳遞數(shù)組的地址，通過(guò)這個(gè)地址就可以訪問到數(shù)組的元素了——雙向傳遞。#include<stdio.h>#defineN20voidf(intb[],intn,intm){inti;for(i=m;i>=n;i--)b[i+1]=b[i];}voidmain(){inti,a[N]={1,2,3,4,5,6,7,8,9,10};f(a,2,9);for(i=0;i<5;i++)printf(“%4d”,a[i]);}a12345678910

b1098764531

2

3

3

434方法二：

用數(shù)組元素作為實(shí)際參數(shù)，是一種傳值的方式，即：調(diào)用函數(shù)時(shí)要復(fù)制數(shù)據(jù)——單向傳遞。

#include<stdio.h>intfmax(intx,inty){ return(x>y?x:y);}

voidmain(){

inta[10],j,max;

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

scanf(“%d”,&a[j]);

max=a[0];

for(j=1;j<=9;j++)

max=fmax(max,a[j]);

printf(“\n最大值為：%8d\n”,max);}35對(duì)函數(shù)參數(shù)的小結(jié)：“值”傳遞形參和實(shí)參都是普通變量實(shí)參是數(shù)組元素，形參是普通變量“地址”傳遞：形參、實(shí)參都是數(shù)組名，完成雙向傳遞。完成單向傳遞36假設(shè)有多個(gè)數(shù)組都需要求平均值?解決方法：定義以數(shù)組為參數(shù)的函數(shù)。以數(shù)組為參數(shù)，不同調(diào)用可以完成對(duì)不同數(shù)組的計(jì)算。定義以double類型的數(shù)組為參數(shù)求元素平均值的函數(shù)，就可解決所有double數(shù)組的平均值問題設(shè)常量LEN是被處理數(shù)組的長(zhǎng)度。doubleavg0(double

a[])

{doublex=0.0;inti;for(i=0;i<LEN;++i)x+=a[i];returnx/LEN;}/*注意：數(shù)組形參不需要寫數(shù)組大小*/37若數(shù)組a1長(zhǎng)LEN，可用：

x=avg0(a1);avg0有一定通用性，若數(shù)組a2長(zhǎng)度也是LEN：

y=avg0(a2);用符號(hào)常量指定數(shù)組大小可解決許多問題。缺點(diǎn)：若數(shù)組長(zhǎng)度不是LEN，就不能用avg0處理。可見：avg0不夠通用，只能正確處理長(zhǎng)為L(zhǎng)EN的數(shù)組。參數(shù)是使函數(shù)能處理一類問題的基本機(jī)制。為提高數(shù)組處理函數(shù)的通用性，定義時(shí)應(yīng)引進(jìn)長(zhǎng)度參數(shù)，使函數(shù)能處理任何給定長(zhǎng)度的數(shù)組。38改造后的函數(shù)：doubleavg(intlen,doublea[]){doublex=0.0;inti;for(i=0;i<len;++i)x+=a[i];returnx/len;}對(duì)調(diào)用提出的新要求：必須正確提供數(shù)組長(zhǎng)度。應(yīng)用實(shí)例：intmain(){doubleb1[]={1.2,2.43,1.74},b2[]={6.5,9.2,8.6,4.5,0.3};printf("%f,%f\n",avg(3,b1),avg(5,b2));return0;}39長(zhǎng)度參數(shù)提高了函數(shù)的通用性。但使用時(shí)必須關(guān)注越界問題。avg(5,b1)引起數(shù)組越界（b1有3個(gè)元素）。長(zhǎng)度實(shí)參可小于數(shù)組大小，avg(3,b2)求b2前3個(gè)