《數(shù)據(jù)結(jié)構(gòu)、代碼》第2章 線性表

第2章線性表(二)張成文北京郵電大學(xué)計(jì)算機(jī)學(xué)院編輯ppt主要內(nèi)容

2.7線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示 2.8單鏈表 2.9循環(huán)鏈表 2.10雙向鏈表 2.11各種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的比較 2.12順序表與鏈表的比較 2.13小結(jié)編輯ppt線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示結(jié)點(diǎn)(Node):既要存儲(chǔ)線性表的每個(gè)數(shù)據(jù)元素值,又要存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址(或位置)信息,以表示結(jié)點(diǎn)間的邏輯關(guān)系。這兩部分信息組成的存儲(chǔ)映象叫做結(jié)點(diǎn)(Node)。編輯ppt1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域指針數(shù)據(jù)指針數(shù)據(jù)指針或樣式：數(shù)據(jù)域：存儲(chǔ)元素的值指針域：存儲(chǔ)直接后繼或直接前驅(qū)元素的存儲(chǔ)地址設(shè)計(jì)思想：犧牲空間效率換取時(shí)間效率編輯ppt其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過指針來實(shí)現(xiàn)！鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)La1a2a3編輯ppt與鏈?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è)指針域（直接前驅(qū)和直接后繼）的鏈表，稱為雙向鏈表；首尾相接的鏈表稱為循環(huán)鏈表。a1heada2an……循環(huán)鏈表示意圖：head編輯ppt4）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別

示意圖如下：頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a1heada2…infoan^頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息，它不計(jì)入表長度。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。下面舉例說明。編輯ppt頭指針L頭指針L頭結(jié)點(diǎn)首元結(jié)點(diǎn)首元結(jié)點(diǎn)空表：L=NULLL^1264126440164016頭結(jié)點(diǎn)的作用：插入和刪除第一個(gè)數(shù)據(jù)元素時(shí)不必對頭指針進(jìn)行特殊處理。^^與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語編輯ppt一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？存儲(chǔ)地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例1：答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31稱：頭指針H的值是31編輯ppt例2：

線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(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)的起始地址為多少？Z47Y31V23X17U05100119答：X=

Y=

Z=

,首址=

末址=.104108116112116NULL/0100108112編輯ppt單鏈表單鏈表:鏈表中的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域,我們將這種鏈表稱為單鏈表。單鏈表包括兩個(gè)域: 數(shù)據(jù)域用來存儲(chǔ)結(jié)點(diǎn)的值; 指針域用來存儲(chǔ)數(shù)據(jù)元素的直接后繼的地址(或位置)。編輯ppt 從鏈表的整體結(jié)構(gòu)上看，鏈表可以是空鏈，也可以由一個(gè)或多個(gè)結(jié)點(diǎn)組成。每條鏈有一個(gè)入口的頭結(jié)點(diǎn)，該結(jié)點(diǎn)僅指示鏈中第一個(gè)結(jié)點(diǎn)的地址。如是空鏈，則可表示為“0”或“∧”，它類似于一個(gè)常量。每條鏈的最后一個(gè)結(jié)點(diǎn)的鏈指針為“0”，也可用“∧”作為鏈的結(jié)束標(biāo)志。下圖給出了鏈表的示意形式。圖(a)中有一個(gè)頭結(jié)點(diǎn)和具有A、B、C、D數(shù)據(jù)元素的鏈，圖(b)所示為線性鏈表的一般表示，結(jié)點(diǎn)與結(jié)點(diǎn)之間用箭頭鏈接。

單鏈表編輯ppt鏈表圖示(a)鏈表的圖示；(b)鏈表的一般表示編輯ppt

以線性表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為線性表的地址，稱作線性表的頭指針。頭結(jié)點(diǎn)

a1a2…...an^頭指針頭指針

有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針?？罩羔樉€性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭站庉媝pt討論:

鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡單數(shù)據(jù)類型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。答：以26個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：字符型指針型假設(shè)每個(gè)結(jié)點(diǎn)用變量node表示，結(jié)點(diǎn)指針用p表示，其中兩個(gè)分量分別用data和*next表示，該如何書寫？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‘a(chǎn)’‘b’qp編輯ppt單鏈表的存儲(chǔ)結(jié)構(gòu)描述typedefstructNode//結(jié)點(diǎn)類型定義{ElemTypedata；structNode*next；}Node,*LinkList；//LinkList為結(jié)構(gòu)指針類型編輯ppt①設(shè)p為指向鏈表的第i個(gè)元素的指針,則第i個(gè)元素的數(shù)據(jù)域?qū)憺?/p>

，指針域?qū)憺?/p>

。練習(xí)：p->dataai的值p->nextai+1的地址②鏈表不具備的特點(diǎn)是

。A、可隨機(jī)訪問任何一個(gè)元素B、插入、刪除操作不需要移動(dòng)元素C、無需事先估計(jì)存儲(chǔ)空間大小D、所需存儲(chǔ)空間與線性表長度成正比編輯ppt靜態(tài)鏈表用數(shù)組模擬可利用空間表

0123456789

381-16cur(游標(biāo))a2a1a4a3data

#defineMAXSIZE10//鏈表的最大長度typedefstruct{ ElemTypedata; intcur;}componet,SLinkList[MAXSIZE];第1個(gè)元素的下標(biāo)：SLinkList[0].cur編輯ppt帶頭結(jié)點(diǎn)的單鏈表上的基本運(yùn)算1建立單鏈表2單鏈表查找3單鏈表插入4單鏈表刪除第i個(gè)結(jié)點(diǎn)編輯ppt建立單鏈表1)頭插法建表（逆序）操作步驟：建立一個(gè)“空表”；輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)并插入；輸入數(shù)據(jù)元素an-1，

建立結(jié)點(diǎn)并插入；ananan-1依次類推，直至輸入a1為止。ss編輯ppt頭插法建表算法LinklistCreateFromHead(){LinkListL;Node*s;intflag=1;//標(biāo)志flag初值為1L=(Linklist)malloc(sizeof(Node));//分配頭結(jié)點(diǎn)L->next=NULL;while(flag)//輸入“$”時(shí),flag置0,建表結(jié)束{c=getchar();if(c!=’$’)//為新結(jié)點(diǎn)分配存儲(chǔ)空間{s=(Node*)malloc(sizeof(Node));s->data=c;

s->next=L->next;L->next=s;}//鏈接elseflag=0;}returnL；}編輯pptr

c1∧sL∧cn∧srr

2)尾插法建表：設(shè)尾指針r建立一個(gè)“空表”,r指向頭結(jié)點(diǎn);輸入數(shù)據(jù)元素C1,建立結(jié)點(diǎn)并鏈接,r指向該結(jié)點(diǎn)；輸入數(shù)據(jù)元素C2,建立結(jié)點(diǎn)并鏈接,r指向該結(jié)點(diǎn)；…輸入數(shù)據(jù)元素Cn,建立結(jié)點(diǎn)并鏈接,r指向該結(jié)點(diǎn)；c2∧sr

…編輯ppt尾插法建表算法LinklistCreateFromTail()//新結(jié)點(diǎn)加到鏈表末尾{LinkListL;Node*r,*s;intflag=1;//flag初值L=(Node*)malloc(sizeof(Node));//分配頭結(jié)點(diǎn)L->next=NULL;r=L;//r始終指向鏈表的表尾while(flag)//輸入“$”時(shí)flag為0，建表結(jié)束{c=getchar();if(c!=’$’){s=(Node*)malloc(sizeof(Node));s->data=c;

r->next=s;r=s}//鏈接else{flag=0;r->next=NULL;}}returnL；}編輯ppt單鏈表查找1)按序號(hào)查找

算法描述：設(shè)帶頭結(jié)點(diǎn)的單鏈表的長度為n,要查找表中第i個(gè)結(jié)點(diǎn),則需要從單鏈表的頭指針L出發(fā),從頭結(jié)點(diǎn)（L->next）開始順著鏈域掃描,用指針p指向當(dāng)前掃描到的結(jié)點(diǎn),初值指向頭結(jié)點(diǎn)(p=L),用j做記數(shù)器,累計(jì)當(dāng)前掃描過的結(jié)點(diǎn)數(shù)(初值為0),當(dāng)j=i時(shí),指針p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。算法實(shí)現(xiàn),算法演示。編輯pptL

