第07章數(shù)組.ppt

1、C語(yǔ)言程序設(shè)計(jì) 數(shù)組,楊俊生 Email: Telephone: 65783332,中國(guó)傳媒大學(xué)計(jì)算中心,內(nèi)容提要,7.1 一維數(shù)組的定義和引用 7.2 二維數(shù)組的定義和引用 7.3 字符數(shù)組 7.4 程序舉例,數(shù)組的概念,用基本數(shù)據(jù)類型可以解決所有問(wèn)題嗎？ 例如：對(duì)某班學(xué)生的成績(jī)按由高到低的次序進(jìn)行排序。,3 名學(xué)生,30名學(xué)生,內(nèi)容提要,7.1 一維數(shù)組的定義和引用 7.2 二維數(shù)組的定義和引用 7.3 字符數(shù)組 7.4 程序舉例,一. 概述,構(gòu)造數(shù)據(jù)類型之一 數(shù)組順序存儲(chǔ)數(shù)據(jù)的集合,用數(shù)組名標(biāo)識(shí) 元素屬同一數(shù)據(jù)類型,用數(shù)組名和下標(biāo)確定,順序 連續(xù) 同一 靜態(tài),二. 定義格式,數(shù)據(jù)類型 數(shù)

2、組名常量表達(dá)式；,合法標(biāo)識(shí)符,表示元素個(gè)數(shù) 下標(biāo)從0開(kāi)始, 下標(biāo)運(yùn)算符 單目運(yùn)算符 優(yōu)先級(jí)(1) 左結(jié)合 不能用( ),二. 定義格式例子,int a6;,分配連續(xù)內(nèi)存 內(nèi)存字節(jié)數(shù)=數(shù)組元素個(gè)數(shù)* sizeof(元素?cái)?shù)據(jù)類型),數(shù)組名表示內(nèi)存首地址， 是地址常量，不能被賦值,二. 定義格式說(shuō)明,例 int i=15; int datai; (不能用變量定義數(shù)組尺寸),例 int n; scanf(“%d”, (不能用變量定義數(shù)組尺寸),三. 一維數(shù)組元素的引用,數(shù)組必須先定義，后使用 只能逐個(gè)引用數(shù)組元素，不能一次引用整個(gè)數(shù)組 數(shù)組元素表示形式： 數(shù)組名下標(biāo) 其中：下標(biāo)可以是整型常量或整型表達(dá)

3、式,例 int a10; printf(“%d”,a); () 必須 for(j=0;j10;j+) printf(“%dt”,aj); (),四. 一維數(shù)組的初始化,在定義數(shù)組時(shí)，為數(shù)組元素賦初值,int a5=1,2,3,4,5; 等價(jià)于：a0=1; a1=2; a2=3; a3=4; a4=5;,四. 一維數(shù)組的初始化,數(shù)組不初始化，其元素值為隨機(jī)數(shù) 對(duì)static數(shù)組元素不賦初值，系統(tǒng)會(huì)自動(dòng)賦以0值,static int a5; 等價(jià)于： a0=0; a1=0; a2=0; a3=0; a4=0;,四. 一維數(shù)組的初始化,只給部分?jǐn)?shù)組元素賦初值,如 int a5=6,2,3; 等價(jià)于：

4、 a0=6; a1=2;a2=3; a3=0; a4=0; 如 int a3=6,2,3,5,1; (),四. 一維數(shù)組的初始化,當(dāng)全部數(shù)組元素賦初值時(shí)，可不指定數(shù)組長(zhǎng)度,int a=1,2,3,4,5,6; 編譯系統(tǒng)根據(jù)初值個(gè)數(shù)確定數(shù)組元素個(gè)數(shù),四. 一維數(shù)組的初始化,若想使一個(gè)數(shù)組中所有元素初值為0，可以象下面這樣做,int a5=0,0,0,0,0; 或 int a5=0;,五. 一維數(shù)組程序舉例,讀10個(gè)整數(shù)存入數(shù)組，找出其中最大值和最小值,五. 一維數(shù)組程序舉例,一級(jí)算法: 1. 輸入:for循環(huán)輸入10個(gè)整數(shù) 2. 處理: (a) 先令max=min=x0 (b) 依次用xi和ma

