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

1、第2章 線性表(二)張成文張成文北京郵電大學(xué)計(jì)算機(jī)學(xué)院北京郵電大學(xué)計(jì)算機(jī)學(xué)院主要內(nèi)容2.7 線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造表示2.8 單鏈表2.9 循環(huán)鏈表2.10 雙向鏈表2.11各種鏈?zhǔn)酱鎯?chǔ)構(gòu)造的比較2.12順序表與鏈表的比較 2.13小結(jié)線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造表示結(jié)點(diǎn)結(jié)點(diǎn)(Node): 既要存儲(chǔ)線性表的每個(gè)數(shù)據(jù)元素值既要存儲(chǔ)線性表的每個(gè)數(shù)據(jù)元素值,又要存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址又要存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址(或位置或位置)信息信息,以以表示結(jié)點(diǎn)間的邏輯關(guān)系。這兩部分信息組成的存表示結(jié)點(diǎn)間的邏輯關(guān)系。這兩部分信息組成的存儲(chǔ)映象叫做結(jié)點(diǎn)儲(chǔ)映象叫做結(jié)點(diǎn)(Node)。1 線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造表示讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都

2、包含兩部分：數(shù)據(jù)域和指針域讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域指針指針指針指針指針指針或或款式：款式：數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)域：存儲(chǔ)元素的值元素的值指針域：存儲(chǔ)直接后繼或指針域：存儲(chǔ)直接后繼或直接前驅(qū)元素的存儲(chǔ)地址直接前驅(qū)元素的存儲(chǔ)地址設(shè)計(jì)思想：犧牲空間效率換取時(shí)間效率設(shè)計(jì)思想：犧牲空間效率換取時(shí)間效率其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？經(jīng)過(guò)指針來(lái)實(shí)現(xiàn)！鏈?zhǔn)酱鎯?chǔ)構(gòu)造特點(diǎn)La1a2a3與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)1結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組

3、成；結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2鏈表：鏈表： n 個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)絺€(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱(chēng)為線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造。存儲(chǔ)映像，稱(chēng)為線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造。3單鏈表、雙向鏈表、循環(huán)鏈表：?jiǎn)捂湵?、雙向鏈表、循環(huán)鏈表： 結(jié)點(diǎn)只需一個(gè)指針域的鏈表，稱(chēng)為單鏈表或線性鏈表；結(jié)點(diǎn)只需一個(gè)指針域的鏈表，稱(chēng)為單鏈表或線性鏈表；有兩個(gè)指針域直接前驅(qū)和直接后繼的鏈表，稱(chēng)為雙向鏈表；有兩個(gè)指針域直接前驅(qū)和直接后繼的鏈表，稱(chēng)為雙向鏈表；首尾相接的鏈表稱(chēng)為循環(huán)鏈表。首尾相接的鏈表稱(chēng)為循環(huán)鏈表。a1heada2an循環(huán)鏈表表示圖：循環(huán)鏈表表

4、示圖：4頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別 表示圖如下：表示圖如下：頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn)首元結(jié)點(diǎn)首元結(jié)點(diǎn)a1heada2infoan頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)的指針；點(diǎn)的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息，它不計(jì)入表長(zhǎng)度。內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息，它不計(jì)入表長(zhǎng)度。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。的結(jié)點(diǎn)。 下面舉例闡明。下面舉例闡明。

5、頭指針L頭指針L頭結(jié)點(diǎn)首元結(jié)點(diǎn)首元結(jié)點(diǎn)空表：L=NULLL 1264126440164016頭結(jié)點(diǎn)的作用：插入和刪頭結(jié)點(diǎn)的作用：插入和刪除第一個(gè)數(shù)據(jù)元素時(shí)不用除第一個(gè)數(shù)據(jù)元素時(shí)不用對(duì)頭指針進(jìn)展特殊處置。對(duì)頭指針進(jìn)展特殊處置。與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)一個(gè)線性表的邏輯構(gòu)造為：一個(gè)線性表的邏輯構(gòu)造為：ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG，其存，其存儲(chǔ)構(gòu)造用單鏈表表示如下，請(qǐng)問(wèn)其頭指針的值是多少？?jī)?chǔ)構(gòu)造用單鏈表表示如下，請(qǐng)問(wèn)其頭指針的值是多少？存儲(chǔ)地址存儲(chǔ)地址數(shù)據(jù)域數(shù)據(jù)域指針域指針域

