1、c 语言链表解析发布于：2013-01-02 11:31浏览量： 553编程思想：链表由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的结构指针。我们称之为 next 指针。最后一个单元的 next 指针指向NULL；该值由 C 定义并且不能与其它指针混淆。ANSI C 规定 NULL 为零。指针变量是包含存储另外某个数据的地址的变量。因此，如果 P 被声明为指向一个结构的指针，那么存储在 P 中的值就被解释为内存中的一个位置，在该位置能够找到一个结构。该结构的一个域可以通过 P-FileName 访问，其中 FileName 是我们要考察的域的名字。如图1所示
2、，这个表含有五个结构，恰好在内存中分配给它们的位置分别是1000，800,712,992和692。第一个结构的指针含有值800，它提供了第二个结构所在的位置。其余每个结构也都有一个指针用于类似的目的。当然，为了访问该表，我们需要知道在哪里能够找到第一个单元。图1为了执行打印表 PrinList（L）或查找表 Find（L，key） ，只要将一个指针传递到该表的第一个元素，然后用一些 Next 指针穿越该表即可。删除命令可以通过修改一个指针来实现。图2给出在原表中删除第三个元素的结果。图2插入命令需要使用一次 malloc 调用从系统得到一个新单元并在此后执行两次指针调整。想法通过图3给出，其中
3、虚线表示原来的指针。图3程序设计：上面的描述实际上足以使每一部分都能正常工作，但还是有几处地方可能会出问题：1、并不存在从所给定义出发在表的前面插入元素的真正显性的方法。2、从表的前面实行删除是一个特殊情况，因为它改变了表的起始端；编程的疏忽将会造成表的丢失。3、在执行删除命令时，要求我们记住被删除元素前面的表元。事实上，稍作一个简单的变化就能够解决所有这三个问题。做一个标志节点表头（header） 。图4表示一个带头头结点的链表。图4为了避免删除操作相关的一些问题，我们需要编写一个 FindPrevious 函数，它将返回我们要删除的表元的前驱元的位置。如果我们使用表头，那么当删除表的第一个
4、元素时，FindPrevious 将返回表头的位置。代码实现：按照 C 的约定，作为类型的 List（表）和 Position（位置）以及函数的原型都列在所谓的.h头文件中。具体的 Node（节点）声明则在.c 文件中。代码1、链表的类型声明#ifndef _List_Hstruct Node;typedef struct Node *PtrToNode;typedef PtrToNode List;typedef PtrToNode Posotion;List MakeEmpty(List L);int IsEmpty(List L);int IsLast（Position P， List
5、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 NodeElementType Elment;Position Next;代码2、测试一个链表是否是空表的函数。 （头结点的 Next 指向 NULL 时为空链表）int IsEmpty(List L)
6、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; return P;代码5、找出含有 X 的表元的前驱元 P 的 FindPrevious 函数Position FindPrevious(ElementType X, List L)Position P；P = L；while（P-Next != NULL
7、 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
