C語言數(shù)組教程PPT

1、CHINA UNIVERSITY OF PETROLEUM(華東)主講教師：孫運(yùn)雷計(jì)算機(jī)與通信工程學(xué)院 計(jì)算機(jī)科學(xué)系入理想的程序，輸出快樂的人生 基本數(shù)據(jù)類型基本數(shù)據(jù)類型：int, float/double, char 數(shù)據(jù)的處理數(shù)據(jù)的處理：根據(jù)問題需求，先作幾個(gè)簡單變量的定義，然后對這些變量賦值并作相應(yīng)的運(yùn)算即得結(jié)果 例如：輸入10個(gè)實(shí)數(shù)，求其平均值。#include int main() int i; float num, sum=0; printf(input 10 numbers: n); for (i=1; i=10; i+) scanf(%f,&n

2、um); sum +=num; printf(average =%.2f n, sum/10.); return 0;輸入理想的程序，輸出快樂的人生 一個(gè)人n門課的成績怎樣存儲(chǔ)和處理？ 一個(gè)班n門課的成績怎樣存儲(chǔ)和處理？ 如何從鍵盤輸入100個(gè)數(shù)然后按相反順序輸出？ 輸入10個(gè)數(shù)，將高于平均值的數(shù)輸出？ .這些數(shù)據(jù)的特點(diǎn)：1.具有相同的數(shù)據(jù)類型2.使用過程中需要保留原始數(shù)據(jù) 為了方便的使用這些數(shù)據(jù)，C語言提供了一種構(gòu)造數(shù)據(jù)類型：數(shù)組。一定要理解并用好數(shù)組！輸入理想的程序，輸出快樂的人生輸入理想的程序，輸出快樂的人生 數(shù)組是具有相同類型的數(shù)據(jù)的順序集合 數(shù)組可以在內(nèi)存中連續(xù)存儲(chǔ)多個(gè)元素Rate1

3、.53.20.0945.39870123數(shù)組元素?cái)?shù)組元素下標(biāo)下標(biāo)Rate0 Rate1 Rate2 Rate3輸入理想的程序，輸出快樂的人生輸入理想的程序，輸出快樂的人生輸入理想的程序，輸出快樂的人生datatype arrayNamesize;類型說明符類型說明符int、char、float 數(shù)組名數(shù)組名常量表達(dá)式：常量表達(dá)式：數(shù)組大小數(shù)組大小int num50;char list_of_initials20;double pressure_level6;#define LIMIT 20. . . int emp_codesLIMIT;數(shù)組和變量一樣，必須數(shù)組和變量一樣，必須先定義后使用先定

4、義后使用；數(shù)組大小定義好后，數(shù)組大小定義好后，將不能改變；將不能改變；數(shù)組大小最好用數(shù)組大小最好用宏宏來定義，以適應(yīng)未來可能的變化來定義，以適應(yīng)未來可能的變化輸入理想的程序，輸出快樂的人生 C89：定義數(shù)組時(shí)不能使用變量定義數(shù)組的大小，即使在此之前變量已經(jīng)賦值，只能使用整形常量定義數(shù)組的大小 C99：允許用變量定義數(shù)組的大小int array(10);int n=5; float scoren;int n;scanf(%d, &n);int datan;char str ;float char10;輸入理想的程序，輸出快樂的人生數(shù)組下標(biāo)從0開始數(shù)組元素在內(nèi)存中按順按順序連續(xù)存放序連續(xù)存

5、放數(shù)組名代表數(shù)組的首地?cái)?shù)組名代表數(shù)組的首地址址，即score的值與score0的地址值相同內(nèi)存內(nèi)存score數(shù)組數(shù)組高地址高地址低地址低地址12345score0score1score2score3score4數(shù)組元素?cái)?shù)組元素序號(hào)序號(hào)int score5;score輸入理想的程序，輸出快樂的人生數(shù)組元素就是變量C語言中，不允許引用數(shù)組進(jìn)行運(yùn)算，只能引用數(shù)組元素基本形式：數(shù)組名數(shù)組名下標(biāo)表達(dá)式下標(biāo)表達(dá)式;說明：p 下標(biāo)表達(dá)式的值必須為整型p 下標(biāo)從0開始，最大下標(biāo)為數(shù)組長度減1p 是下標(biāo)運(yùn)算符，引用數(shù)組元素時(shí)根據(jù)數(shù)組首地址和下標(biāo)計(jì)算出該元素的實(shí)際地址，然后取出該地址的內(nèi)容如引用score2:1.

