一、順序表

二.鏈表

目錄

?一、順序表

二.鏈表

---

---

一.順序表

1.基本概念：是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。我們常見的順序表有數組。

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

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

二.鏈表

1.鏈表和順序表有所區別，儲存地址不一定是連續的。當查詢操作多的時候一般用順序表，刪除和插入多的一般用鏈表，選擇合適的數據結構很重要。

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

圖示：

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

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

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

s.next=head.next; ??

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

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

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

實現代碼如下:

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

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

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

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

圖示：

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

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

將t設置為L.head

t.next=s;

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

圖示：

9.單鏈表例題：

（一）求中位數：

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

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

（二）統計最大值個數：

方法一，直觀方法，先找最大值，再遍歷尋找等于最大值的數，統計個數，需要用到兩次while循環。

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

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

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

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

圖示：

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

圖示如下：

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

在刪除一個結點時，雙鏈表不需要找到前驅結點，只需要找到刪除的結點就可以實現刪除操作。 ?

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

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

13.循環鏈表和單鏈表區別：單鏈表的尾結點指針指向空地址，表示這就是最后的結點了。循環鏈表的尾結點指針是指向鏈表的頭結點。

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