Chap 11 指针进阶 11.1 布袋中的彩色球 11.2 解密藏头诗 11.3 学生信息管理的链表实现.

Presentation on theme: "Chap 11 指针进阶 11.1 布袋中的彩色球 11.2 解密藏头诗 11.3 学生信息管理的链表实现."— Presentation transcript:

1 Chap 11 指针进阶 11.1 布袋中的彩色球 11.2 解密藏头诗 11.3 学生信息管理的链表实现

2 本章要点 指针数组和指向指针的指针是如何被定义和使用的？ 指针如何作为函数的返回值？ 指向函数的指针的意义是什么？
什么是结构的递归定义，哪种应用需要这种定义方法？ 对链表这种数据结构，如何进行动态内存分配操作？ 如何建立单向链表并实现插入、删除以及查找操作？

3 11.1 布袋中的彩色球 11.1.1 程序解析 11.1.2 指针数组的概念 11.1.3 指向指针的指针
11.1 布袋中的彩色球 程序解析 指针数组的概念 指向指针的指针 用指针数组处理多个字符串 命令行参数

4 程序解析 例11-1 已知一个不透明的布袋里装有红、蓝、黄、绿、紫同样大小的圆球各一个，现从中一次抓出两个，问可能抓到的是什么颜色的球？

5 程序解析－例11-1 源程序 指针数组 char *color[5];
color[0] = “red”; color[1] = “blue”; … #include<stdio.h> int main(void) { char *color[5] = {"red", "blue", "yellow", "green", "purple"}; /* 初始化 */ int count = 0, i, j; for(i = 0; i <= 4; i++) /* i代表第一个球对应的颜色下标 */ for(j = i+1; j <= 4; j++) { /* j代表第二个球对应的颜色下标 */ /* 两个球不能同色 */ count ++; printf("%6d", count); printf("%10s %10s\n", color[i], color[j]); } return 0; 指针数组 red blue red yellow red green red purple blue yellow blue green blue purple 8 yellow green 9 yellow purple green purple

6 11.1.2 指针数组的概念 char *color[5]; 类型名 *数组名[数组长度] int a[5];
指针数组的概念 char *color[5]; 类型名 *数组名[数组长度] 数组元素是指针类型，用于存放内存地址 int a[5]; a是一个数组，它有5个元素 每个元素的类型都是整型 color是一个数组，它有5个元素 每个元素的类型都是字符指针

7 指针数组的概念 char *color[5] = {"red", "blue", "yellow", "green", "purple"};
每个元素的类型都是字符指针 数组元素可以处理字符串 对指针数组元素的操作相当于对同类型指针变量的操作 printf("%10s %10s\n", color[i], color[j]);

8 例11-2 使用指针数组输出5种颜色的英文名称 #include <stdio.h> int main(void)
{ int i; char *color[5] = {"red", "blue", "yellow", "green", "purple"}, *tmp; for(i = 0; i < 5; i++) /* 输出字符串的地址和内容*/ printf("%x, %s\n", color[i], color[i]); tmp = color[0]; /* 交换color[0]与color[4]*/ color[0] = color[4]; color[4] = tmp; printf("color[0]:%s, color[4]:%s\n", color[0], color[4]); return 0; } 420064, red 42005c, blue 420054, yellow 42004c, green 420044, purple color[0]:purple, color[4]:red

9 例11-2 图示 交换color[0]与color[4]的值

10 11.1.3 指向指针的指针－示例 例11-3 改写例11-1，用指向指针的指针实现。 指向指针的指针
指向指针的指针－示例 例11-3 改写例11-1，用指向指针的指针实现。 #include<stdio.h> int main(void) { char *color[5] = {"red", "blue", "yellow", "green", "purple"}; char **pc = color; int count = 0, i, j; for(i = 0; i <= 4; i++) for(j = i+1; j <= 4; j++) { count++; printf( "%6d", count ); printf( "%10s %10s\n", color[i], color[j] ); } return 0; 指向指针的指针 pc[i], pc[j] ); 或 *(pc + i), *(pc + j)

11 指向指针的指针－示例分析 char *color[5] = {"red", "blue", "yellow", "green", "purple"}; char **pc = color; printf( "%10s %10s\n", *(pc + i), *(pc + j) ); pc: color 或者&color[0] *pc: color[0]: "red" *(pc+i) : color[i] *color[0]: 'r' **pc: *color[0]: 'r'

