信息學奧林匹克競賽C語言課程膠片5-定向原創(chuàng)V10

1、C語言Part 5 for NOI1. 高級函數(shù)2. 指針 在調用一個函數(shù)的過程中又出現(xiàn)直接或間接地調在調用一個函數(shù)的過程中又出現(xiàn)直接或間接地調用該函數(shù)本身，稱為函數(shù)的遞歸調用。語言的用該函數(shù)本身，稱為函數(shù)的遞歸調用。語言的特點之一就在于允許函數(shù)的遞歸調用。特點之一就在于允許函數(shù)的遞歸調用。函數(shù)的遞歸調用 要求使用遞歸和遞推兩種方法 遞推方法 遞歸方法例8.5 求n!) 1()!1() 1 , 0(1)(fnnnnn#include int main() long fac(int n); int n, y; printf(Please input an integer number:n); s

2、canf(%d, &n); y = fac(n); printf(%d!=%ldn, n, y); n = 0; if(n = 0, n = 1) /整個逗號表達式的值為最右邊表達式的值 printf(comma expression, true for n=1. n=%d, n); else printf(comma expression, false for n=1. n=%d, n); return 0;long fac(int n) long f; if(n 0) printf(n 0, data error!); else if(n = 0, n = 1) /最好寫為n =

3、0 | n = 1 f = 1; else f = fac(n - 1) * n; return (f);例8.5 遞歸代碼fac(5)fac(4)*5fac(3)*4fac(2)*3fac(1)*2n=5(未知)n=4(未知)n=3(未知)n=2(未知)1n=1(邊界)main(未知)已知已知已知已知已知#include int main() long fac(int n); int n, y; printf(Please input an integer number:n); scanf(%d, &n); y = fac(n); printf(%d!=%ldn, n, y); re

4、turn 0;long fac(int n) long f = 1; for(int i = 1; i = n; i+) f = f * i; return (f);例8.5 遞推方法 Hanoi（漢諾）塔問題。這是一個古典的數(shù)學問題，是一個用遞歸方法解題的典型例子。問題是這樣的：古代有一個梵塔，塔內有3個座A、B、C，開始時座上有個盤子，盤子大小不等，大的在下，小的在上。有一個老和尚想把這個盤子從座移到座，但每次只允許移動一個盤，且在移動過程中在3個座上都始終保持大盤在下，小盤在上。在移動過程中可以利用座，要求編程序打印出移動的步驟。例8.6漢諾塔問題例8.6為便于理解，我們先分析將座上個盤

5、子移到座上的過程：(1) 將座上個盤子移到座上（借助）；(2) 將座上個盤子移到座上；(3) 將座上個盤子移到座上（借助）。其中第()步可以直接實現(xiàn)。第步又可用遞歸方法分解為：1.1將上個盤子從移到；1.2將上個盤子從移到；1.3 將上個盤子從移到。第()步可以分解為：3.1將上個盤子從移到上；3.2將上個盤子從移到上；3.3將上個盤子從移到上。例8.6將以上綜合起來，可得到移動3個盤子的步驟為，。由上面的分析可知：將個盤子從座移到座可以分解為以下3個步驟：(1) 將上個盤借助座先移到座上。(2) 把座上剩下的一個盤移到座上。(3) 將個盤從座借助于座移到座上。#include int mai

6、n() void hanoi(int n, char one, char two, char three); /* 對hanoi函數(shù)的聲明 */ int m; printf(“Input the number of disks:); scanf(%d, &m); printf(The step to moving %d disks:n,m); hanoi(m, A, B, C); return 0;void hanoi(int n, char one, char two, char three) /* 定義hanoi函數(shù),將個盤從one座借助two座，移到three座 */ void

7、move(char x,char y); /* 對move函數(shù)的聲明 */ if(n=1) move(one,three); else hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); void move(char x, char y) /* 定義move函數(shù) */ printf(%c-%cn, x, y);例8.6 源代碼Input the number of disks:3The step to moving 3 disks:A-CA-BC-BA-CB-AB-CA-C 也是單向傳遞 也是值傳送方式 數(shù)組

8、元素只能作為函數(shù)實參，不能作為形參使用數(shù)組元素作為函數(shù)實參 有兩只運動隊a和b，各有10個隊員，每個隊員有一個綜合成績。將兩個隊的每個隊員的成績按順序一一對應地逐個比較（即a對第一個隊員和b隊第一個隊員比較，）。如果a隊隊員成績高于b隊隊員成績的數(shù)目多余b隊隊員成績高于a隊隊員成績的數(shù)目（例如：a隊贏6次，b隊贏4次），則認為a隊勝。統(tǒng)計出兩隊隊員比較的結果（a隊高于、等于和低于b隊的次數(shù)）例8.7統(tǒng)計兩支運動隊的成績#include int main() int higher(int, int); int a10, b10, i, n = 0, m = 0, k = 0; printf(En