6、計(jì)算2000+2*4=20082.取出地址2008的內(nèi)容87907786score0score1score2score32000H2004H2008H200CH例如： int a5; a0=20; a4=2*a0;輸入理想的程序，輸出快樂的人生 int a10; scanf(%d,&a10); /*下標(biāo)越界*/ 編譯程序不檢查是否越界 下標(biāo)越界，將訪問數(shù)組以外的空間，可能帶來嚴(yán)重后果#include int main() int a = 1, c = 2, b5 = 0, i; printf(%p, %p, %pn, b, &c, &a); for (i=0; i=8;

7、 i+) bi = i; printf(%d , bi); printf(nc=%d, a=%d, i=%dn, c, a, i); return 0; b0b1b2b3b4 c a ib81234560784044484c5054585c6064686c9運(yùn)行程序或單步執(zhí)行觀察變量變化情況可以看到，變量c和a的值因數(shù)組越界而被悄悄破壞了輸入理想的程序，輸出快樂的人生 初始化：在定義數(shù)組時(shí)給數(shù)組元素賦初值 形式：數(shù)據(jù)類型 數(shù)組名稱數(shù)組長度=數(shù)值列表 在定義數(shù)組時(shí)，對全部數(shù)組元素賦初值： 例如：int a5=0,1,2,3,4; 此時(shí)也可省略數(shù)組長度 例如：int a =0,1,2,3,4; /

8、只寫int a;是錯(cuò)誤的 在定義數(shù)組時(shí)，對部分?jǐn)?shù)組元素賦初值： 例如：int a5=0,1,2; /數(shù)組其余元素自動(dòng)賦0 當(dāng)初值的個(gè)數(shù)多于數(shù)組元素個(gè)數(shù)時(shí)，編譯出錯(cuò) 例如：int a5=0,1,2,3,4,5;輸入理想的程序，輸出快樂的人生l只能逐個(gè)對數(shù)組元素進(jìn)行操作（字符數(shù)組例外）l一般一維數(shù)組的處理用一重循環(huán)來實(shí)現(xiàn)，用循環(huán)變量的值對應(yīng)數(shù)組元素的下標(biāo)動(dòng)態(tài)賦值方法：int a10,i;輸入第3個(gè)數(shù)組元素：scanf( %d ,&a2);輸入整個(gè)數(shù)組元素：for (i=0;i10;i+) scanf( %d , &ai );輸出方法：輸出第1個(gè)數(shù)組元素：printf( %d , a

9、0);輸出整個(gè)數(shù)組元素：for (i=0;i10;i+) printf( %d , ai );輸入理想的程序，輸出快樂的人生【例1】 輸入10個(gè)整數(shù)，輸出它們的和，并逆序打印這些數(shù)#include #define N 10 /數(shù)組程序推薦該用法int main () int i,sum=0,dataN; for( i=0; i=0; i- ) printf( %d, datai ) ; printf(n); return 0; 輸入理想的程序，輸出快樂的人生【例2】用數(shù)組來求Fibonacci數(shù)列前20項(xiàng)#include #define N 20int main() int i,fN=1,1;

10、 for(i=2;iN;i+) fi=fi-2+fi-1; for (i=0; iN ;i+) if (i%4=0) printf(n); printf(%6d,fi); printf(n); return 0; 1 (n=1)Fn = 1 (n=2) Fn-2+Fn-1 (n3)Fibonacci數(shù)列：數(shù)列：1，1，2，3，5，8，13，21，34輸入理想的程序，輸出快樂的人生 數(shù)組是一組相同類型的數(shù)據(jù)組成的有限集合 數(shù)組是可以在內(nèi)存中連續(xù)存儲(chǔ)多個(gè)元素的結(jié)構(gòu) 數(shù)組中的數(shù)據(jù)稱為數(shù)組元素，數(shù)組元素個(gè)數(shù)稱為數(shù)組長度 數(shù)組元素用數(shù)組名和元素下標(biāo)表示，如score0, score1score85937

