線性表教學(xué)課件

第2章線性表

2.1線性表的基本概念

2.2線性表的類型定義

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

2.4線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

2.4.1線性鏈表

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

2.4.3雙向鏈表

2.5一元多項(xiàng)式的表示及相加

06:441

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

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

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

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

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

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

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

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

06:442

2.1線性表的基本概念

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

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

1.線性表的定義

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

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

的長(zhǎng)度?？?/p>

當(dāng)n=0時(shí)稱為空表，即不含有任何元素。

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

(ara2,…分)

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

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

06:443

例1、26個(gè)英文字母組成的字母表

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

例2、從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況。

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

例3、

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

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

20021418^吳小軍d男Q20-計(jì)算機(jī)系024^天津21

20021419P王乾龍*男Q20計(jì)算機(jī)系024c山東淄博?

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

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

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

06:444

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

在非空的線性表，有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)藥,它沒(méi)有直接

前趨，而僅有一個(gè)直接后繼a2；

有且僅有一個(gè)終端結(jié)點(diǎn)a。，它沒(méi)有直接后繼，而僅有一個(gè)

直接前趨an.1；

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

和一個(gè)直接后繼ai+1o

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

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

是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。

06:445

2.1線性表的類型定義

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

ADTList｛

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

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)造一個(gè)空的線性表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中元素個(gè)數(shù)。

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

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

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

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

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

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

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

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

06:448

GetElem(L,i,&e)

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

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

LocateElem(L,e,compare())

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

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

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

ListTraverse(L,visit())

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

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

則操作失敗。

06:449

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

ClearList(&L)

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

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

PutElem(L,i,&e)

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

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

Listinsert(&L,i,e)

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

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

素，插入后原表長(zhǎng)增1。

06:4410

ListDelete(&LJ,&e)

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

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

刪除后表長(zhǎng)減1。

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

06:4411

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

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

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

上述問(wèn)題可演繹為，要求對(duì)線性表作如下操作：

擴(kuò)大線性表LA,將存在于線性表LB中而不存在于

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

06:4412

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

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

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

第二步：依值在線性表LA中進(jìn)行查訪；

LocateElem(LA,e,equalO)

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

Listinsert(LA,n+1,e)

用C語(yǔ)言寫成的程序如下：

06:4413

voidunion(List&LA,ListLB){

〃將所有在線性表LB中而不在LA中的數(shù)據(jù)元素插入到LA中。(見(jiàn)書(shū)p20)

La-len=ListLength(LA);的長(zhǎng)度

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：已知一個(gè)非純集合B,試構(gòu)造一個(gè)純集合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個(gè)數(shù)據(jù)元素賦給e

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

++La-en;

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

}//if」

}//for

器劈度15

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

時(shí)，則程序?qū)⒏?jiǎn)單。

Voidpurge(List&La,ListLb){

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

La-len=ListLength(La);的長(zhǎng)度

Lb-len=ListLength(Lb);

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

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

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

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

en=e;

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

}//for

}//purge

06:4416

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

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

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

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

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

表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中取得當(dāng)前元素如和與；

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

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

用這種方法存儲(chǔ)的線性表簡(jiǎn)稱順序表。

ala2■■■ai-lai■■■an

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

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

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

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

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

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

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

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

機(jī)存儲(chǔ)空間中的存儲(chǔ)地址由該元素在線性表中的序號(hào)惟一確

定。一般來(lái)說(shuō)，長(zhǎng)度為n的線性表(ara2,an)在計(jì)算機(jī)

中的結(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語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可

以用數(shù)組類型來(lái)描述順序表。又因?yàn)槌擞脭?shù)組來(lái)存儲(chǔ)線

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

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

序號(hào)12...i...n<---空閑----?

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

i???4???n

下標(biāo)

o1ilength_1MaxLen"1

06:4423

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

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

此處的元素類型用ElemType來(lái)表示。

綜上所述，在C語(yǔ)言中，可用下述類型定義來(lái)描述順序表：

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

