c语言链表解析.doc

c语言链表解析
发布于：2013-01-02 11:31
浏览量： 553
编程思想：
链表由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的结构指针。我们称之为next指针。最后一个单元的next指针指向NULL；该值由C定义并且不能与其它指针混淆。ANSI C规定NULL为零。

指针变量是包含存储另外某个数据的地址的变量。因此，如果P被声明为指向一个结构的指针，那么存储在P中的值就被解释为内存中的一个位置，在该位置能够找到一个结构。该结构的一个域可以通过P->FileName访问，其中FileName是我们要考察的域的名字。如图1所示，这个表含有五个结构，恰好在内存中分配给它们的位置分别是1000，800,712,992和692。第一个结构的指针含有值800，它提供了第二个结构所在的位置。其余每个结构也都有一个指针用于类似的目的。当然，为了访问该表，我们需要知道在哪里能够找到第一个单元。

图1
为了执行打印表PrinList（L）或查找表Find（L，key），只要将一个指针传递到该表的第一个元素，然后用一些Next指针穿越该表即可。
删除命令可以通过修改一个指针来实现。图2给出在原表中删除第三个元素的结果。

图2
插入命令需要使用一次malloc调用从系统得到一个新单元并在此后执行两次指针调整。想法通过图3给出，其中虚线表示原来的指针。

图3
程序设计：
上面的描述实际上足以使每一部分都能正常工作，但还是有几处地方可能会出问题：
1、并不存在从所给定义出发在表的前面插入元素的真正显性的方法。
2、从表的前面实行删除是一个特殊情况，因为它改变了表的起始端；编程的疏忽将会造成表的丢失。
3、在执行删除命令时，要求我们记住被删除元素前面的表元。
事实上，稍作一个简单的变化就能够解决所有这三个问题。做一个标志节点——表头（header）。图4表示一个带头头结点的链表。

图4
为了避免删除操作相关的一些问题，我们需要编写一个FindPrevious函数，它将返回我们要删除的表元的前驱元的位置。如果我们使用表头，那么当删除表的第一个元素时，FindPrevious将返回表头的位置。

代码实现：
按照C的约定，作为类型的List（表）和Position（位置）以及函数的原型都列在所谓的.h头文件中。具体的Node（节点）声明则在.c文件中。
代码1、链表的类型声明
#ifndef _List_H

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Posotion;

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);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);

struct Node
{
ElementType Elment;
Position Next;
}

代码2、测试一个链表是否是空表的函数。（头结点的Next指向NULL时为空链表）
int IsEmpty(List L)
{
return L->Next == NULL;
}

代码3、测试当前位置是否是链表末尾的函数
int IsLast（Position P， List L）
{
return P->Next == NULL；
}

代码4、查找某个结点的函数
Position Find(int x, List L)
{
Position P；

P = L->Next;
while(P != NULL; && P->Element != X) /*如果与运算的前半部分为假，后半部分则不执行*/
p = p->Next;

return P;
}

代码5、找出含有X的表元的前驱元P的FindPrevious函数
Position FindPrevious(ElementType X, List L)
{
Position P；

P = L；
while（P->Next != NULL && P->Next->Element != X）
P = P->Next;

return P;
}

代码6、删除链表L中的某个元素X函数
void DeleteList(List L)
{
Position P，TmpCell；

P = FindPrevious(X, L)

if（！IsLast（P, L））
{
TmpCell = P->Next;
P->Next = TmpCell->Next;
free(TmpCell);
}
}

代码7、链表的插入函数
void Insert(ElementType X, List L, Position P)
{
Position TmpCell；

TmpCell = malloc（sizeof（struct Node））；
if（TmpCell == NULL）
FataError（“Out of space!”）;

TmpCell->Elment = X;
TmpCell->Next = P->Next;
P->Next = TmpCell
}