數(shù)據(jù)結(jié)構(gòu)-用C語(yǔ)言描述第二版第2章線性表-2

第二章

線性表第2章

線性表2.1線性表的基本概念?2.2線性表的順序存儲(chǔ)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表存儲(chǔ)結(jié)構(gòu)的選擇線性表的應(yīng)用舉例第二章

線性表?從本章開始到第四章討論的線性表、棧、隊(duì)列和串的邏輯結(jié)構(gòu)都屬于線性結(jié)構(gòu)。在線性結(jié)構(gòu)中，元素之間存在一個(gè)對(duì)一個(gè)的相互關(guān)系，其邏輯特征為：存在唯一的一個(gè)被稱為“起始”的數(shù)據(jù)元素。存在唯一的一個(gè)被稱為“終端”的元素。除起始元素外，其它每個(gè)元素有且僅有一個(gè)直接前趨。除終端元素之外，其它每個(gè)元素有且僅有一個(gè)直接后繼。本章的基本內(nèi)容：線性表的邏輯結(jié)構(gòu)定義和各種存儲(chǔ)結(jié)構(gòu)、描述方法及其建立在這兩種存儲(chǔ)結(jié)構(gòu)上的運(yùn)算實(shí)現(xiàn)。第2章

線性表第二章

線性表2.1.2線性表的運(yùn)算常見的線性表的基本運(yùn)算：置空表SETNULL(L)：將線性表L置成空表。求長(zhǎng)度LENGTH(L)：求給定線性表L中數(shù)據(jù)元素的個(gè)數(shù)。取元素GET(L,i)：結(jié)果是線性表L中的第i個(gè)數(shù)據(jù)元素。定位函數(shù)LOCATE(L,x)：當(dāng)線性表中存在一個(gè)值為x的數(shù)據(jù)元素，則結(jié)果是該數(shù)據(jù)元素在表中的位序，否則，表示值為x的數(shù)據(jù)元素不存在。前趨函數(shù)PRIOR(L,x)：若x為線性表中的一個(gè)數(shù)據(jù)元素，且其位序大于1，則結(jié)果為x的直接前趨，否則，給出一個(gè)特殊值示出該元素沒有直接前趨。后繼函數(shù)NEXT（L，x）：若x的位序小于LENGTH（L），則結(jié)果為該元素的直接后繼，否則，給出一個(gè)特殊值，示出x無(wú)直接后繼。第二章

線性表插入INSERT(L,x,i)：函數(shù)功能為在線性表L中的第i個(gè)位置上插入一個(gè)值為x的新元素，使運(yùn)算前長(zhǎng)度為n的線性表變?yōu)殚L(zhǎng)度為n+1的線性表。刪除DELETE(L,i)：函數(shù)功能為刪除線性表L中的第i個(gè)數(shù)據(jù)元素，使在此之前長(zhǎng)度為n的線性表L變成長(zhǎng)度為n–1的線性表。利用基本運(yùn)算可以實(shí)現(xiàn)線性表的其它復(fù)雜運(yùn)算。需要指出的是，這里給出的只是定義在邏輯結(jié)構(gòu)上的抽象運(yùn)算，即只關(guān)心這些運(yùn)算是“做什么”的，至于“怎樣實(shí)現(xiàn)”則依賴于所選定的存儲(chǔ)結(jié)構(gòu)。第二章

線性表2.2.1順序表順序表是線性表的順序存儲(chǔ)結(jié)構(gòu)，即按順序存儲(chǔ)方式構(gòu)成的線性表的存儲(chǔ)結(jié)構(gòu)。其存儲(chǔ)方式是：線性表的第一個(gè)元素存放在個(gè)一片連續(xù)的存儲(chǔ)空間開始位置處，第二個(gè)元素緊跟著存放在第一元素之后…，以此類推。利用順序表來(lái)存儲(chǔ)線性表，可借助數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的物理位置相鄰特性來(lái)表示線性表中數(shù)據(jù)元素之間的線性邏輯關(guān)系。設(shè)線性表每個(gè)元素占c個(gè)存儲(chǔ)單元，若以第一個(gè)數(shù)據(jù)元素在存儲(chǔ)單元