#defineLISTINCREMENT10〃線性表存儲(chǔ)空間的分配增量

typedefstruct{

ElemType*elem;〃存儲(chǔ)空間基址

intlength;〃線性表的實(shí)際長(zhǎng)度

intlistsize；〃當(dāng)前分配的存儲(chǔ)容量，

//(以sizeof(ElemType)為單位

JsqList;

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

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

06:4424

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

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

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

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

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

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

*sizeof(ElemType));

if(!L.elem)exit(OVERFLOW);〃存儲(chǔ)分配失敗

L?length=O;〃空表長(zhǎng)度為0

L.listsize=LIST-INIT-SIZE;

returnok;

}IIInitList-Sq

06:4425

2.順序表的查找算法LocateElem的實(shí)現(xiàn)：

intLocateElem-Sq(SqListL,ElemTypee

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

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

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

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

if(i<=L.length)returni;

elsereturn0;

}//LocateElem-Sq

由算法可知，對(duì)于表長(zhǎng)為n的順序表，在查找過(guò)程中，

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

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

06:4426

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

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

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

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

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

Ki<n+1o

06:4427

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

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

06:44插入前插入后28

StatusListlnsert-Sq(SqList&LZintifElemTypee){

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

if(L.length>=L.lis七size){//當(dāng)前存儲(chǔ)空間已滿,增加分配

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

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

if(!newbase)exit(overflow);//存儲(chǔ)分酉已失敗

L.elem=newbase;〃新基址

L.listsize+=LISTINCREMENT;//增力口存儲(chǔ)容量

}

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;//表長(zhǎng)度力口1

returnOk;

}/4^|stInsert-Sq

29

該算法的時(shí)間主要花費(fèi)在移動(dòng)數(shù)據(jù)元素上，移動(dòng)個(gè)數(shù)取決于插

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

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

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

當(dāng)》=11+1時(shí)，不需要移動(dòng)結(jié)點(diǎn)；當(dāng)i=l時(shí)需要移動(dòng)n個(gè)結(jié)點(diǎn)。由

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

復(fù)雜性是。伽

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

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

數(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

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

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

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

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

?順序表的刪除運(yùn)算是指將表中第i個(gè)元素從線性表中去

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

an)o進(jìn)行刪除以后的線性表表長(zhǎng)變?yōu)榈谋?%,a2,...,

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

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

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

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線性表中的刪除運(yùn)算示意圖

06:4432

在線性表上完成上述運(yùn)算通過(guò)以下兩個(gè)操作來(lái)實(shí)現(xiàn)：

(1)線性表中第i個(gè)至第n個(gè)元素(共n-i個(gè)元素)依次

向前移動(dòng)一個(gè)位置。將所刪除的元素如覆蓋掉，從而

保證邏輯上相鄰的元素物理位置也相鄰。

⑵修改線性表長(zhǎng)度，使其減1。

06:4433

線性表的刪除算法如下：

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

〃刪除線性表中第i個(gè)位置上的元素，

〃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；〃被刪兀素之后的兀素向而移動(dòng)

—L.length;三1

returnOK；

}//ListDelete-Sq

06:4434

刪除算法的時(shí)間性能分析：

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

元素上，刪除第i個(gè)元素時(shí)，其后面的元素aj+i?都要向前移動(dòng)

一個(gè)位置，共移動(dòng)了n-i個(gè)元素，所以在等概率的情況下，在線性

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

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

耳必=E—z>

Z=1

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

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

n5n1

1n—\

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

/=1nz=i2

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

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

06:4435

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

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

后、素°

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

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

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

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

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

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

06:4436

2.3線性表類型的實(shí)現(xiàn)一鏈?zhǔn)接诚?/p>

」線性表的順序表示的特點(diǎn)是用物理位置上的鄰接

關(guān)系來(lái)表示結(jié)點(diǎn)間的邏輯關(guān)系，故可以隨機(jī)存取表中

的任一結(jié)點(diǎn)；但在插入和刪除操作時(shí)需移動(dòng)大量的結(jié)

點(diǎn)。d

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

