第5章 數(shù)組、字符串、指針.ppt

1、,第5章 數(shù)組,教學(xué)內(nèi)容 理解數(shù)組數(shù)據(jù)類(lèi)型 掌握一維數(shù)組與二維數(shù)組的定義、存放、初始化和基本操作 掌握數(shù)組與指針的關(guān)系 掌握字符串的相關(guān)操作 熟悉使用指針處理字符串的方法 掌握數(shù)組的常用算法 教學(xué)重點(diǎn) 字符串的相關(guān)操作 數(shù)組的常用算法 教學(xué)難點(diǎn) 數(shù)組的常用算法,數(shù)組概念,數(shù)組是一種構(gòu)造數(shù)據(jù)類(lèi)型 數(shù)組是相同類(lèi)型有序數(shù)據(jù)的集合 數(shù)組中的每一個(gè)數(shù)據(jù)稱(chēng)為數(shù)組的一個(gè)元素 數(shù)組中的元素可以通過(guò)統(tǒng)一的數(shù)組名和下標(biāo)來(lái)唯一確定 C編譯器給數(shù)組分配一塊連續(xù)存儲(chǔ)空間依次存放數(shù)組的各個(gè)元素,一維數(shù)組,只用一個(gè)下標(biāo)的數(shù)組稱(chēng)為一維數(shù)組 定義 類(lèi)型說(shuō)明符 數(shù)組名常量表達(dá)式; 例：int a10,b2*3; 常見(jiàn)錯(cuò)誤 int

2、 a(10); int n; scanf(“%d”,#define N 10 int aN;,一維數(shù)組,初始化：在定義數(shù)組的同時(shí)給數(shù)組元素賦初值 基本方法：int a5=1,2,3,4,5; 其它方法：教材P127 存放,引用數(shù)組元素 形式：數(shù)組名下標(biāo) 下標(biāo)可以是常量，也可以是變量 下標(biāo)取值范圍從0開(kāi)始,一維數(shù)組的基本操作,輸入輸出 一次處理一個(gè)元素 循環(huán)實(shí)現(xiàn) main() int a10,i; for(i=0;i10;i+) scanf(“%d”, ,一維數(shù)組的基本操作,求最值 逐個(gè)判斷 #define N 10 main() int aN,i,p,max; /*p存放最大值下標(biāo),max存放

3、最大值*/ /*輸入數(shù)組元素*/ max=a0; p=0; for(i=0;imax)max=ai;p=i; printf(“The max number a%d=%d”,p,max); ,一維數(shù)組的基本操作,倒置 ai與aN-i-1交換 N個(gè)元素交換N/2次 for(i=0;iN/2;i+) t=ai; ai=aN-i-1; aN-i-1=t; ,一維數(shù)組應(yīng)用舉例,例5-4：求某班20個(gè)學(xué)生某門(mén)課程考試的平均成績(jī)及高于平均成績(jī)的學(xué)生人數(shù)。P130 程序流程 輸入數(shù)據(jù)：20個(gè)成績(jī) 處理數(shù)據(jù)：求平均分,統(tǒng)計(jì)高于平均分的人數(shù) 輸出結(jié)果：平均分,人數(shù),源程序,#define NUM 20 main(

4、) int aNUM,n,i; float sum,aver; sum=0; for(i=0;iaver)n+; printf(“%dn”,n);,二維數(shù)組,使用兩個(gè)下標(biāo)的數(shù)組稱(chēng)為二維數(shù)組 定義 類(lèi)型說(shuō)明符 數(shù)組名常量表達(dá)式常量表達(dá)式; 例：int a34; 初始化 基本方法： int a34=1,2,3,4,5,6,7,8,9,10,11,12; 其它方法：教材P135,二維數(shù)組,存放：二維表格，按行存儲(chǔ),引用數(shù)組元素 形式：數(shù)組名下標(biāo) 下標(biāo) 下標(biāo)可以是常量，也可以是變量 下標(biāo)取值范圍從0開(kāi)始,二維數(shù)組應(yīng)用舉例,例:設(shè)一個(gè)學(xué)習(xí)小組有5個(gè)學(xué)生,每個(gè)學(xué)生有3門(mén)課的考試成績(jī),求全組每個(gè)學(xué)生的平均成

