C語言程序設計-第八章 優(yōu)化學生成績分析系統(tǒng)-指針

1、C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針項目八八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)- -指針指針C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針【項目要求項目要求】借助于指針對上一章的的學生成績分析系統(tǒng)進行優(yōu)化，對某班一門課的借助于指針對上一章的的學生成績分析系統(tǒng)進行優(yōu)化，對某班一門課的成績進行分析，要求有如下功能：成績進行分析，要求有如下功能：1.1.查詢全部成績；查詢全部成績；2.2.查詢平均分；查詢平均分；3.3.查詢不及格率；查詢不及格率；4.4.查詢最高分；查詢最高分；5.5.按成績降

2、序排列；按成績降序排列；0.0.退出。退出。 為了保存一個班的為了保存一個班的C語言成績需要借助于一維數(shù)組，通過指針對其數(shù)語言成績需要借助于一維數(shù)組，通過指針對其數(shù)據進行操作。將本項目分成兩部分，首先借助于指針對一維數(shù)組進行據進行操作。將本項目分成兩部分，首先借助于指針對一維數(shù)組進行訪問，然后介紹一種新的排序算法訪問，然后介紹一種新的排序算法選擇排序。選擇排序?！卷椖糠治鲰椖糠治觥緾語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針問題情境及實現(xiàn)問題情境及實現(xiàn)v 通過前面所學知道，可以通過下標法訪問數(shù)組元素，數(shù)組名代表數(shù)組通過前面所學知道，可以通過下標法訪

3、問數(shù)組元素，數(shù)組名代表數(shù)組的首地址，即指針，我們亦可通過其對數(shù)組元素進行訪問。的首地址，即指針，我們亦可通過其對數(shù)組元素進行訪問。v #define N 100#define N 100v #include #include v void main()void main()v v int sN,n,int sN,n,* *p;p;v printf(printf(請輸入該班人數(shù)請輸入該班人數(shù)););v scanf(%d,&n);scanf(%d,&n);v printf(printf(請錄入成績請錄入成績););v for(p=s;ps+n;p+)for(p=s;ps+n;p+)

4、v scanf(%d,p); scanf(%d,p);v printf(printf(該班的全部成績是該班的全部成績是:n);:n);v for(p=s;ps+n;p+)for(p=s;ps+n;p+)v printf(%6d, printf(%6d,* *p);p);v C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針4 4 4 4本講主要內容本講主要內容2. 指針與函數(shù)指針與函數(shù)1. 指針與字符串指針與字符串3. 指針數(shù)組指針數(shù)組4. 指針應用舉例指針應用舉例C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針

5、1 1 指針與字符串指針與字符串(1)(1)1.1 1.1 字符串的表示形式字符串的表示形式v用用字符數(shù)組字符數(shù)組存放一個字符串，并輸出該字符串。存放一個字符串，并輸出該字符串。 main()char string =I love China!;printf(%sn,string);C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針1 1 指針與字符串指針與字符串(2)(2)1.1 1.1 字符串的表示形式字符串的表示形式( (續(xù)續(xù)) )v用用字符串指針字符串指針指向一個字符串指向一個字符串 main()char *string=I love China

6、!;printf(%sn,string);C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針1 1 指針與字符串指針與字符串(3)(3)1.1 1.1 字符串的表示形式字符串的表示形式( (續(xù)續(xù)) )例例1 1 寫出下面程序的運行結果寫出下面程序的運行結果 #include void main() char *ptr1,*ptr2; ptr1=ptr2=abcde; while(*ptr2!=0) putchar(*ptr2+); putchar(n); while(-ptr2=ptr1) putchar(*ptr2); putchar(n);運行結果：

7、運行結果：abcdeedcbaC語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針1 1 指針與字符串指針與字符串(4)(4)1.2 1.2 使用字符串指針變量與字符數(shù)組的區(qū)別使用字符串指針變量與字符數(shù)組的區(qū)別字符數(shù)組由若干元素組成字符數(shù)組由若干元素組成，每個元素中放一，每個元素中放一個字符，個字符，而字符指針變量中存放的是地址而字符指針變量中存放的是地址（字（字符串的首地址）。符串的首地址）。賦值方式不同。賦值方式不同。對對字符數(shù)組字符數(shù)組只能對各個元素只能對各個元素賦值，賦值，不能用一個字符串給一個字符數(shù)組賦值不能用一個字符串給一個字符數(shù)組賦值，但對于

