考场纪律&监考要求 课程主讲人和主持人要亲自参加监考。 考场<30人,要有1人监考；考场<100人,要有2人监考；考场>100人,要有3人监考。各考场学生按一定规则均分。 监考教师要提前10分钟到场，关闭手机，不得带资料或笔记本等并行处理工作。 监考教师如发现考生有违纪和作弊迹象，应立即口头警告予以纠正。如考试中出现违纪或作弊问题，应在考场记录中如实填写，并在考试后立即把考场记录和作弊的证据等材料交到考生所在系的教务办公室 。 学生缓考要提交缓考申请单，一律由学院审批；学院批准缓考会把缓考回执单转给任课教师。课程开考后递交的申请和病假条一律无效。

计算概论 第十九讲 链表 北京大学信息学院

计算概论 本讲内容 指针回顾 结构回顾 链表的基本概念 链表的操作 链表的应用

1. 指针回顾 内存是按地址编码的，访问内存的时候是按照其地址进行的。指针就是一个内存地址。我们可以根据指针来访问它所指向的内存。定义指针的时候可以指定它所指向的内存区域所对应的变量的类型。例如： int *pi; // 定义一个名为pi的指向整数类型变量的指针。 float *pf; // 定义一个名为pf的指向浮点类型变量的指针。 我们称pi, pf为指针变量，pi是一个整数指针，pf是浮点数指针。

定义各种类型的指针变量 定义一个指针变量： 其中的“类型” 是指针指向的变量的类型 类型 * 指针变量名 = 指针初值; 其中的“类型” 是指针指向的变量的类型 字符类型的指针变量 char *message; 指向结构类型的指针变量 struct list *next, *previous; 指针数组，数组元素是指向整数类型变量的指针 int *pointers[10]; NULL是一个特殊的指针（地址值），当一个指针的值为NULL时，我们称指针为一个空指针，它不指向任何变量（内存地址）。

