引入
上节，我们学习了什么是线性表以及抽象数据类型，今天我们来看看线性表的抽象数据类型如何来使用。
感受抽象
还记得上节课我们讲的那个例子吗？升旗仪式排队:
1号小红
2号小明
3号小强
4号小姗
…
55号小美
56号小力
- 因为我们记不住编号，所以只要记住前面的同学名称就可以了，也就是找到自己唯一的直接前驱同学就行了。这样大家就可以排好队了，这就是
线性表的创建和初始化。 - 但是发现55号小美太矮了，2号小明太高了，导致队伍不好看，所以就把队伍解散，老师准备重新根据身高排队。解散的动作就类似
线性表重置位空表。 - 刚排好队，发现3号小强请假了，那4号小珊就要向前挪动，4号小姗的前面就是2号小明了，这就是
线性表删除数据。 - 下次升旗仪式，3号小强回来了，就要插入2号小明和4号小姗之间，4号小姗退一位，然后3号小强回到自己的位置上。这就是
线性表插入数据。 - 升旗过程中呢，有学生会检查，发现我们队55号没有穿校服，就反馈给我，我就查了下花名册（线性结构哦），发现是55号是小红，这就是
根据位序得到元素。
线性表抽象数据类型定义
上面我们通过排队的例子，大概了解了线性表的一些操作和原理，那么现在我们就来讲讲线性表的抽象数据类型定义。
定义
声明线性表
ADT 线性表（list）
数据描述
Data
线性表的数据对象集合位{a1,a2,a3,….,an}
每个元素的类型均为 DataType（也就是原子类型，int float char 等等）
除了第一个元素外，每个元素都有一个唯一直接前驱
出了最后一个元素，每个元素都有一个唯一直接后继
数据元素之间的关系是一对一的关系
操作描述
Operation
InitList（*L）：初始化操作，建立一个空的线性表 L
ListEmpty（L）：判断线性表是否位空表，若为空表，返回 ture，否则返回 flase。
ClearList ( *L )：将线性表清空。
GetElem（ L , i , * e）:将线性表 L 的第 i 个位置的元素值返回给 e 。
LocateElem（L,e）：在线性表 L 中查找与给定值 e 相等的元素，成功则返回 e 在表中的序号，失败则返回 0 。
ListInsert（ *L, i, e）：在线性表 L 中第 i 个位置插入新元素 e 。
ListDelete( *L , i , *e)：删除线性表 L 中第 i 个元素，并用 e 返回其值。
ListLength( L )：返回线性表 L 的元素个数。
结束线性表抽象数据结构
end ADT
其实上面，就是分了四块
- ADT 线性表（list）声明类型名
- Data 数据描述
- Operation 数据的操作
- end ADT 结束
我们在实际操作中，会综合使用上面的各种操作。
例子
实现两个线性表 A 和 B 的并集操作，即把 A 中 的所有元素和 B 中的所有元素混合，只保留一个重复项目。
思考
实际上就是把 B 集合中的所有元素进行遍历，和 A 集合进行比较，如果一样则抛弃，不一样，就存入集合 A 中。所以，大概要用以下几个 Operation：
- ListLength( L )；获取集合 B 的长度
- GetElem( L , i , *e); 拿取元素
- LocateElem(L ,e); 获取元素位置
- ListInsert(*L , i , e); 在表 L 中的第 i 位插入 e
解题
void unionL(list *la, list lb){
int la_len, lb_len; //用于存储线性表长度
Elemtype e; //用于存储该类型的值
la_len=ListLength(*la); //存储 *la 的长度，这里不是地址
lb_len=ListLenght(lb); //存储 lb 的长度
for(int i=0;i<lb_len;i++){ //遍历 lb 集合
GetElem(lb , i , &e); //获取 lb 集合中的元素
if(!LocateElem(*la, e)){
//判断有没有，没有的话返回假，!假就是真
ListInsert(*la,++la_len,e); //先把位置向后移动一位，然后把 e 插入到 la 中
}
}
}
其实和普通编程的思路差不多，因为是抽象数据类型，并且是要应用到不同语言的，所以要用这样的 Operation 来执行。
尾巴
这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。
评论