8、但對于字符指針變量可以用一個字符串給它賦字符指針變量可以用一個字符串給它賦值值。char str14;str=“ I love China”;char *pstr;pstr=“ I love China”;C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針1 1 指針與字符串指針與字符串(5)(5)1.2 1.2 使用字符串指針變量與字符數(shù)組的區(qū)別使用字符串指針變量與字符數(shù)組的區(qū)別( (續(xù)續(xù)) )例例2 2 分析下面程序的運行結果分析下面程序的運行結果 main() char *a=I Love China!; a=a+7; printf(“%sn,a)

9、;運行結果：運行結果：China!C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針1 1 指針與字符串指針與字符串(6)(6)1.2 1.2 使用字符串指針變量與字符數(shù)組的區(qū)別使用字符串指針變量與字符數(shù)組的區(qū)別( (續(xù)續(xù)) )例例3 3 分析下面程序的運行結果分析下面程序的運行結果 main()char *a=I Love China!; int i; printf(the sixth character is %cn,a5); for(i=0;ai!=0;i+) printf(%c,ai);運行結果：運行結果：the sixth character

10、is eI Love China!C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(1)(1)2.1 2.1 指針變量作為函數(shù)參數(shù)指針變量作為函數(shù)參數(shù)指針變量作為函數(shù)參數(shù)指針變量作為函數(shù)參數(shù)，實參變量實參變量和和形參變量形參變量的的傳遞方式為傳遞方式為地址傳遞地址傳遞void swap1(int x,int y)int z;z=x;x=y;y=z;void swap2(int *x,int *y)int z;z=*x;*x=*y;*y=z;值傳遞值傳遞地址傳遞地址傳遞C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系

11、統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(2)(2)2.1 2.1 指針變量作為函數(shù)參數(shù)指針變量作為函數(shù)參數(shù)( (續(xù)續(xù)) )例例4 4 程序填空，然后分析運行結果。程序填空，然后分析運行結果。( (輸入輸入5 5，6)6)#include main() int a,b; void swap1(int x,int y); void swap2(int *x,int *y); scanf(%d,%d,&a,&b); printf(a=%dtb=%dn,a,b); swap1( ); printf(a=%dtb=%dn,a,b); swap2( ); printf

12、(a=%dtb=%dn,a,b);運行結果：運行結果：a=5 b=6a=5 b=6a=6 b=5C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(3)(3)2.1 2.1 指針變量作為函數(shù)參數(shù)指針變量作為函數(shù)參數(shù)( (續(xù)續(xù)) )例例5 5 一個自然數(shù)是素數(shù)，且它的數(shù)字位置經過任一個自然數(shù)是素數(shù)，且它的數(shù)字位置經過任意對換后仍為素數(shù)，則稱為意對換后仍為素數(shù)，則稱為絕對素數(shù)絕對素數(shù)，例如，例如1313，試求所有兩位絕對素數(shù)。試求所有兩位絕對素數(shù)。解題思路解題思路使用哪種類型的程序結構？使用哪種類型的程序結構？給出一個數(shù)，如何求任

13、意數(shù)字給出一個數(shù)，如何求任意數(shù)字位置對換后的數(shù)？位置對換后的數(shù)？如何判斷一個數(shù)為素數(shù)？如何判斷一個數(shù)為素數(shù)？C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(4)(4)2.2 2.2 指向函數(shù)的指針變量指向函數(shù)的指針變量 在語言中，在語言中，一個函數(shù)占用一段連續(xù)的內存一個函數(shù)占用一段連續(xù)的內存區(qū)區(qū)，而，而函數(shù)名就是該函數(shù)所占內存區(qū)的首地址函數(shù)名就是該函數(shù)所占內存區(qū)的首地址。我們可以把函數(shù)的這個首地址我們可以把函數(shù)的這個首地址(或稱入口地址或稱入口地址)賦賦予一個指針變量，使該指針變量指向該函數(shù)。然予一個指針變量，使該指針變量

14、指向該函數(shù)。然后通過指針變量就可以找到并調用這個函數(shù)。我后通過指針變量就可以找到并調用這個函數(shù)。我們把這種們把這種指向函數(shù)的指針變量指向函數(shù)的指針變量稱為稱為“函數(shù)指針變函數(shù)指針變量量”。C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(5)(5)2.2 2.2 指向函數(shù)的指針變量指向函數(shù)的指針變量( (續(xù)續(xù)) )函數(shù)指針變量函數(shù)指針變量定義定義的一般形式為：的一般形式為：類型說明符類型說明符 ( (* *指針變量名指針變量名)();)();表示被指函表示被指函數(shù)的返回值數(shù)的返回值的類型的類型“* *”后面的變后面的變量是定