11、7880123score 4 數(shù)組數(shù)組名名(首地址首地址)下標(biāo)下標(biāo)標(biāo)明了元素在標(biāo)明了元素在數(shù)組中的位置數(shù)組中的位置 ，從，從0開始開始數(shù)組元素?cái)?shù)組元素下標(biāo)下標(biāo)數(shù)組大小數(shù)組大小輸入理想的程序，輸出快樂的人生輸入理想的程序，輸出快樂的人生int num42;4 X 2 = 8數(shù)據(jù)類型數(shù)據(jù)類型 數(shù)組名數(shù)組名常量表達(dá)式常量表達(dá)式1 常量表達(dá)式常量表達(dá)式2;為了便于理解，二維數(shù)組一般理解為幾行幾列的矩陣數(shù)據(jù)類型數(shù)據(jù)類型 數(shù)組名數(shù)組名行大小行大小列大小列大小;num00num01num10num11num20num21num30num31錯(cuò)誤的定義錯(cuò)誤的定義：int a3,4, b(3,4);int c

12、, d(3)(4);輸入理想的程序，輸出快樂的人生int a23;a0a1a10a11a12a00a01a02二維數(shù)組元素在內(nèi)存中的二維數(shù)組元素在內(nèi)存中的存放順序存放順序：先按行存放，再按列存放先按行存放，再按列存放，即，即先順序存放第先順序存放第0行的元素行的元素再存放第再存放第1行的元素，行的元素，a00a01a02a10a11a12輸入理想的程序，輸出快樂的人生 二維數(shù)組元素的引用形式： 例如：int a34;a00=3;a01=a00+10;a34=5; /*下標(biāo)越界*/數(shù)組名數(shù)組名行下標(biāo)行下標(biāo) 列下標(biāo)列下標(biāo);輸入理想的程序，輸出快樂的人生按行賦初值：例如：int a23=1, 2,

13、3, 4, 5, 6; int a23=1, 4, 5;按數(shù)組元素存放順序賦初值：例如：int a23=1, 2, 3, 4, 5, 6; int a23=1, 2, 3;省略行數(shù)（根據(jù)初值個(gè)數(shù)和列聲明自動(dòng)確定行數(shù)）例如：int b3=1, 2, 3, 4, 5, 6, 7, 8, 9,10; int c3=1, 2, 3; 1 2 34 5 61 2 30 0 01 0 04 5 04行行1 2 03 0 0輸入理想的程序，輸出快樂的人生 下列二維數(shù)組的定義都是錯(cuò)誤的:int a, b3, c2;int arr2 = 1,2,3, 4,5,6;int b23=1, 2, 3, 4, 5, 6

14、, 7, 8; 輸入理想的程序，輸出快樂的人生一般二維數(shù)組的處理用二重循環(huán)來實(shí)現(xiàn)，用循環(huán)變量的值控制數(shù)組元素的下標(biāo)int a34,i,j;輸入方法：輸入方法：輸入輸入第第i i行第行第j j列列元素的值：元素的值：scanfscanf(“%d(“%d”, &”, &aij);aij);輸入整個(gè)數(shù)組元素：輸入整個(gè)數(shù)組元素：for (i=0for (i=0; i3; i; i3; i+)+) for(j=0 for(j=0; j4; j; j4; j+)+) scanfscanf(“%d(“%d”, ”, & &aijaij ); );輸出方法：輸出方法：輸出第輸出