5、x,min比較(循環(huán)) 若maxxi,令min=xi 3. 輸出:max和min,五. 一維數(shù)組程序舉例,二級(jí)算法（細(xì)化輸入）: #define SIZE 10 void main() int xSIZE,i,max,min; printf(“Enter 10 integers:n”); for(i=0;iSIZE;i+) printf(“%d:”,i+1); scanf(“%d”, ,五. 一維數(shù)組程序舉例,二級(jí)算法（細(xì)化輸出）: #define SIZE 10 void main() int xSIZE,i,max,min; printf(Maximum value is %dn,max)

6、; printf(Minimum value is %dn,min); ,五. 一維數(shù)組程序舉例,二級(jí)算法（細(xì)化處理）: #define SIZE 10 void main() int xSIZE,i,max,min; max=min=x0; for(i=1;ixi) min=xi; ,五. 一維數(shù)組程序舉例,#define SIZE 10 void main() int xSIZE,i,max,min; printf(Enter 10 integers:n); for(i=0;ixi) min=xi; printf(Maximum value is %dn,max); printf(Mini

7、mum value is %dn,min); ,補(bǔ)充 簡(jiǎn)單查找算法,種類 順序查找 折半查找,順序查找算法,思想,void main( ) int a10=9,8,7,6,0,1,2,3,4,5; int i,key; printf(“Please input the key:”); scanf(“%d”, ,查找起始位置,哨兵,思考題 如何將給出算法改為原始數(shù)據(jù)由用戶輸入？ 如何將給出算法改為從后向前查找？ 如何將給出算法改為帶哨兵的查找？ 如何將給出算法改為一個(gè)函數(shù)，形參改為“待查找數(shù)組”和“數(shù)組元素個(gè)數(shù)”？,折半查找算法,前提,基本思想,例子,待查找序列必須是有序(例如從小到大),先確定

8、待查記錄所在范圍（區(qū)間）， 然后逐步縮小范圍直到找到或 找不到該記錄為止,設(shè)三個(gè)指針 low指向待查元素所在范圍的下界 high指向待查元素所在范圍的上界 mid為(low+high) / 2 給定的有序表（所有數(shù)值為關(guān)鍵字） (05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92) low=1, high=11, mid=6,折半查找具體算法,void main( ) int a11=0,10,20,30,40,50,60,70,80,90,100; int low,high,mid,key; printf(“Please input the key:”);

9、scanf(“%d”, ,思考題 如何將給出算法改為原始數(shù)據(jù)由用戶輸入？ 如何將給出算法改為一個(gè)函數(shù)，形參改為“待查找數(shù)組”和“數(shù)組元素個(gè)數(shù)”？,練習(xí)題,將給定數(shù)組中的元素顛倒順序排放,1 2 3 4 5 6 7 8 9 10,10 9 8 7 6 5 4 3 2 1,練習(xí)題,將給定數(shù)組中的元素顛倒順序排放,問(wèn)題： 多占用一倍的存儲(chǔ)空間,1 2 3 4 5 6 7 8 9 10,五. 一維數(shù)組程序舉例,用冒泡法對(duì)10個(gè)數(shù)排序（從小到大）,排序過(guò)程： （1）比較第一個(gè)數(shù)與第二個(gè)數(shù)，若為逆序a0a1，則交換；然后比較第二個(gè)數(shù)與第三個(gè)數(shù)；依次類推，直至第n-1個(gè)數(shù)和第n個(gè)數(shù)比較為止第一趟冒泡排序，結(jié)

10、果最大的數(shù)被安置在最后一個(gè)元素位置上 （2）對(duì)前n-1個(gè)數(shù)進(jìn)行第二趟冒泡排序，結(jié)果使次大的數(shù)被安置在第n-1個(gè)元素位置 （3）重復(fù)上述過(guò)程，共經(jīng)過(guò)n-1趟冒泡排序后，排序結(jié)束,例,38,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,#include void main() int a11,i,j,t; printf(Input 10 numbers:n); for(i=1;iai+1) t=ai; ai=ai+1; ai+1=t; printf

11、(The sorted numbers:n); for(i=1;i11;i+) printf(%d ,ai); ,討論,a0沒(méi)有使用 若使用a0，程序應(yīng)該如何改動(dòng)？ 冒泡排序一定要經(jīng)過(guò)n-1趟嗎？,五. 一維數(shù)組程序舉例,用簡(jiǎn)單選擇法對(duì)10個(gè)數(shù)排序（從小到大）,排序過(guò)程： （1）首先通過(guò)n-1次比較，從n個(gè)數(shù)中找出最小的， 將它與第一個(gè)數(shù)交換第一趟選擇排序，結(jié)果最小的數(shù)被安置在第一個(gè)元素位置上 （2）再通過(guò)n-2次比較，從剩余的n-1個(gè)數(shù)中找出關(guān)鍵字次小的記錄，將它與第二個(gè)數(shù)交換第二趟選擇排序 （3）重復(fù)上述過(guò)程，共經(jīng)過(guò)n-1趟排序后，排序結(jié)束,例,初始： 49 38 65 97 76 13

12、27 ,i=1,13,49,一趟： 13 38 65 97 76 49 27 ,i=2,27,38,六趟： 13 27 38 49 65 76 97 ,#include void main() int a11,i,j,k,x; printf(Input 10 numbers:n); for(i=1;i11;i+) scanf(%d, ,討論,a0沒(méi)有使用 若使用a0，程序應(yīng)該如何改動(dòng)？ 如何使用隨機(jī)數(shù)初始化一維數(shù)組？,randomize random,六. 總結(jié),什么時(shí)候使用 當(dāng)處理的數(shù)據(jù)很多,又希望用循環(huán)來(lái)控制時(shí) 當(dāng)運(yùn)算的中間結(jié)果需要保存時(shí) 一維數(shù)組典型使用方法 排序 查找 線性表的插入、刪

13、除等操作 分類統(tǒng)計(jì),到目前為止應(yīng)掌握的算法,隨機(jī)數(shù) 交換 累和：數(shù)列求和、求平均值、求圓 周率的近似值 累乘：N！、Xn 一元二次方程求解 判a、b、c能否構(gòu)成三角形 判閏年 分段函數(shù)的求解,到目前為止應(yīng)掌握的算法,分類統(tǒng)計(jì)：字符分類統(tǒng)計(jì) 十進(jìn)制數(shù)的每一位的分割 窮舉法：判素?cái)?shù)、水仙花數(shù)、換錢(qián)、 巧填算式等 12. 遞推法： Fibonacci數(shù)列、猴子吃桃 13. 查找：順序查找（最大、最小、特定 值）、折半查找 14. 排序：冒泡、簡(jiǎn)單選擇,到目前為止應(yīng)掌握的算法,數(shù)組逆置,內(nèi)容提要,7.1 一維數(shù)組的定義和引用 7.2 二維數(shù)組的定義和引用 7.3 字符數(shù)組 7.4 程序舉例,一. 定義

