当前课程知识点：基于Linux的C++ > 第八讲 链表与程序抽象 > 8.7 链表（四） > LinuxCPP0807
再接下来一个功能
就是链表的遍历 遍历是什么呢
就是全部走一遍的意思
我这个链表中包含这么多个元素
我想做一件事情
我就逐一访问这个链表中所有的元素
做一个特定的处理
那么像这样的一个操作
我们就叫它遍历
所以我们现在要同学们写一个函数
来遍历这个链表
调用PtTransformIntoString这样一个函数
来输出结点的数据
我们相应的结点之间用一个箭头来连接
我们要做的就这个事
所以我们要写一个函数
来实现这个链表的访问
因为我们要访问链表中的所有元素
一个接着一个地访问
所以这个动作就叫遍历
那么我们怎么实现呢
这个函数LlTraverse就要定义一个临时指针t
t初始化成list->head
当这个链表为空的时候
输出错误信息然后结束
程序流程提前终止
如果这个链表非空
那么我们就循环
t不是指向我们的表头结点吗
取它的data域
把它转换成一个字符串输出 输出箭头
用t=t->next 找它的下一个结点 循环
当t这个指针值 也就是这个结点的地址
非空的时候（不是NULL的时候）
那么就说明这个链表还没有遍历结束
我们输出数据 然后t赋值为t->next域
找下一个结点 循环
这样一个whlie循环
就完成了我们链表中所有结点的遍历
最后我们输出NULL
说明我们链表全部输出完毕了
其中所有二维点的数据
全部都被我们输出完毕了
这个就叫链表的遍历
你注意看这样一个函数LlTraverse
它内部必须有对PtTransformIntoString
这个函数的调用
这就意味着如果我这个链表
存储的是一个抽象二维点的数据
那么你就需要包含二维点的头文件
也就是说你必须使用那个库
不使用那个库没有办法去做点的数据处理
你不能使用POINT类型
所以你就没有办法访问它的数据成员
你更没有办法把它转换成字符串啊
除非你使用PtTransformIntoString函数调用
链表库和我们的点库是紧密相关的
离了点库 我们这个链表库是不能工作的
我们要写一个函数
在链表中查找特定的一个点是不是存在
我们就看我们这个链表的那个point
它的x域和y域是不是和我们要找的这个点
它的x和y域是完全相等的
如果相等我们就找到了
如果不相等那就找下一个
全都找完了 也没找着
那不就没找着嘛 对吧
它其实还是一个遍历的动作
只不过我们刚才那个遍历
是打印全部链表结点的信息
而这个遍历是查找一个特定的元素
所以我们这里面用PtCompare这个函数的调用
来替换PtTransformIntoString那个函数的调用
如果我能够找到这样的一个点
我们就return true
否则我们就继续循环下去
找下一个结点去比较
最后这个函数将会返回true和false
来表明有没有这个链表中找到point
我们当然不会找这样的point本身
而我们找这个结构链表中
是不是存在着一个点
它的内容和我们这个point所指向的
那个二维点的x域和y域
都刚好是完全相同的
现在我们可以对这个链表做一些小结
链表有一个非常重要的优点
就是它的插入和删除操作是非常容易的
你别看我那个插入和删除操作画了好多图
第一步做什么 第二步做什么
第三步做什么 画那么多图
然后那么多步骤 看上去很烦
但实际上它的插入和删除操作是非常容易的
逻辑上也许是比较困难
但是操作是非常节省时间的
它不需要移动数据
这一点和数组不一样
你如果开一个8个元素的数组
如果想在第4号位插入一个新元素
你要维持静态数据的完整性
那么原始的4号位就必须变成5号位
在此之前你必须保证原始的
这个5号位变成6号位
在此之前你必须保证
原始的6号位变成7号位
原始的7号位变成8号位
也就是说在一个标准的静态数组中
插入一个元素
必须让这个元素插入位置后
所有元素都向后挪动一个单位
然后这个数据才能插进去
因为你要保证静态数组连续存放的特性
链表呢 这个移动是不存在的
因为在开始的时候 就谈到过
链表中的结点 它逻辑上是顺序的
而在物理上不要求它是顺序的
也就是说它可以不是顺序的
所以就不需要移动数据
而如果不移动数据
那么插入和删除操作
就是短短几步就能够做完
它是非常非常容易的
数组在这一点上和它是远远比不了的
但是链表呢 它也有它自己的一个缺点
这个链表中的元素它只能顺序地访问
你如果想访问某一个结点
你必须能够找到它 对吧
而你要想找到这个链表中的某一个结点
你必须能够找到它的前一个结点
而你要想找到链表结点的前一个结点
你必须找到它的前一个结点的前一个结点
也就是说这个链表的访问你只能顺序着来
你不能混乱地跳
像这一点 数组又远远好于它
你比如说数组我想访问0号元就访问0号元
我想访问5号元就访问5号元
这个访问完全是随机的 对吧
访问5号元以后
接下来立马我就访问6号元
接下来跳回去又想访问2号元
行不行 行的
可是对于链表 这一点是做不到的
也就是说 链表只能支持顺序访问
而我们静态数组是支持随机访问的
刚才实现的这个链表库
它是有一些问题的
就是这样一个抽象链表库
它事实上只能存储点的数据结构
必须要了解点的接口
不管是链表库的头文件
还是链表库的源文件
都需要包含“point.h”这个头文件
第二个 这个抽象链表库
不能保存其它数据对象
只能保存二维点
如果你想保存其它的东西
比如三维点 比如一个复数
那么你必须重新写一个抽象链表库
也就是说像这样一个链表
它事实上是不抽象的
如果你要想存储
目前还没有实现的数据结构
那怎么办呢 那更糟了
这个头文件你包含不了
你压根就没有办法做
还是我刚才那句话
现在实现的抽象链表实际上不是抽象的
从某种程度上来讲
像这样一个链表实际上
是用来存储其它数据对象的
我们习惯上称它是一个容器
一个container 一个容器
理论上应该是抽象的
你比如讲你有一课桌
然后底下里面有一个抽屉
那个抽屉是多具体的一个东西啊
但是当它作为一个容器的时候
它事实上是一个非常抽象的容器
为什么 因为只要尺寸合适
任何东西都可以放在你的抽屉里
你的铅笔可以放在抽屉里
钢笔可以放在抽屉里
书本、笔记本可以放在抽屉里
钱包也可以放在抽屉里
显然这些东西是不同的
但是抽屉都能放 这样的抽屉是抽象的
如果我们按照这样方式实现这样一个链表
它能算抽象吗 显然不抽象
点我们可以存 事实上我们只能存二维点
如果你想换成三维的点
它都存不了 它都得改 它不抽象吧
也就是说 到目前为止
我们实现的这个抽象链表库
它压根就不抽象
-1.1 提纲
-1.2 程序设计的基本概念
-1.3 简单C/C++程序介绍
-1.4 程序设计的基本流程
-1.5 基本语法元素
-1.6 程序设计风格
-1.7 编程实践
-第一讲 C/C++基本语法元素--编程实践提交入口
-2.1 提纲
-2.2 结构化程序设计基础
-2.3 布尔数据
-2.4 分支结构
-2.5 break语句
-2.6 循环结构
-2.7 编程实践
-第二讲 程序控制结构--编程实践提交入口
-3.1 提纲
-3.2 函数声明、调用与定义
-3.3 函数调用栈框架
-3.4 编程实践
-第三讲 函数--编程实践提交入口
-4.1 提纲
-4.2 算法概念与特征
-4.3 算法描述
-4.4 算法设计与实现
-4.5 递归算法（一）
-4.6 递归算法（二）
-4.7 容错与计算复杂度
-4.8 编程实践
-第四讲 算法--编程实践提交入口
-5.1 提纲
-5.2 库与接口
-5.3 随机数库（一）
-5.4 随机数库（二）
-5.5 作用域与生存期
-5.6 典型软件开发流程（一）
-5.7 典型软件开发流程（二）
-5.8 编程实践
-第五讲 程序组织与开发方法--编程实践提交入口
-6.1 提纲
-6.2 字符
-6.3 数组（一）
-6.4 数组（二）
-6.5 结构体
-6.6 编程实践
-第六讲 复合数据类型--编程实践提交入口
-7.1 提纲
-7.2 指针基本概念
-7.3 指针与函数
-7.4 指针与复合数据类型（一）
-7.5 指针与复合数据类型（二）
-7.6 字符串
-7.7 动态存储管理（一）
-7.8 动态存储管理（二）
-7.9 引用
-7.10 编程实践
-第七讲 指针与引用--编程实践提交入口
-8.1 提纲
-8.2 数据抽象（一）
-8.3 数据抽象（二）
-8.4 链表（一）
-8.5 链表（二）
-8.6 链表（三）
-8.7 链表（四）
-8.8 函数指针（一）
-8.9 函数指针（二）
-8.10 抽象链表（一）
-8.11 抽象链表（二）
-8.12 编程实践
-第八讲 链表与程序抽象--编程实践提交入口
-9.1 提纲
-9.2 程序抽象与面向对象
-9.3 类类型
-9.4 对象（一）
-9.5 对象（二）
-9.6 类与对象的成员（一）
-9.7 类与对象的成员（二）
-9.8 类与对象的成员（三）
-9.9 继承（一）
-9.10 继承（二）
-9.11 继承（三）
-9.12 多态（一）
-9.13 多态（二）
-9.14 编程实践
-第九讲 类与对象--编程实践提交入口
-10.1 提纲
-10.2 四则运算符重载（一）
-10.3 四则运算符重载（二）
-10.4 关系与下标操作符重载
-10.5 赋值操作符重载（一）
-10.6 赋值操作符重载（二）
-10.7 赋值操作符重载（三）
-10.8 赋值操作符重载（四）
-10.9 赋值操作符重载（五）
-10.10 流操作符重载（一）
-10.11 流操作符重载（二）
-10.12 流操作符重载（三）
-10.13 操作符重载总结
-10.14 编程实践
-第十讲 操作符重载--编程实践提交入口
-11.1 提纲
-11.2 泛型编程概览
-11.3 异常处理机制（一）
-11.4 异常处理机制（二）
-11.5 运行期型式信息（一）
-11.6 运行期型式信息（二）
-11.7 模板与型式参数化
-11.8 题外话：术语翻译
-11.9 泛型编程实践（一）
-11.10 泛型编程实践（二）
-11.11 泛型编程实践（三）
-11.12 泛型编程实践（四）
-11.13 泛型编程实践（五）
-11.14 泛型编程实践（六）
-11.15 泛型编程实践（七）
-11.16 泛型编程实践（八）
-11.17 泛型编程实践（九）
-11.18 泛型编程实践（十）
-11.19 编程实践
-第十一讲 泛型编程--编程实践提交入口
-12.1 提纲
-12.2 程序执行环境（一）
-12.3 程序执行环境（二）
-12.4 程序执行环境（三）
-12.5 程序执行环境（四）
-12.6 输入输出（一）
-12.7 输入输出（二）
-12.8 文件系统
-12.9 设备
-12.10 库（一）
-12.11 库（二）
-12.12 makefile文件（一）
-12.13 makefile文件（二）
-12.14 makefile文件（三）
-12.15 编程实践
-第十二讲 Linux系统编程基础--编程实践提交入口
-13.01 提纲
-13.02 进程基本概念
-13.03 信号
-13.04 进程管理（一）
-13.05 进程管理（二）
-13.06 进程管理（三）
-13.07 进程间通信（一）
-13.08 进程间通信（二）
-13.09 进程间通信（三）
-13.10 进程间通信（四）
-13.11 进程池
-13.12 编程实践
-第十三讲 进程编程--编程实践提交入口
-14.1 提纲
-14.2 线程基本概念
-14.3 线程管理（一）
-14.4 线程管理（二）
-14.5 线程管理（三）
-14.6 线程管理（四）
-14.7 线程同步机制（一）
-14.8 线程同步机制（二）
-14.9 C++11线程库（一）
-14.10 C++11线程库（二）
-14.11 C++11线程库（三）
-14.12 C++11线程库（四）
-14.13 C++11线程库（五）
-14.14 编程实践
-第十四讲 线程编程--编程实践提交入口
-15.1 提纲
-15.2 Internet网络协议
-15.3 套接字（一）
-15.4 套接字（二）
-15.5 编程实践
-第十五讲 网络编程--编程实践提交入口
