第15讲 链表 计算机与通信工程学院.

Presentation on theme: "第15讲 链表 计算机与通信工程学院."— Presentation transcript:

1 第15讲 链表 计算机与通信工程学院

2 第15讲 链表 本讲主要内容 链表概述 链表的概念 链表的特点； 定义链表结构； 链表的基本操作 链表结点的插入 链表结点的删除
链表结点的查找 Josephus问题

3 第15讲 链表 教学目标 了解链表的概念、特点。 能熟练定义链表的结点结构，熟悉建立链表的一般过程。
掌握链表结点的插入、删除、查找等基本操作方法。 能使用链表进行简单的数据管理。

4 一、链表概述 链表的概念 链表是结构体最重要的应用，它是一种非固定长度的数据结构，是一种动态存储技术，它能够根据数据的结构特点和数量使用内存，尤其适用于数据个数可变的数据存储。 使用链表存储数据的原理与数组不同，它不需要事先说明要存储的数据数量，系统也不会提前为它准备大的存储空间，而是当需要存储数据时，通过动态内存分配函数malloc()或calloc()向系统获取一定数量的内存，用于数据存储。需要多少，就申请多少，系统就分配多少。

5 一、链表概述 实例：使用链表存储表13-1中前3个学生数据。
构成链表的每一个独立的内存段称为一个链表结点，结点中存储数据的部分称为结点数据域，存储下一个结点地址的部分称为结点指针域，指向第一个结点的指针称为链表的头指针。

6 一、链表概述 链表的特点 链表作为一种动态的数据结构，具有如下特点： ⑴ 链表中的结点具有完全相同的结构，每一个存储一个独立的结构体数据；
⑵ 链表的结点由系统随机分配，它们在内存中的位置可能是相邻的，也可能是不相邻的，结点之间的联系是通过指针域实现的； ⑶ 为了能准确的定位第一个结点，每个链表要有一个表头指针，从第一个结点开始，沿指针链能遍历链表中的所有结点； ⑷ 链表中的结点是在需要时用calloc()申请的，当不再需要时，应有free()函数释放所占用的内存段。 ⑸ 一个链表不需要事先说明它要包括的结点数目，在需要存储新的数据时，就可增加结点，需要删除数据时，就减少结点，链表结点是动态变化的。

7 一、链表概述 定义链表结构 要定义一个链表结点的结构，需要包括两个方面： 一方面定义数据存储所对应的各个成员；
另一方面定义指向其他结点的指针成员。 例如，假若要用链表逐个存储一批整数， 其结点结构可定义如下： struct node { int data; struct node *next; /* 指向struct node类型的指针 */ };

8 一、链表概述 定义链表结构 前面实例(使用链表存储表13-1中前3个学生数据) 的结点结构可定义如下：
struct student { int num； /* 学号 */ char name[20]； /* 姓名 */ char sex； /* 性别 */ int age； /* 年龄 */ float score； /* 成绩 */ char addr； /* 地址 */ struct student *next；/* 指向struct student类型的指针 */ }； 其中，num、name、sex、age、score、addr是结点数据域的成员，next是结点指针域的成员。

9 一、链表概述 生成一个链表结点的一般过程：
⑴ 向系统申请一个内存段，其大小由结点的数据类型决定。例如，calloc(1,sizeof(struct node)) 。 ⑵ p=(结点数据类型 *)calloc(1,sizeof(结点数据类型)); 例如，可使用如下形式申请一个struct node类型的结点： p=(struct node *)calloc(1,sizeof(struct node)); ⑶ 为申请得到的结点添加数据。

10 二、链表的基本操作 链表结点的插入 在链表中插入结点，就是把一个新结点连接到链表中。通常有两种情况：
一种情况是在空链表中插入一个结点，此时，插入的结点既是链表的第一个结点，也是链表的最后一个结点； 另一种情况是在链表的p结点之后插入一个新结点。

11 new=(struct node *)calloc(1,sizeof(struct node))；
二、链表的基本操作 在空链表中插入一个结点 空链表就是头指针head为空的链表。 ⑴ 用如下语句申请一个new结点： new=(struct node *)calloc(1,sizeof(struct node))； ⑵ 为p结点填充数据：将要存储的数据对应传给p结点数据域的各个成员； ⑶ 修改有关指针的指向： ①将head指向new结点。 ②将new的next成员置空，使new结点成为链表的最后一个结点； …… struct node *new； new=(struct node *)calloc(1,sizeof(struct node))； new->data=m； head=new； head->next=NULL； 　……

