項目八優化學生成績分析系統-指針1【項目要求】借助于指針對上一章的的學生成績分析系統進行優化，對某班一門課的成績進行分析，要求有如下功能：1.查詢全部成績；2.查詢平均分；3.查詢不及格率；4.查詢最高分；5.按成績降序排列；0.退出。為了保存一個班的C語言成績需要借助于一維數組，通過指針對其數據進行操作。將本項目分成兩部分，首先借助于指針對一維數組進行訪問，然后介紹一種新的排序算法—選擇排序。【項目分析】2問題情境及實現

通過前面所學知道，可以通過下標法訪問數組元素，數組名代表數組的首地址，即指針，我們亦可通過其對數組元素進行訪問。#defineN100#include<stdio.h>voidmain(){int

s[N],n,*p;printf("請輸入該班人數");scanf("%d",&n);printf("請錄入成績");for(p=s;p<s+n;p++)

scanf("%d",p);printf("該班的全部成績是:\n");for(p=s;p<s+n;p++)printf("%6d",*p);}344本講主要內容2.指針與函數本講小結1.指針與字符串3.指針數組重點：指針與函數4.指針應用舉例1指針與字符串(1)1.1字符串的表示形式用字符數組存放一個字符串，并輸出該字符串。

main(){ charstring[]="IloveChina!";

printf("%s\n",string);}如果用字符指針，這段代碼應如何修改？51指針與字符串(2)1.1字符串的表示形式(續)用字符串指針指向一個字符串

main(){ char*string="IloveChina!";

printf("%s\n",string);}61指針與字符串(3)1.1字符串的表示形式(續)例1寫出下面程序的運行結果

#include<stdio.h>voidmain(){char*ptr1,*ptr2;ptr1=ptr2="abcde";

while(*ptr2!='\0')

putchar(*ptr2++);

putchar('\n');

while(--ptr2>=ptr1)

putchar(*ptr2);

putchar('\n');}運行結果：abcdeedcba71指針與字符串(4)1.2使用字符串指針變量與字符數組的區別①字符數組由若干元素組成，每個元素中放一個字符，而字符指針變量中存放的是地址（字符串的首地址）。②賦值方式不同。對字符數組只能對各個元素賦值，不能用一個字符串給一個字符數組賦值，但對于字符指針變量可以用一個字符串給它賦值。charstr[14];str=“IloveChina”;char*pstr;pstr=“IloveChina”;√81指針與字符串(5)1.2使用字符串指針變量與字符數組的區別(續)例2分析下面程序的運行結果

