第3章 鏈表及其應(yīng)用

回顧：順序表的特點：邏輯關(guān)系上相鄰的兩個元素在物理存儲位置上也相鄰；優(yōu)點：可以隨機存取表中任一元素O(1)；存儲空間使用緊湊缺點：在插入，刪除某一元素時，需要移動大量元素O(n);預(yù)先分配空間需按最大空間分配，利用不充分;表容量難以擴充。討論：在線性排列的一組數(shù)據(jù)元素中插入和刪除數(shù)據(jù)元素時可不可以不移動元素？答：可以！引入另一種數(shù)據(jù)結(jié)構(gòu)——鏈表。1第3章鏈表及其應(yīng)用?

3.1鏈表的基本概念

3.2單鏈表的數(shù)據(jù)結(jié)構(gòu)

3.3單鏈表的基本運算實現(xiàn)

3.4循環(huán)鏈表

3.5鏈表的應(yīng)用

23.1鏈表的基本概念?

3.1.1什么是鏈表

3.1.2鏈表的邏輯結(jié)構(gòu)

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

3.1.4靜態(tài)鏈表和動態(tài)鏈表

3.1.5鏈表的基本運算3?什么是鏈表

?鏈表是滿足下列條件的一種數(shù)據(jù)結(jié)構(gòu)：

⑴是有限個具有相同數(shù)據(jù)類型的數(shù)據(jù)元素的集合，

D={ai|i=1，2，…，n，n≥0，ai為數(shù)據(jù)元素⑵數(shù)據(jù)元素之間的關(guān)系R={<ai-1,ai>|ai-1,ai∈Di=2，3，…，n，n≥0}；⑶數(shù)據(jù)元素ai-1、ai（i=2，3，…，n，n≥0）在存儲器中占用任意的、連續(xù)或不連續(xù)物理存儲區(qū)域。43.1鏈表的基本概念

3.1.1什么是鏈表?

3.1.2鏈表的邏輯結(jié)構(gòu)

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

3.1.4靜態(tài)鏈表和動態(tài)鏈表

3.1.5鏈表的基本運算5?

鏈表的邏輯結(jié)構(gòu)

?同一鏈表中所有數(shù)據(jù)元素的數(shù)據(jù)類型必須相同。

?鏈表中相鄰的元素ai-1、ai間存在序偶關(guān)系，即對于非空的鏈表，ai-1是ai的唯一直接前驅(qū)，ai＋1是ai的唯一直接后繼；而a1無前驅(qū)，an無后繼

?鏈表屬于線性邏輯結(jié)構(gòu)。63.1鏈表的基本概念

3.1.1什么是鏈表

3.1.2鏈表的邏輯結(jié)構(gòu)?

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

3.1.4靜態(tài)鏈表和動態(tài)鏈表

3.1.5鏈表的基本運算7?

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

?

用一組任意的存儲單元來存放表中的元素，這使得鏈表中數(shù)據(jù)元素的邏輯順序與其物理存儲順序不一定相同；

?為確保表中數(shù)據(jù)元素間的線性邏輯關(guān)系，在存儲每一個數(shù)據(jù)元素的同時，存儲其邏輯后繼的存儲地址；

8?鏈表的存儲結(jié)構(gòu)

……

?

ai的值與ai＋1的存儲地址共同組成了鏈表中的一個結(jié)點：datanext其中：data域是數(shù)據(jù)域，用來存放數(shù)據(jù)元素ai的值；

next域是指針域，用來存放ai的直接后繼ai＋1的存儲地址。?

鏈表正是通過每個結(jié)點的指針域?qū)⒈碇衝個數(shù)據(jù)元素按其邏輯順序鏈接在一起的。9【例】設(shè)有一組線性排列的數(shù)據(jù)元素（zhao,qian,sun,li,zhou,wu,zheng,wang），其鏈接存儲形式如圖所示：存儲地址數(shù)據(jù)域指針域………………………………………zhaolizhouzhengqianwang100sunwu160170200210220310320320210160310200220100∧10討論：在該存儲方式下，如何找到表中任一元素？答：在鏈接存儲方式下（鏈表中），每一個數(shù)據(jù)元素的存儲地址是存放在其直接前驅(qū)結(jié)點的next域中，只要知道第一個數(shù)據(jù)元素（結(jié)點）zhao的存儲地址，就可以“順藤摸瓜”找到其后續(xù)的所有結(jié)點。

