C語言程序設計課件-數(shù)組(一維二維數(shù)組-排序算法)

C語言編程課件數(shù)組2/66

一維數(shù)組二維數(shù)組向函數(shù)傳遞一維數(shù)組排序算法向函數(shù)傳遞二維數(shù)組主要內(nèi)容3/66

一維數(shù)組二維數(shù)組向函數(shù)傳遞一維數(shù)組排序算法向函數(shù)傳遞二維數(shù)組主要內(nèi)容4/28

數(shù)組的引出讀入100人的成績，然后求平均成績定義100個不同名整型變量，使用多個scanf()語句進行讀入intscore1,score2,…score100;scanf("%d",&score1);scanf("%d",&score2);......sum=score1+score2+…score100;avg=sum/100;一維數(shù)組5/28

數(shù)組一組具有相同類型的變量的集合使用數(shù)組名來標識這組相同的數(shù)據(jù)構成數(shù)組的每個數(shù)據(jù)項稱為數(shù)組元素一維數(shù)組的定義存儲類型數(shù)據(jù)類型數(shù)組名[正整數(shù)]intscore[100];一維數(shù)組6/66

一維數(shù)組的定義數(shù)組大小必須是值為正的常量，不能為變量一旦定義，不能改變大小數(shù)組大小可以用宏來定義，以適應未來可能的變化#defineSIZE10inta[SIZE];一維數(shù)組7/28

一維數(shù)組的初始化數(shù)組定義后如果不給元素初始值，則其初始值將會是隨機數(shù)，直接使用會產(chǎn)生意外的后果，因此使用前必須進行初始化使用花括號包含所有元素，使用逗號分隔元素如果數(shù)組定義的同時給定所有數(shù)組元素，則元素數(shù)量可以省略inta[5]={12,34,56,78,9};inta[]={11,22,33,44,55};一維數(shù)組8/28

一維數(shù)組的初始化如果給定的初始值數(shù)量少于定義的元素數(shù)量，則其余元素默認為0inta[5]={0};//所有元素全部為0一維數(shù)組inta[5]={1，2，3，4};//a[4]=09/66

一維數(shù)組的使用使用數(shù)組下標（數(shù)組元素的索引）訪問數(shù)組元素數(shù)組下標(index)都是從0開始使用a[0]、a[1]、a[2]、……、a[9]這樣的形式訪問每個元素下標既可是常量，也可以是整型表達式，允許快速隨機訪問，如：a[i]可以像使用普通變量一樣使用它們一維數(shù)組a[i++]=0;10/28

一維數(shù)組的存儲系統(tǒng)為數(shù)組分配一塊連續(xù)的存儲空間，大小為：

sizeof(數(shù)據(jù)類型)*數(shù)組元素數(shù)量數(shù)組名表示數(shù)組的首地址，亦即第一個數(shù)組元素的地址數(shù)組名是一個常量，不可以改變一維數(shù)組a[9]a[8]a[7]a[1]a[0]…inta[10];a=1000;&a[5]=?&a[5]=a+5*4=102011/66main(){inta[4]={1,2,3,4},b[4];

b=a;

}解決方法方法1:逐個元素賦值

b[0]=a[0];b[1]=a[1];b[2]=a[2];b[3]=a[3];方法2:通過循環(huán)賦值

inti;for(i=0;i<4;i++){

b[i]=a[i];}原因:數(shù)組名表示數(shù)組的首地址,其值不可改變!一維數(shù)組

如何使兩個數(shù)組的值相等？12/66示例1：顯示用戶輸入的月份擁有的天數(shù)（不包括閏年的月份）一維數(shù)組13/28intscore[100],i,sum=0;floatavg;for(i=0;i<100;i++){ scanf(“%d”,&score[i]);sum=sum+score[i];}avg=sum/SIZE;一維數(shù)組示例2：使用一維數(shù)組求平均成績14/66下標越界是大忌！a[n-1]是數(shù)組的最后一個元素編譯程序不檢查是否越界下標越界，將訪問數(shù)組以外的空間那里的數(shù)據(jù)是未知的，不受我們掌控，可能帶來嚴重后果一維數(shù)組15/66運行程序或單步執(zhí)行觀察變量變化情況可以看到，變量c和a的值因數(shù)組越界而被悄悄破壞了b[0]b[1]b[2]b[3]b[4]b[5]b[6]b[7]b[8]b[9]ca12345612078910114044484c5054585c6064686c一維數(shù)組16/66

一維數(shù)組二維數(shù)組向函數(shù)傳遞一維數(shù)組排序算法向函數(shù)傳遞二維數(shù)組主要內(nèi)容17/66二維數(shù)組的定義存儲類型數(shù)據(jù)類型數(shù)組名[行數(shù)][列數(shù)]第二維“列數(shù)”不能省略用a[i][j]表示二維數(shù)組第i行，第j列的元素值intscore[3][4];二維數(shù)組18/66