9、ter the array a team:n); for(i = 0; i 10; i+) scanf(%d, &ai); printf(n); printf(Enter the array b team:n); for(i = 0; i 10; i+) scanf(%d, &bi); printf(n); for(i = 0; i k) printf(a team wins!n); else if(n y) flag = 1; else if(x y) flag = -1; else flag = 0; return (flag);例8.7例8.8 有10個學生成績，用一個函

10、數(shù)求全體學生的平均成績#include int main() float average(float); float scores10, avg; int i; printf(Input 10 scores:n); for(i = 0; i 10; i+) scanf(%f, &scoresi); avg = average(scores); printf(Average score is %5.2f:n, avg); return 0;float average(float array10) int i; float avg, sum = array0; for(i = 0; i 1

11、0; i+) sum += arrayi; avg = sum / 10; return (avg);用數(shù)組名作為函數(shù)參數(shù)Input 10 scores:89 98 77 38 67 66 56 89 99 100Average score is 86.80:調用函數(shù)時array并不新分配內存空間，實際傳送的是數(shù)組首地址。本質上也是單向傳送地址的值。#include int main() void sort(int, int); int array10, i; printf(Enter the array:n); for(i=0; i10; i+) scanf(%d, &arrayi)

12、; sort(array, 10); printf(The sorted array:n); for(i=0; i10; i+) printf(%d , arrayi); return 0;void sort(int array, int n) int i, j, k, t; for(i=0; in; i+) k = i; for(j=i+1; jn; j+) if(arrayj arrayk) k=j; /把當前最小元素的序號j保存在k中 t = arrayk; arrayk = arrayi; arrayi = t;/將最小元素和第i個元素對換 例8.9 用一個函數(shù)實現(xiàn)10個數(shù)的升序排序，

13、采用選擇排序方法所謂選擇法就是先將所謂選擇法就是先將10個數(shù)中最小的數(shù)與個數(shù)中最小的數(shù)與a0對換對換;再將再將a1到到a9中最小的數(shù)與中最小的數(shù)與a1對換對換每比較一輪每比較一輪,找出一個未經(jīng)排序的數(shù)中最找出一個未經(jīng)排序的數(shù)中最小的一個。共比較小的一個。共比較9輪。輪。Enter the array:5 7 -3 21 -43 67 321 33 51 0The sorted array:-43 -3 0 5 7 21 33 51 67 321#include int main() float highest_score(float 5); /第二個中括號中必須寫長度 float scores