另外：鏈表中的最后一個數(shù)據(jù)元素?zé)o后繼，則最后一個結(jié)點（尾結(jié)點）的指針域為空。

11通常情況下，我們用箭頭來表示指針域中的指針，忽略每一個結(jié)點的實際存儲位置，而重點突出鏈表中結(jié)點間的邏輯順序，將鏈表直觀地畫成用箭頭鏈接起來的結(jié)點序列。zhaozhouzhengqianlisunwuwang∧123.1鏈表的基本概念

3.1.1什么是鏈表

3.1.2鏈表的邏輯結(jié)構(gòu)

3.1.3鏈表的存儲結(jié)構(gòu)?

3.1.4靜態(tài)鏈表和動態(tài)鏈表

3.1.5鏈表的基本運算13

?靜態(tài)鏈表

靜態(tài)鏈表是用地址連續(xù)的存儲空間(一般使用計算機語言中的“數(shù)組”)存儲鏈表中的元素，及其邏輯后繼在數(shù)組中的位置。與順序表不同的是，在靜態(tài)鏈表中邏輯位置相鄰的元素其物理位置不一定相鄰。14

【例】如圖所示的靜態(tài)鏈表。該鏈表存儲在一個數(shù)組空間中，該數(shù)組為結(jié)構(gòu)類型，每一個數(shù)組元素包括兩個分量(也可以是多個分量)：存放表中元素值的data分量和存放該元素直接后繼位置的next分量。15我們可以用結(jié)構(gòu)體來定義靜態(tài)鏈表的節(jié)點數(shù)據(jù)類型：

typedef

struct{

Datatypedata；

intnext；

}node；一個靜態(tài)鏈表可以描述為：

#definemaxsize100nodenodepool[maxsize]；//存放鏈表的數(shù)組

inthead； //放頭指針的head

在靜態(tài)鏈表中進行插入與刪除操作不需要移動元素，只需改變被插入(刪除)元素的直接前驅(qū)的next域中的值。16?動態(tài)鏈表

由于靜態(tài)鏈表需要事先估計表中數(shù)據(jù)元素的個數(shù)，通常情況下，我們可以為鏈表中的每一個數(shù)據(jù)元素分配相應(yīng)的存儲空間.

該存儲空間中存放有該數(shù)據(jù)元素的值(data域)和其直接后繼的存儲空間地址(next域)，數(shù)據(jù)元素之間的邏輯關(guān)系由每一個這樣的存儲空間中所存儲的地址來維系。我們稱這樣的鏈表為動態(tài)鏈表。我們在本章后續(xù)所討論的鏈表都是動態(tài)鏈表。173.1鏈表的基本概念

3.1.1什么是鏈表

3.1.2鏈表的邏輯結(jié)構(gòu)

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

3.1.4靜態(tài)鏈表和動態(tài)鏈表?

3.1.5鏈表的基本運算18我們可以定義鏈表的以下6種基本運算：（1）置空表LLsetnull(L)

運算的結(jié)果是將鏈表L置成空表。（2）求表長LLlength(L)

運算結(jié)果是輸出鏈表中數(shù)據(jù)元素的個數(shù)。（3）按序號取元素LLget(L,i)

當(dāng)1≤i≤length(L)時，輸出鏈表L中第i個結(jié)點的值或其地址。19（4）按值查找（定位）LLlocate(L,x)

當(dāng)鏈表L中存在值為x的結(jié)點時，輸出該元素的地址。若表L中存在多個值為x的結(jié)點，則依次輸出它的所有地址；當(dāng)表中不存在值為x的結(jié)點時，則輸出空指針。（5）插入LLinsert(L,i,x)

在鏈表L中的第i位置插入值為x的結(jié)點，表長由n變?yōu)閚+1。20（6）刪除LLdelete(L,i)

在鏈表L中刪除第i個結(jié)點，表長由n變?yōu)閚-1。

在解決具體問題時，所需要的運算可能僅是上述運算中的一部分，也可能需要更為復(fù)雜的運算。對于復(fù)雜運算，可通過上述6種基本運算的組合來實現(xiàn)。21第3章鏈表及其應(yīng)用

3.1鏈表的基本概念?

3.2單鏈表的數(shù)據(jù)結(jié)構(gòu)

3.3單鏈表的基本運算實現(xiàn)

3.4循環(huán)鏈表

3.5鏈表的應(yīng)用

22定義

