线性表教学课件

第2章线性表

2.1线性表的基本概念

2.2线性表的类型定义

2.3线性表的顺序表示和实现

2.4线性表的链式表示和实现

2.4.1线性链表

II2.4.2循环链表

2.4.3双向链表

2.5一元多项式的表示及相加

06:441

本章学习导读

俵喉表（Linearlist）是最简单且最常用的一种数据结

构。这种结构具有下列特点：存在一个唯一的没有前驱的

（头）数据元素；存在一个唯一的没有后继的（尾）数据

元素；此外，每一个数据元素均有一个直接前驱和一个直

接后继数据元素。

通过本章的学习，我们应能掌握线性表的逻辑结构和

存储结构，以及线性表的基本运算以及实现算法。

06:442

2.1线性表的基本概念

线性表由一组具有相同属性的数据元素构成。数据元素的含

义广泛，在不同的具体情况下，可以有不同的含义。

1.线性表的定义

'线性表L是n(n>0)个具有相同属性的数据元素%,a2,

a3,....an组成的有限序列，其中序列中元素的个数n称为线性表

的长度。口

当n=0时称为空表，即不含有任何元素。

常常将非空的线性表(n>0)记作：

(ara2,…分)

这里的数据元素药(lWi皂n)只是一个抽象的符号，其具体含

义在不同的情况下可以不同。

06:443

例1、26个英文字母组成的字母表

(A,B,C、・・.、Z)

例2、从1978年到1983年各种型号的计算机拥有量的变化情况。

(6,17,28,50,92,188)

例3、

表2-1学生基本情况表下

学号〃姓名一性别一年龄「班级Q籍贯/

20021418^吴小军d男Q20-计算机系024^天津21

20021419P王乾龙*男Q20计算机系024c山东淄博©

200214200李晋东2男Q19^计算机系。24・1上海」

200214214-1高小珊/女。19・」计算机系02小，辽宁丹东，

20021422/杜都」女二20*3计菖机系02务山东烟台值

06:444

从以上例子可看出线性表的逻辑特征是：

在非空的线性表，有且仅有一个开始结点药,它没有直接

前趋，而仅有一个直接后继a2；

有且仅有一个终端结点a。，它没有直接后继，而仅有一个

直接前趋an.1；

其余的内部结点%（2皂i皂n-1）都有且仅有一个直接前趋aM

和一个直接后继ai+1o

线性表是一种典型的线性结构。

数据的运算是定义在逻辑结构上的，而运算的具体实现则

是在存储结构上进行的。

06:445

2.1线性表的类型定义

抽象数据类型线性表的定义如下：

ADTList｛

数据对象

D=｛aJa；eElemSet,i=1,2,,n,n>0｝

数据关系

R1=<<ah1,a/|aM,eD,i=2,,n｝

基本操作：

｛结构初始化｝｛销毁结构｝

｛引用型操作｝｛加工型操作｝

怜叫List

6

｛结构初始化｝

InitList(&L)

操作结果：构造一个空的线性表L。

｛销毁结构｝

DestroyList(&L)

初始条件：线性表L已存在。

操作结果：销毁线性表L。

｛引用型操作｝7操作的结果不改变线性表的结构)

ListEmpty(L)

初始条件：线性表L已存在。

操作结果：若L为空表，则返回True,否则FALSE。

06:447

ListLength(L)

初始条件：线性表L已存在。

操作结果：返回L中元素个数。

PriorElem(L,cur-e,&pre-e)

初始条件：线性表L已存在。

操作结果：若cur-e是L的元素，但不是第一个，则用pre-e返回它

的前驱，否则操作失败，pre-e无定义。

NextElem(L,cur-e,&next-e)

初始条件：线性表L已存在。

操作结果：若cur.e是L的元素，但不是最后第一个，则用next-e

返回它的后继，否则操作失败，next-e无定义。

06:448

GetElem(L,i,&e)

初始条件：线性表L已存在，IWigListLenth(L)。

操作结果：用e返回L中第i个数据元素的值。

LocateElem(L,e,compare())

初始条件：线性表L已存在，compare()是元素判定函数。

操作结果：返回L中第1个与e满足compare()的数据元素的位序,

若这样的元素不存在，则返回值为0。

ListTraverse(L,visit())

初始条件：线性表L已存在，IWiWListLenth(L)。

操作结果：依次对L的每个元素调用visit()o一旦visit()失败,