15、第i i行第行第j j列列元素的值：元素的值：printfprintf( (“ “%d%d“ “, ai, aij);j);輸出整個(gè)數(shù)組元素：輸出整個(gè)數(shù)組元素：for (for (i=0; i3; ii=0; i3; i+)+) for(j=0 for(j=0; j4; j; j4; j+)+) printfprintf(“%d(“%d”, ”, a ai ij j ); );輸入理想的程序，輸出快樂的人生為一個(gè)為一個(gè)3行行4列的二維數(shù)組輸入列的二維數(shù)組輸入/輸出數(shù)據(jù)輸出數(shù)據(jù)int main() int a34, i, j; for (i=0; i3; i+) for (j=0; j4; j+

16、) scanf(“%d”,&aij); for (i=0; i3; i+) for (j=0; j4; j+) printf(“%5d”, aij); printf(“n”); return 0; 輸入理想的程序，輸出快樂的人生 【例3】將二維數(shù)組a轉(zhuǎn)置存到二維數(shù)組b中654321a635241ba01b10a12b21設(shè)行下標(biāo)為i，列下標(biāo)為j，則: bji aij輸入理想的程序，輸出快樂的人生#include int main() int a23=1,2,3,4,5,6, b32, i, j; printf(數(shù)組a : n); for (i=0; i2 ; i+) for (j=0

17、; j3; j+) printf(%5d, aij); printf(n); for (i=0; i2 ; i+) for (j=0 ; j3; j+) bji=aij; /* 轉(zhuǎn)置 */ printf(數(shù)組 b: n); for (i=0; i=2;i+) for (j=0 ; j=1 ; j+) printf(%5d, bij); printf(n); return 0; 輸入理想的程序，輸出快樂的人生【例4】從鍵盤上為一個(gè)55整型數(shù)組賦值，找出其中的最小值和最大值（平均值，上三角），并顯示出來分析： 設(shè)最大值為max，最小值為min. 1、令max =a00 min =a00 2、對0=

18、row5,0=col5 （顯然要用二重循環(huán)）: 如果arowcolmax，則將其存入max中。 3、輸出min和max。輸入理想的程序，輸出快樂的人生#include int main () int row,col,a55,max,min; printf(請輸入5個(gè)整數(shù)：); for(row=0; row5; row+) for(col=0; col5; col+) scanf(%d,&arowcol); min=a00;max=a00; for(row=0; row5; row+) for(col=0; col5; col+) if (arowcolmax) max=arowcol;

19、 printf(min=%d ,min); printf(max=%dn,max); return 0;輸入理想的程序，輸出快樂的人生 數(shù)組是由同一種數(shù)據(jù)類型的元素系列構(gòu)成 數(shù)組元素按順序在內(nèi)存中連續(xù)存儲(chǔ)，并通過使用數(shù)組下標(biāo)（或索引）來訪問，首元素的索引值為0 數(shù)組必須先聲明然后才能使用。聲明一個(gè)數(shù)組只是為該數(shù)組留出連續(xù)內(nèi)存空間，并不會(huì)為其賦任何值 一維數(shù)組定義：數(shù)據(jù)類型 數(shù)組名數(shù)組大小 二維數(shù)組可以看作是一維數(shù)組的數(shù)組 一維數(shù)組可用一個(gè)循環(huán)動(dòng)態(tài)賦值，而二維數(shù)組可用二重嵌套循環(huán)動(dòng)態(tài)賦值 C把數(shù)組名解釋為該數(shù)組第1個(gè)元素(a0)的首地址，并且C編譯器不檢查所引用的數(shù)組元素下標(biāo)是否越界輸入理想的程

20、序，輸出快樂的人生輸入理想的程序，輸出快樂的人生 根據(jù)實(shí)實(shí)參類型參類型的不同，有兩種傳遞方式 值傳遞 地址傳遞1、值傳遞方式 類型 簡單變量(數(shù)組之前所學(xué)的變量類型) 方式 調(diào)用函數(shù)時(shí)：將實(shí)參值值復(fù)制一份傳給函數(shù)的形參 調(diào)用結(jié)束后：原值不變原值不變（變的只是副本） 特點(diǎn) 實(shí)參與形參占用不同的不同的內(nèi)存單元輸入理想的程序，輸出快樂的人生#include void swap ( int x, int y ) int temp; temp = x; x = y; y = temp;int main ( ) int a, b; scanf(%d%d,&a,&b); swap(a, b)

