線性表教學(xué)課件

第2章線性表

2.1線性表的基本概念

2.2線性表的類型定義

2.3線性表的順序表示和實現(xiàn)

2.4線性表的鏈式表示和實現(xiàn)

2.4.1線性鏈表

II2.4.2循環(huán)鏈表

2.4.3雙向鏈表

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

06:441

本章學(xué)習(xí)導(dǎo)讀

俵喉表（Linearlist）是最簡單且最常用的一種數(shù)據(jù)結(jié)

構(gòu)。這種結(jié)構(gòu)具有下列特點：存在一個唯一的沒有前驅(qū)的

（頭）數(shù)據(jù)元素；存在一個唯一的沒有后繼的（尾）數(shù)據(jù)

元素；此外，每一個數(shù)據(jù)元素均有一個直接前驅(qū)和一個直

接后繼數(shù)據(jù)元素。

通過本章的學(xué)習(xí)，我們應(yīng)能掌握線性表的邏輯結(jié)構(gòu)和

存儲結(jié)構(gòu)，以及線性表的基本運算以及實現(xiàn)算法。

06:442

2.1線性表的基本概念

線性表由一組具有相同屬性的數(shù)據(jù)元素構(gòu)成。數(shù)據(jù)元素的含

義廣泛，在不同的具體情況下，可以有不同的含義。

1.線性表的定義

'線性表L是n(n>0)個具有相同屬性的數(shù)據(jù)元素%,a2,

a3,....an組成的有限序列，其中序列中元素的個數(shù)n稱為線性表

的長度?？?/p>

當n=0時稱為空表，即不含有任何元素。

常常將非空的線性表(n>0)記作：

(ara2,…分)

這里的數(shù)據(jù)元素藥(lWi皂n)只是一個抽象的符號，其具體含

義在不同的情況下可以不同。

06:443

例1、26個英文字母組成的字母表

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

例2、從1978年到1983年各種型號的計算機擁有量的變化情況。

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

例3、

表2-1學(xué)生基本情況表下

學(xué)號〃姓名一性別一年齡「班級Q籍貫/

20021418^吳小軍d男Q20-計算機系024^天津21

20021419P王乾龍*男Q20計算機系024c山東淄博?

200214200李晉東2男Q19^計算機系。24?1上?！?/p>

200214214-1高小珊/女。19?」計算機系02小，遼寧丹東，

20021422/杜都」女二20*3計菖機系02務(wù)山東煙臺值

06:444

從以上例子可看出線性表的邏輯特征是：

在非空的線性表，有且僅有一個開始結(jié)點藥,它沒有直接

前趨，而僅有一個直接后繼a2；

有且僅有一個終端結(jié)點a。，它沒有直接后繼，而僅有一個

直接前趨an.1；

其余的內(nèi)部結(jié)點%（2皂i皂n-1）都有且僅有一個直接前趨aM

和一個直接后繼ai+1o

線性表是一種典型的線性結(jié)構(gòu)。

數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算的具體實現(xiàn)則

是在存儲結(jié)構(gòu)上進行的。

06:445

2.1線性表的類型定義

抽象數(shù)據(jù)類型線性表的定義如下：

ADTList｛

數(shù)據(jù)對象

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

數(shù)據(jù)關(guān)系

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

基本操作：

｛結(jié)構(gòu)初始化｝｛銷毀結(jié)構(gòu)｝

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

憐叫List

6

｛結(jié)構(gòu)初始化｝

InitList(&L)

操作結(jié)果：構(gòu)造一個空的線性表L。

｛銷毀結(jié)構(gòu)｝

DestroyList(&L)

初始條件：線性表L已存在。

操作結(jié)果：銷毀線性表L。

｛引用型操作｝7操作的結(jié)果不改變線性表的結(jié)構(gòu))

ListEmpty(L)

初始條件：線性表L已存在。

操作結(jié)果：若L為空表，則返回True,否則FALSE。

06:447

ListLength(L)

初始條件：線性表L已存在。

操作結(jié)果：返回L中元素個數(shù)。

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

初始條件：線性表L已存在。

操作結(jié)果：若cur-e是L的元素，但不是第一個，則用pre-e返回它

的前驅(qū)，否則操作失敗，pre-e無定義。

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

初始條件：線性表L已存在。

操作結(jié)果：若cur.e是L的元素，但不是最后第一個，則用next-e

返回它的后繼，否則操作失敗，next-e無定義。