则操作失败。

06:449

｛加工型操作｝(操作的结果改变线性表的结构)

ClearList(&L)

初始条件：线性表L已存在。

操作结果：将L重置为空表。

PutElem(L,i,&e)

初始条件：线性表L已存在。

操作结果：L中第i个元素赋值同e的值。

Listinsert(&L,i,e)

初始条件：线性表L已存在，lWiWLengthList(L)+l

操作结果：在线性表L的第i个元素之前插入一个值为e的元

素，插入后原表长增1。

06:4410

ListDelete(&LJ,&e)

初始条件：线性表L已存在，l<i<LengthList(L)

操作结果：删除L的第i个元素，并用e返回其值,

删除后表长减1。

利用上述定义的线性表可以完成更复杂的操作。

06:4411

例2・L假设有两个集合A和B,分别用两个线性表LA

和LB表示（即：线性表中的数据元素即为集合中的

成员），现要求一个新的集合A二AUB。

上述问题可演绎为，要求对线性表作如下操作：

扩大线性表LA,将存在于线性表LB中而不存在于

LA中的数据元素插入到线性表LA中去。

06:4412

上述操作可写成下述三步：

第一步：从线性表LB中依次取得每个数据元素；

GetElem(LB,i)fe(用线性的操作描述)

第二步：依值在线性表LA中进行查访；

LocateElem(LA,e,equalO)

第三步：若不存在，则插入之。

Listinsert(LA,n+1,e)

用C语言写成的程序如下：

06:4413

voidunion(List&LA,ListLB){

〃将所有在线性表LB中而不在LA中的数据元素插入到LA中。(见书p20)

La-len=ListLength(LA);的长度

Lb-len=ListLength(LB);

for(i=l;i<=Lb-len;i++){

GetElem(LB,i,e);

if(!LocateElem(LA,e,equal))ListInsert(LA,++La-en,e)

,中不存在和e相同的数据元素，则插入之

}

}//union

06:4414

例2-2：已知一个非纯集合B,试构造一个纯集合A,使A中只

包含B中所有值各不相同的数据元素。

Voidpurge(List&La,ListLb){

InitList(La);//设置空的线性表La

La-len=ListLength(La);

Lb-len=ListLength(Lb);

for(i=l;i<=Lb-len;i++){

GetElem(LB,i,e);〃取LB中第i个数据元素赋给e

if(!LocateElem(LA,e,equal)){

++La-en;

ListInsert(LA,La-en,e);三素e插入线性表La中

}//if」

}//for

器劈度15

上面的程序是指非纯集合B未排好序，若非纯集合B已排好序

时，则程序将更简单。

Voidpurge(List&La,ListLb){

InitList(La);〃设置空的线性表La

La-len=ListLength(La);的长度

Lb-len=ListLength(Lb);

for(i=l;i<=Lb-len;i++){

GetElem(Lb,i,e);〃取LB中第i个数据元素赋给e

if(ListEmpty(La)||!Equal(en,e)){

ListInsert(La,++La-en,e);

en=e;

}//AIHe相同的数据则插入之

}//for

}//purge

06:4416

两个程序策略不一样，时间复杂度也不一样

第一个的时间复杂度为O(1>2)

第二个的时间复杂度为O(n)

例2-3巳知线性表LA和线性表LB中的数据元素按值非

递减有序排列，现要求将LA和LB归并为一个新的线性

表LC,且LC中的元素仍按值非递减有序排列。

分析：设La=(a1,…，ai,・・，3_口)

Lb=(b],・・.，bj,・・.，bm)

I-jC(],・・・，k,■■■,m+n)

则Ck=?，k=l,2,…，m+n

06:4417

1.分别从LA,LB中取得当前元素如和与；

2.若如<=%,则将如插入到Lc中；否则将bj插入到Lc中。

VoidMergeList(Listla,Listlb,List&lc)

“巳知线，表LA和线性表LB中的数据元素按值非递减排列

口LB得?新的线性表LC,LC中的元素仍按值非递减排列。

InitList(Lc);

i=j=l;k=O;

La-len=ListLength(La);

Lb-len=ListLength(Lb);

while((i<=La-len)&&(j<=Lb-len)){//La和Lb均非空

06:4418

GetElem(La,i,aj);GetElem(Lb,j,bJ：);

if(aj<=bj){ListInsert(Lc,++k,%);++i;}

else{ListInsert(Lc,++k,bj);++j;}

)

