數(shù)據(jù)結(jié)構(gòu)第三章、鏈表課件

第三章鏈表一、鏈表相關(guān)知識什么是線性結(jié)構(gòu)。線性結(jié)構(gòu)的特征。什么鏈表。鏈表的特點。鏈表的分類。線性結(jié)構(gòu)線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序（次序）集合。它有四個基本特征：

1．集合中必存在唯一的一個“第一元素”；

2．集合中必存在唯一的一個“最后元素”；

3．除最后元素之外，其它數(shù)據(jù)元素均有唯一的“后繼”；

4．除第一元素之外，其它數(shù)據(jù)元素均有唯一的“前驅(qū)”。線性結(jié)構(gòu)兩種存儲方式： 1.順序存儲方式。 2.鏈?zhǔn)酱鎯Ψ绞?。每個數(shù)據(jù)元素的兩部分信息組合在一起被稱為結(jié)點其中表示數(shù)據(jù)元素內(nèi)容的部分被稱為數(shù)據(jù)域（data）表示直接后繼元素存儲地址的部分被稱為指針或指針域（next）結(jié)點結(jié)構(gòu)圖：鏈表的特點（1）鏈表中的數(shù)據(jù)元素在存儲單元中的存放順序與邏輯順序不一定一致（2）在對鏈表操作時，只能通過頭指針進(jìn)入鏈表，并通過每個結(jié)點的指針域向后掃描其余結(jié)點。鏈表的分類單向鏈表雙向鏈表循環(huán)鏈表二、單鏈表單鏈表的含義。單鏈表及其結(jié)點的程序?qū)崿F(xiàn)。單鏈表上的基本運算。單鏈表結(jié)構(gòu)的實現(xiàn)。單鏈表及其結(jié)點的程序?qū)崿F(xiàn)。（參看課本P28程序片段）1.建立單鏈表頭插法：2.求表長LinkList_Length()算法思路： 設(shè)一個移動指針p和計數(shù)器j。P向后移動，如果p后面還有結(jié)點則j++；否則跳出循環(huán)返回最終j的值。publicintLinkLisk_Length(){ ListNodep=head; intlen=0;while(p!=null){++len;p=p.Next;}returnlen;}3.查找操作按序號查找LinkList_Get(inti)：此運算是從第一個結(jié)點算起，返回單鏈表中第i個結(jié)點。按值查找LinkList_Get(datax)：單鏈表中的按值查找是指在表中查找其值滿足給定值的結(jié)點。4.插入操作LinkList_Insert(i,x)算法過程： 1）找到第i-1個結(jié)點，若存在進(jìn)行下一步；否則結(jié)束。 2）對新結(jié)點進(jìn)行初始化。 3）將第i-1個結(jié)點的后繼作為新節(jié)點的后繼。 4）將新節(jié)點作為第i-1個結(jié)點的后繼。5.刪除操作LinkList_Delete(i)算法過程： 1）找到第i-1個結(jié)點，若存在進(jìn)行下一步；否則結(jié)束。 2）若存在第i個結(jié)點，進(jìn)行下一步；否則結(jié)束。 3）將第i個結(jié)點的后繼賦值給第i-1個結(jié)點的后繼。7.清空單鏈表LinkList_Clear()算法思路： 建立在遍歷的基礎(chǔ)上，對遍歷到得結(jié)點，將每個結(jié)點數(shù)據(jù)域賦值為空。8.求前驅(qū)LinkList_PriorElem（datax）算法思路： 1）如果鏈表為空，結(jié)束；否則，向下進(jìn)行。 2）如果查到x是第一個結(jié)點的值，則沒有前驅(qū)，結(jié)束；否則向下進(jìn)行。 3）查找到值為x的結(jié)點為第i個結(jié)點。 4）查找第i-1個節(jié)點。單鏈表結(jié)構(gòu)的實現(xiàn)ArrayList類的實現(xiàn)。HashTable類的實現(xiàn)。StoredList類的實現(xiàn)HashTable表示鍵/值對的集合，這些鍵/值對根據(jù)鍵的哈希代碼進(jìn)行組織。命名空間:System.Collections每個元素都是一個存儲在DictionaryEntry對象中的鍵/值對。鍵不能為空引用（在VisualBasic中為Nothing），但值可以。

三、循環(huán)鏈表和雙向鏈表循環(huán)鏈表有些應(yīng)用不需要鏈表中有明顯的頭尾結(jié)點。在這種情況下，可能需要方便地從最后一個結(jié)點訪問到第一個結(jié)點。此時，最后一個結(jié)點的引用域不是空引用，而是保存的第一個結(jié)點的地址（如果該鏈表帶結(jié)點，則保存的是頭結(jié)點的地址），也就是頭引用的值。循環(huán)鏈表的基本操作與單鏈表大體相同，只是判斷鏈表結(jié)束的條件并不是判斷結(jié)點的引用域是否為空，而是判斷結(jié)點的引用域是否為頭引用，其它沒有較大的變化。雙向鏈表雙向鏈表結(jié)點示意圖：雙向鏈表結(jié)點的定義與單鏈表結(jié)點的定義很相似，只是多了一個指針域prev。雙向鏈表插入操作算法思路：（將新節(jié)點插入p結(jié)點后） 1）對新節(jié)點進(jìn)行初始化。 2）將新節(jié)點s作為p結(jié)點后繼結(jié)點的前驅(qū)。即p.next.prev=s 3）將p作為s的前驅(qū)。即s.prev=p 4）將p結(jié)點的后繼作為s的后繼