06:448

GetElem(L,i,&e)

初始條件：線性表L已存在，IWigListLenth(L)。

操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值。

LocateElem(L,e,compare())

初始條件：線性表L已存在，compare()是元素判定函數(shù)。

操作結(jié)果：返回L中第1個與e滿足compare()的數(shù)據(jù)元素的位序,

若這樣的元素不存在，則返回值為0。

ListTraverse(L,visit())

初始條件：線性表L已存在，IWiWListLenth(L)。

操作結(jié)果：依次對L的每個元素調(diào)用visit()o一旦visit()失敗,

則操作失敗。

06:449

｛加工型操作｝(操作的結(jié)果改變線性表的結(jié)構(gòu))

ClearList(&L)

初始條件：線性表L已存在。

操作結(jié)果：將L重置為空表。

PutElem(L,i,&e)

初始條件：線性表L已存在。

操作結(jié)果：L中第i個元素賦值同e的值。

Listinsert(&L,i,e)

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

操作結(jié)果：在線性表L的第i個元素之前插入一個值為e的元

素，插入后原表長增1。

06:4410

ListDelete(&LJ,&e)

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

操作結(jié)果：刪除L的第i個元素，并用e返回其值,

刪除后表長減1。

利用上述定義的線性表可以完成更復(fù)雜的操作。

06:4411

例2?L假設(shè)有兩個集合A和B,分別用兩個線性表LA

和LB表示（即：線性表中的數(shù)據(jù)元素即為集合中的

成員），現(xiàn)要求一個新的集合A二AUB。

上述問題可演繹為，要求對線性表作如下操作：

擴大線性表LA,將存在于線性表LB中而不存在于

LA中的數(shù)據(jù)元素插入到線性表LA中去。

06:4412

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

第一步：從線性表LB中依次取得每個數(shù)據(jù)元素；

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

第二步：依值在線性表LA中進行查訪；

LocateElem(LA,e,equalO)

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

Listinsert(LA,n+1,e)

用C語言寫成的程序如下：

06:4413

voidunion(List&LA,ListLB){

〃將所有在線性表LB中而不在LA中的數(shù)據(jù)元素插入到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相同的數(shù)據(jù)元素，則插入之

}

}//union

06:4414

例2-2：已知一個非純集合B,試構(gòu)造一個純集合A,使A中只

包含B中所有值各不相同的數(shù)據(jù)元素。

Voidpurge(List&La,ListLb){

InitList(La);//設(shè)置空的線性表La

La-len=ListLength(La);

Lb-len=ListLength(Lb);

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

GetElem(LB,i,e);〃取LB中第i個數(shù)據(jù)元素賦給e

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

++La-en;

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

}//if」

}//for

器劈度15

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

時，則程序?qū)⒏唵巍?/p>

Voidpurge(List&La,ListLb){

InitList(La);〃設(shè)置空的線性表La

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

Lb-len=ListLength(Lb);

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

GetElem(Lb,i,e);〃取LB中第i個數(shù)據(jù)元素賦給e

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

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

en=e;

}//AIHe相同的數(shù)據(jù)則插入之

}//for

}//purge

06:4416

兩個程序策略不一樣，時間復(fù)雜度也不一樣

第一個的時間復(fù)雜度為O(1>2)

第二個的時間復(fù)雜度為O(n)

例2-3巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非

遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性

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

分析：設(shè)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中的數(shù)據(jù)元素按值非遞減排列

口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線性表類型的實現(xiàn)—順序映象

用一組地址連續(xù)的存儲單元依次存放線性表里的數(shù)據(jù)元素。

用這種方法存儲的線性表簡稱順序表。

ala2■■■ai-lai■■■an

線性表的起始地址稱作線性表的地址

以存儲位置相鄰來表示有序?qū)Α碼naj即線性表中第i個數(shù)

據(jù)元素的存儲位置LOC(a。和第i?l個數(shù)據(jù)元素的存儲位置

LOC(aM)之間滿足下列關(guān)系：

LOC(ai)=LOC(aw)+L(一個數(shù)據(jù)元素所占的存儲位置)

所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位

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

即在順序存儲結(jié)構(gòu)中，線性表中每一個數(shù)據(jù)元素在計算

機存儲空間中的存儲地址由該元素在線性表中的序號惟一確

定。一般來說，長度為n的線性表(ara2,an)在計算機

中的結(jié)構(gòu)如下：

21

06:44

內(nèi)存地址

LOCa)