中的存儲(chǔ)地址作為起始地址，則可得出線性表中第i個(gè)數(shù)據(jù)元素的地址為：LOC(ai)=LOC(a1)+(i-1)*

c

（1≤i≤LENGTH(L)）這樣，一旦起始地址LOC（a1）

（圖2.1中設(shè)為b）和一個(gè)數(shù)據(jù)元素占用的存儲(chǔ)單元的大?。╟值）確定下來(lái)，就可求出任一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址，顯然，這種表便于進(jìn)行隨機(jī)訪問，因此，順序表是一種隨機(jī)存取的結(jié)構(gòu)。2.2線性表的順序存儲(chǔ)第二章

線性表第二章

線性表在具體實(shí)現(xiàn)時(shí)，可利用高級(jí)程序設(shè)計(jì)語(yǔ)言中的一維數(shù)組即向量來(lái)

為線性表的順序存儲(chǔ)開辟存儲(chǔ)空間，存儲(chǔ)空間大小應(yīng)大于等于線性表

長(zhǎng)度，用一個(gè)整型變量來(lái)表示線性表的長(zhǎng)度，從而可將順序表描述為：#define

MAXSIZE

999typedef

int

elemtype；/*

elemtype表示元素類型，此處設(shè)為int

*/typedef

struct{elemtype

vec[MAXSIZE]；int

len；}sequenlist

；在上面描述中，順序表是一個(gè)結(jié)構(gòu)體類型。其中，vec成員（又稱為數(shù)據(jù)域）指線性表數(shù)據(jù)元素所占用的存儲(chǔ)空間，而len成員（又稱為長(zhǎng)度域）則用于存儲(chǔ)線性表長(zhǎng)度，它表示線性表最后一個(gè)元素在向量中的位置，elemtype則為線性表中數(shù)據(jù)元素類型。第二章

線性表本節(jié)討論在定義線性表順序存儲(chǔ)結(jié)構(gòu)之后，如何在這種結(jié)構(gòu)上實(shí)

現(xiàn)有關(guān)數(shù)據(jù)運(yùn)算。下面重點(diǎn)討論線性表的數(shù)據(jù)元素的插入和刪除運(yùn)算。1．插入運(yùn)算線性表的插入運(yùn)算是指在表的第i個(gè)元素之前插入一個(gè)新的數(shù)據(jù)元素，插入的結(jié)果使得線性表的長(zhǎng)度由n變?yōu)閚+1，線性表的數(shù)據(jù)元素間的邏輯關(guān)系發(fā)生了變化，使得物理存儲(chǔ)順序也發(fā)生相應(yīng)的變化。插入過(guò)程如圖2.2所示。2.2.2順序表上的基本運(yùn)算第二章

線性表第二章

線性表具體算法描述如下：int

insert(sequenlist

*L，

int

i，elemtype

x){

int

j；if

(((*L).len)>=MAXSIZE-1){printf(“the

list

is

overflow!\n”)；/*溢出判斷*/return（0）；}elseif

((

i<1)

||

(

i>(*L).len+1)){printf(“position

is

not

correct!\n”)；return（0）；/*插入位置不正確*/}第二章

線性表else{for(j=(*L).len；j>=i-1；j--)/*后移元素*/(*L).vec[j+1]=(*L).vec[j]；(*L).vec[i-1]=x；/*插入新元素x*/(*L).len=(*L).len+1；/*修改表長(zhǎng)*/}return(1);}

/*insert*/在本算法中是從最后一個(gè)元素開始后移，直到第i個(gè)元素為止。該算法時(shí)間主要花費(fèi)在for循環(huán)語(yǔ)句上，執(zhí)行的次數(shù)為n-i+1。當(dāng)i=1時(shí)，全部元素均參加移動(dòng)，共需要移動(dòng)n次；當(dāng)i=n+1時(shí)，不需移動(dòng)元素。算法在最壞情況下，時(shí)間復(fù)雜度為O(n)，最好情況下時(shí)間復(fù)雜度為O(1)。顯然，元素移動(dòng)的次數(shù)直接影響了算法執(zhí)行時(shí)間。第二章

線性表平均移動(dòng)次數(shù)。假設(shè)pi為在第i個(gè)元素之前插入一個(gè)元素的概率，且為等概率，則平均移動(dòng)次數(shù)的期望值為：其中，當(dāng)1≤i≤n+1時(shí)，p1=p

