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

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

3.1鏈表的基本概念

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

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

3.4循環(huán)鏈表

3.5鏈表的應(yīng)用

23.1鏈表的基本概念?

3.1.1什么是鏈表

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

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

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

3.1.5鏈表的基本運(yùn)算3?什么是鏈表

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

⑴是有限個(gè)具有相同數(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）在存儲(chǔ)器中占用任意的、連續(xù)或不連續(xù)物理存儲(chǔ)區(qū)域。43.1鏈表的基本概念

3.1.1什么是鏈表?

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

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

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

3.1.5鏈表的基本運(yùn)算5?

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

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

?鏈表中相鄰的元素ai-1、ai間存在序偶關(guān)系，即對(duì)于非空的鏈表，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鏈表的存儲(chǔ)結(jié)構(gòu)

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

3.1.5鏈表的基本運(yùn)算7?

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

?

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

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

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

……

?

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

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

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

另外：鏈表中的最后一個(gè)數(shù)據(jù)元素?zé)o后繼，則最后一個(gè)結(jié)點(diǎn)（尾結(jié)點(diǎn)）的指針域?yàn)榭铡?/p>

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

3.1.1什么是鏈表

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

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

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

3.1.5鏈表的基本運(yùn)算13

?靜態(tài)鏈表

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

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

typedef

struct{

Datatypedata；

intnext；

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

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

inthead； //放頭指針的head

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

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

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

3.1.1什么是鏈表

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

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

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

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

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

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

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

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

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

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

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

3.1鏈表的基本概念?

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

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

3.4循環(huán)鏈表

3.5鏈表的應(yīng)用

22定義

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

存儲(chǔ)該結(jié)點(diǎn)所對(duì)應(yīng)的數(shù)據(jù)元素信息的data域

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

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

typedef

structnode{DataTypedata;

structnode*next;}LinkList

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

?

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

?

若H非空，*H為L(zhǎng)inkList類型的結(jié)點(diǎn)變量，它有兩個(gè)分量：(*H).data

和(*H).next

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

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

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

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

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

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

：

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

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

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

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

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

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

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

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

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

?

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

p->next

p->data

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

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

?

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

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

在帶頭結(jié)點(diǎn)的單鏈表中，我們稱第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)為首元素結(jié)點(diǎn)，稱最后一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)為尾結(jié)點(diǎn)。頭指針頭結(jié)點(diǎn)首元素結(jié)點(diǎn)尾結(jié)點(diǎn)32何謂頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)？頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自亟Y(jié)點(diǎn)）的指針。

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

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

3.1鏈表的基本概念

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

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

3.4循環(huán)鏈表

3.5鏈表的應(yīng)用

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

3.3.1帶頭結(jié)點(diǎn)的單鏈表的基本運(yùn)算實(shí)現(xiàn)

3.3.2單鏈表的運(yùn)算效率分析

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

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

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