DXCaXJ+Uk

*

■

■

LOCa)+(i-l)*k

*

■

*

LOCa)+(n-l)*k

LjOC(a1J+(MAX-l)*k

UU：f—乙乙

由于C語言中的一維數(shù)組也是采用順序存儲表示，故可

以用數(shù)組類型來描述順序表。又因為除了用數(shù)組來存儲線

性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表

的長度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。

序號12...i...n<---空閑----?

數(shù)據(jù)元索aa

i???4???n

下標

o1ilength_1MaxLen"1

06:4423

這樣，一個線性表的順序存儲結(jié)構(gòu)需要兩個分量。為體現(xiàn)數(shù)組

data和length之間的內(nèi)在聯(lián)系，通常將它們定義在一個結(jié)構(gòu)類型中。

此處的元素類型用ElemType來表示。

綜上所述，在C語言中，可用下述類型定義來描述順序表：

#defineLIST-INIT-SIZE100〃線性表存儲空間的初始分配量

#defineLISTINCREMENT10〃線性表存儲空間的分配增量

typedefstruct{

ElemType*elem;〃存儲空間基址

intlength;〃線性表的實際長度

intlistsize；〃當前分配的存儲容量，

//(以sizeof(ElemType)為單位

JsqList;

sqListL;〃定義表結(jié)構(gòu)的變量

typedefintElemType〃在實際應(yīng)用中，將ElemType定義成實際類型

06:4424

本節(jié)將討論采用順序存儲結(jié)構(gòu)之后，如何實現(xiàn)線性表的某些操作。

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

順序表的初始化操作就是為順序表分配一個預(yù)定義大小的數(shù)組空

間，并將線性表的當前長度設(shè)為0。

StatusInitList-Sq(SqList&L){〃構(gòu)造一個空的線性表

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的實現(xiàn)：

intLocateElem-Sq(SqListL,ElemTypee

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

i=l;//i的初值為第一個數(shù)據(jù)元素的位序

P=L.elem；//P的初值為第一個數(shù)據(jù)元素的存儲位置

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

if(i<=L.length)returni;

elsereturn0;

}//LocateElem-Sq

由算法可知，對于表長為n的順序表，在查找過程中，

數(shù)據(jù)元素比較次數(shù)最少為1,最多為n,元素比較次數(shù)的平

均值為(n+l)/2,時間復(fù)雜度為O㈤。

06:4426

3.順序表的插入算法ListInsert(&L,i,e)的實現(xiàn)

慳序表的插入是指在表的第i個位置上插入一個值為e

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

a.,ai+1,…,an),成為表長為n+1的表：

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

Ki<n+1o

06:4427

下圖表示一個順序表中的數(shù)組在進行插入運算前后，數(shù)

據(jù)元素在數(shù)組中的下標變化。

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;//插入位置及之后數(shù)據(jù)元素后移

*p=e;//插入e

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

returnOk;

}/4^|stInsert-Sq

29

該算法的時間主要花費在移動數(shù)據(jù)元素上，移動個數(shù)取決于插

入位置i和表的長度n。所以可以用數(shù)據(jù)元素的移動操作來估計算法

的時間復(fù)雜度。在第i個位置上插入e,共需要移動n-i+1個元素，

i的取值范圍為：l<i<n+1,即有n+1個位置可以插入。

當》=11+1時，不需要移動結(jié)點；當i=l時需要移動n個結(jié)點。由

此可以看出，算法在最好的情況下時間復(fù)雜性為O0,最壞的時間

復(fù)雜性是。伽

由于插入的位置是隨機的，因此，需要分析執(zhí)行該算法移動數(shù)

據(jù)元素的平均值。設(shè)在第i個位置上作插入的概率為匕，則平均移動

數(shù)據(jù)元素的次數(shù)：

Eis=ZPZZ—/+1）

i=l

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

n+1n+1

1n

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

i=l〃+1z=i2

06:4430

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

半的數(shù)據(jù)元素，當n較大時，算法的效率是比較低的，所以

在線性表上進行插入操作的時間復(fù)雜度為0(n)o

6.順序表的刪除操作ListDelete(&L,i,&e)的實現(xiàn)

?順序表的刪除運算是指將表中第i個元素從線性表中去

掉，原表長為n的線性表(a?a2,…，aM,aPai+1,…，

an)o進行刪除以后的線性表表長變?yōu)榈谋?%,a2,...,

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