6、1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例例1：答：頭指針是指向鏈答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋針，因此關(guān)鍵是要尋覓第一個(gè)結(jié)點(diǎn)的地址。覓第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31稱(chēng)：頭指針?lè)Q：頭指針H的值是的值是31其中指針其中指針X X，Y Y，Z Z的值分別為多少？該線性表的首結(jié)點(diǎn)起始的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？地址為多少？末結(jié)點(diǎn)的起始地址為多少？答：答：X= Y= Z= ,X= Y= Z= , 首址首址= = 末址末址= .= .單鏈表

7、 單鏈表單鏈表: 鏈表中的每個(gè)結(jié)點(diǎn)只需一個(gè)指針域鏈表中的每個(gè)結(jié)點(diǎn)只需一個(gè)指針域,我們將這種鏈表稱(chēng)為單鏈表。我們將這種鏈表稱(chēng)為單鏈表。 單鏈表包括兩個(gè)域單鏈表包括兩個(gè)域: 數(shù)據(jù)域用來(lái)存儲(chǔ)結(jié)點(diǎn)的值數(shù)據(jù)域用來(lái)存儲(chǔ)結(jié)點(diǎn)的值; 指針域用來(lái)存儲(chǔ)數(shù)據(jù)元素的直接后繼的地指針域用來(lái)存儲(chǔ)數(shù)據(jù)元素的直接后繼的地址址(或位置或位置)。DATA FIELDLINK FIELDi從鏈表的整體構(gòu)造上看，鏈表可以是空鏈，也可以由一個(gè)或多個(gè)結(jié)點(diǎn)組成。每條鏈有一個(gè)入口的頭結(jié)點(diǎn)，該結(jié)點(diǎn)僅指示鏈中第一個(gè)結(jié)點(diǎn)的地址。如是空鏈，那么可表示為“0或“，它類(lèi)似于一個(gè)常量。每條鏈的最后一個(gè)結(jié)點(diǎn)的鏈指針為“0，也可用“作為鏈的終了標(biāo)志。以下圖給

8、出了鏈表的表示方式。圖(a)中有一個(gè)頭結(jié)點(diǎn)和具有A、B、C、D數(shù)據(jù)元素的鏈，圖(b)所示為線性鏈表的普通表示，結(jié)點(diǎn)與結(jié)點(diǎn)之間用箭頭鏈接。 單鏈表 鏈表圖示(a) 鏈表的圖示；(b) 鏈表的普通表示ABCDHead(a )Head(b ) 以線性表中第一個(gè)數(shù)據(jù)元素 的存儲(chǔ)地址作為線性表的地址，稱(chēng)作線性表的頭指針。1a頭結(jié)點(diǎn)頭結(jié)點(diǎn) a1 a2 . an 頭指針頭指針 有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針?？罩羔樉€性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭?討論: 鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類(lèi)型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類(lèi)型

9、通常不一致，所因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類(lèi)型通常不一致，所以要采用構(gòu)造數(shù)據(jù)類(lèi)型。以要采用構(gòu)造數(shù)據(jù)類(lèi)型。答：答：以以2626個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：字符型字符型指針型指針型假設(shè)每個(gè)結(jié)點(diǎn)用變量假設(shè)每個(gè)結(jié)點(diǎn)用變量nodenode表示，結(jié)點(diǎn)表示，結(jié)點(diǎn)指針用指針用p p表示，其中兩個(gè)分量分別用表示，其中兩個(gè)分量分別用datadata和和* *nextnext表示，該如何書(shū)寫(xiě)？表示，該如何書(shū)寫(xiě)？p方式方式1： 直接表示為直接表示為 node.dataa；node.next=q方式方式2：p指向結(jié)點(diǎn)首地址，然后指向結(jié)點(diǎn)首地址，然后 p-data=

10、a; p-next=q; 方式方式3： p指向結(jié)點(diǎn)首地址，然后指向結(jié)點(diǎn)首地址，然后 (*p).data=a； (*p).nextqb單鏈表的存儲(chǔ)構(gòu)造描畫(huà)typedef struct Node /typedef struct Node /結(jié)點(diǎn)類(lèi)型定義結(jié)點(diǎn)類(lèi)型定義 ElemType data ElemType data； struct Node struct Node * * next next；Node,Node,* *LinkListLinkList；/LinkList/LinkList為構(gòu)造指針類(lèi)型為構(gòu)造指針類(lèi)型設(shè)設(shè)p p為指向鏈表的第為指向鏈表的第i i個(gè)元素的指針個(gè)元素的指針, ,那么第