while(i<=La-len){

GetElem((La,i++,aj);ListInsert(Lc,++k,a。；

)

while(j<=Lb-len){

GetElem((Lb,j++,bj);ListInsert(Lc,++k,JbJ：);

)

}//MergeList

06:4419

2.2线性表类型的实现—顺序映象

用一组地址连续的存储单元依次存放线性表里的数据元素。

用这种方法存储的线性表简称顺序表。

ala2■■■ai-lai■■■an

线性表的起始地址称作线性表的地址

以存储位置相邻来表示有序对〈anaj即线性表中第i个数

据元素的存储位置LOC(a。和第i・l个数据元素的存储位置

LOC(aM)之间满足下列关系：

LOC(ai)=LOC(aw)+L(一个数据元素所占的存储位置)

所有数据元素的存储位置均取决于第一个数据元素的存储位

置：0644LOC(aj)=LOC(ai)+(i・l)*L(l<i<n)20

即在顺序存储结构中，线性表中每一个数据元素在计算

机存储空间中的存储地址由该元素在线性表中的序号惟一确

定。一般来说，长度为n的线性表(ara2,an)在计算机

中的结构如下：

21

06:44

内存地址

LOCa)

DXCaXJ+Uk

*

■

■

LOCa)+(i-l)*k

*

■

*

LOCa)+(n-l)*k