15、義的指量是定義的指針變量針變量指針變量所指指針變量所指的是一個函數(shù)的是一個函數(shù)如：如：int (*pf)();C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(6)(6)2.2 2.2 指向函數(shù)的指針變量指向函數(shù)的指針變量( (續(xù)續(xù)) )用函數(shù)指針變量用函數(shù)指針變量調用函數(shù)調用函數(shù)的一般形式為：的一般形式為：( (* *指針變量名指針變量名)()(實參表實參表) )C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(7)(7)2.2 2.2 指向函數(shù)的指針變

16、量指向函數(shù)的指針變量( (續(xù)續(xù)) )例例6 6 將給出的程序修改為使用函數(shù)指針變量定義將給出的程序修改為使用函數(shù)指針變量定義的方式的方式 main() int max(int,int); int a,b,c; scanf(%d,%d,&a,&b); c=max(a,b); printf(a=%d,b=%d,max=%d,a,b,c);max(int x,int y) int z; if(xy) z=x; else z=y; return(z);int (*p)();p=max;c=(*p)(a,b);C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系

17、統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(8)(8)2.2 2.2 指向函數(shù)的指針變量指向函數(shù)的指針變量函數(shù)指針作為函數(shù)參數(shù)函數(shù)指針作為函數(shù)參數(shù)例例7 7 分析下面程序的執(zhí)行過程分析下面程序的執(zhí)行過程#include main() int add(int a,int b); int sub(int a,int b); fun(int (*)p(),int a,int b); int (*ps)(),x,y,z; scanf(%d,%d,&x,&y); if(xy) z=fun(add,x,y); else ps=sub;z=fun(ps,x,y); printf(x=%d,y=

18、%d,z=%dn,x,y,z);add(int a,int b) return (a+b);sub(int a,int b) return (a-b);fun(int (*pf)(),int a,int b) return (*pf)(a,b);C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(9)(9)2.2 2.2 指向函數(shù)的指針變量指向函數(shù)的指針變量返回值為指針的函數(shù)返回值為指針的函數(shù)定義定義返回值為指針變量類型的函數(shù)返回值為指針變量類型的函數(shù)的一般形式為：的一般形式為：類型符類型符 * *函數(shù)名函數(shù)名( (參數(shù)表參數(shù)

19、表) )C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(10)(10)2.2 2.2 指向函數(shù)的指針變量指向函數(shù)的指針變量返回值為指針的函數(shù)返回值為指針的函數(shù)例例8 8 分析給出程序的運行結果分析給出程序的運行結果#include int *f(int *x,int *y)if (*x*y)return x;elsereturn y;void main()int a=17,b=18,*p,*q,*r;p=&a;q=&b;r=f(p,q);printf(%d,%d,%dn,*p,*q,*r);運行結果：運行結

20、果：17，18，17C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針3 3 指針數(shù)組指針數(shù)組 (1)(1)3.1 3.1 指針數(shù)組指針數(shù)組指針數(shù)組的定義形式為：指針數(shù)組的定義形式為：類型符類型符 * *指針數(shù)組名指針數(shù)組名 常量表達式常量表達式;課堂練習，分析下面語句的含義：課堂練習，分析下面語句的含義：int *p4;Int (*p)4;指針數(shù)組，有指針數(shù)組，有4個元素，個元素，每個元素每個元素都是指向整型變量指針變量都是指向整型變量指針變量由由4個整型變量組成的數(shù)組的指針個整型變量組成的數(shù)組的指針C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績

21、分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針3 3 指針數(shù)組指針數(shù)組 (2)(2)3.1 3.1 指針數(shù)組指針數(shù)組( (續(xù)續(xù)) )#include main() static int a34=11,22,33,44,55,66,77,88,99,110,122,133; int *p3=a0,a1,a2; int i,j; for(i=0;i3;i+) for(j=0;j4;j+) printf(a%d%d=%dt,i,j,pij); printf(n); 133133122122110110999988887777666655554444333322221111p0p1p2C語言程序設計語言程序設

22、計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針3 3 指針數(shù)組指針數(shù)組 (3)(3)3.1 3.1 指針數(shù)組指針數(shù)組( (續(xù)續(xù)) )#include main() static int a34=11,22,33,44,55,66,77,88,99,110,122,133; int *p3=a0,a1,a2; int (*q)4; int i,j; q=a; for(i=0;i3;i+) for(j=0;j4;j+)printf(a%d%d=%dt,i,j,(*(q+i)j); printf(n); 13313312212211011099998888777766665555

23、4444333322221111qq+1q+2(*q)0(*q)1(*q)2(*q)3C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針3 3 指針數(shù)組指針數(shù)組(4)(4)C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針4 4 指針應用舉例指針應用舉例(1)(1)例例9 編寫程序，編寫程序，利用系統(tǒng)提供的圖形庫函數(shù)在屏利用系統(tǒng)提供的圖形庫函數(shù)在屏幕上畫一個圖形幕上畫一個圖形，方法是將一個半徑為，方法是將一個半徑為r1的圓周的圓周等分等分n份，再以每個等分點為圓心，以半徑份，再以每個等分點為圓心，以半徑rs畫畫n個

