c語(yǔ)言程序設(shè)計(jì)14第十三講(第六章中).ppt

1,C語(yǔ)言編程是一項(xiàng)技藝，需要多年的歷練才能達(dá)到較為完善的境界！ -摘自Expert C Programming,2,第六章 數(shù)組,3,復(fù)習(xí)（數(shù)值型數(shù)組）,如何定義數(shù)組？ 數(shù)組如何初始化？ 數(shù)組元素如何引用？ 循環(huán)語(yǔ)句 循環(huán)三要素循環(huán)不變關(guān)系 數(shù)組元素做函數(shù)參數(shù)傳遞的是什么？,4,作業(yè)提示,7.寫一個(gè)函數(shù)，它判斷一個(gè)整數(shù)（或浮點(diǎn)數(shù)）是否在一個(gè)數(shù)組中出現(xiàn)。如果出現(xiàn)，給出第一次出現(xiàn)的位置下標(biāo)；沒(méi)出現(xiàn)時(shí)給出-1。 15.1 請(qǐng)寫一個(gè)程序，它輸入一個(gè)學(xué)生成績(jī)文件，輸出按照每10分一個(gè)成績(jī)段的學(xué)生人數(shù)。,5,數(shù)組的概念、定義和使用 數(shù)組程序?qū)嵗?數(shù)組作為函數(shù)參數(shù) 字符數(shù)組和字符串 兩維和多維數(shù)組 編程實(shí)例,主要內(nèi)容,一維數(shù)值型數(shù)組的重要應(yīng)用,6,一維數(shù)組上的重要操作,排序 查找 插入 刪除 元素交換,7,將計(jì)算機(jī)學(xué)院08級(jí)學(xué)生按平均分高低排序 將08的奧運(yùn)會(huì)各參賽國(guó)按英文字典序排序 搜索引擎網(wǎng)頁(yè)排序(PageRank)learning to rank 排序問(wèn)題無(wú)處不在,例1 一維數(shù)組的應(yīng)用（排序）,8,常用的排序算法,冒泡排序 選擇排序 插入排序 快速排序 希爾排序 堆排序 ,9,冒泡排序法 輸入n個(gè)正整數(shù)存在數(shù)組中，按由小到大的順序排序 （最大的數(shù)下沉）,例,38,49,76,97,13,97,97,27,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,a0 a1 a2 a3 a4 a5 a6 a7,10,用冒泡法對(duì)10個(gè)數(shù)進(jìn)行排序（N-S圖及程序）,變量、數(shù)組長(zhǎng)度定義,for(j=0;j=N-i-1;j+),scanf ( “%d” , &ai ),for(i=0;iN;i+),for(i=0;iN;i+),ajaj+1,1,0,aj與aj+1交換,for(i=1;i=N-1;i+),printf ( “%6d”, ai ),/*冒泡法對(duì)10個(gè)數(shù)由小到大排序*/ #include #define N 10 void main() int aN , i , j , t; printf(“請(qǐng)輸入10個(gè)數(shù):n“); for ( i = 0 ; i aj+1) t = aj; aj = aj+1; aj+1 = t; printf(“n排序后的數(shù)據(jù)為:n“); for (i = 0; i N; i+) printf(“%6d“, ai); printf(“n“); ,11,問(wèn)題,輸入十個(gè)正整數(shù)，把這十個(gè)正整數(shù)按由大到小的順序排序，如何修改程序？課后作業(yè) n值如果是可變的? 如果只對(duì)部分?jǐn)?shù)據(jù)進(jìn)行排序？ 某趟循環(huán)未發(fā)生交換，后面可不再循環(huán)， 如何改進(jìn)冒泡排序?,12,void BubbleSort(int n, int a ) int flag, i, j; for (i = 1; i aj+1) t = ai; ai = ai+1; ai+1 = t; flag = 1; if ( !flag ) return; ,改進(jìn)的冒泡排序（函數(shù)）：設(shè)標(biāo)志flag，如果某趟未發(fā)生交換，flag=0，說(shuō)明排序完成，返回。,13,將數(shù)組a中的前5個(gè)數(shù)進(jìn)行排序,#include void BubbleSort(int n, int a ); int main() int a10 , i , j , t; printf(“請(qǐng)輸入10個(gè)數(shù):n“); for( i = 0 ; i 10 ; i+) scanf(“%d”, ,14,冒泡排序算法的復(fù)雜度分析,最壞情形下掃描數(shù)據(jù)總數(shù) n*(n+1)/2 最壞情形下數(shù)據(jù)交換的次數(shù) n*(n-1)/2,15,選擇法排序：把n個(gè)正整數(shù)按由小到大的順序排序。,例,初始： 49 38 65 97 76 13 27 ,i=1,13,49,一趟： 13 38 65 97 76 49 27 ,i=2,27,38,六趟： 13 27 38 49 65 76 97 ,16,用選擇法對(duì)10個(gè)數(shù)進(jìn)行排序（N-S圖及程序）,/*選擇法對(duì)10個(gè)數(shù)由小到大排序*/ #include #define N 10 void SelectSort(int n, int a); void main() int aN, i; for (i = 0; i N; i+) scanf(“%d“, ,變量、數(shù)組長(zhǎng)度定義,k=i for(j=i+1;jN;j+),scanf ( “%d” , &ai ),for(i=0;iN;i+),for(i=0;iN;i+),ajak,1,0,k=j,for(i=0;iN-1;i+),printf ( “%4d”, ai ),ai與ak交換,17,void SelectSort(int n, int a) int i, j, k, t; for (i = 0; i n-1; i+) k = i; for (j = i+1; j n; j+) if (aj ak) k = j; t = ak; ak = ai; ai = t; ,可否優(yōu)化？如何優(yōu)化？,18,選擇排序算法的復(fù)雜度分析,最壞情形下掃描數(shù)據(jù)總數(shù) n*(n+1)/2 最壞情形下數(shù)據(jù)交換的次數(shù) n1次,19,直接插入排序,排序方法（以排雜志為例）： 1. 任取一本雜志，作為排好序的一疊雜志的開始情況； 2. 從剩余雜志中任取一本，根據(jù)月份把它插入排好序的那疊雜志里的正確位置，使插入后的這疊雜志仍有序； 3.如果還有未排好的雜志，就回到2，否則就結(jié)束；,20,a,t=8,t=77,t=66,t=55,21,void insertsort(int n, int a) /* 遞增序直接插入排序 */ int i, j; int t; /*默認(rèn)a0為已排好序*/ for( i = 1; i = 0 ,排序函數(shù)的定義：,t=55,a0,ai,ai-1,將t插入到a0到ai之間,22,插入排序的復(fù)雜度分析,最壞情形下數(shù)據(jù)移動(dòng)的次數(shù) n*(n-1)/2,23,例2 一維數(shù)組的應(yīng)用（查找）,int search(int b, int key, int n) int j; for(j = 0; j n; j+) if (bj = key) return j; return (-1); ,線性查找： 從頭到尾逐個(gè)查找，也稱為順序查找。,效率底！ 最壞情形下的時(shí)間復(fù)雜度是O(n),#include #define N 10 int search(int b,int,int); void main() int aN, i, searchkey, element; for (i = 0; i N; i+) scanf(“%d “, ,24,先檢索中間的一個(gè)數(shù)據(jù)，如果不是所需的數(shù)據(jù)，則判斷這要找的數(shù)在那一邊，在所在的一邊中再看中間的數(shù)是否為所需的數(shù)，依次下去。 只適用于已排好序的數(shù)列。,折半查找,10 17 20 22 31 44 51 55 68 73 89 95 120 133 137 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,折半查找最壞情形下的復(fù)雜度是O(lgn),25,折半查找程序,#include #define N 100 void f(int , int, int); void main() int aN, j, n, x; scanf(“%d”, ,void f(int a ,int n , int x) int b = 0, t, find = 0, m; t = n - 1; do m = ( t + b) / 2; if (am = x) printf(“找到了%3d,是a%dn“,x,m); find = 1; else if (x am) t = m - 1; else b = m + 1; while( b = t ,26,例3 一維數(shù)組的應(yīng)用（插入/刪除） 將一個(gè)數(shù)插入一個(gè)有序的數(shù)列中，插入后數(shù)列仍然有序。an，有m個(gè)有序數(shù)(小-大），nm,算法：需插入x,3）插入x,1）找插入位置P,將ap到am依次后移一個(gè)位置,x=16,p,p = 0; while (x ap) /*小于或等于時(shí)插入*/,for (j = m-1; j = p; j-) aj+1 = aj;,ap = x;,如何用for改寫,if (x am-1) am = x; else for (i = 0; i = x) for (j = m-1; j= i; j-) aj+1 = aj; ai = x ; break; ,27,例4 一維數(shù)組的應(yīng)用（元素交換） 將a數(shù)組中從第m個(gè)元素起一直到最后的元素平移到數(shù)組的開頭，把a(bǔ)0到am-2中的元素向后順移。,a0,am-1,an-1,算法：1、輸入數(shù)組a ,m 2、for(j=1;jn-m+1 ;j+) 將an-1放臨時(shí)單元t； an-2a0依次后移一個(gè)位置； a0 =t; 3、輸出數(shù)組a,28,字符數(shù)組預(yù)備知識(shí),字符常量與字符串常量有什么區(qū)別？ 如何定義一個(gè)字符變量？,29,規(guī)定： 一個(gè)字符串書寫時(shí)不能跨行 多個(gè)字符串之間僅由空白分隔，系統(tǒng)會(huì)將它們連成一個(gè)長(zhǎng)字 符串。雙引號(hào)需用轉(zhuǎn)義符：“He said: “Im ok!“。,字符串以字符數(shù)組形式保存，存儲(chǔ)形式是在所有字符后放0作為串結(jié)束標(biāo)志。例 “Beijing“,0不是串內(nèi)容，卻是字符串表示不可缺的部分。 標(biāo)準(zhǔn)庫(kù)的字符串處理函數(shù)都按這種表示設(shè)計(jì)，寫字符串處理程序時(shí)也應(yīng)該遵守這一規(guī)則。,30,6.4 字符數(shù)組與字符串,字符數(shù)組定義方式（與其他數(shù)組一樣）： char line1000; 字符數(shù)組使用方式(與其他數(shù)組一樣)： i=0; /* 注意越界控制 */ while(i1000 ,字符數(shù)組初始化方式一：逐個(gè)字符賦值 char city15=B,e,i,j,i,n,g; 未指定初值的元素自動(dòng)設(shè)0，編碼0的字符稱為0字符/空字符，用0表示，在C中有特殊用途（字符串結(jié)束標(biāo)志）。,31,若字符數(shù)組里存了一些字符后放0 ，就符合字符串形式，可當(dāng)作字符串使用（數(shù)組里存著字符串）： char a5 = g, o, o, d, b5 = i, s, a, c5 = o, k, 0, d5 = o, k, 0, x, x5 = i,s,n,o,t; 注意：字符數(shù)組的有效長(zhǎng)度指第一個(gè)0前的字符個(gè)數(shù)+1,32,初始化方式二：用字符串常量 char a120 = “Peking University“; 未標(biāo)元素個(gè)數(shù)時(shí)，數(shù)組大小確定為串長(zhǎng)加1。例： char a3 = “Peking University“; 數(shù)組a3有18個(gè)字符元素。,字符數(shù)組變量中保存字符串后，可作字符串用。 例，若多個(gè)輸出語(yǔ)句都用同樣輸出格式描述： char outform1 = ”point: (%f, %f)n“; . printf(outform1, x, y); . printf(outform1, s, t);,33,字符數(shù)組的賦值,將一個(gè)字符串賦值給一個(gè)字符數(shù)組,只能用在初始化的情況下,不能用在賦值語(yǔ)句中 例如: char str11; str = “I am happy”;是錯(cuò)誤的.,34,字符串的輸入輸出,逐個(gè)字符I/O： %c 數(shù)組名下標(biāo) 整個(gè)字符串I/O： %s 數(shù)組名,例 用%c main() char str5; int i; for (i = 0; i 5; i+) scanf(“%c”, ,例 用%s main() char str5; scanf(“%s”, str); printf(“%s”, str); ,輸入用字符數(shù)組名,不要加& 輸入串長(zhǎng)度數(shù)組維數(shù) 遇空格或回車結(jié)束 自動(dòng)加0,輸出用字符數(shù)組名, 遇0結(jié)束,35,int main() int i; char a5; scanf(“%s“, a); for (i = 0; i 5; i+) printf(“%c“, ai); return 0; ,運(yùn)行情況： （1）若輸入 hel , 正常 （2）若輸入 hell , 正常 （3）若輸入 hello , 用%s 輸出，會(huì)出現(xiàn)問(wèn)題？,輸入字符串長(zhǎng)度數(shù)組維數(shù),例子,36,#include 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? 輸出：a=How,scanf中%s輸入時(shí),遇空格或回車結(jié)束,運(yùn)行情況： 輸入：How are you?,字符串輸入舉例,37,void str_copy (char s, const char t) int i = 0; while (ti != 0) si = ti; +i; si = 0; ,循環(huán)結(jié)束時(shí)ti的空字符正好賦給si。 void str_copy (char s, const char t) int i = 0; while (si = ti) != 0) +i; ,字符串處理程序?qū)嵗?例1，寫函數(shù)將一字符串復(fù)制到一字符數(shù)組。假定數(shù)組足以存放被 復(fù)制串及空字符。,38,字符串處理函數(shù)的典型循環(huán)： for (i = 0; si != 0; +i) 用是否空字符確定對(duì)字符串的處理是否已完成。,例2，（二進(jìn)制轉(zhuǎn)換）寫函數(shù)，給它一個(gè)表示二進(jìn)制數(shù)的0/1字符串，它算出這個(gè)串表示的整數(shù)值。,二進(jìn)制數(shù)bnbn-1.b2b1b0的值可以用下面公式計(jì)算： (.(bn2) +bn-1)2 +.)2 + b2)2 + b1)2 + b0 據(jù)此可寫出循環(huán)，循環(huán)條件判斷二進(jìn)制數(shù)是否結(jié)束。 二進(jìn)制數(shù)位只能是0/1，只需要在遇到1時(shí)加1。,39,int bin2int(const char s) int i = 0, n = 0; while(si!=0 ,由于數(shù)字字符的編碼連續(xù)排列.函數(shù)改為： int bin2int(const char s) int i = 0, n = 0; while(si!=0 /* 這種寫法可以推廣到八進(jìn)制和其他進(jìn)制 */,40,例3 計(jì)算字符數(shù)組的有效長(zhǎng)度,#include int strLen(const char s); int main() int len; char str10; scanf(“%s“, str); len = strLen(str); printf(“%dn“, len); printf(“%sn“, str); return 0; ,int strLen(const char s) int i=0; while(si!=0) i+; return (i+1); ,有問(wèn)題嗎？,41,包含在頭文件 string.h,字符串輸出函數(shù)puts 格式：puts(字符數(shù)組) 功能：向顯示器輸出字符串（輸出完，換行） 說(shuō)明：字符數(shù)組必須以0結(jié)束,字符串輸入函數(shù)gets 格式：gets(字符數(shù)組) 功能：從鍵盤輸入一以回車結(jié)束的字符串放入字符數(shù)組中， 并自動(dòng)加0 說(shuō)明：輸入串長(zhǎng)度應(yīng)小于字符數(shù)組維數(shù),標(biāo)準(zhǔn)庫(kù)中常用的字符串處理函數(shù),42,例 #include main( ) char string80; printf(“Input a string:”); gets(string); puts(string); 輸入: How are you? 輸出: How are you ?,scanf(“%s”,str); gets(str); 區(qū)別是scanf取不到空格,gets()函數(shù)是個(gè)過(guò)時(shí)的函數(shù),43,標(biāo)準(zhǔn)庫(kù)中常用的字符串處理函數(shù),包含在頭文件 string.h 字符串（實(shí)際）長(zhǎng)度函數(shù) strlen(const char s);,#include #include int main() char str10 = “China“; int n; printf(“Length=%dn“, strlen(str); n = strlen(str); printf(“n=%dn“, n); return 0; ,44,標(biāo)準(zhǔn)庫(kù)中常用字符串處理函數(shù),復(fù)制函數(shù)： strcpy(char s,const char t); t應(yīng)為字符串，const說(shuō)明參數(shù)值不修改。字符數(shù)組s應(yīng)足夠大，以保證復(fù)制不越界。例： char a116, a216; strcpy(a1, “programming“); strcpy(a2, a1);,限界復(fù)制函數(shù)strncpy，限制復(fù)制長(zhǎng)度： strncpy(char s,const char t,int n); 將t中前n個(gè)字符復(fù)制到s中。,a1,45,#include #include int main() char a5 , b5 = “Power“, c1, c2; c1 = A; c2 = B; printf(“b=%sn“, b); a0 = C; a1 = h; a2 = i; a3 = n; a4 = a; printf(“a=%sn“, a); a = “Study“; printf(“a=%sn“, a); a = b; printf(“a=%sn“, a); return 0; ,程序查錯(cuò),46,#include #include int main() char a6 ,b6= “Power“,c1,c2; c1=A;c2=B; printf(“b=%sn“,b); a0=C;a1=h; a2=i; a3=n; a4=a;a5=0; printf(“a=%sn“,a); strcpy(a,“ Study “); printf(“a=%sn“,a); strcpy(a,b); printf(“a=%sn“,a); return 0; ,改正錯(cuò)誤后,47,int strcmp(const char s1, const char s2) 兩字符串相同時(shí)返回值0; s1大于s2的情況下返回大于0的值; 否則返回小于0的值。 判斷字符串大小的標(biāo)準(zhǔn)是字符串的字