線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

1第2章線性表2.1線性表的邏輯結(jié)構(gòu)2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4一元多項(xiàng)式的表示和相加22.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1鏈表的表示2.3.2鏈表的實(shí)現(xiàn)2.3.3一個(gè)帶頭結(jié)點(diǎn)的單鏈表類型2.3.4其它形式的鏈表3鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過(guò)指針來(lái)實(shí)現(xiàn)！讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域指針數(shù)據(jù)指針數(shù)據(jù)指針或樣式：數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)指針域：存儲(chǔ)直接后繼或者直接前驅(qū)的存儲(chǔ)位置設(shè)計(jì)思想：犧牲空間效率換取時(shí)間效率2.3.1鏈表的表示4鏈表存放示意圖如下：

a1heada2/\an……討論1：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和討論2：在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由

指示。

其直接前驅(qū)結(jié)點(diǎn)的鏈域的值(2)與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)：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)。只包含一個(gè)指針域的稱為單鏈表或線性鏈表指針域53）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a1heada2…infoan^首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息，它不計(jì)入表長(zhǎng)度。頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)、或?yàn)槭自Y(jié)點(diǎn)）的指針；示意圖如下：6討論2：在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？討論1：

如何表示空表？因?yàn)槿魏谓Y(jié)點(diǎn)都有前驅(qū)結(jié)點(diǎn)，而在做插入和刪除操作時(shí)，都需修改其前驅(qū)結(jié)點(diǎn)的指針域，因此對(duì)首元結(jié)點(diǎn)可以統(tǒng)一處理。即簡(jiǎn)化插入和刪除操作；表頭指針是指向頭結(jié)點(diǎn)的非空指針，因此空表和非空表的處理一樣。無(wú)頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；^頭指針無(wú)頭結(jié)點(diǎn)^頭指針頭結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。頭結(jié)點(diǎn)不計(jì)入鏈表長(zhǎng)度！7一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問(wèn)其頭指針的值是多少？存儲(chǔ)地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31稱：頭指針H的值是31（3）舉例例1：8

現(xiàn)有一個(gè)具有五個(gè)元素的線性表L={23，17，47，05，31}，若它以鏈接方式存儲(chǔ)在下列100～119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（占2個(gè)字節(jié)）和指針（占2個(gè)字節(jié)）組成，如下圖所示。其中指針X，Y，Z的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？116NULL(0)100108112答：X=

Y=

Z=

,

首址=

末址=

。例2：Z47Y31V23X17U051001191041081161129討論:

鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。答：設(shè)每個(gè)結(jié)點(diǎn)用變量node表示，其指針用p表示，兩個(gè)分量分別用data和*next表示，這兩個(gè)分量如何賦值？p*nextdatanode方式1：直接表示為

node.data＝'a'；node.next=q;方式2：p指向結(jié)點(diǎn)首地址p->data='a';p->next=q;方式3：p指向結(jié)點(diǎn)首地址(*p).data='a'；(*p).next＝q;10單鏈表的抽象數(shù)據(jù)類型描述如下（參見教材P28）：typedefstructLNode

{ElemTypedata;//數(shù)據(jù)域

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

//*LinkList為L(zhǎng)node類型的指針Q1：第一行的LNode

與最后一行的LNode是不是一回事？A1：不是。前者LNode是結(jié)構(gòu)名，后者LNode是對(duì)整個(gè)struct類型的一種“縮寫”，是一種“新定義名”，它只是對(duì)現(xiàn)有類型名的補(bǔ)充，而不是取代。這就是我們?cè)趶?fù)習(xí)c語(yǔ)言時(shí)講的自引用結(jié)構(gòu)11Q2：那為何兩處要同名(LNode和LNode）？太不嚴(yán)謹(jǐn)了吧？A2：同名是為了表述起來(lái)方便。因?yàn)槊枋龅膶?duì)象相同，方便閱讀和理解。Q3：結(jié)構(gòu)體中間的那個(gè)struct

LNode是何意？A3：在“縮寫”

LNode還沒(méi)出現(xiàn)之前，只能用原始的structLNode來(lái)進(jìn)行變量說(shuō)明。此處說(shuō)明了指針?lè)至康臄?shù)據(jù)類型是structLNode。返回122.3.2鏈表的實(shí)現(xiàn)（1）單鏈表的存?。?）單鏈表的插入（3）單鏈表的刪除（4）單鏈表的建立13（1）單鏈表的存取思路：要存取第i個(gè)數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點(diǎn)的指針p，然后才能執(zhí)行p->data=new_value。訪問(wèn)第i個(gè)數(shù)據(jù)元素的操作函數(shù)可寫為：Status

