我所理解的链表
虽然使用数组可以很方便的查找每一个元素，但如果要插入或删除元素时，因为要移动大量的元素，所以需要一定的运行时间，而且代码也变的复杂。为了能够方便的删除和插入元素，我们一般不采用顺序存取结构，而采用链表存取。根据链表中结点的性质，我把它分为两种，一种是使用指针来指向它的后继（为简单起见，我暂时只讲一下单向链表，至于双向链表和循环链表，大家可以在单向链表的基础上做一定扩展即可），每一个结点的空间由系统动态分配，我们称之为动态链表；另一种是用游标（相当于指针）来指向它的后继，每一个结点的空间由程序建立的“模拟空间分配站”来分配，这个“模拟空间分配站”实际上是一个事先给定足够空间的结构数组，它为链表的结点分配空间，链表上释放的结点空间再返回给“模拟空间分配， 站”，由于这个“模拟空间分配站”的空间是由系统事先静态分配好空间的，所以称这种链表为静态链表。静态链表满足了那些不支持指针的高级语言（如BASIC和FORTRAN）需要链表的要求，它的使用方法和动态链表极为相似。 首先我们来了解动态链表。它的类型声明和基本操作如下表所示： //-----------线性表的单链表存储结构------------- typedef struct Node{ ElemType data; struct Node *next; } *LNode, *LinkList; //----------线性表的单链表基本操作------------ LinkList InitList(void); //构造一个空的线性表 void DestroyList(LinkList *L);//初始条件：线性表L已存在。 操作结果：销毁线性表L。 LinkList MakeEmpty(LinkList L);//初始条件：线性表L已存在。 操作结果：将线性表L重置为空表。 int IsEmpty(LinkList L);//初始条件：线性表L已存在。 操作结果：判断线性表是否为空表。 int ListLength(LinkList L);//初始条件：线性表L已存在。 操作结果：返回线性表L结点的个数。 LNode IsLast(LinkList L); //初始条件：线性表L已存在。 操作结果：返回线性表L的最后一个结点（尾结点）。 LNode NewLNode(ElemType X);//构造一个数据域为X的新结点 LNode FindPrefious(ElemType X, LinkList L);//初始条件：线性表L已存在。 操作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。 void ListDelete(LNode Pre);//初始条件：线性表L中结点P已找到。 操作结果：删除该结点。 void ListInsert(LNode Pre, LNode S);//初始条件：线性表L中结点P已找到，新结点S已构造。 操作结果：在该结点之前插入新结点X。 注意：为操作方便起见，在执行函数void ListDelete(LNode Pre, LinkList L) 和void ListInsert(LNode Pre, LNode X, LinkList L)时，通常把结点P的前驱Pre作为实参。而且这两个函数通常与函数LNode FindPrefious(ElemType X, LinkList L)一起使用，即先查找结点，再执行插入或删除操作。
评论