14、定義方式,數(shù)據(jù)類型數(shù)組名常量表達(dá)式常量表達(dá)式；,行數(shù),列數(shù),元素個(gè)數(shù)=行數(shù)*列數(shù),例 int a34; float b25; int c234; int a3,4; (),一. 定義數(shù)組元素存放順序,原因:內(nèi)存是一維的 二維數(shù)組：按行序優(yōu)先 多維數(shù)組：最右下標(biāo)變化最快,一. 定義對(duì)二維數(shù)組理解,每個(gè)元素ai由包含4個(gè)元素的一維數(shù)組組成,二維數(shù)組a是由3個(gè)元素組成,二. 二維數(shù)組元素的引用,數(shù)組名下標(biāo)下標(biāo),三. 二維數(shù)組元素的初始化,分行初始化,三. 二維數(shù)組元素的初始化,分行初始化,三. 二維數(shù)組元素的初始化,分行初始化,三. 二維數(shù)組元素的初始化,按元素排列順序初始化,三. 二維數(shù)組元素的初

15、始化,按元素排列順序初始化,三. 二維數(shù)組元素的初始化,按元素排列順序初始化,小結(jié) 在程序中為數(shù)組賦值的方法,用scanf語(yǔ)句由用戶輸入,for (i=0 ; i3 ; i+) for (j=0 ; j4 ; j+) scanf(“%d” , ,小結(jié) 在程序中為數(shù)組賦值的方法,由循環(huán)變量自動(dòng)構(gòu)成(前提：元素排列有規(guī)律) 由隨機(jī)數(shù)構(gòu)成,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,for (i=0;i4;i+) for（j=0;j4;j+) aij = 4*i+j+1;,程序舉例,例 將二維數(shù)組行列元素互換，存到另一個(gè)數(shù)組中,思考 1、例子中使用“按行”操作的方法

