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

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

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

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

程序解析－例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; 指针数组 1 red blue 2 red yellow 3 red green 4 red purple 5 blue yellow 6 blue green 7 blue purple 8 yellow green 9 yellow purple 10 green purple

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

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

例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

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

11.1.3 指向指针的指针－示例 例11-3 改写例11-1，用指向指针的指针实现。 指向指针的指针 11.1.3 指向指针的指针－示例 例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)

指向指针的指针－示例分析 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'

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

例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;

例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; ?

例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;

例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;

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

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; }

例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; }

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]

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

请输入颜色名称，每行一个，#结束输入： 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] );

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

对指针数组的进一步讨论 (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]);

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

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

带参数的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 接收以字符串常量形式存放的命令行参数(命令名本身也作为一个参数)

例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?

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

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

11.2.1 程序解析 请输入藏头诗： 一叶轻舟向东流， 帆梢轻握杨柳手， 风纤碧波微起舞， 顺水任从雅客悠。 一帆风顺 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);

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

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

例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'为止。

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

例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;

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

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

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

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

例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

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

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

例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); /* 遍历 */

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

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

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

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

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

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

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

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

1.链表的建立

程序段 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); } 程序段

2. 链表的遍历 ptr->num ptr->score ptr=ptr->next ptr ptr head 9905 Qian 80 NULL 9901 Wang 80 9902 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);

链表的遍历－函数 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);

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

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

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

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