線性表的操作

Get(L,i)在單鏈表中i=3時(shí),Get的實(shí)現(xiàn)過程:211830754256∧pppj12

3P->data=30編輯ppt

因此，查找第i個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針，比較j和i。

令指針p始終指向線性表中第j個(gè)數(shù)據(jù)元素。單鏈表是一種順序存取的結(jié)構(gòu),為找第i個(gè)數(shù)據(jù)元素,必須先找到第i-1個(gè)數(shù)據(jù)元素。編輯ppt按序號(hào)查找算法實(shí)現(xiàn)//找第i個(gè)結(jié)點(diǎn),找到返回指向它的指針;否則返回空Node*Get(LinkListL,inti){Node*p；p=L；j=0；//從頭結(jié)點(diǎn)開始掃描while((p->next!=NULL)&&(j<i){p=p->next；j++；//掃描下一結(jié)點(diǎn)}if（i==j）returnp；//找到了第i個(gè)結(jié)點(diǎn)elsereturnNULL；//找不到,i≤0或i>n}算法時(shí)間復(fù)雜度為:O(Length(*L))編輯ppt2)按值查找算法描述：按值查找是指在單鏈表中查找是否有結(jié)點(diǎn)值等于e的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為e的結(jié)點(diǎn)的存儲(chǔ)位置，否則返回NULL。查找過程從單鏈表的頭指針指向的頭結(jié)點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定值e作比較。算法實(shí)現(xiàn)，算法演示。編輯ppt按值查找算法實(shí)現(xiàn)//查找其結(jié)點(diǎn)值等于key的結(jié)點(diǎn)，若找到則返回該結(jié)點(diǎn)的位置p，否則返回NULL*/Node*Locate(LinkListL,ElemTypekey){Node*p;p=L->next;//從表中第一個(gè)結(jié)點(diǎn)比較while(p!=NULL)if(p->data!=key) p=p->next;elsebreak;//找到結(jié)點(diǎn)key，退出循環(huán)returnp;}算法時(shí)間復(fù)雜度為:O(Length(*L))編輯pptai-13.單鏈表插入操作InsList(L,i,e)的實(shí)現(xiàn)：

