内容发布更新时间 : 2024/6/8 23:59:45星期一 下面是文章的全部内容请认真阅读。

c语言链表解析

编程思想：

链表由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的结构指针。我们称之为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））