16、，如果使用 “按列”處理的方法，程序應(yīng)該如何編寫(xiě)？ 2、如果給定的是一個(gè)方陣，如何在一個(gè)數(shù)組上 完成轉(zhuǎn)置操作？,例 求二維數(shù)組中最大元素值及其行列號(hào) 1.設(shè)一個(gè)變量存放最大值max; 2 設(shè)兩個(gè)變量存放最大值在數(shù)組中的行列. 3.遍歷數(shù)組中的每一個(gè)元素 該題的實(shí)質(zhì)：遍歷二維數(shù)組,#include void main() int a34=1,2,3,4, 9,8,7,6, -10,10,-5,2; int i,j,row=0,colum=0,max; max=a00; for(i=0;imax) max=aij; row=i; colum=j; printf(max=%d,row=%d, col

17、um=%dn,max,row,colum); ,實(shí)驗(yàn)提示,找出一個(gè)二維數(shù)組的“鞍點(diǎn)”，即該位置上的元素在該行上最大，在該列上最小。 也可能沒(méi)有鞍點(diǎn)。(習(xí)題7.8) 分析：實(shí)質(zhì)為遍歷數(shù)組,一級(jí)算法： SIZEOFROW 行數(shù) SIZEOFCOL 列數(shù) FOUND 找到鞍點(diǎn)標(biāo)志，初值為0（即沒(méi)有鞍點(diǎn)） 輸入數(shù)組各元素； for(i=0;iSIZEOFROW；i+) 1、找出第i行最大值，并記錄所在“列”到col中； 2、找出col這一列中最小元素minofcol； 3、如果minofcol=aicol，打印鞍點(diǎn)，F(xiàn)OUND=1; if(!FOUND) 打印“沒(méi)有鞍點(diǎn)”；,二級(jí)算法1： 實(shí)質(zhì)：對(duì)二維

