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

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

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

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

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

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

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