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

1、C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针项目八八 优化学生成绩分析系统优化学生成绩分析系统- -指针指针C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针【项目要求项目要求】借助于指针对上一章的的学生成绩分析系统进行优化，对某班一门课的借助于指针对上一章的的学生成绩分析系统进行优化，对某班一门课的成绩进行分析，要求有如下功能：成绩进行分析，要求有如下功能：1.1.查询全部成绩；查询全部成绩；2.2.查询平均分；查询平均分；3.3.查询不及格率；查询不及格率；4.4.查询最高分；查询最高分；5.5.按成绩降

2、序排列；按成绩降序排列；0.0.退出。退出。 为了保存一个班的为了保存一个班的C语言成绩需要借助于一维数组，通过指针对其数语言成绩需要借助于一维数组，通过指针对其数据进行操作。将本项目分成两部分，首先借助于指针对一维数组进行据进行操作。将本项目分成两部分，首先借助于指针对一维数组进行访问，然后介绍一种新的排序算法访问，然后介绍一种新的排序算法选择排序。选择排序。【项目分析项目分析】C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针问题情境及实现问题情境及实现v 通过前面所学知道，可以通过下标法访问数组元素，数组名代表数组通过前面所学知道，可以通过下标法访

3、问数组元素，数组名代表数组的首地址，即指针，我们亦可通过其对数组元素进行访问。的首地址，即指针，我们亦可通过其对数组元素进行访问。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(请输入该班人数请输入该班人数););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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针4 4 4 4本讲主要内容本讲主要内容2. 指针与函数指针与函数1. 指针与字符串指针与字符串3. 指针数组指针数组4. 指针应用举例指针应用举例C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针

5、1 1 指针与字符串指针与字符串(1)(1)1.1 1.1 字符串的表示形式字符串的表示形式v用用字符数组字符数组存放一个字符串，并输出该字符串。存放一个字符串，并输出该字符串。 main()char string =I love China!;printf(%sn,string);C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针1 1 指针与字符串指针与字符串(2)(2)1.1 1.1 字符串的表示形式字符串的表示形式( (续续) )v用用字符串指针字符串指针指向一个字符串指向一个字符串 main()char *string=I love China

6、!;printf(%sn,string);C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针1 1 指针与字符串指针与字符串(3)(3)1.1 1.1 字符串的表示形式字符串的表示形式( (续续) )例例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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针1 1 指针与字符串指针与字符串(4)(4)1.2 1.2 使用字符串指针变量与字符数组的区别使用字符串指针变量与字符数组的区别字符数组由若干元素组成字符数组由若干元素组成，每个元素中放一，每个元素中放一个字符，个字符，而字符指针变量中存放的是地址而字符指针变量中存放的是地址（字（字符串的首地址）。符串的首地址）。赋值方式不同。赋值方式不同。对对字符数组字符数组只能对各个元素只能对各个元素赋值，赋值，不能用一个字符串给一个字符数组赋值不能用一个字符串给一个字符数组赋值，但对于

8、但对于字符指针变量可以用一个字符串给它赋字符指针变量可以用一个字符串给它赋值值。char str14;str=“ I love China”;char *pstr;pstr=“ I love China”;C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针1 1 指针与字符串指针与字符串(5)(5)1.2 1.2 使用字符串指针变量与字符数组的区别使用字符串指针变量与字符数组的区别( (续续) )例例2 2 分析下面程序的运行结果分析下面程序的运行结果 main() char *a=I Love China!; a=a+7; printf(“%sn,a)

9、;运行结果：运行结果：China!C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针1 1 指针与字符串指针与字符串(6)(6)1.2 1.2 使用字符串指针变量与字符数组的区别使用字符串指针变量与字符数组的区别( (续续) )例例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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(1)(1)2.1 2.1 指针变量作为函数参数指针变量作为函数参数指针变量作为函数参数指针变量作为函数参数，实参变量实参变量和和形参变量形参变量的的传递方式为传递方式为地址传递地址传递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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系

11、统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(2)(2)2.1 2.1 指针变量作为函数参数指针变量作为函数参数( (续续) )例例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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(3)(3)2.1 2.1 指针变量作为函数参数指针变量作为函数参数( (续续) )例例5 5 一个自然数是素数，且它的数字位置经过任一个自然数是素数，且它的数字位置经过任意对换后仍为素数，则称为意对换后仍为素数，则称为绝对素数绝对素数，例如，例如1313，试求所有两位绝对素数。试求所有两位绝对素数。解题思路解题思路使用哪种类型的程序结构？使用哪种类型的程序结构？给出一个数，如何求任