12 指向指针的指针－定义 指向指针的指针（二级指针） 类型名 **变量名 int a = 10; int *pa = &a;
类型名 **变量名 int a = 10; int *pa = &a; int **ppa = &pa; &a pa a 10 &p ppa *pa *ppa **ppa

13 例11-4 int a = 10, b = 20, t; int *pa = &a, *pb = &b, *pt;
int **ppa = &pa, **ppb = &pb, **ppt; 例11-4 &a pa a 10 &pa ppa **ppa *pa &b pb b 20 &pb ppb **ppb *pb 操作(1)：ppt = ppb; ppb = ppa; ppa = ppt;

14 例11-4 int a = 10, b = 20, t; int *pa = &a, *pb = &b, *pt;
int **ppa = &pa, **ppb = &pb, **ppt; 例11-4 pa a ppa &a 10 &pb **ppb *pa &b pb b 20 &pa ppb **ppa *pb 操作(1)：ppt = ppb; ppb = ppa; ppa = ppt; 操作(2)：pt = pb; pb = pa; pa = pt; ?

15 例11-4 int a = 10, b = 20, t; int *pa = &a, *pb = &b, *pt;
int **ppa = &pa, **ppb = &pb, **ppt; 例11-4 pa a ppa &b 10 &pb **ppa *pb &a pb b 20 &pa ppb **ppb *pa 操作(1)：ppt = ppb; ppb = ppa; ppa = ppt; 操作(2)：pt = pb; pb = pa; pa = pt; 操作(3)：t = b; b = a; a = t;

16 例11-4 int a = 10, b = 20, t; int *pa = &a, *pb = &b, *pt;
int **ppa = &pa, **ppb = &pb, **ppt; 例11-4 pa a ppa &b 20 &pb **ppa *pb &a pb b 10 &pa ppb **ppb *pa 操作(1)：ppt = ppb; ppb = ppa; ppa = ppt; 操作(2)：pt = pb; pb = pa; pa = pt; 操作(3)：t = b; b = a; a = t;

17 11.1.4 用指针数组处理多个字符串 处理多个字符串 二维字符数组 指针数组 使用指针数组更节省内存空间
用指针数组处理多个字符串 处理多个字符串 二维字符数组 char ccolor[ ][7] = {"red", "blue", "yellow", "green", "purple"}; 指针数组 char *pcolor[ ] = {"red", "blue", "yellow", "green", "purple"}; 使用指针数组更节省内存空间

18 1. 用指针数组处理多个字符串－排序 例11-5 将5个字符串从小到大排序后输出。 #include <stdio.h>
int main(void) { int i; int a[5] = {6, 5, 2, 8, 1}; void fsort( int a[ ], int n ); fsort( a, 5 ); for(i = 0; i < 5; i++) printf("%d ", a[i]); return 0; } #include <stdio.h> int main(void) { int i; char *pcolor[5]={ "red", "blue", "yellow", "green", "purple" }; void fsort(char *color[ ], int n); fsort( pcolor, 5 ); for(i = 0; i < 5; i++) printf("%s ", pcolor[i]); return 0; }