2=……=pn+1

=可見，在順序存儲(chǔ)的線性表中插入一個(gè)元素，約平均移動(dòng)線性表中一半的元素，顯然，當(dāng)n較大時(shí)，算法效率較低，算法的平均時(shí)間復(fù)雜度為O(n)。2．刪除運(yùn)算刪除運(yùn)算是指將線性表中的第i個(gè)元素刪除，使線性表的長(zhǎng)度由n變成

n-1，由：(a1，a2，…，a

i-1，ai，a

i+1，…，an)

變成為：

(a1，a2，…，a

i-1，a

i+1，…，an)其中，1≤i≤n。線性表進(jìn)行刪除元素后，仍是一個(gè)線性表。刪除過(guò)程如圖2.3所示。第二章

線性表第二章

線性表具體算法如下：void

delete(L，i)sequenlist

*L；int

i；{

int

j；if

((i<1)

||

(i>(*L).len+1))printf(“delete

fail！\n”)；/*刪除位置不正確*/else{*y=(*L).vec[i-1]；/*y為一外部變量，用于接收被刪除的元素*/for(j=i；j<=(*L).len；j++)(*L).vec[j-1]=(*L).vec[j]；/*元素前移*/(*L).Len--；/*修改表長(zhǎng)*/}}

/*delete*/第二章

線性表與插入算法相似，要?jiǎng)h除一個(gè)元素需向前移動(dòng)元素，刪除第i個(gè)元素時(shí)，將第i+1，i+2，…，n個(gè)元素依次前移，其移動(dòng)次數(shù)為n-i，假設(shè)刪除線性表中的任一位置上元素的概率相等（等于1/n），則刪除運(yùn)算所需的移動(dòng)元素的平均移動(dòng)次數(shù)如下所示。由此可見，對(duì)線性表刪除一個(gè)元素時(shí)，約需有一半的元素參加移動(dòng)。顯然，該算法的時(shí)間復(fù)雜度為Ｏ(n)。通過(guò)以上討論可以發(fā)現(xiàn)，當(dāng)表長(zhǎng)較大時(shí)，對(duì)順序存儲(chǔ)結(jié)構(gòu)進(jìn)行插入和刪除運(yùn)算，由于要移動(dòng)元素，運(yùn)算效率低，但這種存儲(chǔ)結(jié)構(gòu)對(duì)于隨機(jī)存取元素卻十分方便。第二章

線性表例如，一個(gè)線性表中可能含有重復(fù)的元素（值相同），現(xiàn)要求刪除重復(fù)元素中的多余元素，只保留其中位序最小的一個(gè)。如線性表（5，2，2，

3，5，2），經(jīng)過(guò)清除重復(fù)元素后變?yōu)?5，2，3)。假定線性表以順序存儲(chǔ)方式存儲(chǔ)，則其算法可描述如下：void

purge(sequenlist

*L

){

int

i=0，j

，k；while

(

i<=(*L).Len-1){

j

=

i+1；while

(

j<=(*L).Len-1)if

((*L).vec[i]=

=(*L).vec[j]){

for

(

k

=j；k<=(*L).

Len-1；k

++)(*L).vec[k–1]=(*L).vec[k]；/*元素前移*/(*L).Len--；/*修改表長(zhǎng)度*/}elsej

+

+；i

+

+；}}

/*

purge

*/第二章

線性表線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：無(wú)需為表示數(shù)據(jù)元素之間的關(guān)系而增加額外存儲(chǔ)空間；可以方便地隨機(jī)存取表中任一元素。必須預(yù)先為線性表分配空間，表容量難以擴(kuò)充，必須按線性表最大可能的長(zhǎng)度分配空間，有可能造成存儲(chǔ)空間浪費(fèi)。插入和刪除運(yùn)算時(shí)必須移動(dòng)大量元素，效率較低；為避免大量元素的移動(dòng)，本節(jié)討論線性表的另一種存儲(chǔ)結(jié)構(gòu)，即鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是最常用的存儲(chǔ)方法之一，它不僅可以表示線性表，而且可以表示各種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。這種結(jié)構(gòu)按不同的分類方法可分為單鏈表、循環(huán)鏈表和雙向鏈表等。2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)第二章

線性表2.3.1單鏈表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是利用任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素，這些單元可以是連續(xù)的，也可以是不連續(xù)的。由于線性表中各元素間存在著線性關(guān)系，每一個(gè)元素有一個(gè)直接前驅(qū)和一個(gè)直接后繼，為了表示出每個(gè)元素與其直接后繼之間的關(guān)系，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，除了存儲(chǔ)元素本身的信息外，還需要存儲(chǔ)指示其直接后繼的信息，所以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示線性表中的一個(gè)元素時(shí)其結(jié)點(diǎn)形式至少需要兩部分，其中，用一個(gè)域存儲(chǔ)數(shù)據(jù)元素本身的信息（稱作數(shù)據(jù)域），用另一個(gè)域存儲(chǔ)直接后繼的信息（稱作指針域或鏈域），結(jié)點(diǎn)結(jié)構(gòu)如下圖。第二章

線性表第二章

線性表這樣，利用每個(gè)結(jié)點(diǎn)的指針域就可以將n個(gè)結(jié)點(diǎn)按其邏輯次序連成一個(gè)鏈表，這種鏈表中每個(gè)結(jié)點(diǎn)只含一個(gè)指針域，故稱為線性鏈表或單鏈表。例如，線性表（red，orange，white，yellow，green，blue），其單鏈表的存儲(chǔ)方式如圖2.4所示。由于單鏈表中第一個(gè)結(jié)點(diǎn)無(wú)直接前趨，可另設(shè)一個(gè)頭指針head存儲(chǔ)第一個(gè)結(jié)點(diǎn)的地址。同樣，最后一個(gè)結(jié)點(diǎn)無(wú)直接后繼，其指針域?yàn)榭罩导礊镹ULL，有時(shí)用^表示。整個(gè)單鏈表可由頭指針唯一地確定。單鏈表是一

種非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。也可以將圖2.4中的單鏈表直觀地畫成如圖2.5所示，其中箭頭用來(lái)表示鏈域中的指針。第二章

線性表單鏈表可以用C語(yǔ)言中的指針數(shù)據(jù)類型實(shí)現(xiàn)，描述如下：typedef

int

elemtype；typedef

struct

node{

elemtype

data

；/*結(jié)點(diǎn)類型定義*//*數(shù)據(jù)域*/struct

node

*next；/*定義指針域*/}

linklist

；linklist

*

head，*p；/*

head，p為單鏈表指針類型*/另外，利用C語(yǔ)言中的指針數(shù)據(jù)類型要注意指針變量和結(jié)點(diǎn)變量，其關(guān)系如圖2.6所示。第二章

線性表2.3.2單鏈表上的基本運(yùn)算為了便于實(shí)現(xiàn)各種運(yùn)算，常在單鏈表的第一個(gè)結(jié)點(diǎn)之前增設(shè)一個(gè)附加的結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，其它的結(jié)點(diǎn)稱為表結(jié)點(diǎn)。本章若無(wú)特殊說(shuō)明，均采用帶頭結(jié)點(diǎn)的單鏈表，如圖2.7的(a)，(b)所示。第二章

線性表1．建立單鏈表（1）建立帶頭結(jié)點(diǎn)的單鏈表linklist

*

creatlist()/*函數(shù)返回一個(gè)指向單鏈表表頭的指針*/{

char

ch；int

x

；linklist

*head

，

*r

，

*p

；p

=（linklist

*）malloc（sizeof（linklist））；head

=

p

；p->next=NULL；/*生成頭結(jié)點(diǎn)*/r=p；/*建立單鏈表表尾指針*/ch=getchar()；/*ch為建立與否標(biāo)志*/while(ch!=‘?’)/*‘?’為輸入結(jié)束標(biāo)志符*/{scanf(“%d”,&x)；/*讀入新數(shù)據(jù)元素*/p

=（linklist

*）malloc

(sizeof

(linklist

))；p->data

=

x

;p->next=NULL；/*生成新結(jié)點(diǎn)*/r->next=p；/*連接新結(jié)點(diǎn)*/r=r->next；/*修改尾指針*/ch=getchar()；/*讀入建立與否的標(biāo)志*/}return(head)；/*返回表頭指針head

*/}

/*

creatlist

*/第二章

線性表（2）建立不帶頭結(jié)點(diǎn)的單鏈表linklist

*

creatlist()/*函數(shù)返回一個(gè)指向鏈表表頭的指針*/{char

ch；int

x

；linklist

*head

，*p，*rhead

=NULL

；r

=NULL

；

/*設(shè)立尾指針r，其初值為空*/ch

=

getchar

(

)；

/*讀入建立與否標(biāo)志*/while(ch!=‘?’)

/*‘?’為輸入結(jié)束標(biāo)志符*/{p=(linklist

*)malloc(sizeof(linklist))；/*申請(qǐng)新結(jié)點(diǎn)空間*/scanf(“%d”，&x)；p->data

=

x

;if

(head

=

=

NULL)

head

=

p；else

r->next

=

p；

/*非空表，則新結(jié)點(diǎn)*p插入到*r之后*/r

=

p

；

/*尾指針移動(dòng)，指向新的表尾*/ch=getchar()；/*讀入建立與否的標(biāo)志*/}if(r!=NULL)r->next=NULL；return

head；/*返回表頭指針head

*/}

/*

creatlist

*/在算法中引入頭結(jié)點(diǎn)可以不必區(qū)分空表與非空表，可以統(tǒng)一空鏈表與非空鏈表的處理。上述兩個(gè)算法的時(shí)間復(fù)雜度都為O(n)。第二章

線性表2.單鏈表上元素的檢索一般情況下，可以按某個(gè)元素的序號(hào)或按某給定值兩種方法檢索。（1）按值檢索按值檢索，即是檢索單鏈表中是否存在值為給定值k的結(jié)點(diǎn)，整個(gè)過(guò)程可以通過(guò)結(jié)點(diǎn)的值和給定值的比較而實(shí)現(xiàn)。linklist

*locate（

linklist

*head

，

elemtype

k

）{

linklist

*s；s=head->next；/*從第一個(gè)結(jié)點(diǎn)起開始比較*/while(s!=NULL)/*掃描整個(gè)鏈表*/if

(

s->data

!=

k)s

=

s->next

；elsebreak

；return

s；

/*返回結(jié)點(diǎn)的位置或NULL*/}

/*Locate*/算法時(shí)間復(fù)雜度為O(n)。第二章

線性表（2）按序號(hào)檢索即利用被訪問結(jié)點(diǎn)的序號(hào)而檢索或查找結(jié)點(diǎn)的過(guò)程。linklist

*get(linklist

*head，int

i){

int

j；linklist

*p

；p

=

head

；j

=

0；while

(

(p->next

!=

NULL

)&&(

i

>

j

)){p

=

p->next；j

++

；}if

(i=

=j)

return

p；elsereturn

NULL

；}

/*get

*/該算法中最壞情況下的時(shí)間復(fù)雜度為O(n)。第二章

線性表3．單鏈表上元素的插入和刪除運(yùn)算插入結(jié)點(diǎn)的指針變化圖2.8所示。指針的修改操作為：①s->next=p->next；

②

p->next=s；上述指針進(jìn)行相互賦值的語(yǔ)句順序不能顛倒，若次序變化為：①p->next=s；②s->next=p->next；則會(huì)導(dǎo)致錯(cuò)誤。同樣，要?jiǎng)h除單鏈表結(jié)點(diǎn)*p的后繼結(jié)點(diǎn)也很簡(jiǎn)單，只要用一個(gè)指針指向被刪除結(jié)點(diǎn)，修改*p的指針域，最后釋放結(jié)點(diǎn)*p即可，如圖2.9所示。刪除一個(gè)結(jié)點(diǎn)*

p的后繼結(jié)點(diǎn)的指針操作為：p->next

=

p->next

->next

；不難發(fā)現(xiàn)，在單鏈表存儲(chǔ)結(jié)構(gòu)中進(jìn)行元素的插入和刪除時(shí)，只需要修改有關(guān)的指針內(nèi)容，而不需要移動(dòng)元素。第二章

線性表第二章

線性表（1）插入算法（a）

insert

(linklist

*p

,elemtype

x)/*將值為x的新結(jié)點(diǎn)插入*p之后*/{

linklist

*s；s=（linklist

*）malloc(sizeof(linklist))；/*生成x的新結(jié)點(diǎn)s->data=x；s->next=p->next；/*新結(jié)點(diǎn)鏈入單鏈表*/p->next=s；}

/*insert*/第二章

線性表（b）

voidinsert

(linklist

*head,elemtype

k,elemtype

x)/*在單鏈表中值為k的結(jié)點(diǎn)之前插入一個(gè)值為x的新結(jié)點(diǎn)*/{

linklist

*q，

*p，

*r；r=(linklist

*)malloc(sizeof(linklist))；/*生成新結(jié)點(diǎn)*/r->data=x；if

(

head->next

=

=NULL){

head->next

=

r

；r->next

=

NULL

；}else{

q

=

head->next；p

=

head->next->next

；while

(

p

!

=

NULL

){

if

(

p->data

!

=

k

)

*/{

q

=

p；p

=

p->next

；}elsebreak

；第二章

線性表if

(

p

!

=

NULL

){

q

->next

=

r

；r->next

=

p；}else/*在鏈表表尾處插入新結(jié)點(diǎn)*/{

q

->next

=

r；r->next

=NULL；}}}

/*

insert

*/該算法的時(shí)間主要耗費(fèi)在查找值為k的結(jié)點(diǎn)位置上，算法時(shí)間復(fù)雜度為O(n)。第二章

線性表/*刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)*/（2）刪除算法（a）

delete

(linklist

*p

){

linklist

*r；r

=

p->next

；if(r!=NULL){p->next

=

r->next；free

(r)；}}

/*delete*/（b）linklist

*delete(linklist

*head，int

i)/*刪除單鏈表head的第i個(gè)結(jié){

intj

=

0

；linklist

*p，*s，*q；p

=

head

；j

=

0

；while

((p->next

!=

NULL)&&

(j<

i-1)}{

p

=p->next

；j

++

；}第二章

線性表if

(

p->next!=NULL

){

q

=p->next

；p->next

=

p->next->next

；free

(q)

；}elsereturn

NULL

；s

=

head

；

return

s

；}

/*

delete

*/該算法時(shí)間復(fù)雜度為O(n)。第二章

線性表例，將兩個(gè)遞增的單鏈表合并為一個(gè)遞增單鏈表，且要求不重新開辟空間，其算法可描述如下：void*union

(linklist

*heada，linklist

*headb

)/*合并單鏈表heada與headb

*/{

linklist

*p，*q，*r，*u

；p

=

heada->next

；q

=

headb->next

；r

=

heada

；while

(

p

!

=

NULL

)&&

(q

!

=

NULL

){

if

(

p->data

>

q->data

；{

u

=q->next

；r->next

=

q

；r

=

q

；q->next

=

p

；q

=

u

；}第二章

線性表elseif

(p->data

<

=q->data

){

r

=

p；p

=

p->next

；}}if

(

q

!

=

NULL)

r->next

=

q；}

/*

union

*/第二章

線性表2.3.3循環(huán)鏈表如果將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域改為存放鏈表中頭結(jié)點(diǎn)（或第一個(gè)表結(jié)點(diǎn)）的地址值，就使得整個(gè)鏈表構(gòu)成一個(gè)環(huán)，如圖2.10所示，這樣的鏈表稱為循環(huán)鏈表。顯然，它是一種首尾相接的鏈表，從循環(huán)鏈表中任一個(gè)

結(jié)點(diǎn)出發(fā)都可訪問到表中所有其它結(jié)點(diǎn)。對(duì)單鏈表的鏈接方式稍作一些改

變，就可構(gòu)成一個(gè)新的存儲(chǔ)結(jié)構(gòu)——單循環(huán)鏈表。同樣，也有多重鏈的循

環(huán)鏈表。在循環(huán)鏈表中，為了使空表和非空表的處理一致，同樣可設(shè)置一

個(gè)頭結(jié)點(diǎn)。第二章

線性表循環(huán)鏈表的基本運(yùn)算與單鏈表基本一致，差別只在于最后一個(gè)結(jié)點(diǎn)的循環(huán)處理上。只要將單鏈表算法中出現(xiàn)NULL處改為頭指針即可。例如，將單循環(huán)鏈表倒置或逆置。linklist

*invert(head)

linklist

*head；{linklist

*p，*q，*s;q

=

head；p=

head->next；while

(

p

!

=

head

){

s

=

q

；q

=

p

；p

=

p->next

；q->next

=

s；}p->next

=

q；return

head；}

/*

invert

*/第二章

線性表2.3.4雙向鏈表在單循環(huán)鏈表中，從任一個(gè)已知結(jié)點(diǎn)出發(fā)可以找到其前趨結(jié)點(diǎn)，但時(shí)間耗費(fèi)需O(n)，若希望能快速確定一個(gè)結(jié)點(diǎn)的直接前趨，可以再加上一個(gè)指針域存儲(chǔ)其直接前趨的信息，這樣就可以構(gòu)成雙向鏈表，它有兩個(gè)方向不同的鏈，如果將每個(gè)方向的鏈表構(gòu)成一個(gè)環(huán)，則可以構(gòu)成雙向循環(huán)鏈表。雙向鏈表的C語(yǔ)言描述：typedef

struct

dupnode{

elemtype

data；struct

dupnode*next，*prior；}

dulinklist

；dulinklist

*head

;雙向循環(huán)鏈表也可由頭指針head唯一確定，同樣可增加頭結(jié)點(diǎn)，使得雙鏈表的某些運(yùn)算簡(jiǎn)便一些，如圖2.11所示。第二章

線性表第二章

線性表由于雙向鏈表在其結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)既有指向其直接前趨的指針域，又有指向其直接后繼的指針域，因此比起單鏈表來(lái)，要在一個(gè)雙向鏈表中檢索某一個(gè)已知結(jié)點(diǎn)的直接前趨和后繼結(jié)點(diǎn)要方便得多。結(jié)點(diǎn)*p可通過(guò)多種方式訪問，設(shè)指針p指向雙向鏈表中某個(gè)結(jié)點(diǎn)，則有：p->next->prior=p=p->prior->next雙向鏈表中結(jié)點(diǎn)的插入情況如圖2.12所示。第二章

線性表在*p結(jié)點(diǎn)之前插入結(jié)點(diǎn)*s的正確步驟應(yīng)為：①

p->prior->next

=

s；②

s->prior

=

p->prior；③

s->next

=

p

；④

p->ps；由于雙向鏈表中每個(gè)結(jié)點(diǎn)涉及兩個(gè)指針的運(yùn)算，對(duì)于某些運(yùn)算要注意運(yùn)

算順序。在上面的步驟中指針p->prior的修改必須在*p結(jié)點(diǎn)的前趨結(jié)點(diǎn)*(p->prior)的后繼指針修改之后方可改動(dòng)，否則會(huì)不能正確地插入結(jié)點(diǎn)。在雙向鏈表中刪除一個(gè)結(jié)點(diǎn)*p的指針變化如圖2.13所示。指針修改的運(yùn)算步驟為：①p->prior->next=

p->next；②

p->next->prior

=p->prior；第二章

線性表1．插入算法void

indulist

(dulinklist

*head

,int

i,

elemtype

x)/*在雙向循環(huán)鏈表head中的第i個(gè)結(jié)點(diǎn)之前插入值為x的新結(jié)點(diǎn)*/{

dulinklist

*p，*s

;int

j

;p

=

head

;

j

=

0

;while

((

p->next!

=

head)&&(j

<

i-1)){p

=

p->next

;j++

;}if

((

i

>0)&&(j=

=i-1)){

s

=

malloc

(sizeof(dulinklist))

;s->data

=

x

;s->next

=

p->next

;s->prior

=

p

；p->next

=

s；s->next->prior

=

s

;}else

printf

(

“error！\n”

)/*

indulist

*/第二章

線性表2．刪除算法void

deledulist

(dulinklist

*head,int

i)/*刪除雙向鏈表head中的第i個(gè)結(jié)點(diǎn)*/{

dulinklist

*p

;

int

j

;p

=

head

;

j

=

0

;while

((p->next!

=

head)&&(j

<

i)){

p

=p->next

;j

++

;}if

((

i

>

0)&&(j

=

=

i)){p->prior->next

=

p->next

;p->next->prior

=

p->prior

;free(p)

;}else

printf

(“error\n”);}

/*deledulist*/以上兩個(gè)算法的時(shí)間復(fù)雜度都為O(n)。第二章

線性表2.4線性表存儲(chǔ)結(jié)構(gòu)的選擇一般而言，對(duì)存儲(chǔ)結(jié)構(gòu)的選擇應(yīng)主要從存儲(chǔ)空間、運(yùn)算時(shí)間、程序設(shè)計(jì)語(yǔ)言三方面考慮。存儲(chǔ)空間。運(yùn)算時(shí)間。程序設(shè)計(jì)語(yǔ)言。線性表的順序?qū)崿F(xiàn)和鏈接實(shí)現(xiàn)各有優(yōu)缺點(diǎn)，只能根據(jù)實(shí)際問題的具體實(shí)現(xiàn)需要，對(duì)各個(gè)方面的優(yōu)缺點(diǎn)加以綜合平衡后來(lái)確定適宜的存儲(chǔ)結(jié)構(gòu)。第二章

線性表2.5線性表的應(yīng)用舉例在數(shù)學(xué)上，一個(gè)一元多項(xiàng)式Pn(x)可寫成：Pn(x)=p0+p1x+p2x2+…+pnxn顯然，該多項(xiàng)式可以由每項(xiàng)的系數(shù)p0，p1，…，pn唯一地確定，所以，可以將它用一個(gè)線性表P來(lái)表示成：P=(p0，p1，…，pi，…，pn)若Qm(x)也是一元多項(xiàng)式，則其也可用線性表Q表示為：Q=(q0，q1，…，qm)則Pn(x)+Qm(x)同樣也可用線性表R表示。設(shè)m<n，則

R=(p0+q0，p1+q1，p2+q2，…，pm+qm，pm+1，…，pn)如果對(duì)P、Q都采用順序存儲(chǔ)結(jié)構(gòu)，可以很方便地實(shí)現(xiàn)多項(xiàng)式的相加。例如，一個(gè)多項(xiàng)式T(x)=1

+

2

x1

0

0

0

0+

4

x4

0

0

0

0第二章

線性表若對(duì)該多項(xiàng)式選擇順序存儲(chǔ)結(jié)構(gòu)，只存儲(chǔ)每項(xiàng)的系數(shù)構(gòu)成一個(gè)線性表而讓每項(xiàng)的指數(shù)隱含在系數(shù)的序號(hào)中，會(huì)造成存儲(chǔ)空間的極大浪費(fèi)。若在存儲(chǔ)系數(shù)的同時(shí)也存儲(chǔ)相應(yīng)的指數(shù)，這樣，對(duì)于含有n項(xiàng)的多項(xiàng)式在最壞情形下（即n+1項(xiàng)的系數(shù)均不為0時(shí)）也只需2(n+1)個(gè)存儲(chǔ)單元的空間，這種表示將大大的節(jié)省存儲(chǔ)空間。其數(shù)據(jù)類型可定義如下：#define

MAXSIZE

9999typedef

struct

node

/*定義結(jié)點(diǎn)類型*/{float

coef

;int

exp

;/*系數(shù)域*//*指數(shù)域*/}

elemtype

;typedef

struct{

elemtype

vec[MAXSIZE]

；/*

定義線性表的向量結(jié)構(gòu)*/int len

；

/*

線性表長(zhǎng)度*/}sequenlist;/*類型定義*/第二章

線性表由于順序存儲(chǔ)結(jié)構(gòu)具有隨機(jī)存取的特點(diǎn)，對(duì)于元素的插入和刪除運(yùn)算需要移動(dòng)大量元素，所以，當(dāng)只需求解一個(gè)多項(xiàng)式的值而無(wú)需修改多項(xiàng)式的系數(shù)和指數(shù)值時(shí)，宜采用順序存儲(chǔ)結(jié)構(gòu)。由于多項(xiàng)式相加時(shí)會(huì)產(chǎn)生新的項(xiàng)和系數(shù)可能為零的項(xiàng)，需要進(jìn)行相應(yīng)的結(jié)點(diǎn)空間的增加和釋放，所以一般