24、圓，要求在命令方式下給出個圓，要求在命令方式下給出r1,rs的值及環(huán)的顏的值及環(huán)的顏色值。色值。C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針4 4 指針應用舉例指針應用舉例(2)(2)例例10 編寫程序，采用冒泡法對一組整數(shù)進行升序編寫程序，采用冒泡法對一組整數(shù)進行升序或降序排序，然后輸出排序結果。要求：由計算或降序排序，然后輸出排序結果。要求：由計算機生成機生成10100以內的以內的隨機整數(shù)隨機整數(shù)50個個，放入數(shù)組。，放入數(shù)組。通過通過函數(shù)指針，完成對數(shù)組的升序或者降序的排函數(shù)指針，完成對數(shù)組的升序或者降序的排序。序。C語言程序設計語言程序設計

25、項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針27272727本講小結本講小結v掌握字符指針的使用掌握字符指針的使用v掌握指針作為函數(shù)參數(shù)的使用掌握指針作為函數(shù)參數(shù)的使用v了解指向函數(shù)的指針變量的使用了解指向函數(shù)的指針變量的使用v了解指針數(shù)據的使用了解指針數(shù)據的使用C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針【項目要求項目要求】借助于指針對上一章的的學生成績分析系統(tǒng)進行優(yōu)化，對某班一門課的借助于指針對上一章的的學生成績分析系統(tǒng)進行優(yōu)化，對某班一門課的成績進行分析，要求有如下功能：成績進行分析，要求有如下功能：1.1.查詢全部成績；

26、查詢全部成績；2.2.查詢平均分；查詢平均分；3.3.查詢不及格率；查詢不及格率；4.4.查詢最高分；查詢最高分；5.5.按成績降序排列；按成績降序排列；0.0.退出。退出。 為了保存一個班的為了保存一個班的C語言成績需要借助于一維數(shù)組，通過指針對其數(shù)語言成績需要借助于一維數(shù)組，通過指針對其數(shù)據進行操作。將本項目分成兩部分，首先借助于指針對一維數(shù)組進行據進行操作。將本項目分成兩部分，首先借助于指針對一維數(shù)組進行訪問，然后介紹一種新的排序算法訪問，然后介紹一種新的排序算法選擇排序。選擇排序。【項目分析項目分析】C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針

27、指針問題情境及實現(xiàn)問題情境及實現(xiàn)v 通過前面所講可實現(xiàn)本系統(tǒng)的前通過前面所講可實現(xiàn)本系統(tǒng)的前4 4個功能，下面借助于指針實現(xiàn)數(shù)據個功能，下面借助于指針實現(xiàn)數(shù)據的排序。采用簡單選擇排序方法進行，程序如下：的排序。采用簡單選擇排序方法進行，程序如下：v #define N 100#define N 100v #include #include v #include #include v void fselectsort(int void fselectsort(int * *a,int n)a,int n)v v int int * *p,p,* *q,q,* *pmax,t;pmax,t;v f

28、or(p=a;pa+n-1;p+)for(p=a;pa+n-1;p+)v pmax=p; pmax=p;v for(q=p+1;qa+n;q+) for(q=p+1;qa+n;q+)v if( if(* *pmaxpmax* *q) pmax=q;q) pmax=q;v if(p!=pmax) t= if(p!=pmax) t=* *p;p;* *p=p=* *pmax;pmax;* *pmax=t;pmax=t;v v C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針相關知識：簡單選擇排序相關知識：簡單選擇排序v 簡單選擇排序的基本方法是：第一趟，從

29、簡單選擇排序的基本方法是：第一趟，從n n個記錄中找出關鍵字最小的記錄與第一個記個記錄中找出關鍵字最小的記錄與第一個記錄交換；第二趟，從第二個記錄開始的錄交換；第二趟，從第二個記錄開始的n-1n-1個記錄中再選出關鍵字最小的記錄與第二個個記錄中再選出關鍵字最小的記錄與第二個記錄交換；如此，第記錄交換；如此，第i i趟，則從第趟，則從第i i個記錄開個記錄開始的始的vn-i+1n-i+1個記錄中選出關鍵字最小的記錄與第個記錄中選出關鍵字最小的記錄與第i i個記錄交換，直到整個序列按關鍵字有序排個記錄交換，直到整個序列按關鍵字有序排列。列。C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系

