PowerPoint 演示文稿

Transcription

1 第 12 章再谈指针 本章的基本内容是 : 指针与数组 指针与结构体 动态存储分配 由于指针可以直接对内存进行操作, 所以指针的功能非常 强大 正确灵活地使用指针可以有效地表示复杂的数据结 构, 并可动态分配内存空间, 提高程序的运行效率

2 任务 12.1 判断回文 问题 输入一个字符串, 判断该字符串是否为回文 ( 首尾对称的字句, 例如 abcba abba 均为回文 ) 要求用指针实现 想法 设两个指针变量 p 和 q, 其中 p 指向串的首部,q 指向串的尾部,p 从前向后,q 从后向前, 依次取出字符进行匹配, 直到 p 和 q 相遇, 如果匹配不成功则说明不是回文 算法 设函数 TurnString 实现判断回文, 其算法描述如下 : 输入 : 字符串 str 功能 : 判断回文输出 : 如果是回文, 则返回 1, 否则返回 0 step1: 指针 p 指向字符串 str 的首部, 指针 q 指向字符串 str 的尾部 ; step2: 重复执行下述操作, 直到 p 和 q 相遇 : step2.1: 如果 p 所指字符不等于 q 所指字符, 则 str 不是回文, 返回 0; step2.2: p++; q--; step3: str 是回文, 返回 1;

3 12.1 指针与数组 指向一维数组的指针 对一维数组元素的访问共有三种方式 : 1. 通过下标访问数组元素 : int a[10]; for (int i = 0; i < 10; i++) a[i] = i ; 2. 通过地址访问数组元素 int a[10]; for (int i = 0; i < 10; i++) *(a + i) = i ; 元素值 a[0] a[1] a[i-1] a[i] i 个元素 地址 a a + i

4 12.1 指针与数组 指向一维数组的指针 对一维数组元素的访问共有三种方式 : 3. 通过指针访问数组元素 : int a[10]; int *p = a ; for (int i = 0; i < 10; i++) *(p + i) = i ; p a i 个元素 p + i a[0] a[1] a[i-1] a[i]

5 12.1 指针与数组 p++ 自增运算要比 p+i 算术运算快得多, 因此其执行效率比地址 方式高 int a[10]; int *p = a ; for (int i = 0; p < (a + 10); i++, p++) *p = i ; // 表达式 3 是逗号表达式 a[9] 循环结束时 p a + 10 可能存储其他数据 a[9] p p a[1] a[0] 4 个字节 循环开始时 p a a[1] a[0]

6 12.1 指针与数组 例 12.1 在一维数组 r[n] 中查找最大值元素 要求用指针实现 #include <stdio.h> #define N 5 int main( ) int a[n], max; int *p = a; printf(" 请输入 %d 个整数 :", N) ; for (int i = 0; i < N; i++) scanf("%d", &a[i]) ; for (max = *p, p = a + 1 ; p < (a + N); p++) if (max < *p) max = *p ; printf(" 最大值为 :%d\n", max); return 0 ;

7 12.1 指针与数组 指向二维数组的指针 二维数组是一维数组的推广, 即可以把二维数组的每一行看成是一个一维数组, 其中每个数组元素是一个一维数组 行指针 地址常量 地址常量 列指针 元素指针 a *(a + 0) *(a + 0) + 2 a[0] a[0][0] a[0][1] a[0][2] a[0][3] a + 1 *(a + 1) *(a + 1) + 4 a[1] a[1][0] a[1][1] a[1][2] a[1][3] a + 2 *(a + 2) *(a + 2) + 3 a[2] a[2][0] a[2][1] a[2][2] a[2][3]

8 12.1 指针与数组 通过指针访问二维数组的不同形式 形式 性质 含义 a 行指针 二维数组名, 指向一维数组 a[0], 相当于 &a[0][0] a + i 行指针 指向一维数组 a[i], 相当于 &a[i][0] *a 列指针 即 *(a + 0), 指向第 0 行第 0 列, 相当于 &a[0][0] *(a + i) 列指针 指向第 i 行第 0 列, 相当于 &a[i][0] *(a + i) + j 元素指针 指向第 i 行第 j 列, 相当于 &a[i][j] int a[3][4]; int *p = a; int a[3][4]; int *p = a[0]; // 编译错误, 无法实现类型转换 int a[3][4]; int *p = &a[0][0];

9 12.1 指针与数组 指向二维数组的指针 二维数组元素的访问可以有三种方式 : 1. 通过下标访问数组元素 int a[3][4] ; for(int i = 0; i < 3; i++) for(int j = 0; j < 4; j++) a[i][j] = i + j ; int a[3][4] ; for(int i = 0; i < 3; i++) for(int j = 0; j < 4; j++) *(*(a + i) + j) = i + j ; 2. 通过地址访问数组元素 对于二维数组元素 a[i][j], [ ] 实际上是变址运算符, 即将元素 a[i][j] 的存储地址转换为 a[i] +j

