前面講了 ‘’談?wù)剶?shù)據(jù)結(jié)構(gòu)之集合的順序存儲(chǔ)‘’,今天接著講集合的鏈?zhǔn)酱鎯?chǔ)，鏈?zhǔn)酱鎯?chǔ)不像順序存儲(chǔ)要求存儲(chǔ)的地址空間是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)的地址空間是任意的。但是所有任意的地址空間必須可以串聯(lián)起來(lái)，不能中斷，只要某一個(gè)地址沒(méi)有被串聯(lián)，那么，它后面的數(shù)據(jù)也就丟失了。鏈?zhǔn)酱鎯?chǔ)的示意圖如下：

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)圖

其中每個(gè)節(jié)點(diǎn)的地址是任意的，每個(gè)節(jié)點(diǎn)包含兩部分：數(shù)據(jù)部分和指向下一節(jié)點(diǎn)地址的指針（由于集合之間元素是沒(méi)有關(guān)系的，所以指針之間隨意串聯(lián)即可，沒(méi)有必要刻意以某種順序來(lái)連接）。

相比于順序存儲(chǔ)，它需要更多的空間,因?yàn)槊總€(gè)節(jié)點(diǎn)除了保存數(shù)據(jù)外，還需要保存一個(gè)代表元素之間關(guān)系的下一節(jié)點(diǎn)地址的指針。

它的優(yōu)點(diǎn)是，插入和刪除元素不需要移動(dòng)元素，只需改變指針的指向關(guān)系就可以了，比如刪除上圖中的a2節(jié)點(diǎn)，則只需把a(bǔ)1的指針指向a3即可。所以時(shí)間復(fù)雜度是O（1），而順序存儲(chǔ)由于要移動(dòng)元素，時(shí)間復(fù)雜度是O（n）。

它的缺點(diǎn)是，訪問(wèn)元素必須重頭開(kāi)始遍歷，比順序存儲(chǔ)慢。比如要訪問(wèn)a7,則必須從a1遍歷到a7才行。所以時(shí)間復(fù)制度是O(n)，而順序存儲(chǔ)只需要通過(guò)下標(biāo)即可訪問(wèn)，所以時(shí)間復(fù)雜度是O(1)。

集合的抽象數(shù)據(jù)類(lèi)型之前講了,‘’談?wù)剶?shù)據(jù)結(jié)構(gòu)之集合的順序存儲(chǔ)‘’

如下：

ADT Set is

? Data:

? ? ? ? 采用任何一種存儲(chǔ)方法存儲(chǔ)的一個(gè)集合

? ? Operation:

? ? ? initSet() //初始化集合

? ? ? add(obj)//添加元素

? ? ? remove(obj)//刪除元素

? ? ? find(obj)//查找元素并返回

? ? ? value(i)//返回集合中第i個(gè)元素的值

? ? ? contains(obj)//集合中是否包含某個(gè)元素

? ? ? size()//獲取集合的長(zhǎng)度

? ? ? isEmpty//判斷集合是否為空

? ? ? clear()//清空集合

? ? ? output()//輸出集合中的所有值

? ? ? union(set)//求兩個(gè)集合的并集

? ? ? intersection(set) //求兩個(gè)集合的交集

同樣的，我用Java把集合的鏈?zhǔn)酱婧筒僮鬟M(jìn)行了實(shí)現(xiàn)，比之前的順序存儲(chǔ)實(shí)現(xiàn)，稍微難度難了那么一點(diǎn)點(diǎn)，但是總體來(lái)說(shuō)還是比較簡(jiǎn)單的。

先看鏈表的節(jié)點(diǎn)類(lèi)型,上面講了它包含兩部分，數(shù)據(jù)和指向下一節(jié)點(diǎn)的指針

節(jié)點(diǎn)類(lèi)型代碼

接著看看鏈表的非操作部分,一個(gè)是代表集合長(zhǎng)度的len，和鏈表的頭指針，以及集合的初始化,集合鏈表實(shí)現(xiàn)了上篇文章講的Set接口,Set接口包含了集合的所有操作。

鏈表的初始化

下面是具體的操作部分：

新增操作