圖2-5表示一個順序表的數(shù)組在進行刪除運算前后，其數(shù)

據(jù)元素在數(shù)組中的下標變化。

06:4431

AetAet

0ai0a1

1

1a9a2

2?2

*

i-1

i-1-1

內(nèi)9一A

ia.1i+lai+1

i+l

a；+ii+2*

?

?

n—1ann—1%

?

n*

*

*

MaxLen_1MaxLen_1

稔9c玲9&

圖2?5線性表中的刪除運算示意圖

06:4432

在線性表上完成上述運算通過以下兩個操作來實現(xiàn)：

(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

刪除算法的時間性能分析：

與插入運算相同，刪除運算的時間也主要消耗在移動表中數(shù)據(jù)

元素上，刪除第i個元素時，其后面的元素aj+i?都要向前移動

一個位置，共移動了n-i個元素，所以在等概率的情況下，在線性

表中刪除數(shù)據(jù)元素所需移動數(shù)據(jù)元素的期望值，即平均移動數(shù)據(jù)

元素的次數(shù)為：〃

耳必=E—z>

Z=1

通常情況下，我們認為在線性表中任何位置刪除元素是等概

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

n5n1

1n—\

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

/=1nz=i2

由此可以看出，在線性表上刪除數(shù)據(jù)元素時大約需要移動表中一

半的元素，顯然該算法的時間復(fù)雜度為。伽

06:4435

線性表的順序存儲結(jié)構(gòu)中任意數(shù)據(jù)元素的存儲地址可由公式

直接導(dǎo)出，因此順序存儲結(jié)構(gòu)的線性表是可以隨機存取其中的任

后、素°

J旦是,順序存儲結(jié)構(gòu)也有一些不方便之處，主要表現(xiàn)在：

(1)數(shù)據(jù)元素最大個數(shù)需預(yù)先確定，使得高級程序設(shè)計語言編譯

系統(tǒng)需預(yù)先分配相應(yīng)的存儲空間；

(2)插入與刪除運算的效率很低。為了保持線性表中的數(shù)據(jù)元素

順序，在插入操作和刪除操作時需移動大量數(shù)據(jù)。對于插入和刪

除操作頻繁的線性表、將導(dǎo)致系統(tǒng)的運行速度難以提高。

06:4436

2.3線性表類型的實現(xiàn)一鏈式映象

」線性表的順序表示的特點是用物理位置上的鄰接

關(guān)系來表示結(jié)點間的邏輯關(guān)系，故可以隨機存取表中

的任一結(jié)點；但在插入和刪除操作時需移動大量的結(jié)

點。d

為避免大量結(jié)點的移動，介紹線性表的另一種存

儲方式：鏈式存儲結(jié)構(gòu)，簡稱鏈表。

鏈式存儲方式可用于表示線性結(jié)構(gòu)，也可用于表

示非線性結(jié)構(gòu)。

06:4437

一.鏈表的存儲結(jié)構(gòu)

鏈式存儲結(jié)構(gòu)是利用任意的存儲單元來存放線性表中的元素,

存儲數(shù)據(jù)的單元在內(nèi)存中可以連續(xù)，也可以零散分布。

由于線性表中各元素間存在著線性關(guān)系，每一個元素有一個直

接前驅(qū)和一個直接后繼。為了表示元素間的這種線性關(guān)系，在這

種結(jié)構(gòu)中不僅要存儲線性表中的元素，還要存儲表示元素之間邏

輯關(guān)系的信息。所以用鏈式存儲結(jié)構(gòu)表示線性表中的一個元素時

至少需要兩部分信息，除了存儲每一個數(shù)據(jù)元素值以外，還需存

儲其后繼或前驅(qū)元素所在內(nèi)存的地址。兩部分信息一起構(gòu)成鏈表

中的一個結(jié)點。結(jié)點的結(jié)構(gòu)如下所示。

⑥/?Qg6

datanext

06:4438

二、C語言采用結(jié)構(gòu)數(shù)據(jù)類型描述結(jié)點如下：

TypedefstructLNode{

ElemTypedata;//結(jié)點值

structLNode*next;//指針域，存儲下一個結(jié)點的地址

}LNoder*LinkList;

在此結(jié)構(gòu)中，用數(shù)據(jù)域data存儲線性表中數(shù)據(jù)元素。指針域

next,它給出下一個結(jié)點的存儲地址。結(jié)點的指針域?qū)⑺薪Y(jié)點