10 12.1 指针与数组 指向二维数组的指针 3. 通过指针访问数组元素 可以定义一个指针指向二维数组的起始地址, 然后通过这个指针变量依次访问数组元素 int a[3][4] ; int *p = &a[0][0] ; for(int i = 0; i < 3; i++) for(int j = 0; j < 4; j++) *(p++) = i + j ; // 相当于 *p = i + j; p++;

11 12.1 指针与数组 例 12.2 求二维数组 r[m][n] 的最大值元素 要求用指针实现 #include <stdio.h> int main( ) int a[10][10], max, m, n; int *p = &a[0][0]; printf(" 请输入二维数组的行数和列数 :") ; scanf("%d%d", &m, &n) ; printf(" 请输入 %d 个整数 :", m * n) ; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) scanf("%d", &a[i][j]) ; max = *p; for (p = &a[0][1]; p < *(a + m - 1) + n ; p++) if (max < *p) max = *p ; printf(" 最大值是 :%d\n", max) ; return 0;

12 指针数组 12.1 指针与数组 指针数组 数组元素是指针 语法 定义一维指针数组的一般形式如下: 指针定义符基类型 * 数组名 [ 数组长度 ] ; 数组 数组元素为指针 指针指向的数据类型 语义 定义一个指针数组变量, 数组元素为指向基类型的指针

13 12.1 指针与数组 char *str[3] = "Red", "Green", "Blue" ; 指针数组 str str[0] str[1] str[2] 字符串 R e d \0 G r e e n \0 B l u e \0

14 12.1 指针与数组 例 12.3 求 N 个字符串中值最大的字符串 要求用指针实现 #include <stdio.h> #include <string.h> #define N 5 int main( ) char *str[n] = "Red", "Green", "Blue", "Yellow", "Black"; int index = 0; for (int i = 1; i < N; i++) if (strcmp(str[i], str[index]) > 0) index = i; printf(" 最大的字符串是 %s\n", str[index]); return 0;

15 解决任务 12.1 的程序 #include <stdio.h> #include <string.h> int TurnString(char str[ ]); int main( ) char str[80]; printf(" 请输入字符串 :"); scanf("%s", str); if (TurnString(str)) printf(" 该字符串是回文!\n"); else printf(" 该字符串不是回文!\n"); return 0; int TurnString(char str[ ]) char *p = str ; char *q = str + strlen(str) - 1; for ( ; p < q; p++, q--) if (*p!= *q) return 0; return 1;

16 任务 12.2 统计入学成绩 ( 函数版 ) 问题 某大学的博士入学考试科目为外语和两门专业课, 对于每个考生, 输入各科考试成绩, 并计算总分 要求用函数实现 想法 输入一个考生的各项信息, 再计算总分 算法 设函数 AddMarks 计算一个考生的总分, 算法如下 : 输入 : 一个考生的成绩信息功能 : 计算总分输出 : 该生的总分 step1: 输入一个考生的各项信息 ; step2: sum = 外语成绩 + 专业课 1 成绩 + 专业课 2 成绩 ; step3: 输出 sum;

17 12.2 指针与结构体 指向结构体的指针 结构体指针 指向结构体变量的指针 1. 结构体指针的定义 语法 声明结构体指针的一般形式如下 : 指针定义符结构体类型 * 指针变量名 ; 基类型为结构体指针 其中, 结构体类型是一个已经定义或正在定义的结构体类型 ; 指针变量名是一个合法的标识符 语义 定义一个指针指向结构体类型

18 12.2 指针与结构体 指向结构体的指针 定义一个结构体指针后, 需要将该指针与一个结构体变量的地址绑定, 例如, 如下语句声明并初始化了一个指向结构体的指针 p struct DateType int year, month, day ; ; struct DateType birthday = 1968, 3, 26 ; struct DateType *p = &birthday; p birthday

19 12.2 指针与结构体 指向结构体的指针 2. 通过指针访问结构体成员 语法 通过指针访问结构体成员的一般形式如下 : (* 指针 ). 成员 其中, * 指针 一定要用括号括起来, 因为成员运算符. 的优先级高于间接引用运算符 * 的优先级 指针 -> 成员指针结构体 结构体的某个成员 语义 通过结构体指针引用结构体变量的某个具体成员

20 12.2 指针与结构体 指向结构体的指针 struct DateType int year, month, day ; ; struct DateType birthday = 1968, 3, 26 ; struct DateType *p = &birthday; printf("%4d-%2d-%2d\n", p->year, p->month, p->day);

