大家好
数据结构与算法这一讲
我们继续学习第二章线性表
今天我们学习线性表当中的
链接结构
也就是链表
链表呢它是通过指针
来表达线性表的数据之间的
逻辑关系的
除了这个data数据域以外呢
我们还需要一个next域
它是指向它的后继元素的
这样的一个存储地址
链表根据它的链接形式
以及指针的多少
我们可以分为单链 双链和循环链
简单的单链呢
我们在学程序设计语言的时候
可能也学过这样的指针
这里面的单链
那时候的实现呢
往往都是把head指针呢
就是直接指向整个链表里面的
第一个元素
如果是一个空表呢
那就是head直接等于空
在数据结构里面
我们引入一个带头结点的单链
这个结点是跟我们表里面的
其他元素的类型是一样
它的一个特点呢
就是这里面的数据域
是没有意义的
整个第一个元素呢
它是head所指向的next
然后 我们如果是个空表
不能说head等于空
因为head是永远不会为空的
应该判断head的next域
是指向空
在这种带头结点的情况
其实我们在表达
当前这个元素的时候
往往是用它的前驱结点来表示的
这样的话
我们在很多操作中
就非常的便捷
我们来看单链的结点类型
在定义中呢
我们除了data数据域以外呢
我有一个指向我整个这个链的结点
同类型的这么一个指针
通过这个next指针域呢
把这个单链里面的结点
给它关联起来
我们来看这个单链的定义
除了我们线性表里面
所定义的那些增删查改的
这些函数以外
我还有head和tail
这两个变量
来维持单链里面的头和尾
这样的结点
我还有一个函数呢
是指定了这么一个下标位置
然后呢
我找到它相应的结点的指针
我们来看查找单链表里面
第i个元素算法
这个算法呢
其实就对应于我们顺序表
也就是数组里面
对第i个下标元素来进行定位
那这个i呢
它的编号也是从0到n-1
这个定位过程呢
我首先是设置一个变量count=0
然后我对它进行计数
如果是i=-1
其实呢 我们的定位的意思
是当前整个这个链表里面的
第一个元素之前的那个位置
那也就是说
对于插入的情况
我要求是插入到整个线性表的头
作为第一个元素
这种情况呢
我们输入的一个参数呢
就是i=-1
这种情况我们是返回的
整个这个线性表里面的
它的虚的头结点
其他的情况呢
我们先从线性表里面
第一个有效元素出发
那也就是从这个虚的头结点的
下一个结点来出发
我们设为p
然后当这个p不空的时候
以及它的计数还没有到达
你所指定的这个i的时候
我们就是让p=next p
然后再往下面接着数
如果是定位到了这样的一个元素
那我们就返回相应的结点p
我们再来看
单链的插入
如果我是在当前结点12之前呢
插入一个元素
首先我要创建一个新的元素
然后呢我再把这个新元素10
它的后继和前驱呢
都给它拉上链
那就插入到这个表里面了
我们看这个算法的实现
这个算法里面呢
是要求在第i个下标位呢
插入一个元素
我给的值是value
首先寻找这个i下标
它的前驱结点
我们给set Posn
这个参数呢
是设为i-1
如果是找不到这样合法的位置呢
我们就返回假
找到了以后呢
我们就先new出一个结点q
然后把这个结点q
它的值设为value
它的next域呢
我们设为p的next
其实也就是我们待插入的
第i个结点
然后我们还要做一下判断
看看p它是不是在尾部
如果p在尾部呢
其实相当于
你刚才传入的这个参数i呢
是等于n
也就是说你在整个这个链表的
最后一位呢进行插入
这种情况呢
我们就需要把这个链表的尾指针tail
设为刚插入的那个结点q
然后返回真
单链的删除
我们是首先呢要定位
你待删的这个结点
这个定位过程
可能是根据值或者是根据下标
来定位的
然后呢 我们把这个结点呢
从单链里面脱离下来
最后再释放它相应的空间
我们来看
删除的这么一个示意
首先呢
我这个待删结点是x
我也是通过定位的算法
然后我找到它的前驱p
这个定位的过程呢
也是我们从虚的头结点开始
然后逐个去找
看到p的next域
它如果还不是x呢
就继续往下找
一直找到正好p是x的前驱为止
我们在删除的时候呢
我先把这个p它的next
给它记录在变量q里面
也就是待删的这个x
然后我们让p的next域
直接跨过q
然后指向q的下一位
那就把这个x给剥离出来了
然后我们free（q）
就完成了删除操作
我们来看一下算法本身
这个算法呢
也是根据下标位置来定位的
我们也是要设置
当前待删的这个下标i
它的前驱
我先找到这个前驱p
如果这个p是非法的
那我就返回假
否则我就继续操作
我让这个q是等于p的next
也就是q定位为我们的x
如果q是尾部的这个结点
那我们就让这个tail指针是等于p
而且让p的next域指为空
这个是非常重要的
我们保证整个链呢
它的最后一个结点的next域是空
在我们控制对单链的
一些操作的时候
我们往往都是通过最后那个结点
它指向空
来停止这样的一个
对单链的一个遍历
否则我们就让p的next域
指向q的next域
这样就把这个q结点呢
给它剥离出来了
然后我们delete q
并且返回真
我们再来看单链上的运算
对于一个单链上头的结点
我们都是先要定位它
然后再进行相应的操作
这个定位的过程
往往都是从头结点开始
然后在里面顺序的找
这个过程是需要大O（n）的时间
插入和删除本身
其实很简单
都是大O（1）的时间
进行这些链的局部的指针维护
就可以
但是总体的代价呢
我们还是大O（n）的
双链是为了更方便找前驱
而产生的
当然它也带来了
维护的时候其他的一些麻烦
也就是我们插入删除的时候呢
除了这样的一个next域
我同时要维护prev这个域
我们来看一下
双链它的类型的定义
除了这个data域以外呢
我们还有指向下一个结点的next域
以及指向前驱的prev域
其他的情况就是类似的实现了
我们注意
双链的这个插入过程
我们在双链里面呢
我表示这个结点的时候
我只需要是定位到
当前结点就行
因为它找前驱是非常方便的
在插入的时候
我首先定位到p
然后我再new出一个新结点
这个新结点呢
它的next域指向p的next
然后它的prev指向p本身
然后接着我再去
对这个链表里面的其他的指针
进行维护
我把p的next域指向q
原来那个p的next
它的前驱呢
我们再指向q
因为原来p的那个next
已经被q所继承了
所以我们其实就是新结点q
它的next域指向了q本身
删除的过程更简单一些
我们删除的时候
先定位到当前待删的这个p
然后我把p它的prev前驱
这个结点它的next域
指向p的next
然后把p的next结点的
那个prev域呢
指向p的prev
这样的话呢
就把p安全的剥离了这个双链
然后我们把p结点再delete掉就可以
循环链呢
它是把head和tail
首尾给它连起来
如果是循环的双链
我们tail的next域指向head
然后head的prev域指向tail
循环链它并没有增加特别的开销
使得我们在某些运算里面呢
是更加方便
我们从这个循环连里面
任何一个结点出发
我都可以到达其他的结点
在一些我需要把整个链
看作一个环的情况
我们这样的循环链的操作
会非常方便
但是呢 我们要注意
对循环连它的结束的判断条件
你可能是用计数的方法
或者是当遇到虚的头结点的时候呢
可能这个循环是需要结束了
链表呢它的处理
因为有指针的存在
所以其实还是比较麻烦的
我们要特别注意呢
不要进行非法的指针操作
有两类需要特别处理的情况
首先就是对一些特殊的结点
比如说头或者是尾部
我们要做相应的处理
特别是尾部的情况呢
我们需要对于这种单链呢
它的最后那个结点
一定要注意保持
它的next域是指向空
这样才能够保证
我们对于链的
这么一个遍历操作的时候
能够成功的结束
还有就是循环链要注意
它的尾结点的next域呢
要指回到头结点
然后对整个链表的处理呢
我们要注意对空链进行一个判断
还有就是我们在插入和删除的时候
要注意相应的指针进行修改
使得整个链
它是能保持正确的逻辑结构的
有就是我们指针移动的时候呢
也需要要正确的处理
否则我们可能会陷入一个死循环
比如说我对于链
进行遍历操作的时候
我的这样的一个当前结点是p
但是在循环里面呢
你忘了设置这个p=p（next）
这样的话就会形成一个死循环
我们最后给大家留一下思考
对于带表头和不带表头的情况
有一些什么差异
在前面的讲义里面呢
我们实现了对带表头情况的
插入和删除
你可以实现一下
不带表头情况
插入和删除算法
你可以看一下
那种情况呢
它所需要处理的边界条件
更多更麻烦
另外就是处理链表的时候呢
除了我们前面总结的
这些问题以外
你自己还经常犯哪些错误
好好总结一下
链表呢
我们是必须要能够完全掌握的
这么一个数据结构
掌握了链表以后呢
指针操作我们就通了
然后在后面一些复杂的数据结构
像树 图这里面呢
你就在操作时候
就不太容易犯一些指针错误了
谢谢大家