大家好
欢迎回来继续学习
C++语言程序设计
接下来的这一节
我们来学习
顺序访问的线性群体
一个链表类
链表呢跟数组一样
它都可以用来存储线性群体
但是它的不同地方在于什么呢
我们想想用数组的时候
不管你是静态数组
还是动态数组
如果你需要频繁地插入
和删除元素的时候
是不是其他元素都在频繁的移动
这样会影响程序的运行效率的
有没有一种
不同的数据结构
能够使我们
随时插入删除元素
不太影响其他的元素呢
这种数据结构就是链表
链表
它是一种动态数据结构
是可以用来
表示顺序访问的线性群体的
什么是顺序访问的线性群体呢
我们还是温故而知新
回想一下数组
我们是怎么访问数组元素的呢
用数组名下标
这叫做直接访问
也就是说指哪个就访问哪个
有个数组名给个下标
就找到这个元素了
而链表呢
它的访问方式是另外一种
不能够一下就指到
某个序号的元素去访问它
而要首先从
链表的最开头的元素开始
每一次从一个元素
找到它的下一个元素
再找到下一个元素
好象顺藤摸瓜一样
一个一个往下访问
这就是顺序访问的方式
链表呢
它是由结点组成的
结点是可以在运行的时候
动态生成的
那每一个结点呢
除了包含数据以外
还要包含指向它后继结点的指针
如果每个链表结点中
只有一个指向后继结点的指针
那么这样的链表呢
就称为单链表
为什么链表的结点中
除了存放数据
还要存放指向后继结点的指针呢
因为我们要依赖这个指针
要靠这个指针去维持
结点与结点之间的次序关系
我们知道数组中的元素
是按照它的逻辑次序
在物理地址上
也是依次连续存放的
所以呢
使用数组的时候
我们是靠这个物理地址上的
这种相邻关系
来维持它逻辑上的次序关系
而链表呢
它的一个个结点
在物理地址上不再相邻了
其实这是它很大的一个优势
当然
它也带来另外一个方面的不足
就是说你无法通过它的物理地址
来维持它逻辑关系上的相邻性
那怎么办呢
就要附加一个信息
每一个结点就都要存储
它后继结点的地址
这样顺着一个一个
就可以找到
全部的链表中的结点了
现在呢
我们来看一个单链表的示意图
大家看
这就是一个单链表的示意图
这里面的每一个大方框呢
就表示一个结点
这些结点呢
它们的物理地址是不必相邻的
往往它还就真不是相邻的
在任何时候
需要插入一个新结点了
那么就构造一个新结点
插到链表里面就行了
其他结点
它的存储位置都不用动
如果需要删除一个结点
那么删除就好了
后面我会给大家讲
这个插入和删除的代码怎么写
反正你插入也好 删除也好
都不影响其他的结点
这就解决了我们在数组中
插入删除元素
需要移动其他元素的
这样一个问题
但是呢
我们就要在结点中
多附加一点信息
除了存储每个结点
应该存储的数据以外
还要存储它后继结点的地址
在这个示意图中就用箭头来表示
每一个箭头指向下一个结点
那么这个链表呢
应该一定要有一个表头指针的
应该有一个指针指向它的首元素
第一个结点
然后顺着这个第一个结点
可以找到第二个
顺着第二个可以找到第三个
是不是还要有一个指针
指向尾元素呢
那么根据你的算法需要
可以有 也可以没有
但是它的头指针
可千万不能丢了
因为找到每一个结点的唯一方式
就是通过它的前驱结点找到它
如果我们把前面的头指针丢了
那么这个链表可就丢失了
什么也找不到了
接下来呢
我们来看一下
这个单链表
它的结点怎么样用程序去实现
我们来看一个
单链表结点类的模板
因为它是模板
所以这个结点里面
放任何类型的数据
都是可以的
这是单链表的结点类模板
这个模板里面的数据呢
包括这个结点本身
要存储的数据元素的内容
以及指向后继结点的地址
也就是后继结点的指针
那这个数据元素内容呢
它的类型是T类型
是将来这个结点应该能够容纳
任何类型的数据
它这个模板
然后这里把它设为public数据
当然这样访问起来比较方便
如果你要设成private的话
那要给它增加
这种get set这样的公有接口
好 这个指向后继结点的指针
设为一个私有成员
然后它的成员函数比较简单
只有这几个
一个是构造函数
构造函数
第一个参数是
结点需要容纳的数据项
数据元素
第二个参数是后继指针
初始化为空指针
然后一个inserAfter
是在当前结点之后
插入一个结点的函数
deleteAfter呢
是在删除当前结点之后
下一个结点的函数
这个nexNode
是返回下一个结点的指针
它的地址这样一个函数
现在我们就来看一下
这几个主要函数它的实现
以及它的示意图
比如说insertAfter
需要在当前结点之后
插入一个结点
比如说这个结点是当前结点
那么在它之后插入一个结点
显然我们需要的结果就是说
把新结点放在这儿
更改一下
它的指向后继结点的指针
这个链更改一下
把它换成这个黄颜色的
但是这个变更的次序
是有讲究的
我们来看
首先第一步呢
这个新结点
我们要让新结点的后继指针
指向data2这个结点
为什么呢
这样就保证了这个链表的后半截
跟前面这个新结点就连上了
这个必须第一步完成
然后第二步才是让
这个当前结点
data1这个结点
它的后继指针指向这个新结点
如果这个两个步骤反了
那你还没有让新结点的后继
指向后头的后半截链表
你就把这个断开的话
那么链表的后半部分就丢了
因为找到一个结点的唯一办法
是通过它的前驱结点找到
所以先得把它的新前驱结点
放在这儿
那么原来的这个指针才可以
改变方向
这是删除当前结点
之后的一个结点
按说删除呢
从逻辑上删除呢
我只要把后继指针改一下
就行了
但是如果
你仅仅这样从逻辑上删除的话
这个结点它当初
通过动态分配得到的这个空间
势必就泄露了
内存空间会泄露
所以我们删除一个结点以后呢
需要释放这个结点
所占有的内存空间
那么到底是不是在deleteAfter
这个函数里面
去释放这个空间呢
我觉得在这个函数里面
去释放空间
不一定就是最适合的
因为删除这个结点
从逻辑上删除它
真正的目的
到底是说我真的不用它了
把它删除
还是说把这个结点拿来
作为材料 作为素材
我串到别的链表上去
还有别的用途
这个仅仅
在删除结点的这个函数里面
是无法了解到
为什么要删除结点这个用途的
所以我们在这里设计这个函数呢
就是
我们首先将要被删除的这个结点
它的地址存在这个临时变量
tempPtr里面
然后接下来看
如果
要删除的结点根本就不存在
是最后一个结点之后的
那就是空了
所以看看这个next
这个next
就是它当前结点的后继指针
这个next如果是空的话
那什么也不用干了
return一个0就可以了
return为空就可以了
如果next不空
说明你的要求
要删除结点这个要求
是可以为你去做的
后面是有结点的
那就改一下指针
这样要删除的这个结点
也就tempPtr指向的这个结点
它的后继指针
存到当前结点里面来
那么就把这个指针就换了方向了
对吧
好 现在我们来看这个
完整的结点类模板的代码
这是刚才我们看到的
结点类模板Node它的定义
还有后面看到
这是它的各个函数的实现
构造函数呢
它就是初始化这个数据
以及后继指针
那么这个nextNode函数呢
就是返回它的后继指针
这个next予以返回就行了
这个nextNode这个函数呢
有两个版本
一个是const版本
const版本返回的那是常指针
通过常指针呢
它是只读的
可以访问读取这个结点的内容
但是不许改变它的状态了
这就是刚才我们看到的
那个实现在当前结点之后
插入一个结点p
这是删除当前结点的后继结点
并且返回它的地址
这就是这个结点类模板