2.3 线性链表在线视频

同学们大家好

我是云南大学信息学院教师孔兵

今天这节课我们讨论线性表的非顺序映象实现方式

线性链表

利用非顺序映象实现线性表的特点是

借助指针来明示数据元素之间的关系

从图中可以看到，对于线性表中的每个数据元素

申请一个结点来存储它

为了描述数据元素之间前驱和后继的关系

每个结点附设一个指针

用这个指针指向存储该元素后继的结点

所以a1结点的指针指向a2结点

a2结点的指针指向a3结点

依次类推，直到an-1结点的指针指向an结点

an结点没有后继，其指针置空

附设一个头结点，头结点不存数据元素

头结点的指针指向a1结点

线性链表存储结构的定义主要就是定义结点的存储结构

其存储结构被定义为一个结构体

结构体中包含两个成员

一个是存储线性表中数据元素的成员data.

一个是指向其后继的指针next.

通过typedef给这个结构体取了一个类型名Lnode

声明了一个指向结构体的指针类型名linklist

下面我们看一下，基于这样的存储结构

一些基本操作的实现

首先看一下采用头插法创建单链表的操作

创建单链表涉及到的参数主要是有两个

一个是linklist类型的L,这是一个指向结构体的指针

创建好单链表以后，L指向链表的头结点

另外一个参数是n，

这个参数给出要创建的链表中数据元素的个数

如果要创建一个空链表，只需要调用时n对应的实参为0即可

这里通过图演示一下建立单链表的过程

单链表的创建，大致可以分为两步

第1步是创建一个头结点

用malloc函数申请一个Lnode类型的结点

让指针L指向它，结点不存数据元素

结点指针next置空

到此创建了只含有一个头结点的单链表

也可以看作是一个空表

随后进入一个循环，每次循环，生成一个结点

读入一个数据元素存入到结点成员data中

并且把该结点插入到链表的头结点之后

这就是所谓的头插法，每次生成一个新的结点之后

总是把它插入到头结点之后

总共循环n次，形成一个长度为n的单链表

在图中我们看一下第一次循环的演示

malloc申请一个结点，用指针p指向该结点

接着读入数据元素an，存入到这个结点的data中

随后把这个结点插入到头结点之后

这里插入主要是涉及到两个指针的赋值

p->next被赋值L->next，L->next被赋值p

让头结点的指针an这个结点，完成了第一个结点的插入

插入完成后，链表如箭头后面的样子

再看下次循环，申请一个结点

存入an-1，p指向这个结点

同样怎么样执行上述两条语句

p->next被赋值L->next

这样an-1结点的指针an结点

描述an-1的后继是an，L->next被赋值p

头结点的指针指向an-1结点

an-1结点插入到头结点之后

后续结点的插入过程和这个类似，多次循环

依次把包含数据元素的结点插入到单链表中

就获得了一个长度为n的，带头结点的单链表

大家要注意的是，头插法中

结点插入次序和线性表序列的次序是相反的

下面我们看一下程序实现

黄色部分的两个语句是建立头结点

申请头结点，指针L指向它，结点的next置空

下面的循环就是依次生成链表结点并插入到单链表中

结合图已经讲过，就不重复了

注意循环控制变量i是从n开始

主要是想说明首先创建的是链表中的第n个结点

也就是最后一个

下面我们讨论，在链式存储结的线性表中

如何在线性表的第i个位置插入一个数据元素的操作

前一节，我们讨论过基于线性表的顺序存储实现线性表插入操作

这里讨论基于线性链表实现插入操作

插入操作涉及的参数和上一节一样

对外的接口是统一，调用时没有什么明显的差异

涉及到的参数还是三个, 一个是要插入的线性表

一个是位置, 一个是要插入的元素

其含义和在顺序存储结构中讨论的是一样的

这里我们主要讨论在链式结构中

如何实现在线性表的第i个位置来插入一个数据元素e

就是说e应该插到序列中第ai-1之后，ai之前

在逻辑结构中e是ai-1的后继，是ai的前驱

从链表的图示中我们可以看到

ai-1结点的指针指向ai结点，指明ai-1的后继是ai

插入后，ai-1的后继是e, e的后继是ai