儲(chǔ)方式：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱鏈表。

鏈?zhǔn)酱鎯?chǔ)方式可用于表示線性結(jié)構(gòu)，也可用于表

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

06:4437

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

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是利用任意的存儲(chǔ)單元來(lái)存放線性表中的元素,

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

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

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

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

輯關(guān)系的信息。所以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示線性表中的一個(gè)元素時(shí)

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

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

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

⑥/?Qg6

datanext

06:4438

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

TypedefstructLNode{

ElemTypedata;//結(jié)點(diǎn)值

structLNode*next;//指針域，存儲(chǔ)下一個(gè)結(jié)點(diǎn)的地址

}LNoder*LinkList;

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

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

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

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

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

空指針，C語(yǔ)言用NULL或0來(lái)表示，在圖中表示為“八”。

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

結(jié)點(diǎn)，該線性表在存儲(chǔ)空間中的存儲(chǔ)情況如圖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àn)，每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址存

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

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

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

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

其指針域得到存儲(chǔ)數(shù)據(jù)C的結(jié)點(diǎn)地址，訪問(wèn)

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

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

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

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

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

06:4441

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

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

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

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

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

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

數(shù)據(jù)元素之間的邏輯關(guān)系由指針來(lái)確定。由于鏈?zhǔn)?/p>

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

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

06:4442

三、單鏈表

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

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

向訪問(wèn)。稱這種鏈表為單向鏈表或線性鏈表。這是一種最簡(jiǎn)單

的鏈表。

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

對(duì)于空鏈表，頭結(jié)點(diǎn)的指針域?yàn)榭?。圖2?8是帶頭結(jié)點(diǎn)的鏈

表示方式：head

(a)6Aft

head

a.￡,b)Q0At

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

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

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

始位置計(jì)算得到。而在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間

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

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

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

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

單鏈表中第j個(gè)元素值，必須從頭指針開(kāi)始遍歷鏈表，依次訪問(wèn)每

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

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

06:4444

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

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

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

StatusGetElem(LinkListL,inti,ElemType&e)

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

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

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

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

e=p->data;//取第i個(gè)元素

returnok;

}//GetElem_L

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

06:4445

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

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

向新的鏈接位置來(lái)完成的插入操作，而無(wú)需移動(dòng)任何元素。

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

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

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

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

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

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

06:4446

p

▼

a?>a.____

(a)找到插入位置

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

s->data=e；

6)申請(qǐng)新結(jié)點(diǎn)s,數(shù)據(jù)域置e

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

圖2-9插入s結(jié)點(diǎn)過(guò)程示意圖

上述指針進(jìn)行相互賦值的語(yǔ)句順序不能顛倒。

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é)點(diǎn)

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

returnok;

}//ListlnsertL

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

06:4448

3.鏈表的冊(cè)I除運(yùn)算ListDelete(&Lj&e)的實(shí)現(xiàn)

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

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

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

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

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

具體算法描述為：

06:4449

p

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

n

q

e=q—>data；

(c)修改指針域，將結(jié)點(diǎn)q刪除

free(q);

圖2?10線性鏈表的刪除過(guò)程示意圖

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

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

06:4451

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

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

法中實(shí)行插入和刪除操作時(shí)沒(méi)有移動(dòng)元素的位置，只是修改了

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

高。-

在插入和刪除算法中，我們分別用了c語(yǔ)言中的兩個(gè)標(biāo)準(zhǔn)函

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

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

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

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

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

可以備作再次生成結(jié)點(diǎn)時(shí)用。

06:4452

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

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

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

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

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

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

由系統(tǒng)應(yīng)需求即時(shí)生成。因此建立線性表的鏈?zhǔn)酱?/p>

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

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

插入鏈表。

06:4453

VoidCreateList-L(LinkList&L,intn){

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

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

L->next=null;〃先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表(頭結(jié)點(diǎn)的指針域?yàn)榭?

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

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

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

p->next=L->next;

L->next=p;

}//for

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

06:4454

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