14、45 = 61,73,85.5,87,90, 72,84,66,88,78, 75,87,93.5,81,96, 65,85,64,76,71; printf(The highest score is %6.2f.n, highest_score(scores); return 0;float highest_score(float scores5) int i, j; float max; max = scores00; for(i=0;i4;i+) for(j=0;jmax) max=scoresij; return (max);例8.10 利用多維數(shù)組模擬：四個學生五門課程，并設計一個函

15、數(shù)，求其中的最高成績。 內部變量或者局部變量 函數(shù)或者復合語句內定義的變量 形參也是局部變量 全局變量或者外部變量 函數(shù)之外定義的變量 從定義變量的位置開始到本源程序文件結束變量的作用域#include int StudentNo, CourseNo;int main() float highest_score(float 5); /第二個中括號中必須寫長度 float scores45 = 61,73,85.5,87,90, 72,84,66,88,78, 75,87,93.5,81,96, 65,85,64,76,71; printf(The highest score is %6.2f.

16、n, highest_score(scores); printf(Student no. is %d.n, StudentNo); printf(Course no. is %d.n, CourseNo); return 0;float highest_score(float scores5) int i, j; float max; max = scores00; for(i=0;i4;i+) for(j=0;jmax) max=scoresij; StudentNo = i; CourseNo = j; return (max);例8.11 在8.10基礎上輸出最高成績所述學生和課程只有在

17、逼不得已的情況下使用全局變量，因為：1.全稱占用內存，2.使函數(shù)具有弱通用性，3.降低可讀性 變量的存在時間 有的變量存在于程序的整個運行過程 有的變量存在于函數(shù)被調用期間 生存期和存儲方式是一個事物的兩面 存儲方式有兩種： 靜態(tài)存儲方式 動態(tài)存儲方式變量的生存期 靜態(tài)存儲方式 在程序運行期間由系統(tǒng)在靜態(tài)存儲區(qū)分配存儲空間，在程序運行期間不釋放 動態(tài)存儲方式 在函數(shù)調用期間根據(jù)需要在動態(tài)存儲區(qū)分配存儲空間 全局變量 采用靜態(tài)存儲方式 每個變量和函數(shù)都有兩個屬性 數(shù)據(jù)類型 數(shù)據(jù)的存儲類別auto，static，register，extern變量的存儲方式（變量的可見性） auto int b,

18、c=3; Auto關鍵詞，可以省略 函數(shù)中大多數(shù)變量屬于自動變量自動變量 靜態(tài)局部變量 在函數(shù)中聲明靜態(tài)變量，實現(xiàn)：在函數(shù)調用結束后變量的值還繼續(xù)保留原值靜態(tài)變量#include int main() int fac(int); int i, n; printf(Please input an integer number:n); scanf(%d, &n); for(i=1; i=n; i+) printf(%d!=%dn, i, fac(i); return 0;int fac(int n) static int f = 1; f=f*n; return (f);例8.12 階乘n

19、！，要求在函數(shù)中使用靜態(tài)局部變量F保留了上次調用結束時的值此句表示在上次的f值基礎上乘以nPlease input an integer number:51!=12!=23!=64!=245!=120 C語言允許把局部變量放在CPU的寄存器中 優(yōu)化程序執(zhí)行效率：如果變量執(zhí)行次數(shù)頻繁，那么應把局部變量改為寄存器變量 register int f; 現(xiàn)代編譯器能夠自動優(yōu)化，所以一般不手工使用register 寄存器變量 extern A; 在一個文件內擴展外部變量的作用域 將外部變量的作用域擴展到其他文件外部變量的可見性變量的存儲類變量的存儲類別別函數(shù)內作用域函數(shù)內作用域函數(shù)內存在性函數(shù)內存在性函

20、數(shù)外作用域函數(shù)外作用域函數(shù)外存在性函數(shù)外存在性自動變量寄存器變量靜態(tài)局部變量靜態(tài)全局變量（僅限本文件）外部變量作用域和生存期匯總 內部函數(shù)，又稱靜態(tài)函數(shù) 只能在本文件中被其他函數(shù)調用 格式：static 類型標識符 函數(shù)名(形參表); 外部函數(shù) 可被其他文件的函數(shù)調用 格式：extern 類型標識符 函數(shù)名(形參表); 定義函數(shù)時可省略extern 聲明函數(shù)時使用extern表示所調用的函數(shù)在其他文件中內部函數(shù)和外部函數(shù)例8.13 有一個字符串，內含若干字符，現(xiàn)輸入一個字符，如果字符串中含有此字符，則把此字符從字符串中刪除。要求使用外部函數(shù)實現(xiàn)。This is a c program.cThi

21、s is a program.#include int main() extern void enter_strng(char str); extern void delete_string(char str, char ch); extern void print_string(char str); char c; char str80; enter_string(str); scanf(%c, &c); delete_string(str, c); print_string(str); return 0;Main.c#include void enter_string(char s

22、tr) gets(str);enter.c#include void delete_string(char str, char ch) int i, j; for(i=j=0; stri!=0; i+) if(stri!=ch) strj+=stri; strj = 0;#include void print_string(char str) printf(%sn, str);print.cdelete.c 有的編譯器從左到右順序求實參的值 有的編譯器從右到左順序求實參的值 例8.14 求證所用編譯器實參求值順序 int i = 0, j = 0; printf(%d,%dn, j=i, +i

23、); if(j = 0) printf(實參求值順序：從左到右n); else printf(實參求值順序：從右到左n);實參求值的順序1. 高級函數(shù)2. 指針 指針是指向變量的內存單元的地址 編譯器給變量分配的內存單元的每個字節(jié)都有一個編號 直接訪問 直接按變量名對變量內存單元進行訪問 間接訪問 通過指針變量對變量內存單元進行訪問 指針變量是特殊變量，用于存放地址 指針變量的值是地址什么是指針 int a = 100, b = 10; int *ptr1, *ptr2; ptr1 = &a; ptr2 = &b; printf(a=%d, b=%dn, a, b); prin

24、tf(*ptr1=%d, *ptr2=%dn, *ptr1, *ptr2); printf(ptr1=0 x%X, ptr2=0 x%Xn, ptr1, ptr2); printf(ptr1=0%o, ptr2=0%on, ptr1, ptr2); printf(&ptr1=0 x%x, &ptr2=0 x%xn, &ptr1, &ptr2);例9.1通過指針變量訪問整型變量數(shù)字0作為前綴表示八進制數(shù)字0 x作為前綴表示十六進制a=100, b=10*ptr1=100, *ptr2=10ptr1=0 x22FF1C, ptr2=0 x22FF18ptr1=010

25、577434, ptr2=010577430&ptr1=0 x22ff14, &ptr2=0 x22ff100 x22FF1C100ptr1a(*ptr1)指針變量的值每次運行都不一樣變量內存單元十六進制，16位。如果是64位CPU，應該是多少位的地址int i, j, k, *i_pointer;基類型 *指針變量名 int *pointer_1, *pointer_2;基類型 基類型用來規(guī)定指針變量可以指向的變量的類型 基類型指數(shù)據(jù)類型，每個數(shù)據(jù)類型在內存占用的長度不同 方便進行指針操作：指針移動、指針加減運算指針運算符*，或者稱為“間接訪問”運算符, 表示指針變量取地址運

26、算符&不允許不同基類型的指針指向不同數(shù)據(jù)類型的變量 float a = 1.1; int *ptr1 = &a; /這句是錯誤的不允許指針變量被賦值為一個整數(shù) int *ptr1; ptr1 = 100; /這句是錯誤的指針變量的定義 給指針變量賦值 int a = 10, *ptr = &a; /合法 Int a = 10, *ptr; ptr = &a; /合法 int *ptr = 100;/非法 int *ptr; ptr = NULL; /合法，NULL在stdio.h中定義#define NULL 0 int *ptr;/合法，但沒有賦初值的指針有無

27、法預料的值 引用指針變量指向的變量 int *ptr; *ptr = 100; /合法 printf(“%d”, *p); /合法 引用指針變量的值 printf(“0%o”, ptr); /合法指針變量的引用 int *ptr1, *ptr2, *ptr, a, b; scanf(%d,%d, &a, &b); ptr1 = &a; ptr2 = &b; if (a b) ptr = ptr1; ptr1 = ptr2; ptr2 = ptr; /使兩個指針互換 printf(a=%d, b=%dn, a, b); printf(max=%d, min=%dn

28、, *ptr1, *ptr2);例9.2 輸入兩個整數(shù)，按先大后小的順序輸出。方法1：直接互換指針#include int main() void swap(int*, int*); int *ptr1, *ptr2, a, b; scanf(%d,%d, &a, &b); ptr1 = &a; ptr2 = &b; if (a b) swap(ptr1, ptr2); /調用函數(shù)swap printf(a=%d, b=%dn, a, b); printf(max=%d, min=%dn, *ptr1, *ptr2); return 0;void swap(in

29、t *p1, int *p2) int temp; temp = *p1; /交換值，而不是交換指針 *p1 = *p2; *p2 = temp;例9.2 方法2：指針變量作為函數(shù)參數(shù)調用結束后形參p1和p2是否還存在？此處換為int *temp; *temp = *p1; *p1=*p2; *p2 = *temp;是錯誤的，為什么？swap換為如下代碼是錯誤的，為什么？void swap(int x, int y) int temp; temp = x; x = y; y = temp;swap換為如下代碼是錯誤的，為什么？void swap(int *p1, int *p2) int *p

30、; p = p1; p1 = p2; p2 = p; 數(shù)組元素的指針就是數(shù)組元素的地址 可用一個指針變量指向一個數(shù)組元素 引用數(shù)組元素除了下標法之外，還可使用指針法 int a10; printf(“%d”, a2); int a10; printf(“%d”, *(a + 2); 數(shù)組名代表數(shù)組的首元素的地址，以下語句等價： int a10, *p; p = &a0; Int a10, *p; p = a;數(shù)組元素的指針#include int main() void print1(int); void print2(int); void print3(int*); void pri

31、nt4(int); int i, a10, *p = a; for(i=0; i10; i+) scanf(%d, &ai); print1(a); print2(p); print3(a); print4(p); return 0;void print1(int array10) for(int i=0; i10; i+) printf(%d , arrayi); /下標法 printf(n);void print2(int array10) for(int i=0; i10; i+) printf(%d , *(array + i);/對數(shù)組名采用指針法 printf(n);voi

32、d print3(int *p) for(int i=0; i10; i+) printf(%d , *(p + i);/指針法 printf(n);void print4(int array10) for(int *p = array; p (array + 10); p+)/對指針變量做加操作 printf(%d , *p);/指針法 printf(n);例9.3 有一個數(shù)組存放10學生的年齡，使用下標法和指針法輸出數(shù)組的所有元素。指針的加運算：不是直接在值上加i，而是加（i*數(shù)據(jù)類型的存儲長度） ，和數(shù)組元素下標吻合此句改為如下是錯誤的，為什么？for(int *p = array; a

33、rray (p + 10); array+)思考：指針的減運算和加運算有什么不同？兩個指針是否可以相減？兩個指針是否可以比較實參和形參都可以從數(shù)組名、指針變量選其一#include int main() int a10, *p = a; for(int i=0; i10; i+) scanf(%d, p+); for(int i=0; i10; i+, p+) printf(%d , *p); printf(n); return 0;例9.3 錯在哪里？for(int i=0, p=a; i10; i+, p+)void sort(int array, int n) int i, j, k,

34、t; for(i=0; in; i+) k = i; for(j=i+1; jn; j+) if(arrayj arrayk) k=j; /把當前最小元素的序號j保存在k中 t = arrayk; arrayk = arrayi; arrayi = t;/將最小元素和第i個元素對換 例9.4 改造選擇法排序函數(shù)。要求參數(shù)改為指針，數(shù)組元素訪問方法采用指針法#include int main() char *string = I love China!; printf(%sn, string); return 0;例9.5通過字符指針引用字符串不能稱為字符串變量此句能否拆分為以下兩句？char

35、*string;*string = “I love China!”;#include #include int main() char a100; printf(Please input a string:n); gets(a); char b100; strcpy(b, a); printf(%sn, b); return 0;例9.6 要求輸入一個字符串，復制后原樣輸出。方法1：引用庫函數(shù)#include int main() char a100; puts(Please input a string:); gets(a); char b100; int i = 0; for (; *(a

36、+i)!=0; i+) *(b+i) = *(a+i); *(b+i)=0; puts(b); return 0;例9.6 要求輸入一個字符串，復制后原樣輸出。方法2：使用數(shù)組名地址法重寫復制語句#include int main() char a100; puts(Please input a string:); gets(a); char b100; int i = 0; char *ptr1 = a, *ptr2 = b; for (; *(ptr1+i)!=0; i+) *(ptr2+i) = *(ptr1+i); *(ptr2+i)=0; puts(ptr2); return 0;例

37、9.6 要求輸入一個字符串，復制后原樣輸出。方法3：使用指針變量重寫復制語句字符數(shù)組b是否可以刪除？#include int main() void mystrcpy(char*, const char*); char a100; puts(Please input a string:); gets(a); char b100, *ptr = b; mystrcpy(ptr, a); puts(ptr); return 0;void mystrcpy(char *p_dest, const char *p_source) for (; *p_source!=0; p_source+, p_de

38、st+) *p_dest = *p_source; *p_dest=0;例9.6 要求輸入一個字符串，復制后原樣輸出。方法4：使用字符指針重寫復制函數(shù) while(*p_dest=*p_source)!=0) p_dest+; p_source+; while(*p_dest+=*p_source+)!=0); while(*p_source!=0) *p_dest+=*p_source+; *p_dest=0; while(*p_source) *p_dest+=*p_source+; *p_dest=0; while(*p_dest+=*p_source+); for(;*p_dest+=

39、*p_source+;);#include int main() char* mystrcat(char*, char*); char a100; puts(Please input first string:); gets(a); char b100; puts(Please input second string:); gets(b); mystrcat(a, b); puts(a); return 0;char *mystrcat(char *dest, char *src) int i; for(i=0; *dest!=0; i+) dest+; for(;*src!=0;dest+,

40、 src+) *dest = *src; *dest = 0; return dest;例9.7重寫庫函數(shù)strcat字符數(shù)組存放字符元素，而字符指針存放地址初始化char str14=“I love China”; /rightchar *ptr = “I love China”; /right賦值char str14; str=“I love China”; /errorchar str14; str=“I love China”; /errorchar *ptr; ptr = “I love China”; /right野指針沒有初始化的指針，或者指向不存在的內存單元，或者指向無法管理的內存單元字符指針的值可以改變，而字符數(shù)組名是常量地址，不能改變字符指針和字符數(shù)組均可以使用下標法引用char *ptr=“china”; printf(“%c”, ptr3);字符數(shù)組的元素值能被修改，但是字