LLlength(LinkList*L){

//求帶頭結(jié)點(diǎn)的單鏈表L的長(zhǎng)度

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

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

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

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

j=1；

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

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

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

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

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

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

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

LinkList

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

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

退出循環(huán)

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

在鏈表中插入一個(gè)元素的示意圖如下：xsbapabp插入步驟（即核心語句）：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next元素x結(jié)點(diǎn)應(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é)點(diǎn)的單鏈表L中第i個(gè)位置插入值為x的新結(jié)點(diǎn)

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

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

//為e申請(qǐng)一個(gè)新的結(jié)點(diǎn)并由s指向它

s->data=x;//將待插入結(jié)點(diǎn)的值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é)點(diǎn)相連*/free(q)；

/*

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

1≤i≤n

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

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

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

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

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

i-1個(gè)結(jié)點(diǎn)和第i個(gè)結(jié)點(diǎn)均存在

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

free(q)；

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

3.3.1帶頭結(jié)點(diǎn)的單鏈表的基本運(yùn)算實(shí)現(xiàn)?

3.3.2單鏈表的運(yùn)算效率分析

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

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

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

O(n)。56?

空間效率分析

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

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

3.3.1帶頭結(jié)點(diǎn)的單鏈表的基本運(yùn)算實(shí)現(xiàn)

3.3.2單鏈表的運(yùn)算效率分析?

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

//字母鏈表的生成，要一個(gè)一個(gè)鏈入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ù)第一個(gè)結(jié)點(diǎn)值為字符zS=malloc(sizeof(LinkList));S->next=L->next;L->next=S;}S->data=‘z’-i;//插入第一個(gè)結(jié)點(diǎn)字符areturnL;}

642.單鏈表的輸出實(shí)現(xiàn)思路：順著頭指針，從第一個(gè)結(jié)點(diǎn)開始，“順藤摸瓜”，直到最后一個(gè)結(jié)點(diǎn)（其next域?yàn)榭眨Ｋ惴ǎ?/p>

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

p=head->next;

while(p!=NULL){

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

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

}

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

3.1鏈表的基本概念

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

3.3單鏈表的基本運(yùn)算實(shí)現(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：?jiǎn)捂湵砟懿荒苁孜蚕噙B？怎樣實(shí)現(xiàn)？答：能。只要將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)即可(P->next=L;)。這種形成環(huán)路的單鏈表稱為單循環(huán)鏈表。a1Lanaip68特別地：帶頭結(jié)點(diǎn)的空循環(huán)鏈表樣式

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

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

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

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

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

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

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

(3)記下鏈表B的尾指針，并釋放其頭結(jié)點(diǎn)。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ǎn)捂湵碇荒懿檎医Y(jié)點(diǎn)的直接后繼，能不能查找直接前驅(qū)？如何實(shí)現(xiàn)？答：能。只要把單鏈表再多開一個(gè)指針域即可。這種有兩個(gè)指針的鏈表稱為雙向鏈表。La1anai74?

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

struct

dnode{

datatypedata;

struct

dnode*prior,*next;}

Dlinklist;75?

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

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

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

后插：在*p結(jié)點(diǎn)后插入新結(jié)點(diǎn)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é)點(diǎn)*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單鏈表的基本運(yùn)算實(shí)現(xiàn)

3.4循環(huán)鏈表?

3.5鏈表的應(yīng)用

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

3.5.1多項(xiàng)式相加問題

3.5.2兩個(gè)鏈表的歸并問題

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

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

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

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

struct

Pnode{

int

coef；

intexp；

struct

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

兩個(gè)一元多項(xiàng)式相加

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

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

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

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

p->coef=p->coef+q->coefprepreB若約定相加的結(jié)果用單鏈表A表示，則free(B)，且B=q；87A-102891175∧B1106228-9∧qp15qB指針q后移，即：q=q->next，同時(shí)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é)點(diǎn)前：

q=q->next；

B->next=p；

pre->next=B；pre=B；

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

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

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

pre->next=p->next；

free(p)；

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

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

intsum；

p=A->next；

q=B->next//p和q分別指向A和B多項(xiàng)式鏈表中的第一個(gè)節(jié)點(diǎn)

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

free(B)； //釋放多項(xiàng)式B的頭節(jié)點(diǎn)空間92

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

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

}//如果p指向的多項(xiàng)式項(xiàng)的指數(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é)點(diǎn)空間

}93

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

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

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

pre=pre->next；

}}94

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

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

return(A)；

}

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

3.5.1多項(xiàng)式相加問題?

3.5.2兩個(gè)鏈表的歸并問題

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

——鏈串96兩個(gè)鏈表的歸并

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

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

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

LinkList*p，*q，*pre；

p=A->next；

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

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

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

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

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

100

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

B=q；q=q->next；

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

}}

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

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

return(A)；

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

3.5.1多項(xiàng)式相加問題

3.5.2兩個(gè)鏈表的歸并問題?

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

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

鏈串的概念：103

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

structnode{chardata；structnode*next；}LinkString；

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

：104

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

#define