第二章-線性表(2)-2013-9-26

數(shù)據(jù)結(jié)構(gòu)2013年9月26日第二章線性表（2）第一章緒論

第六章樹與二叉樹第二章線性表第七章圖第三章棧和隊(duì)列第八章動(dòng)態(tài)存儲(chǔ)管理第四章串

第九章查找第五章數(shù)組與廣義表第十章內(nèi)部排序數(shù)據(jù)結(jié)構(gòu)1第二章線性表2.1線性表的類型定義2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

2.3.1線性鏈表

2.3.2循環(huán)鏈表

2.3.3雙向鏈表2

下一小節(jié)：2.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)順序表的缺陷：插入/刪除耗費(fèi)大量時(shí)間線性鏈表：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素（這些單元可以是連續(xù)的，也可以是不連續(xù)的）。

利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素。每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息。42.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)其結(jié)點(diǎn)由兩部分信息組成：

（1）數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素本身信息；（2）指針域：存儲(chǔ)直接后繼的存儲(chǔ)位置（地址）?！矜湵眍^指針指示鏈表中的第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置，整個(gè)鏈表的存取必須從頭指針開始。最后一個(gè)結(jié)點(diǎn)沒有直接后繼，其指針域?yàn)椤翱铡保∟ULL）。52.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)6ZHAOQIANSUNLIZHOUWUZHENGWANG^H例

線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲(chǔ)地址1713192531374331H頭指針7與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語：1、結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像,由數(shù)據(jù)域和指針域兩部分組成；2、鏈表：n個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3、單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表或線性鏈表；有兩個(gè)指針域的鏈表，稱為雙鏈表；有多個(gè)指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。a1heada2an……h(huán)ead循環(huán)鏈表示意圖：2.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)2.3.1單鏈表：

數(shù)據(jù)域指針域存儲(chǔ)地址數(shù)據(jù)域指針域

1 Li 437 Qian 1313 Sun 1 19 Wang NULL25 Wu 3731 Zhao 737 Zheng1943 Zhou 2531頭指針H82.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)單鏈表：?jiǎn)捂湵淼倪壿嫿Y(jié)構(gòu)LiZhaoQianSunZhouWuZhengWang^H92.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)單鏈表：一般附加一個(gè)頭結(jié)點(diǎn)，其數(shù)據(jù)域不存儲(chǔ)信息，指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針。

a1an^a2...頭指針H頭結(jié)點(diǎn)H^非空表空表10頭指針是指向鏈表中第一個(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)a1單鏈表結(jié)構(gòu)：注意頭指針，頭結(jié)點(diǎn)等概念的不同含義。

一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問其頭指針的值是？存儲(chǔ)地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31∴頭指針的值是312.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①

無頭結(jié)點(diǎn)②

有頭結(jié)點(diǎn)132.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)為什么要加頭結(jié)點(diǎn)？

頭結(jié)點(diǎn)是鏈表的開始結(jié)點(diǎn)之前的一個(gè)附加結(jié)點(diǎn)。該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，

使用頭結(jié)點(diǎn)的好處在于：對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。（1）沒有頭結(jié)點(diǎn)的情況下，頭指針是指向開始結(jié)點(diǎn)的指針。開始結(jié)點(diǎn)是指鏈表中的第一個(gè)結(jié)點(diǎn)，它沒有直接前驅(qū)。

(2)有了頭結(jié)點(diǎn)，

由于開始結(jié)點(diǎn)位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上的操作一致，無須進(jìn)行特殊處理。如在第一個(gè)數(shù)據(jù)元素前面加入新元素或者刪除第一個(gè)節(jié)點(diǎn)時(shí)頭指針的值不變。