按線性表的邏輯次序鏈接成一個整體，形成一個鏈表。由于鏈表

中第一個結(jié)點沒有直接前驅(qū)，所以必須設(shè)置一個頭指針head存儲

第一個結(jié)點的地址。最后一個結(jié)點沒有直接后繼，其指針域應(yīng)為

空指針，C語言用NULL或0來表示，在圖中表示為“八”。

假設(shè)有一個線性表為(A,B,C,D,E),存儲空間具有10個存儲

結(jié)點，該線性表在存儲空間中的存儲情況如圖2-7(a)所示。

06:4439

datanext;

1?Q?

head

5

6

7

8

9

IO

(a)IBDArtzAiAXT

t?0@

head

(b)BDAXf

圖2-7鏈表結(jié)構(gòu)示意圖

06:4440

從圖中可見，每個結(jié)點的存儲地址存

放在直接前驅(qū)的指針域中。所以要訪問鏈表

中數(shù)據(jù)元素C,必須由頭指針head得到第一

個結(jié)點（數(shù)據(jù)A）的地址，由該結(jié)點的指針

域得到第二個結(jié)點（數(shù)據(jù)B）的地址，再由

其指針域得到存儲數(shù)據(jù)C的結(jié)點地址，訪問

該結(jié)點的數(shù)據(jù)域就可以處理數(shù)據(jù)C了。鏈表

這種順著指針鏈依次訪問數(shù)據(jù)元素的特點，

表明鏈表是一種順序存?。ǚ请S機存?。┑?/p>

存儲結(jié)構(gòu)，只能順序操作鏈表中元素。不能

像順序表（數(shù)組）那樣可以按下標隨機存取。

06:4441

為了提高順序操作的速度，使操作更加靈活方便,

對鏈表中的指針采用了不同的設(shè)置，構(gòu)成了不同的

鏈表。如只設(shè)置一個指向后繼結(jié)點地址的指針域是

單鏈表；將其首尾相接構(gòu)成一個環(huán)狀結(jié)構(gòu)，稱為循

環(huán)鏈表；增加一個指向前驅(qū)的指針就構(gòu)成雙向鏈表。

I在鏈表存儲結(jié)構(gòu)中，不要求存儲空間的連續(xù)性,

數(shù)據(jù)元素之間的邏輯關(guān)系由指針來確定。由于鏈式

存儲的靈活性，這種存儲方式既可用于表示線性結(jié)

構(gòu)，也可以用來表示非線性結(jié)構(gòu)。

06:4442

三、單鏈表

在所示的鏈表中，每個結(jié)點只有一個指向后繼的指針。也

就是說訪問數(shù)據(jù)元素只能由鏈表頭依次到鏈表尾，而不能做逆

向訪問。稱這種鏈表為單向鏈表或線性鏈表。這是一種最簡單

的鏈表。

單鏈表分為帶頭結(jié)點和不帶頭結(jié)點兩種類型。

對于空鏈表，頭結(jié)點的指針域為空。圖2?8是帶頭結(jié)點的鏈

表示方式：head

(a)6Aft

head

a.￡,b)Q0At

06:44圖2-8(a)為帶頭結(jié)點的空鏈(b)為帶頭結(jié)點的單鏈表43

在線性表的順序存儲結(jié)構(gòu)中，由于邏輯上相鄰的兩個元素

在物理位置上也相鄰，則每個元素的存儲位置都可從線性表的起

始位置計算得到。而在單鏈表中，任何兩個元素的存儲位置之間

沒有固定的聯(lián)系。然而每個元素的存儲位置都包含在其直接前驅(qū)

結(jié)點的信息中。假設(shè)p指向線性表中第j個結(jié)點（結(jié)點ap的指針。

則p?>next是指向第j+1個數(shù)據(jù)元素（結(jié)點為+i）的指針。換句話說,

若p?>data=Hj,貝ijp->next->data=aj+1o由此，在單鏈表中要訪問

單鏈表中第j個元素值，必須從頭指針開始遍歷鏈表，依次訪問每

個結(jié)點，直到訪問到第j個結(jié)點為止。因此，單鏈表是非隨機存取

的存儲結(jié)構(gòu)。

06:4444

三、單鏈表操作的實現(xiàn)

1.按序號取元素GetElem(L,i,&e)的實現(xiàn)

基本操作：使指針p始終指向線性表中第j個數(shù)據(jù)元素