11、那么第i i個(gè)元素個(gè)元素的的數(shù)據(jù)域?qū)憺閿?shù)據(jù)域?qū)憺?，指針域?qū)憺椋羔樣驅(qū)憺?。練習(xí)：練習(xí)：p-dataai的值的值p-nextai+1的地址的地址鏈表不具備的特點(diǎn)是鏈表不具備的特點(diǎn)是 。 A A、可隨機(jī)訪問(wèn)任何一個(gè)元素、可隨機(jī)訪問(wèn)任何一個(gè)元素 B B、插入、刪除操作不需求挪動(dòng)元素、插入、刪除操作不需求挪動(dòng)元素 C C、無(wú)需事先估計(jì)存儲(chǔ)空間大小、無(wú)需事先估計(jì)存儲(chǔ)空間大小 D D、所需存儲(chǔ)空間與線性表長(zhǎng)度成正比、所需存儲(chǔ)空間與線性表長(zhǎng)度成正比 靜態(tài)鏈表靜態(tài)鏈表 用數(shù)組模擬可利用空間表用數(shù)組模擬可利用空間表 0 1 2 3 4 5 6 7 8 9 3 8 1 -1 6 cur(游標(biāo)) a2 a1 a

12、4 a3 data # define MAXSIZE 10 /鏈表的最大長(zhǎng)度鏈表的最大長(zhǎng)度typedef struct ElemType data;int cur;componet, SLinkListMAXSIZE;第第1 1個(gè)元素的下標(biāo)：個(gè)元素的下標(biāo)： SLinkList0.curSLinkList0.cur帶頭結(jié)點(diǎn)的單鏈表上的根本運(yùn)算1 1 建立單鏈表建立單鏈表2 2 單鏈表查找單鏈表查找3 3 單鏈表插入單鏈表插入4 4 單鏈表刪除第單鏈表刪除第i i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)建立單鏈表1) 頭插法建表逆序頭插法建表逆序操作步驟：操作步驟：建立一個(gè)建立一個(gè)“空表；空表；輸入數(shù)據(jù)元素輸入數(shù)據(jù)元素an，

