本章主要介紹了下線性表的兩種存儲結構——順序存儲和鏈式存儲，然后引入了大量的練習題來鞏固這兩種存儲方式。 繼續使用[第1章線性表 ](http://blog.csdn.net/u013595419/article/details/50461712)中的配圖來比較下順序表和鏈表。  ## 一.順序表和鏈表的比較 ### 1.1存取方式 > - 順序表既可以順序存取，又可以隨機存取； > - 鏈表只能從表頭到表尾順序存取。 ### 1.2邏輯結構與物理結構（存儲方式） > - 順序表中，邏輯上相鄰的元素，其對應的物理位置亦相鄰； > - 鏈表中，邏輯上相鄰的元素，物理位置不一定相鄰，其對應的邏輯關系是通過指針鏈接形成的。 **注：**此處應注意區別存儲方式和存取方式的基本定義。 　　存取方式指的是讀取數據的方式，比如隨機存取，離散存取等； 　　存儲方式指的是數據的物理結構，比如順序存儲，離散存儲等。 ### 1.3基本操作 ### 1.3.1查找操作 - 按值查找 > 順序表無序的情況下，查找時間復雜度為O(n)；若有序，查找時間復雜度為O(1)。 鏈表無論是否有序，查找時間復雜度均為O(n)。 - 按序號查找 > 順序表支持隨機訪問，時間復雜度為O(1)； 鏈表需要從表頭遍歷到表尾，時間復雜度為O(n)。 ### 1.3.2插入刪除操作 > 順序表需要移動大量元素，時間復雜度為O(n)； 鏈表只需修改節點的指針域即可，時間復雜度為O(1)。 ### 1.4空間分配 > 順序表在創建時就要求分配足夠大的存儲空間。 　采用靜態分配時，若分配空間過大，則會造成浪費嚴重；若分配過小，則會造成溢出； 　采用動態分配時，擴充需要移動大量元素，造成操作效率低下； 鏈表僅在需要的時候申請分配，只要內存空間足夠便可完成分配。 ## 二．順序表和鏈表在現實生活中的選擇 根據上述順序表和鏈表的比較，使得我們更加熟悉了線性表的基本操作。對此我們變可以根據自身的需求來選擇合適的線性表結構。下面說明幾點參考標準： ### 2.1基于存儲的考慮 對于線性表的長度或存儲規模難以估計時，不宜采用順序表；鏈表不用事先估計存儲規模，但鏈表的存儲密度比較低，顯然采用鏈式存儲的線性表存儲密度是小于1的。 ### 2.2基于運算的考慮 當我們在線性表操作中涉及到大量的按序號查找值的操作時，采用順序表無疑是一種不錯的選擇，順序表因為可以實現離散存取，時間復雜度僅為O(1)；而鏈表因為必須使用順序存取，時間復雜度為O(n)。 如果實際使用中使用到了大量的插入和刪除操作時，順序表平均需要移動表中一半的元素，最壞時間復雜度為O(1)；而鏈表做相同的操作時，時間復雜度僅為O(1)。明顯，我們會選擇鏈表。 ### 2.3基于環境的考慮 順序表容易實現，任何高級語言中都有數組類型；而鏈表的操作是基于指針的，有些高級語言中并不具備指針。 總之，究竟選擇順序表還是鏈表還是需要根據自身需要來確定，只有合適的才是最好的。