二維數(shù)組的存儲一個兩行三列a[2][3]的數(shù)組的邏輯存儲結(jié)構二維數(shù)組的存儲空間大小：數(shù)據(jù)類型大小*一維數(shù)組元素數(shù)量*二維數(shù)組元素數(shù)量a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]第0列第1列第2列第0行第1行二維數(shù)組19/66

二維數(shù)組的存儲按行存儲，即存儲完第一行，再存儲第二行…

依次進行shortinta[2][3];a[0]a[1]a[1][0]a[1][1]a[1][2]a[0][0]a[0][1]a[0][2]a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]二維數(shù)組20/66

二維數(shù)組的初始化按元素初始化按行初始化省略行數(shù)的初始化inta[3][3]={1,2,3,4,5,6,7,8,9}inta[3][3]={{1,2,3},{4,5,6},{7,8,9}}inta[][3]={{1,2,3},{4,5,6},{7,8,9}}二維數(shù)組21/66

二維數(shù)組的初始化初始化時，如果初始化列表中的初值個數(shù)少于數(shù)組元素的個數(shù)，系統(tǒng)自動給后面的元素初始化為0不建議這么做二維數(shù)組//初始化的個數(shù)為6個，而定義的個數(shù)為9個，因此剩下的a[2][0]、a[2][1]、a[2][2]三個元素值自動被初始化為0inta[3][3]={1,2,3,4,5,6}22/66結(jié)果：5,0,0單擊此處編輯母版標題樣式intmain(){inta[][3]={{1,2,3},{4,5},{6},{0}};printf("%d,%d,%d\n",a[1][1],a[2][1],a[3][1]);return0;}二維數(shù)組

二維數(shù)組的初始化以下程序的運行結(jié)果是什么？12345060000023/66【例】若inta[][3]={1,2,3,4,5,6,7}，則a數(shù)組的第一維大小是多少？123456700單擊此處編輯母版標題樣式二維數(shù)組

二維數(shù)組的初始化實例24/66二維數(shù)組實例：從鍵盤輸入年月(包括閏年)，輸出該年該月?lián)碛械奶鞌?shù)25/66

一維數(shù)組二維數(shù)組向函數(shù)傳遞一維數(shù)組排序算法向函數(shù)傳遞二維數(shù)組主要內(nèi)容26/66使用不帶方括號的數(shù)組名作為參數(shù)傳遞傳遞的是數(shù)組的首地址只復制一個地址自然比復制全部數(shù)據(jù)效率高由于首地址相同，故實參數(shù)組與形參數(shù)組占用同一段內(nèi)存在調(diào)用函數(shù)內(nèi)，不僅可以讀這個數(shù)組的元素，還可以修改它們簡單變量和數(shù)組作為參數(shù)傳遞的區(qū)別簡單變量傳遞是變量的值，調(diào)用后，實參的值不會改變數(shù)組傳遞的是數(shù)組的首地址，是對地址進行的操作，形參和實參指向的是同一個地址段，調(diào)用后數(shù)組元素的值可能被改變向函數(shù)傳遞一維數(shù)組27/66簡單變量和數(shù)組作為參數(shù)傳遞的區(qū)別簡單變量向函數(shù)傳遞一維數(shù)組28/66簡單變量和數(shù)組作為參數(shù)傳遞的區(qū)別數(shù)組向函數(shù)傳遞一維數(shù)組29/66實例：計算班級成績平均分從鍵盤輸入某班學生某門課程的成績(已知每班人數(shù)最多不超過40人，具體人數(shù)由鍵盤輸入，試編程計算其平均分可以使用多種方法來實現(xiàn)向函數(shù)傳遞一維數(shù)組30/66程序代碼使用計數(shù)循環(huán)實現(xiàn)實例：計算班級成績平均分31/66程序代碼使用計數(shù)循環(huán)實現(xiàn)實例：計算班級成績平均分32/66程序代碼使用標記循環(huán)實現(xiàn)實例：計算班級成績平均分33/66程序代碼使用標記循環(huán)實現(xiàn)實例：計算班級成績平均分34/66傳遞數(shù)組時為什么同時要傳遞數(shù)組長度？數(shù)組做為形參時，如果使用方括號，方括號內(nèi)的數(shù)字并不能真正表示數(shù)組的長度向函數(shù)傳遞一維數(shù)組時，最好同時再用一個單獨的形參來傳遞數(shù)組的長度向函數(shù)傳遞一維數(shù)組35/66思路：先假設其中的第一個學生成績?yōu)樽罡?/p>

maxScore=score[0];

然后對所有學生成績依次進行比較，如果發(fā)現(xiàn)比現(xiàn)有最高值還高的，則修改現(xiàn)有最高值，即：打印最高分maxScorefor(i=1;i<n;i++){

若score[i]>maxScore

則修改maxScore值為score[i]}實例：計算班級成績最高分36/66流程圖實例：計算班級成績最高分37/66#defineN40intReadScore(intscore[]);intFindMax(intscore[],intn);//函數(shù)聲明intmain(){ intscore[N],max,n; n=ReadScore(score); printf("Totalstudentsare%d\n",n); max=FindMax(score,n);//調(diào)用函數(shù)

