线性表
线性表的定义
线性表零个或多个数据元素的有限序列。
若将线性表记为（a1, …,ai-1, ai, ai+1, …, an)，则表中ai-1领先于ai，ai领先于ai+1，称ai-1时ai的直接先驱元素，ai+i是ai的直接后继元素。当i=1,2,…,n-1时，ai有且仅有一个直接后继，当i=2,3,…,n时，ai有且仅有一个直接前驱。
线性表元素的个数n(n >=0)定义为线性表的长度，当n=0时，称为空表。
线性表的抽象数据类型
1
2
3
4
5
6
7
8
9
10
11
12
13
ADT 线性表(List)
Data
线性表的数据对象集合为{a1,a2,...,an}，每个元素的类型均为DataType。其中，除第一个元素a1，每个元素有且仅有一个直接前驱元素，除了最后一个元素an外，每一个元素有且仅有一个直接后继元素。数据元素之间的关系是一对一的。
Operation
InitList(*L): 初始化操作，建立一个空的线性表L。
ListEmpty(L): 若线性表为空，返回true，否则返回false
ClearList(*L): 将线性表清空
GetElem(L, i, *e): 将线性表L中的第i个位置元素值返回给e
LocateElem(L, e): 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败
ListInsert(*L, i, e): 在线性表中的第i个位置插入新元素e。
ListDelete(*L, i, *e): 删除线性表L中第i个位置元素，并用e返回其值。
ListLength(L): 返回线性表L的元素个数
endADT
实现两个线性表集合A和B的并集操作。即：把存在集合B中但并不存在A中的数据元素插入到A中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*将所有的在线性表Lb中但不在La中的数据元素插入到La中*/
void union(List *La, List Lb)
{
int La_len, Lb_len, i;
ElemType e; /*声明与La和Lb相同的数据元素e*/
La_len = ListLength(La); /*求线性表的长度*/
Lb_len = ListLength(Lb);
for (i=1; i<=Lb_len; i++)
{
GetElem(Lb, i, e); /*取Lb中第i个数据元素赋给e*/
if(!LocateElem(La,e,equal)) /*La中不存在和e相同的数据元素*/
ListInsert(La, ++La_len, e);
}
}
线性表的顺序存储结构
线性表的顺序存储结构，指的是用一段地址连续的存储单元一次存储线性表的数据元素。
线性表的链式存储结构
为了表示每个数据元素a1与其直接后继数据元素ai+1之间的逻辑关系，对于数据元素a1来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node)
n个结点(ai的存储映像)链结成一个链表，即为线性表(a1,a2,…,an)的链式存储结构，因为此链表的每个的结点中只包含一个指针域，所以叫做单链表。
链表中第一个结点的存储位置叫做头指针。
链表的最后一个结点为空（通常用null或”^”表示）
单链表的第一个结点前附设一个结点，称为头结点。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。
头指针与头结点的异同
头指针
- 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
- 头指针具有标识作用，所以常用头指针冠以链表的名字
- 无论链表是否为空，头指针均不为空。头指针是链表的必要元素
头结点
- 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
- 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
- 头结点不一定是链表必须要素
参考资料：