首先進(jìn)行集合中是否包含新增元素的校驗(yàn),因?yàn)榧喜荒艹霈F(xiàn)重復(fù)元素,時(shí)間復(fù)雜度為O（n）。不包含則新增.集合長(zhǎng)度加一，所以新增的時(shí)間復(fù)雜度為O(n）。

新增操作代碼

刪除操作

首先要找到刪除節(jié)點(diǎn)的位置,要從頭結(jié)點(diǎn)開(kāi)始遍歷，所以時(shí)間復(fù)制度為O（n），沒(méi)找到則返回false。如果找到刪除位置后，則用刪除節(jié)點(diǎn)的下一節(jié)點(diǎn)的指針替換刪除節(jié)點(diǎn)的指針，集合長(zhǎng)度減一。所以整體時(shí)間復(fù)雜度O（n）

刪除操作代碼

查找操作

直接從頭結(jié)點(diǎn)開(kāi)始遍歷，找到則返回該節(jié)點(diǎn)的值，否則返回null，時(shí)間復(fù)雜度O（n）

查找操作代碼

獲取第i個(gè)元素操作

i從0開(kāi)始，也需要從頭結(jié)點(diǎn)遍歷,找到第i個(gè)元素后，獲取該節(jié)點(diǎn)的值。時(shí)間復(fù)雜度為O(n)

獲取第i個(gè)元素代碼

判斷元素是否存在于集合操作

首先也得從頭結(jié)點(diǎn)開(kāi)始遍歷，判斷是否等于每個(gè)節(jié)點(diǎn)的值，如果相等，則存在

判斷元素是否存在于集合代碼

清空集合操作

直接把集合長(zhǎng)度設(shè)置為0，然后頭指針指向null，所以時(shí)間復(fù)雜度為O(1)

清空集合代碼

集合判空操作

直接判斷l(xiāng)en是否等于0來(lái)實(shí)現(xiàn),時(shí)間復(fù)雜度O(1)

集合判空代碼

集合輸出操作

直接從頭開(kāi)始遍歷輸出，時(shí)間復(fù)雜度O(n)

集合輸出代碼

獲取集合長(zhǎng)度操作

直接返回len的值即可，時(shí)間復(fù)雜度O(1)

獲取集合長(zhǎng)度

求兩個(gè)集合的并集操作

求并集,即求兩個(gè)集合的非共同元素,即求只包含于A集合,但不包含于B集合或者只包含于B集合,但不包含與A集合的元素。

首先值循環(huán)遍歷本集合A的每個(gè)元素賦值給目標(biāo)集合并集des（時(shí)間復(fù)雜度O(n）），然后遍歷B集合set1得到每個(gè)元素(遍歷m次,時(shí)間復(fù)雜度O（m）),如果不包含與A集合，則添加該元素到并集中(contains需要遍歷A,時(shí)間復(fù)雜度O(n))。所以整的時(shí)間復(fù)雜度為O(m*n)，m、n分別為兩個(gè)集合的長(zhǎng)度

求兩個(gè)集合并集代碼

求兩個(gè)集合交集操作

求交集,即求兩個(gè)集合的共有元素,即既存在于A集合,，也存在于B集合的元素。

首先循環(huán)遍歷一個(gè)集合(循環(huán)n次,n為A集合的長(zhǎng)度),判斷是否存在于另外一個(gè)集合（contains時(shí)間復(fù)雜度為o(m）,m為B集合的長(zhǎng)度）,如果存在則添加到交集中,整體時(shí)間復(fù)雜度為O(m*n).

求兩個(gè)集合交集代碼

好了，到現(xiàn)在，對(duì)集合的說(shuō)明以及它的順序存儲(chǔ)實(shí)現(xiàn)和鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)都講完了，整的花了大概四五個(gè)小時(shí)的時(shí)間寫(xiě)代碼和調(diào)試，三四個(gè)小時(shí)在簡(jiǎn)書(shū)寫(xiě)博文，但是樂(lè)在其中，后面接著聊另外一種比較重要和常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)線性表。歡迎大家關(guān)注吐槽，謝謝。

下面附上所有的代碼和調(diào)試代碼

鏈?zhǔn)郊贤暾a

測(cè)試代碼