18、數(shù)組的引用。 for(i=0;iSIZEOFROW;i+) for(j=0;jSIZEOFCOL;j+) printf(a%d%d:,i,j); scanf(%d, ,二級(jí)算法2：對(duì)第一步的細(xì)化 實(shí)質(zhì)：在一維數(shù)組中找最大值。 maxofrow=ai0; col=0; for(j=1;jSIZEOFCOL;j+) if(maxofrowaij) maxofrow=aij; col=j; ,二級(jí)算法3：對(duì)第二步的細(xì)化 實(shí)質(zhì)：在一維數(shù)組中找最小值。 minofcol=aicol; for(j=0;jajcol) minofcol=ajcol; ,二級(jí)算法4：對(duì)第三步的細(xì)化 if(minofcol=a

19、icol) printf(“an dian is a%d%d= %d”, i,col,aicol); FOUND=1; ,程序： 請(qǐng)同學(xué)們自己實(shí)現(xiàn)該程序。,內(nèi)容提要,7.1 一維數(shù)組的定義和引用 7.2 二維數(shù)組的定義和引用 7.3 字符數(shù)組 7.4 程序舉例,字符數(shù)組 定義,字符數(shù)組的初始化 逐個(gè)字符賦值 用字符串常量 字符數(shù)組的引用,例 char c10, ch34;,例 輸出一個(gè)字符串（實(shí)際上不是一個(gè)嚴(yán)格意義上的字符串）,#include void main() char c10=I, ,a,m, ,a, ,b,o,y; int i; for(i=0;i10;i+) printf(%c,

20、ci); printf(n); ,字符串 字符串及其結(jié)束標(biāo)志 無(wú)字符串變量，用字符數(shù)組處理字符串 字符串結(jié)束標(biāo)志：0,字符串的輸入輸出 逐個(gè)字符I/O： %c 整個(gè)字符串I/O： %s,例 用%c void main() char str5; int i; for(i=0;i5;i+) scanf(“%c”, ,例 用%s void main() char str5; scanf(“%s”, str); printf(“%s”, str); ,用字符數(shù)組名,不要加 printf(“%s”,a); ,例 void main( ) char a =“Hello”; printf(“%s”,a);

21、,結(jié)果：Hello#-=*,結(jié)果：Hello,用“%s”輸出時(shí)，遇0結(jié)束,void main() char a=h,e,l,0,l,o,0; printf(%s,a); ,例,輸出：hel,數(shù)組中有多個(gè)0時(shí), 遇第一個(gè)結(jié)束,例 字符串輸入舉例,#include void main() char a15,b5,c5; scanf(%s%s%s,a,b,c); printf(a=%snb=%snc=%sn,a,b,c); scanf(%s,a); printf(a=%sn,a); ,運(yùn)行情況： 輸入：How are you? 輸出：a=How b=are c=you? 輸入：How are you

22、? 輸出：a=How,scanf中%s輸入時(shí),遇空格或回車結(jié)束,運(yùn)行情況： 輸入：How are you?,例 若準(zhǔn)備將字符串“This is a string.”記錄下來(lái)， 錯(cuò)誤的輸入語(yǔ)句為： （A）scanf(“%20s”,s); （B）for(k=0;k17;k+) sk=getchar(); （C）while(c=getchar()!=n) sk+=c;,遇空格認(rèn)為字符串的輸入結(jié)束,常用的字符串處理函數(shù) 包含在頭文件 string.h,字符串輸出函數(shù)puts 格式：puts(字符數(shù)組) 功能：向顯示器輸出字符串（輸出完，換行） 說(shuō)明：字符數(shù)組必須以0結(jié)束,字符串輸入函數(shù)gets 格式：

23、gets(字符數(shù)組) 功能：從鍵盤(pán)輸入一以回車結(jié)束的字符串放入字符數(shù)組中，并自動(dòng)加0 說(shuō)明：輸入串長(zhǎng)度應(yīng)小于字符數(shù)組尺寸,例 #include void main( ) char string80; printf(“Input a string:”); gets(string); puts(string); 輸入: How are you? 輸出: How are you ?,字符串連接函數(shù)strcat 格式：strcat(字符數(shù)組1,字符數(shù)組2) 功能：把字符數(shù)組2連到字符數(shù)組1后面 返值：返回字符數(shù)組1的首地址 說(shuō)明：字符數(shù)組1必須足夠大 連接前,兩串均以0結(jié)束;連接后,串1 的0取消,

24、新串最后加0,字符串拷貝函數(shù)strcpy 格式：strcpy(字符數(shù)組1,字符串2) 功能：將字符串2，拷貝到字符數(shù)組1中去 返值：返回字符數(shù)組1的首地址 說(shuō)明：字符數(shù)組1必須足夠大 拷貝時(shí)0一同拷貝 不能使用賦值語(yǔ)句為一個(gè)字符數(shù)組賦值,例 char str120,str220; str1=“Hello!”; () str2=str1; (),例 strcpy與strcat舉例,#include #include void main() char destination25; char blank = , c= C+, turbo = Turbo; strcpy(destination, tu

25、rbo); strcat(destination, blank); strcat(destination, c); printf(%sn, destination); ,Turbo C+,字符串比較函數(shù)strcmp 格式：strcmp(字符串1,字符串2) 功能：比較兩個(gè)字符串 比較規(guī)則：對(duì)兩串從左向右逐個(gè)字符比較（ASCII碼），直到遇到不同字符或0為止 返值：返回int型整數(shù)， a. 若字符串1 字符串2， 返回正整數(shù) c. 若字符串1= 字符串2， 返回零 說(shuō)明：字符串比較不能用“=”,必須用strcmp,字符串長(zhǎng)度函數(shù)strlen 格式：strlen(字符數(shù)組) 功能：計(jì)算字符串長(zhǎng)度 返值：返回字符串實(shí)際長(zhǎng)度，不包括0在內(nèi),例 對(duì)于以下字符串，strlen(s)的值為： （1）char s10=A,0,B,C,0,D; （2）char s =“tv0willn”; （3）char s =“x69082n”;,答案：1 3 1,How are you?Hello! Len1=6,Len2=12,Len3=18,例 有三個(gè)字符串，找出其中最大者,#include #include void main() char string20,str32