19 例11-5 字符串排序 void fsort(char *color[ ], int n)
{ int k, j; char *temp; for(k = 1; k < n; k++) for(j = 0; j < n-k; j++) if(strcmp(color[j],color[j+1])>0){ temp = color[j]; color[j] = color[j+1]; color[j+1] = temp; } void fsort(int a[ ], int n) { int k, j; int temp; for(k = 1; k < n; k++) for(j = 0; j < n-k; j++) if(a[j] > a[j+1]){ temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; }

20 pcolor red\0 blue\0 yellow\0 green\0 purple\0 pcolor[0] pcolor[1] pcolor[2] pcolor[3] 排序前 pcolor[4] pcolor red\0 blue\0 yellow\0 green\0 purple\0 pcolor[0] pcolor[1] 排序后 pcolor[2] pcolor[3] pcolor[4]

21 2. 动态输入多个字符串－示例 用动态分配内存的方法处理多个字符串的输入示例
例11-6 输入一些球的颜色，以#作为输入结束标志，再输出这些颜色。 其中颜色数小于20，颜色的英文名称不超过10个字符。

22 请输入颜色名称，每行一个，#结束输入： red blue yellow # 你输入的颜色是：red blue yellow #include <stdio.h> #include<stdlib.h> #include<string.h> int main(void) { int i, n = 0; char *color[20], str[10]; printf("请输入颜色名称，每行一个，#结束输入：\n"); scanf("%s", str); while(str[0] != '#') { color[n] = (char *) malloc ( sizeof (char) * ( strlen(str) + 1 ) ); strcpy(color[n], str); n++; } printf("你输入的颜色是："); for(i = 0; i < n; i++) printf("%s ", color[i]); return 0; for( i=0; i<20; i++) color[i] = NULL; for( i=0; i<n; i++) free( color[i] );

23 3. 对指针数组的进一步讨论 char *color[ ] = {"red", "blue", "yellow", "green", "purple"}; color：二级指针(char **)，等于&color[0] color+2：指向color[2] *(color+2)和color[2]等价 color[0]：指向字符串"red"的首字符r color[0]+2：指向首字符r后的第2个字符d

24 对指针数组的进一步讨论 (1) color[k]*(color+k) printf("%s", color[2]);
(2) *(color[k]+j)  *(*(color+k)+j)  color[k][j] printf("%c %c", *(color[2]), *(color[2]+2)); printf("%c %c", color[2][0], color[2][2]);

25 11.1.5 命令行参数 C语言源程序经编译和连接处理，生成可执行程序后，才能运行。
命令行参数 C语言源程序经编译和连接处理，生成可执行程序后，才能运行。 在DOS环境的命令窗口中，输入可执行文件名，就以命令方式运行该程序。 输入命令时，在可执行文件（命令）名的后面可以跟一些参数，这些参数被称为命令行参数。 test world 命令名 命令行参数

26 命令行参数 命令名 参数1 参数2 … 参数n 命令名和各个参数之间用空格分隔，也可以没有参数
使用命令行的程序不能在编译器中执行，需要将源程序经编译、链接为相应的命令文件（一般以.exe为后缀），然后回到命令行状态，再在该状态下直接输入命令文件名。

27 带参数的main()函数 test world! Hello world!
#include <stdio.h> /* test.c */ int main(int argc, char *argv[ ]) { printf("Hello "); printf("%s", argv[1]); return 0; } argc: 2 *argv[ ]: {"test", "world!"} 第1个参数 argc 接收命令行参数(包括命令名)的个数 第2个参数 argv 接收以字符串常量形式存放的命令行参数(命令名本身也作为一个参数)

28 例10-7 输出命令行参数 例11-7 编写C程序echo，它的功能是将所有命令行参数在同一行上输出。
#include <stdio.h> int main(int argc, char *argv[ ]) { int k; for(k = 1; k < argc; k++) /* 从第1个命令行参数开始 */ printf("%s ", argv[k]); /* 打印命令行参数 */ printf("\n"); return 0; } 在命令行状态下输入： echo How are you? How are you?

29 11.2 解密藏头诗 程序解析 指针作为函数的返回值 指向函数的指针

30 11.2.1 程序解析－解密藏头诗 例11-8 输入一首藏头诗（假设只有4句），输出其真实含义。
程序解析－解密藏头诗 例11-8 输入一首藏头诗（假设只有4句），输出其真实含义。 藏头诗：将这首诗每一句的第一个字连起来，所组成的内容就是该诗的真正含义。

31 11.2.1 程序解析 请输入藏头诗： 一叶轻舟向东流， 帆梢轻握杨柳手， 风纤碧波微起舞， 顺水任从雅客悠。 一帆风顺
程序解析 #include <stdio.h> char *change(char s[ ][20], char t[ ]); int main(void) { int i; char s[4][20], t[10], *p; printf(“请输入藏头诗：\n”); for(i = 0; i < 4; i++) scanf("%s", s[i]); p = change(s, t); printf("%s\n", p); return 0; } char * change(char s[ ][20], char t[ ]) { int i; for(i= 0; i < 4; i++) { t[2*i] = s[i][0]; t[2*i+1] = s[i][1]; } t[2*i] = '\0'; return t; 函数的返回值是字符指针 printf("%s\n", change(s, t) ); 或 change(s, t); printf("%s\n", t);

32 11.2.2 指针作为函数的返回值 函数返回值的类型 函数的定义、调用方法与其他函数一样 整型、字符型、浮点型、结构类型
指针作为函数的返回值 函数返回值的类型 整型、字符型、浮点型、结构类型 指针（返回一个地址） 函数的定义、调用方法与其他函数一样

33 指针作为函数的返回值－例11-9 输入一个字符串和一个字符，如果该字符在字符串中，就从该字符首次出现的位置开始输出字符串中的字符。
要求定义函数match(s, ch)，在字符串s中查找字符ch，如果找到，返回第一次找到的该字符在字符串中的位置（地址）；否则，返回空指针NULL。 例如，输入字符r和字符串program后，输出rogram。

34 例11-9 源程序 字符指针p接收match返回的地址，从p指向的存储单元开始，连续输出其中的内容，直至'\0'为止。
例11-9 源程序 #include <stdio.h> char *match(char *s, char ch) { while(*s != '\0') if(*s == ch) return(s); /* 若找到字符ch，返回相应的地址 */ else s++; return(NULL); /* 没有找到ch，返回空指针 */ } int main(void ) { char ch, str[80], *p = NULL; printf(“Please Input the string:\n”); scanf("%s", str); getchar( ); ch = getchar( ); if( ( p = match(str, ch) ) != NULL ) printf("%s\n", p); else printf("Not Found\n"); return 0; Please Input the string: University v versity Please Input the string: school a Not Found 字符指针p接收match返回的地址，从p指向的存储单元开始，连续输出其中的内容，直至'\0'为止。

35 指针作为函数的返回值的进一步讨论 函数返回值的类型 函数的定义、调用方法与其他函数一样 进一步讨论 整型、字符型、浮点型、结构类型
指针（返回一个地址） 函数的定义、调用方法与其他函数一样 进一步讨论 定义函数时，可以： 动态分配内存 操作这些新分配的单元 返回新分配单元的地址 修改例11-8，采用动态分配内存的方法

36 例11.8 修改－动态分配内存 #include <stdio.h> #include <stdlib.h>
char *change_d(char s[ ][20]); int main(void) { int i; char s[4][20], *p = NULL; printf("请输入藏头诗：\n"); for(i = 0; i < 4; i++) scanf("%s", s[i]); p = change_d(s); printf("%s\n", p); free(p); return 0; } char * change_d(char s[ ][20]) { int i; char *head, *p; p = (char *) calloc(8, sizeof(char)); head = p; for(i= 0; i < 4; i++) { *(p++) = s[i][0]; *(p++) = s[i][1]; } *p = '\0'; return head;

37 11.2.3 指向函数的指针 每个函数都占用一段内存单元，有一个入口地址（起始地址） 函数名：函数的入口地址
指向函数的指针 每个函数都占用一段内存单元，有一个入口地址（起始地址） 函数名：函数的入口地址 函数指针：一个指针变量，接收函数的入口地址，让它指向函数 通过函数指针调用函数 做为函数的参数 指令1 指令2 指令3 … 指令n 入口地址

38 函数指针的定义和赋值 定义 类型名 (*变量名)( ); int (*funptr)( ); 赋值 funptr = fun;
类型名 (*变量名)( ); 所指向函数的返回值的类型 int (*funptr)( ); 定义一个函数指针funpt funpt指向一个返回值类型为int的函数 赋值 funptr = fun; 函数fun的入口地址赋给funptr funptr指向函数fun int fun(x ,y) { return x > y ? x : y; }

39 通过函数指针调用函数 int (*funptr)( ); funptr = fun; 调用函数 (*函数指针名)(参数表) 函数名
z = fun(3, 5); 函数指针 (*funptr)(3, 5); (*函数指针名)(参数表) int fun(x ,y) { return x > y ? x : y; }

40 函数指针做为函数的参数 实参：函数名或已赋值的函数指针 形参：函数指针，指向实参所代表函数的入口地址
例11-10 编写一个函数calc(f, a, b)，用梯形公式求函数f(x)在[a, b]上的数值积分。 然后调用calc(f, a, b)计算下列数值积分。 分析： 函数定义时，形参：函数指针f、积分区间上下限参数a，b 函数调用时，实参：被积函数的名称（或函数指针）和积分区间的上下限

41 例11-10 源程序 1: resule=0.5000 2: resule=0.6481 double f1 ( double x )
{ return (x*x); } double f2 ( double x ) { return (sin(x)/x); } double calc ( double (*f)(double), double a, double b ) { double z; z = (b-a)/2 * ( (*f)(a) + (*f)(b) ); /* 调用 f 指向的函数 */ return ( z ); } int main ( void ) { double result; result = calc(f1, 0.0, 1.0); /* 函数名f1作为函数calc的实参 */ printf("1: resule=%.4f\n", result); funp = f2; result = calc(funp, 1.0, 2.0); /* 函数指针funp作为函数calc的实参 */ printf("2: resule=%.4f\n", result); return 0; 1: resule=0.5000 2: resule=0.6481

42 11.3 学生信息管理的链表实现 程序解析 链表的概念 单向链表的常用操作

43 程序解析 head 9905 Qian 80 NULL 9901 Wang 80 Li 90 例11-11 建立一个学生成绩信息（包括学号、姓名、成绩）的单向链表，学生记录按学号由小到大顺序排列，要求实现对成绩信息的插入、修改、删除和遍历操作。 main InsertDoc DeleteDoc Print_Stu_Doc Create_Stu_Doc

44 例11-11 数据定义与函数声明 struct stud_node{ /*链表结点类型*/ int num; char name[20];
int score; struct stud_node *next; }; struct stud_node * Create_Stu_Doc(); /* 新建链表 */ struct stud_node * InsertDoc(struct stud_node * head, struct stud_node *stud); /* 插入 */ struct stud_node * DeleteDoc(struct stud_node * head, int num); /* 删除 */ void Print_Stu_Doc(struct stud_node * head); /* 遍历 */

45 11.3.2 链表的概念 一种动态存储分布的数据结构 若干个同一结构类型的“结点”依次串接而成 单向链表、双向链表 头指针 尾结点 结点
链表的概念 head 9903 Qian 80 NULL 9901 Wang 80 Li 90 一种动态存储分布的数据结构 若干个同一结构类型的“结点”依次串接而成 单向链表、双向链表 头指针 结点 尾结点

46 链表的概念－结点定义 struct stud_node{ int num; char name[20]; int score;
head 9905 Qian 80 NULL 9901 Wang 80 Li 90 struct stud_node{ int num; char name[20]; int score; struct stud_node *next; }; 结构的递归定义

47 链表的概念－与数组比较 数组 链表 事先定义固定长度的数组 在数组元素个数不确定时，可能会发生浪费内存空间的情况 动态存储分配的数据结构
根据需要动态开辟内存空间，比较方便地插入新元素（结点） 使用链表可以节省内存，提高操作效率

48 动态存储分配函数malloc() void *malloc(unsigned size)
若申请成功，则返回一个指向所分配内存空间的起始地址的指针 若申请不成功，则返回NULL（值为0） 返回值类型：(void *) 通用指针的一个重要用途 将malloc的返回值转换到特定指针类型，赋给一个指针

49 malloc()示例 int *ip = (int *) malloc( sizeof(int) ) struct student * p;
p = (struct student *) malloc(sizeof(struct student)); 调用malloc时，用 sizeof 计算存储块大小 虽然存储块是动态分配的，但它的大小在分配后也是确定的，不要越界使用。 p

50 动态存储释放函数free 当某个动态分配的存储块不再用时，要及时将它释放 void free(void *ptr)
free(ip); free(p); p

51 单向链表的常用操作 1. 链表的建立 2. 链表的遍历 3. 插入结点 4. 删除结点

52 1.链表的建立 struct stud_node *head, *tail, *p; head = tail = NULL;
size = sizeof(struct stud_node); p = (struct stud_node *) malloc(size); num name score next head p tail p tail

53 1.链表的建立

54 程序段 head = tail = NULL; scanf("%d%s%d", &num,name, &score);
while(num != 0){ p = (struct stud_node *) malloc(size); p->num = num; strcpy(p->name, name); p->score = score; p->next = NULL; if(head == NULL) head = p; else tail->next = p; tail = p; scanf("%d%s%d", &num, name, &score); } 程序段

55 2. 链表的遍历 ptr->num ptr->score ptr=ptr->next ptr ptr
head 9905 Qian 80 NULL 9901 Wang 80 Li 90 ptr ptr ptr->num ptr->score ptr=ptr->next for(ptr = head; ptr != NULL; ptr = ptr -> next) printf("%ld, %d", ptr -> num, ptr -> score);

56 链表的遍历－函数 void Print_Stu_Doc(struct stud_node * head) {
struct stud_node * ptr; if(head == NULL){ printf("\nNo Records\n"); return; } printf("\nThe Students' Records Are: \n"); printf(" Num Name Score\n"); for(ptr = head; ptr!=NULL; ptr = ptr->next) printf("%8d %20s %6d \n", ptr->num, ptr->name, ptr->score);

57 3. 插入结点 head ptr s s->next = ptr->next ptr->next = s 先连后断

58 3. 插入结点 head ptr s ptr->next = s s->next = ptr->next 行吗？

59 3. 插入结点 ptr->next = s s->next = ptr->next 行吗？ head ptr s
老大不高兴后果很严重

60 4. 删除结点 free(ptr2) ptr2=ptr1->next 先接后删 ptr1->next=ptr2->next
head ptr1 ptr2 head ptr1 ptr2 free(ptr2) 先接后删 ptr2=ptr1->next ptr1->next=ptr2->next