线性表（Linear List）
由同种数据元素构成有序序列的线性结构
- 表中元素个数称为线性表的长度
- 线性表没有元素时，称为空表
- 表起始位置称表头，结束位置称表尾
抽象数据类型描述
类型名称：线性表(List)
数据对象集：n(>=0)个元素构成的有序序列
操作集：假定线性表类型为List，其中具体的一个线性表为L，里面有个元素类型为ElementType的x，主要操作有：
- List MakeEmpty():初始化一个空线性表L
- ElementType FindKth(int K,list L):根据位序k，返回相应元素
- int Find(ElementType X,List L):在线性表L中查找X的第一次出现位置：
- void insert(ElementType X, int i, List L):在位序i前插入一个新元素X
- void Delete(int i, List L):删除指定位序i的元素
- int Length(List L):返回线性表L的长度n
线性表的存储
顺序存储
利用数组的连续存储空间顺序存放线性表的各元素
由于是连续，所以要定义一个Last来存储最后一个元素，表明结尾的位置
typedef struct LNode*List; struct LNode{ ElementType Data[MAXSIZE]; int Last; }; struct LNode L; List PtrL;
主要操作的实现
初始化
List MakeEmpty() { List PtrL; PtrL = (List)malloc(sizeof(struct LNode)); ptrL->Last = -1; return PtrL; }
查找
int Find(ElementType X,List PtrL) { int i = 0; while(i<=PtrL->Last && PtrL->Data[i]!= X ) i++; if(i>PtrL->Last) return -1; else return i; }
这种查找成功的平均比较此时为(n+1)/2,平均时间性能为O(n)
线性表推广
广义表（Generalized List）
对于线性表 n个元素都是基本的单元素
对于广义表 这些元素不仅可以是单元素也可以是另一个广义表
typedef struct GNode *Glist; struct GNode{ int Tag; /*标志域：0表示节点是单元素，1表示结点是广义表*/ union { ElemenType Data; /*子表指针域Sublist与单元素数据域Data复用，即共用存储空间*/ GList SubList; }URegion; GList Next; /*指向后继结点*/ };
多重链表
广义表实际上就是多重链表
多重链表中的结点可能同时隶属多个链
指针域会有多个，例如上面代码行中的Next和SubList两个指针域
但双向链表中包含两个指针域，并不是多重链表
用途
基本上树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。
矩阵
采用典型的多重链表——十字链表来代替二维数组来存储稀疏矩阵
（二维数组存储稀疏矩阵缺点：1.会造成大量空间浪费
2.数组大小需要事先确定）
- 只存储矩阵非0元素项
结点的数据域：行坐标Row、列坐标Col、数值Value
- 每个结点通过两个指针域把同行同列串起来
行指针（向右指针）Right
列指针（向下指针）Down
