第07章數(shù)組.ppt

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

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

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

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

5、x,min比較(循環(huán)) 若maxxi,令min=xi 3. 輸出:max和min,五. 一維數(shù)組程序舉例,二級算法（細化輸入）: #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ù)組程序舉例,二級算法（細化輸出）: #define SIZE 10 void main() int xSIZE,i,max,min; printf(Maximum value is %dn,max)

6、; printf(Minimum value is %dn,min); ,五. 一維數(shù)組程序舉例,二級算法（細化處理）: #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); ,補充 簡單查找算法,種類 順序查找 折半查找,順序查找算法,思想,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ù)由用戶輸入？ 如何將給出算法改為從后向前查找？ 如何將給出算法改為帶哨兵的查找？ 如何將給出算法改為一個函數(shù)，形參改為“待查找數(shù)組”和“數(shù)組元素個數(shù)”？,折半查找算法,前提,基本思想,例子,待查找序列必須是有序(例如從小到大),先確定

8、待查記錄所在范圍（區(qū)間）， 然后逐步縮小范圍直到找到或 找不到該記錄為止,設三個指針 low指向待查元素所在范圍的下界 high指向待查元素所在范圍的上界 mid為(low+high) / 2 給定的有序表（所有數(shù)值為關鍵字） (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ù)由用戶輸入？ 如何將給出算法改為一個函數(shù)，形參改為“待查找數(shù)組”和“數(shù)組元素個數(shù)”？,練習題,將給定數(shù)組中的元素顛倒順序排放,1 2 3 4 5 6 7 8 9 10,10 9 8 7 6 5 4 3 2 1,練習題,將給定數(shù)組中的元素顛倒順序排放,問題： 多占用一倍的存儲空間,1 2 3 4 5 6 7 8 9 10,五. 一維數(shù)組程序舉例,用冒泡法對10個數(shù)排序（從小到大）,排序過程： （1）比較第一個數(shù)與第二個數(shù)，若為逆序a0a1，則交換；然后比較第二個數(shù)與第三個數(shù)；依次類推，直至第n-1個數(shù)和第n個數(shù)比較為止第一趟冒泡排序，結

10、果最大的數(shù)被安置在最后一個元素位置上 （2）對前n-1個數(shù)進行第二趟冒泡排序，結果使次大的數(shù)被安置在第n-1個元素位置 （3）重復上述過程，共經(jīng)過n-1趟冒泡排序后，排序結束,例,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沒有使用 若使用a0，程序應該如何改動？ 冒泡排序一定要經(jīng)過n-1趟嗎？,五. 一維數(shù)組程序舉例,用簡單選擇法對10個數(shù)排序（從小到大）,排序過程： （1）首先通過n-1次比較，從n個數(shù)中找出最小的， 將它與第一個數(shù)交換第一趟選擇排序，結果最小的數(shù)被安置在第一個元素位置上 （2）再通過n-2次比較，從剩余的n-1個數(shù)中找出關鍵字次小的記錄，將它與第二個數(shù)交換第二趟選擇排序 （3）重復上述過程，共經(jīng)過n-1趟排序后，排序結束,例,初始： 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沒有使用 若使用a0，程序應該如何改動？ 如何使用隨機數(shù)初始化一維數(shù)組？,randomize random,六. 總結,什么時候使用 當處理的數(shù)據(jù)很多,又希望用循環(huán)來控制時 當運算的中間結果需要保存時 一維數(shù)組典型使用方法 排序 查找 線性表的插入、刪

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

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

15、始化,按元素排列順序初始化,三. 二維數(shù)組元素的初始化,按元素排列順序初始化,小結 在程序中為數(shù)組賦值的方法,用scanf語句由用戶輸入,for (i=0 ; i3 ; i+) for (j=0 ; j4 ; j+) scanf(“%d” , ,小結 在程序中為數(shù)組賦值的方法,由循環(huán)變量自動構成(前提：元素排列有規(guī)律) 由隨機數(shù)構成,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ù)組行列元素互換，存到另一個數(shù)組中,思考 1、例子中使用“按行”操作的方法

16、，如果使用 “按列”處理的方法，程序應該如何編寫？ 2、如果給定的是一個方陣，如何在一個數(shù)組上 完成轉置操作？,例 求二維數(shù)組中最大元素值及其行列號 1.設一個變量存放最大值max; 2 設兩個變量存放最大值在數(shù)組中的行列. 3.遍歷數(shù)組中的每一個元素 該題的實質：遍歷二維數(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ù)組的“鞍點”，即該位置上的元素在該行上最大，在該列上最小。 也可能沒有鞍點。(習題7.8) 分析：實質為遍歷數(shù)組,一級算法： SIZEOFROW 行數(shù) SIZEOFCOL 列數(shù) FOUND 找到鞍點標志，初值為0（即沒有鞍點） 輸入數(shù)組各元素； for(i=0;iSIZEOFROW；i+) 1、找出第i行最大值，并記錄所在“列”到col中； 2、找出col這一列中最小元素minofcol； 3、如果minofcol=aicol，打印鞍點，F(xiàn)OUND=1; if(!FOUND) 打印“沒有鞍點”；,二級算法1： 實質：對二維

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

19、icol) printf(“an dian is a%d%d= %d”, i,col,aicol); FOUND=1; ,程序： 請同學們自己實現(xiàn)該程序。,內容提要,7.1 一維數(shù)組的定義和引用 7.2 二維數(shù)組的定義和引用 7.3 字符數(shù)組 7.4 程序舉例,字符數(shù)組 定義,字符數(shù)組的初始化 逐個字符賦值 用字符串常量 字符數(shù)組的引用,例 char c10, ch34;,例 輸出一個字符串（實際上不是一個嚴格意義上的字符串）,#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); ,字符串 字符串及其結束標志 無字符串變量，用字符數(shù)組處理字符串 字符串結束標志：0,字符串的輸入輸出 逐個字符I/O： %c 整個字符串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、,結果：Hello#-=*,結果：Hello,用“%s”輸出時，遇0結束,void main() char a=h,e,l,0,l,o,0; printf(%s,a); ,例,輸出：hel,數(shù)組中有多個0時, 遇第一個結束,例 字符串輸入舉例,#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); ,運行情況： 輸入：How are you? 輸出：a=How b=are c=you? 輸入：How are you

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

23、gets(字符數(shù)組) 功能：從鍵盤輸入一以回車結束的字符串放入字符數(shù)組中，并自動加0 說明：輸入串長度應小于字符數(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的首地址 說明：字符數(shù)組1必須足夠大 連接前,兩串均以0結束;連接后,串1 的0取消,

24、新串最后加0,字符串拷貝函數(shù)strcpy 格式：strcpy(字符數(shù)組1,字符串2) 功能：將字符串2，拷貝到字符數(shù)組1中去 返值：返回字符數(shù)組1的首地址 說明：字符數(shù)組1必須足夠大 拷貝時0一同拷貝 不能使用賦值語句為一個字符數(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) 功能：比較兩個字符串 比較規(guī)則：對兩串從左向右逐個字符比較（ASCII碼），直到遇到不同字符或0為止 返值：返回int型整數(shù)， a. 若字符串1 字符串2， 返回正整數(shù) c. 若字符串1= 字符串2， 返回零 說明：字符串比較不能用“=”,必須用strcmp,字符串長度函數(shù)strlen 格式：strlen(字符數(shù)組) 功能：計算字符串長度 返值：返回字符串實際長度，不包括0在內,例 對于以下字符串，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,例 有三個字符串，找出其中最大者,#include #include void main() char string20,str32