13、 建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；輸入數(shù)據(jù)元素輸入數(shù)據(jù)元素an-1， 建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；ananan-1依次類(lèi)推，直至輸入依次類(lèi)推，直至輸入a1為止。為止。ss頭插法建表算法Linklist CreateFromHead()Linklist CreateFromHead() LinkList L;Node LinkList L;Node * *s;int flag=1;/s;int flag=1;/標(biāo)志標(biāo)志flagflag初值初值為為1 1 L=(Linklist)malloc(sizeof(Node);/ L=(Linklist)malloc(sizeof(Node);/分配頭

14、結(jié)分配頭結(jié)點(diǎn)點(diǎn) L-next=NULL; L-next=NULL; while(flag) / while(flag) /輸入輸入“$ $時(shí)時(shí), flag, flag置置0, 0, 建建表終了表終了 c=getchar(); c=getchar(); if(c!= if(c!=$ $) /) /為新結(jié)點(diǎn)分配存儲(chǔ)空間為新結(jié)點(diǎn)分配存儲(chǔ)空間 s=(Node s=(Node* *)malloc(sizeof(Node); s-data=c;)malloc(sizeof(Node); s-data=c; s-next=L-next; L-next=s; / s-next=L-next; L-next=s

15、; /鏈接鏈接 else flag=0; else flag=0; return L return L； r c1 c1 s sLcn cn s 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 c2 s sr 尾插法建表算法Linklist CreateFromTail() /Linklist CreateFromTail() /新結(jié)點(diǎn)加到鏈表末尾新結(jié)點(diǎn)加到鏈表末尾 LinkList L;Node LinkLis

16、t L;Node * *r,r,* *s;int flag =1;/flags;int flag =1;/flag初值初值 L=(Node L=(Node * *)malloc(sizeof(Node); /)malloc(sizeof(Node); /分配頭結(jié)點(diǎn)分配頭結(jié)點(diǎn) L-next=NULL; r=L; /r L-next=NULL; r=L; /r一直指向鏈表的表尾一直指向鏈表的表尾 while(flag) / while(flag) /輸入輸入“$ $時(shí)時(shí)flagflag為為0 0，建表終，建表終了了 c=getchar(); c=getchar(); if(c!= if(c!=$

17、$) ) s=(Node s=(Node* *)malloc(sizeof(Node);s-data=c;)malloc(sizeof(Node);s-data=c; r-next=s; r=s / r-next=s; r=s /鏈接鏈接 else flag=0; r-next=NULL; else flag=0; r-next=NULL; return L return L； 單鏈表查找1) 按序號(hào)查找按序號(hào)查找 算法描畫(huà)：設(shè)帶頭結(jié)點(diǎn)的單鏈表的算法描畫(huà)：設(shè)帶頭結(jié)點(diǎn)的單鏈表的長(zhǎng)度為長(zhǎng)度為n, 要查找表中第要查找表中第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), 那么需那么需求從單鏈表的頭指針求從單鏈表的頭指針L出發(fā)出發(fā),

18、 從頭結(jié)點(diǎn)從頭結(jié)點(diǎn)L-next開(kāi)場(chǎng)順著鏈域掃描開(kāi)場(chǎng)順著鏈域掃描, 用指針用指針p指向當(dāng)前掃描到的結(jié)點(diǎn)指向當(dāng)前掃描到的結(jié)點(diǎn),初值指向頭結(jié)點(diǎn)初值指向頭結(jié)點(diǎn) (p=L), 用用j做記數(shù)器做記數(shù)器, 累計(jì)當(dāng)前掃描過(guò)的累計(jì)當(dāng)前掃描過(guò)的結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)(初值為初值為0), 當(dāng)當(dāng)j=i 時(shí)時(shí), 指針指針p所指的所指的結(jié)點(diǎn)就是要找的第結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。算法實(shí)現(xiàn)個(gè)結(jié)點(diǎn)。算法實(shí)現(xiàn), 算法演示。算法演示。L 線性表的操作 Get (L, i)在單鏈表中i=3時(shí),Get的實(shí)現(xiàn)過(guò)程:211830754256pppj1 2 3P-data=30 因此，查找第因此，查找第 i 個(gè)數(shù)據(jù)元素的根本個(gè)數(shù)據(jù)元素的根本操作為：挪

19、動(dòng)指針，比較操作為：挪動(dòng)指針，比較 j 和和 i 。 令指針令指針 p 一直指向線性表中第一直指向線性表中第 j 個(gè)數(shù)據(jù)元素。個(gè)數(shù)據(jù)元素。 單鏈表是一種順序存取的構(gòu)造單鏈表是一種順序存取的構(gòu)造, 為為找第找第 i 個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素, 必需先找到第必需先找到第 i-1個(gè)個(gè)數(shù)據(jù)元素。數(shù)據(jù)元素。按序號(hào)查找算法實(shí)現(xiàn)/找第找第i i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), ,找到前往指向它的指針找到前往指向它的指針; ;否那么前往否那么前往空空Node Node * * Get(LinkList L, int i) Get(LinkList L, int i) Node Node * *p p； p=L p=L；j=0j=0

20、； / / 從頭結(jié)點(diǎn)開(kāi)場(chǎng)掃描從頭結(jié)點(diǎn)開(kāi)場(chǎng)掃描 while (p-next!=NULL)&(jnext!=NULL)&(jnext p=p-next； j+ j+； / / 掃描下一結(jié)點(diǎn)掃描下一結(jié)點(diǎn) if ifi= =ji= =jreturn preturn p； / / 找到了第找到了第i i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) else return NULL else return NULL； / / 找不到找不到,i0,i0或或inin 算法時(shí)間復(fù)雜度為算法時(shí)間復(fù)雜度為: :O(Length(*L)2) 2) 按值查找按值查找算法描畫(huà)：按值查找是指在單鏈表算法描畫(huà)：按值查找是指在單鏈表中查找能否

21、有結(jié)點(diǎn)值等于中查找能否有結(jié)點(diǎn)值等于e e的結(jié)點(diǎn)，假的結(jié)點(diǎn)，假設(shè)有的話，那么前往初次找到的其值為設(shè)有的話，那么前往初次找到的其值為e e的結(jié)點(diǎn)的存儲(chǔ)位置，否那么前往的結(jié)點(diǎn)的存儲(chǔ)位置，否那么前往NULLNULL。查找過(guò)程從單鏈表的頭指針指向的頭結(jié)查找過(guò)程從單鏈表的頭指針指向的頭結(jié)點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定值值e e作比較。算法實(shí)現(xiàn)，算法演示。作比較。算法實(shí)現(xiàn)，算法演示。按值查找算法實(shí)現(xiàn)/查找其結(jié)點(diǎn)值等于查找其結(jié)點(diǎn)值等于keykey的結(jié)點(diǎn)，假設(shè)找到那么前往的結(jié)點(diǎn)，假設(shè)找到那么前往該結(jié)點(diǎn)的位置該結(jié)點(diǎn)的位置p p，否那么前往，否那么前往NULL NULL * *

22、 / /Node Node * *Locate( LinkList L,ElemType key)Locate( LinkList L,ElemType key) Node Node * *p;p; p=L-next; / p=L-next; / 從表中第一個(gè)結(jié)點(diǎn)比較從表中第一個(gè)結(jié)點(diǎn)比較 while (p!=NULL)while (p!=NULL) if (p-data!=key) if (p-data!=key) p=p-next; p=p-next; else break; / else break; / 找到結(jié)點(diǎn)找到結(jié)點(diǎn)keykey，退出循環(huán)，退出循環(huán) return p;return p

23、; 算法時(shí)間復(fù)雜度為算法時(shí)間復(fù)雜度為: :O(Length(*L)ai-13. 單鏈表插入操作單鏈表插入操作 InsList(L, i, e)的實(shí)現(xiàn)：的實(shí)現(xiàn)： 有序?qū)?改動(dòng)為 和 eaiai-1 可見(jiàn)可見(jiàn), 插入結(jié)點(diǎn)需求修正第插入結(jié)點(diǎn)需求修正第 i-1 個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的指針和新結(jié)點(diǎn)的指針。指針和新結(jié)點(diǎn)的指針。在單鏈表第在單鏈表第i i個(gè)結(jié)點(diǎn)之前插入結(jié)點(diǎn)的步驟為個(gè)結(jié)點(diǎn)之前插入結(jié)點(diǎn)的步驟為: :pres1)1)找到單鏈表的第找到單鏈表的第i-1i-1個(gè)結(jié)點(diǎn)并由指針個(gè)結(jié)點(diǎn)并由指針prepre指示。指示。2)2)然后懇求一個(gè)新結(jié)點(diǎn)并由指針然后懇求一個(gè)新結(jié)點(diǎn)并由指針s s指示。指示。3)3)將將prep

