🧨抽象数据类型线性表的定义
🎃基本操作
🎍初始化
InitList(&L) (intialization List)
操作结果：构造一个空的线性表L
🎎销毁线性表
DestoryList(&L)
初始条件：线性表L已经存在。
操作结果：销毁线性表L
🥼线性表置空/清空线性表
ClearList(&L)
初始条件：线性表L已经存在
操作结果：将线性表L重置为空表。
🖼判断线性表是否为空
ListEmpty(L)
初始条件：线性表L已经存在
操作结果：若线性表L为空表，则返回true;否则返回false
✨判断元素个数(表长)
ListLength(L)
初始条件：线性表L已经存在
操作结果：返回线性表L中的数据元素个数。
🎐线性表的按值查找
GetElem(L,i,&e)
初始条件：线性表L已经存在，1<=i<=ListLength(L)
操作结果：用e返回线性表L中第i个数据元素的值
LocateElem(L,e,Compare())
初始条件：线性表L已经存在，compare()是数据元素判定函数。
操作结果：返回L中第一个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。
🧵查找某个元素的前驱
PriorElem(L,cur_e,&pre_e)
初始条件：线性表L已经存在
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回他的前驱，否则操作失败。pre_e无意义。
🧵查找某个元素的后继
NextElem(L,cur_e,&next_e)
初始条件：线性表L已经存在
操作结果：若cur_e是L的数据元素，且不是第最后一个，则用next_e返回他的后继，否则操作失败，next_e无意义。
🥽插入元素
ListInsert(&L, i, e)
初始条件：线性表L已经存在，1<=i<=ListLength(L)+1
操作结果：在L的第i个位置之前插入新的数据元素e,L的长度加一。
🎑删除某个元素
ListDelete(&L,i,&e)
初始条件：线性表L已经存在，1<=i<=ListLength(L)
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减一。
🛒对线性表每个元素做操作
ListTraverse(&L, visited())
初始条件：线性表L已经存在
操作结果：依次对线性表中每个元素调用visited()
🥓插入算法
(在线性表a3位置之前插入一个新元素e(e=6))
插入位置在最后在线性表的最后添加一个元素不需要移动直接添加
插入位置在最前在原线性表的第1个元素之前插入一个新的元素，线性表的所有元素都要移动移动次数最多
插入位置中间如下
🥫删除算法
🧈小结
查找、插入、删除的平均算法复杂度为O(n)
空间复杂度显然顺序表操作没有占用辅助空间算法的空间复杂度O(1)
🍠线性表的优点
-
存储密度大(结点本身所占用的空间/结点结构所占存储量=1)无需为表示表中元素之间的逻辑关系，而增加额外的存储空间
-
可以随机存取表中任意位置的元素
🍣线性表的缺点
-
插入、删除某一元素需移动大量元素
-
当线性表长度变化较大时，难以确定存储空间的容量，
-
数据元素的个数不能自由扩充(存储空间不灵活)
评论区