StatusGetElem(LinkListL,inti,ElemType&e)

{p=L->next;j=l;〃初始化，p指向第一個結(jié)點，j為計數(shù)器

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

旨釗’后查找，直到p指向第i個元素或P為空

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

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

returnok;

}//GetElem_L

時間復(fù)雜度：0(ListLength(L))

06:4445

2.鏈表的插入算法Listlnsert(&L,i,e)的實現(xiàn)

單鏈表結(jié)點的插入是利用修改結(jié)點指針域的值，使其指

向新的鏈接位置來完成的插入操作，而無需移動任何元素。

a.為插入數(shù)據(jù)元素e,首先要生成一個數(shù)據(jù)為e的結(jié)點，然

「后插入在單鏈表中。Y-

b.根據(jù)插入操作的邏輯定義，還需要修改結(jié)點a-中的指

針域，令其指向結(jié)點e,而結(jié)點e中的指針域指向接點電。

假設(shè)s為指向結(jié)點e的指針，p為指向結(jié)點ar的指針。則

完成該操作的過程如圖2-9所示。

06:4446

p

▼

a?>a.____

(a)找到插入位置

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

s->data=e；

6)申請新結(jié)點s,數(shù)據(jù)域置e

(c)修改指針域，將新結(jié)點s插入

圖2-9插入s結(jié)點過程示意圖

上述指針進行相互賦值的語句順序不能顛倒。

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));〃生成新結(jié)點

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

returnok;

}//ListlnsertL

算法的時間復(fù)雜度：O(ListLength(L))

06:4448

3.鏈表的冊I除運算ListDelete(&Lj&e)的實現(xiàn)

基本操作：刪除鏈表中第i個結(jié)點，首先在單鏈表

中找到刪除位置前一個結(jié)點a1,并用指針p指向

它，刪除后的結(jié)點需動態(tài)的釋放。如下圖2?10所

示。假定刪除的結(jié)點是值為%的結(jié)點。圖240(c)

中虛線表示刪除結(jié)點外后的指針指向。

具體算法描述為：

06:4449

p

(b)返回被刪除結(jié)點數(shù)據(jù)e

n

q

e=q—>data；

(c)修改指針域，將結(jié)點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

算法的時間復(fù)雜度：O(ListLength(L))

06:4451

在插入和刪除算法中，都是先查詢確定操作位置，然后再

進行插入和刪除操作。所以其時間復(fù)雜度均為。㈤。另外在算

法中實行插入和刪除操作時沒有移動元素的位置，只是修改了

指針的指向，所以采用鏈表存儲方式要比順序存儲方式的效率

高。-

在插入和刪除算法中，我們分別用了c語言中的兩個標準函

數(shù)malloc和free。在設(shè)有“指針”數(shù)據(jù)類型的高級語言中均存在

與其相應(yīng)的過程和函數(shù)。

p二(LinkList)malloc(sizeof(LNode))：系統(tǒng)生成一^個

Lnode型的結(jié)點，同時將該結(jié)點的起始位置賦給指針變量p；

Free(q)：系統(tǒng)回收一個Lnode型的結(jié)點，回收后的空間

可以備作再次生成結(jié)點時用。

06:4452

以上我們講了鏈表的3個主要操作：取第i個數(shù)據(jù)

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

本身的生成與順序表截然不同。

單鏈表和順序存儲結(jié)構(gòu)不同，它是一種動態(tài)存

儲結(jié)構(gòu)。整個可用存儲空間可為多個鏈表共同享用，

每個鏈表占用的空間不需預(yù)先分配劃定，而是可以

由系統(tǒng)應(yīng)需求即時生成。因此建立線性表的鏈式存

儲結(jié)構(gòu)的過程就是一個動態(tài)生成鏈表的過程。即從

“空表”的初始狀態(tài)起，依次建立各結(jié)點，并逐個

插入鏈表。

06:4453

VoidCreateList-L(LinkList&L,intn){

〃逆位序輸入n個元素的值，建立帶表頭結(jié)點的單鏈線性表L

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

L->next=null;〃先建立一個帶頭結(jié)點的單鏈表(頭結(jié)點的指針域為空)

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

p=(LinkList)malloc(sizeof(Lnode));〃生成新結(jié)點

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

p->next=L->next;

L->next=p;

}//for

}//CreateList-L算法的時間復(fù)雜度：O(listlength(L))

06:4454