13、意数字给出一个数，如何求任意数字位置对换后的数？位置对换后的数？如何判断一个数为素数？如何判断一个数为素数？C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(4)(4)2.2 2.2 指向函数的指针变量指向函数的指针变量 在语言中，在语言中，一个函数占用一段连续的内存一个函数占用一段连续的内存区区，而，而函数名就是该函数所占内存区的首地址函数名就是该函数所占内存区的首地址。我们可以把函数的这个首地址我们可以把函数的这个首地址(或称入口地址或称入口地址)赋赋予一个指针变量，使该指针变量指向该函数。然予一个指针变量，使该指针变量

14、指向该函数。然后通过指针变量就可以找到并调用这个函数。我后通过指针变量就可以找到并调用这个函数。我们把这种们把这种指向函数的指针变量指向函数的指针变量称为称为“函数指针变函数指针变量量”。C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(5)(5)2.2 2.2 指向函数的指针变量指向函数的指针变量( (续续) )函数指针变量函数指针变量定义定义的一般形式为：的一般形式为：类型说明符类型说明符 ( (* *指针变量名指针变量名)();)();表示被指函表示被指函数的返回值数的返回值的类型的类型“* *”后面的变后面的变量是定

15、义的指量是定义的指针变量针变量指针变量所指指针变量所指的是一个函数的是一个函数如：如：int (*pf)();C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(6)(6)2.2 2.2 指向函数的指针变量指向函数的指针变量( (续续) )用函数指针变量用函数指针变量调用函数调用函数的一般形式为：的一般形式为：( (* *指针变量名指针变量名)()(实参表实参表) )C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(7)(7)2.2 2.2 指向函数的指针变

16、量指向函数的指针变量( (续续) )例例6 6 将给出的程序修改为使用函数指针变量定义将给出的程序修改为使用函数指针变量定义的方式的方式 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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系

17、统-指针指针2 2 指针与函数指针与函数(8)(8)2.2 2.2 指向函数的指针变量指向函数的指针变量函数指针作为函数参数函数指针作为函数参数例例7 7 分析下面程序的执行过程分析下面程序的执行过程#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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(9)(9)2.2 2.2 指向函数的指针变量指向函数的指针变量返回值为指针的函数返回值为指针的函数定义定义返回值为指针变量类型的函数返回值为指针变量类型的函数的一般形式为：的一般形式为：类型符类型符 * *函数名函数名( (参数表参数

19、表) )C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(10)(10)2.2 2.2 指向函数的指针变量指向函数的指针变量返回值为指针的函数返回值为指针的函数例例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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针3 3 指针数组指针数组 (1)(1)3.1 3.1 指针数组指针数组指针数组的定义形式为：指针数组的定义形式为：类型符类型符 * *指针数组名指针数组名 常量表达式常量表达式;课堂练习，分析下面语句的含义：课堂练习，分析下面语句的含义：int *p4;Int (*p)4;指针数组，有指针数组，有4个元素，个元素，每个元素每个元素都是指向整型变量指针变量都是指向整型变量指针变量由由4个整型变量组成的数组的指针个整型变量组成的数组的指针C语言程序设计语言程序设计项目八项目八 优化学生成绩

21、分析系统优化学生成绩分析系统-指针指针3 3 指针数组指针数组 (2)(2)3.1 3.1 指针数组指针数组( (续续) )#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、计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针3 3 指针数组指针数组 (3)(3)3.1 3.1 指针数组指针数组( (续续) )#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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针3 3 指针数组指针数组(4)(4)C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针4 4 指针应用举例指针应用举例(1)(1)例例9 编写程序，编写程序，利用系统提供的图形库函数在屏利用系统提供的图形库函数在屏幕上画一个图形幕上画一个图形，方法是将一个半径为，方法是将一个半径为r1的圆周的圆周等分等分n份，再以每个等分点为圆心，以半径份，再以每个等分点为圆心，以半径rs画画n个

24、圆，要求在命令方式下给出个圆，要求在命令方式下给出r1,rs的值及环的颜的值及环的颜色值。色值。C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针4 4 指针应用举例指针应用举例(2)(2)例例10 编写程序，采用冒泡法对一组整数进行升序编写程序，采用冒泡法对一组整数进行升序或降序排序，然后输出排序结果。要求：由计算或降序排序，然后输出排序结果。要求：由计算机生成机生成10100以内的以内的随机整数随机整数50个个，放入数组。，放入数组。通过通过函数指针，完成对数组的升序或者降序的排函数指针，完成对数组的升序或者降序的排序。序。C语言程序设计语言程序设计