main(){char*a="ILoveChina!";

a=a+7;

printf(“%s\n",a);}運行結果：China!91指針與字符串(6)1.2使用字符串指針變量與字符數組的區別(續)例3分析下面程序的運行結果

main(){char*a="ILoveChina!";

inti;

printf("thesixthcharacteris%c\n",a[5]);for(i=0;a[i]!='\0';i++)

printf("%c",a[i]);}運行結果：thesixthcharacteriseILoveChina!返回主菜單102指針與函數(1)2.1指針變量作為函數參數指針變量作為函數參數，實參變量和形參變量的傳遞方式為地址傳遞voidswap1(intx,inty){

intz; z=x; x=y; y=z;}voidswap2(int*x,int*y){

intz; z=*x; *x=*y; *y=z;}值傳遞地址傳遞112指針與函數(2)2.1指針變量作為函數參數(續)例4程序填空，然后分析運行結果。(輸入5，6)#include<stdio.h>main(){

int

a,b;voidswap1(intx,inty);voidswap2(int*x,int*y);

scanf("%d,%d",&a,&b);

printf("a=%d\tb=%d\n",a,b);swap1(

);

printf("a=%d\tb=%d\n",a,b);swap2(

);

printf("a=%d\tb=%d\n",a,b);}運行結果：a=5b=6a=5b=6a=6b=5a,b&a,&b122指針與函數(3)2.1指針變量作為函數參數(續)例5

一個自然數是素數，且它的數字位置經過任意對換后仍為素數，則稱為絕對素數，例如13，試求所有兩位絕對素數。解題思路①使用哪種類型的程序結構？②給出一個數，如何求任意數字位置對換后的數？③如何判斷一個數為素數？例5程序編寫思考：如果求所有三位絕對素數，132指針與函數(4)2.2指向函數的指針變量在Ｃ語言中，一個函數占用一段連續的內存區，而函數名就是該函數所占內存區的首地址。我們可以把函數的這個首地址(或稱入口地址)賦予一個指針變量，使該指針變量指向該函數。然后通過指針變量就可以找到并調用這個函數。我們把這種指向函數的指針變量稱為“函數指針變量”。142指針與函數(5)2.2指向函數的指針變量(續)函數指針變量定義的一般形式為：類型說明符(*指針變量名)();表示被指函數的返回值的類型“*”后面的變量是定義的指針變量指針變量所指的是一個函數如：int(*pf)();152指針與函數(6)2.2指向函數的指針變量(續)用函數指針變量調用函數的一般形式為：(*指針變量名)(實參表)162指針與函數(7)2.2指向函數的指針變量(續)例6將給出的程序修改為使用函數指針變量定義的方式

main(){

int

max(int,int);

inta,b,c;

scanf("%d,%d",&a,&b);c=max(a,b);

printf("a=%d,b=%d,max=%d",a,b,c);}max(int

x,inty){

intz;

if(x>y)z=x;elsez=y;return(z);}int(*p)();p=max;c=(*p)(a,b);172指針與函數(8)2.2指向函數的指針變量—函數指針作為函數參數例7分析下面程序的執行過程#include<stdio.h>main(){int

add(int

a,intb);

int

sub(int

a,intb);

fun(int(*)p(),int

a,intb);

int(*ps)(),x,y,z;

scanf("%d,%d",&x,&y);

if(x<y) z=fun(add,x,y);else{ ps=sub; z=fun(ps,x,y);}

printf("x=%d,y=%d,z=%d\n",x,y,z);}add(int

a,intb){return(a+b);}sub(int

a,intb){return(a-b);}fun函數如何定義？fun(int(*pf)(),int

a,intb){return((*pf)(a,b));}182指針與函數(9)2.2指向函數的指針變量—返回值為指針的函數定義返回值為指針變量類型的函數的一般形式為：類型符*函數名(參數表)192指針與函數(10)2.2指向函數的指針變量—返回值為指針的函數例8分析給出程序的運行結果#include<stdio.h>int*f(int*x,int*y){ if(*x<*y) returnx; else returny;}voidmain(){ inta=17,b=18,*p,*q,*r; p=&a; q=&b; r=f(p,q);

printf("%d,%d,%d\n",*p,*q,*r);}運行結果：17，18，17返回主菜單203指針數組(1)3.1指針數組指針數組的定義形式為：類型符*指針數組名[常量表達式];課堂練習，分析下面語句的含義：int*p[4];Int(*p)[4];指針數組，有4個元素，每個元素都是指向整型變量指針變量由4個整型變量組成的數組的指針213指針數組(2)3.1指針數組(續)#include<stdio.h>main(){staticint

a[3][4]={{11,22,33,44},{55,66,77,88},{99,110,122,133}};

int*p[3]={a[0],a[1],a[2]};

int

i,j;

for(i=0;i<3;i++){

for(j=0;j<4;j++)

printf("a[%d][%d]=%d\t",i,j,p[i][j]);

printf("\n");}}133122110998877665544332211p[0]p[1]p[2]223指針數組(3)3.1指針數組(續)#include<stdio.h>main(){staticint

a[3][4]={{11,22,33,44},{55,66,77,88},{99,110,122,133}};

int*p[3]={a[0],a[1],a[2]};

int(*q)[4];

int

i,j;q=a;

for(i=0;i<3;i++){

for(j=0;j<4;j++)

printf("a[%d][%d]=%d\t",i,j,(*(q+i))[j]);

printf("\n");}}133122110998877665544332211qq+1q+2(*q)[0](*q)[1](*q)[2](*q)[3]233指針數組(4)P223指向指針的指針P224main函數的參數返回主菜單244指針應用舉例(1)例9

編寫程序，利用系統提供的圖形庫函數在屏幕上畫一個圖形，方法是將一個半徑為r1的圓周等分n份，再以每個等分點為圓心，以半徑rs畫n個圓，要求在命令方式下給出r1,rs的值及環的顏色值。本例主要說明main函數參數的使用，254指針應用舉例(2)例10編寫程序，采用冒泡法對一組整數進行升序或降序排序，然后輸出排序結果。要求：由計算機生成10—100以內的隨機整數50個，放入數組。通過函數指針，完成對數組的升序或者降序的排序。本例主要說明指針作為函數參數，返回主菜單262727本講小結掌握字符指針的使用掌握指針作為函數參數的使用了解指向函數的指針變量的使用了解指針數據的使用【項目要求】借助于指針對上一章的的學生成績分析系統進行優化，對某班一門課的成績進行分析，要求有如下功能：1.查詢全部成績；2.查詢平均分；3.查詢不及格率；4.查詢最高分；5.按成績降序排列；0.退出。為了保存一個班的C語言成績需要借助于一維數組，通過指針對其數據進行操作。將本項目分成兩部分，首先借助于指針對一維數組進行訪問，然后介紹一種新的排序算法—選擇排序。【項目分析】28問題情境及實現

