链表概述
链表是由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的结构的指针，称之为Next指针。最后一个单元的Next指针指向NULL；该值由C定义并且不能与其他指针混淆。ANSI C 规定NULL为零。
链表例程
类型声明
typedef int ElementType;//数据元素类型
struct Node;//结点
typedef struct Node *PtrToNode;//指向结点的指针
typedef PtrToNode List;//链表
typedef PtrToNode Position;//位置
struct Node
{
ElementType Element;//表元素
Position Next;//指向下一结点（后继元）的指针
};
测试一个链表是否为空表
int IsEmpty(List L)//传进的是头结点
{
return L->Next == NULL;
}
测试当前位置是否为链表的末尾（配合删除结点使用）
int IsLast(Position P, List l)
{
return P->Next == NULL;
}
Find 例程（返回关键字首次出现的位置）
Position Find(ElementType X, List L)
{
Position P;
P = L->Next;//从第一个结点开始寻找
while(P != NULL && P->Element != X)//直到找到或者到达链表末尾
P = P->Next;
return P;
}
链表的插入例程（将元素X插入到位置P之后）
void Insert(ElementType X, List L, Position P)
{
Position TmpCell;
TmpCell = malloc(sizeof(struct Node));//申请空间
/*malloc(sizeof(struct Node))是合法的，但是它并不是给结构体分配足够的空间，只是给指针分配一个空间*/
if(TmpCell == NULL)//申请失败
exit(-1);
TmpCell->Element = X;//插入结点
TmpCell->Next = P->Next;
P->Next = TmpCell;
}
FindPrevious 例程（返回表元的前驱元的位置）
Position FindPrevious(ElementType X, List L)
{
Position P;
P = L;
while(P->Next != NULL && P->Next->Element != X)//直到P的下一结点元素与关键字相等或者到达链表尾
P = P->Next;
return P;
}
链表的删除例程（与FindPrevious 例程，IsLast()一起使用）
void Delete(ElementType X, List L)
{
Position P, TmpCell;
P = FindPrevious(X, L);
if(!IsLast(P, L))//如果找到元素X，则删除之；否则表示链表中不存在X
{
TmpCell = P->Next;
P->Next = TmpCell->Next;
free(TmpCell);
}
}
删除一个链表
void DeleteList(List L)
{
Position P, Tmp;
P = L->Next;
L->Next = NULL;
while(P != NULL);
{
Tmp = P->Next;
free(P);//释放结点
P = Tmp;
}
}
双链表
在结构体中添加一个域，使它包含指向前一个单元的指针。
struct Node
{
ElementType Element;//表元素
Position Last， Next;
//指向上一结点（前继元）、下一结点（后继元）的指针
};
循环链表
让最后的单元反过来直指第一个单元的做法。
