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

1、數(shù)據(jù)結(jié)構(gòu)講義- 鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)信息工程學(xué)院信息工程學(xué)院王晟王晟Email:2.3 .1 鏈表的表示鏈表的表示特點(diǎn)：特點(diǎn)：l用一組用一組任意任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素l利用利用指針指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素的元素l每個(gè)數(shù)據(jù)元素每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息接后繼的信息l結(jié)點(diǎn)結(jié)點(diǎn) 數(shù)據(jù)域數(shù)據(jù)域：元素本身信息：元素本身信息 指針域指針域：指示直接后繼的存儲(chǔ)位置：指示直接后繼的存儲(chǔ)位置ZHAOQIANSUNLIZHOUWUZHENGWANGH例

2、例 線性表線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲(chǔ)地址1713192531374331H頭指針1、結(jié)點(diǎn)：結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2、鏈表：鏈表： n 個(gè)結(jié)點(diǎn)由個(gè)結(jié)點(diǎn)由指針鏈指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)浇M成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像存儲(chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3、單鏈表單鏈表、雙鏈表雙鏈表、多鏈表多鏈表、循環(huán)鏈表循環(huán)鏈表： 結(jié)點(diǎn)

3、只有一個(gè)指針域的鏈表，稱為結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表單鏈表或或線性鏈表線性鏈表；有兩個(gè)指針域的鏈表，稱為有兩個(gè)指針域的鏈表，稱為雙鏈表雙鏈表；有多個(gè)指針域的鏈表，稱為有多個(gè)指針域的鏈表，稱為多鏈表多鏈表；首尾相接的鏈表稱為首尾相接的鏈表稱為循環(huán)鏈表循環(huán)鏈表。a1heada2anhead循環(huán)鏈表示意圖：循環(huán)鏈表示意圖：頭指針頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)槭侵赶蜴湵碇械谝粋€(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)頭結(jié)點(diǎn)或或?yàn)闉槭自Y(jié)點(diǎn)首元結(jié)點(diǎn)）的指針。）的指針。 單鏈表可由一個(gè)頭指針唯一確定。單鏈表可由一個(gè)頭指針唯一確定。頭結(jié)點(diǎn)頭結(jié)點(diǎn)是在鏈表的是在鏈表的首元結(jié)點(diǎn)首元結(jié)點(diǎn)之前之前附設(shè)附設(shè)的一個(gè)結(jié)點(diǎn)；的一個(gè)結(jié)點(diǎn)

4、；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息; ;首元結(jié)點(diǎn)首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a a1 1的結(jié)點(diǎn)。的結(jié)點(diǎn)。 頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn) 首元結(jié)點(diǎn)首元結(jié)點(diǎn)a1一個(gè)線性表的邏輯結(jié)構(gòu)為：一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請問其請問其頭指針頭指針的的值值是多少？是多少？存儲(chǔ)地址存儲(chǔ)地址數(shù)據(jù)域數(shù)據(jù)域指針域指針域1LI437QIAN131

5、3SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：答：頭指針頭指針是指向是指向鏈表中第一個(gè)結(jié)點(diǎn)鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵的指針，因此關(guān)鍵是要尋找是要尋找第一個(gè)結(jié)第一個(gè)結(jié)點(diǎn)點(diǎn)的的地址地址。7ZHAOH31頭指針的值是頭指針的值是31上例鏈表的邏輯結(jié)構(gòu)示意圖有以下上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式兩種形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH區(qū)別：區(qū)別： 無頭結(jié)點(diǎn)無頭結(jié)點(diǎn) 有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)答：答：討論1. 在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？討論2. 如何表示空表空表

6、？頭結(jié)點(diǎn)頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對鏈表點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對鏈表進(jìn)行操作時(shí)，可以對進(jìn)行操作時(shí)，可以對空表、非空表空表、非空表的情況以及對的情況以及對首元結(jié)點(diǎn)首元結(jié)點(diǎn)進(jìn)行進(jìn)行統(tǒng)一處理，編程更方便。統(tǒng)一處理，編程更方便。答：答：無頭結(jié)點(diǎn)時(shí)，無頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空當(dāng)頭指針的值為空時(shí)表示空表；時(shí)表示空表；有頭結(jié)點(diǎn)時(shí)，有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭债?dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。時(shí)表示空表。頭指針頭指針頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn)無頭結(jié)點(diǎn)無頭結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭結(jié)