21、; printf(n%d,%dn,a,b); .20002010201420042008200C5變量變量a 變量變量b(main)9 變量變量temp 變量變量y 變量變量x(swap)559 59COPY輸入理想的程序，輸出快樂的人生2、地址傳遞方式 類型 數(shù)組、指針、結(jié)構(gòu)體 方式 調(diào)用函數(shù)時(shí)：將實(shí)參地址地址復(fù)制一份傳給函數(shù)的形參 調(diào)用結(jié)束后：原原值改變值改變 特點(diǎn) 形參與實(shí)參占用相同的相同的內(nèi)存單元輸入理想的程序，輸出快樂的人生值傳遞值傳遞地址傳遞地址傳遞類型 簡單類型數(shù)組、指針、結(jié)構(gòu)體方式調(diào)用函數(shù)時(shí)：將實(shí)參值復(fù)制一份傳給函數(shù)的形參調(diào)用結(jié)束后：原值不變（變的只是副本）調(diào)用函數(shù)時(shí)：將實(shí)參地

22、址復(fù)制一份傳給函數(shù)的形參調(diào)用結(jié)束后：原值改變特點(diǎn)實(shí)參與形參占用不同的內(nèi)存單元形參與實(shí)參占用相同的內(nèi)存單元簡記為：傳遞簡單類型是值傳遞；傳遞其他類型是地址傳遞輸入理想的程序，輸出快樂的人生輸入理想的程序，輸出快樂的人生 1、一維數(shù)組元素作函數(shù)參數(shù) 【例】求5個(gè)整數(shù)中的最小數(shù)#include #define N 5int main( ) int aN,i,m; for(i=0;iN;i+) scanf(%d,&ai); m=a0; for(i=1;iN;i+) m=min(m,ai); printf(min=%dn,m); return 0; int min(int x,int y) re

23、turn (xy?x:y);傳遞的是數(shù)組元素的值值，所以是值值傳遞方式輸入理想的程序，輸出快樂的人生 2、一維數(shù)組名作函數(shù)參數(shù)重點(diǎn) 定義階段： 形參應(yīng)定義為數(shù)組形式，形參數(shù)組的長度可以省略，但是不能省略，否則就不是數(shù)組形式 如 void fun(int myArray, int length) 調(diào)用階段： 實(shí)參為數(shù)組名 如： fun(myArray); 數(shù)組名表示數(shù)組在內(nèi)存中的起始地址，傳遞的是數(shù)組名，所以是地址傳遞方式輸入理想的程序，輸出快樂的人生#include float average(int stu10, int n);int main() int score10, i; float

24、 av; printf(Input 10 scores：n); for( i=0; i10; i+ ) scanf(%d, &scorei); av=average(score,10); printf(Average is：%.2f, av); return 0;float average(int stu10, int n) int i; float total=0; for( i=0; i0 ? total/n : -1; /更安全更安全輸入理想的程序，輸出快樂的人生#include #define N 40int ReadScore(int score);int FindMax(i

25、nt score, int n);int main() int scoreN, max, n;n = ReadScore(score);printf(Total students are %dn, n);max = FindMax(score, n);printf(The highest score is %dn, max); return 0;輸入理想的程序，輸出快樂的人生max(i=0)max(i=2)max(i=3)輸入理想的程序，輸出快樂的人生 假設(shè)其中的一個(gè)學(xué)生成績?yōu)樽罡適axScore = score0; 對所有學(xué)生成績進(jìn)行比較，即 for (i=1; i maxScore 則修改

26、maxScore值為scorei 打印最高分maxScore輸入理想的程序，輸出快樂的人生 有一個(gè)班，30個(gè)學(xué)生，4門課程成績，要求：利用函數(shù)計(jì)算每個(gè)學(xué)生的平均分并在主函數(shù)中輸出平均分。 思路 使用二維數(shù)組作為參數(shù)輸入理想的程序，輸出快樂的人生#include #define SN 30#define CN 4int main()int i,j;float scoreSNCN,sum,avgSN;for(i=0;iSN;i+) sum=0;for(j=0;jCN;j+) scanf(%f,&scoreij); sum=sum+scoreij;avgi=sum/CN;for(i=0;iS

27、N;i+)printf(%.2fn,avgi);return 0;輸入理想的程序，輸出快樂的人生#include #define SN 30#define CN 4int main() int i,j; float scoreSNCN,avgSN; for(i=0;iSN;i+) for(j=0;jCN;j+) scanf(%f,&scoreij); fun(score,avg); for(i=0;iSN;i+) printf(%.2fn,avgi); return 0;void fun(float aCN,float average) float sum; int i,j; for(