30、統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針 簡單選擇排序算法簡單選擇排序算法: :v void selectsort(datatype r,int n)void selectsort(datatype r,int n)v int i,j,t; int i,j,t;v for(i=1;i=n;i+) for(i=1;i=n;i+) v t=i; t=i;v for(j=i+1; j=n;j+) for(j=i+1; jrj) t=j; if(rtrj) t=j; v if(i!=t) r0=rt; if(i!=t) r0=rt; v rt=ri; rt=ri;v ri=r0; ri=r0;v v v C語

31、言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針 對如下關鍵字對如下關鍵字(49,38,65,97,76,13,27,49)(49,38,65,97,76,13,27,49)進行簡單選擇排序的過程見下圖進行簡單選擇排序的過程見下圖。 r012345678初始關鍵字4938659776132749 13 38 65 97 76 49 27 49v第一趟結果第一趟結果：v第二趟結第二趟結果：果： 13 27 65 97 76 49 38 49v第三趟結果第三趟結果： 13 27 38 97 76 49 65 49v第四趟結果第四趟結果： 13 27 38 49

32、 76 97 65 49v第五趟結果第五趟結果： 13 27 38 49 49 97 65 76v第六趟結果第六趟結果： 13 27 38 49 49 65 97 76v第七趟結果第七趟結果： 13 27 38 49 49 65 76 97 簡單選擇排序移動記錄的次數(shù)較少，但關鍵字的比較次數(shù)依然是n(n+1)/2，所以時間復雜度仍為O(n2)。 C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針樹形選擇排序樹形選擇排序v按照錦標賽的思想進行，將按照錦標賽的思想進行，將n n個參賽的選手看成完個參賽的選手看成完全二叉樹的葉結點，則該完全二叉樹有全二叉樹的葉

33、結點，則該完全二叉樹有2n-22n-2或或2n-2n-1 1個結點。首先，兩兩進行比賽個結點。首先，兩兩進行比賽( (在樹中是兄弟的在樹中是兄弟的進行，否則輪空，直接進入下一輪進行，否則輪空，直接進入下一輪) )，勝出的再兄，勝出的再兄弟間再兩兩進行比較，直到產生第弟間再兩兩進行比較，直到產生第1 1名。名。v接下來，將作為第接下來，將作為第1 1名的結點看成最差的，并從該名的結點看成最差的，并從該結點開始，沿該結點到根路徑上，依次進行各分結點開始，沿該結點到根路徑上，依次進行各分枝結點子女間的比較，勝出的就是第枝結點子女間的比較，勝出的就是第2 2名。因為和名。因為和他比賽的均是剛剛輸給第他

34、比賽的均是剛剛輸給第1 1名的選手。名的選手。v如此，繼續(xù)進行下去，直到所有選手的名次排定。如此，繼續(xù)進行下去，直到所有選手的名次排定。C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針 對如下關鍵字對如下關鍵字(49,38,65,97,76,13,27,49)(49,38,65,97,76,13,27,49)進行簡單選擇排序的過程見下圖。進行簡單選擇排序的過程見下圖。 r012345678初始關鍵字4938659776132749492776133849976549977649977697 存放排序012345678結果的數(shù)組97再將再將97設為最差設

35、為最差(最小最小)。 C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針 r012345678初始關鍵字49386507613274949277613384906549657649657676 存放排序012345678結果的數(shù)組7697再將再將76設為最差設為最差(最小最小)。 C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針 r012345678初始關鍵字493865001327494927013384906549651349654965 存放排序012345678結果的數(shù)組657697再將再將65設為最差設

36、為最差(最小最小)。 C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針 r012345678初始關鍵字493800013274949270133849004901349494949 存放排序012345678結果的數(shù)組49657697v注意：若取注意：若取4949則為穩(wěn)定的排序。則為穩(wěn)定的排序。再將再將49設為最差設為最差(最小最小)。 C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針 r012345678初始關鍵字0380001327490270133849003801349384949 存放排序012345

37、678結果的數(shù)組4949657697再將再將49設為最差設為最差(最小最小)。 C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針 r012345678初始關鍵字03800013270027013380003801327382738 存放排序012345678結果的數(shù)組384949657697再將再將38設為最差設為最差(最小最小)。 C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針 r012345678初始關鍵字0000013270027013000000132702727 存放排序012345678結果的數(shù)組

38、27384949657697再將再將27設為最差設為最差(最小最小)。 C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針 r012345678初始關鍵字0000013000001300000013001313 最后排序012345678 的結果1327384949657697C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針堆排序堆排序v堆排序是樹形選擇排序方法的改進，它使用的輔堆排序是樹形選擇排序方法的改進，它使用的輔助空間較少，僅增加一個記錄空間進行交換，同助空間較少，僅增加一個記錄空間進行交換，同時關鍵字比