LjOC(a1J+(MAX-l)*k

UU：f—乙乙

由于C语言中的一维数组也是采用顺序存储表示，故可

以用数组类型来描述顺序表。又因为除了用数组来存储线

性表的元素之外，顺序表还应该用一个变量来表示线性表

的长度属性，所以我们用结构类型来定义顺序表类型。

序号12...i...n<---空闲----►

数据元索aa

i•・•4•・・n

下标

o1ilength_1MaxLen"1

06:4423

这样，一个线性表的顺序存储结构需要两个分量。为体现数组

data和length之间的内在联系，通常将它们定义在一个结构类型中。

此处的元素类型用ElemType来表示。

综上所述，在C语言中，可用下述类型定义来描述顺序表：

#defineLIST-INIT-SIZE100〃线性表存储空间的初始分配量

#defineLISTINCREMENT10〃线性表存储空间的分配增量

typedefstruct{

ElemType*elem;〃存储空间基址

intlength;〃线性表的实际长度

intlistsize；〃当前分配的存储容量，

//(以sizeof(ElemType)为单位

JsqList;

sqListL;〃定义表结构的变量

typedefintElemType〃在实际应用中，将ElemType定义成实际类型

06:4424

本节将讨论采用顺序存储结构之后，如何实现线性表的某些操作。

1.线性表的初始化操作(L)

顺序表的初始化操作就是为顺序表分配一个预定义大小的数组空

间，并将线性表的当前长度设为0。

StatusInitList-Sq(SqList&L){〃构造一个空的线性表

L.elem=(ElemType*)malloc(LIST-INIT-SIZE

*sizeof(ElemType));

if(!L.elem)exit(OVERFLOW);〃存储分配失败

L・length=O;〃空表长度为0

L.listsize=LIST-INIT-SIZE;

returnok;

}IIInitList-Sq

06:4425

2.顺序表的查找算法LocateElem的实现：

intLocateElem-Sq(SqListL,ElemTypee

status(*compare)(ElemType,ElemType)){

i=l;//i的初值为第一个数据元素的位序

P=L.elem；//P的初值为第一个数据元素的存储位置

while(i<=L.length&&!(*compare)(*p++,e))++i；

if(i<=L.length)returni;

elsereturn0;

}//LocateElem-Sq

由算法可知，对于表长为n的顺序表，在查找过程中，

数据元素比较次数最少为1,最多为n,元素比较次数的平

均值为(n+l)/2,时间复杂度为O㈤。

06:4426

3.顺序表的插入算法ListInsert(&L,i,e)的实现

悭序表的插入是指在表的第i个位置上插入一个值为e

的新元素，插入后使原表长为n的表：(a〃a2,...,a^,

a.,ai+1,…,an),成为表长为n+1的表：

(aPa2,…，%,e,a.,ai+1,…，an),i的取值范围为

Ki<n+1o

06:4427

下图表示一个顺序表中的数组在进行插入运算前后，数

据元素在数组中的下标变化。

06:44插入前插入后28

StatusListlnsert-Sq(SqList&LZintifElemTypee){

if(i<l||i>L.length+1)returnError//插入位置出错

if(L.length>=L.lis七size){//当前存储空间已满,增加分配

newbase=(ElemType*)realloc(L.elem^

(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(overflow);//存储分酉已失败

L.elem=newbase;〃新基址

L.listsize+=LISTINCREMENT;//增力口存储容量

}

q=&(L.elem[i-l]);〃q指示插入位置

for(p=&(L.elem[L.length-1]);p>=q；—p)

*(p+l)=*p;//插入位置及之后数据元素后移

*p=e;//插入e

++L.length;//表长度力口1

returnOk;

}/4^|stInsert-Sq

29

该算法的时间主要花费在移动数据元素上，移动个数取决于插

入位置i和表的长度n。所以可以用数据元素的移动操作来估计算法

的时间复杂度。在第i个位置上插入e,共需要移动n-i+1个元素，

i的取值范围为：l<i<n+1,即有n+1个位置可以插入。

当》=11+1时，不需要移动结点；当i=l时需要移动n个结点。由

此可以看出，算法在最好的情况下时间复杂性为O0,最坏的时间

复杂性是。伽

由于插入的位置是随机的，因此，需要分析执行该算法移动数

据元素的平均值。设在第i个位置上作插入的概率为匕，则平均移动

数据元素的次数：

Eis=ZPZZ—/+1）

i=l

假设表中任何位置插入概率是均等的，即Pi=l/(n+l),则:

n+1n+1

1n

E[=E2（〃-"1）=z（〃1+1）二一

i=l〃+1z=i2

06:4430

由此可以看出，在线性表上做插入操作需要移动表中一

半的数据元素，当n较大时，算法的效率是比较低的，所以

在线性表上进行插入操作的时间复杂度为0(n)o

6.顺序表的删除操作ListDelete(&L,i,&e)的实现

•顺序表的删除运算是指将表中第i个元素从线性表中去

掉，原表长为n的线性表(a»a2,…，aM,aPai+1,…，

an)o进行删除以后的线性表表长变为的表(%,a2,...,

aM,%+j…，an),i的取值范围为：IWiWn。

图2-5表示一个顺序表的数组在进行删除运算前后，其数

据元素在数组中的下标变化。

06:4431

AetAet

0ai0a1

1

1a9a2

2•2

*

i-1

i-1-1

内9一A

ia.1i+lai+1

i+l

a；+ii+2*

•

•

n—1ann—1%

•

n*

*

*

MaxLen_1MaxLen_1

稔9c玲9&

图2・5线性表中的删除运算示意图

06:4432

在线性表上完成上述运算通过以下两个操作来实现：

(1)线性表中第i个至第n个元素(共n-i个元素)依次

向前移动一个位置。将所删除的元素如覆盖掉，从而

保证逻辑上相邻的元素物理位置也相邻。

⑵修改线性表长度，使其减1。

06:4433

线性表的删除算法如下：

StatusListDelete-Sq(SqList&LZinti,ElemType&e){

〃删除线性表中第i个位置上的元素，

〃i的合法蔡为l〈iWListLength-Sq(L)

if((i<l)||i>L.length))returnERROR

〃g凝才及删除位置的合法性

p=&(L.elem[i-1]；

e=*P；

q=L.elem+L.length-1；

for(++p；p<=q；++p)//P之后的兀素而移，所以P先增1

*(p-l)，p；〃被删兀素之后的兀素向而移动

—L.length;三1

returnOK；

}//ListDelete-Sq

06:4434

删除算法的时间性能分析：

与插入运算相同，删除运算的时间也主要消耗在移动表中数据

元素上，删除第i个元素时，其后面的元素aj+i〜都要向前移动

一个位置，共移动了n-i个元素，所以在等概率的情况下，在线性

表中删除数据元素所需移动数据元素的期望值，即平均移动数据

元素的次数为：〃

耳必=E—z>

Z=1

通常情况下，我们认为在线性表中任何位置删除元素是等概

率的，即Pi=l/n,则：

n5n1

1n—\

Edl==Z2（H—%）=一工O—2）=-----------

/=1nz=i2

由此可以看出，在线性表上删除数据元素时大约需要移动表中一

半的元素，显然该算法的时间复杂度为。伽

06:4435

线性表的顺序存储结构中任意数据元素的存储地址可由公式

直接导出，因此顺序存储结构的线性表是可以随机存取其中的任

后、素°

J旦是,顺序存储结构也有一些不方便之处，主要表现在：

(1)数据元素最大个数需预先确定，使得高级程序设计语言编译

系统需预先分配相应的存储空间；

(2)插入与删除运算的效率很低。为了保持线性表中的数据元素

顺序，在插入操作和删除操作时需移动大量数据。对于插入和删

除操作频繁的线性表、将导致系统的运行速度难以提高。

06:4436

2.3线性表类型的实现一链式映象

」线性表的顺序表示的特点是用物理位置上的邻接

关系来表示结点间的逻辑关系，故可以随机存取表中

的任一结点；但在插入和删除操作时需移动大量的结

点。d

为避免大量结点的移动，介绍线性表的另一种存

储方式：链式存储结构，简称链表。

链式存储方式可用于表示线性结构，也可用于表

示非线性结构。

06:4437

一.链表的存储结构

链式存储结构是利用任意的存储单元来存放线性表中的元素,

存储数据的单元在内存中可以连续，也可以零散分布。

由于线性表中各元素间存在着线性关系，每一个元素有一个直

接前驱和一个直接后继。为了表示元素间的这种线性关系，在这

种结构中不仅要存储线性表中的元素，还要存储表示元素之间逻

辑关系的信息。所以用链式存储结构表示线性表中的一个元素时

至少需要两部分信息，除了存储每一个数据元素值以外，还需存

储其后继或前驱元素所在内存的地址。两部分信息一起构成链表

中的一个结点。结点的结构如下所示。

⑥/®Qg6

datanext

06:4438

二、C语言采用结构数据类型描述结点如下：

TypedefstructLNode{

ElemTypedata;//结点值

structLNode*next;//指针域，存储下一个结点的地址

}LNoder*LinkList;

在此结构中，用数据域data存储线性表中数据元素。指针域

next,它给出下一个结点的存储地址。结点的指针域将所有结点

按线性表的逻辑次序链接成一个整体，形成一个链表。由于链表

中第一个结点没有直接前驱，所以必须设置一个头指针head存储

第一个结点的地址。最后一个结点没有直接后继，其指针域应为

空指针，C语言用NULL或0来表示，在图中表示为“八”。

假设有一个线性表为(A,B,C,D,E),存储空间具有10个存储

结点，该线性表在存储空间中的存储情况如图2-7(a)所示。

06:4439

datanext;

1•Q©

head

5

6

7

8

9

IO

(a)IBDArtzAiAXT

t«0@

head

(b)BDAXf

图2-7链表结构示意图

06:4440

从图中可见，每个结点的存储地址存

放在直接前驱的指针域中。所以要访问链表

中数据元素C,必须由头指针head得到第一

个结点（数据A）的地址，由该结点的指针

域得到第二个结点（数据B）的地址，再由

其指针域得到存储数据C的结点地址，访问

该结点的数据域就可以处理数据C了。链表

这种顺着指针链依次访问数据元素的特点，

表明链表是一种顺序存取（非随机存取）的

存储结构，只能顺序操作链表中元素。不能

像顺序表（数组）那样可以按下标随机存取。

06:4441

为了提高顺序操作的速度，使操作更加灵活方便,

对链表中的指针采用了不同的设置，构成了不同的

链表。如只设置一个指向后继结点地址的指针域是

单链表；将其首尾相接构成一个环状结构，称为循

环链表；增加一个指向前驱的指针就构成双向链表。

I在链表存储结构中，不要求存储空间的连续性,

数据元素之间的逻辑关系由指针来确定。由于链式

存储的灵活性，这种存储方式既可用于表示线性结

构，也可以用来表示非线性结构。

06:4442

三、单链表

在所示的链表中，每个结点只有一个指向后继的指针。也

就是说访问数据元素只能由链表头依次到链表尾，而不能做逆

向访问。称这种链表为单向链表或线性链表。这是一种最简单

的链表。

单链表分为带头结点和不带头结点两种类型。

对于空链表，头结点的指针域为空。图2・8是带头结点的链

表示方式：head

(a)6Aft

head

a.£,b)Q0At

06:44图2-8(a)为带头结点的空链(b)为带头结点的单链表43

在线性表的顺序存储结构中，由于逻辑上相邻的两个元素

在物理位置上也相邻，则每个元素的存储位置都可从线性表的起

始位置计算得到。而在单链表中，任何两个元素的存储位置之间

没有固定的联系。然而每个元素的存储位置都包含在其直接前驱

结点的信息中。假设p指向线性表中第j个结点（结点ap的指针。

则p・>next是指向第j+1个数据元素（结点为+i）的指针。换句话说,

若p・>data=Hj,贝ijp->next->data=aj+1o由此，在单链表中要访问

单链表中第j个元素值，必须从头指针开始遍历链表，依次访问每

个结点，直到访问到第j个结点为止。因此，单链表是非随机存取

的存储结构。

06:4444

三、单链表操作的实现

1.按序号取元素GetElem(L,i,&e)的实现

基本操作：使指针p始终指向线性表中第j个数据元素

StatusGetElem(LinkListL,inti,ElemType&e)

{p=L->next;j=l;〃初始化，p指向第一个结点，j为计数器

while(p&&j<i){p=p->next;++j;}

旨钊’后查找，直到p指向第i个元素或P为空

if(!p||j>i)returnERROR;

e=p->data;//取第i个元素

returnok;

}//GetElem_L

时间复杂度：0(ListLength(L))

06:4445

2.链表的插入算法Listlnsert(&L,i,e)的实现

单链表结点的插入是利用修改结点指针域的值，使其指

向新的链接位置来完成的插入操作，而无需移动任何元素。

a.为插入数据元素e,首先要生成一个数据为e的结点，然

「后插入在单链表中。Y-

b.根据插入操作的逻辑定义，还需要修改结点a-中的指

针域，令其指向结点e,而结点e中的指针域指向接点电。

假设s为指向结点e的指针，p为指向结点ar的指针。则

完成该操作的过程如图2-9所示。

06:4446

p

▼

a?>a.____

(a)找到插入位置

s=(LinkList)malloc(sizeof(LNode))；

s->data=e；

6)申请新结点s,数据域置e

(c)修改指针域，将新结点s插入

图2-9插入s结点过程示意图

上述指针进行相互赋值的语句顺序不能颠倒。

06:4447

StatusListInsert_L(LinkList&L,inti,ElemType)

{p=L;j=O;

while(p&&j<i-l){p=p->next;++j;}

if(!p||j>i-l)returnERROR;

s=(LinkList)malloc(sizeof(LN()de));〃生成新结点

s->data=e;s->next=p->next;p->next=s;

returnok;

}//ListlnsertL

算法的时间复杂度：O(ListLength(L))

06:4448

3.链表的册I除运算ListDelete(&Lj&e)的实现

基本操作：删除链表中第i个结点，首先在单链表

中找到删除位置前一个结点a1,并用指针p指向

它，删除后的结点需动态的释放。如下图2・10所

示。假定删除的结点是值为%的结点。图240(c)

中虚线表示删除结点外后的指针指向。

具体算法描述为：

06:4449

p

(b)返回被删除结点数据e

n

q

e=q—>data；

(c)修改指针域，将结点q删除

free(q);

图2・10线性链表的删除过程示意图

06:4450

StatusListDelete(LinkListL,inti,ElemType&e)

{p=L;j=0;

while(p->next&&j<i-l){p=p->next;++j;}

if(!(p->next)||j>i-l)returnERROR;

q=p->next;p->next=q->next;

e=q->data;free(q);

returnOK;

}//ListDeleteL

算法的时间复杂度：O(ListLength(L))

06:4451

在插入和删除算法中，都是先查询确定操作位置，然后再

进行插入和删除操作。所以其时间复杂度均为。㈤。另外在算

法中实行插入和删除操作时没有移动元素的位置，只是修改了

指针的指向，所以采用链表存储方式要比顺序存储方式的效率

高。-

在插入和删除算法中，我们分别用了c语言中的两个标准函

数malloc和free。在设有“指针”数据类型的高级语言中均存在

与其相应的过程和函数。

p二(LinkList)malloc(sizeof(LNode))：系统生成一^个

Lnode型的结点，同时将该结点的起始位置赋给指针变量p；

Free(q)：系统回收一个Lnode型的结点，回收后的空间

可以备作再次生成结点时用。

06:4452

以上我们讲了链表的3个主要操作：取第i个数据

元素、插入、删除，那么链表本身它怎么得到，它

本身的生成与顺序表截然不同。

单链表和顺序存储结构不同，它是一种动态存

储结构。整个可用存储空间可为多个链表共同享用，

每个链表占用的空间不需预先分配划定，而是可以

由系统应需求即时生成。因此建立线性表的链式存

储结构的过程就是一个动态生成链表的过程。即从

“空表”的初始状态起，依次建立各结点，并逐个

插入链表。

06:4453

VoidCreateList-L(LinkList&L,intn){

〃逆位序输入n个元素的值，建立带表头结点的单链线性表L

L=(LinkList)malloc(sizeof(Lnode))

L->next=null;〃先建立一个带头结点的单链表(头结点的指针域为空)

fdr(i=n;i>0;—i){

p=(LinkList)malloc(sizeof(Lnode));〃生成新结点

scanf((、'%d”,&p—>data);//输入元素值

p->next=L->next;

L->next=p;

}//for

}//CreateList-L算法的时间复杂度：O(listlength(L))

06:4454

用上述定义的单链表实现线性表的操作时，存在的问题：

1.单链表的表长是一个隐含的值；

2.在单链表的最后一个位置插入元素时，需遍历整个链表；

3.在链表中，元素的“位序”概念淡化，结点的“位置”概念强

化。

改进链表的设置：

1.增加“表长”、“表尾指针”和“当前位置的指针”三个

数据域；

2.将基本操作由“位序”改变为“指针”。

06:4455

四、一个带头结点的线性链表类型

TypedefStructLNode{〃结点类型

ElemTypedata;

structLnode*next;

}*Link,"Position；

StatusMakeNode(Link&P,ElemTypee);

//分配由p指向的值为e的结点，并返回OK；

//若分配失败，则返回ERROR；

VoidFreeNode(Link&P);

//释放p所指结点

06:4456

TypedefStruct{〃链表类型

Linkhead,tail;〃指向头结点和最后一个结点

intlen;//指示链表长度

Linkcurrent;

〃指向当前访问的结点的指针，初始位置指向头结点

}Linklist；

06:4457

链表的基本操作：

｛结构初始化和销毁结构｝

｛引用型操作｝

｛加工型操作｝

看书上P37页

58

06:44

例一、StatusListInsert-L(LinkListL,inti,ElemTypee)

〃在带头结点的单链线性表L的第i个元素之前插入元素e

If(!LocataPos(L,i-l)returnERROR;〃i值不合法

If(InsAfter(L,e))returnOK;//插入在第i・l结点之后

elsereturnERROR;

}//Listlnsert-L

06:4459

例二：VoidMergeList-L(LinkList&La,LinkList&Lb,LinkList&Lc)

int(*compare)(ElemType,ElemType)){

〃已知单链线性表La和Lb的元素值按值非递减排列。

〃归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列。

if(!InitList(Lc))returnERROR;

ha=GetHead(La);hb=GetHead(Lb);

pa=NextPos(La,ha);pb=NextPos(Lb,hb)

While(pa&&pb){

a=GetCurElem(pa);b=GetCurElem(pb);

if((*compare)(a,b)<=0){//a<=b

DelFirst(ha,q);Append(Lc,q);pa=NextPos(La,ha);}

else{//a>b

DelFirst(hb,q);Append(Lc,q);pb=NextPos(Lb,hb);

}//while

06:4460

If(pa)Append(Lc9pa);//链接La中剩余结点

ElseAppend(Lc,pb);〃链接Lb中乘U余结点

FreeNode(ha);FreeNode(hb);returnok;

〃释放La和Lb的头结点

}//MergeList-L

06:4461

静态链表

L有些高级程序设计语言中没有指针类型，这可以通过定义

一个结构体数组实现类似于“链表”结构的形式，即用数组

实现的线性链表，称为静态链表。由于它是利用数组定义的,

一在整个运算过程中存储空间的大小不会发生变化,因此称这

一种结构为静态链表。gS

2.静态链表的类型定义：

#defineMAXSIZE100〃链表的最大长度

typedefStruct{

ElemTypedata;

intcur;

}Component,SLinkList[MaxSize];

06:4462

3.静态链表

静态链表是用数组描述线性链表。

静态链表的每个结点由两个数据成员构成：

“数据域Data:存储数据元素

1游标Cur：存储直接后继元素所在的数组下标

datanext

011EO

I-Q©

2C9

head

1a33

44A7

2b45

3c26

7B2

4d58

9D1

5e-1IO

06:446(a)iB0AfckMt于

4.静态链表的操作：a-c-b-d-e

在d之前插入f,变成a-c-b-f-d・e

01

1a3

2b6

3c2

4d5

5e-1

6f4

06:4464

静态链表的操作：a-c-b-d-e

删除b,变成a・c・d・e

0

1

2

3

4

5

6

06:4465

四、其它形式的链表

1.循环链表

在单链表中，最后一个结点的指针域为空(NULL)。

访问单链表中任何数据只能从链表头开始顺序访问，而不能

进行任何位置的随机查询访问。如要查询的结点在链表的尾

部也需遍历整个链表。所以单链表的应用受到一定的限制。

循环链表(CircularLinkedList)是另一种形式的链式存储

结构。它将单链表中最后一个结点的指针指向链表的头结点,

使整个链表头尾相接形成一个环形。这样，从链表中任一结

点出发，顺着指针链都可找到表中其它结点。循环链表的最

大特点是不增加存储量，只是简单地改变一下最后一个结点

的指针指向，就可以使操作更加方便灵活。图2/3是循环链

装15存储结构示意图。66

head

£•at0&A0N»•At

江劭产栅嬲41a"a/+►••.可^^..・f^

£'bt0I,ftAN»•Afh

2.13循环链表结构示意图

带头结点的单循环链表的操作算法和带头结点的单链表的

操作算法很相似，差别仅在于算法中的循环条件不同。条件不

是p或p・>next是否为空，而是它们是否指向头结点。

06:4467

2,双向链表

单链表只有一个指向后继的指针来表示结点间的逻辑关系。故

从任一结点开始找其后继结点很方便，但要找前驱结点则比较困难。

双向链表是用两个指针表示结点间的逻辑关系。即增加了一个指向

其直接前驱的指针域，这样形成的链表有两条不同方向的链，前驱

和后继，因此称为双链表。在双链表中，根据已知结点查找其直接

前驱结点可以和查找其直接后继结点一样方便。这里也仅讨论带头

结点的双链表。仍假设数据元素的类型为ElemType。

双向链表结点的定义如下：

typedefstructDuLNode{

ElemTypedata;priordatanext

structDuLNode*prior;

structDuLNode*next;

图2/5双向链表结点结构图

}DuLnode,*DuLinkList;

桀虚的结构如图2・15所示。

(b)非空双向链表

P->next->prior=p=p->prior->next

图2-16带头结点的双向链表

双向链表的优点：找当前指针的前驱是限量级的，而不是

线性的。

在双向链表中，有些操作如求表长(ListLength)、取元素

值(GetElem)、D定位(LocateElem)等仅涉及一个方向的

指针，则它们的算法描述和线性表的操作相同，但在插入和删

除时有很大不同，需要修改两个方向的指针。

06:4469

关键语句：

@s->prior=p->prior;

@p->prior->next=s;

@s->next=p;

(a)插入前的状态@p->prior=s;

(b)插入过程

图2-17双链表插入结点示意图

注意：在图2・17中，关键语句指针操作序列既不是唯一也不是任意

的。操作①必须在操作④之前完成，否则*p的前驱结点就丢掉了。

06:4470

p

关键语句：

①p->prior->next=p->next;

(a)删除前状态

②p->next->prior=p->prior;

③free(p)；

②

(b)删除过程

注意：在双向链表中进行插入和删除时，对指

针的修改需要同时修改结点的前驱指针和后继

指针的指向。

06:4471

2.4线性表的应用——一元多项式的表示及相加

1.一元多项式表示

链式存储结构的典型应用之一是在高等数学的多项式方面。

本节主要讨论采用链表结构表示的一元多项式的操作处理。

在数学上，一个一元多项式P0(X)可以表示为：

211

Pn(x)=p0+p1x+p2x+...+pnx(最多有n+1项)

Pi*i是多项式的第i项(OWign)。其中R为系数，x为自变

量，i为指数。多项式中有n+1个系数，而且是线性排列。

一个多项式由多个(IWiWm)项组成，每个多项式

coefexpnnext

06:4472

coefexpnnext

其中，coef数据域存放系数p〕expn数据域存放指数g；

next域是一个链域，指向下一个结点。由此，一个多项式可以

表示成由这些结点链接而成的单链表(假设该单链表是带头结

点的单链表)。

在计算机中，多项式可用一个线性表listP来表示：listP=(

Po,PrP2…，PQ。但这种表示无法分清每一项的系数和指

数。所以可以采用另一种表示一元多项式的方法：listP={Ip。

，e0