通過前面所講可實現本系統的前4個功能，下面借助于指針實現數據的排序。采用簡單選擇排序方法進行，程序如下：#defineN100#include<stdio.h>#include<string.h>voidfselectsort(int*a,intn){int*p,*q,*pmax,t;for(p=a;p<a+n-1;p++){pmax=p;

for(q=p+1;q<a+n;q++)if(*pmax<*q)pmax=q;

if(p!=pmax){t=*p;*p=*pmax;*pmax=t;}}}

29相關知識：簡單選擇排序

簡單選擇排序的基本方法是：第一趟，從n個記錄中找出關鍵字最小的記錄與第一個記錄交換；第二趟，從第二個記錄開始的n-1個記錄中再選出關鍵字最小的記錄與第二個記錄交換；如此，第i趟，則從第i個記錄開始的n-i+1個記錄中選出關鍵字最小的記錄與第i個記錄交換，直到整個序列按關鍵字有序排列。30

簡單選擇排序算法:voidselectsort(datatype

r[],intn){int

i,j,t;

for(i=1;i<=n;i++){t=i;

for(j=i+1;j<=n;j++)

if(r[t]>r[j])t=j;

if(i!=t){r[0]=r[t];

r[t]=r[i];

r[i]=r[0];} }}31對如下關鍵字(49,38,65,97,76,13,27,49)進行簡單選擇排序的過程見下圖。

r012345678初始關鍵字4938659776132749

13[38

65

97764927

49]第一趟結果：第二趟結果：

1327

[65

97764938

49]第三趟結果：

1327

38

[97

764965

49]第四趟結果：

1327

38

49[769765

49]第五趟結果：

1327

38

4949[9765

76]第六趟結果：

1327

38

4949[6597

76]第七趟結果：

1327

38

49496576

97簡單選擇排序移動記錄的次數較少，但關鍵字的比較次數依然是n(n+1)/2，所以時間復雜度仍為O(n2)。

32樹形選擇排序按照錦標賽的思想進行，將n個參賽的選手看成完全二叉樹的葉結點，則該完全二叉樹有2n-2或2n-1個結點。首先，兩兩進行比賽(在樹中是兄弟的進行，否則輪空，直接進入下一輪)，勝出的再兄弟間再兩兩進行比較，直到產生第1名。接下來，將作為第1名的結點看成最差的，并從該結點開始，沿該結點到根路徑上，依次進行各分枝結點子女間的比較，勝出的就是第2名。因為和他比賽的均是剛剛輸給第1名的選手。如此，繼續進行下去，直到所有選手的名次排定。33對如下關鍵字(49,38,65,97,76,13,27,49)進行簡單選擇排序的過程見下圖。

r012345678初始關鍵字4938659776132749492776133849976549977649977697存放排序012345678結果的數組97再將97設為最差(最小)。34

r012345678初始關鍵字49386507613274949277613384906549657649657676存放排序012345678結果的數組7697再將76設為最差(最小)。35

r012345678初始關鍵字493865001327494927013384906549651349654965存放排序012345678結果的數組657697再將65設為最差(最小)。36

r012345678初始關鍵字493800013274949270133849004901349494949存放排序012345678結果的數組49657697注意：若取49則為穩定的排序。再將49設為最差(最小)。37

r012345678初始關鍵字0380001327490270133849003801349384949存放排序012345678結果的數組4949657697再將49設為最差(最小)。38

r012345678初始關鍵字03800013270027013380003801327382738存放排序012345678結果的數組384949657697再將38設為最差(最小)。39

r012345678初始關鍵字0000013270027013000000132702727存放排序012345678結果的數組27384949657697再將27設為最差(最小)。40