有序?qū)?lt;ai-1,ai>改變?yōu)?lt;ai-1,e>和<e,ai>eaiai-1可見,插入結(jié)點(diǎn)需要修改第i-1個(gè)結(jié)點(diǎn)的指針和新結(jié)點(diǎn)的指針。在單鏈表第i個(gè)結(jié)點(diǎn)之前插入結(jié)點(diǎn)的步驟為:pres1)找到單鏈表的第i-1個(gè)結(jié)點(diǎn)并由指針pre指示。2)然后申請一個(gè)新結(jié)點(diǎn)并由指針s指示。3)將pre指示結(jié)點(diǎn)的指針值賦給s指示結(jié)點(diǎn)的指針域。(將第i個(gè)結(jié)點(diǎn)鏈接到新結(jié)點(diǎn)上)4)然后修改pre指示結(jié)點(diǎn)的指針域,使它等于s。(新結(jié)點(diǎn)鏈接到第i-1個(gè)結(jié)點(diǎn)上)單鏈表插入編輯pptintInsList(LinkListL,inti,ElemTypee){//在單鏈表L第i個(gè)結(jié)點(diǎn)前插入值為e的新結(jié)點(diǎn)Node*pre,*s;pre=L;intk=0;

//先找到第i-1個(gè)結(jié)點(diǎn)的存儲(chǔ)位置,讓Pre指向它while(pre!=NULL&&k<i-1){pre=pre->next; k=k+1;}if(k!=i-1)return0;s=(Node*)malloc(sizeof(Node));//申請新結(jié)點(diǎn)s->data=e;//將e賦給s指示的數(shù)據(jù)域

s->next=pre->next;pre->next=s;

//鏈接return1;}算法時(shí)間復(fù)雜度為:O(Length(*L))編輯ppts=(Node*)malloc(sizeof(Node));//申請新結(jié)點(diǎn)s->data=e;//將e賦給s的數(shù)據(jù)域s->next=pre->next;pre->next=s;//鏈接}ai-1eaiai-1pres編輯ppt如下圖所示的是鏈表插入前、后的邏輯狀態(tài)。從圖中可以看出，要插入一個(gè)結(jié)點(diǎn)，首先要從空間表中取一個(gè)空結(jié)點(diǎn)k，使得q結(jié)點(diǎn)（前趨結(jié)點(diǎn)的地址）的指針指向k，k結(jié)點(diǎn)的指針指向p（存儲(chǔ)ai值的結(jié)點(diǎn)地址），同時(shí)把數(shù)據(jù)x存入k，即 q->next=k; k->next=p;編輯ppt鏈表插入邏輯示意圖(a)插入前；(b)插入后編輯ppt 在鏈表的插入操作中，結(jié)點(diǎn)插入的位置可能有四種情況，下面分別加以介紹。設(shè)Head是鏈表入口或表頭，x是插入結(jié)點(diǎn)的存儲(chǔ)地址。 (1)原來鏈表為空表，即Head=NULL，則插入結(jié)點(diǎn)為表首結(jié)點(diǎn)，表示為 Head=x； x->next=NULL； (2)插入位置在表中第一個(gè)結(jié)點(diǎn)Head之前，則插入結(jié)點(diǎn)為新的表頭，表示為 x->next=Head； Head=x；

編輯ppt (3)插入位置在表的中間，為q結(jié)點(diǎn)之后，p結(jié)點(diǎn)之前，表示為 q->next=x；

x->next=p；

(4)插入位置在鏈尾，即新結(jié)點(diǎn)x作為原表尾結(jié)點(diǎn)p之后的新表尾，表示為 x->next=p->next； p->next=x； 或 p->next=x； x->next=NULL；編輯ppt單鏈表刪除第i個(gè)結(jié)點(diǎn)操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)*p,修改其指針域讓它指向第i+1個(gè)結(jié)點(diǎn)。釋放第i個(gè)結(jié)點(diǎn)的空間。ai-1aiai+1ai-1r=p->next;p->next=r->next;

free(r);pr編輯pptintDelList(LinkListL,inti,ElemType*e)//刪除單鏈表L中第i個(gè)元素,并保存其值到變量*e中{Node*p,*r;p=L;intk=0;while(p->next!=NULL&&k<i-1)//找i的前驅(qū)結(jié)點(diǎn){p=p->next;k=k+1;}if(k!=i-1)//即循環(huán)因p->next=NULL而跳出return0;

r=p->next;p->next=r->next;

//刪除結(jié)點(diǎn)free(r);//釋放被刪除結(jié)點(diǎn)所占空間return1;}算法的時(shí)間復(fù)雜度為:O(Length(*L))編輯ppt鏈表刪除的邏輯示意圖(a)刪除前；(b)刪除后編輯ppt 從上圖中可以看出，要?jiǎng)h除某一個(gè)結(jié)點(diǎn)，必須知道被刪除結(jié)點(diǎn)的前趨結(jié)點(diǎn)。設(shè)被刪除結(jié)點(diǎn)的地址為s，s的前趨結(jié)點(diǎn)為q，s的后繼結(jié)點(diǎn)為p，則被刪除的基本操作步驟為 q->next=p； 或q->next=s->next；

