说明：笔记只作为个人随笔，方便记忆。

1.什么是线性表？

定义：一个线性表是n个数据元素的有限序列。

特征：（1）元素个数n成为表长，n=0时代表空表；（2）元素属于同一数据对象；

（3）ai的直接前驱是ai-1,直接后继是ai+1,a1没有直接前驱，an没有直接后继。

2.线性表的顺序存储(SqList)

最简单的一种顺序映像方法是：令y的存储位置和x的存储位置相邻。

顺序表：用一组地址连续的存储单元依次存放线性表中的数据元素。

基地址：a1，又称为起始地址。

所有数据元素的存储位置均取决于第一个数据元素的存储位置

LOC(ai)=LOC(a1)+（i-1)*C；

优点：随机存取；；

缺点：插入删除操作需要移动较多的数据元素。

3.线性表的链式存储（LinkList)

（1）单链表：用一组地址任意的存储单元存放线性表中的数据元素。

元素+指针=结点；

以结点的序列表示线性表称作为链表。

以线性表中第一个数据元素a1的存储地址作为线性表的地址，称作线性表的头指针；

有时会在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。

单链表是一种顺序存取的结构。

头插法：由表头插入，得到的是逆序；

尾插法：由表尾插入，得到的是正序。

（2）双向链表：除了数据元素还有一个指向前驱的指针，和一个指向后继的指针。

（3）循环链表：最后一个结点的指针域的指针又指回第一个结点的链表。

（4）双向循环链表：将双向链表和循环链表的特点结合。