线性表的特点
只有唯一一个首元素
只有唯一一个尾元素
除首元素外，每个元素只有唯一一个前驱
除尾元素外，每个元素只有唯一一个后继
2.1 线性表的类型定义
一个线性表是n个数据元素的有限序列
2.2 线性表的顺序表示和实现
用一组地址连续的存储单元（数组）依次存储线性表的数据元素，即逻辑上相邻的数据元素在物理存储结构上也是相邻的。
存储位置关系
特点
可以随机存取
删除、插入元素较慢
结构定义
- 动态分配内存的顺序存储结构
typedef struct{
ElemType *elem; //存储空间首地址
int length; //当前长度
int listsize; //分配的存储容量
}SqlList;
- 静态顺序存储结构
#define LIST_INIT_SIZE 100
typedef struct{
ElemType elem[LIST_INIT_SIZE];
int length; //当前长度
int listsize; //分配的存储容量
}SqlList;
插入和删除的注意点
由于是顺序存储结构，在中间插入或删除元素时，需要移动元素，假若顺序线性表非常长时， 则插入和删除就会较为耗时，时间复杂度为
插入和删除元素平均移动次数
2.3 线性表的链式表示和实现
2.3.1 线性链表
单链表
链表使用一组任意的存储单元存储线性表的数据元素，相邻元素通过指针进行相连，也就是逻辑上相邻的数据元素在物理存储上不必相邻。
结点组成
-
数据域
存储数据信息
-
指针域
存储指向下一个结点的指针
结构定义
typedef struct LNode{
ElemType data; //存储数据
struct LNode *next; //存储下一个元素的位置
}LNode, * LinkList;
头指针
通常我们在单链表的第一个结点之前添加一个头结点，头结点可以不存储数据，也可以存储链表的长度等信息，头结点指向链表的第一个结点。
特点
-
不能随机存取
要找一个元素只能从第一个结点开始，一直沿着这条链找下去，时间复杂度为
-
插入、删除结点很快
只需断开链表，插入、删除结点即可（不算上找到对应操作位置的时间），算上找到操作位置的时间，总的时间复杂度为
链表的建立
-
头插法
每次新结点都插在头结点后面
元素的顺序与插入的顺序相反，先插入的在最后面，后插入的在最前面
-
尾插法
每次新结点都插入在最后面，需要维护一个尾指针来记录最后一个结点的位置.
元素的顺序与插入的顺序相同
静态链表
使用数组存储整个链表，用元素的下标代替指针。
结构定义
#define MAXSIZE 100
typedef struct{
ElemType data;
int next;
}component, SLinkList[MAXSIZE];
查找
- 操作和单链表一致
添加/删除结点
- 添加结点需要知道数组中有哪些位置是空的，因此需要维护一条所有未被使用的数组分量的链表
- 添加结点时，从该链表中取下一个结点使用
- 删除结点时，将删除的结点链接到该链表中
2.3.2 循环链表
将链表中最后一个结点的指针不再指向NULL,而是指向头结点，从而形成循环。
与单链表的差异
- 单链表在判断是否搜寻到链表尾部时，使用
这个判断条件
- 循环链表在判断是否搜寻到链表尾部时，使用
这个判断条件
2.3.3 双向链表
上述的链表都为单向链表，只能沿着链表从前往后查找，即每个节点只储存了指向后继的指针，在双向链表中，每个节点不仅存储了指向后继的指针，还存储了指向前驱节点的指针（head->next == NULL）
结构定义
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior;
struct DulNode *next;
}DuLNode, * DuLinkList;
