资源描述：
《c语言链表解析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、C语言链表解析发布于：2013-01-0211:31浏览量：553编程思想：链表由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的结构指针。我们称之为next指针。最后一个单元的next指针指向NULL；该值由C定义并且不能与其它指针混淆。ANSIC规定NUI丄为零。指针变量是包含存储另外某个数据的地址的变量。因此，如果P被声明为指向一个结构的指钊•，那么存储在P中的值就被解释为内存中的一个位置，在该位置能够找到一个结构。谡吉构的一个域可以通过PTFileName访问，其中FileName是我们要考察的域的名字。如图1所示,这个表含有五个结构，恰好在内存中分配
2、给它们的位置分別是1000,800,712,992和692。笫一个结构的指针含有值800,它提供了第二个结构所在的位置。英余每个结构也都有一个指针用于类似的目的。当然，为了访问该表，我们需要知道在哪里能够找到第一个单ycoA1A1800A2A2712A3A3992A4A4692A5A501000800712992692图1为了执行打印表PrinList(L)或查找表Find(L,key),只要将一个指针传递到该表的第一个元素，然后用一些Next指针穿越该表即可。删除命令可以通过修改一个指针来实现。图2给出在原表中删除第三个元素的结果。图2插入命令需要使用一次malloc调用从系统得到一个新单
3、元并在此后执行两次指针调整。想法通过图3给出，其中虚线表示原来的指针。A1I图3程序设计：上面的描述实际上足以使每一部分都能止常工作，但还是有几处地方可能会出问题：1、并不存在从所给定义出发在表的前面插入元素的真正显性的方法。2、从表的前面实行删除是一个特殊情况，因为它改变了表的起始端；编程的疏忽将会造成表的丢失。3、在执行删除命令时，要求我们记住被删除元素前面的表元。事实上，稍作一个简单的变化就能够解决所有这三个问题。做一个标志节点一一表头（header）o图4表示一个带头头结点的链表。一ED-图4为了避免删除操作相关的一些问题，我们需要编写一个FindPrevious函数，它将返冋我们要
4、删除的表元的前驱元的位置。如果我们使用表头，那么当删除表的第一个元素时，FindPrevious将返回表头的位置。代码实现：按照C的约定，作为类型的List（表）和Position（位置）以及函数的原型都列在所谓的.h头文件中。具体的Node（节点）声明则在.c文件中。代码1、链表的类型声明#ifndef丄ist_HstructNode;typedefstructNode*PtrToNode;typedefPtrToNodeList;typedefPtrToNodePosotion;ListMakeEmpty(ListL);intTsEmpty(ListL);intIsLast(Positi
5、onP,ListL)；PositionFind(ElementTypeX,ListL);voidDelete(ElementTypeX,ListL);PositionFindPrevious(ElementTypeX,ListL);voidInsert(ElementTypeX,ListL,PositionP);voidDeleteList(ListL);structNodeElementTypeElment;PositionNext;}代码2、测试一个链表是否是空表的函数。(头结点的Next指向NUI丄时为空链表)intTsEmpty(ListL){returnL->Next==NULL;
6、}代码3、测试当前位置是否是链表末尾的函数intIsLast(PositionP,ListL){returnP->Next=NULL；}代码4、查找某个结点的函数PositionFind(intx,ListL){PositionP；P=L->Next;while(P!=NULL;&&P->Element!=X)/*如果与运算的前半部分为假，后半部分则不执行*/p=p->Next;returnP;}代码5、找出含有X的表元的前驱元P的FindPrevious函数PositionFindPrevious(ElementTypeX,ListL){PositionP；P=L;while(P->Nex
7、t!=NULL&&P->Next->Element!=X)P=P->Next;returnP;}代码6、删除链表L中的某个元素X函数voidDeleteList(ListL){PositionP,TmpCel1:P=FindPrevious(X,L)if(!TsLast(P,D){TmpCel1=P-〉Next;P->Next=TmpCell->Next;free(TmpCel1);}代码7、链表的插入函数v