編輯ppt 刪除操作和插入操作相同，即在鏈表中搜索到被刪除的結(jié)點(diǎn)，修改相應(yīng)的指針，同時(shí)把被刪除的結(jié)點(diǎn)通過調(diào)用free(x)，將該結(jié)點(diǎn)的空間送空間表。根據(jù)被刪除結(jié)點(diǎn)在鏈表中的位置，刪除操作有如下四種情況： (1)鏈表中只有一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)就是被刪除的結(jié)點(diǎn)，其操作為 Head=NULL； 或 Head=Head->next； (2)被刪除的結(jié)點(diǎn)是鏈中第一個(gè)結(jié)點(diǎn)，其操作為Head=Head->next；編輯ppt (3)被刪除的結(jié)點(diǎn)在鏈的中間，其中刪除結(jié)點(diǎn)的地址為p，前趨結(jié)點(diǎn)的地址為q，其操作為 q->next=p->next； (4)被刪除的結(jié)點(diǎn)在鏈尾，其中刪除結(jié)點(diǎn)的地址為p，前趨結(jié)點(diǎn)的地址為q，其操作為 q->next=NULL； 或 q->next=p->next； 下圖給出了線性表刪除算法的框圖。編輯ppt線性鏈表刪除算法框圖編輯ppt 刪除算法： DELETE(head，key) /*在head為入口的鏈表中刪除值為key的結(jié)點(diǎn)*/ {i=head；w=i； /*設(shè)置前趨結(jié)點(diǎn)的地址*/ while((i!=NULL)&&(i->data!=key)) {w=i； i=i->next； } /*查找刪除結(jié)點(diǎn)的位置*/編輯pptif(i==NULL){printf(＂無此結(jié)點(diǎn)＂)；return；}else{if(head==i)head=i->next； /*刪除頭結(jié)點(diǎn)*/elsew->next=i->next；/*刪除鏈中間和鏈尾結(jié)點(diǎn)*/free(i)；}}編輯ppt用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問題：

改進(jìn)鏈表的設(shè)置：1．單鏈表的表長是一個(gè)隱含的值；

1．增加表長、表尾指針和當(dāng)前位置指針；2．在單鏈表的最后一個(gè)元素之后插入元素時(shí)，需遍歷整個(gè)鏈表；3．在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的“位置”概念加強(qiáng)。2．將基本操作中的“位序i”改變?yōu)椤爸羔榩”。編輯ppt3循環(huán)鏈表

最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)（或頭結(jié)點(diǎn)）的鏈表a1a2…...an

和單鏈表的差別:判別鏈表中尾結(jié)點(diǎn)的條件不再是“后繼指針是否為空”，而是“后繼指針是否為頭指針”。編輯pptrear

L空鏈表a1……ai-1aianL設(shè)頭指針的一般形式

a1……ai-1aian設(shè)尾指針的一般形式

rear->next帶頭結(jié)點(diǎn)的循環(huán)單鏈表示意圖編輯ppt 通過查詢，確定關(guān)鍵字值KEY不在鏈中，該結(jié)點(diǎn)插入的位置和插入的操作有如下幾種情況： (1)若表空(Head=NULL)，則插入結(jié)點(diǎn)后是只有一個(gè)結(jié)點(diǎn)的環(huán)鏈表。 (2)若表非空，則分為三種情況： ①插入的位置是在第一個(gè)結(jié)點(diǎn)，即原表的第一個(gè)結(jié)點(diǎn)成為結(jié)點(diǎn)插入后新表的第二個(gè)結(jié)點(diǎn)，同時(shí)為了保持循環(huán)鏈表的結(jié)構(gòu)特征，在形成新的入口后，鏈表中最末一個(gè)結(jié)點(diǎn)的鏈指針應(yīng)修正指向新的入口結(jié)點(diǎn)。

循環(huán)鏈表的插入操作編輯ppt ②插入的位置是在最末一個(gè)結(jié)點(diǎn)之后，那么，最末一個(gè)結(jié)點(diǎn)的指針指向插入的結(jié)點(diǎn)，插入結(jié)點(diǎn)的指針仍指向首結(jié)點(diǎn)。 ③插入的位置是在鏈的中間，那么可通過插入位置的前趨結(jié)點(diǎn)的指針，完成新結(jié)點(diǎn)的插入。 下圖所示為四種插入操作的示意圖。

