现在就使用数据封装与信息隐藏的
那个技术手段来设计抽象的链表库
首先我们来看抽象链表的接口
要想设计一个能够处理点的
数据类型抽象链表接口
就是“list.h”头文件
在设计它的时候就需要特别注意
一个 这个链表本身必须是抽象的
我要能够把它的数据封装起来
信息要能够藏起来
声明一个LIST这样一个结构体类型
“struct LIST;”
注意我们没有定义它的细节
我们把PLIST定义为指向struct LIST的指针类型
这就完成最基本的数据封装和信息隐藏
然后我们提供相应的接口
提供LlCreate、LlDestroy
完成这个链表的创建和销毁
然后提供LlAppend、LlInsert、LlDelete、LlClear
来完成链表结点的追加、插入、删除、清除
像这样的工作
我们提供LlTraverse、LlSearch
来完成这个链表的遍历与查找
这个就是抽象链表库的标准接口
接下来就是我们抽象链表库的基本实现
在这里要完成这些功能
链表的构造和删除、链表的追加、插入、删除、
遍历和查找这些最基本的功能
我们首先来看链表的构造与销毁
怎么实现这个链表构造与销毁呢
LlCreate这个函数里面
我们要动态地构造LIST类型的一个对象
我们用PLIST类型的一个指针变量p来保存
所构造出来的这个对象的地址
目标结构体的count域设为0
然后head和tail域都设成NULL
最后返回指针
然后LlDestroy 销毁
想销毁这个链表的时候 我们要注意
我们必须首先删除链表中所有的元素
然后才能销毁链表
因为我们这个链表里面包括一些
非常重要的数据结构
第一个 有一个struct LIST
LlDestroy这个函数 它的这个参数list
它实际上是一个指向struct LIST的指针
我们要销毁的就是那个struct LIST
目标数据对象
而这个目标数据对象有head指针和tail指针
尤其是head指针
它将指向我们的链表表头结点
而我们链表结点都是struct NODE
这样的一个数据对象
而这样的数据对象
又总是动态内存分配出来的
所以在我们销毁list所指向的
链表目标数据对象之前
必须保证这个链表中的所有结点
都已经被我们销毁了
如果你没有销毁链表中的全部的结点
你就销毁这个list
所指向的struct LIST那个目标结构体
那么这个链表中全部结点都会丢掉
这个做法是不对的
所以我们首先要调用一个函数
来完成链表结点的销毁
这个函数就是LlClear
LlClear这样一个函数要做的一个事情就是
必须一个接着一个地销毁链表中的所有结点
为了方便起见
总是从链表的表头结点开始删除
所以当链表的表头指针非空的时候
list->head这个链表的表头指针
一旦指向某一个确定的结点
而不是NULL的时候
就会设一个临时指针t
把它初始化成list->head
就是让它和表头指针指向同一个结点
也就是指向表头结点
然后list->head赋值为t->next
这样的话这个链表的表头指针
这个时候将不再指向原始的表头结点
而是指向原始表头结点的下一个结点
也就让下一个结点变成我们新的表头结点
而我们的t将使向原始的表头结点
对于我们的链表而言
因为链表中那个data字段
保存的是点的抽象数据
实际上保存是指向POINT那个二维点的指针
所以在你销毁t所指向的表头结点之前
必须调用PtDestroy(t->data)
销毁这个data字段所指向的
那个二维点的目标数据对象
此后整个链表的元素要递减
while循环 删除下一个表头
再循环 再删除表头
一直到链表的全部元素都被你删除
最后把链表的表尾结点设成NULL
这是我们的LlClear函数
因为保存是抽象的点的数据结构
所以在我们这个链表的头文件
也就是抽象链表库接口那个地方
我们必须包含“point.h”这个头文件
因为我们要用到PPOINT类型
而我们实现这个链表的时候
“list.cpp”也需要包含我们的“point.h”这个头文件
因为我们要使用PtDestroy
来销毁t->data所指向的目标二维点
也就是抽象链表库和抽象点库
两者是紧密关联的
你没有办法割裂这两者之间的关系
接下来就是表头结点的删除
我们可以为它画上这样一个图
那么对于表头结点删除动作的话
你已经看到我们的LlClrea函数的实现
那么我们怎么实现这个表头结点的删除呢
它实际上包含了最重要的几个步骤
第一步 我要需要设置一个临时指针t
也就是让它和head指向同样一个结点
指向这个表头结点
因为表头结点这个data域
将指向我们标准的二维点
所以你看到整个存储布局
我们的第一步
就需要让t指向我们的表头结点
我们的第二步
就要将链表的表头结点
从原始结点改变成原始结点的下一结点
head结点一改 原来表头结点
就从我们的这个链表中被抠出来了
不存在了
我们有临时指针t指向它
倒不担心内存泄露 但是链表本身
这个结点已经不存在了
接下来我们要销毁这个结点
在销毁这个结点之前你要记住
因为这个链表存储的是
二维点的一个数据结构
所以data字段
将指向二维点那个目标结构体
所以在销毁这个结点之前
第三步你要做的事情就是
首先你必须销毁二维点的数据结构
然后第四步
你才能够销毁我们的原始表头结点
t所指向的这个目标结点
第五步 我们要递减链表的结点数目