21 12.2 指针与结构体 指向结构体的指针 结构体类型可以嵌套定义, 在引用结构体成员时需要注意使用合适的运算符 struct DateType int year, month, day ; ; struct StudentType char name[10]; struct DateType birthday; ; struct StudentType stu = " 周思言 ", 1997, 1, 4; struct StudentType *p = &stu; printf("%s 的生日是 %d 月 %d 日 \n",p->name,p->birthday.month,p->birthday.day);

22 12.2 指针与结构体 结构体指针作为函数参数 将结构体变量传递给函数, 可以有以下三种方法 : (1) 形参是结构体成员, 实参是对应结构体成员的值, 参数传递是将结构体成员的值传递给形参 (2) 形参是结构体变量, 实参是结构体变量的值, 参数传递是将结构体变量的值传递给形参 (3) 形参是指向结构体类型的指针, 实参是结构体变量的地址或指向结构体变量的指针, 参数传递是将结构体变量的首地址传递给形参 前两种方法属于值传递方式, 结构体规模较大时, 空间和时间的开销很大, 一般较少使用 下面介绍第 3 种方法

23 12.2 指针与结构体 例 12.4 将输入的日期按下列格式之一输出 :1. 中文 ( 中国 ) 格式 ;2. 中文 ( 台湾 ) 格式 ;3. 英语 ( 美国 ) 格式 ;4. 英语 ( 英国 ) 格式 要求用函数实现 #include <stdio.h> struct DateType int year, month, day ; ; void FormatDay(struct DateType *p); int main( ) struct DateType date ; printf(" 请输入一个日期, 分别对应年 月 日 :") ; scanf("%d%d%d", &date.year, &date.month, &date.day) ; FormatDay(&date); return 0 ;

24 12.2 指针与结构体 void FormatDay(struct DateType *p) int select; printf("1. 中文 ( 中国 ) 格式 2. 中文 ( 台湾 ) 格式 \n") ; printf("3. 英语 ( 美国 ) 格式 4. 英语 ( 英国 ) 格式 \n") ; printf("5. 其他格式 \n 请输入对应数字 :\n") ; scanf("%d", &select) ; switch (select) case 1: printf(" 中国格式 :%d-%d-%d\n", p->year, p->month, p->day); break ; case 2: printf(" 台湾格式 :%d/%d/%d\n", p->year, p->month, p->day); break ; case 3: printf(" 美国格式 :%2d/%2d/%d\n", p->month, p->day, p->year); break ; case 4: printf(" 英国格式 :%2d/%2d/%d\n", p->day, p->month, p->year); break ; default: printf(" 其他格式 :%d-%d-%d\n", p->year, p->month, p->day); break ; return;

25 printf(" 请输入考生外语成绩 :"); 解决任务 scanf("%lf", 12.2 的程序 &stu.foreign); printf(" 请输入专业课 1 成绩 :"); scanf("%lf", &stu.spec1); #include<stdio.h> printf(" 请输入专业课 2 成绩 :"); struct StudentType scanf("%lf", &stu.spec2); sum = AddMarks(&stu); char no[10] ; printf("%s 的总分是 %5.1f\n", stu.name, sum); char name[10] ; return 0; double foreign ; double spec1 ; double spec2 ; ; double AddMarks(struct StudentType *p); int main( ) struct StudentType stu; double sum; printf(" 请输入考生考号 :"); scanf("%s", stu.no); printf(" 请输入考生姓名 :"); scanf("%s", stu.name); double AddMarks(struct StudentType *p) double sum; sum = p->foreign + p->spec1 + p->spec2; return sum;

26 任务 12.3 进制转换 问题 将十进制整数转换为任意 r 进制整数 想法 十进制整数转换为 r 进制整数的规则是 : 除基取余, 逆序排列, 即将十进制整数逐次除以 r 进制的基数 r, 直到商为 0, 然后将得到的余数逆序排列 算法 设函数 Transform 实现进制转换, 其算法描述如下 : 输入 : 十进制整数 A, 转换的进制数 r 功能 : 将十进制整数转换为 r 进制整数输出 : 转换后的 r 进制整数 step 1: 重复下述操作直到 A 为 0: step1.1: B = A % r; step1.2: 保存 B; step1.3: A = A / r; step2: 逆序输出得到的 B 值 ; 如何保存 B 的值? 能够确定 r 进制数的位数吗?

27 12.3 动态存储分配 静态存储分配与动态存储分配 静态存储分配 : 在编译时为变量分配内存空间, 并且一经分配就始终占有固定的存储单元, 直到该变量退出其作用域 动态存储分配 : 在程序运行期间根据实际需要随时申请内存, 并在不需要时释放 C 语言中的动态存储分配是通过指针实现的