25、项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针27272727本讲小结本讲小结v掌握字符指针的使用掌握字符指针的使用v掌握指针作为函数参数的使用掌握指针作为函数参数的使用v了解指向函数的指针变量的使用了解指向函数的指针变量的使用v了解指针数据的使用了解指针数据的使用C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针【项目要求项目要求】借助于指针对上一章的的学生成绩分析系统进行优化，对某班一门课的借助于指针对上一章的的学生成绩分析系统进行优化，对某班一门课的成绩进行分析，要求有如下功能：成绩进行分析，要求有如下功能：1.1.查询全部成绩；

26、查询全部成绩；2.2.查询平均分；查询平均分；3.3.查询不及格率；查询不及格率；4.4.查询最高分；查询最高分；5.5.按成绩降序排列；按成绩降序排列；0.0.退出。退出。 为了保存一个班的为了保存一个班的C语言成绩需要借助于一维数组，通过指针对其数语言成绩需要借助于一维数组，通过指针对其数据进行操作。将本项目分成两部分，首先借助于指针对一维数组进行据进行操作。将本项目分成两部分，首先借助于指针对一维数组进行访问，然后介绍一种新的排序算法访问，然后介绍一种新的排序算法选择排序。选择排序。【项目分析项目分析】C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针

27、指针问题情境及实现问题情境及实现v 通过前面所讲可实现本系统的前通过前面所讲可实现本系统的前4 4个功能，下面借助于指针实现数据个功能，下面借助于指针实现数据的排序。采用简单选择排序方法进行，程序如下：的排序。采用简单选择排序方法进行，程序如下：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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针相关知识：简单选择排序相关知识：简单选择排序v 简单选择排序的基本方法是：第一趟，从

29、简单选择排序的基本方法是：第一趟，从n n个记录中找出关键字最小的记录与第一个记个记录中找出关键字最小的记录与第一个记录交换；第二趟，从第二个记录开始的录交换；第二趟，从第二个记录开始的n-1n-1个记录中再选出关键字最小的记录与第二个个记录中再选出关键字最小的记录与第二个记录交换；如此，第记录交换；如此，第i i趟，则从第趟，则从第i i个记录开个记录开始的始的vn-i+1n-i+1个记录中选出关键字最小的记录与第个记录中选出关键字最小的记录与第i i个记录交换，直到整个序列按关键字有序排个记录交换，直到整个序列按关键字有序排列。列。C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系