那么，按照关系描述的要求

我们需要生成一个结点存储e

ai-1结点的指针指向它，它指针指向ai结点

首先的问题就是要确定这个插入的位置

具体来说就是要找到线性表中的ai-1这个结点

寻找的方法是通过一个指针和一个计数器来实现的

首先，指针P被赋值L，让p指向链表头结点

计数器j赋值0，计数器j和指针p同步

用j来记录p所指结点的元素是线性序列中第几个元素

给出该元素他的位置。

在p指头结点

它并不是线性表的元素，所以j初值等于0

随后，用一个循环找ai-1这个结点

当j小于等于i-1的时候，执行循环

循环中做p被赋值p->next

p移动指向后继结点，++j计算器加1，同步位置

正常情况下，循环完成以后

j应该等于i-1，同时，p指向ai-1结点

找到这个位置以后的，插入操作就很简单了

首先调用malloc函数生成一个结点

指针s指向这个结点

把要插入的元素e存到结点的data中

随后，s->next=p->next

使e结点的指针指向它的后继ai结点

p->next赋值s，让ai-1结点的指针指向e结点

到此就完成了在线性表的第i个位置来插入一个数据元素e的操作

如图中最后的图所示

下面呢，看一下它的程序实现

在插入函数中，黄色这一块是寻找插入的位置

首先对指针和计数器初始化

随后循环，当p不为空，j

每次循环把指针向后移动，同时计数器加1

正常情况下，循环结束以后

p指向序列中第i-1个位置的结点

绿色一句是对插入位置合法性的一个判定

如果非p为真，是说明插入位置i给的偏大

插入位置大于n+1。j>i-1这个条件是说插入位置给小了

小于1。这两种情况都说明，给的插入位置非法

那么就return error, 返回一个错误

后面的几个语句就是申请结点

插入到链表中的个语句

前面结合图形已经说过，这里不再重复

前面我们讨论过的单链表都是带头结点的单链表

如果链表不带头结点是否可以呢

就存储线性表，描述数据元素之间关系来说

没有什么问题

如果不带头结点

指向链表的指针L就直接指向链表中存储a1的结点

这个结点一般叫做首元结点

不带头结点，在实现一些某些基本操作时有些不方便

比如说插入操作

我们知道插入操作合法的位置是1到n+1

如果插入位置是2~n+1

那么，插入的过程和带头结点的单链表没有什么太大的差异

但如果插入位置是1的时候

需要做特殊处理

如果插入的位置是1，那么插入以后

包含e的这个结点将成为新的首元结点

指向链表的指针L要重新赋值

让它指向新的首元结点

下面我们看一下它的具体实现

在不带头结点的单链表中进行插入

程序前面操作的部分和带头结点的，差异不大

主要区别是在黄色这部分的代码

如果插入位置i=1，需要做特殊处理，s-> next=L

让新插入结点的指针指向链表原来的首元结点

L=s，让指向链表的指针L指向新的首元结点

就是s所指的这个结点

其他情况和前面带头结点的类似

线性表的删除操作也有类似的问题

当要删除的位置是位置1的元素时

也需要进行特殊处理

从这呢，我们可以看出

单链表中带头结点的好处

单链表带头结点以后

由于第1个元素结点的位置被存放在头结点的指针域中

所以在链表第1个位置上的操作

和在表中其他位置上的操作就一致了

不需要对他进行特殊处理

这一节的最后，我们简单看一下单链表的删除

单链表的删除操作也涉及到三个参数

删除的对象L, 要删除元素在线性表中的位置i,

引用e把这个要删元素带回来

删除操作中，首先仍然是要找到

线性表中第i-1这个位置的结点

这是要删除元素的ai的前驱

找到这个结点以后，q=p->next;

让q指向要删除的结点. e=q->data;

把要删除的元素赋值个引用e，

p->next= q->next; ai删除以后

ai-1的后继变成了ai+1，这里让ai-1的指针指向ai+1

指明它新后继是ai+1

随后通过Free（q） 把删除的这个结点释放掉

回收它的存储空间，这样就完成了线性表中一个元素的删除

注意：在线性表插入和删除的时候

不要使链表断开

好，同学们这一节我们就讲到这儿

下节课再见