28、i=0;iSN;i+) sum=0; for(j=0;jCN;j+) sum=sum+aij; averagei=sum/CN; 二維數(shù)組作函數(shù)參數(shù)方法與一維數(shù)組相同需要注意的是：形參為二維數(shù)組時(shí)，可以省略第一維長度說明，但是不能省略第二維的長度說明。輸入理想的程序，輸出快樂的人生輸入理想的程序，輸出快樂的人生 冒泡排序, Bubble Sort 選擇排序, Selection Sort 雙向冒泡排序, Shaker Sort 插入排序, Insertion Sort 希爾排序, Shell Sort, 也稱縮小增量排序 歸并排序, Merge Sort 堆排序, Heap Sort 快速排序

29、快速排序, Quick Sort 猴子排序, Bogo Sort 排序算法動(dòng)畫比較演示 http:/jsdo.it/norahiko/oxIy/fullscreen http:/www.sorting- http:/ for (i=0; in-1; i+) for (j=i+1; j scorei) 交換成績scorej和scorei 輸入理想的程序，輸出快樂的人生temp = scorej;scorej = scorei; scorei = temp; tempscorejscorei ？7050705070輸入理想的程序，輸出快樂的人生#include #define N 10int ma

30、in () int i, j, t, aN; printf(順序輸入%d個(gè)整數(shù)： , N) ; for(i=0; iN; i+) scanf(%d, &ai) ; printf(原序列為：n); for(i=0; iN; i+) printf( %d, ai) ; for(i=0; iN-1; i+) /*控制比較的趟數(shù)*/ for(j=i+1; jai) t=ai; ai=aj; aj=t; printf(n排序后的序列為：n); for(i=0; iN; i+) printf( %d, ai); printf(n); return 0;輸入理想的程序，輸出快樂的人生#include

31、 #define N 10void printArray(int a);void sort(int a,int n);int main( ) int a=11,22,63,97,58, 80,45,32,73,36; printf(Before sort:n); printArray(a); sort(a,N); printf(After sort:n); printArray(a); return 0; void printArray(int b) int i; for (i=0;iN;i+) printf(%5d,bi); printf(n);void sort(int b, int n)

32、 int i,j,t; for (i=0;in-1;i+) for (j=i+1;jbi) t=bi; bi=bj; bj=t; 實(shí)參用數(shù)組實(shí)參用數(shù)組名，相當(dāng)于：名，相當(dāng)于：把把a(bǔ)的地址傳給了形參的地址傳給了形參b形參用數(shù)組定義形參用數(shù)組定義輸入理想的程序，輸出快樂的人生k=1k=2k=0k=1輸入理想的程序，輸出快樂的人生k=3k=4k=3k=4輸入理想的程序，輸出快樂的人生for (i=0; in-1; i+) k = i; for (j=i+1; j scorek)記錄此輪比較中最高分的元素下標(biāo)k=j; 若k中記錄的最大數(shù)不在位置i，則交換成績scorek和scorei， 交換學(xué)號(hào)num

33、k和numi； 輸入理想的程序，輸出快樂的人生void DataSort(int score, long num, int n) int i, j, k, temp1; long temp2; for (i=0; in-1; i+) k = i; for (j=i+1; j scorek) k = j; /*記錄最大數(shù)下標(biāo)位置*/ if (k != i) /*若最大數(shù)不在下標(biāo)位置i*/ temp1 = scorek; scorek = scorei; scorei = temp1; temp2 = numk; numk = numi; numi = temp2; 輸入理想的程序，輸出快樂的人生