1.單鏈表的表長(zhǎng)是一個(gè)隱含的值；

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

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

化。

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

1.增加“表長(zhǎng)”、“表尾指針”和“當(dāng)前位置的指針”三個(gè)

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

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

06:4455

四、一個(gè)帶頭結(jié)點(diǎn)的線性鏈表類型

TypedefStructLNode{〃結(jié)點(diǎn)類型

ElemTypedata;

structLnode*next;

}*Link,"Position；

StatusMakeNode(Link&P,ElemTypee);

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

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

VoidFreeNode(Link&P);

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

06:4456

TypedefStruct{〃鏈表類型

Linkhead,tail;〃指向頭結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)

intlen;//指示鏈表長(zhǎng)度

Linkcurrent;

〃指向當(dāng)前訪問(wèn)的結(jié)點(diǎn)的指針，初始位置指向頭結(jié)點(diǎn)

}Linklist；

06:4457

鏈表的基本操作：

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

｛引用型操作｝

｛加工型操作｝

看書(shū)上P37頁(yè)

58

06:44

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

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

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

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

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é)點(diǎn)

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

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

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

}//MergeList-L

06:4461

靜態(tài)鏈表

L有些高級(jí)程序設(shè)計(jì)語(yǔ)言中沒(méi)有指針類型，這可以通過(guò)定義

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

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

一在整個(gè)運(yùn)算過(guò)程中存儲(chǔ)空間的大小不會(huì)發(fā)生變化,因此稱這

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

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

#defineMAXSIZE100〃鏈表的最大長(zhǎng)度

typedefStruct{

ElemTypedata;

intcur;

}Component,SLinkList[MaxSize];

06:4462

3.靜態(tài)鏈表

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

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

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

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

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)鏈表

在單鏈表中，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭?NULL)。

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

進(jìn)行任何位置的隨機(jī)查詢?cè)L問(wèn)。如要查詢的結(jié)點(diǎn)在鏈表的尾

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

循環(huán)鏈表(CircularLinkedList)是另一種形式的鏈?zhǔn)酱鎯?chǔ)

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

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

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

大特點(diǎn)是不增加存儲(chǔ)量，只是簡(jiǎn)單地改變一下最后一個(gè)結(jié)點(diǎn)

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

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

head

￡?at0&A0N??At

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

￡'bt0I,ftAN??Afh

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

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

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

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

06:4467

2,雙向鏈表

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

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

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

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

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

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

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

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

typedefstructDuLNode{

ElemTypedata;priordatanext

structDuLNode*prior;

structDuLNode*next;

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

}DuLnode,*DuLinkList;

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

(b)非空雙向鏈表

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

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

雙向鏈表的優(yōu)點(diǎn)：找當(dāng)前指針的前驅(qū)是限量級(jí)的，而不是

線性的。

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

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

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

除時(shí)有很大不同，需要修改兩個(gè)方向的指針。

06:4469

關(guān)鍵語(yǔ)句：

@s->prior=p->prior;

@p->prior->next=s;

@s->next=p;

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

(b)插入過(guò)程

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

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

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

06:4470

p

關(guān)鍵語(yǔ)句：

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

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

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

③free(p)；

②

(b)刪除過(guò)程

注意：在雙向鏈表中進(jìn)行插入和刪除時(shí)，對(duì)指

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

指針的指向。

06:4471

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

1.一元多項(xiàng)式表示

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的典型應(yīng)用之一是在高等數(shù)學(xué)的多項(xiàng)式方面。

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

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

211

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

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

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

一個(gè)多項(xiàng)式由多個(gè)(IWiWm)項(xiàng)組成，每個(gè)多項(xiàng)式

coefexpnnext

06:4472

coefexpnnext

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

next域是一個(gè)鏈域，指向下一個(gè)結(jié)點(diǎn)。由此，一個(gè)多項(xiàng)式可以

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

點(diǎn)的單鏈表)。

在計(jì)算機(jī)中，多項(xiàng)式可用一個(gè)線性表listP來(lái)表示：listP=(

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

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

，e0