r012345678初始關鍵字0000013000001300000013001313最后排序012345678的結果132738494965769741堆排序堆排序是樹形選擇排序方法的改進，它使用的輔助空間較少，僅增加一個記錄空間進行交換，同時關鍵字比較的次數和樹形選擇排序相當。1.堆的定義和存儲結構堆是一棵完全二叉樹，組成這棵完全二叉樹的n個元素序列k1，k2，…，kn，當且僅當滿足下述關系之一時，稱之為堆。Ki≥k2iKi≥k2i+1大頭堆或者Ki≤k2iKi≤k2i+1小頭堆其中i=1,2,…,n/242如以下關鍵字(49,38,65,97,76,13,27,49)所建立的大頭堆和小頭堆如下圖所示：用一維數組存儲一個堆，則堆對應的存儲結構如下：9776654949132738大頭堆1338274976654997小頭堆

012345678大頭堆9776654949132738012345678小頭堆133827497665499743建立初始堆

對初始序列建堆的過程，就是一個反復進行篩選的過程。對n個結點的完全二叉樹只需從第n/2個元素開始。例如:對元素(49,38,65,97,76,13,27,49)進行篩選的過程見下圖(建小頭堆)。4938659776132749i=4將97與49交換4938654976132797i=3將65與13交換444938134976652797i=2不進行交換4938134976652797i=1將49與13交換再與27交換1338274976654997建好的小頭堆45從篩選過程可以看出，所建小頭堆是從第4個元素97開始，最后到第1個元素為止。整個篩選過程應該是在數組中進行的，其數組的變化過程見下圖。876543210

r4927137697653849初始關鍵字

4938

65497613279797被篩選后：

4938

13497665279765被篩選后：

4938

13497665279738被篩選后：

1338

27497665499749被篩選后(初始堆)：46堆排序

設有n個元素，首先將這n個元素按關鍵字建成堆（根據所排序列的要求建成大頭堆或小頭堆），用根結點元素與第n個結點元素交換；然后對前n-1個結點進行篩選，重新建堆，再以根結點元素與第n-1個結點元素交換；重復上述操作，直到整個序列有序。對上例進行堆排序的過程見下圖。133827497665499713與97交換9738274976654913重建堆472738494976659713973849497665271327與97交換3849499776652713重建堆38與65交換6549499776382713重建堆48496549977638271349與76交換7665499749382713重建堆496576974938271349與97交換9765764949382713重建堆49659776494938271365與76交換7697654949382713重建堆769765494938271376與97交換977665494938271350整個堆排序和重建堆的過程也是在數組中進行的其變化過程見下圖所示。初始012345678小頭堆1338274976654997初始012345678小頭堆1338274976654997堆排序中的數組變化過程重建堆的數組變化過程

973827497665491313與97對調：

273849

4976659713

973849497665271327與97對調：

3849

499776652713

654949977638271338與65對調：

4965499776382713

766549974938271349與76對調：

4965769749382713

976576494938271349與97對調：

6597764949382713

769765494938271365與76對調：

7697654949382713

977665494938271376與97對調：重建堆重建堆重建堆重建堆重建堆重建堆堆排序的時間復雜度也為O(nlog2n),是一個不穩定的排序方法。51按遞減序列堆排序的算法:voidheapadjust(datatype

r[],int

s,intm){r[0]=r[s];

for(j=2*s;j<=m;j=j*2)/*沿關鍵字較小的孩子結點向下篩選*/ {if(j<m&&r[j]>r[j+1])j=j+1;/*為關鍵字較小的元素下標*/ if(r[0]<r[j])break;/*r[0]應插入在位置s上*/

else{r[s]=r[j];s=j;}/*使s結點滿足堆定義*/}

r[s]=r[0];/*插入*/}voidheapsort(datatype

r[],intn){for(i=n/2;i>0;i--)Heapadjust(r,i,n);/*將r[1..n]建成堆*/

for(i=n;i>1;i--){r[0]=r[1];r[1]=r[i];r[i]=r[0];/*堆頂與堆低元素交換*/heapadjust(r,1,i-1);/*將r[1..i-1]重新調整為堆*/ }}521指針與字符串(1)1.1字符串的表示形式用字符數組存放一個字符串，并輸出該字符串。

main(){ charstring[]="IloveChina!";

printf("%s\n",string);}如果用字符指針，這段代碼應如何修改？531指針與字符串(2)1.1字符串的表示形式(續)用字符串指針指向一個字符串

main(){ char*string="IloveChina!";

printf("%s\n",string);}541指針與字符串(3)1.1字符串的表示形式(續)例1寫出下面程序的運行結果

#include<stdio.h>voidmain(){char*ptr1,*ptr2;ptr1=ptr2="abcde";

while(*ptr2!='\0')

putchar(*ptr2++);

putchar('\n');

while(--ptr2>=ptr1)

putchar(*ptr2);

putchar('\n');}運行結果：abcdeedcba551指針與字符串(4)1.2使用字符串指針變量與字符數組的區別①字符數組由若干元素組成，每個元素中放一個字符，而字符指針變量中存放的是地址（字符串的首地址）。②賦值方式不同。對字符數組只能對各個元素賦值，不能用一個字符串給一個字符數組賦值，但對于字符指針變量可以用一個字符串給它賦值。charstr[14];str=“IloveChina”;char*pstr;pstr=“IloveChina”;√561指針與字符串(5)1.2使用字符串指針變量與字符數組的區別(續)例2分析下面程序的運行結果

main(){char*a="ILoveChina!";

a=a+7;

printf(“%s\n",a);}運行結果：China!571指針與字符串(6)1.2使用字符串指針變量與字符數組的區別(續)例3分析下面程序的運行結果

main(){char*a="ILoveChina!";

inti;

printf("thesixthcharacteris%c\n",a[5]);for(i=0;a[i]!='\0';i++)

printf("%c",a[i]);}運行結果：thesixthcharacteriseILoveChina!返回主菜單582指針與函數(1)2.1指針變量作為函數參數指針變量作為函數參數，實參變量和形參變量的傳遞方式為地址傳遞voidswap1(intx,inty){

intz; z=x; x=y; y=z;}voidswap2(int*x,int*y){

intz; z=*x; *x=*y; *y=z;}值傳遞地址傳遞592指針與函數(2)2.1指針變量作為函數參數(續)例4程序填空，然后分析運行結果。(輸入5，6)#include<stdio.h>main(){

int

a,b;voidswap1(intx,inty);voidswap2(int*x,int*y);

scanf("%d,%d",&a,&b);

printf("a=%d\tb=%d\n",a,b);swap1(

);

printf("a=%d\tb=%d\n",a,b);swap2(

);

printf("a=%d\tb=%d\n",a,b);}運行結果：a=5b=6a=5b=6a=6b=5a,b&a,&b602指針與函數(3)2.1指針變量作為函數參數(續)例5

一個自然數是素數，且它的數字位置經過任意對換后仍為素數，則稱為絕對素數，例如13，試求所有兩位絕對素數。解題思路①使用哪種類型的程序結構？②給出一個數，如何求任意數字位置對換后的數？③如何判斷一個數為素數？例5程序編寫思考：如果求所有三位絕對素數，612指針與函數(4)2.2指向函數的指針變量在Ｃ語言中，一個函數占用一段連續的內存區，而函數名就是該函數所占內存區的首地址。我們可以把函數的這個首地址(或稱入口地址)賦予一個指針變量，使該指針變量指向該函數。然后通過指針變量就可以找到并調用這個函數。我們把這種指向函數的指針變量稱為“函數指針變量”。622指針與函數(5)2.2指向函數的指針變量(續)函數指針變量定義的一般形式為：類型說明符(*指針變量名)();表示被指函數的返回值的類型“*”后面的變量是定義的指針變量指針變量所指的是一個函數如：int(*pf)();632指針與函數(6)2.2指向函數的指針變量(續)用函數指針變量調用函數的一般形式為：(*指針變量名)(實參表)642指針與函數(7)2.2指向函數的指針變量(續)例6將給出的程序修改為使用函數指針變量定義的方式

main(){

int

max(int,int);

inta,b,c;

scanf("%d,%d",&a,&b);c=max(a,b);

printf("a=%d,b=%d,max=%d",a,b,c);}max(int

x,inty){

intz;

if(x>y)z=x;elsez=y;return(z);}int(*p)();p=max;c=(*p)(a,b);652指針與函數(8)2.2指向函數的指針變量—函數指針作為函數參數例7分析下面程序的執行過程#include<stdio.h>main(){int

add(int

a,intb);

int

sub(int

a,intb);

fun(int(*)p(),int

a,intb);

int(*ps)(),x,y,z;

scanf("%d,%d",&x,&y);

if(x<y) z=fun(add,x,y);else{ ps=sub; z=fun(ps,x,y);}

printf("x=%d,y=%d,z=%d\n",x,y,z);}add(int

a,intb){return(a+b);}sub(int

a,intb){return(a-b);}fun函數如何定義？fun(int(*pf)(),int

a,intb)