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种颜色的英文单词按一定顺序排列，输入任意一个颜色的英文单词，从已有颜色中查找并输出该颜色的位置值，若没有找到，则输出“Not Found”。

5 11.1.1 程序解析 运行结果1 Input a color:yellow position:3 运行结果2 指针数组
程序解析 运行结果1 Input a color:yellow position:3 运行结果2 Input a color:purple Not Found #include<stdio.h> #include<string.h> int main(void) { int i; char *color[5] = {“red”, ”blue”, ”yellow”, ”green”, ”black” }; char str[20]; printf(“Input a color:”); scanf(“%s”, str); for(i = 0; i < 5; i++) if(strcmp(str, color[i]) == 0) /* 比较颜色是否相同 */ break; if(i < 5) printf(“position:%d\n”, i+1); else printf(“Not Found\n”); return 0; } 指针数组

6 11.1.2 指针数组的概念 C语言中的数组可以是任何类型，如果数组的各个元素都是指针类型，用于存放内存地址，那么这个数组就是指针数组。
指针数组的概念 C语言中的数组可以是任何类型，如果数组的各个元素都是指针类型，用于存放内存地址，那么这个数组就是指针数组。 一维指针数组定义的一般格式为： 类型名 *数组名[数组长度]

7 11.1.2 指针数组的概念 int a[10]; char *color[5]; a是一个数组，它有10个元素 每个元素的类型都是整型
指针数组的概念 int a[10]; a是一个数组，它有10个元素 每个元素的类型都是整型 char *color[5]; color是一个数组，它有5个元素 每个元素的类型都是字符指针

8 11.1.2 指针数组的概念 对指针数组元素的操作和对同类型指针变量的操作相同
指针数组的概念 char *color[5] = {"red", "blue", "yellow", "green", "black" }; color是一个数组，它有5个元素 每个元素的类型都是字符指针 数组元素可以处理字符串 对指针数组元素的操作: printf("%s %x\n", color[i], color[i]); 对指针数组元素的操作和对同类型指针变量的操作相同

