数据结构单链表

单链表是一个动态存储结构，建立单链表需要动态分配存储空间，依次蔽或肆建立各节点。我想你说的初始化单链表应该是对各个节点的数据域赋初值吧。可以用自定宏轿义函数CreateList_L()完成。在主函数main()中可以先调用CreateList_L()建立两个单链表，如La和Lb，然后进行合并 *** 作，比如可以调用函数MergeList_L()。

我在下面复制一下CreateList_L()函数的实现吧，在主函数中可以调用这个函数。该函数循环建立结点，并插入到表头，也就是逆序的。

void CreateList_L(LinkList &L,int n)//逆位序输入n个元素的值，建立带表头结点的单团梁链线性表L

{ 

int i

LNode * p

L=(LinkList)malloc(sizeof(LNode))

L->next=NULL//先建立一个带头结点的单链表

for(i=ni>0--i)

{ 

p=(LinkList)malloc(sizeof(LNode))//生成新结点

printf("请输入第%d个结点的数据:\n",i)

scanf("%d",&p->data)//输入元素值

p->next=L->next

L->next=p//插入到表头

}

}

单链表

定义：实现表的另一种方法是用指针将存储表元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销。

为了将存储表元素的所有单元用指针串蠢亩联起来，我们让每个单元包含一个元素域和一个指针域，其中的指针指向表中下一个元素所在的单元。例如，如果表是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:datatypep:pointer)

var

temp:integer

begin

new(temp)

temp^.data:=x

temp^.next:= p^.next

p^.next:=temp

end

在上述Insert算法中，位置变量p指向单链表中一个合法位置，要插入的新元素x应紧接在p所指单元的后面。指针p的合法性应在执行Insert运算之前判定。往一个单链表中插入新元素通常在表头或表尾进行，因此p的合法性容易判定。Insert运算所需的时间显然为O(1)。

过程 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:integer

begin

q:=p^.next

p^.next:=p^.next^.next

dispose(q)

end

说明

这个过程很简单，其指针的修改如图3所示。

若要从一个表中删除一个元素x，但不知道它在表中的位置，则应先用Locate(x,L)找出指示要删除的元素的位置，然后再用Delete删除该位置指示的元素。Delete过程所需的时间显然也为O(1)。

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所示的双向链表或简称为双链表。

图8 双链表

由于在双链表中可以直接确定一个单元的前驱单元和后继单元，我们可以用一种更自然的方式表示元素的位置，即用指向双链表中第i个单元而不是指向其前一个单元的指针来表示表的第i个位置。

双链表的单元类型定义如下。 type dupointer=^celltype

celltype=record

data:datatype

next，previous:dupointer

end

dulist=dupointer

和单链的循环表类似，双链表也可以有相应的循环表。我们用一个表头单元将双链表首尾相接，即将表头单元中的previous指针指向表尾，并将表尾单元的next指针指向表头单元

下面仅以双向循环链表为例给出三种基本运算的实现。

(1)在双向循环链表L的位置p处插入一个新元素x的过程Insert可实现如下。 procedure Insert(x:datatdatap:pointervar L:duList)

Var

q:integer

begin

new(q)

q^.data:=x

q^.previous:=p^.previous

q^.next:=p

p^.previous^.next:=q

p^.previous:=q

end

算法Insert中没有检查位置p的合法性，因此在调用Insert之前应保证位置p的合法性。由于插入通常是在表的头尾两端进行的，所以容易检查位置p的合法性。

(2)从双向循环链表L中删除位置p处的元素可实现如下: procedure Delete(p:integervar L:duList)

begin

if (p<>nil)and(p<>L) then

begin

p^.previous^.next:=p^.next

p^.next^.previous:=p^.previous

dispose(p^)

end

end

我打了37分钟，望LZ采纳

---