14無頭結(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)（3）有了頭結(jié)點(diǎn)之后頭指針指向頭結(jié)點(diǎn)，不論鏈表是否為空，頭指針總是非空（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨?，因此空表和非空表的處理也就統(tǒng)一了。2.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)15教材P28對(duì)于單鏈表的抽象描述:structLNode /*單鏈表結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)*/{ ElemTypedata；//數(shù)據(jù)域

LNode *next;//指針域}Lnode,*LinkList;

//*LinkList為L(zhǎng)node類型的指針16結(jié)構(gòu)類型的C語言表示法17結(jié)構(gòu)類型的C語言表示法介紹三個(gè)有用的庫(kù)函數(shù)（都在<stdlib.h>中）：sizeof(x)—計(jì)算變量x的長(zhǎng)度；malloc(m)—開辟m字節(jié)長(zhǎng)度的地址空間，并返回這段空間的首地址；free(p)—釋放指針p所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。單鏈表基本操作：

1、StatusInitList_L(LinkList&L){

//建立頭結(jié)點(diǎn)，其Next為空

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;returnOK;}2.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)182、VoidCreateList_L(LinkList&L,intn){/*創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的鏈表*/L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//創(chuàng)建頭結(jié)點(diǎn)

for(i=n;i>0;--i){//按數(shù)組倒序建立鏈表

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

scanf(&p->data);//輸入元素值

p->next=L->next; L->next=p;//插入到表頭

}}//CreateList_L

算法結(jié)果演示：..\數(shù)據(jù)結(jié)構(gòu)-光盤\DSDemoW2.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)193、算法2.8單鏈表的元素讀取（非隨機(jī)存?。㏒tatusGetElem_L(LinkList&L,inti,ElemType&e){//L為帶//頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回//OK，否則返回ERRORLinkListp;//鏈表指針pp=L->next;//L為頭結(jié)點(diǎn)

intj=1;//初始化，p指向首元結(jié)點(diǎn)，j為計(jì)數(shù)器

while(p&&j<i){//順指針向后查找，直到p指向第i個(gè)元素或p為空

p=p->next;++j;}if(!p||j>i)returnERROR;//第i個(gè)元素不存在

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

returnOK;}//GetElem_L2.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)204.單鏈表的插入在單鏈表中插入一個(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;S->next=p->nextStatusListInsert_L(LinkList&L,inti,ElemTypee){//算法2.9

//在帶頭結(jié)點(diǎn)的單鏈線性表L的第i個(gè)元素之前插入元素eLinkListp,s;p=L;intj=0;while(p&&j<i-1){//尋找第i-1個(gè)結(jié)點(diǎn)

p=p->next;++j;}if(!p||j>i-1)returnERROR;//i小于1或者大于表長(zhǎng)

s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)

s->data=e;s->next=p->next;//插入L中

p->next=s;returnOK;}//LinstInsert_L算法結(jié)果演示：..\數(shù)據(jù)結(jié)構(gòu)-光盤\DSDemoW22●單鏈表結(jié)點(diǎn)插入算法描述：

5.單鏈表結(jié)點(diǎn)的刪除在鏈表中刪除某元素的示意圖如下：cabp刪除步驟（即核心語句）：q=p->next;

//保存b的指針，靠它才能指向cp->next=q->next;//a、c兩結(jié)點(diǎn)相連free(q)；//刪除b結(jié)點(diǎn)，徹底釋放p->next思考：省略free(q)語句行不行？(p->next)->next××p->next=p->next->next;24malloc函數(shù)和free函數(shù)

假設(shè)您的程序在執(zhí)行過程中需要分配一定量的內(nèi)存。您可以隨時(shí)調(diào)用malloc函數(shù)從堆中申請(qǐng)一塊內(nèi)存。在操作系統(tǒng)為您的程序預(yù)留出這塊內(nèi)存，之后您就可以隨意使用它了。