30、统优化学生成绩分析系统-指针指针 简单选择排序算法简单选择排序算法: :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、言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针 对如下关键字对如下关键字(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 简单选择排序移动记录的次数较少，但关键字的比较次数依然是n(n+1)/2，所以时间复杂度仍为O(n2)。 C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针树形选择排序树形选择排序v按照锦标赛的思想进行，将按照锦标赛的思想进行，将n n个参赛的选手看成完个参赛的选手看成完全二叉树的叶结点，则该完全二叉树有全二叉树的叶

33、结点，则该完全二叉树有2n-22n-2或或2n-2n-1 1个结点。首先，两两进行比赛个结点。首先，两两进行比赛( (在树中是兄弟的在树中是兄弟的进行，否则轮空，直接进入下一轮进行，否则轮空，直接进入下一轮) )，胜出的再兄，胜出的再兄弟间再两两进行比较，直到产生第弟间再两两进行比较，直到产生第1 1名。名。v接下来，将作为第接下来，将作为第1 1名的结点看成最差的，并从该名的结点看成最差的，并从该结点开始，沿该结点到根路径上，依次进行各分结点开始，沿该结点到根路径上，依次进行各分枝结点子女间的比较，胜出的就是第枝结点子女间的比较，胜出的就是第2 2名。因为和名。因为和他比赛的均是刚刚输给第他

34、比赛的均是刚刚输给第1 1名的选手。名的选手。v如此，继续进行下去，直到所有选手的名次排定。如此，继续进行下去，直到所有选手的名次排定。C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针 对如下关键字对如下关键字(49,38,65,97,76,13,27,49)(49,38,65,97,76,13,27,49)进行简单选择排序的过程见下图。进行简单选择排序的过程见下图。 r012345678初始关键字4938659776132749492776133849976549977649977697 存放排序012345678结果的数组97再将再将97设为最差设

35、为最差(最小最小)。 C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针 r012345678初始关键字49386507613274949277613384906549657649657676 存放排序012345678结果的数组7697再将再将76设为最差设为最差(最小最小)。 C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针 r012345678初始关键字493865001327494927013384906549651349654965 存放排序012345678结果的数组657697再将再将65设为最差设

36、为最差(最小最小)。 C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针 r012345678初始关键字493800013274949270133849004901349494949 存放排序012345678结果的数组49657697v注意：若取注意：若取4949则为稳定的排序。则为稳定的排序。再将再将49设为最差设为最差(最小最小)。 C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针 r012345678初始关键字0380001327490270133849003801349384949 存放排序012345

37、678结果的数组4949657697再将再将49设为最差设为最差(最小最小)。 C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针 r012345678初始关键字03800013270027013380003801327382738 存放排序012345678结果的数组384949657697再将再将38设为最差设为最差(最小最小)。 C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针 r012345678初始关键字0000013270027013000000132702727 存放排序012345678结果的数组

38、27384949657697再将再将27设为最差设为最差(最小最小)。 C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针 r012345678初始关键字0000013000001300000013001313 最后排序012345678 的结果1327384949657697C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针堆排序堆排序v堆排序是树形选择排序方法的改进，它使用的辅堆排序是树形选择排序方法的改进，它使用的辅助空间较少，仅增加一个记录空间进行交换，同助空间较少，仅增加一个记录空间进行交换，同时关键字比

39、较的次数和树形选择排序相当。时关键字比较的次数和树形选择排序相当。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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针v如

40、以下关键字如以下关键字(49,38,65,97,76,13,27,(49,38,65,97,76,13,27,4949) )所建立所建立的大头堆和小头堆如下图所示：的大头堆和小头堆如下图所示：v用一维数组存储一个堆，则堆对应的存储结构如下：用一维数组存储一个堆，则堆对应的存储结构如下：9776654949132738v 大头大头堆堆1338274976654997v 小头小头堆堆 012345678大头堆9776654949132738012345678小头堆1338274976654997C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优

42、化学生成绩分析系统-指针指针4938134976652797v i=2v 不进行交换4938134976652797v i=1v 将49与13交换再与27交换1338274976654997v 建好的小头堆建好的小头堆C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针v从筛选过程可以看出，所建小头堆是从第从筛选过程可以看出，所建小头堆是从第4 4个元素个元素9797开始，最后到第开始，最后到第1 1个元素为止。整个筛选过程应个元素为止。整个筛选过程应该是在数组中进行的，其数组的变化过程见下图。该是在数组中进行的，其数组的变化过程见下图。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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针堆排序堆排序v 设有设有n n个元素，首先将这个元素，首先将这n n个元素按关键字建成堆（个元素按关键字建成堆（根据所排序列的要求建成大

44、头堆或小头堆），用根结根据所排序列的要求建成大头堆或小头堆），用根结点元素与第点元素与第n n个结点元素交换；然后对前个结点元素交换；然后对前n-1n-1个结点进个结点进行筛选，重新建堆，再以根结点元素与第行筛选，重新建堆，再以根结点元素与第n-1n-1个结点个结点元素交换；重复上述操作，直到整个序列有序。对上元素交换；重复上述操作，直到整个序列有序。对上例进行堆排序的过程见下图。例进行堆排序的过程见下图。1338274976654997v 13与97交换9738274976654913v 重建堆C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2738

45、4949766597139738494976652713v 27与97交换3849499776652713v 重建堆v 38与65交换6549499776382713v 重建堆C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针4965499776382713v 49与76交换7665499749382713v 重建堆4965769749382713v 49与97交换9765764949382713v 重建堆C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针6597764949382713v 65与76交换76976

46、54949382713v 重建堆7697654949382713v 76与97交换9776654949382713C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针整个堆排序和重建堆的过程也是在数组中进行的其变化过程整个堆排序和重建堆的过程也是在数组中进行的其变化过程见下图所示。见下图所示。 初始012345678小头堆1338274976654997 初始012345678小头堆1338274976654997v堆排序中的数组变化堆排序中的数组变化过程过程v重建堆的数组变化重建堆的数组变化过程过程 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),是一个不稳定的排序方法。是一个不稳定的排序方法。C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针按递减序列堆排序的算法按递减序列堆排序的算法: :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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针1 1 指针与字符串指针与字符串(1)(1)1.1 1.1 字符串的表示形式字符串的表示形式v用用字符数组字符数组存放一个字符串，并输出该字符串。存放一个字符串，并输出该字符串。 main()ch

