再接下来一个功能
就是链表的遍历 遍历是什么呢
就是全部走一遍的意思
我这个链表中包含这么多个元素
我想做一件事情
我就逐一访问这个链表中所有的元素
做一个特定的处理
那么像这样的一个操作
我们就叫它遍历
所以我们现在要同学们写一个函数
来遍历这个链表
调用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 一个容器
理论上应该是抽象的
你比如讲你有一课桌
然后底下里面有一个抽屉
那个抽屉是多具体的一个东西啊
但是当它作为一个容器的时候
它事实上是一个非常抽象的容器
为什么 因为只要尺寸合适
任何东西都可以放在你的抽屉里
你的铅笔可以放在抽屉里
钢笔可以放在抽屉里
书本、笔记本可以放在抽屉里
钱包也可以放在抽屉里
显然这些东西是不同的
但是抽屉都能放 这样的抽屉是抽象的
如果我们按照这样方式实现这样一个链表
它能算抽象吗 显然不抽象
点我们可以存 事实上我们只能存二维点
如果你想换成三维的点
它都存不了 它都得改 它不抽象吧
也就是说 到目前为止
我们实现的这个抽象链表库
它压根就不抽象