一.绪论

看看就行，需要你会时间空间复杂度分析

二.线性表

1.顺序表

数组。

• 第$i$个元素的地址,$loc(a_i) = loc(a_0)+i*k$ ,其中$k$是单个元素的内存大小
• 插入、删除元素复杂度$O(n)$

2.线性表

链表。 这部分代码要注意空指针的情况

单链表

typedef strcut node{
	Elemtype element; //数据域
	struct node*next //指针域
}Node;

要求会写：

• 单链表结点增加（指针$p$先遍历到要插入的位置前，插入结点指向未插入前的结点的下一个结点，再使未插入前的结点指向插入结点）
• 单链表结点删除（指针$p$先遍历到要删除的位置前，当前结点指向要删除的结点的下一个节点，再释放掉要删除结点的空间）
• 在单链表的基础上加入一个表头结点。表头结点的数据域没有元素，链表为空时表头结点也存在
• 插入删除时间复杂度$O(1)$，读取$O(n)$
• 空间复杂度在需求空间未知时比较优秀

单循环链表

单链表的最后一个结点指向头结点

双向链表

在单链表的基础上再增加指向每个结点前面一个结点的指针

3.线性表的应用

多项式的运算

…

三.堆栈和队列