單鏈表是滿足下列條件的一種數(shù)據(jù)：⑴是有限個具有相同數(shù)據(jù)類型的數(shù)據(jù)元素組成的鏈表；⑵該鏈表的每個結(jié)點只有一個指針域。23單鏈表中的每一個結(jié)點包括兩個域：?

存儲該結(jié)點所對應(yīng)的數(shù)據(jù)元素信息的data域

——數(shù)據(jù)域?存儲其直接后繼的存儲位置的next域

——指針域datanext24該結(jié)點的數(shù)據(jù)類型用C語言描述為：

typedef

structnode{DataTypedata;

structnode*next;}LinkList

；可以定義一個該類型的指針變量：LinkList*H；datanext25zhaozhouqianlisunzhengwuwang∧H稱H為該單鏈表的頭指針。若已知單鏈表的頭指針，則可以搜索到表中任一結(jié)點；也就是說，單鏈表由頭指針唯一確定。因此，單鏈表可以用頭指針的名字來命名。上圖所示的單鏈表可稱為單鏈表H。若有：26注意：嚴(yán)格區(qū)分指針變量和結(jié)點變量

?

對于上例，H為指針變量；若它的值非空，則它的值為linklist類型的某結(jié)點的地址；

?

若H非空，*H為LinkList類型的結(jié)點變量，它有兩個分量：(*H).data

和(*H).next

或者寫成H->data和H->next其中：(*H).data為DataType類型的變量，若它的值非空，其值為該數(shù)據(jù)元素ai的值；

(*H).next是與H同類型的指針變量，其值為ai的直接后繼ai+1的地址。

27上圖所示的單鏈表H，表中各結(jié)點的地址及數(shù)據(jù)元素值分別表示為：

結(jié)點1的地址：H數(shù)據(jù)元素a1值：H->data

結(jié)點2的地址：H->next

數(shù)據(jù)元素a2值：H->next->data若令p=H->next

：

則數(shù)據(jù)元素a2值為：p->data

結(jié)點3的地址：p->next；

pa1a2a4a5a3∧H28再令p=p->next，

數(shù)據(jù)元素a3值：p->data

結(jié)點4的地址：p->next；pa1a2a4a5a3∧Hp29再令p=p->next

數(shù)據(jù)元素a4值：p->data

結(jié)點5的地址：p->next；pa1a2a4a5a3∧H再令p=p->next，

數(shù)據(jù)元素a5值：p->data

結(jié)點5無后繼結(jié)點，則p->next=NULL。pa1a2a4a5a3∧Hp30

?

可以看出：若有LinkList*p＝H->next（或LinkList*p＝H），則除第一個結(jié)點外，其余結(jié)點的地址、數(shù)據(jù)元素值均有一致的表述方式，分別為

p->next

p->data

?為使單鏈表中所有結(jié)點都有一致的描述方式，不妨在第一個結(jié)點之前加一個同類型的結(jié)點，并稱該結(jié)點為頭結(jié)點。anaiai+1ai-1a1a2∧H31anaiai+1ai-1a1a2∧H

?頭結(jié)點的data域中不存放任何內(nèi)容，或者存放表長信息；

?

頭結(jié)點的next域中存放第一個數(shù)據(jù)元素結(jié)點的地址，而指針H記錄頭結(jié)點的地址。?

我們稱這樣的單鏈表為帶頭結(jié)點的單鏈表。

在帶頭結(jié)點的單鏈表中，我們稱第一個數(shù)據(jù)元素結(jié)點為首元素結(jié)點，稱最后一個數(shù)據(jù)元素結(jié)點為尾結(jié)點。頭指針頭結(jié)點首元素結(jié)點尾結(jié)點32何謂頭指針、頭結(jié)點和首元結(jié)點？頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元素結(jié)點）的指針。

單鏈表可由一個頭指針唯一確定。頭結(jié)點是在鏈表的首元素結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息;首元素結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素a1的結(jié)點。

頭指針頭結(jié)點首元素結(jié)點a133答：討論1.在鏈表中設(shè)置頭結(jié)點有什么好處？討論2.如何表示空表？頭結(jié)點即在鏈表的首元素結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點的數(shù)據(jù)域中不存儲數(shù)據(jù)元素的值，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元素結(jié)點進行統(tǒng)一處理，編程更方便。答：無頭結(jié)點時，當(dāng)頭指針的值為空時表示空表；有頭結(jié)點時，當(dāng)頭結(jié)點的指針域為空時表示空表。^頭指針^頭指針頭結(jié)點無頭結(jié)點有頭結(jié)點34第3章鏈表及其應(yīng)用

