C语言程序设计-第八章优化学生成绩系统-指针

项目八优化学生成绩分析系统-指针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)