顺序存储
链式存储
顺序存储与链式存储对比
习题
1. 顺序存储
定义：线性表的顺序存储结构是指用一块地址连续的存储空间依次存储线性表的数据元素。这种存储结构称为向量，也称为顺序表。
定义一个顺序表：
typedef struct
{ int data[MAX];
int n;
}SeqList
2. 链式存储
定义：链表是通过一组任意的存储单元来存储线性表中的数据结构的。
定义一个单链表：
typedef struct node
{ int data;
struct node *next;
}Lnode, *LinkList;
LinkList Head;
LNode *p;
p=(LNode *)malloc(sizeod(LNode));
// (*p).data 或p->data访问节点数据
p.free
此外，还有循环链表，双链表，静态链表、动态链表等。动静态链表将在下一篇介绍。
3. 顺序存储与链式存储对比
| 方向 | 顺序存储 | 链式存储 |
|---|---|---|
| 实现难度 | 易 | 适中 |
| 存储开销与密度 | 开销小密度大 | 有额外开销，密度较小 |
| 随机访问 | 效率高 | 效率低 |
| 插入删除操作 | 效率低 | 效率高 |
| 空间分配 | 预先分配足够大空间，容易闲置或溢出 | 不需要预先分配空间 |
| 两者选取条件 | 是 | 否 |
|---|---|---|
| 线性表长度与规模是否可估计？ | 链式表 | |
| 常按序号访问数据？ | 线性表 | |
| 经常插入删除数据？ | 链式表 |
综上：简单来说，常做插入删除选链式表，数据不常变动较稳定选顺序表。
4. 线性表的应用
1.大型程序变量与常量过多，导致大量的重复定义操作，可以考虑使用顺序表。
2.使用顺序表时表过于稀疏，如存储一元多项式，此时使用链式表。
习题：
- 合并两递增顺序（链）表A，B到C使得C也递增。
- 编写函数将单链表（顺序表）逆置。
- 将两个循环单链表合并成一个。
- 单（双）链表删除第i个节点。
- 单（双）链表第i个节点后插入元素为x的节点。
...