指针相关的操作符 &求地址运算符 *指针运算符 若执行了p=&m，则 *p 与 m 等价，都代表变量m的存储单元 void main() { int m = 0; int n = 0; int *p; // 求m的地址赋值给变量p p = &m; // 给p所指向的变量赋值1 *p = 1; p = &n; *p = 2; // 读取p所指向的变量的值 m = *p; } &求地址运算符 *指针运算符 若执行了p=&m，则 *p 与 m 等价，都代表变量m的存储单元

指向结构的指针 当指针指向一个结构时，可用"指针->分量"或"(*指针).分量"形式访问结构的分量，例如 struct point { float x, y; } point1, point2; struct point * pc = &point1; // pc->x 等价与 point1.x 等价于 (*pc).x pc->x = 10; pc->y = 20; pc = &point2; (*pc).x = 100; (*pc).y = 200;

指针变量作为结构的分量 结构中的分量也可以是指针变量，可指向一块内存空间，例如： struct node { float x, y; int * px; } node1, node2; 此时，node1.px、node2.px分别是2个整型指针变量

2. 结构 把多个紧密关联的变量顺序组织在一起，定义成一个新的复合类型——结构类型 定义一个结构类型 结构分量的类型可以相同，也可不同 struct 结构类型名 { 类型1 分量名1; 类型2 分量名2; ...... }; 结构分量的类型可以相同，也可不同 同一个结构内的分量名不可相同

2. 结构 Why? 结构分量的类型不能是正在定义的结构类型，但可以是该结构类型的指针 struct student { int num; char name[12]; double score; struct student next; }; struct student { int num; char name[12]; double score; struct student *next; }; Why?

3. 链表的基本概念 数组：在定义时元素个数是确定的 动态数组：可以在程序运行时动态确定元素的个数（即根据需要申请相应的内存空间），但一旦确定元素个数后，是不能再变化的。 但元素个数是动态变化的呢？ 开始时是2个元素 一会儿后变成4个元素 再一会儿后变成3个元素 ……

3. 链表的基本概念 链表是一种常用的重要的数据结构，链表可以存放任意多个元素，并且其个数可以动态变化。 a1 a2 a3 an ∧ … header NULL 链表通常有一个“头指针”变量，上图中以header表示，它存放一个地址。该地址指向一个元素。链表中每个元素称为“结点”，每个结点都包括2个部分：一为所需存储的实际数据；二为下一个结点的地址。可以看出：header指向第一个元素，第一个元素指向第二个，…，直到最后一个元素，它不再指向其它元素，称为链表的“表尾”，其地址部分为“NULL”，链表到此结束。

3. 链表的基本概念 可以看出，链表中每个元素的存放地址在内存中是不需连续的。要找某一个元素，必须先找到上一个元素，通过它提供的下一元素的地址才能找到下一个元素。如果不提供“头指针”（header），则整个链表都无法访问。 由于链表的结点中，既有数据，又有地址，因此，用结构体来表示链表的结点，是最合适的。在这个结构体类型中，包含了存放实际数据的各种类型的数据分量，同时，还包含一个指针变量，其类型为该结构体类型本身，用于存放下一个结点的地址。

3. 链表的基本概念 结点类型 struct nodetype { elementtype data ; struct nodetype *next ; } ; 结点形式 data next 结点信息 下一结点地址 nodetype struct nodetype *header ; struct nodetype *p , *q; header … a1 a2 a3 an ∧ p q a2: ( *p ).data ; q: ( *p ).next ; a2: p->data ; q: p->next ; 记法:

4. 链表的操作：创建与遍历 #include <stdio.h> #include <string.h> 计算概论 4. 链表的操作：创建与遍历 #include <stdio.h> #include <string.h> struct student { int num; char name[12]; double score; struct student *next; }; int main() { struct student a, b, c, *header, *p; a.num = 111; strcpy(a.name, “Li”); a.score = 90.4; b.num = 222; strcpy(b.name, “Zh”); b.score = 80.0; c.num = 333; strcpy(c.name, “Wu”); c.score = 85.6; header = &a; a.next = &b; b.next = &c; c.next = NULL; … return 0; } … p = header; while(p!=NULL) { printf(“%d, %s, %f\n”, (*p).num, p->name, p->score); p = p->next; }

4. 链表的操作：结点定位 从链表中找出与给定条件相符的结点 struct student * locate_num(struct student *header, int num) //char *name { struct student *p; p = header; while(p!=NULL) if( (*p).num == num ) return p; //strcmp( (*p).name, name)==0 p = p->next; } return p; //此时p为NULL，即没有找到符合条件的结点

4. 链表的操作：结点插入与删除 一般插入 一般删除

4. 链表的操作：结点插入 a1 x header q 插入表头结点q q->next = header; header = q ; (b) 中间插入元素 ai-1 ai x p q 插入一般结点q q->next = p->next ; p->next = q ; (c) 表尾插入元素 an ∧ x q p

4. 链表的操作：结点删除 a1 header a2 q 删除表头结点q header = q->next ; ai-1 ai p q (b) 删除中间元素 ai+1 删除一般结点q p->next = q->next ; an ∧ an-1 q p (c) 删除表尾元素

4. 链表的操作：结点插入与删除 在结点插入和删除操作过程中，往往要利用结点定位函数： 插入：找到要在其后插入结点的结点 删除：找到要删除的结点及其前一个节点

4. 链表的操作：动态创建 struct student * create_link() { struct student *header,*p,*q; int num, n = 0; char name[12]; double score; p = q = (struct student *)malloc(sizeof(struct student)); header = NULL; scanf("%d %s %lf", &num, name, &score); while( num != 0 ) n++; p->num = num; strcpy(p->name, name); p->score = score; if( n == 1) header = p; else q->next = p; q = p; p = (struct student *)malloc(sizeof(struct student)); } q->next = NULL; free(p); return header; 输入学生的学号、姓名及成绩，当学号为0时，停止输入。

动态删除 struct student * delete_num(struct student *header , int num) { struct student *p,*q; if( header == NULL ) return header; p = header; while( (p!=NULL) && (p->num!=num) ) q = p; p = p->next; } if( p!=NULL && p->num == num) if( p == header ) header = p->next; else q->next = p->next; free(p); //根据具体情况，确定是否需要释放该删除节点的内存空间 return header; 找到符合条件的结点，将它从链表中删除，并返回表头。若没有找到，则什么也不做。

动态插入 将结点in插入到符合条件的结点后面，如果没有符合条件的结点，则插入到链表尾部 如果插入到符合条件的结点之前呢？ struct student * insert_num(struct student *header, int num, struct student *in) { struct student *p, *q; if( header == NULL ) header = in; in->next = NULL; return header; } p = header; while( (p!=NULL) && (p->num!=num) ) q = p; p = p->next; if( p!=NULL && p->num == num ) //找到符合条件的结点 in->next = p->next; p->next = in; else //q是链表最后一个结点 q->next = in; 将结点in插入到符合条件的结点后面，如果没有符合条件的结点，则插入到链表尾部 如果插入到符合条件的结点之前呢？

动态释放 ? 释放链表所占内存空间 free(p); p = p->next; void free_link(struct student *header) { struct student *p, *q; p = header; while( (p!=NULL) ) q = p; p = p->next; free(q); } ? free(p); p = p->next;

4. 链表的应用：多项式表示及加法 AH: 1 - 10x6 + 2x8 + 7x14 header BH: -x4 + 10x6 - 3x10 + 8x14 + 4x18 header CH: 1 – x4 + 2x8 - 3x10 header

4. 链表的应用：多项式表示及加法 struct item{ int coefficient; //系数 int power; //幂 struct item *next; };

链表的各种形式 简单链表 循环链表 双向链表 循环双向链表 header header NULL header header NULL ^ header

循环链表的应用：约瑟夫问题 有N个猴子围成一圈，每个猴子有一个编号，编号从1到N。打算从中选出一个大王。经过协商，决定选大王的规则如下：第一个猴子开始从1开始报数，报到M的猴子出列，然后下一个猴子再从1开始报数，最后剩下来的就是大王。 尝试不同的解决方法： 利用公式求解 利用数组求解 利用循环列表求解

双向链表的结点结构 //双向链表的结点结构 struct node{ elementtype data; struct node *pre; //前一结点 struct node *next; //后一结点 };

链表的各种形式：双向链表的插入与删除 双向链表 header 插入 删除

计算概论 小结 结构 指针 链表 基本概念 操作 应用 链表的各种形式