5、績(jī). 分析:處理一批性質(zhì)相同的數(shù)據(jù)時(shí),可以考慮使用數(shù)組,并根據(jù)數(shù)據(jù)間的邏輯關(guān)系選擇數(shù)組的維數(shù) 用一個(gè)二維數(shù)組存放考試成績(jī) 用一個(gè)一維數(shù)組存放平均成績(jī),源程序,main() int a53,aver5,sum,i,j; for(i=0;i5;i+) for(j=0;j3;j+) scanf(“%d”, ,如何找出最高成績(jī)?,sum=0;,printf(“n”);,矩陣操作,相乘P136 Cm,n=Am,l*Bl,n,(i=1,2,m; j=1,2,n),for(i=0;iM;i+) for(j=0;jN;j+),cij=0; for(k=0;kL;k+) cij= cij+aik*bkj;, ,

6、矩陣操作,轉(zhuǎn)置P137 方陣轉(zhuǎn)置:可以不定義新數(shù)組 非方陣轉(zhuǎn)置:需要定義新數(shù)組,147 258 369,123 456 789,對(duì)角線上的元素不交換,行列下標(biāo)相同,i=j,aij與aji交換,逐行處理,第i行需要處理N-i-1個(gè)元素,指向一維數(shù)組的指針,可將某個(gè)數(shù)組元素的地址存放在一個(gè)指針變量中 前提:定義一個(gè)基類(lèi)型與數(shù)組元素?cái)?shù)據(jù)類(lèi)型相同的指針變量 例:輸入輸出一維數(shù)組中的所有元素 下標(biāo)法 #include #define N 10 void main() int aN,i; for(i=0;iN;i+) scanf(%d, ,/*等價(jià)于scanf(%d,a+i);*/,/*等價(jià)于printf

7、(%d,*(a+i);*/,指向一維數(shù)組的指針,指針?lè)?#include #define N 10 void main() int aN,i,*p; for(p=a;pa+N;p+) scanf(%d,p); for(p=a;pa+N;p+) printf(%d,*p); ,二維數(shù)組的存儲(chǔ)與訪問(wèn),以int a23為例,數(shù)組a,二維數(shù)組的存儲(chǔ)與訪問(wèn),數(shù)組是一種構(gòu)造數(shù)據(jù)類(lèi)型，構(gòu)成數(shù)組的元素是既可以是整型等基本數(shù)據(jù)類(lèi)型，也可以是數(shù)組數(shù)據(jù)類(lèi)型 一個(gè)二維數(shù)組就是一維數(shù)組，其中每個(gè)元素又都是一個(gè)一維數(shù)組,a0,a1,a,2000,a+1,2006,二維數(shù)組的存儲(chǔ)與訪問(wèn),二維數(shù)組的存儲(chǔ)與訪問(wèn),a0=*(a+

