数据结构-线性表

线性表

线性表是具有相同数据类型的n（n对于等于0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为
$$L=\left(a_1,a_2,\dots ,a_i,a_{i+1},\dots ,a_n\right)$$

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

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

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

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值

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

GetElem(L,i)：按位查找操作。。

其他常用操作：

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

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

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

顺序表的定义

用顺序存储的方式实现线性表

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现

静态分配

动态分配

顺序表的特点

1. 随机访问，即可以在O(1)时间内找到第i个元素

2. 存储密度高，每个节点只存储数据元素

3. 拓展容量不方便

4. 插入、删除操作不方便，需要移动大量元素

线性表的插入与删除

插入

优化

插入操作的时间复杂度

删除

删除操作的时间复杂度

线性表的查找

按位查找

按位查找的时间复杂度

按值查找

按值查找的时间复杂度

单链表的定义

单链表

优点：不要求大片连续空间，改变容量方便

缺点：不可随机存取，要耗费一定空间存放指针

不带头结点的单链表

带头结点的单链表

单链表的插入删除

按位序插入（带头结点）

在第一个位置插入图示

在中间位置插入

在表尾插入

按位序插入（不带头结点）

指定结点的后插操作

指定结点的前插操作

按位序删除（带头结点）

指定结点的删除

单链表的查找

按位查找

按值查找

求表的长度

单链表的建立

尾插法建立单链表

后插操作

正向建立单链表

头插法建立单链表

双链表

双链表的初始化（带头结点）

双链表的插入

解决插入的位置是最后一个结点的情况

双链表的删除

双链表的遍历

循环链表

循环单链表

循环双链表

循环双链表的初始化

循环双链表的插入

双链表的删除

静态链表

静态链表：分配一整片连续的内存空间，各个结点集中安置

用代码定义一个静态链表

顺序表和链表的比较

存储结构

顺序表：

优点：支持随机存取、存储密度高

缺点：大片连续空间分配不方便，改变容量不方便

链表：

优点：离散的小空间分配方便，改变容量方便

缺点：不可随机存取，存储密度低