链表

链表由一系列不必再内存中相连的结构组成，每一个结构都含有表元素和指向该元素后继元的结构的指针。这个是定义，看着比较晕。其实链表就是一个表，表中有两个内容，一个是一些基本元素，另外一个是指针，顺着这个指针，可以找到下一个表。如图所示：

链表分有头结点的链表，和没有头结点的链表，上图是有头结点的链表，没有头结点的链表就是把头部分去掉。即

一般来说带有头结点的链表比较常用，在检查是否空表以及在表头插入结点等方面，带有头结点的链表比较有优势。

链表比较常用的操作主要有检查空表，查找节点，插入节点，删除节点。下面编程实现一下：

先来定义一下头结点：

这要用到先下面1) 中的一些定义

void InitList(List L)
{
	header = (Position) malloc(sizeof(struct Node));
	if(header==NULL)
		FataError("out of space");
	header->Next = NULL;
}

链表的定义以及一些初始声明

typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType 

struct Node
{
	ElementType Element;
	Position Next;
};

前四行是利用typedef做的一些声明，这里应用typedef的原因主要有两点：

• 一是方便以后程序移植或修改，例如当我们需要让链表中存放的是double时，则只需要修改就可以了

typedef double ElementType

• 二是能够使程序清晰明确，例如我们看到List就知道这是一个链表指针，这很清晰，其实List等价于

struct Node *List；

检查空表

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

空表就是表的第一个指针指向NULL。

查找结点

Position Find(ElementType X, List L)
{
	Position P;
	P = L->Next;
	while(L!=NULL && L->Element!=X)
		P = P->Next;
	return P;
}

函数返回值是指向我们要查找的结点的指针，我们要查找的结点就是P->Element。需要注意的一个地方就是L!=NULL，L==NULL标志着表的结束，如果没有限定条件L!=NULL，表是要查找过界的。

插入结点

插入结点的步骤如下图(a)所示：

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

删除结点

删除结点的步骤如上图(b)所示：

在执行删除前，首先我们要找到删除的地方

Position FindPrevious(ElementType X, List L)
{
	Position P;
	P=L;
	while(P->Next!=NULL && P_>Next->Element!=X)
		P=P->Next;
	return p;
}

然后再执行删除操作

void Delete(ElementType X,List L)
{
	Position P,Tmp;
	P = FindPrevious(X,L);
	if(!IsLast(P,L))
	{
		Tmp = P->Next;
		p->Next = Tmp->Next;
		free(Tmp);
	}
}
int IsLast(Position P,List L)
{
	return P->Next==NULL;
}

在进行链表操作的时候最好画出相关的示意图，如上面的插入删除图所示，这样可以避免一些错误。

删除整个链表

删除整个链表就相当于依次释放各个节点也就是我们不断通过malloc函数动态创建的指针，声明指针本身是不占用内存空间的，但是malloc函数是动态分配了内存的，因此当删除链表时，应该用free函数释放这些内存，否则会使内存越来越小最终泄露。

void DeleteList(List L)
{
	Position P,Tmp;
	P = L->Next;	//得到头结点，现在P就相当于Header
	L->Next = NULL; //header指向NULL
	while(P!=NULL)
	{
		Tmp = P->Next;
		free(P);
		P=Tmp;
	}
}

这里面会容易产生一个错误：

while(P!=NULL)
	{
		free(P);
		P=P->Next;
	}

这一部分中，如果free(P)了，那么就没有P了，所以程序也就无法得知P->Next是什么了。