8.1.3 链表遍历与释放在线视频

那么经过刚才的这样的一个展示

大家已经知道呢在链表去组织数据的时候

它有一个节点的创建过程

然后呢要把节点去赋值 对吧

然后把赋完值的节点链接到链表里头去

这个它有包含了三步 所以我们可以看到

在屏幕上我们显示了一个链表的创建

的通用的过程 首先要定义一个头指针

开始是空的 这个大家都是如此

就是表示没有内容的

接着是一个while循环

当然了在不同的应用里头

它的whlie里头执行的过程是不一样的

但是这个算法上是类似的

不断的往里头去加新东西

那么怎么加呢 是由三部分组成的

刚才我们说过了 第一分配节点

所以我们看到Node*data=new node

它要去new一个节点出来

第二步把数据读到这个node节点里头去

就是读到这个data所指的单元里头去

那像刚才我们的例子里头呢

是读到data所指的那6个整数啊

还有它的ID啊还有它的operation啊等等

读到那个里头去这是第二步

第三步呢把它加到链表里头去

我们采取的是往链表的头部

去加入这个新节点的办法

因为往头部加入呢我们只需要两条语句

而且呢只需要保持这个head变量就够了

也就是说我通过head这一个变量

不断的把新节点往头部去加

只需要两条语句就可以完成这个事情

也就是大家看到的data的next

也就是新节点的

next=head head=data

有同学可能就会说

那你往这个链表的头部去加入这个新节点

那如果我想把它加到队伍尾巴后边去呢

那先来先到先来先得的往队伍的尾巴后去排去

那怎么来实现这个呢 甚至还有人说

我想插到队伍的中间去 那怎么让队伍不散架

怎么让新的节点能够安全的链接到

一个已有的链表里头去呢 那么这个问题

我们作为思考题给大家课后去思考

那么当我们把这个数据组织成了链表之后

怎么去访问它的内容就成为一个很重要的

一个问题 比方说在上面的链表当中

我们存储的是用户的编号

我们希望把这个用户的信息它的这个编号

依次的输出出来

那还同时输出记录的这个条目的序号

那下面我们就给出一种常见的一种实现方法

一种常见的去访问链表元素的方法

这样的一个方法呢我们去访问链表的元素

有的时候也被称为对链表的这种遍历

所以大家可以看到在链表的这个遍历的过程当中

一般来讲它是通过一个循环来做的

比如我们现在看到的是一个whlie循环

为了去打它的节点的序号

所以我们在循环的前面

定义了一个cnt这样的一个计数器

这样的一个整数变量从0开始计数

那如果链表不为空我就去访问它的元素

所以while循环的参数就是head这个指针变量

我们知道呢while它需要的是一个条件判断

需要的是一个布尔值来判断它是真是假

从而决定是否去循环 那我给它一个指针

它怎么变成一个逻辑变量变成一个布尔值呢

这就是我们以前讲到的 当指针为空的时候

就是为null的时候 它就是对应的是false

如果这个指针的值不是空那它就是true

不是空的情形很多呀 那么就对应着返回

ture这种情形的很多 也就是当且仅当

head=null的时候 它才会相当于是false

其他的所有的情况都是ture

因此这个whlie head就表示

如果这个head这个指针不是空

那我就开始循环 那循环做什么呢

我们这里头是写的cnt这个输出出来这个序号

然后空格然后这个用户的编号

这个用户的编号是当前节点的那个ID的域

所以我们写的是head这个指针箭头ID

完了cnt++ 再接着

注意这是当前节点已经输出完了

那怎么找下一个节点呢

首先得知道下个节点在哪里

我们现在从当前节点是可以知道

下一个节点在哪里的 这样这个办法就是

head=head的next 也就是让head

这个变量它的这个单元的值改变

因为它单元是存放地址的 让它的地址值变成

这个head它的next所指的那个单元的地址

这句话翻译成c++的语句就是

head=head->next

那有了这样的一个办法之后呢

我们就可以去依次的遍历链表里头的每一个节点

当遍历到最后一个节点的时候

我们可以知道这个head=head->next

最后一个节点了嘛 它的next一定是空了

所以呢这个时候在这样的一个赋值之下

head就变成空了 于是呢这个while循环就退出了

当然了我们以前讲过whlie循环其实

跟for循环是等价的 那我们也给大家看一看

用for循环来实现这个代码 它会长得怎么样

大家可以对比一下这两个代码

思考一下它们在访问链表的时候它的相同点

和不同点 那这个也比较有趣

我们可以看到在for循环里头啊

它初始的条件是用一个变量去指向这个

head等于它 然后呢在它的终止判断条件的时候呢

这个P是不是为空 在它的第三个递增的项里头呢

写的是P=P的next 就是下一个接点

然后for的循环体里头是这个信息的输出包括cnt++

那大家课后去仔细的思考一下

这两种表示实现的方法各有什么优劣

大家将来可以结合自己的爱好和程序里头

具体的运用去决定使用for循环还是while循环

那么链表的元素呢因为我们是通过

new这种运算符来动态分配出来的

当我们不再去使用它们的时候啊

应该把它们释放掉以免发生内存的泄露

关于这一点我们以前在讲这个动态数组的时候

已经说明过了 像我们以前为了去做那个旋转的矩阵

我们分配了一个二维的数组 这个都是要把它删掉的

那么这样的一个删除链表的节点

甚至包括链表本身的操作

当然它也是通过delete这个运算符来实现的

一个链表到底该怎么去运用

delete运算符来删除它呢

我们来看一般来讲在释放链表的时候

我们也是 因为链表是一个一个串上去的

所以我们释放的时候呢也得一个一个的

把它拆下来 所以它也是一种遍历

只不过这种遍历不是为了读它的数据

而是为了删除它的节点 所以这是一种

特殊形式的一种链表的遍历

我们看上方写的这个代码 它用到的跟

我们刚才在遍历链表的元素的算法是雷同的

都通过一个while循环

看看这个head指针是不是为空啊

如果不为空呢 做三件事情 很关键啊

大家注意看 这三条语句是有次序的 一定不能乱

第一条语句 定义一个临时的指针变量

去指向这个head 就是我先指着当前的节点

因为head的这个变量它存的是地址值

把这个值通过等号赋给tmp这个指针变量

那就意味着tmp和head两个指针都指向了

同一个内存单元 下面我们画了一个图

实际上就是head这个红块它所指的那个黑块和

tmp这个蓝块所指的那个黑块是同一个块

那这就是tmp=head它的含义

接下来第二句head=head的next

就是head->next

那大家看到在这个黑块的后面呢有一个虚线

那它指向的其他的一个内存单元 我这边画了

一个示意的这种图 那根红线就表示当执行了

第二条语句的时候 红块这个head这个变量

指向的就是新的内存单元 所以这是第二句

那这个时候我们可以看到黑块是由蓝色的tmp来指的

而下面那个白块是由红色的head指着的

注意啊红色head指着的是链表的剩余部分

那么现在头部的第一个接点已经是tmp指向了

head不再指向它 注意看第三句话

delete tmp 那么tmp它的变量所指的

那个黑块的内存就会被系统回收回去

注意看当这个过程完成之后我们的链表缩小了

这个头已经被掐掉了

大家可以在纸上画出一个示意图

当第一个节点被tmp所指之后

head指向下一个之后

第一个节点已经不受head控制了

这个时候呢delete tmp就把这个给它去掉了

那么这个链表就变短了 第一个节点不要了

那么大家可以对照着代码和下面的这个图

大家思考一下在这个过程当中指针的这种变化

尤其是要记得这三条语句的顺序是不能错乱的