7、點(diǎn)typedef struct Lnode ElemType data; /數(shù)據(jù)域 struct Lnode *next; /指針域Lnode, *LinkList; / *LinkList為Lnode類型的指針教材P28對于單鏈表的抽象描述:介紹三個(gè)有用的庫函數(shù)（都在介紹三個(gè)有用的庫函數(shù)（都在 中）：中）：sizeof(x)計(jì)算變量計(jì)算變量x的長度；的長度；malloc(m) 開辟開辟m字節(jié)長度的地址空間，并返回這字節(jié)長度的地址空間，并返回這段空間的首地址；段空間的首地址；free(p) 釋放指針釋放指針p所指變量的存儲(chǔ)空間，即徹底所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。刪除一個(gè)變量。1.

8、1. 單鏈表的插入單鏈表的插入2. 2. 單鏈表的刪除單鏈表的刪除3. 3. 鏈表的合并鏈表的合并l實(shí)例1（和順序表一樣）：一條記錄有學(xué)號和成績兩個(gè)數(shù)據(jù)項(xiàng)，先不考慮有序的情況編寫程序記錄數(shù)據(jù)。ch2_ltable1.c在鏈表中插入一個(gè)元素的示意圖如下：在鏈表中插入一個(gè)元素的示意圖如下：xsbapabp插入步驟（即核心語句）：插入步驟（即核心語句）：Step 1Step 1：s-next=p-next;Step 2Step 2：p-next=s ；p-nexts-next元素x結(jié)點(diǎn)應(yīng)預(yù)先生成：s=(LinkList)malloc(m);s-data=x;s-next=p-nextStatus L