3.1鏈表的基本概念

3.2單鏈表的數(shù)據(jù)結(jié)構(gòu)?

3.3單鏈表的基本運算實現(xiàn)

3.4循環(huán)鏈表

3.5鏈表的應(yīng)用

353.3單鏈表的基本運算實現(xiàn)?

3.3.1帶頭結(jié)點的單鏈表的基本運算實現(xiàn)

3.3.2單鏈表的運算效率分析

3.3.3單鏈表的建立和輸出361、置空表LLsetnull(L)

∧L沒有元素，僅有頭結(jié)點即：L->next=NULL(空）算法：

LinkList*LLsetnull(LinkList*L){L->next=NULL;return(L);}372、求表長LLlength(L)a1a2a3anL∧P難點分析：每個數(shù)據(jù)元素在內(nèi)存中是“零散”存放的，怎么查詢數(shù)據(jù)元素的個數(shù)？實現(xiàn)思路：從頭結(jié)點開始，順著各個結(jié)點next域中記錄的地址，依次訪問各結(jié)點，直到遇到某結(jié)點的next的值為空（NULL）為止。38流程圖：p=L－>nextn=0n=n+1p=p－>nextYp=NULLNa1a2a3anL∧P39int

LLlength(LinkList*L){

//求帶頭結(jié)點的單鏈表L的長度

LinkList*p;intn;p=L->next;n=0;//用來存放單鏈表的長度

while(p!=NULL){p=p->next;n++;}returnn;}算法描述如下：403、取第i個元素LLget(L,i）思路：要取第i個數(shù)據(jù)元素，關(guān)鍵是要先找到該結(jié)點的指針p，然后輸出該結(jié)點的地址p，或輸出該數(shù)據(jù)元素的值p->data均可。難點：單鏈表中想取得第i個元素，必須從頭指針出發(fā)尋找（順藤摸瓜），不能隨機存取。a1a2a3anL∧P41方法：從單鏈表的頭指針L出發(fā)，從首元素結(jié)點（L->next）開始順著鏈域掃描，用指針p指向當(dāng)前掃描到的結(jié)點,初值指向首元素結(jié)點，用j做計數(shù)器，累計當(dāng)前掃描過的結(jié)點數(shù)（初值為1），當(dāng)j=i時，指針p所指的結(jié)點就是要找的第i個結(jié)點。a1a2a3anL∧P42流程圖：j=ip=NULL

Np=p－>next；j++;Np=L－>next；j=1;YY所找的結(jié)點不存在返回pa1a2a3anL∧P43算法描述：LinkList*Get(LinkList*L,inti){//在帶頭結(jié)點的單鏈表L中查找第i個結(jié)點，若找到(1≤i≤n)，則返回該結(jié)點的存儲位置;否則返回NULL

intj；LinkList*p；p=L->next；

j=1；

//從首元素結(jié)點開始掃描

while(p!=NULL&&j<i){p=p->next；//掃描下一結(jié)點

j++；//已掃描結(jié)點計數(shù)器

}if（i==j）returnp；//找到了第i個結(jié)點

elsereturnNULL；//找不到，i≤0或i>n

}444、查找LLlocate(L,x)在表L中查找值為x的結(jié)點的地址思路：從單鏈表的頭指針指向的頭結(jié)點出發(fā)（或者從首元素結(jié)點出發(fā)），順著鏈逐個將結(jié)點的值和給定值x作比較。若有結(jié)點值等于x的結(jié)點，則返回首次找到的其值為x的結(jié)點的存儲位置，否則返回NULL。

a1a2a3anL∧P45流程圖：p=NULLp->data=xNp=p－>nextNp=L－>nextYY返回pa1a2a3anL∧P所找的結(jié)點不存在46算法描述：LinkList*LLlocate(LinkList*L,DataTypex){//在帶頭結(jié)點的單鏈表L中查找其結(jié)點值等于X的結(jié)點，若找到則返回該結(jié)點的位置p；否則返回NULL

LinkList

*p;p=L->next;//從表中第一個結(jié)點比較

while(p!=NULL)if(p->data!=x)p=p->next;elsebreak;//找到值為x的結(jié)點，

退出循環(huán)

returnp;}475.單鏈表的插入LLinsert(L,i,x)

在鏈表中插入一個元素的示意圖如下：xsbapabp插入步驟（即核心語句）：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next元素x結(jié)點應(yīng)預(yù)先生成：S=(LinkList)malloc(m);S->data=x;48插入條件：

1≤i≤n+1

即：可在a1前，或an后插入也就是說，要求第i–1位置不空即：get(L,i-1)≠NULL(空）

49流程圖：p=get(L,i–1)

p=NULL

S=malloc(sizeof(linklist))S－>data=xS－>next=p－>nextP－>next=SNY50voidLLinsert(LinkList*L,inti,DataTypex){//在帶頭結(jié)點的單鏈表L中第i個位置插入值為x的新結(jié)點

LinkList*p,*s;p=get(L,i-1);//在第i個元素之前插入，則先找到第i-1個數(shù)據(jù)元素的存儲位置,使指針p指向它

if(p!=NULL){s=malloc(sizeof(LinkList));

//為e申請一個新的結(jié)點并由s指向它

s->data=x;//將待插入結(jié)點的值x賦給s的數(shù)據(jù)域

s->next=p->next;//完成插入操作

p->next=s;;}}516.單鏈表的刪除LLdelete(L,i)

在鏈表中刪除某元素的示意圖如下：cabp刪除步驟（即核心語句）：q=p->next;/*保存b的指針，靠它才能指向c*/p->next=q->next;/*

a、c兩結(jié)點相連*/free(q)；

/*

刪除b結(jié)點，徹底釋放*/p->next思考：省略free(q)語句行不行？(p->next)->next××52刪除條件:

1≤i≤n

即：結(jié)點ai-1不空，且不是尾結(jié)點。

即：若p＝get(L,i-1)，則p≠NULL

且p->next≠NULL53voidLLdelete(LinkList*L,inti){

//在帶頭結(jié)點的單鏈表L中刪除第i個結(jié)點LinkList*p,*q;p=get(L,i-1);//刪除第i個結(jié)點，則先找到第i-1個結(jié)點的存儲位置,使指針p指向它

if(p!=NULL&&p->next!=NULL){//第

i-1個結(jié)點和第i個結(jié)點均存在

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

free(q)；

}}543.3單鏈表的基本運算實現(xiàn)

3.3.1帶頭結(jié)點的單鏈表的基本運算實現(xiàn)?

3.3.2單鏈表的運算效率分析

3.3.3單鏈表的建立和輸出55鏈表的運算效率分析（1）查找包括按序號查找LLget()和按值查找LLlocate()，因單鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為O(n)。?

時間效率分析（2）插入和刪除因單鏈表不需要移動元素，只要修改指針，一般情況下時間復(fù)雜度為O(1)。

但在單鏈表中進行插入或刪除操作時，要調(diào)用LLget()函數(shù)，該函數(shù)的時間復(fù)雜度為O(n)，這使得插入或刪除操作所耗時間復(fù)雜度為

O(n)。56?

空間效率分析

單鏈表中每個結(jié)點都要增加一個指針空間，相當(dāng)于總共增加了n個整型變量，空間復(fù)雜度為

O(n)。573.3單鏈表的基本運算實現(xiàn)

3.3.1帶頭結(jié)點的單鏈表的基本運算實現(xiàn)

3.3.2單鏈表的運算效率分析?

3.3.3單鏈表的建立和輸出581、頭插法建立單鏈表實例：用單鏈表結(jié)構(gòu)來存放26個英文字母組成的線性表（a，b，c，…，z）,請寫出C語言程序。難點分析：每個數(shù)據(jù)元素在內(nèi)存中是“零散”存放的，其首地址怎么找？又怎么一一鏈接？實現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個數(shù)據(jù)元素開辟存儲空間并賦值，并及時將該結(jié)點插入到頭結(jié)點后（首元素結(jié)點前）。59建表過程如圖所示:

L=malloc(sizeof(LinkList));L->next=NULL;60scanf(“%d”,&x);S=malloc(sizeof(LinkList));S->data=x;S->next=NULL;61L->next=S;62while(條件

){

scanf(“%d”,&x);S=malloc(sizeof(LinkList));S->data=x;S->next=L->next;L->next=S;}63LinkList*SetList(){

//字母鏈表的生成，要一個一個鏈入LinkList*L,*S;inti;L=malloc(sizeof(LinkList));S=malloc(sizeof(LinkList));L->next=S;

S->next=NULL;

for(i=0;i<25;i++){

S->data=‘z’-i;//倒數(shù)第一個結(jié)點值為字符zS=malloc(sizeof(LinkList));S->next=L->next;L->next=S;}S->data=‘z’-i;//插入第一個結(jié)點字符areturnL;}

642.單鏈表的輸出實現(xiàn)思路：順著頭指針，從第一個結(jié)點開始，“順藤摸瓜”，直到最后一個結(jié)點（其next域為空）。算法：

voiddisplay(LinkList*head){//字母鏈表的輸出

p=head->next;

while(p!=NULL){

printf("%c",p->data);

p=p->next;//只要沒到最后一個元素，就不停地向后搜索

}

}65第3章鏈表及其應(yīng)用

3.1鏈表的基本概念

3.2單鏈表的數(shù)據(jù)結(jié)構(gòu)

3.3單鏈表的基本運算實現(xiàn)?

3.4循環(huán)鏈表

3.5鏈表的應(yīng)用

663.4循環(huán)鏈表?

3.4.1單循環(huán)鏈表

3.4.2雙向循環(huán)鏈表67討論1：單鏈表能不能首尾相連？怎樣實現(xiàn)？答：能。只要將表中最后一個結(jié)點的指針域指向頭結(jié)點即可(P->next=L;)。這種形成環(huán)路的單鏈表稱為單循環(huán)鏈表。a1Lanaip68特別地：帶頭結(jié)點的空循環(huán)鏈表樣式

單循環(huán)鏈表的特點：

1、從任一結(jié)點出發(fā)均可找到表中其他結(jié)點。

2、操作僅有一點與單鏈表不同：結(jié)束循環(huán)的條件單鏈表-----p=NULL或p->next=NULL

循環(huán)鏈表-----p=L或p->next=LL這時：L－>next=L69帶尾指針的單循環(huán)鏈表：a1anaiRR空表：這時：R－>next=R這時：頭指針為：

R－>next70例：兩個帶尾指針的循環(huán)鏈表首尾相接思路:(1)將b1的地址存放在an的next域中，同時注意不可以丟掉鏈表A的頭指針；

(2)應(yīng)記錄完成后的鏈表的頭指針或尾指針。a1aianAb1bibnB實現(xiàn):(1)用指針變量u記錄鏈表A的頭指針；

(2)將b1的地址存放在an的next域中；

(3)記下鏈表B的尾指針，并釋放其頭結(jié)點。u71a1aianAb1bibnBu(A)步驟:(1)u=A－>next(2)A－>next=B－>next－>next(3)free(B－>next)(4)B－>next=u(5)A=B723.4循環(huán)鏈表

3.4.1單循環(huán)鏈表?

3.4.2雙向循環(huán)鏈表

73討論2：單鏈表只能查找結(jié)點的直接后繼，能不能查找直接前驅(qū)？如何實現(xiàn)？答：能。只要把單鏈表再多開一個指針域即可。這種有兩個指針的鏈表稱為雙向鏈表。La1anai74?

雙向鏈表中的指針域next和prior分別記錄其前驅(qū)、后繼結(jié)點的地址。priordatanext?結(jié)點數(shù)據(jù)類型描述：typedef

struct

dnode{

datatypedata;

struct

dnode*prior,*next;}

Dlinklist;75?

帶頭結(jié)點的空雙向鏈表樣式：L這時：L－>next=L－>prior=L?

雙向鏈表中的運算，基本上同單鏈表。這里，重點介紹插入和刪除運算：插入：包括前插和后插

前插：在*p結(jié)點前插入新結(jié)點

后插：在*p結(jié)點后插入新結(jié)點76后插：ai-1paiai+1插入方法同單鏈表。xsx插入過程：ai+1aipai-177(4)p－>prior=s(3)p－>prior－>next=s(1)s－>prior=p－>prior(2)s－>next=pxspai-1aiai+1p->prior

前插：78刪除：刪除結(jié)點*ppaiai+1ai-1p－>prior－>next=p－>next;

p－>next－>prior=p－>prior;free(p);p－>priorp－>next79第3章鏈表及其應(yīng)用

3.1鏈表的基本概念

3.2單鏈表的數(shù)據(jù)結(jié)構(gòu)

3.3單鏈表的基本運算實現(xiàn)

3.4循環(huán)鏈表?

3.5鏈表的應(yīng)用

803.5鏈表的應(yīng)用?

3.5.1多項式相加問題

3.5.2兩個鏈表的歸并問題

3.5.3鏈表在字符處理方面的應(yīng)用

——鏈串81?一元多項式的表示通常，一個n次一元多項式P(x)可按升冪的形式寫成：

P(x)=a0+a1x+a2x2+…+anxn

它實際上包含n+1項，由n+1個系數(shù)唯一確定。在計算機內(nèi)，我們可以用一個鏈表來表示一個一元多項式。為了節(jié)省存儲空間，我們只存儲多項式中系數(shù)非0的項。鏈表中的每一個節(jié)點存放多項式的一個系數(shù)非0項，它包含三個域，分別存放該項的系數(shù)、指數(shù)以及指向下一多項式項節(jié)點的指針。82下圖所示為該節(jié)點的結(jié)構(gòu)：該節(jié)點的數(shù)據(jù)類型如下：typedef

struct

Pnode{

int

coef；

intexp；

struct

Pnode*next；}Polynode；83例如：多項式P=3+4x+6x3+8x7+23x21的單鏈表表示形式如下圖所示：為方便以后的運算，我們也在該單鏈表中增加了頭節(jié)點，并給定指數(shù)值為-1。84?

兩個一元多項式相加

兩個多項式相加的法則是：兩個多項式中同指數(shù)項的對應(yīng)系數(shù)相加，若和不為零，則形成“和多項式”中的一項；所有指數(shù)不同的項均直接移位至“和多項式”中。85【例】

兩個一元多項式A(x)=2+5x+9x8+5x17，B(x)=10x+22x6-9x8，分別用單鏈表表示，試描述其相加的過程。

A-1028915175∧pB-11106228-9∧q指針p、q指向多項式鏈表A、B的首元素結(jié)點，并令指針pre=A;pre86A-1028915175∧pB-11106228-9∧qpp->exp<

q->exp，指針p、pre后移：即：pre=p,p=p->next此時p->exp=q->exp，則將*p和*q結(jié)點的系數(shù)相加：

p->coef=p->coef+q->coefprepreB若約定相加的結(jié)果用單鏈表A表示，則free(B)，且B=q；87A-102891175∧B1106228-9∧qp15qB指針q后移，即：q=q->next，同時free(B)，且B=q；prep->exp<q->exp，指針p、pre后移：即：pre=p,p=p->nextppre88A-102891175∧6228-9∧15qBp->exp>

q->exp，應(yīng)將*q插入到*p結(jié)點前：

q=q->next；

B->next=p；

pre->next=B；pre=B；

B=q；ppreq××Bpre8989175∧6228-9∧A-102115Bppreq此時p->exp=

q->exp，則將*p和*q結(jié)點的系數(shù)相加：

p->coef=p->coef+q->coef9080175∧6228-9∧A-102115Bppreq但相加后p->coef=0；需要將結(jié)點*p從鏈表A中刪除：

pre->next=p->next；

free(p)；

p=pre->next；指針q后移，即：q=q->next，同時free(B)，且B=q；qBp此時q=NULL，算法結(jié)束。91綜合以上分析，兩個一元多項式相加的算法如下：Polynode*polyadd(Polynode*A，Polynode*B){//兩個多項式相加，將和多項式存放在多項式A中，并將多項式B刪除

Polynode*p，*q，*temp，*pre；

intsum；

p=A->next；

q=B->next//p和q分別指向A和B多項式鏈表中的第一個節(jié)點

pre=A； //pre指向*p的前趨節(jié)點

free(B)； //釋放多項式B的頭節(jié)點空間92

while(p!=NULL&&q!=NULL){//當(dāng)兩個多項式均未掃描結(jié)束時

if(p->exp<q->exp){pre=p；p=p->next；

}//如果p指向的多項式項的指數(shù)小于q的指數(shù)，指針p后移

elseif(p->exp==q->exp){//若指數(shù)相等，則相應(yīng)的系數(shù)相加sum=p->coef+q->coef

；

if(sum!=0){ p->coef=sum；B=q；pre=p；

p=p->next；q=q->next；

free(B)； //釋放原先的*q節(jié)點空間

}93

else{temp=p；p=p->next；pre->next=p；free(temp)；

B=q；q=q->next；free(B)；//若系數(shù)和為零，則刪除節(jié)點*p與*q，并將指針指向下一個節(jié)點

}else{//若p->exp>q->exp，將*q節(jié)點插入到多項式A中*p節(jié)點前 B=q；q=q->next；B->next=p；pre->next=B；

pre=pre->next；

}}94

if(q!=NULL)pre->next=q；

//若多項式B中還有剩余，則將剩余的節(jié)點加入到和多項式A中

return(A)；

}

若多項式A有n項，多項式B有m項，則上述算法的時間復(fù)雜度為953.5鏈表的應(yīng)用

3.5.1多項式相加問題?

3.5.2兩個鏈表的歸并問題

3.5.3鏈表在字符處理方面的應(yīng)用

——鏈串96兩個鏈表的歸并

若將多項式鏈表A、B中的每個節(jié)點的系數(shù)域去掉，并修改上節(jié)中的一元多項式相加算法，則可形成兩個鏈表的歸并操作算法。97【例】有兩個有序表A=(0,1,8,17)，B=(1,6,8)，將它們歸并為一個有序表。0

p->data<q->data，令指針p后移；1∧1781∧86BApqpp->data＝q->data，應(yīng)將*q節(jié)點插入到鏈表A中的*p節(jié)點之前qpqqp->data<q->data，令指針p后移p->data>q->data，應(yīng)將*q節(jié)點插入到鏈表A中的*p節(jié)點之前p->data=q->data，應(yīng)將*q節(jié)點插入到鏈表A中的*p節(jié)點之前q=NULL，則鏈表A即歸并后的鏈表98算法分析：算法主要包括：搜索、比較、插入三個操作：搜索：需要兩個指針?biāo)阉鲀蓚€鏈表；比較：比較結(jié)點數(shù)據(jù)域中數(shù)據(jù)的大?。徊迦耄簩蓚€結(jié)點中數(shù)據(jù)小的結(jié)點插入新鏈表。99兩個有序鏈表歸并的算法可以描述為：

LinkList*Lmerge(LinkList*A，LinkList*B){

LinkList*p，*q，*pre；

p=A->next；

q=B->next；//p和q分別指向鏈表A和B中的第一個節(jié)點

pre=A； //pre指向*p的前趨節(jié)點

free(B)； /釋放鏈表B的頭節(jié)點空間

while(p!=NULL&&q!=NULL){//當(dāng)兩個鏈表均未掃描結(jié)束時

if(p->data<q->data){pre=p；p=p->next；}//如果*p節(jié)點的data值小于*q的data值，指針p后移

100

else{//否則，將*q節(jié)點插入到鏈表A中*p節(jié)點前

B=q；q=q->next；

B->next=p；pre->next=B；pre=pre->next；

}}

if(q!=NULL)pre->next=q；

//若鏈表B中還有剩余，則將剩余的節(jié)點插入到鏈表A的表尾

return(A)；

}1013.5鏈表的應(yīng)用

3.5.1多項式相加問題

3.5.2兩個鏈表的歸并問題?

3.5.3鏈表在字符處理方面的應(yīng)用

——鏈串102鏈串是滿足下列條件的一種數(shù)據(jù)結(jié)構(gòu)：⑴由0個或多個字符組成的有限序列；一般記為：S=“a1...ai...an”，i=1，2，…，n。⑵字符之間的關(guān)系R={<ai，ai＋1>|ai，ai＋1∈S}。⑶相鄰字符ai、ai＋1在存儲器中不一定占用相鄰的物理存儲單元。其中ai(1≤i≤n)是單個字符，可以是字母、數(shù)字或其它字符。n是串中字符的個數(shù)，稱為串的長度。

鏈串的概念：103

在許多系統(tǒng)中，當(dāng)一個字符占用一個字節(jié)空間的情況時，而鏈表節(jié)點中指針域要占用多個字節(jié)存儲空間。這樣，普通鏈串(如圖所示的每個節(jié)點只有一個字符的鏈串)空間利用率非常低。其節(jié)點類型可描述為：typedef

structnode{chardata；structnode*next；}LinkString；

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

：104

為了提高存儲密度，可以讓每個節(jié)點存放多個字符，也稱這種存儲結(jié)構(gòu)為塊鏈結(jié)構(gòu)，相應(yīng)的鏈串稱為塊鏈串，而塊鏈串中每個節(jié)點最多能存放的字符的個數(shù)稱為節(jié)點的大小。下圖所示的是節(jié)點大小為4的塊鏈串。105塊鏈結(jié)構(gòu)中，結(jié)點類型描述為：

#define