9 11.1.2 指针数组的概念 继续执行： char * tmp; tmp = color[0]; color[0] = color[4];
指针数组的概念 继续执行： char * tmp; tmp = color[0]; color[0] = color[4]; color[4] = tmp; color[0]与color[4]交换后的情况 指针数组操作时： 可以直接对数组元素进行赋值（地址值）和引用 tmp=color[0]; 也可以间接访问和操作数组元素所指向的单元内容 strcpy(color[0], “purple");

10 11.1.3 指向指针的指针 C语言中，指向指针的指针(二级指针)一般定义为： 类型名 **变量名 int **pp = &p; &a p
指向指针的指针 C语言中，指向指针的指针(二级指针)一般定义为： 类型名 **变量名 int a = 10; int *p = &a; int **pp = &p; &a p a 10 &p pp *p *pp **pp

11 【例11-2】 int a = 10, b = 20, t; int *pa = &a, *pb = &b, *pt;
int **ppa = &pa, **ppb = &pb, **ppt; 【例11-2】 pa a ppa &a 10 &pb **ppb *pa &b pb b 20 &pa ppb **ppa *pb &a pa a 10 &pa ppa **ppa *pa &b pb b 20 &pb ppb **ppb *pb pa a ppa &b 10 &pb **ppa *pb &a pb b 20 &pa ppb **ppb *pa 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;

12 11.1.3 指向指针的指针 【例11-3】改写例11-1，用指向指针的指针实现。 指向指针的指针 使用指向指针的指针 操作数据
指向指针的指针 【例11-3】改写例11-1，用指向指针的指针实现。 #include<stdio.h> #include<string.h> int main(void) { int i; char *color[5] = {“red”, ”blue”, ”yellow”, ”green”, ”black”}; / char **pc; /* 定义二级指针变量 */ char str[20]; pc = color; /* 二级指针赋值 */ printf(“Input a color:”); scanf(“%s”, str); for(i = 0; i < 5; i++) if(strcmp(str, *(pc+i)) == 0) /* 比较颜色是否相同 */ break; if(i < 5) printf(“position:%d\n”, i+1); else printf(“Not Found\n”); return 0; } 指向指针的指针 使用指向指针的指针 操作数据

13 11.1.3 指向指针的指针 【例11-3】改写例11-1，用指向指针的指针实现。 pc  color &color[0]
指向指针的指针 【例11-3】改写例11-1，用指向指针的指针实现。 pc  color &color[0] *pc  color[0] *(pc+i)color[i] **pc*(*pc)*color[0] : ‘r’

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

15 11.1.4 用指针数组处理多个字符串 2．用指针数组操作多个字符串 【例11-4】将5个字符串从小到大排序后输出。
用指针数组处理多个字符串 2．用指针数组操作多个字符串 【例11-4】将5个字符串从小到大排序后输出。 #include <string.h> void main( ) { int i; char *pcolor[ ] ={ “red”, ”blue”, ”yellow”, ”green”, ”black”}; void fsort(char *color[ ], int n); fsort(pcolor, 5); for(i = 0; i < 5; i++) printf("%s ", pcolor[i]); } void main( ) { 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]); }

16 11.1.4 用指针数组处理多个字符串 void fsort(char *color[ ], int n) { int k, j;
用指针数组处理多个字符串 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; }

17 用指针数组处理多个字符串 排序前 排序后

18 11.1.4 用指针数组处理多个字符串 3．动态输入多个字符串
用指针数组处理多个字符串 3．动态输入多个字符串 例11-5 输入一些有关颜色的单词，每行一个，以#作为输入结束标志，再按输入的相反次序输出这些单词。其中单词数小于20，每个单词不超过15个字母（用动态分配内存的方法处理多个字符串的输入）。

19 采用动态分配内存的方法处理多个字符串的输入的优点在于，能够根据实际输入数据的多少来申请和分配内存空间，从而提高了内存的使用率。
#include <stdio.h> #include<stdlib.h> #include<string.h> int main(void) { int i, n = 0; char *color[20], str[15]; scanf("%s", str); while(str[0] != '#') { color[n] = (char *)malloc(sizeof(char)*(strlen(str)+1)); /* 动态分配 */ strcpy(color[n], str); /* 将输入的字符串赋值给动态内存单元 */ n++; } for(i = n-1; i >= 0; i--) printf("%s ", color[i]); return 0; 采用动态分配内存的方法处理多个字符串的输入的优点在于，能够根据实际输入数据的多少来申请和分配内存空间，从而提高了内存的使用率。 运行结果: red blue yellow # yellow blue red

20 11.1.4 用指针数组处理多个字符串 4．对指针数组的进一步讨论
用指针数组处理多个字符串 4．对指针数组的进一步讨论 char *color[ ] = {“red”, ”blue”, ”yellow”, ”green”, ”black”}; 数组名color代表数组首元素color[0]的地址，是指向指针的指针(二级指针) color+2指向color[2] ，*(color+2)和color[2]等价 color[0]指向字符串"red"的首字符r，color[0]+2指向首字符r后的第2个字符d

21 11.1.4 用指针数组处理多个字符串 4．对指针数组的进一步讨论 color[k]*(color+k)
用指针数组处理多个字符串 4．对指针数组的进一步讨论 color[k]*(color+k) printf("%s", color[2]); printf("%s", *(color+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]);

22 用指针数组处理多个字符串 例11-6 解密藏头诗。所谓藏头诗，就是将一首诗每一句的第一个字连起来，所组成的内容就是该诗的真正含义。编写程序，输出一首藏头诗的真实含义。 一叶轻舟向东流， 帆梢轻握杨柳手， 风纤碧波微起舞， 顺水任从雅客悠。

23 11.1.4 用指针数组处理多个字符串 #include <stdio.h>
用指针数组处理多个字符串 #include <stdio.h> char *change(char s[][20]); int main(void) { int i; char *poem[4] = { "一叶轻舟向东流，", "帆梢轻握杨柳手，", "风纤碧波微起舞，", "顺水任从雅客悠。"}; /* 指针数组初始化 */ char mean[10]; for(i = 0; i<4; i++){ /* 每行取第1个汉字存入mean */ mean[2 * i] = *(poem[i]); mean[2 * i + 1] = *(poem[i] + 1); } mean[2 * i] = ’\0’; printf("%s\n", mean); /* 输出结果 */ return 0;

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

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

26 *11.1.5 命令行参数 带参数的main()函数格式： int main(int argc, char *argv[ ])
* 命令行参数 带参数的main()函数格式： int main(int argc, char *argv[ ]) { ...... } 第1个参数argc接收命令行参数（包括命令名）的个数；第2个参数argv接收以字符串常量形式存放的命令行参数（包括命令名本身也作为一个参数）。

27 *11.1.5 命令行参数 【例11-7】编写C程序echo，它的功能是将所有命令行参数在同一行上输出。
* 命令行参数 【例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?

28 11.2 字符定位 程序解析 指针作为函数的返回值 * 指向函数的指针

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

30 11.2.1 程序解析 运行结果1 Please Input the string: University v versity 运行结果2
school a Not Found 程序解析 #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) /* 调用函数match() */ printf("%s\n", p); else printf("Not Found\n"); return 0; 函数match()返回一个地址（指针）。 在主函数中，用字符指针p接收match()返回的地址，从p指向的存储单元开始，连续输出其中的内容，直至'\0'为止。

31 11.2.2 指针作为函数的返回值 函数返回值的类型 在C语言中，函数返回值也可以是指针，定义和调用这类函数的方法与其他函数是一样的。 整型
指针作为函数的返回值 函数返回值的类型 整型 浮点型 字符型 结构类型 指针（返回一个地址） 在C语言中，函数返回值也可以是指针，定义和调用这类函数的方法与其他函数是一样的。

32 11.2.2 指针作为函数的返回值 思考：在例11-8中，如果将str的定义及相应的数据输入都放在函数match() 中，结果会如何？
指针作为函数的返回值 思考：在例11-8中，如果将str的定义及相应的数据输入都放在函数match() 中，结果会如何？ char * match() { char ch, str[80],*s=str; /* 定义局部字符数组 */ printf("Please Input the string:\n"); /* 输入 */ scanf("%s", str); getchar(); ch = getchar(); while(*s != '\0') if(*s == ch) return s; /* 返回局部字符数组地址 */ else s++; return(NULL); } 不能返回在函数内部定义的局部数据对象的地址，这是因为所有的局部数据对象在函数返回时就会消亡，其值不再有效 返回指针的函数一般都返回全局数据对象或主调函数中数据对象的地址

33 *11.2.3 指向函数的指针 每个函数都占用一段内存单元，它们有一个入口地址（起始地址） 在C语言中，函数名代表函数的入口地址。
* 指向函数的指针 每个函数都占用一段内存单元，它们有一个入口地址（起始地址） 在C语言中，函数名代表函数的入口地址。 我们可以定义一个指针变量，接收函数的入口地址，让它指向函数，这就是指向函数的指针，也称为函数指针。 通过函数指针可以调用函数，它也可以作为函数的参数。 指令1 指令2 指令3 … 指令n 入口地址

34 *11.2.3 指向函数的指针 1.函数指针的定义 函数指针定义的一般格式为： 类型名 (*变量名)( 参数类型表); 例如：
* 指向函数的指针 1.函数指针的定义 函数指针定义的一般格式为： 类型名 (*变量名)( 参数类型表); 类型名指定函数返回值的类型，变量名是指向函数的指针变量的名称。 例如： int (*funptr)( int, int); 定义一个函数指针funptr，它可以指向有两个整型参数且返回值类型为int的函数。

35 *11.2.3 指向函数的指针 2.通过函数指针调用函数 通过函数指针调用函数的一般格式为： (*函数指针名)(参数表) 例如：
* 指向函数的指针 2.通过函数指针调用函数 通过函数指针调用函数的一般格式为： (*函数指针名)(参数表) 例如： int fun(int x, int y); int (*funptr)(int, int); funptr = fun; (*funptr)(3 , 5);

36 * 指向函数的指针 3.函数指针作为函数的参数 C语言的函数调用中，函数名或已赋值的函数指针也能作为实参，此时，形参就是函数指针，它指向实参所代表函数的入口地址。 例如： f(int (*funptr)(int, int)) {…} void main() { … int (*funptr)(int, int); funptr = fun; f( funptr ); … }

37 *11.2.3 指向函数的指针 【例11-9】编写一个函数calc(f, a, b)，用梯形公式求函数f(x)在[a, b]上的数值积分。
* 指向函数的指针 【例11-9】编写一个函数calc(f, a, b)，用梯形公式求函数f(x)在[a, b]上的数值积分。 然后调用该函数计算下列数值积分。（函数指针作为函数参数示例） 分析：calc()是一个通用函数，用梯形公式求解数值积分。它和被积函数f(x)以及积分区间[a, b]有关，相应的形参包括函数指针、积分区间上下限参数。在函数调用时，把被积函数的名称（或函数指针）和积分区间的上下限作为实参。

38 *11.2.3 指向函数的指针 运行结果 1: resule=0.5000 2: resule=0.6481
* 指向函数的指针 /* 计算数值积分（函数指针作为函数参数示例） */ int main(void) { double result; double (*funp)(double); result = calc(f1, 0.0, 1.0); /* 函数名f1作为函数calc的实参 */ printf("1: resule=%.4f\n", result); funp = f2; /* 对函数指针funp赋值 */ result = calc(funp, 1.0, 2.0); /* 函数指针funp作为函数calc的实参 */ printf("2: resule=%.4f\n", result); return 0; } /* 函数指针funp作为函数的形参 */ double calc(double (*funp)(double), double a, double b) { double z; z = (b-a)/2 * ((*funp)(a) + (*funp)(b)); /* 调用funp指向的函数 */ return(z); 运行结果 1: resule=0.5000 2: resule=0.6481

39 11.3 用链表构建学生信息库 程序解析 链表的概念 单向链表的常用操作

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

41 11.3.1 程序解析 struct stud_node{ /*链表结点类型*/ int num; char name[20];
程序解析 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); /* 遍历 */

42 链表的概念 链表是一种常见而重要的动态存储分布的数据结构。它由若干个同一结构类型的“结点”依次串接而成。链表分单向链表和双向链表。 头指针 结点 尾结点 头结点

43 11.3.2 链表的概念 通常使用结构来定义单向链表结点的数据类型： struct stud_node{ int num;
链表的概念 通常使用结构来定义单向链表结点的数据类型： struct stud_node{ int num; char name[20]; int score; struct stud_node *next; }; 结构的递归定义

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

45 11.3.2 链表的概念 动态分配相关函数 void *malloc(unsigned size) void free(void *ptr)
链表的概念 动态分配相关函数 void *malloc(unsigned size) 功能：在内存的动态存贮区中分配一块长度为size的连续空间。 返回值：指针，存放被分配内存的起始地址。若未申请到空间，则返回 NULL( 0 )。 例如：(int *) malloc(sizeof(int)) (struct student *) malloc(sizeof(struct student)) void free(void *ptr) 功能：释放由malloc()申请的动态内存空间，ptr存放该空间的首地址。 返回值：无。 例如：free(p);

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

47 单向链表的常用操作 1. 链表的建立

48 11.3.3 单向链表的常用操作 1. 链表的建立 头部插入法： p->next=head; head=p; 尾部插入
单向链表的常用操作 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); } 头部插入法： p->next=head; head=p; 尾部插入

49 单向链表的常用操作 2. 链表的遍历 for(ptr = head; ptr!=NULL; ptr = ptr->next) printf("%d\t%s\t%d\n", ptr->num, ptr->name, ptr->score);

50 11.3.3 单向链表的常用操作 先连: s->next = ptr->next; 后断: ptr->next = s;
单向链表的常用操作 3. 插入结点 head ptr s 先连: s->next = ptr->next; 后断: ptr->next = s;

51 11.3.3 单向链表的常用操作 4. 删除结点 head ptr1 ptr2 head ptr1 ptr2
单向链表的常用操作 4. 删除结点 head ptr1 ptr2 head ptr1 ptr2 ptr2=ptr1->next; 先接:ptr1->next=ptr2->next; ptr1->next = ptr1->next->next; 后删:free(ptr2);

52 本章总结 指针数组 指针与函数 单向链表 能够熟练掌握指针数组的操作与应用 能够熟练处理与操作函数与指针的各种关系
能够掌握单向链表的基本操作 指针数组 指针数组概念与应用 指向指针的指针（二级指针） 命令行参数 指针与函数 指针作为函数的返回值 函数指针 单向链表 链表的概念 结点的结构定义与动态分配 链表的基本操作（建立、遍历、插入、删除）