2.3 线性表的链式存储结构1.单链表定义：实现表的另一种方法是用指针将存储表元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销。为了将存储表元素的所有单元用指针串联起来，我们让每个单元包含一个元素域和一个指针域，其中的指针指向表中下一个元素所在的单元。例如，如果表是a1,a2,…,an ，那么含有元素ai的那个单元中的指针应指向含有元素ai+1的单元(i=1,2,…,n-1)。含有an的那个单元中的指针是空指针nil。此外，通常我们还为每一个表设置一个表头单元header，其中的指针指向开始元素中所在的单元，但表头单元header中不含任何元素。设置表头单元的目的是为了使表运算中的一些边界条件更容易处理。这一点我们在后面可以看到。如果我们愿意单独地处理诸如在表的第一个位置上进行插人与删除操作等边界情况，也可以简单地用一个指向表的第一个单元的指针来代替表头单元。上述这种用指针来表示表的结构通常称为单链接表，或简称为单链表或链表。单链表的逻辑结构如图1所示。表示空表的单链表只有一个单元，即表头单元header，其中的指针是空指针nil。为了便于实现表的各种运算，在单链表中位置变量的意义与用数组实现的表不同。在单链表中位置i是一个指针，它所指向的单元是元素ai-1所在的单元，而不是元素ai所在的单元(i=2,3,…,n)。位置1是指向表头单元header的指针。位置End(L)是指向单链表L中最后一个单元的指针。这样做的目的是为了避免在修改单链表指针时需要找一个元素的前驱元素的麻烦，因为在单链表中只设置指向后继元素的指针，而没有设置指向前驱元素的指针。单链表结构的主要类型可形式地定义为:type pointer=^nodetype nodetype=record data:datatype; next:pointer; end;linklist=pointer;基本运算的实现：过程 Insert(x,p) 功能在表L的位置p处插入元素x，并将原来占据位置p的元素及其后面的元素都向后推移一个位置。例如，设L为a1,a2,…,an，那么在执行Insert(x,p)后，表L变为a1,a2,…ap-1,x,ap,…,an 。若p为End(L)，那么表L变为a1,a2,…,an,x 。若表L中没有位置p，则该运算无定义。实现Procedure Insert(x:datatype;p:pointer);var temp:integer;begin new(temp); temp^.data:=x; temp^.next:= p^.next p^.next:=temp;end;上述算法中，链表指针的修改情况见图2

过程 Delete(p)功能从表L中删除位置p的下一元素。例如，当L为a1,a2,…,an时，执行Delete(p)后，L变为a1,a2,…,ap-1,ap+1,…,an 。当L中没有位置p或p=End(L)时，该运算无定义。实现Procedure Delete(p:pointer);var q:integerbegin q:=p^.next; p^.next:=p^.next^.next; dispose(q);end;说明这个过程很简单，其指针的修改如图3所示。

2.静态链表静态链表：用游标指示数组单元地址的下标值，它属整数类型数组元素是记录类型，记录中包含一个表元素和一个作为游标的整数；具体说明如下:type jid=record data:datatype; next:integer; end;var alist=array[0..maxsize] of jid游标就是。我们可以用游标来模拟指针, 对于一个表L，我们用一个整型变量Lhead(如Lhead=0)作为L的表头游标。。这样，我们就可以用游标来模拟指针，实现单链表中的各种运算。当i>1时，表示第i个位置的位置变量pi的值是数组alist中存储表L的第i-1个元素next值,用p:=alist(p).next后移。照此，我们虽然是用数组来存储表中的元素，但在作表的插人和删除运算时，不需要移动元素，只要修改游标，从而保持了用指针实现表的优点。因此，有时也将这种用游标实现的表称为静态链表。 3.循环链表我们在用指针实现表时，表中最后一个元素所在单元的指针域(next)为空指针nil。如果将这个空指针改为指向表头单元的指针就使整个链表形成一个环。这种首尾相接的链表称为循环链表。在循环链表中，从任意一个单元出发可以找到表中其他单元。图6所示的是一个单链的循环链表或简称为单循环链表。在单循环链表上实现表的各种运算的算法与单链表的情形是类似的。它们仅在循环终止条件上有所不同:前者是p或p^.next指向表头单元；后者是p或p^.next指向空(nil)。在单链表中我们用指向表头单元的指针表示一个表L，这样就可以在O(1)时间内找到表L中的第一个元素。然而要找到表L中最后一个元素就要花O(n)时间遍历整个链表。在单循环链表中，我们也可以用指向表头单元的指针表示一个表L。但是，如果我们用指向表尾的指针表示一个表L时，我们就可以在O(1)时间内找到表上中最后一个元素。同时通过表尾单元中指向表头单元的指针，我们也可以在O(1)时间内找到表L中的第一个元素。在许多情况下，用这种表示方法可以简化一些关于表的运算。

4.双链表单循环链表中，虽然从任一单元出发，可以找到其前驱单元，但需要O(n)时间。如果我们希望能快速确定表中任一元素的前驱和后继元素所在的单元，可以在链表的每个单元中设置两个指针，一个指向后继，另一个指向前驱，形成图8所示的双向链表或简称为双链表。由于在双链表中可以直接确定一个单元的前驱单元和后继单元，我们可以用一种更自然的方式表示元素的位置，即用指向双链表中第i个单元而不是指向其前一个单元的指针来表示表的第i个位置。双链表的单元类型定义如下。 type dupointer=^celltype celltype=recorddata:datatype;next，previous:dupointer;end; dulist=dupointer;和单链的循环表类似，双链表也可以有相应的循环表。我们用一个表头单元将双链表首尾相接，即将表头单元中的previous指针指向表尾，并将表尾单元的next指针指向表头单元，构成如图9所示的双向循环链表。

好资料不能沉

顶啊~~

顶上去啊