34、 【例4】用冒泡法對數(shù)組元素進(jìn)行排序，排序后元素按數(shù)值從小到大順序排列 冒泡排序： 依次比較相鄰的兩個(gè)數(shù)，將大數(shù)上升（放右邊） 第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將大數(shù)放右邊。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，結(jié)果是將最大數(shù)放最右邊。 第二趟：重復(fù)以上過程，仍從第一對數(shù)開始比較，將大數(shù)放右邊，一直比較到倒數(shù)第二對數(shù)，第二趟結(jié)束，得到一個(gè)次大數(shù)。 如此下去，直至最終完成排序。 由于排序過程如同冒氣泡，所以稱作冒泡排序 輸入理想的程序，輸出快樂的人生for (i=0; in-1; i+) for (j=0; j aj+1) 交換aj和aj+1;for (i=0; in-1;

35、 i+)k = i; for (j=i+1; j ak) k = j; /*記錄最大數(shù)下標(biāo)位置*/if (k!= i) /*若最大數(shù)不在下標(biāo)位置i*/交換aj和ak;for (i=0; in-1; i+) for (j=i+1; j ai) 交換aj和ai“;輸入理想的程序，輸出快樂的人生 基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。 整個(gè)排序過程需要三步：1. 尋找一個(gè)中心元素（通常為第一個(gè)數(shù)）2. 所有小于中心點(diǎn)的元素，都移到中心點(diǎn)的左邊；所有大于中心點(diǎn)的元素，都移到中心點(diǎn)的右邊。

36、3. 對中心點(diǎn)左邊和右邊的兩個(gè)子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。輸入理想的程序，輸出快樂的人生 需要解決的問題 當(dāng)已知中心元素的前提下，怎樣將其他元素劃分好？（即：大于中心點(diǎn)在之后，小于中心點(diǎn)在之前）i012345i=0i=1j=5j=5ji=1j=3i=1j=4i=2j=3i=2j=2算法終止算法終止該算法有沒有可以改進(jìn)的地方?輸入理想的程序，輸出快樂的人生 通過動(dòng)畫，可以看出每次中心元素都要交換。根據(jù)劃分的思想最后位置一定是中心元素i012345i=0i=1j=5j=5ji=1j=3i=1j=4i=2j=3i=2j=2算法終止算法終止可以申請一個(gè)變量保存中心元素

37、，以避免交換輸入理想的程序，輸出快樂的人生void QuickSort(int *arr, int left, int right) int i,j,temp; if(lefttemp & ij) j-; /從右向左找第1小于中心點(diǎn)的位置j if(ij) /找到了，位置為j arri = arrj; i+; /將第j個(gè)元素置于左端并重置i while(arritemp & ij) i+; /從左向右找第1個(gè)大于中心點(diǎn)的位置i if(ij) /找到了，位置為i arrj = arri; /將第i個(gè)元素置于右端并重置j j-; while(i!=j); arri = temp; /

38、將中心點(diǎn)放入它的最終位置,本次劃分結(jié)束 QuickSrt(arr, left, i-1); /對中心點(diǎn)左半部遞歸調(diào)用本函數(shù) QuickSort(arr, i+1, right); /對中心點(diǎn)右半部遞歸調(diào)用本函數(shù) *arr為數(shù)組指針，下一章講解 輸入理想的程序，輸出快樂的人生 在頭文件中，提供了一個(gè)快速排序函數(shù)qsort，它的函數(shù)原型如下：void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *); 四個(gè)參數(shù)分別是： 1 待排序數(shù)組首地址 2 數(shù)組中待排序元素?cái)?shù)量 3 各元素的占用空間大小 4