24、re指示結(jié)點(diǎn)的指針值賦給指示結(jié)點(diǎn)的指針值賦給s s指示結(jié)點(diǎn)的指針域。指示結(jié)點(diǎn)的指針域。 ( (將第將第i i個(gè)結(jié)點(diǎn)鏈接到新結(jié)點(diǎn)上個(gè)結(jié)點(diǎn)鏈接到新結(jié)點(diǎn)上) )4)4)然后修正然后修正prepre指示結(jié)點(diǎn)的指針域指示結(jié)點(diǎn)的指針域, , 使它等于使它等于s s。 ( (新結(jié)點(diǎn)鏈接到第新結(jié)點(diǎn)鏈接到第i-1i-1個(gè)結(jié)點(diǎn)上個(gè)結(jié)點(diǎn)上) )單鏈表插入int InsList(LinkList L,int i,ElemType e)int InsList(LinkList L,int i,ElemType e) / /在單鏈表在單鏈表L L第第i i個(gè)結(jié)點(diǎn)前插入值為個(gè)結(jié)點(diǎn)前插入值為e e的新結(jié)點(diǎn)的新結(jié)點(diǎn) Node

25、Node * *pre,pre,* *s; pre=L; int k=0;s; pre=L; int k=0; / /先找到第先找到第i-1i-1個(gè)結(jié)點(diǎn)的存儲(chǔ)位置個(gè)結(jié)點(diǎn)的存儲(chǔ)位置, ,讓讓PrePre指向它指向它 while(pre!=NULL&ki-1) while(pre!=NULL&knext; pre=pre-next; k=k+1; k=k+1; if(k!=i-1) return 0; if(k!=i-1) return 0; s=(Node s=(Node* *)malloc(sizeof(Node); /)malloc(sizeof(Node); /懇求新結(jié)點(diǎn)懇

26、求新結(jié)點(diǎn) s-data=e; / s-data=e; /將將e e賦給賦給s s指示的數(shù)據(jù)域指示的數(shù)據(jù)域 s-next=pre-next; pre-next=s; / s-next=pre-next; pre-next=s; /鏈接鏈接 return 1; return 1; 算法時(shí)間復(fù)雜度為算法時(shí)間復(fù)雜度為: :O(Length(*L) s=(Node s=(Node* *)malloc(sizeof(Node); /)malloc(sizeof(Node); /懇求新結(jié)點(diǎn)懇求新結(jié)點(diǎn) s-data=e; / s-data=e; /將將e e賦給賦給s s的數(shù)據(jù)域的數(shù)據(jù)域 s-next=pre

27、-next; pre-next=s; / s-next=pre-next; pre-next=s; /鏈接鏈接 ai-1 eaiai-1pres 如以下圖所示的是鏈表插入前、后的邏輯形狀。從圖中可以看出，要插入一個(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; 鏈表插入邏輯表示圖(a) 插入前；(b) 插入后(b)a1ai1kaiqpankHeadxp(a)a1a2ai1aiqpanxkHead在鏈表的插入操作中，結(jié)點(diǎn)插入的位置能夠有四種情況，下面分別加以引見(jiàn)。設(shè)He

28、ad是鏈表入口或表頭，x是插入結(jié)點(diǎn)的存儲(chǔ)地址。(1) 原來(lái)鏈表為空表，即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；(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； 單鏈表刪除第i個(gè)結(jié)點(diǎn)操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)*p,修正

29、其指針域讓它指向第i+1個(gè)結(jié)點(diǎn)。釋放第i個(gè)結(jié)點(diǎn)的空間。ai-1aiai+1ai-1r= p-next; p-next= r-next; r= p-next; p-next= r-next; free(r);free(r);print DelList(LinkList L,int i,ElemType int DelList(LinkList L,int i,ElemType * *e)e)/刪除單鏈表刪除單鏈表L L中第中第i i個(gè)元素個(gè)元素, ,并保管其值到變量并保管其值到變量* *e e中中 Node Node * *p,p,* *r; p=L; int k =0;r; p=L; int

30、k =0; while(p-next!=NULL & knext!=NULL & knext; k=k+1; p=p-next; k=k+1; if(k!=i-1) / if(k!=i-1) /即循環(huán)因即循環(huán)因p-next=NULLp-next=NULL而跳出而跳出 return 0; return 0; r=p-next; p-next=r-next; / r=p-next; p-next=r-next; /刪除結(jié)點(diǎn)刪除結(jié)點(diǎn) free(r); / free(r); / 釋放被刪除結(jié)點(diǎn)所占空間釋放被刪除結(jié)點(diǎn)所占空間 return 1; return 1; 算法的時(shí)間復(fù)雜度為算法

31、的時(shí)間復(fù)雜度為:O(Length(*L) 鏈表刪除的邏輯表示圖(a) 刪除前；(b) 刪除后xHeadqsp(a)xHeadqsp(b) 從上圖中可以看出，要?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；刪除操作和插入操作一樣，即在鏈表中搜索到被刪除的結(jié)點(diǎn)，修正相應(yīng)的指針，同時(shí)把被刪除的結(jié)點(diǎn)經(jīng)過(guò)調(diào)用free(x)，將該結(jié)點(diǎn)的空間送空間表。根據(jù)被刪除結(jié)點(diǎn)在鏈表中的位置，刪除操作有如下四種情況：(1) 鏈表中只需一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)就是被刪除的結(jié)點(diǎn)，其操作為Head=N

32、ULL；或 Head=Head-next；(2) 被刪除的結(jié)點(diǎn)是鏈中第一個(gè)結(jié)點(diǎn)，其操作為 Head=Head-next；(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；以下圖給出了線性表刪除算法的框圖。 線性鏈表刪除算法框圖開(kāi)始循環(huán)查找值為KEY的結(jié)點(diǎn)是否找到？是否第一個(gè)結(jié)點(diǎn)?刪除中間或鏈尾結(jié)點(diǎn)刪除結(jié)點(diǎn)送空間表結(jié)束輸出無(wú)此結(jié)點(diǎn)修改鏈?zhǔn)譟YNN刪除算法：DELETE(head，key)/* 在hea

33、d為入口的鏈表中刪除值為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)的位置 */if(i=NULL) printf(無(wú)此結(jié)點(diǎn))；return；else if(head=i) head=i-next；/* 刪除頭結(jié)點(diǎn) */ else w-next=i-next；/*刪除鏈中間和鏈尾結(jié)點(diǎn) */ free(i)；用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問(wèn)題：存在的問(wèn)題： 改良鏈表的設(shè)置：改良鏈表的設(shè)置：1單鏈表的

34、表長(zhǎng)是一個(gè)隱含的值；單鏈表的表長(zhǎng)是一個(gè)隱含的值； 1添加表長(zhǎng)、表尾指針 和 當(dāng)前位置指針 ；2在單鏈表的最后一個(gè)元素之后插入元素時(shí)，在單鏈表的最后一個(gè)元素之后插入元素時(shí)， 需遍歷整個(gè)鏈表；需遍歷整個(gè)鏈表；3在鏈表中，元素的在鏈表中，元素的“位序概念淡化，結(jié)點(diǎn)的位序概念淡化，結(jié)點(diǎn)的 “位置概念加強(qiáng)。位置概念加強(qiáng)。2將根本操作中的將根本操作中的“位序位序 i 改動(dòng)為改動(dòng)為“指針指針 p 。3 循環(huán)鏈表 最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)或頭結(jié)點(diǎn)的鏈表 a1 a2 . an 和單鏈表的差別: 判別鏈表中尾結(jié)點(diǎn)的條件不再是“后繼指針能否為空，而是“后繼指針能否為頭指針。rear L空鏈表空鏈表

35、a1ai-1aian L設(shè)頭指針的普通方式設(shè)頭指針的普通方式 a1ai-1aian 設(shè)尾指針的普通方式設(shè)尾指針的普通方式 rear-next帶頭結(jié)點(diǎn)的循環(huán)帶頭結(jié)點(diǎn)的循環(huán)單鏈表表示圖單鏈表表示圖經(jīng)過(guò)查詢(xún)，確定關(guān)鍵字值KEY不在鏈中，該結(jié)點(diǎn)插入的位置和插入的操作有如下幾種情況：(1) 假設(shè)表空(Head=NULL)，那么插入結(jié)點(diǎn)后是只需一個(gè)結(jié)點(diǎn)的環(huán)鏈表。(2) 假設(shè)表非空，那么分為三種情況： 插入的位置是在第一個(gè)結(jié)點(diǎn)，即原表的第一個(gè)結(jié)點(diǎn)成為結(jié)點(diǎn)插入后新表的第二個(gè)結(jié)點(diǎn)，同時(shí)為了堅(jiān)持循環(huán)鏈表的構(gòu)造特征，在構(gòu)成新的入口后，鏈表中最末一個(gè)結(jié)點(diǎn)的鏈指針應(yīng)修正指向新的入口結(jié)點(diǎn)。循環(huán)鏈表的插入操作 插入的位置是

36、在最末一個(gè)結(jié)點(diǎn)之后，那么，最末一個(gè)結(jié)點(diǎn)的指針指向插入的結(jié)點(diǎn)，插入結(jié)點(diǎn)的指針仍指向首結(jié)點(diǎn)。 插入的位置是在鏈的中間，那么可經(jīng)過(guò)插入位置的前趨結(jié)點(diǎn)的指針，完成新結(jié)點(diǎn)的插入。以下圖所示為四種插入操作的表示圖。 循環(huán)有序鏈表的插入操作表示圖HeadxxHead(c)(d)(a)Headx(b)Headx 以下圖給出了循環(huán)鏈表刪除關(guān)鍵字值為KEY的結(jié)點(diǎn)的算法框圖。循環(huán)鏈表的刪除操作循環(huán)鏈表刪除算法框圖開(kāi)始調(diào)用查找子程序被刪除記錄是否在表中？被刪除記錄是否在表首？表中是否只有一個(gè)記錄？查循環(huán)鏈表最末一個(gè)記錄刪除指定的記錄，修正循環(huán)鏈表入口最末一個(gè)記錄鏈的指針指向新的入口 刪除指定的記錄， 修正有關(guān)鏈指針刪

37、除指定的記錄，表空被刪記錄不在表中被刪除記錄送空鏈表結(jié)束NYYNNY 必需留意，在循環(huán)鏈表中，要充分思索到能夠出現(xiàn)被刪除結(jié)點(diǎn)位置不同的各個(gè)邊境條件。假設(shè)被刪除結(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)的算法類(lèi)似。循環(huán)鏈表刪除首結(jié)點(diǎn)(a) 刪除結(jié)點(diǎn)之前；(b) 刪除結(jié)點(diǎn)之后ijkHeadjkHead(a)(b)例例 有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表LALA、LBL

38、B，編寫(xiě)算法，將兩個(gè)循環(huán)單鏈表合并為一個(gè)編寫(xiě)算法，將兩個(gè)循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表，其頭指針為循環(huán)單鏈表，其頭指針為L(zhǎng)ALA。算法思想：先找到兩個(gè)鏈表的尾，并分別由指算法思想：先找到兩個(gè)鏈表的尾，并分別由指針針p p、q q指向它們，然后將第一個(gè)鏈表的尾與第指向它們，然后將第一個(gè)鏈表的尾與第二個(gè)表的第一個(gè)結(jié)點(diǎn)鏈接起來(lái)，并修正第二個(gè)二個(gè)表的第一個(gè)結(jié)點(diǎn)鏈接起來(lái)，并修正第二個(gè)表的尾表的尾q q，使它的鏈域指向第一個(gè)表的頭結(jié)點(diǎn)。，使它的鏈域指向第一個(gè)表的頭結(jié)點(diǎn)。LinkList merge_1(LinkList LA,LinkList LB)LinkList merge_1(LinkList LA

39、,LinkList LB)/ /* *此算法將兩個(gè)循環(huán)單鏈表的首尾銜接起來(lái)此算法將兩個(gè)循環(huán)單鏈表的首尾銜接起來(lái)* */ / Node Node * *p, p, * *q; p=LA; q=LB;q; p=LA; q=LB; while(p-next!=LA) p=p-next; / while(p-next!=LA) p=p-next; /找到找到LALA的表尾的表尾 while(q-next!=LB) q=q-next; / while(q-next!=LB) q=q-next; /找到找到LBLB的表尾的表尾 p-next=LB-next; / p-next=LB-next; /使使LA

40、LA尾指針指向尾指針指向LBLB第第1 1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) q-next=LA; / q-next=LA; /使使LBLB的尾指針指向表的尾指針指向表LALA的頭結(jié)點(diǎn)的頭結(jié)點(diǎn) free(LB); / free(LB); /釋放釋放LBLB的頭結(jié)點(diǎn)空間的頭結(jié)點(diǎn)空間 return(LA); return(LA); 4 雙向鏈表雙向鏈表typedef struct Node /typedef struct Node /結(jié)點(diǎn)類(lèi)型定義結(jié)點(diǎn)類(lèi)型定義 ElemType data ElemType data； struct Node struct Node * * next next； struct Node s

41、truct Node * * prior; prior;Node,Node,* *LinkListLinkList；/LinkList/LinkList為構(gòu)造指針類(lèi)型為構(gòu)造指針類(lèi)型后繼指針域后繼指針域prior data next前驅(qū)指針域前驅(qū)指針域數(shù)據(jù)域數(shù)據(jù)域雙向鏈表的構(gòu)造Head雙向鏈表的構(gòu)造有以下特點(diǎn)：(1) 假設(shè)Head為空(NULL)，那么雙向鏈表為空。(2) 在雙向鏈表中，假設(shè)結(jié)點(diǎn)i有i-Lnext=NULL那么該結(jié)點(diǎn)是鏈的第一個(gè)結(jié)點(diǎn)；假設(shè)結(jié)點(diǎn)i有i-Lnext=i-Rnext=NULL 那么該結(jié)點(diǎn)i是鏈的第一個(gè)結(jié)點(diǎn)且該鏈僅有這個(gè)結(jié)點(diǎn)i。(3) 在雙鏈表中，假設(shè)結(jié)點(diǎn)i有i-Rnex

42、t=NULL那么該結(jié)點(diǎn)是鏈的最末一個(gè)結(jié)點(diǎn)。(4) 在雙向鏈表中，假設(shè)結(jié)點(diǎn)i是表中恣意結(jié) 點(diǎn) 的 地 址 ， 那 么 該 結(jié) 點(diǎn) 的 前 趨 結(jié) 點(diǎn) 是iLnext，后繼結(jié)點(diǎn)的地址是iRnext，對(duì)結(jié)點(diǎn)i也可以表示為i= i-Rnext-Lnext= i-Lnext-Rnext這個(gè)表達(dá)式非常直觀地反映了雙向鏈表構(gòu)造的本質(zhì)特點(diǎn)，即無(wú)論是沿著表向前，還是向后都同樣方便。雙向鏈表的操作特點(diǎn)：雙向鏈表的操作特點(diǎn)：“查詢(xún)和單鏈表一樣?？商砑右环N從后向前的“查詢(xún)方式?！安迦氩迦?和和“刪除時(shí)需求同時(shí)修正刪除時(shí)需求同時(shí)修正兩個(gè)方向上的指針。兩個(gè)方向上的指針。ai-1aies-next = p-next; p-

43、next = s;s-next = p-next; p-next = s;s-next-prior = s; s-prior = p;s-next-prior = s; s-prior = p;sai-1ai插入插入pai-1刪除刪除aiai+1q=p-next; p-next=q-next;q=p-next; p-next=q-next;p-next-prior=p; free(q);p-next-prior=p; free(q);pai-1q雙向鏈表刪除操作能否可不用任務(wù)指針雙向鏈表刪除操作能否可不用任務(wù)指針q?q?q qai-1刪除刪除aiai+1p-next = p-next-next;p-next = p-next-next;free(p-next-prior);free(p-next-prior);p-next-prior = p; p-next-prior = p; pai-1空表空表