39、較的次數(shù)和樹形選擇排序相當。時關鍵字比較的次數(shù)和樹形選擇排序相當。v1. 1. 堆的定義和存儲結構堆的定義和存儲結構 v堆是一棵完全二叉樹，組成這棵完全二叉樹的堆是一棵完全二叉樹，組成這棵完全二叉樹的n n個個元素序列元素序列 k k1 1，k k2 2，k kn n，當且僅當滿足下述關，當且僅當滿足下述關系之一時，稱之為堆。系之一時，稱之為堆。 vKik2ivKik2i+1v 大大頭頭堆堆v 或或者者vKik2ivKik2i+1v 小小頭頭堆堆v 其中其中i=1,2, i=1,2, ,n/2,n/2C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針v如

40、以下關鍵字如以下關鍵字(49,38,65,97,76,13,27,(49,38,65,97,76,13,27,4949) )所建立所建立的大頭堆和小頭堆如下圖所示：的大頭堆和小頭堆如下圖所示：v用一維數(shù)組存儲一個堆，則堆對應的存儲結構如下：用一維數(shù)組存儲一個堆，則堆對應的存儲結構如下：9776654949132738v 大頭大頭堆堆1338274976654997v 小頭小頭堆堆 012345678大頭堆9776654949132738012345678小頭堆1338274976654997C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針v建立初始堆建

41、立初始堆 v對初始序列建堆的過程，就是一個反復進行篩選的對初始序列建堆的過程，就是一個反復進行篩選的過程。對過程。對n n個結點的完全二叉樹只需從第個結點的完全二叉樹只需從第 n/2 n/2 個元個元素開始。例如素開始。例如: :對元素對元素(49,38,65,97,76,13,27,(49,38,65,97,76,13,27,4949) )進行篩選的過程見下圖進行篩選的過程見下圖( (建小頭堆建小頭堆) )。4938659776132749v i=4v 將97與49交換4938654976132797v i=3v 將65與13交換C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)

42、化學生成績分析系統(tǒng)-指針指針4938134976652797v i=2v 不進行交換4938134976652797v i=1v 將49與13交換再與27交換1338274976654997v 建好的小頭堆建好的小頭堆C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針v從篩選過程可以看出，所建小頭堆是從第從篩選過程可以看出，所建小頭堆是從第4 4個元素個元素9797開始，最后到第開始，最后到第1 1個元素為止。整個篩選過程應個元素為止。整個篩選過程應該是在數(shù)組中進行的，其數(shù)組的變化過程見下圖。該是在數(shù)組中進行的，其數(shù)組的變化過程見下圖。876543210

43、 r4927137697653849初始關鍵字 49 38 65 49 76 13 27 97v9797被篩選后被篩選后： 49 38 13 49 76 65 27 97v6565被篩選后被篩選后： 49 38 13 49 76 65 27 97v3838被篩選后被篩選后： 13 38 27 49 76 65 49 97v4949被篩選后被篩選后( (初始堆初始堆) )：C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針堆排序堆排序v 設有設有n n個元素，首先將這個元素，首先將這n n個元素按關鍵字建成堆（個元素按關鍵字建成堆（根據所排序列的要求建成大

44、頭堆或小頭堆），用根結根據所排序列的要求建成大頭堆或小頭堆），用根結點元素與第點元素與第n n個結點元素交換；然后對前個結點元素交換；然后對前n-1n-1個結點進個結點進行篩選，重新建堆，再以根結點元素與第行篩選，重新建堆，再以根結點元素與第n-1n-1個結點個結點元素交換；重復上述操作，直到整個序列有序。對上元素交換；重復上述操作，直到整個序列有序。對上例進行堆排序的過程見下圖。例進行堆排序的過程見下圖。1338274976654997v 13與97交換9738274976654913v 重建堆C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2738

45、4949766597139738494976652713v 27與97交換3849499776652713v 重建堆v 38與65交換6549499776382713v 重建堆C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針4965499776382713v 49與76交換7665499749382713v 重建堆4965769749382713v 49與97交換9765764949382713v 重建堆C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針6597764949382713v 65與76交換76976

46、54949382713v 重建堆7697654949382713v 76與97交換9776654949382713C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針整個堆排序和重建堆的過程也是在數(shù)組中進行的其變化過程整個堆排序和重建堆的過程也是在數(shù)組中進行的其變化過程見下圖所示。見下圖所示。 初始012345678小頭堆1338274976654997 初始012345678小頭堆1338274976654997v堆排序中的數(shù)組變化堆排序中的數(shù)組變化過程過程v重建堆的數(shù)組變化重建堆的數(shù)組變化過程過程 97 38 27 49 76 65 49 13v13與