printf("Thehighestscoreis%d\n",max); return0;}實例：計算班級成績最高分實現(xiàn)代碼主函數(shù)38/66向函數(shù)傳遞一維數(shù)組實現(xiàn)代碼FindMax函數(shù)實現(xiàn)39/66

一維數(shù)組二維數(shù)組向函數(shù)傳遞一維數(shù)組排序算法向函數(shù)傳遞二維數(shù)組主要內(nèi)容40/28排序算法排序算法排序(sorting)把一系列無序的數(shù)據(jù)按照特定的順序(升序或降序)重新排列為有序序列的過程。交換法(exchange)選擇法(selection)插入排序法(insertion)冒泡法(bubblesort)快速排序法41/28排序算法排序算法交換排序法算法思想(以降序為例)第一步，將第一個數(shù)依次與后面所有的數(shù)進行比較，如果后面的數(shù)較大，則交換兩數(shù)位置第一輪過后，其最大值位于第一個數(shù)的位置第二步，從第二個數(shù)開始，類似第一步，與其后的所有數(shù)依次比較、交換數(shù)據(jù)依此類推，直到最后一輪比較此時，所有元素均按降序排列42/28排序算法84838887618884第一輪：第一輪結(jié)果：

8883848761排序算法交換排序法示例原始數(shù)據(jù)序列：848388876143/28排序算法

8883848761第二輪：83848487第二輪結(jié)果：

8887838461交換排序法示例原始數(shù)據(jù)序列：8483888761排序算法44/28排序算法

8887838461第三輪：8384第三輪結(jié)果：

8887848361交換排序法示例原始數(shù)據(jù)序列：8483888761排序算法45/28排序算法

8887848361第四輪：最終結(jié)果：

8887848361交換排序法示例原始數(shù)據(jù)序列：8483888761排序算法46/28for(i=0;i<n-1;i++){for(j=i+1;j<n;j++){if(score[j]>score[i])

"交換成績score[j]和score[i]"}}排序算法交換排序法偽代碼排序算法47/28temp=score[j];score[j]=score[i];score[i]=temp;排序算法tempscore[j]score[i]？7050705070排序算法交換排序法如何實現(xiàn)交換兩個數(shù)？48/28voidDataSort(intscore[],intn){inti,j,temp;for(i=0;i<n-1;i++){for(j=i+1;j<n;j++){if(score[j]>score[i]){

temp=score[j];score[j]=score[i];score[i]=temp;}}}}交換排序法最終代碼排序算法49/28排序算法排序算法選擇排序法交換排序的缺點交換次數(shù)多，效率低交換排序的改進使用一個最大值下標變量在每次比較中，當后值比當前最大值還大時，不進行交換，只記錄新的最大值下標每輪比較結(jié)束后，如果最大值下標發(fā)生改變，即交換兩數(shù)位置，否則不進行交換50/28排序算法8483888761i=0k=0i≠k交換a[i]和a[k]ik28883848761排序算法交換排序法示例原始數(shù)據(jù)序列：8483888761第一輪：51/28

8883848761i=1k=1i≠k交換a[i]和a[k]ik2888784

83613排序算法交換排序法示例原始數(shù)據(jù)序列：8483888761第二輪：52/28

8887848361i=2k=2i＝k不產(chǎn)生交換ik排序算法第三輪：交換排序法示例原始數(shù)據(jù)序列：848388876153/28排序算法

8887848361i=3k=3i＝k不產(chǎn)生交換ik結(jié)果：888384

8761排序算法交換排序法示例原始數(shù)據(jù)序列：8483888761第四輪：54/28for(i=0;i<n-1;i++){k=i; for(j=i+1;j<n;j++){if(score[j]>score[k])

記錄此輪比較中最高分的元素下標k=j;}

若k中記錄的最大數(shù)不在位置i，則

"交換成績score[k]和score[i]"，}排序算法選擇排序法偽代碼55/66

一維數(shù)組二維數(shù)組向函數(shù)傳遞一維數(shù)組排序算法向函數(shù)傳遞二維數(shù)組主要內(nèi)容56/66使用不帶方括號的數(shù)組名作為參數(shù)傳遞傳遞的是數(shù)組的首地址，也是二維數(shù)組的第一個元素的地址二維數(shù)組做為形參時不可以省略第二維長度由于二維數(shù)組的按行存儲，編譯器必須知道每行有多少個元素，否則會不確定具體的元素地址向函數(shù)傳遞二維數(shù)組57/66實例：計算班級成績某班期末考試科目為數(shù)學、英語、物理。班級人數(shù)不超過40人，要求計算：

1、每個學生的總分和平均分

2、每門課程的總分和平均分數(shù)學英語物理111110101111110102111110103111110104向函數(shù)傳遞二維數(shù)組58/66實例：計算班級成績計算每門課程平均分：向函數(shù)傳遞二維數(shù)組void

AverforCourse(int

score[][COURSE_N],

intsum[],floataver[],intn){

inti,j;

for(j=0;j<COURSE_N