9、istInsert(LinkList &L, int i, ElemType e)p=L-next; j=1;while(p&jnext; +j;if(!p|ji-1)return ERROR;s=(LinkList)malloc(sizeof(Lnode);s-data=x;s-next=p-next;p-next=s;return OK;注意：注意：i的范的范圍，循環(huán)執(zhí)圍，循環(huán)執(zhí)行完后行完后i的值的值是多少？是多少？在鏈表中刪除某元素的示意圖如下：在鏈表中刪除某元素的示意圖如下：cabp刪除步驟（即核心語句）：刪除步驟（即核心語句）：q = p-next; /保存保存b的指

10、針，靠它才能指向的指針，靠它才能指向cp-next=q-next; /a、c兩結(jié)點(diǎn)相連兩結(jié)點(diǎn)相連free(q) ； /刪除刪除b結(jié)點(diǎn)，徹底釋放結(jié)點(diǎn)，徹底釋放p-next思考：思考： 省略省略free(q)語句語句行不行？行不行？(p-next) - next注意：注意：j的范的范圍，循環(huán)執(zhí)圍，循環(huán)執(zhí)行完后行完后j的值的值是多少？是多少？Status ListDelete(LinkList &L, int i, ElemType &e)p=L-next; j=1;while(p&jnext; +j;if(!p|ji-1)return ERROR;q=p-next;p-ne

11、xt=q-next;e=q-data;Free(q);return OK;算法要求：算法要求：已知：已知：線性表線性表 A、B，分別由，分別由單鏈表單鏈表 LA , LB 存儲(chǔ)，存儲(chǔ)，其中數(shù)據(jù)元素按值其中數(shù)據(jù)元素按值非遞減有序非遞減有序排列，排列，要求：要求：將將 A ，B 歸并歸并為一個(gè)新的線性表為一個(gè)新的線性表C , C 的數(shù)據(jù)的數(shù)據(jù)元素仍按值非遞減排列元素仍按值非遞減排列 。設(shè)線性表。設(shè)線性表 C 由由單鏈表單鏈表 LC 存儲(chǔ)。存儲(chǔ)。假設(shè)：假設(shè)：A=（3，5，8，11），），B=（2，6，8，9，11）預(yù)測：預(yù)測：合并后合并后 C =（ 2 , 3 , 5 , 6 , 8 , 8 , 9

12、 , 11，11 ） 3 511 / 8 LaLa 2 611 / 8 LbLb 9 2 3 6 5 LcLc 8 811 / 911頭結(jié)點(diǎn)頭結(jié)點(diǎn)算法主要包括：算法主要包括：搜索、比較、插入搜索、比較、插入三個(gè)操作：三個(gè)操作：搜索：搜索：需要需要兩個(gè)指針兩個(gè)指針?biāo)阉鲀蓚€(gè)鏈表；搜索兩個(gè)鏈表；比較：比較：比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大??；比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大??；插入：插入：將兩個(gè)結(jié)點(diǎn)中數(shù)據(jù)將兩個(gè)結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表小的結(jié)點(diǎn)插入新鏈表。La3 5 8 11 Lb2 6 8 119 PaPbPaPbPa、Pb用于搜索用于搜索La和和Lb， Pc指向新鏈表當(dāng)前結(jié)點(diǎn)指向新鏈表當(dāng)前結(jié)點(diǎn)Lc Pa3 P

13、cPa5 Pc11Pc2 PbPcPa算法實(shí)現(xiàn)：算法實(shí)現(xiàn)： Void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) /按值排序的單鏈表按值排序的單鏈表LA,LB，歸并為，歸并為LC后也按值排序后也按值排序 free(Lb); /釋放釋放Lb的頭結(jié)點(diǎn)的頭結(jié)點(diǎn) /MergeList_L pc-next = pa?pa:pb ; /插入剩余段插入剩余段 while(pa&pb) /將將pa 、pb結(jié)點(diǎn)按大小依次插入結(jié)點(diǎn)按大小依次插入C中中 if(pa-datadata) pc-next=pa; pc=pa; p

14、a=pa-next; else pc-next=pb; pc=pb; pb=pb-next pa=La-next; pb=Lb-next; Lc=pc=La； /初始化初始化 答：能。只要將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)答：能。只要將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)即可點(diǎn)即可 ( (P-next=head;P-next=head;) ) 。這種形成環(huán)路的鏈表稱。這種形成環(huán)路的鏈表稱為為循環(huán)鏈表循環(huán)鏈表。特別：帶頭結(jié)點(diǎn)的特別：帶頭結(jié)點(diǎn)的空空循環(huán)鏈表樣式循環(huán)鏈表樣式H參見教材參見教材P35P35 特點(diǎn)：特點(diǎn)： 答：能。只要把單鏈表再多開一個(gè)指針域即可答：能。只要把單鏈表再多開一個(gè)指針域即可(

15、(例例如用如用* *nextnext和和* *priorprior; ;) ) 。雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。prior datanext這種有兩個(gè)指針的鏈表稱為這種有兩個(gè)指針的鏈表稱為雙向鏈表雙向鏈表。其特點(diǎn)是。其特點(diǎn)是可以雙向查找表中結(jié)點(diǎn)。參見教材可以雙向查找表中結(jié)點(diǎn)。參見教材P3539P3539。特別：帶頭結(jié)點(diǎn)的特別：帶頭結(jié)點(diǎn)的空空雙向鏈表樣式：雙向鏈表樣式： /1. 查找查找 因線性鏈表只能順序存取，即在查找時(shí)要因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為從頭指針找起，查找的時(shí)間復(fù)雜度為 O(n)。時(shí)間效率分析2. 插入和刪除插入和刪除 因線性鏈表不需要移動(dòng)元素，只要修因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為改指針，一般情況下時(shí)間復(fù)雜度為 O(1)。 但是，如果要在單鏈表中進(jìn)行但是，如果要在單鏈表中進(jìn)行前插前插或或刪除刪除操作，操作，由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為