当前课程知识点：数据结构 > 第2章 线性表 > 2.5 循环链表和双向链表 > 2.5 循环链表和双向链表
同学们，大家好
我是云南大学信息学院教师孔兵
这节课我们讨论循环链表和双向链表
循环链表是在单链表的基础上
做了一点改变，让单链表的最后一个结点的指针域
不再指向空，而是指向头结点
整个链表就形态上来说形成一个环
图中是循环链表的示例
第一个循环链表是空的循环链表
在空的循环链表中，这个头结点的指针指向自身
空表的判定条件是L->next==L
第2个循环链表是一个普通的循环链表
最后一个结点an的指针指向头结点
在我们使用循环链表的时候，要稍微注意一下
就说循环的结束的问题就是循环结束的条件
普通链表当中
如果我们用指针p扫描链表
当p指向最后一个结点an时
可以用p->next==NULL判别p指向的是最后一个结点
那么，在循环链表当中呢
循环结束的条件应该变为p->next==L
这时p指向的就是最后一个结点了
这一点注意一下就可以了
循环链表除了最后结点指针指向头结点外
和普通单链表没有什么太大差异
操作之类的我们就不多介绍了
之所以讨论循环链表，主要是在一些特殊的问题当中
我们用循环链表更便利一些
比如约瑟夫环问题，用循环链表就比较方便
下面呢，我们看一下双向链表
在单链表中，每一个结点的有附设一个指针next
用next这个指针指向存储其后继的结点
在这样的单链表中，假如我们扫描的话
我们只能从前向后扫描
可以从第1个结点开始不断的通过next指针找后继
也就是说可以从前驱找后继
但是不能从后继找前驱，如果在我们的问题中
既需要找后继方便，也需要找前驱方便
可以考虑采用双向链表
双向链表中每个结点包含两个指针
一个是指向后继的next
一个是指向其前驱的prior
双向链表的结点定义为一个结构体
包含3个成员，一个是存储数据元素的data
一个指向其前驱的指针prior
一个是指向后继的指针next
和单链表比较来看，就是增加了一个指向前驱的指针
从图中可以直观的看出
这样的一个结点包含指前驱和指后期的指针
那么从任何一个结点出发，向前找前驱
或是向后找后继都是很方便的
当然这里也是要付出代价的
毕竟每个结点增加了一个指针
存储空间的需求增大，操作实现也麻烦一些
下面我们看一下两个主要的操作：插入和删除
双向链表的插入操作，仍然是一些指针里的赋值
当然这里要赋值的指针更多一些
如图所示。假设p是指向要插入结点的位置
S指向待插入的结点，插入后
ai-1的后继是e，e是ai的前驱
要重新赋值的指针是图中红色的这4个
一般先对s的两个指针进行赋值
s->prior=p->prior; s->next=p;
让e前驱的指针指向ai-1，e后继的指针指向ai
p->prior=s, 让ai前驱的指针指向e
s->prior-> next=s; 让ai-1指向后继的指针指向e
通过这4个指针域的赋值
完成s所指这个结点的插入
下面呢，我们看一下删除
双向链表的删除，我们也简单的看一下
假设p指向待删除的这个结点
删除后，ai-1的后继变为ai+1
对称的，ai+1的前驱变为ai-1
要重新赋值的指针是图中红色的这2个
p->prior-> next=p-> next;
让ai-1指向后继的指针指向ai+1
p-> next->prior= p->prior;
让ai+1指向前驱的指针指向ai-1
最后，把p所指结点释放掉就可以了
好，同学们
我们关于循环链表和双向链表的讨论就到这儿
下次课再见
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结