51、ar string =I love China!;printf(%sn,string);C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针1 1 指针与字符串指针与字符串(2)(2)1.1 1.1 字符串的表示形式字符串的表示形式( (续续) )v用用字符串指针字符串指针指向一个字符串指向一个字符串 main()char *string=I love China!;printf(%sn,string);C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针1 1 指针与字符串指针与字符串(3)(3)1.1 1.1 字符

52、串的表示形式字符串的表示形式( (续续) )例例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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针1 1 指针与字符串指针与字符串(4)(4)1.2 1.2 使用字符串指针变

53、量与字符数组的区别使用字符串指针变量与字符数组的区别字符数组由若干元素组成字符数组由若干元素组成，每个元素中放一，每个元素中放一个字符，个字符，而字符指针变量中存放的是地址而字符指针变量中存放的是地址（字（字符串的首地址）。符串的首地址）。赋值方式不同。赋值方式不同。对对字符数组字符数组只能对各个元素只能对各个元素赋值，赋值，不能用一个字符串给一个字符数组赋值不能用一个字符串给一个字符数组赋值，但对于但对于字符指针变量可以用一个字符串给它赋字符指针变量可以用一个字符串给它赋值值。char str14;str=“ I love China”;char *pstr;pstr=“ I love Ch

54、ina”;C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针1 1 指针与字符串指针与字符串(5)(5)1.2 1.2 使用字符串指针变量与字符数组的区别使用字符串指针变量与字符数组的区别( (续续) )例例2 2 分析下面程序的运行结果分析下面程序的运行结果 main() char *a=I Love China!; a=a+7; printf(“%sn,a);运行结果：运行结果：China!C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针1 1 指针与字符串指针与字符串(6)(6)1.2 1.2 使用字符串指

55、针变量与字符数组的区别使用字符串指针变量与字符数组的区别( (续续) )例例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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(1)(1)2.1 2.1 指针变量作为函数

56、参数指针变量作为函数参数指针变量作为函数参数指针变量作为函数参数，实参变量实参变量和和形参变量形参变量的的传递方式为传递方式为地址传递地址传递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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(2)(2)2.1 2.1 指针变量作为函数参数指针变量作为函数参数( (续续) )例例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语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指

58、针与函数指针与函数(3)(3)2.1 2.1 指针变量作为函数参数指针变量作为函数参数( (续续) )例例5 5 一个自然数是素数，且它的数字位置经过任一个自然数是素数，且它的数字位置经过任意对换后仍为素数，则称为意对换后仍为素数，则称为绝对素数绝对素数，例如，例如1313，试求所有两位绝对素数。试求所有两位绝对素数。解题思路解题思路使用哪种类型的程序结构？使用哪种类型的程序结构？给出一个数，如何求任意数字给出一个数，如何求任意数字位置对换后的数？位置对换后的数？如何判断一个数为素数？如何判断一个数为素数？C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指

59、针2 2 指针与函数指针与函数(4)(4)2.2 2.2 指向函数的指针变量指向函数的指针变量 在语言中，在语言中，一个函数占用一段连续的内存一个函数占用一段连续的内存区区，而，而函数名就是该函数所占内存区的首地址函数名就是该函数所占内存区的首地址。我们可以把函数的这个首地址我们可以把函数的这个首地址(或称入口地址或称入口地址)赋赋予一个指针变量，使该指针变量指向该函数。然予一个指针变量，使该指针变量指向该函数。然后通过指针变量就可以找到并调用这个函数。我后通过指针变量就可以找到并调用这个函数。我们把这种们把这种指向函数的指针变量指向函数的指针变量称为称为“函数指针变函数指针变量量”。C语言程

60、序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(5)(5)2.2 2.2 指向函数的指针变量指向函数的指针变量( (续续) )函数指针变量函数指针变量定义定义的一般形式为：的一般形式为：类型说明符类型说明符 ( (* *指针变量名指针变量名)();)();表示被指函表示被指函数的返回值数的返回值的类型的类型“* *”后面的变后面的变量是定义的指量是定义的指针变量针变量指针变量所指指针变量所指的是一个函数的是一个函数如：如：int (*pf)();C语言程序设计语言程序设计项目八项目八 优化学生成绩分析系统优化学生成绩分析系统-指针指针2 2 指针与函数指针与函数(6)(6)2.2 2.2 指向函数的指针变量指向函数的指针变量( (续续) )用函数指针变量用