28 12.3 动态存储分配 申请和释放存储空间 1. 通用指针 可以指向任何类型的指针 语法 定义通用指针的一般形式如下 : 指针定义符 void * 指针变量名 ; 通用指针 语义 定义一个通用指针

29 12.3 动态存储分配 申请和释放存储空间 void *general_ptr = NULL ; int *int_ptr, num = 10 ; double *double_ptr, radius = 2.5 ; general_ptr = &num ; int_ptr = (int *) general_ptr ; general_ptr = &radius ; double_ptr = (double *) general_ptr ; general_ptr 10 num general_ptr 2.5 radius (int *) (double *) int_ptr (a) general_ptr 指向 int 型变量 double_ptr (b) general_ptr 指向 double 型变量

30 12.3 动态存储分配 申请和释放存储空间 2. 申请存储空间 函数原型 malloc 函数的原型如下 : void *malloc(unsigned int size) ; 通用指针 以字节为单位 功能 申请分配 size 字节的内存单元, 但不清空该内存单元 返回值 如果分配成功, 则返回这段内存空间的起始地址, 否则返回 NULL 一般在调用 malloc 函数后紧跟一条 if 语句判断内存分配是否成功

31 12.3 动态存储分配 申请和释放存储空间 int *p = NULL ; p = (int *)malloc(sizeof(int)) ; if (p ==NULL) printf(" 申请空间操作失败 ") ; p 随机数 sizeof(int)

32 12.3 动态存储分配 申请和释放存储空间 3. 释放存储空间 在程序的执行过程中, 如果不断地动态申请存储空间, 使用完时却不及时返还给内存, 必然会造成可用内存空间减少, 造成 内存泄露 动态申请的存储空间要及时释放 函数原型 free 函数的原型如下 : void free(void *block) ; 通用指针 指针变量 功能 释放动态申请的内存空间, 该内存空间的起始地址是 block

33 12.3 动态存储分配 申请和释放存储空间 int *p = NULL ; p = (int *)malloc(sizeof(int)) ; *p = 10 ; free(p) ; 指针 p 仍然存在 p 10 只释放这个存储单元

34 例 12.5 求任意 N 个字符串中值最大的字符串 要求使用动态存储分配 #include <stdio.h> #include <string.h> #include <malloc.h> #define N 5 int main( ) char *str[n] ; int index, i; 12.3 动态存储分配 for (index = 0, i = 1; i < N; i++) if (strcmp(str[i], str[index]) > 0) index = i; printf(" 最大的字符串是 %s\n", str[index]); for (i = 0; i < N; i++) free(str[i]); return 0; printf(" 请输入 %d 个字符串, 每个字符串以回车结束 :\n", N); for (i = 0; i < N; i++) str[i] = (char *)malloc(80); gets(str[i]);

35 解决任务 12.3 的程序 #include <stdio.h> #include <malloc.h> struct Node int data; struct Node *next; ; struct Node *Transform(int A, int r); void PrintLink(struct Node *first); int main( ) int A, r; struct Node *first; printf(" 请输入一个十进制整数 :"); scanf("%d", &A); printf(" 请输入转换进制的基数 :"); scanf("%d", &r); first = Transform(A, r); printf(" 十进制整数 %d 转换为 %d 进制整数 ", A, r); PrintLink(first); return 0;

36 struct Node *Transform(int A, int r) 解决任务 12.3 的程序 struct Node *first, *s; int B; first = (struct Node *)malloc(sizeof(struct Node)); first->next = NULL; while (A!= 0) B = A % r; A = A / r; s = (struct Node *)malloc(sizeof(struct Node)); s->data = B; s->next = first->next; first->next = s; return first; void PrintLink(struct Node *first) struct Node *p = first->next; if (first->next == NULL) printf("0\n"); return; while (p!= NULL) printf("%d", p->data); p = p->next; printf("\n"); return;

37 12.4 程序设计实例 实例 1 发纸牌 问题 假设纸牌的花色有梅花 方块 红桃和黑桃, 纸牌的点数有 J Q K A, 要求根据用户输入的纸牌张数 n, 随机发 n 张纸牌 实例 2 约瑟夫环问题 问题 约瑟夫环 (Josephus) 问题由古罗马史学家约瑟夫提出, 他参加并记录了公元 66~70 年犹太人反抗罗马的起义 约瑟夫作为一个将军, 设法守住了裘达伯特城达 47 天之久, 在城市沦陷之后, 他和 40 名死硬的将士在附近的一个洞穴中避难 在那里, 这些叛乱者坚持 要投降毋宁死 于是, 约瑟夫建议每个人轮流杀死另一个人, 而这个顺序是由抽签决定的, 约瑟夫有预谋地抓到了最后一签, 活了下来并投降了罗马 请设计程序实现约瑟夫环问题