[数据结构与算法]数据结构：顺序表与链表对比

顺序表和链表的优缺点

顺序表（顺序存储）
优点：支持随机存取、存储密度高
缺点：连续空间分配不方便，改变容量不方便

链表（链式存储）
优点：离散的小空间分配方便，改变容量
缺点：不可随机存取，存储密度低

基本操作

创销、增删改查

初始化

顺序表：需要预分配大片连续空间。若分配空间过小，泽之后不方便拓展容量：若分配空间过大，则浪费内存资源

链表：只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展

静态分配：静态数组（容量不可改变）
动态分配：动态数组（malloc、free）容量可 以改变、但需要移动大量元素，时间代价高

销毁

顺序表：修改Length = 0，系统自动回收空间

链表：依次删除各个结点（free）需要手动free

注：malloc和free必须是成对出现的

插入数据

顺序表：插入或者删除元素要将后继元素都后移或者前移
时间复杂度：O(n) 主要是移动时间代价高
代价相对较高

链表：插入或者删除只需要修改指针即可
时间复杂度：O(n) 主要是查找目标元素时间代价高，代价相对较低

查找数据

顺序表：
按位查找：O(1)
按值查找：O(n)，若表内元素有序，可在O(log2n)时间内找到

链表：
按位查找：O(n)
按值查找：O(n)

链表：表长难以预估、经常要增加/删除元素 使用
顺序表：表长可预估、查询（搜索）操作较多使用

总结问题：
描述顺序表和链表的特点?

顺序表和链表的逻辑结构都是线性结构，都属于线性表。

但是二者的存储结构不同，顺序表采用顺序存储…（特点，带来的优点缺点)；链表采用链式存储（特点，带来的优缺点）

由于采用不同的存储方式实现，因此基本操作的实现效率也不同，当初始化是…；当插入一个数据元素时…；当删除一个数据元素时…；当查找一个元素时…

（以上引导词根据上述内容编写）

//初始化表。构造一个空的线性表L，分配内存空间
InitList(&L);

//销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
DestroyList(&L)

//插入操作。在表L中的第i个位置插入指定元素e
ListInsert(&L,i,e)

//删除操作。删除表L中的第i个位置的元素的值
ListDelete(&L,i,&e)

//按值查找操作。在表L中查找具有给定关键字值得元素 
LocateElem(L,e)

//按位查找操作。获取表中L的第i个位置的元素的值
GetElem(L,i)

//求表长。返回线性表L的长度，即L中数据元素的个数
Length(L)

//输出操作。按前后顺序输出线性表L的所有元素值
PrintList(L)

//判空操作。若L为空表，则返回true，否则返回false
Empty(L)