数据结构与算法分析笔记02：链表

1.抽象数据类型（abstract data type,ADT）是一些操作的集合。
2.链表由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元结构的指针。我们称之为Next指针。最后一个单元的Next指针指向NULL；该值由C定义并且不能与其他指针混淆。ANSI C规定NULL为零。



链表的类型声明

```c
#ifndef _List_H
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X,List L);
void Delete(ElementType X,List L);
Postion FindPrevious(ELementType X,List L);
void Insert(ELementType X,List L,Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
 #endif  /*_List_H */
 struct Node
 {
ElementType Element;
Position Next;
} 

测试一个链表是否是空表的函数

```c
int 
IsEmpty(List L)
{
return L->Next ==NULL;
}

测试当前位置是否是链表的末尾函数

int
IsLast(Position P,List L)
{
rerurn 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;
}

链表的删除例程

void
Delete(ElementType X,List L)
{
Position P,TmpCell;
P = FindPrevious(X,L);
if(!Islast(P,L))
{
TmpCell =P->Next;
p->Next = TmpCell->Next;
free(TmpCell)
}
}

链表的插入例程

void
Insert(ELementType X,List L,Position P)
{
Position TmpCell;
TmpCell = malloc(sizeof(struct Node));
if (TmpCell == NULL)
	FatalError("Out of space!!!");
TmpCell->Element = X;
TmpCell->Next = P->Next;	
P->Next = TmpCell;
}

双链表
只要在数据结构上附加一个域，使它包含指向前一个单元的指针即可。

循环链表
最后的单元反过来直指第一个单元

使用链表的三个例子：
1.表示一元多项式的简单方法
2.某些特殊情况下以线性时间进行排序的一种方法
3.大学的课程注册

链表的游标实现
在链表的指针实现中又两个重要的特点：
1.数据存储在一组结构体中。每一个结构体包含有数据以及指向下一个结构体的指针。
2.一个新的结构体可以通过调用malloc而从系统全局global memory得到，并可通过调用free而被释放。