用上述定義的單鏈表實現(xiàn)線性表的操作時，存在的問題：

1.單鏈表的表長是一個隱含的值；

2.在單鏈表的最后一個位置插入元素時，需遍歷整個鏈表；

3.在鏈表中，元素的“位序”概念淡化，結(jié)點的“位置”概念強

化。

改進鏈表的設(shè)置：

1.增加“表長”、“表尾指針”和“當前位置的指針”三個

數(shù)據(jù)域；

2.將基本操作由“位序”改變?yōu)椤爸羔槨薄?/p>

06:4455

四、一個帶頭結(jié)點的線性鏈表類型

TypedefStructLNode{〃結(jié)點類型

ElemTypedata;

structLnode*next;

}*Link,"Position；

StatusMakeNode(Link&P,ElemTypee);

//分配由p指向的值為e的結(jié)點，并返回OK；

//若分配失敗，則返回ERROR；

VoidFreeNode(Link&P);

//釋放p所指結(jié)點

06:4456

TypedefStruct{〃鏈表類型

Linkhead,tail;〃指向頭結(jié)點和最后一個結(jié)點

intlen;//指示鏈表長度

Linkcurrent;

〃指向當前訪問的結(jié)點的指針，初始位置指向頭結(jié)點

}Linklist；

06:4457

鏈表的基本操作：

｛結(jié)構(gòu)初始化和銷毀結(jié)構(gòu)｝

｛引用型操作｝

｛加工型操作｝

看書上P37頁

58

06:44

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

〃在帶頭結(jié)點的單鏈線性表L的第i個元素之前插入元素e

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

If(InsAfter(L,e))returnOK;//插入在第i?l結(jié)點之后

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中剩余結(jié)點

ElseAppend(Lc,pb);〃鏈接Lb中乘U余結(jié)點

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

〃釋放La和Lb的頭結(jié)點

}//MergeList-L

06:4461

靜態(tài)鏈表

L有些高級程序設(shè)計語言中沒有指針類型，這可以通過定義

一個結(jié)構(gòu)體數(shù)組實現(xiàn)類似于“鏈表”結(jié)構(gòu)的形式，即用數(shù)組

實現(xiàn)的線性鏈表，稱為靜態(tài)鏈表。由于它是利用數(shù)組定義的,

一在整個運算過程中存儲空間的大小不會發(fā)生變化,因此稱這

一種結(jié)構(gòu)為靜態(tài)鏈表。gS

2.靜態(tài)鏈表的類型定義：

#defineMAXSIZE100〃鏈表的最大長度

typedefStruct{

ElemTypedata;

intcur;

}Component,SLinkList[MaxSize];

06:4462

3.靜態(tài)鏈表

靜態(tài)鏈表是用數(shù)組描述線性鏈表。

靜態(tài)鏈表的每個結(jié)點由兩個數(shù)據(jù)成員構(gòu)成：

“數(shù)據(jù)域Data:存儲數(shù)據(jù)元素

1游標Cur：存儲直接后繼元素所在的數(shù)組下標

datanext

011EO

I-Q?

2C9

head

1a33

44A7

2b45

3c26

7B2

4d58

9D1

5e-1IO

06:446(a)iB0AfckMt于

4.靜態(tài)鏈表的操作：a-c-b-d-e

在d之前插入f,變成a-c-b-f-d?e

01

1a3

2b6

3c2

4d5

5e-1

6f4

06:4464

靜態(tài)鏈表的操作：a-c-b-d-e

刪除b,變成a?c?d?e

0

1

2

3

4

5

6

06:4465

四、其它形式的鏈表

1.循環(huán)鏈表

在單鏈表中，最后一個結(jié)點的指針域為空(NULL)。

訪問單鏈表中任何數(shù)據(jù)只能從鏈表頭開始順序訪問，而不能

進行任何位置的隨機查詢訪問。如要查詢的結(jié)點在鏈表的尾

部也需遍歷整個鏈表。所以單鏈表的應(yīng)用受到一定的限制。

循環(huán)鏈表(CircularLinkedList)是另一種形式的鏈式存儲

結(jié)構(gòu)。它將單鏈表中最后一個結(jié)點的指針指向鏈表的頭結(jié)點,

使整個鏈表頭尾相接形成一個環(huán)形。這樣，從鏈表中任一結(jié)

點出發(fā)，順著指針鏈都可找到表中其它結(jié)點。循環(huán)鏈表的最