GetElem_L(LinkListL,inti,ElemTypee){p=L->next;j=1;//帶頭結(jié)點(diǎn)的鏈表while(p&&j<i){p=p->next;++j;}if(!p||j>i)returnERROR;//i不合法

p->data=e;//若是讀取則為：e=p->data;

returnOK;}//

GetElem_L缺點(diǎn)：想尋找單鏈表中第i個(gè)元素，只能從頭指針開始逐一查詢（順藤摸瓜），無(wú)法隨機(jī)存取。14在鏈表中第i個(gè)位置前插入一個(gè)元素x的示意圖如下：Xsai-1aip鏈表插入的核心語(yǔ)句：Step1：s->next=p->next;p->nexts->next思考：Step1和2能互換么？X結(jié)點(diǎn)的生成方式：s=(Lnode*)malloc(m);s->data=x;s->next=?aiai-1p插入X（2）單鏈表的插入（重點(diǎn)）Step2:p->next=s;15StatusListInsert_L(LinkListL,inti,ElemTypee){

}//LinstInsert_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))p=L;j=0;while(p&&

j<i-1)

{p=p->next;++j;}

//尋找第i-1

個(gè)結(jié)點(diǎn)if(!p||j>i-1)returnERROR;//i不合法

s=(LinkList)malloc(sizeof(LNode))s->data=e;s->next=p->next;p->next=s;//插入returnOK;16在鏈表中刪除某元素ai的示意圖如下：ai+1ai-1aip刪除動(dòng)作的核心語(yǔ)句（要借助輔助指針變量q）：q=p->next;//首先保存ai的指針，靠它才能找到ai+1

p->next(p->next)->next×q（3）單鏈表的刪除（重點(diǎn)）p->next=q->next；//將ai-1與ai+1兩結(jié)點(diǎn)相連,淘汰ai結(jié)點(diǎn)×free(q);

17StatusListDelete_L(LinkListL,inti,ElemType&e){

//刪除以L為頭指針(帶頭結(jié)點(diǎn))的單鏈表中第i個(gè)結(jié)點(diǎn)

}//ListDelete_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前趨if(!(p->next)||j>i-1)

returnERROR;//刪除位置不合理q=p->next;p->next=q->next;//刪除并釋放結(jié)點(diǎn)

e=q->data;free(q);returnOK;18空間效率分析鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間，相當(dāng)于總共增加了n個(gè)整型變量，空間復(fù)雜度為O(n)。在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*P，需找到它的，其時(shí)間復(fù)雜度。

前驅(qū)結(jié)點(diǎn)的地址/指針O(n)練習(xí)：19操作步驟：一、建立一個(gè)“空表”；二、輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)并插入；三、輸入數(shù)據(jù)元素an-1，建立結(jié)點(diǎn)并插入表頭；ananan-1四、依次類推，直至輸入a1為止。（4）單鏈表的建立例如：頭插法輸入n個(gè)數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表。鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要預(yù)先分配空間，因此生成鏈表的過(guò)程是一個(gè)結(jié)點(diǎn)“逐個(gè)插入”的過(guò)程。–頭插法建表該方法從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。。21voidCreateList_L(LinkList&L,intn){

//頭插法建立帶頭結(jié)點(diǎn)的單鏈表}//CreateList_L算法的時(shí)間復(fù)雜度為:O(Listlength(L))L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;--i){

s=(LinkList)malloc(sizeof(LNode));

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

s->next=L->next;①

L->next=s;

②

//插入}–尾插法建表該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)尾插法建表voidCreateList_L(LinkList&L,intn){

tail=L=(LinkList)malloc(sizeof(LNode));//尾指針初始化為表頭指針L->next=NULL;for(i=n;i>0;--i){s=(LinkList)malloc(sizeof(LNode));scanf(&s->data);s->next=NULL;

tail->next=s;①

tail=s;②}}24算法要求：已知：線性表A和B，分別由單鏈表La和Lb存儲(chǔ)，其中數(shù)據(jù)元素按值非遞減有序排列（即已經(jīng)有序）；要求：將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）例1：兩個(gè)鏈表的歸并（教材P31例）算法設(shè)計(jì)：算法主要包括搜索、比較、插入三個(gè)操作：搜索：需要設(shè)立三個(gè)指針來(lái)指向La、Lb和Lc鏈表；請(qǐng)將該例子和ch2-1的ppt的第18頁(yè)進(jìn)行比較！25La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，Pc指向新鏈表當(dāng)前結(jié)點(diǎn)。歸并過(guò)程示意如下：Lc=LaPbPaPaPb比較：比較La和Lb表中結(jié)點(diǎn)數(shù)據(jù)的大小；插入：將La和Lb表中數(shù)據(jù)較小的結(jié)點(diǎn)插入新鏈表Lc。請(qǐng)注意鏈表的特點(diǎn)，僅改變指針便可實(shí)現(xiàn)數(shù)據(jù)的移動(dòng),即“數(shù)據(jù)不動(dòng)，指針動(dòng)”26

voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//已知單鏈線性表La和Lb的元素按值非遞減排列。歸并為L(zhǎng)c后也按值非遞減排列。

free(Lb);

//釋放Lb的頭結(jié)點(diǎn)}//MergeList_L

pc->next=pa

?pa:pb;

//插入非空表的剩余段

while(pa&&pb)

//將pa、pb結(jié)點(diǎn)按大小依次插入Lc中

{if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}

else{pc->next=pb;pc=pb;pb=pb->next}}

pa=La->next;pb=Lb->next;Lc=pc=La；

//有頭結(jié)點(diǎn)注：Lc用的是La的頭指針?biāo)伎迹褐貜?fù)的數(shù)據(jù)元素不需要插入，怎么修改？練習(xí)：已知L是帶頭結(jié)點(diǎn)的非空單鏈表，指針p所指的結(jié)點(diǎn)既不是第一個(gè)結(jié)點(diǎn)，也不是最后一個(gè)結(jié)點(diǎn)刪除*p結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列

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

free(q);刪除*p結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列

q=L;while(q->next->next!=p)q=q->next;s=q->next;//s即所要找到的p的前驅(qū)q->next=p;//鏈接

free(s);刪除*p結(jié)點(diǎn)的語(yǔ)句序列

q=L;while(q->next!=p)q=q->next;q->next=p->next;

free(p);刪除首元結(jié)點(diǎn)的語(yǔ)句序列

q=L->next;L->next=q->next;

free(q);刪除最后一個(gè)結(jié)點(diǎn)的語(yǔ)句序列

while(p->next->next!=NULL)p=p->next;q=p->next;p->next=NULL;

free(q);29用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問(wèn)題：改進(jìn)鏈表的設(shè)置：1．單鏈表的表長(zhǎng)是一個(gè)隱含的值；1.增加“表長(zhǎng)”、“表尾指針”和“當(dāng)前位置的指針”三個(gè)數(shù)據(jù)域；

2.將基本操作中的“位序i”改變?yōu)椤爸羔榩”。2．在單鏈表的最后一個(gè)元素之后插入元素時(shí)，需遍歷整個(gè)鏈表；3．在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的“位置”概念加強(qiáng)。返回30typedefstructLNode{

//結(jié)點(diǎn)類型Elemtypedata;

structLNode*next;}*Link,*Positiontypedefstruct

{

//鏈表類型

Linkhead,tail;

//分別指向鏈表頭尾結(jié)點(diǎn)

intlen;

//鏈表中元素個(gè)數(shù)（長(zhǎng)度）}Linklist;2.3.3一個(gè)帶頭結(jié)點(diǎn)的線性鏈表類型定義如下：

（用類C語(yǔ)言，見P37）：結(jié)點(diǎn)的結(jié)構(gòu)表結(jié)構(gòu)基本操作（略）返回31

最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表。從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)

a1a2......an

1.循環(huán)鏈表

和單鏈表的差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”即p->next?=headhead2.3.4其它形式的鏈表32單鏈表中查找只能從前往后，而不能從后往前查。為了查找方便，提高查找速度，可以在結(jié)點(diǎn)上增加一個(gè)指針域，用來(lái)存結(jié)點(diǎn)的直接前驅(qū)，這樣的鏈表稱為雙向鏈表。其結(jié)點(diǎn)的結(jié)構(gòu)為：typedefstructDuLNode{

ElemTypedata;//數(shù)據(jù)域

structDuLNode*prior;

//前驅(qū)指針域

structDuLNode*next;//后繼指針域}DuLNode,*DuLinkList;

雙向鏈表類型的定義如下：2.3.4其它形式的鏈表2.雙向鏈表設(shè)指針p指向某一結(jié)點(diǎn)，則雙向鏈表結(jié)構(gòu)的對(duì)稱性描述如下：–(p→prior)→next=p=(p→next)→prior,即結(jié)點(diǎn)*p的存儲(chǔ)位置既存放在其前趨結(jié)點(diǎn)*(p→prior)的直接后繼指針域中，也存放在它的后繼結(jié)點(diǎn)*(p→next)的直接前趨指針域中ai-1aiai+1p343.雙向循環(huán)鏈表空表非空表a1a2…...anhead->prior=head->next=headhead35雙向鏈表插入操作（重點(diǎn)）：設(shè)p已指向第

i元素，請(qǐng)?jiān)诘?/p>