12 二、链表的基本操作 在head链表的p结点之后插入一个结点
设head链表和要插入结点new如下图所示。要将new结点插入在p结点之后，就是将new结点变成结点C的下一个结点，而使new的下一个结点成为结点D。 对new和p结点的指针域进行如下操作： ⑴ 使new的指针域存储结点D的首地址： new->next=p->next； ⑵ 把new的首地址存储到结点p的指针域中： p->next=new；

13 二、链表的基本操作 如下是在head链表的p结点之后插入值为m的结点的函数insert()，函数的返回值是链表的头指针：
#include "malloc.h" #include "stdio.h" struct student *insert(struct node *head,struct node *p,int m) {struct node *new； new=(struct node *)calloc(1,sizeof(struct node))； new->data=m； if(head==NULL) { head=new； head->next=NULL；} else { new->next=p->next； p->next=new； } return(head)； }

14 二、链表的基本操作 例14-1 用插入结点的方法建立下图所示的学生成绩链表，链表head有10个结点，每个结点存储一个学生的学号和学习成绩数据。 struct s_node *creat_node(void) {struct s_node *p； float score； fflush(stdin)； p=(struct s_node *)calloc(1, sizeof(struct s_node))； gets(p->num)； scanf("%f",&score)； p->score=score； p->next=NULL； return(p)； } #include "stdio.h" #define N 5 struct s_node {char num[4]； float score； struct s_node *next； }； main() { struct s_node *creat_node(void)； struct s_node *creat_list(int n)； void out_list(struct s_node *head)； struct s_node *head=NULL； head=creat_list(N)； out_list(head)； }