大特點是不增加存儲量，只是簡單地改變一下最后一個結(jié)點

的指針指向，就可以使操作更加方便靈活。圖2/3是循環(huán)鏈

裝15存儲結(jié)構(gòu)示意圖。66

head

￡?at0&A0N??At

江劭產(chǎn)柵嬲41a"a/+???.可^^..?f^

￡'bt0I,ftAN??Afh

2.13循環(huán)鏈表結(jié)構(gòu)示意圖

帶頭結(jié)點的單循環(huán)鏈表的操作算法和帶頭結(jié)點的單鏈表的

操作算法很相似，差別僅在于算法中的循環(huán)條件不同。條件不

是p或p?>next是否為空，而是它們是否指向頭結(jié)點。

06:4467

2,雙向鏈表

單鏈表只有一個指向后繼的指針來表示結(jié)點間的邏輯關(guān)系。故

從任一結(jié)點開始找其后繼結(jié)點很方便，但要找前驅(qū)結(jié)點則比較困難。

雙向鏈表是用兩個指針表示結(jié)點間的邏輯關(guān)系。即增加了一個指向

其直接前驅(qū)的指針域，這樣形成的鏈表有兩條不同方向的鏈，前驅(qū)

和后繼，因此稱為雙鏈表。在雙鏈表中，根據(jù)已知結(jié)點查找其直接

前驅(qū)結(jié)點可以和查找其直接后繼結(jié)點一樣方便。這里也僅討論帶頭

結(jié)點的雙鏈表。仍假設(shè)數(shù)據(jù)元素的類型為ElemType。

雙向鏈表結(jié)點的定義如下：

typedefstructDuLNode{

ElemTypedata;priordatanext

structDuLNode*prior;

structDuLNode*next;

圖2/5雙向鏈表結(jié)點結(jié)構(gòu)圖

}DuLnode,*DuLinkList;

桀虛的結(jié)構(gòu)如圖2?15所示。

(b)非空雙向鏈表

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

圖2-16帶頭結(jié)點的雙向鏈表

雙向鏈表的優(yōu)點：找當前指針的前驅(qū)是限量級的，而不是

線性的。

在雙向鏈表中，有些操作如求表長(ListLength)、取元素

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

指針，則它們的算法描述和線性表的操作相同，但在插入和刪

除時有很大不同，需要修改兩個方向的指針。

06:4469

關(guān)鍵語句：

@s->prior=p->prior;

@p->prior->next=s;

@s->next=p;

(a)插入前的狀態(tài)@p->prior=s;

(b)插入過程

圖2-17雙鏈表插入結(jié)點示意圖

注意：在圖2?17中，關(guān)鍵語句指針操作序列既不是唯一也不是任意

的。操作①必須在操作④之前完成，否則*p的前驅(qū)結(jié)點就丟掉了。

06:4470

p

關(guān)鍵語句：

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

(a)刪除前狀態(tài)

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

③free(p)；

②

(b)刪除過程

注意：在雙向鏈表中進行插入和刪除時，對指

針的修改需要同時修改結(jié)點的前驅(qū)指針和后繼

指針的指向。

06:4471

2.4線性表的應(yīng)用——一元多項式的表示及相加

1.一元多項式表示

鏈式存儲結(jié)構(gòu)的典型應(yīng)用之一是在高等數(shù)學(xué)的多項式方面。

本節(jié)主要討論采用鏈表結(jié)構(gòu)表示的一元多項式的操作處理。

在數(shù)學(xué)上，一個一元多項式P0(X)可以表示為：

211

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

Pi*i是多項式的第i項(OWign)。其中R為系數(shù)，x為自變

量，i為指數(shù)。多項式中有n+1個系數(shù)，而且是線性排列。

一個多項式由多個(IWiWm)項組成，每個多項式

coefexpnnext

06:4472

coefexpnnext

其中，coef數(shù)據(jù)域存放系數(shù)p〕expn數(shù)據(jù)域存放指數(shù)g；

next域是一個鏈域，指向下一個結(jié)點。由此，一個多項式可以

表示成由這些結(jié)點鏈接而成的單鏈表(假設(shè)該單鏈表是帶頭結(jié)

點的單鏈表)。

在計算機中，多項式可用一個線性表listP來表示：listP=(

Po,PrP2…，PQ。但這種表示無法分清每一項的系數(shù)和指

數(shù)。所以可以采用另一種表示一元多項式的方法：listP={Ip。

，e0