8、0)=*a=2000 for(i=0;iM;i+) for(j=0;jN;j+) scanf(%d,scanf(%d,ai+j);,printf(%d,*(ai+j);,指向二維數(shù)組的指針,指針?lè)?#include #define M 4 #define N 5 void main() int aMN,i,*p; for(p= ,p=a,雖然a+1的值與a10的地址相等，但p+1卻指向a01，因?yàn)閜的基類(lèi)型為整型，每執(zhí)行一次p+，指針將移動(dòng)2個(gè)字節(jié).,指向二維數(shù)組的指針,#include #define M 4 #define N 5 void main() int aMN,i; int (*

9、p)N; /*定義一個(gè)指向包含N個(gè)元素的整型一維數(shù)組的指針變量*/ for(p=a;paM;p+) for(i=0;iN;i+) scanf(%d,*p+i); for(p=a;paM;p+) for(i=0;iN;i+) printf(%d,*(*p+i); printf(n); ,指針變量p的基類(lèi)型為包含N個(gè)元素的整型一維數(shù)組。 每執(zhí)行一次p+，指針將移動(dòng)2*N個(gè)字節(jié)，即指向二維數(shù)組的下一行 *p+i指向當(dāng)前行第i個(gè)元素，*(*p+i)為當(dāng)前行第i個(gè)元素的值,不要將int (*p)N;寫(xiě)成int *pN;，后者表示定義一個(gè)包含N個(gè)元素的一維數(shù)組，每個(gè)元素為基類(lèi)型為整型的指針變量,字符數(shù)組,

10、用于存放字符數(shù)據(jù)的數(shù)組，字符數(shù)組中的一個(gè)元素存放一個(gè)字符 定義 char 數(shù)組名常量表達(dá)式; 初始化 char c7=W, e, l, c, o, m, e; 引用 數(shù)組名下標(biāo),字符串,C語(yǔ)言中沒(méi)有字符串?dāng)?shù)據(jù)類(lèi)型，而是使用字符數(shù)組來(lái)處理字符串 系統(tǒng)自動(dòng)為字符串常量增加一個(gè)字符串結(jié)束標(biāo)志0（ASCII碼為0） 字符串“Welcome”的存放形式,8個(gè)字節(jié),char c=“Welcome”;數(shù)組c的存放形式,8個(gè)元素,c0 c1 c2 c3 c4 c5c6 c7,不等價(jià)于char c7=W, e, l, c, o, m, e;,字符數(shù)組,輸入 逐個(gè)字符輸入 for(i=0;iN;i+)scanf(

11、“%c”,%s格式符使用說(shuō)明:P99100 輸出時(shí),遇0結(jié)束且不輸出0 輸入輸出時(shí),均使用數(shù)組名作參數(shù),scanf函數(shù)以空格和回車(chē)作為輸入結(jié)束標(biāo)志 gets函數(shù)以回車(chē)作為輸入結(jié)束標(biāo)志,字符串函數(shù),P157162 #include 字符串連接：strcat 字符串復(fù)制：strcpy 字符串比較：strcmp 字符串長(zhǎng)度：strlen 字符串小寫(xiě)：strlwr 字符串大寫(xiě)：strupr,字符數(shù)組應(yīng)用舉例,例5-32：加密問(wèn)題教材P173 程序流程 輸入數(shù)據(jù)：一行字符（原文） 處理數(shù)據(jù)：字母字符按規(guī)律轉(zhuǎn)換，非字母字符不變 輸出結(jié)果：密文 算法分析 逐一判斷是否為字母，對(duì)字母進(jìn)行轉(zhuǎn)換 解決方案：循環(huán)

12、循環(huán)條件 循環(huán)變量初始化 改變循環(huán)變量的值,當(dāng)前字符不是結(jié)束標(biāo)志0,取第一個(gè)字符,取下一個(gè)字符,流程圖,A B C D E F G H I J Z K Y L X M W V U T S R Q P O N,源程序,#include #define K 3 main() char st80,strp80,tmp; int i=0; printf(“Enter a stringn”); gets(st); while(sti!=0) if(sti =a,是否可改為: if(sti =a,字符數(shù)組應(yīng)用舉例,例5-33：統(tǒng)計(jì)單詞個(gè)數(shù)P175 程序流程 輸入數(shù)據(jù)：一行字符 處理數(shù)據(jù)：統(tǒng)計(jì) 輸出結(jié)果：?jiǎn)?/p>

13、詞個(gè)數(shù) 算法分析 問(wèn)題實(shí)質(zhì)：統(tǒng)計(jì)問(wèn)題 解決方案： 單詞之間以空格或其它標(biāo)點(diǎn)符號(hào)進(jìn)行分隔 如果當(dāng)前字符不是分隔符,而前一個(gè)字符是分隔符,則表示一個(gè)新單詞開(kāi)始 實(shí)現(xiàn)形式：循環(huán),流程圖,逐個(gè)判斷,源程序,#include main() char st80,last= ,ch; int i=0,nw=0; printf(“Enter a stringn”); gets(str); while(ch=sti)!=0) if(!(ch= |ch=,|ch=;|ch=! |ch=.) if(last= |last=,|last=; |last=!|last=.) nw+; last=ch; i+; prin

14、tf(“%d wordsn”,nw);,字符串,長(zhǎng)度 strlen(“Hello World!”) strlen(“Hello World!n”) strlen(“Hello0World!n”),s1,存儲(chǔ) char s1= “Hello World!n”; char s2= “Hello0World!n”;,12,13,5,訪問(wèn) 下標(biāo)法:s1i 等價(jià)于*(s1+i),指向字符串的指針,使用字符數(shù)組處理字符串的缺點(diǎn) 不能直接將一個(gè)字符串賦值給一個(gè)已經(jīng)定義好的數(shù)組 只能將各個(gè)字符逐一賦值給數(shù)組中各元素 并且數(shù)組中能夠存放的字符串不能超過(guò)數(shù)組長(zhǎng)度 使用指針處理字符串的方法 定義一個(gè)基類(lèi)型為字符型為

15、指針變量 char *s; 將需要處理的字符串直接賦值 s=“Welcome”;,指向字符串的指針,例5-19:字符串復(fù)制P154 使用字符數(shù)組 #include void main() char s1=Hello World!n,s220;/*數(shù)組s2的長(zhǎng)度要定義合適*/ int i; for(i=0;s1i!=0;i+) s2i=s1i; s2i=0; /*復(fù)制循環(huán)中未復(fù)制的字符串結(jié)束標(biāo)志*/ puts(s1);/*printf(“%s”,s1);*/ puts(s2); ,指向字符串的指針,使用指針變量 #include #include #include void main() cha

16、r *s1=Hello World!n,*s2,*t; puts(s1); /*初始化s2，使其指向一塊能夠容納所復(fù)制字符串的存儲(chǔ)空間*/ s2=calloc(strlen(s1)+1,sizeof(char); t=s2; while(*s1!=0) *s2=*s1; s1+; s2+; *s2=0;/*復(fù)制循環(huán)中未復(fù)制的字符串結(jié)束標(biāo)志*/ s2=t; puts(s2);,常用算法,排序 選擇法排序 冒泡法排序 查找 順序查找 二分查找（折半查找） 插入,選擇法排序,算法描述（遞增） 從n個(gè)數(shù)中選出最小的數(shù)與第1個(gè)數(shù)交換位置 除第1個(gè)數(shù)外，從剩下n-1個(gè)數(shù)中選出最小的數(shù)與第2個(gè)數(shù)交換位置 重

17、復(fù)上述步驟n-1次得到一個(gè)遞增序列,排序過(guò)程示意圖,數(shù)組 a0a1a2a3a4 排序前：53691 第1次選擇后：13695 第2次選擇后：13695 第3次選擇后：13596 第4次選擇后：13569,第i次選擇的范圍為第i個(gè)到第n-1個(gè)元素 第i次選擇出的元素與第i個(gè)元素交換,0 1 2 3,流程圖,注意：變量i除了控制選擇次數(shù)外，還表示本次選出的元素將要存放的位置,源程序,#define N 20 main() int aN,i,j,p,t; for(i=0;iN;i+)scanf(“%d”, ,冒泡法排序,算法描述（遞增） 第1趟從第1個(gè)數(shù)到第n個(gè)數(shù)，將相鄰的兩個(gè)數(shù)進(jìn)行比較，并將小的數(shù)

18、調(diào)到前面 第2趟將除第n個(gè)數(shù)外所有相鄰的兩個(gè)數(shù)進(jìn)行比較，并將小的數(shù)調(diào)到前面 重復(fù)n-1趟得到一個(gè)遞增序列,排序過(guò)程示意圖,數(shù)組 a0a1a2a3a4 排序前：53691 第1趟：35691 35691 35691 35619 第2趟：35169 第3趟：31569 第4趟：13569,第i趟比較的范圍為第0個(gè)到第n-i-1個(gè)元素 每趟都是將第j個(gè)元素與第j+1個(gè)元素比較,0 1 2 3,流程圖,源程序,#define N 10 main() int aN,i,j,k,t; for(i=0;iaj+1) t=aj;aj=aj+1;aj+1=t; for(i=0;iN;i+)printf(“%d”

19、,ai); ,順序查找,算法描述 將待查數(shù)據(jù)依次與各個(gè)元素進(jìn)行比較，若找到則返回元素下標(biāo)，若均不相等，則表明查無(wú)此數(shù) 流程圖,正常出口,緊急出口,源程序,#define N 10 main() int aN,i,n; for(i=0;i=N)printf(“not findn”); ,與教材P168程序進(jìn)行比較,體會(huì)變量index的用途,二分查找,前提：在有序數(shù)列中查找 算法描述（以遞增序列為例） 用top代表當(dāng)前查找起始范圍，用bot代表當(dāng)前查找終止范圍 計(jì)算當(dāng)前查找范圍中間位置mid=(top+bot)/2 將待查數(shù)x與第mid個(gè)數(shù)進(jìn)行比較，若相等則返回mid，若大于第mid個(gè)數(shù)則bot=

20、m+1，若小于第m個(gè)數(shù)則top=mid-1 重復(fù)上述步驟直到找到，或發(fā)現(xiàn)topbot，此時(shí)表明查無(wú)此數(shù),查找過(guò)程示意圖,數(shù)組 a0a1a2a3a4 原始數(shù)據(jù)：13579 待查數(shù)據(jù)：3 次數(shù)bottopmid 1042 2010 3111 4,8 bottopmid 042 343 444 43 ,流程圖,緊急出口,正常出口,源程序,#define N 10 main() int aN=1,2,3,4,5,6,7,8,9,10; int bot,top,mid,x; scanf(“%d”, ,與教材P169程序進(jìn)行比較,體會(huì)變量find的用途,插入法,把一個(gè)給定的數(shù)據(jù)x按大小順序插入已排好序的數(shù)組中,插入后數(shù)組元素仍然有序 算法分析 確定插入位置 空出插入位置 插入元素,50,40,30,25,源程序,#define N 10 /* N代表數(shù)據(jù)的個(gè)數(shù) */ void main() /* 定義N+1個(gè)元素的數(shù)組 */ int aN+1=1,4,7,13,16,19,28,36,49,60; int x,p,i; printf( Befor Inserted:n); for(i=0;iN;i+) /* 輸出插入前的數(shù)據(jù)序列 */ prin