一、順序表

二.鏈表

目錄

?一、順序表

二.鏈表

---

---

一.順序表

1.基本概念：是指用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)。我們常見的順序表有數(shù)組。

2.操作方面：可以基本實現(xiàn)數(shù)據(jù)的增刪改查，因為有下標索引，所以查詢工作很方便，效率很高。但是在增加元素和刪除就不是很方便了，因為元素要整體移位置，會比較麻煩，下面的鏈表可以解決這個問題。

3.時間復雜度的對比：如圖所示

二.鏈表

1.鏈表和順序表有所區(qū)別，儲存地址不一定是連續(xù)的。當查詢操作多的時候一般用順序表，刪除和插入多的一般用鏈表，選擇合適的數(shù)據(jù)結(jié)構(gòu)很重要。

2.單鏈表有head頭結(jié)點，后繼結(jié)點，尾結(jié)點指向為null。用指針進行遍歷時，While（p.next!=null）即可。

圖示：

3.head頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，也可以存儲如線性表的長度等類的附加信息。頭結(jié)點的指針域指向首元結(jié)點。并且頭結(jié)點不計入鏈表的長度。

4.注意：單鏈表只有后繼結(jié)點，可以向后移動，不可以回頭。當結(jié)點在向后移動時，要保存p結(jié)點往后的結(jié)點，可以設置一個臨時q=p.next來保存p的后繼結(jié)點。

5.在插入時，注意順序，如：要求在head和head.next之間插入一個s，代碼如下：

s.next=head.next; ??

head.next=s;(注：兩者順序不能調(diào)換)

6.刪除時，單鏈表與順序表比較很是方便，時間復雜度是O（1），只需將要刪除的結(jié)點的后繼結(jié)點改為待刪除結(jié)點的后繼結(jié)點即可。

在java中刪除的結(jié)點會自動回收，在c語言中要自己釋放刪除的結(jié)點：free(p)。

實現(xiàn)代碼如下:

? ? ? ? ? ? ? ? ?s.next=p.next; (s為待刪除結(jié)點p的前一個結(jié)點)

7.頭插法：倒序排列——可以理解為將其插在head和head.next之間。實現(xiàn)代碼：將數(shù)組元素值傳遞給s結(jié)點，for循環(huán)遍歷

? ? ? ? ? ? ? ? ? s.next=L.head.next;

???????????????????L.head.next=s;

圖示：

注：在實際運用中一般要用一個q來臨時保存s的后繼結(jié)點。

8.尾插法：正序排列——可以理解為一個個按順序插在head后面。實現(xiàn)代碼：將數(shù)組元素值傳遞給s結(jié)點，for循環(huán)遍歷

將t設置為L.head

t.next=s;

????????????t=s；//將t向后移動

圖示：

9.單鏈表例題：

（一）求中位數(shù)：

方法一，找到編號（n-1）/2+1位置的結(jié)點即可。其中可以用Math.cell（n/2f）向上取整代替，其中f是為了使其里面變成double類型。

方法二,快慢指針法，快指針一次移動兩個結(jié)點，慢結(jié)點一次移動一個結(jié)點。所有當快指針遍歷完時，慢指針只走了一般，即所指向的位置就是中位數(shù)。

（二）統(tǒng)計最大值個數(shù)：

方法一，直觀方法，先找最大值，再遍歷尋找等于最大值的數(shù)，統(tǒng)計個數(shù)，需要用到兩次while循環(huán)。

方法二，設置p指向首結(jié)點，初始化最大值為首結(jié)點的值，p=p.next不停的向后移動。

思想：當遍歷未結(jié)束時，將后繼的結(jié)點和max比較，比它大設置新的max值，個數(shù)記為1。再次遇到相同的值，個數(shù)再加1……知道遇到比max大的后繼結(jié)點，在設置新的max值，重置個數(shù)為1，依次進行直到結(jié)束。一次while循環(huán)即可。

（三）二路歸并有序表A和B合并為新的升序表C，空間復雜度為O（1），只能結(jié)點重組來建立單鏈表C。

（四）將A和B中的相同元素放入單鏈表C，不改變A和B，只能通過復制來建立單鏈表C。兩者注意區(qū)分。

圖示：

10.雙鏈表：可以理解為高級一些的鏈表，結(jié)點由前端指針域，數(shù)據(jù)域和后端指針域三要素組成。每一個結(jié)點有兩個指向，其中頭結(jié)點的前端指向null，尾結(jié)點后端指向null。

圖示如下：

11.雙鏈表和單鏈表的對比：雙鏈表更加高效，可以實現(xiàn)從前往后，也可以從后往前遍歷；而單鏈表則是比較單一，只能從前往后，只有一個指針，無法找前驅(qū)結(jié)點。

在刪除一個結(jié)點時，雙鏈表不需要找到前驅(qū)結(jié)點，只需要找到刪除的結(jié)點就可以實現(xiàn)刪除操作。 ?

12.循環(huán)鏈表：顧名思義，就是是表中最后一個結(jié)點的指針域指向頭結(jié)點(首節(jié)點和末節(jié)點被連接在一起)，整個鏈表形成一個環(huán)。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖示：

13.循環(huán)鏈表和單鏈表區(qū)別：單鏈表的尾結(jié)點指針指向空地址，表示這就是最后的結(jié)點了。循環(huán)鏈表的尾結(jié)點指針是指向鏈表的頭結(jié)點。

14.循環(huán)鏈表的運用：適用于存儲有循環(huán)特點的數(shù)據(jù)，比如約瑟夫問題：由一群元素構(gòu)成的環(huán)形鏈表，首先由某個元素開始報數(shù)，報到K時的那個元素需要出圈，然后又由下一個元素開始報數(shù)，直到全部的元素出圈時才結(jié)束。