用完之后，要使用free函數(shù)將這塊內(nèi)存返回給操作系統(tǒng)進(jìn)行回收。以后其他程序還可以按自己的需要預(yù)留這塊內(nèi)存。StatusListDelete_L(LinkList&L,inti,ElemType&e){//算法//2.10。在帶頭結(jié)點(diǎn)的單鏈線性表L中，刪除第i個(gè)元素，并由e返回其值

LinkListp,q;p=L;intj=0;while(p->next&&j<i-1){//尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前趨

p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;//刪除位置不合理

q=p->next;//預(yù)刪除的結(jié)點(diǎn)ip->next=q->next;//刪除并釋放結(jié)點(diǎn)

e=q->data;free(q);returnOK;}//ListDelete_L算法結(jié)果演示：..\數(shù)據(jù)結(jié)構(gòu)-光盤\DSDemoW25●單鏈表結(jié)點(diǎn)刪除算法描述：LNode*LocateElem_L(LinkListL,ElemTypee){//在L中找到第一個(gè)值和e相同的結(jié)點(diǎn)，返回其

//地址，若不存在，返回空值。

if(!L)returnNULL;p=L;while(p&&p->data!=e)p=p->next;returnp;}該算法時(shí)間復(fù)雜度：O(n)266.單鏈表查找算法描述算法要求：已知：線性表A、B，分別由單鏈表LA,LB

存儲(chǔ)，其中數(shù)據(jù)元素按值非遞減有序排列，要求：將A，B歸并為一個(gè)新的線性表C,C的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表C由單鏈表LC

存儲(chǔ)。假設(shè)：A=（3，5，8，11），B=（2，6，8，9，11）預(yù)測(cè)：合并后C=（2,3,5,6,8,8,9,11，11）7.兩個(gè)鏈表的歸并（教材P31）3511/\8

La2611/\8

Lb92365

Lc8頭結(jié)點(diǎn)7.兩個(gè)鏈表的歸并算法分析：算法主要包括：搜索、比較、插入三個(gè)操作：搜索：需要兩個(gè)指針?biāo)阉鲀蓚€(gè)鏈表；比較：比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大??；插入：將兩個(gè)結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表。7.兩個(gè)鏈表的歸并La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

Pc指向新鏈表當(dāng)前結(jié)點(diǎn)Lc

…

Pa3

PcPa5

Pc11^Pc2

PbPcPa307.兩個(gè)鏈表的歸并算法實(shí)現(xiàn)（2.12）：VoidMergeList_L(LinkList&Lc,LinkListLa,LinkListLb){

//已知兩個(gè)非遞減單鏈表為L(zhǎng)a,Lb//歸并單鏈表La,Lb,形成新的有序鏈表Lcpa=La->next;pb=Lb->next;Lc=pc=La;//用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)317.兩個(gè)鏈表的歸并

while(pa&&pb){//La,Lb非空

if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;//插入剩余段，思考題:如何實(shí)現(xiàn)？

free(Lb);//釋放Lb的頭結(jié)點(diǎn)}//MergeList_L算法結(jié)果演示：..\數(shù)據(jù)結(jié)構(gòu)-光盤\DSDemoW時(shí)間復(fù)雜度分析：O(n)

327.兩個(gè)鏈表的歸并單鏈表與順序表的比較：?jiǎn)捂湵淼拇鎯?chǔ)密度比順序表低，它多占用了存儲(chǔ)空間。但在許多情況下，鏈?zhǔn)降姆峙浔软樞蚍峙溆行?，順序表必須分配足夠大的連續(xù)的存儲(chǔ)空間，而鏈表可以利用零星的存儲(chǔ)單元

在單鏈表里進(jìn)行插入、刪除運(yùn)算比在順序表里容易得多對(duì)于順序表，可隨機(jī)訪問任一個(gè)元素，而在單鏈表中，需要順著鏈逐個(gè)進(jìn)行查找，因此單鏈表適合于在成批地、順序地處理線性表中的元素時(shí)采用。2.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)33其它鏈表形式34答：能。只要將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)即可(P->next=head;)。這種形成環(huán)路的鏈表稱為循環(huán)鏈表。特別：帶頭結(jié)點(diǎn)的空循環(huán)鏈表樣式H參見教材P35

特點(diǎn)：

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

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

循環(huán)鏈表-----p=head或p->next=head討論1：鏈表能不能首尾相連？怎樣實(shí)現(xiàn)？2.3.2循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)操作與線性鏈表基本一致循環(huán)條件：p->next==p->head（單鏈表：p->next=NULL