39、指向函數(shù)的指針，用于確定排序的順序 要求學(xué)完指針后能熟練調(diào)用，有余力的同學(xué)可以先學(xué)習(xí)先用 http:/ 表中除首元素和尾元素外，每個(gè)元素都有且只有一個(gè)前驅(qū)；有且只有一個(gè)后繼。 a0ai-1,ai,ai+1aN-1 數(shù)組和鏈表是線性表的兩種實(shí)現(xiàn)方式。 鏈表選學(xué)輸入理想的程序，輸出快樂的人生 例1假設(shè)數(shù)組a中已有5個(gè)整數(shù)，要插入一個(gè)數(shù)x到第1個(gè)數(shù)前面并保持這5個(gè)數(shù)的前后關(guān)系不變，試編程實(shí)現(xiàn)分析分析：數(shù)組最終存放數(shù)組最終存放6個(gè)元素，應(yīng)定義數(shù)組個(gè)元素，應(yīng)定義數(shù)組a6元素下標(biāo)012345初始狀態(tài)12345最后一個(gè)元素沒有使用移動(dòng)過程12345從右邊起各元素依次右移第一個(gè)元素已不再使用插入元素12345

40、首元素位置插入數(shù)XX432151輸入理想的程序，輸出快樂的人生#include #define N 5int main()int i, x, aN+1 ;printf(Input %d numbers:, N ) ;for( i=0; iN; i+ ) scanf(%d, &ai) ;printf( Before insert: );for( i=0; i0; i- ) ai = ai-1 ;ai = x ; / a0=xprintf(After insert: );for( i=0; iN+1; i+ )printf(%d, ai);printf(n); return 0; 后移后移

41、并并插插入數(shù)據(jù)入數(shù)據(jù)輸入理想的程序，輸出快樂的人生 【例2】隨機(jī)產(chǎn)生20個(gè)整數(shù)保存在數(shù)組中，試用順序查找方法查找某個(gè)整數(shù)。 分析： 產(chǎn)生隨機(jī)數(shù)：使用函數(shù)srand()和rand() 順序查找：從數(shù)組的第1個(gè)元素開始逐一與要查找的數(shù)據(jù)進(jìn)行比較，如果有一個(gè)元素與之相同，就是找到了，查找過程即可結(jié)束。如果所有元素都不同于要查找的數(shù)據(jù)，則沒找到。輸入理想的程序，輸出快樂的人生#include #include #include #define N 20int main ( ) int i, x, aN,find=0; srand(time(NULL); /*保證每次產(chǎn)生不同的隨機(jī)數(shù)序列*/ for(i

42、=0; iN; i+) /*產(chǎn)生N個(gè)小于100的隨機(jī)數(shù)*/ ai = rand( )%100; if(i%10=0) printf(n); printf(%6d,ai); printf(n要查找的整數(shù)是? ); scanf(%d, &x ); for(i=0; iN; i+) if(x=ai) find=1; break; if(find)printf(找到了，%d是數(shù)組的第%d個(gè)元素。n,x,i+1); else printf(沒有找到%d。n , x);return 0;一旦找到，設(shè)置find=1，通過break語句跳出循環(huán)輸入理想的程序，輸出快樂的人生 【例3】設(shè)整型數(shù)組a10

43、，刪去某數(shù)x，并使原來的順序關(guān)系不變，試編程實(shí)現(xiàn)。 問題分析： 主要解決兩個(gè)關(guān)鍵問題： 查找某個(gè)元素是否等于x：用順序查找法 找到后刪除該元素：該元素后的數(shù)組元素逐個(gè)向前移動(dòng)一個(gè)位置輸入理想的程序，輸出快樂的人生#include #define N 10int main () int i, k, x, aN, del=0, m=0 ; printf(輸入%d個(gè)整數(shù):, N) ; for(i=0; iN; i+) scanf(%d, &ai) ; printf(原數(shù)組為：); for(i=0; iN; i+) printf( %d, ai) ; printf(n輸入要?jiǎng)h除的數(shù)： ); scanf(%d, &x ); for(i=0; iN; i+) if(ai=x) for(k=i+1;kN;k+) ak-1=ak; del=1; m+ ; if (del) printf(刪除%d后的數(shù)組為： , x);for(i=0; iN-m; i+) printf( %d, ai);printf(n); else printf(沒有