15 二、链表的基本操作 struct s_node *creat_list(int n)
{struct s_node *new,*p； struct s_node *head； int i； if(n>=1) { new=creat_node()； head=new； p=new；} for(i=2；i<=n；i++) p->next=new； return(head)； else return(NULL)； } void out_list(struct s_node *head) {struct s_node *p； if(head!=NULL) { p=head； while(p!=NULL) { printf("%s %f\n",p->num, p->score)； p=p->next； } }

16 二、链表的基本操作 链表结点的删除 在链表中删除结点一般有两个过程： 一是把指定的结点从链表中拿下来，它需要通过修改有关结点的指针域来完成；
二是释放该结点使用的内存空间，它需要使用free()函数来实现。

17 二、链表的基本操作 上图是一个head链表，删除p结点的过程如下：
⑴ 若p结点是链表的第一个结点，则将p指针域的地址保存到head中，使p的后继结点成为head链表的第一个结点，然后转步骤⑶。修改指针的操作如下： head=head->next；或 head=p->next； ⑵ 若p结点不是链表的第一个结点，则首先从head开始，找到p结点的前一个结点q，然后使q的指针域存储p的后继结点的地址，这样沿链表的指针访问链表中的结点时，p结点将不会被访问到，亦即p结点从链表head中被删除了。链表指针的修改操作如下： q->next=p->next； ⑶ 释放p结点使用的内存空间。操作如下：free(p)；

18 二、链表的基本操作 如下是在head链表中删除p结点的delete()函数： #include "stdio.h"
void delete(struct node *head,struct node *p) {struct node *q； q=head； if(p==head) head=head->next； /* p是第一个结点是，修改链表的头指针 */ else { while(q->next!=p) /* 找到p的前一个结点的地址 */ q=q->next； q->next=p->next； /* 删除p结点 */ } free(p)； /* 释放p结点占用的内存 */

19 二、链表的基本操作 链表结点的查找 在链表中进行查找，就是从链表的第一个结点开始，沿着指针链，用查找值与链表结点逐个比较的过程。找到符合要求的结点之后，停止查找过程，返回相应结点的指针，否则返回一个空指针。如下是在head链表中查找data值为m的结点的过程，其中p为struct node型指针： ⑴ p=head； ⑵ 当p≠NULL时，若p->data==m，则找到要求结点，查找结束，返回结点地址p；否则，执行下一步⑶；当p== NULL时，链表中不存在要找的结点，查找结束，返回空指针NULL； ⑶ p=p->next；/* 将p指向下一个结点 */ ⑷ 重复⑵、⑶步骤。

20 二、链表的基本操作 #include "stdio.h"
链表结点的查找函数find()设计如下： #include "stdio.h" struct node *find(struct node *head,int m) {struct node *p=head； while(p!=NULL&&p->data!=m) p=p->next； if(p==NULL) return(NULL) else return(p)； }

21 二、链表的基本操作 例14-2 对如下图所示的head链表，删除其值是x的结点。具体要求如下：⑴ 输出被删除结点的值；⑵ 当指定值结点不存在时，显示一个提示信息；⑶ x的值由键盘输入。 该问题的关键点有两点： 第一是查找data等于x的结点p； 第二是删除p结点。 需要注意的是，p结点删除之后，要将其使用的内存释放。

22 二、链表的基本操作 #include "stdio.h" struct node { int data；
struct node *next； }； struct node *find_x( struct node *head,int x) {struct node *p,*q； p=q=head； while(p!=NULL&&p->data!=x) { q=p； p=p->next； } if(p==NULL) return(NULL)； else return(q)； void delete_p( struct node *head, struct node *p) {struct node *q； if(p==NULL) { printf("no found\n")； return； } if(p==head) { head=p->next； q=p；} else { q=p->next； p->next=q->next；} printf("\ndelete: %d\n", q->data)； free(q)； }

23 二、链表的基本操作 struct node *creat_number(int n) {int i；
struct node *head,*new,*p； if(n>=1) { new=(struct node*)malloc( sizeof(struct node))； new->data=1； new->next=NULL； head=new； p=new；} for(i=2；i<=n；i++) new->data=i； p->next=new； if(n>=1) return(head)； else return(NULL)； } main() {int n,x； struct node *head,*p； printf("Enter n,x: ")； scanf("%d,%d",&n,&x)； head=creat_number(n)； p=find_x(head,x)； delete_p(head,p)； }

24 二、链表的基本操作 Josephus问题 例14-3 Josephus问题：有n个人围成一圈，从1开始顺序编号到n，现在从1号开始顺时针从1数数，数到m者自动出列，然后从下一个人开始重新数数，仍然每次数到m者自动出列。请给出这n个人出列的顺序。 我们用下图所示的链表解决Josephus问题，head链表从第一个结点开始依次存储n个人的编号，但与其他链表不同的是，它最后一个结点的指针域没有存储空指针，而是存放了第一个结点的地址，使得链表在链路上形成了一个环，这样的链表称为循环链表。

25 二、链表的基本操作 #include "stdio.h" #include "alloc.h" struct circle
{int number； struct circle *next； }； struct circle *creat_j(int n) {int i； struct circle *head,*new,*p； new=(struct circle*)malloc( sizeof(struct circle))； new->number=1； head=new； p=new； for(i=2；i<=n；i++) { new=(struct circle*)malloc( new->number=i； p->next=new； p=new； } p->next=head； return(head)； } void josephus( struct circle *head,int m) {struct circle *p,*q,*temp； int i=1； q=p=head； while(p!=p->next) { if(i==m) { printf("%5d", p->number)； q->next=p->next； temp=p； p=p->next； free(temp)； i=1；} else { q=p； i++；} } printf("%5d\n",p->number)；

26 二、链表的基本操作 main() {int n,m； struct circle *head； printf("Enter n,m: ")；
scanf("%d,%d",&n,&m)； head=creat_j(n)； josephus(head,m)； } 如下是程序的一个执行结果： Enter n,m: 10,5

27 链表-小结 1．链表是一种动态的数据存储结构，它的每一个结点都是结构体类型的数据，同一个链表中的所有结点具有相同的数据类型。
2．一个链表结点分为数据域和指针域两部分，数据域存储需要处理的数据，指针域存储下一个结点的位置。链表结点在物理位置上没有相邻性，结点之间的联系通过指针实现。 3．对链表施行的基本操作有插入结点、删除结点、查找结点、结点数据读写等，向链表插入结点前必须先用动态内存分配函数获得结点，从链表中删除的结点要进行释放操作。 4．从空链表开始不断地插入结点即可建立一个链表，任何一个链表必须有一个头指针，只有通过头指针才能访问链表结点。当一个链表结点的指针域为空时，表明是链表的最后一个结点，当最后一个结点的指针指向开头结点时，便形成一个循环链表。