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

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

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

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

2.3.1線性鏈表

2.3.2循環(huán)鏈表

2.3.3雙向鏈表2

下一小節(jié)：2.3線性表的鏈式表示及實現(xiàn)2.3線性表的鏈式表示及實現(xiàn)順序表的缺陷：插入/刪除耗費大量時間線性鏈表：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（這些單元可以是連續(xù)的，也可以是不連續(xù)的）。

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

（1）數(shù)據(jù)域：存儲數(shù)據(jù)元素本身信息；（2）指針域：存儲直接后繼的存儲位置（地址）?！矜湵眍^指針指示鏈表中的第一個結(jié)點的存儲位置，整個鏈表的存取必須從頭指針開始。最后一個結(jié)點沒有直接后繼，其指針域為“空”（NULL）。52.3線性表的鏈式表示及實現(xiàn)6ZHAOQIANSUNLIZHOUWUZHENGWANG^H例

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

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

1 Li 437 Qian 1313 Sun 1 19 Wang NULL25 Wu 3731 Zhao 737 Zheng1943 Zhou 2531頭指針H82.3線性表的鏈式表示及實現(xiàn)單鏈表：單鏈表的邏輯結(jié)構(gòu)LiZhaoQianSunZhouWuZhengWang^H92.3線性表的鏈式表示及實現(xiàn)單鏈表：一般附加一個頭結(jié)點，其數(shù)據(jù)域不存儲信息，指針域存儲指向第一個結(jié)點的指針。

a1an^a2...頭指針H頭結(jié)點H^非空表空表10頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針。

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

頭指針頭結(jié)點首元結(jié)點a1單鏈表結(jié)構(gòu)：注意頭指針，頭結(jié)點等概念的不同含義。

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

無頭結(jié)點②

有頭結(jié)點132.3線性表的鏈式表示及實現(xiàn)為什么要加頭結(jié)點？

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

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

(2)有了頭結(jié)點，

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

14無頭結(jié)點時，當(dāng)頭指針的值為空時表示空表；有頭結(jié)點時，當(dāng)頭結(jié)點的指針域為空時表示空表。^頭指針^頭指針頭結(jié)點無頭結(jié)點有頭結(jié)點（3）有了頭結(jié)點之后頭指針指向頭結(jié)點，不論鏈表是否為空，頭指針總是非空（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。2.3線性表的鏈式表示及實現(xiàn)15教材P28對于單鏈表的抽象描述:structLNode /*單鏈表結(jié)點存儲結(jié)構(gòu)*/{ ElemTypedata；//數(shù)據(jù)域

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

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

1、StatusInitList_L(LinkList&L){

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

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;returnOK;}2.3線性表的鏈式表示及實現(xiàn)182、VoidCreateList_L(LinkList&L,intn){/*創(chuàng)建一個帶頭結(jié)點的鏈表*/L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//創(chuàng)建頭結(jié)點

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

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

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

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

}}//CreateList_L

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

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

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

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

e=p->data;//取第i個元素

returnOK;}//GetElem_L2.3線性表的鏈式表示及實現(xiàn)204.單鏈表的插入在單鏈表中插入一個元素的示意圖如下：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;S->next=p->nextStatusListInsert_L(LinkList&L,inti,ElemTypee){//算法2.9

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

La2611/\8

Lb92365

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

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

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

…

Pa3

PcPa5

Pc11^Pc2

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

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

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;//插入剩余段，思考題:如何實現(xiàn)？

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

327.兩個鏈表的歸并單鏈表與順序表的比較：單鏈表的存儲密度比順序表低，它多占用了存儲空間。但在許多情況下，鏈式的分配比順序分配有效，順序表必須分配足夠大的連續(xù)的存儲空間，而鏈表可以利用零星的存儲單元

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

特點：

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

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

循環(huán)鏈表-----p=head或p->next=head討論1：鏈表能不能首尾相連？怎樣實現(xiàn)？2.3.2循環(huán)鏈表最后一個結(jié)點的指針域的指針又指回第一個結(jié)點操作與線性鏈表基本一致循環(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é)點的直接后繼，能不能查找直接前驅(qū)？如何實現(xiàn)？答：能。只要把單鏈表再多開一個指針域即可(例如用*next和*prior;)。雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。priordatanext這種有兩個指針的鏈表稱為雙向鏈表。其特點是可以雙向查找表中結(jié)點。參見教材P35—39。特別：帶頭結(jié)點的空雙向鏈表樣式：2.3.3雙向鏈表可以在單鏈表的每一個結(jié)點里再增加一個指向其前趨和后繼的指針域。這樣鏈表中有兩條不同方向的鏈。優(yōu)點：既可以找前驅(qū)，也可以找后繼。H

H

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

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

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

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

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

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

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

O(1)。

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

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