）表空條件：p->head->next==p->head（單鏈表：p=NULL）其它鏈表形式HH空循環(huán)鏈表非空循環(huán)鏈表35其它鏈表形式36討論2：?jiǎn)捂湵碇荒懿檎医Y(jié)點(diǎn)的直接后繼，能不能查找直接前驅(qū)？如何實(shí)現(xiàn)？答：能。只要把單鏈表再多開一個(gè)指針域即可(例如用*next和*prior;)。雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。priordatanext這種有兩個(gè)指針的鏈表稱為雙向鏈表。其特點(diǎn)是可以雙向查找表中結(jié)點(diǎn)。參見教材P35—39。特別：帶頭結(jié)點(diǎn)的空雙向鏈表樣式：2.3.3雙向鏈表可以在單鏈表的每一個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其前趨和后繼的指針域。這樣鏈表中有兩條不同方向的鏈。優(yōu)點(diǎn)：既可以找前驅(qū)，也可以找后繼。H

H

空雙向鏈表非空雙向鏈表priordatanext雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。37其它鏈表形式雙向鏈表存儲(chǔ)結(jié)構(gòu)：

typedefstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;38其它鏈表形式雙向循環(huán)鏈表H

H空雙向循環(huán)鏈表非空雙向循環(huán)鏈表39其它鏈表形式雙向(循環(huán))鏈表的插入和刪除刪除雙向鏈表的結(jié)點(diǎn)p->prior->next=p->next;p->next->prior=p->prior;往雙向鏈表中插入結(jié)點(diǎn)s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=sABCpABCsp①②③④①②③④40其它鏈表形式雙向循環(huán)鏈表的插入算法：StatusListInsert_Dul(DuLinkList&L,inti,ElemTypee){//在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表第i個(gè)位置插入元素eif(!(p=GetElemP_Dul(L,i)))returnERROR；//在L中

//確定插入位置；表的長(zhǎng)度未達(dá)i，即插入位置不合法

s=(DuLinkList)malloc(sizeof(ElemType));if(!s)exit(OVERFLOW)//空間不夠，溢出

s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;//更改指針域，插入結(jié)點(diǎn)e}//ListInsert_Dul41其它鏈表形式雙向循環(huán)鏈表的刪除算法：StatusListDelete_Dul(DuLinkList&L,inti,ElemType&e){//在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中刪除第i個(gè)位置元素，并將結(jié)果存入eif(!(p=GetElemP_Dul(L,i)))returnERROR；//表的長(zhǎng)度未達(dá)ie=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);//更改指針域，釋放第i個(gè)結(jié)點(diǎn)

returnOK;}//ListDelete_Dul42其它鏈表形式線性鏈表與順序表的比較：線性鏈表

優(yōu)點(diǎn)：空間的合理利用；插入和刪除時(shí)不需要移動(dòng)缺點(diǎn)：實(shí)現(xiàn)基本操作（如求表長(zhǎng)）不如順序表數(shù)據(jù)元素的“位序”概念被淡化很多場(chǎng)合下，線性鏈表是線性表的首選存儲(chǔ)結(jié)構(gòu)2.3線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)43鏈表的運(yùn)算效率分析1.查找因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為

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

O(1)。

但是，如果要在單鏈表中進(jìn)行前插或刪除操作，由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為O(n)?？臻g效率分析鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間，相當(dāng)于總共增加了n個(gè)整型變量，空間復(fù)雜度為

O(n)。鏈表的運(yùn)算效率分析本章小結(jié)了解線性表的邏輯結(jié)構(gòu)特征熟悉掌握順序表和鏈表的描述方法、特點(diǎn)及有關(guān)概念重點(diǎn)掌握順序表上的插入和刪除算法重點(diǎn)掌握鏈表的建立、查找、插入和刪除算法掌握從時(shí)間和空間的角度綜合比較順序表以及鏈表的不同特點(diǎn)及其適用場(chǎng)合46本章作業(yè)1、簡(jiǎn)述下列概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。請(qǐng)理解，不必書寫。2、填空：（1