編輯ppt循環(huán)有序鏈表的插入操作示意圖編輯ppt下圖給出了循環(huán)鏈表刪除關(guān)鍵字值為KEY的結(jié)點(diǎn)的算法框圖。循環(huán)鏈表的刪除操作編輯ppt循環(huán)鏈表刪除算法框圖編輯ppt必須注意，在循環(huán)鏈表中，要充分考慮到可能出現(xiàn)被刪除結(jié)點(diǎn)位置不同的各個(gè)邊界條件。若被刪除結(jié)點(diǎn)在鏈?zhǔn)?，則必須修改入口Head，而且還要考慮到鏈表中最末一個(gè)記錄的指針要指向結(jié)點(diǎn)刪除后的新入口，該情況的操作示意圖如下圖所示；特殊情況下，被刪除結(jié)點(diǎn)是第一個(gè)且僅只有這一個(gè)結(jié)點(diǎn)，那么循環(huán)鏈表入口因設(shè)置為空，Head=NULL；其他情況與單鏈表的刪除結(jié)點(diǎn)的算法相似。編輯ppt循環(huán)鏈表刪除首結(jié)點(diǎn)(a)刪除結(jié)點(diǎn)之前；(b)刪除結(jié)點(diǎn)之后編輯ppt例有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表LA、LB，編寫算法，將兩個(gè)循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表，其頭指針為LA。算法思想：先找到兩個(gè)鏈表的尾，并分別由指針p、q指向它們，然后將第一個(gè)鏈表的尾與第二個(gè)表的第一個(gè)結(jié)點(diǎn)鏈接起來，并修改第二個(gè)表的尾q，使它的鏈域指向第一個(gè)表的頭結(jié)點(diǎn)。編輯pptLinkListmerge_1(LinkListLA,LinkListLB)/*此算法將兩個(gè)循環(huán)單鏈表的首尾連接起來*/{Node*p,*q;p=LA;q=LB;while(p->next!=LA)p=p->next;

//找到LA的表尾while(q->next!=LB)q=q->next;

//找到LB的表尾p->next=LB->next;

//使LA尾指針指向LB第1個(gè)結(jié)點(diǎn)q->next=LA;

//使LB的尾指針指向表LA的頭結(jié)點(diǎn)free(LB);

//釋放LB的頭結(jié)點(diǎn)空間

return(LA);}

編輯ppt

4雙向鏈表typedefstructNode

//結(jié)點(diǎn)類型定義{ElemTypedata；structNode*next；

structNode*prior;}Node,*LinkList；//LinkList為結(jié)構(gòu)指針類型后繼指針域priordatanext前驅(qū)指針域數(shù)據(jù)域編輯ppt雙向鏈表的結(jié)構(gòu)編輯ppt 雙向鏈表的結(jié)構(gòu)有以下特點(diǎn)： (1)若Head為空(NULL)，則雙向鏈表為空。 (2)在雙向鏈表中，若結(jié)點(diǎn)i有 i->Lnext=NULL 則該結(jié)點(diǎn)是鏈的第一個(gè)結(jié)點(diǎn)；若結(jié)點(diǎn)i有 i->Lnext=i->Rnext=NULL 則該結(jié)點(diǎn)i是鏈的第一個(gè)結(jié)點(diǎn)且該鏈僅有這個(gè)結(jié)點(diǎn)i。 (3)在雙鏈表中，若結(jié)點(diǎn)i有 i->Rnext=NULL 則該結(jié)點(diǎn)是鏈的最末一個(gè)結(jié)點(diǎn)。編輯ppt (4)在雙向鏈表中，若結(jié)點(diǎn)i是表中任意結(jié)點(diǎn)的地址，則該結(jié)點(diǎn)的前趨結(jié)點(diǎn)是i→Lnext，后繼結(jié)點(diǎn)的地址是i→Rnext，對結(jié)點(diǎn)i也可以表示為 i=i->Rnext->Lnext=i->Lnext->Rnext 這個(gè)表達(dá)式非常直觀地反映了雙向鏈表結(jié)構(gòu)的本質(zhì)特點(diǎn)，即無論是沿著表向前，還是向后都同樣方便。

編輯ppt雙向鏈表的操作特點(diǎn)：“查詢”和單鏈表相同?？稍黾右环N從后向前的“查詢”方式。“插入”和“刪除”時(shí)需要同時(shí)修改兩個(gè)方向上的指針。編輯pptai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;sai-1ai插入p編輯pptai-1刪除aiai+1q=p->next;p->next=q->next;p->next->prior=p;free(q);pai-1q雙向鏈表刪