47、97對調： 27 38 49 49 76 65 97 13 97 38 49 49 76 65 27 13v27與97對調： 38 49 49 97 76 65 27 13 65 49 49 97 76 38 27 13v38與65對調： 49 65 49 97 76 38 27 13 76 65 49 97 49 38 27 13v49與76對調： 49 65 76 97 49 38 27 13 97 65 76 49 49 38 27 13v49與97對調： 65 97 76 49 49 38 27 13 76 97 65 49 49 38 27 13v65與76對調： 76 97 65

48、49 49 38 27 13 97 76 65 49 49 38 27 13v76與97對調：v重建堆v重建堆v重建堆v重建堆v重建堆v重建堆堆排序的時間復雜度也為堆排序的時間復雜度也為O(nlog2n),是一個不穩(wěn)定的排序方法。是一個不穩(wěn)定的排序方法。C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針按遞減序列堆排序的算法按遞減序列堆排序的算法: :v void heapadjust(datatype r,int s,int m)void heapadjust(datatype r,int s,int m)v r0=rs; r0=rs;v for(j=

49、2 for(j=2* *s;j=m;j=js;j=m;j=j* *2) /2) /* * 沿關鍵字較沿關鍵字較小的孩子結點向下篩選小的孩子結點向下篩選 * */ /v if(jrj+1)j=j+1; / if(jrj+1)j=j+1; /* * 為關鍵字較小的為關鍵字較小的元素下標元素下標* */ /v if(r0rj) break; / if(r00;i-)Heapadjust(r,i,n); / for(i=n/2;i0;i-)Heapadjust(r,i,n); /* * 將將r1.nr1.n建成堆建成堆 * */ /v for(i=n;i1;i-) r0=r1; r1=ri; ri=r

50、0; for(i=n;i1;i-) r0=r1; r1=ri; ri=r0; / /* * 堆頂與堆低元素交換堆頂與堆低元素交換 * */ /v heapadjust(r,1,i-1); heapadjust(r,1,i-1); / /* *將將r1.i-1r1.i-1重新調整為堆重新調整為堆* */ /v v C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針1 1 指針與字符串指針與字符串(1)(1)1.1 1.1 字符串的表示形式字符串的表示形式v用用字符數(shù)組字符數(shù)組存放一個字符串，并輸出該字符串。存放一個字符串，并輸出該字符串。 main()ch

51、ar string =I love China!;printf(%sn,string);C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針1 1 指針與字符串指針與字符串(2)(2)1.1 1.1 字符串的表示形式字符串的表示形式( (續(xù)續(xù)) )v用用字符串指針字符串指針指向一個字符串指向一個字符串 main()char *string=I love China!;printf(%sn,string);C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針1 1 指針與字符串指針與字符串(3)(3)1.1 1.1 字符

52、串的表示形式字符串的表示形式( (續(xù)續(xù)) )例例1 1 寫出下面程序的運行結果寫出下面程序的運行結果 #include void main() char *ptr1,*ptr2; ptr1=ptr2=abcde; while(*ptr2!=0) putchar(*ptr2+); putchar(n); while(-ptr2=ptr1) putchar(*ptr2); putchar(n);運行結果：運行結果：abcdeedcbaC語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針1 1 指針與字符串指針與字符串(4)(4)1.2 1.2 使用字符串指針變

53、量與字符數(shù)組的區(qū)別使用字符串指針變量與字符數(shù)組的區(qū)別字符數(shù)組由若干元素組成字符數(shù)組由若干元素組成，每個元素中放一，每個元素中放一個字符，個字符，而字符指針變量中存放的是地址而字符指針變量中存放的是地址（字（字符串的首地址）。符串的首地址）。賦值方式不同。賦值方式不同。對對字符數(shù)組字符數(shù)組只能對各個元素只能對各個元素賦值，賦值，不能用一個字符串給一個字符數(shù)組賦值不能用一個字符串給一個字符數(shù)組賦值，但對于但對于字符指針變量可以用一個字符串給它賦字符指針變量可以用一個字符串給它賦值值。char str14;str=“ I love China”;char *pstr;pstr=“ I love Ch

54、ina”;C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針1 1 指針與字符串指針與字符串(5)(5)1.2 1.2 使用字符串指針變量與字符數(shù)組的區(qū)別使用字符串指針變量與字符數(shù)組的區(qū)別( (續(xù)續(xù)) )例例2 2 分析下面程序的運行結果分析下面程序的運行結果 main() char *a=I Love China!; a=a+7; printf(“%sn,a);運行結果：運行結果：China!C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針1 1 指針與字符串指針與字符串(6)(6)1.2 1.2 使用字符串指

55、針變量與字符數(shù)組的區(qū)別使用字符串指針變量與字符數(shù)組的區(qū)別( (續(xù)續(xù)) )例例3 3 分析下面程序的運行結果分析下面程序的運行結果 main()char *a=I Love China!; int i; printf(the sixth character is %cn,a5); for(i=0;ai!=0;i+) printf(%c,ai);運行結果：運行結果：the sixth character is eI Love China!C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(1)(1)2.1 2.1 指針變量作為函數(shù)

56、參數(shù)指針變量作為函數(shù)參數(shù)指針變量作為函數(shù)參數(shù)指針變量作為函數(shù)參數(shù)，實參變量實參變量和和形參變量形參變量的的傳遞方式為傳遞方式為地址傳遞地址傳遞void swap1(int x,int y)int z;z=x;x=y;y=z;void swap2(int *x,int *y)int z;z=*x;*x=*y;*y=z;值傳遞值傳遞地址傳遞地址傳遞C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(2)(2)2.1 2.1 指針變量作為函數(shù)參數(shù)指針變量作為函數(shù)參數(shù)( (續(xù)續(xù)) )例例4 4 程序填空，然后分析運行結果。程序填空，然

57、后分析運行結果。( (輸入輸入5 5，6)6)#include main() int a,b; void swap1(int x,int y); void swap2(int *x,int *y); scanf(%d,%d,&a,&b); printf(a=%dtb=%dn,a,b); swap1( ); printf(a=%dtb=%dn,a,b); swap2( ); printf(a=%dtb=%dn,a,b);運行結果：運行結果：a=5 b=6a=5 b=6a=6 b=5C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指

58、針與函數(shù)指針與函數(shù)(3)(3)2.1 2.1 指針變量作為函數(shù)參數(shù)指針變量作為函數(shù)參數(shù)( (續(xù)續(xù)) )例例5 5 一個自然數(shù)是素數(shù)，且它的數(shù)字位置經過任一個自然數(shù)是素數(shù)，且它的數(shù)字位置經過任意對換后仍為素數(shù)，則稱為意對換后仍為素數(shù)，則稱為絕對素數(shù)絕對素數(shù)，例如，例如1313，試求所有兩位絕對素數(shù)。試求所有兩位絕對素數(shù)。解題思路解題思路使用哪種類型的程序結構？使用哪種類型的程序結構？給出一個數(shù)，如何求任意數(shù)字給出一個數(shù)，如何求任意數(shù)字位置對換后的數(shù)？位置對換后的數(shù)？如何判斷一個數(shù)為素數(shù)？如何判斷一個數(shù)為素數(shù)？C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指

59、針2 2 指針與函數(shù)指針與函數(shù)(4)(4)2.2 2.2 指向函數(shù)的指針變量指向函數(shù)的指針變量 在語言中，在語言中，一個函數(shù)占用一段連續(xù)的內存一個函數(shù)占用一段連續(xù)的內存區(qū)區(qū)，而，而函數(shù)名就是該函數(shù)所占內存區(qū)的首地址函數(shù)名就是該函數(shù)所占內存區(qū)的首地址。我們可以把函數(shù)的這個首地址我們可以把函數(shù)的這個首地址(或稱入口地址或稱入口地址)賦賦予一個指針變量，使該指針變量指向該函數(shù)。然予一個指針變量，使該指針變量指向該函數(shù)。然后通過指針變量就可以找到并調用這個函數(shù)。我后通過指針變量就可以找到并調用這個函數(shù)。我們把這種們把這種指向函數(shù)的指針變量指向函數(shù)的指針變量稱為稱為“函數(shù)指針變函數(shù)指針變量量”。C語言程

60、序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(5)(5)2.2 2.2 指向函數(shù)的指針變量指向函數(shù)的指針變量( (續(xù)續(xù)) )函數(shù)指針變量函數(shù)指針變量定義定義的一般形式為：的一般形式為：類型說明符類型說明符 ( (* *指針變量名指針變量名)();)();表示被指函表示被指函數(shù)的返回值數(shù)的返回值的類型的類型“* *”后面的變后面的變量是定義的指量是定義的指針變量針變量指針變量所指指針變量所指的是一個函數(shù)的是一個函數(shù)如：如：int (*pf)();C語言程序設計語言程序設計項目八項目八 優(yōu)化學生成績分析系統(tǒng)優(yōu)化學生成績分析系統(tǒng)-指針指針2 2 指針與函數(shù)指針與函數(shù)(6)(6)2.2 2.2 指向函數(shù)的指針變量指向函數(shù)的指針變量( (續(xù)續(xù)) )用函數(shù)指針變量用