i元素前插入元素x①ai-1的后繼從

ai(指針是p)變?yōu)?/p>

x（指針是s):

s->next=p;

p->prior->next=s;

②ai的前驅(qū)從

ai-1(指針是p->prior)變?yōu)?/p>

x(指針是s);

s->prior=

p->prior;

p->prior

=s;

注意：要修改雙向指針！x

sai-1

ai

p指針域的變化：××voiddinsertbefor(DuLNode*p，ElemTypex){DuLNode*s=malloc(sizeof(DuLNode));s—>data=x;s—>next=p;p—>prior—>next=s;s—>prior=p—>prior;p—>prior=s;}

問(wèn)：（1）（2）（3）,（4）位置是否可交換？原則是什么？改成如下代碼試試：s—>prior=p—>prior;s—>next=p;p—>prior—>next=s;p—>prior=s;改成如下代碼試試：s—>next=p;s—>prior=p—>prior;p—>prior=s;p—>prior—>next=s;37指針域的變化：①ai-1的后繼由ai變?yōu)閍i+1(指針p->next

);

p->prior->next

=

p->next;

②

ai+1的前驅(qū)由ai變?yōu)閍i-1

(指針p->prior);

p->next->prior

=p->prior;

ai-1

ai+1

ai

p雙向鏈表刪除操作：設(shè)p指向第i個(gè)元素,刪除第i個(gè)元素注意：要修改雙向指針！voidddeletenode(dlistnode*p){p–>prior–>next=p–>next;

p–>next–>prior=p–>prior;free(p);

39動(dòng)態(tài)鏈表樣式：靜態(tài)鏈表樣式：指針數(shù)據(jù)指針數(shù)據(jù)指針數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)數(shù)組中每個(gè)元素都至少有兩個(gè)分量，屬于結(jié)構(gòu)型數(shù)組。常用于無(wú)指針類型的高級(jí)語(yǔ)言中。用一片連續(xù)空間（一維數(shù)組）實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)，這種方式稱為靜態(tài)鏈表。具體實(shí)現(xiàn)方法：定義一個(gè)結(jié)構(gòu)型數(shù)組（每個(gè)元素都含有數(shù)據(jù)域和指示域），就可以完全描述鏈表，指示域就相當(dāng)于動(dòng)態(tài)鏈表中的指針,指示結(jié)點(diǎn)在數(shù)組中的相對(duì)位置。4.靜態(tài)鏈表（自學(xué)）40

靜態(tài)單鏈表的類型定義如下：#defineMAXSIZE1000//預(yù)分配鏈表的最大長(zhǎng)度

typedefstruct{ElemTypedata;//數(shù)據(jù)域

intcur;

//指示域

}component

,SLinkList[MAXSIZE];

//這是一維結(jié)構(gòu)型數(shù)組前例1：一線性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用靜態(tài)鏈表如何表示？說(shuō)明1：假設(shè)S為SLinkList型變量，則S[MAXSIZE]

為一個(gè)靜態(tài)鏈表；S[0].cur則表示第1個(gè)結(jié)點(diǎn)在數(shù)組中的位置。41說(shuō)明2：如果數(shù)組的第i個(gè)分量表示鏈表的第k個(gè)結(jié)點(diǎn)，則：S[i].data表示第k個(gè)結(jié)點(diǎn)的數(shù)據(jù)；

S[i].cur

表示第k+1個(gè)結(jié)點(diǎn)(即k的直接后繼)的位置。data1ZHAO3LI5QIAN6WU0ZHOU4SUN2…………0123456…1000curi頭結(jié)點(diǎn)說(shuō)明3：靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動(dòng)元素，只需修改指示器就可以了。例如：在線性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之間插入新元素LIU，可以這樣實(shí)現(xiàn)：42Step1:將QIAN的指示器原內(nèi)容備份到臨時(shí)變量temp：temp=S[3].cur；Step2:將QIAN的指示器換為新元素LIU的位置：S[3].cur=7；Step3: