链表的构造Word文档下载推荐.docx

链表的构造Word文档下载推荐.docx

《链表的构造Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《链表的构造Word文档下载推荐.docx（18页珍藏版）》请在冰点文库上搜索。

链表结点类的数据结构如下：

TAtom*data;

数据指针，用来指向结点的数据。

unsignedlong*RefCount;

整型指针，用来表示结点数据的引用数。

TListNode*next;

链表结点指针，用来指向链表中的下一个结点。

1、链表的基本操作

TList（）;

构造空表

TList（TAtom*a1,TAtom*a2=0,TAtom*a3=0,TAtom*a4=0,TAtom*a5=0,TAtom*a6=0,TAtom*a7=0）;

构造1到7个结点的链表

调用方法:

TListl1（a1）;

该链表包含一个数据为a1的结点

Tlistl2（a1,a2）;

该链表包含两个数据分别为a1,a2的结点

。

Tlistl7（a1,a2,a3,a4,a5,a6,a7）;

该链表包含七个数据分别为a1,a2,…,a7的结点

virtualTList*Clone（）;

virtualTAtom*Copy（）;

TAtom*eval（）;

链表的复制，即复制链表中的每一个结点，而结点的复制是指构造一个

新的结点，但新结点的数据与原结点的数据共享，只把引用计数增加1

TList&

operator=（TList&

r）;

链表的赋值操作，与链表的复制相似，赋值运算符两边的链表将共享数据。

TListl1,l2;

l1=l2;

1.04、链表的显示

virtualvoiddisplay（outtype&

out=wout）const;

若链表的结点为a1,a2,…,an，则它将输出为以下形式：

[a1,a2,…,an]

1.05、链表的长度（结点的个数）

intlength（）;

返回链表中的结点个数

示例：

l:

=[1,2,3,4,5,6,7,8];

l->

length（）=8

=[];

length（）=0

TListNode*first（）const；

返回指向链表头结点的指针

TListNode*last（）const；

返回指向链表尾结点的指针

virtualTAtom*Part（intn）;

返回链表的第n（n是int类型）个结点的数据的指针（该数据不被复制）

n从1开始计数

l1:

=[10,20,30,40];

l1->

Part

（1）=10

l2:

=[a,b,c,[e,f]];

l2->

Part（4）=[e,f]

virtualTAtom*Part（TBigIntn）;

返回链表的第n（n是TBigInt类型）个结点的数据的指针（该数据不被复制）

virtualTAtom*Part（TNumbern）;

返回链表的第n（n是TNumber类型）个结点的数据的指针（该数据不被复制）

virtualTAtom*HEAD（）const;

返回链表头结点的数据的指针（该数据被复制）

virtualTAtom*TAIL（）const;

返回链表尾结点的数据的指针（该数据被复制）

virtualTList*Rest（）;

原表不变

构造新表返回,它是把原表的第一个结点删除之后的链表。

=[1,2,3,4];

Rest（）=[2,3,4]

=[a];

Rest（）=[]

TAtom*pop（）;

修改原表l

返回l的第一个结点的数据的指针（该数据不被复制），

并把l的头指针直接指向l的第二个结点，第一个结点不删除。

1.07、链表的插入

virtualvoidappend（TAtom*data）;

修改原表

不论数据data是否在原表中，都先把数据data构造成结点，然后把这个结点直接插入原表的表尾,。

不去掉重复结点。

data不复制。

append（3）;

链表l被修改为[1,2,3,4,3]

virtualvoidappend（TListNode*data）;

不论结点data是否在原表中，都把它直接插入原表的表尾。

data不复制。

voidgappend（TAtom*v）;

如果数据v已在原表中，则不进行任何操作，否则把v直接插入原表的表尾。

v不复制。

gappend（3）;

链表l未被修改，仍是[1,2,3,4]

gappend（5）;

链表l被修改为[1,2,3,4,5]

TList*lappend（TAtom*v）;

不论v是否在原表中，都把v插入原表的表头，形成新表，

然后再去掉新表中的重复结点后返回。

注意数据v被复制后插入链表。

=[2,3,3,5,5,7];

lappend（7）=[7,2,3,5]

TList*sappend（TAtom*v）;

若v已在原表中，返回原表的复制。

若v不在原表中，把v插入原表的表尾，形成新表返回。

结果可能还有重复结点（因为不去掉原表中的重复结点）。

（sappend（）与gappend（）实现方式不同，但功能相同。

）

l1->

sappend（8）=[2,3,3,5,5,7,8]

=[2,3,7,5,5,3];

l2->

sappend（7）=[2,3,7,5,5,3]

virtualvoiddmerge（TList*l）;

链表的合并，即把链表l的结点直接插入原表的表尾,不去掉重复结点。

链表l不复制。

注意：

不是把l作为子表插入

示例：

l1:

=[1,2,3];

l2:

=[3,4,5];

dmerge（l2）;

链表l1被修改为[1,2,3,3,4,5]

TList*merge（TList*l）;

原表不变，链表l也不变。

链表的合并，即先把原表和链表l都复制之后，再把复制之后链表l的结点插入复制之后原表的表尾，形成新表返回，不去掉重复结点。

=[1,2,3];

=[3,4,5];

merge（l2）=[1,2,3,3,4,5]

virtualvoiddinsert（TAtom*data,intpos=1）;

在原表的第pos个结点之前直接插入data，此时data是数据指针。

若原表的长度为n，则1<

=pos<

=n+1,pos缺省时插入在表头。

=[1,2,3,4,5,6,7];

dinsert（10,8）;

链表l1被修改为[1,2,3,4,5,6,7,10]

dinsert（10,1）;

链表l2被修改为[10,1,2,3,4,5,6,7]

l3:

l3->

dinsert（10,3）;

链表l3被修改为[1,2,10,3,4,5,6,7]

virtualvoiddinsert（TListNode*data,intpos=1）;

在原表的第pos个结点之前直接插入data，此时data是结点指针。

virtualvoiddinsert（TList*list,intpos=1）;

在原表的第pos个结点之前直接插入链表list的结点。

链表list不复制。

注意：

不是把list作为子表插入

=[1,2,3,4,5,6,7];

dinsert（[1,2,3],5）;

链表l被修改为[1,2,3,4,1,2,3,5,6,7]

virtualvoiddinsert（TAtom*data,TListNode*pos=0）;

修改原表

在原表的pos所指向的结点之前直接插入数据data，此时data是数据指针。

pos缺省时或pos=0时插入在表头。

virtualvoiddinsert（TListNode*data,TListNode*pos=0）;

在原表的pos所指向的结点之前直接插入结点data，此时data是结点指针。

virtualvoiddinsert（TList*list,TListNode*pos=0）;

在原表的pos所指向的结点之前直接插入链表list的结点。

TList*insert（TAtom*data,TListNode*pos=0）;

在复制的原表中pos所指向的结点之前直接插入数据data，形成新表返回，此时data是数据指针。

TList*insert（TListNode*data,TListNode*pos=0）;

在复制的原表中pos所指向的结点之前直接插入结点data，形成新表返回，此时data是结点指针。

TList*insert（intpos,TAtom*data）;

把数据data插入链表的第pos个结点之前,形成新表返回。

=n+1

注意数据data被复制后插入链表。

insert（8,10）=[1,2,3,4,5,6,7,10]

insert（1,10）=[10,1,2,3,4,5,6,7]

insert（3,10）=[1,2,10,3,4,5,6,7]

1.08、隶属关系判断

intfindindex（TAtom*v）;

找到数据v在链表中第一次出现的位置，返回该位置结点的索引值，若v不在链表中，则返回0。

=[1,2,a,b,c,a];

findindex（a）=3

=[1,2,[a,b],3,[a,b]];

findindex（[a,b]）=3

=[1,2,3,4];

findindex（5）=0

TAtom*find（TAtom*v）;

找到数据v在链表中第一次出现的位置，返回指向该位置结点的数据的指针，若v不在链表中，则返回NULL。

TListNode*findnode（TAtom*v）;

找到数据v在链表中第一次出现的位置，返回指向该位置结点的指针，若v不在链表中，则返回NULL。

intIssub（TList*l1,TList*l2）;

//外部函数

如果l1是l2的子表，则返回1，否则返回0。

l1=l2时，返回1。

Issub（[1,2,3],[1,2,3,4,5,6,7]）=1

Issub（[1,2,3],[1,2,3]）=1

Issub（[1,2,3],[2,3,4]）=0

TList*Union（TList*l）;

求原表和链表l的并集，形成新表返回，它将首先包含原表的全部结点，再把链表l中的不重复的结点加入。

原表和链表l都被复制。

=[1,2,3,3,3,5,5];

=[1,2,5,7,7,8,9];

Union（l2）=[1,2,3,3,3,5,5,7,8,9]

voidgunion（TList*l）;

求原表和链表l的并集，把链表l中的不重复的结点直接加入原表，返回修改后的原表。

链表l不复制。

gunion（l2）;

链表l1被修改为[1,2,3,3,3,5,5,7,8,9]

TList*Intersect（TList*l）;

求原表和链表l的交集，形成新表返回。

=[2,3,6,7];

l1>

Intersect（l2）=[2,3]

TList*Minus（TList*l）;

求原表和链表l的差集（原表减去链表l），形成新表返回。

Minus（l2）=[1,4]

TList*lunion（）;

形成新表返回，它是把原表的重复结点删除之后的链表，

即返回的链表不再包含重复结点。

=[1,1,1,2,2,2,3,3,3];

lunion[]=[1,2,3]

1.10、链表的比较

boolequal（TList*l）;

比较两个链表是否相等，两个链表相等是指所有对应的结点的数据都类型一致且相等。

equal（[1,2,3,4]）=true

equal（[2,1,4,3]）=false

1.11、替代和求逆

TList*replace（inti,TAtom*v）;

用数据v替换链表的第i个结点,形成新表返回。

若链表的长度为n，则1<

=i<

=n。

注意数据v被复制后替换。

replace（1,a）=[a,2,3,4]

=[a,b,c,d];

replace（2,[c,d]）=[a,[c,d],c,d]

TList*Inverse（）;

构造原表的逆表，形成新表返回。

Inverse（）=[4,3,2,1]

1.12、删除链表的结点

virtualvoiddremove（intpos）;

直接在原表上删除第pos个结点

dremove（3）;

链表l被修改为[10,20,40]

virtualvoiddremove（TlistNode*data）;

直接在原表上删除data所指向的结点

virtualvoiddremove（TAtom*data）;

首先找到数据data在原表上第一次出现的位置，然后直接在原表上删除该位置上的结点。

=[10,20,30,20,50];

dremove（20）;

链表l被修改为[10,30,20,50]

TList*remove（intpos）;

首先复制原表，然后在复制的原表上删除第pos个结点。

形成新表返回。

remove（3）=[10,20,40]

remove（0）=[10,20,30,40]

TList*remove（TListNode*data）;

首先复制原表，然后在复制的原表上删除data所指向的对应位置的结点。

TList*remove（TAtom*data）;

首先复制原表，然后在复制的原表上找到数据data第一次出现的位置，并且删除该位置上的结点。

remove（20）=[10,30,20,50]

virtualvoidcleardata（）;

直接在原表上删除其所有结点，使之成为空表。

以下宏一般用于系统函数

#defineFIRST（l）（l->

Part

（1））

#defineSECOND（l）（l->

Part

（2））

#defineTHIRD（l）（l->

Part（3））

#defineFOURTH（l）（l->

Part（4））

#defineFIFTH（l）（l->

Part（5））

以下宏一般用于链表的遍历

#defineFIRSTNODE（l）（l->

first（））

#defineNEXT（l）（l->

next）

#defineRNEXT（l）（l=l->

#defineDATA（l）（l->

getdata（））

3.1、关于链表操作的两种实现方式

在本系统中我们为有关链表的一些常用的基本操作提供了两种实现方式，即构造性的实现和破坏性的实现。

构造性的实现是指不修改被操作的原表本身，实现时通常先对原表进行复制，然后在复制的原表上进行相应的操作，返回一个新表；

破坏性的实现是指直接在原表上进行操作，即原表本身被修改，这样的函数是没有返回值的。

编程时应根据具体环境和需要选择其中的一种实现。

删除链表的第n个结点的操作有以下两个实现函数，它们的函数功能相同，但实现方式不同：

virtualvoiddremove（intn）;

//破坏性的实现

直接在原表上删除第n个结点

TList*remove（intn）;

//构造性的实现

原表不变

首先复制原表，然后在复制的原表上删除第n个结点。

3.2、关于链表的遍历方法

对链表的每一个结点进行遍历的方法如下（以下三种写法均可）：

TList*l;

TListNode*tmp;

//tmp指向链表的结点

一般的链表遍历的写法：

for（tmp=l->

first（）;

tmp;

tmp=tmp->

{

TAtom*a=tmp->

getdata（）;

//获得结点的数据

}

利用宏的链表遍历的写法：

for（tmp=FIRSTNODE（l）;

RNEXT（tmp））

TAtom*a=DATA（tmp）;

或者

tmp=NEXT（tmp））

注：

本说明书中友元函数和外部函数都已注明，其它未注明者均为TList类的成员函数。