順序表和鏈式表存儲結構研究

梁少剛

（寶雞職業(yè)技術學院，陜西 寶雞721000）

1 線性表的概述

線性表（Linear list）是最簡單且最常用的一種數(shù)據(jù)結構。這種結構具有下列特點：存在一個唯一的沒有前驅(qū)的（頭）數(shù)據(jù)元素；存在一個唯一的沒有后繼的（尾）數(shù)據(jù)元素；此外，每一個數(shù)據(jù)元素均有一個直接前驅(qū)和一個直接后繼數(shù)據(jù)元素。

1.1 線性表的邏輯結構

線性表是有限元素（a1,a2,a3，…，an）有序序列的集合，a1，a2，…，an都是完全相同結構的數(shù)據(jù)類型，同時它們之間的排列嚴格有序，其中任何元素都對應唯一的前驅(qū)以及唯一的后繼。這樣一個序列可以有查詢、刪除、插入隊列任何位置的數(shù)據(jù)操作。

1.2 線性表的物理結構

順序線性表是用一定大小的數(shù)據(jù)來存放線性表，數(shù)組長度代表線性表的長度，元素在數(shù)組的位置代表元素在線性表的位置。但對數(shù)組中元素不能跳躍插入，因為線性表中元素是順序且連接著的，不像數(shù)組中間可以空元素。同時刪除元素時，必須大量移動剩下的元素，因為必須實現(xiàn)其連續(xù)性。插入元素同樣需要大量移動數(shù)據(jù)。因此這樣存儲的運行效率并不夠高。所以對于有著頻繁插入和刪除運算的線性表，是不適合采用順序存儲的。

鏈式線性表是通過動態(tài)分配，分配物理上不一定相鄰的存儲單元。為表示他們的連續(xù)性連接性，再在分配這個存儲單元時，附加一部分存儲單元———指針域來指出這個元素的后繼元素的存儲地址。鏈式存儲結構又分為單鏈表、循環(huán)鏈表和雙向鏈表等。這樣的鏈式存儲多節(jié)省了操作的時間，但需要更多的存儲空間。

2 順序線性表

2.1 順序表及其存儲結構

用一組地址連續(xù)的存儲單元依次存放線性表里的數(shù)據(jù)元素。用這種方法存儲的線性表簡稱順序表。

線性表的起始地址稱作線性表的地址，以存儲位置相鄰來表示有序?qū)Α碼i-1，ai〉即線性表中第i個數(shù)據(jù)元素的存儲位置LOC(ai)和第i-1個數(shù)據(jù)元素的存儲位置LOC(ai-1)之間滿足下列關系：

LOC(ai)=LOC(ai-1)+L（一個數(shù)據(jù)元素所占的存儲位置）

所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置：順序表的類型定義如下：

2.2 順序表的基本運算

2.2.1 插入算法

1）不用查找插入位置i，只需要判斷i的合法位置，其范圍是1≤i≤L.length+1，否則不合法；

2）判斷線性表是否滿，若L.length≥L.listsize說明線性表滿了，不能進行插入數(shù)據(jù)元素操作，要增加存儲空間的分量或者做出錯處理；

3）將線性表的最后一個數(shù)據(jù)元素到第i-1個數(shù)據(jù)元素依次往后移動一個數(shù)據(jù)單元，空出第i-1個位置的數(shù)據(jù)單元；

4）把新的數(shù)據(jù)元素插入到剛才空出來的數(shù)據(jù)單元中；5）線性表長度增加 1。

2.2.2 刪除算法

1）不用查找刪除位置i，也不用另外判斷線性表是否為空，只要 i取值為1≤i≤L.length就包括了線性表判空操作和刪除位置i的合法性判斷了，否則不合法。

2）將線性表的第i個數(shù)據(jù)元素到最后一個數(shù)據(jù)元素依次往前移動一個數(shù)據(jù)單元，就算刪除了第i個數(shù)據(jù)元素。

3）線性表長度減 1。

2.2.3 查找算法

1）順序查找算法對數(shù)據(jù)元素有序、無序沒有要求，只要把給定的關鍵字與線性表中的數(shù)據(jù)元素逐個進行比較，若相等查找就成功，若找遍整個線性表中的數(shù)據(jù)元素都沒有找到與關鍵字相等的數(shù)據(jù)元素，則查找失敗。

2）折半查找是要求順序存儲和存儲的數(shù)據(jù)元素有序，查找時把給定的關鍵字與表中的中間位置元素進行比較，若相等就查找成功，若關鍵字比中間位置大，則下次在右半部分查找，若比中間位置上的數(shù)據(jù)元素小，則下次在左半部分查找，依次重復，直到找完查找區(qū)間的所有數(shù)據(jù)元素也沒有找到與關鍵字相等的數(shù)據(jù)元素存在，則查找失敗。

3）索引查找是把順序表中的數(shù)據(jù)元素等分成相等的幾部分，使后一個子表的所有數(shù)據(jù)元素均大于前一個子表的最大數(shù)據(jù)元素，并用每一個子表的最大關鍵字建立索引表。進行查找時，將給定關鍵字先與索引表中的關鍵字進行比較，確定此關鍵字屬于哪一個子表，再在這個子表上進行查找。

4）哈希查找是關鍵字與哈希函數(shù)存在某種對應關系，只要通過哈希函數(shù)就能直接確定數(shù)據(jù)元素在哈希表中的對應位置。如果數(shù)據(jù)元素沒有沖突，不用查找就能找到關鍵字；如果存在沖突，就利用解決沖突的辦法來查找這個關鍵字。

3 鏈式線性表

3.1 單鏈表及其存儲結構

線性表最簡單的鏈式存儲形式稱為單鏈表或線性鏈表，鏈表中每個結點僅含一個數(shù)據(jù)域和一個指針域，可描述為：

其中ElemType可根據(jù)需要用int，char等類型來代替；當然這里的數(shù)據(jù)域也可以是一個記錄（如學生記錄）。在這里我們使用帶頭結點的單鏈表。

3.2 鏈表的基本運算

3.2.1 插入算法

1）鏈式存儲的線性表做插入操作，不判斷線性表是否滿，但是要從頭指針開始，通過循環(huán)語句循環(huán)查找第i-1個結點。

2）判斷i的合法性，i的合法范圍是1≤i≤n，否則就是不合法。

3）申請一個結點的存儲空間，并用一個指針變量指向這個結點，把需要插入的數(shù)據(jù)元素值賦給這個結點的數(shù)據(jù)域中。

4）修改插入數(shù)據(jù)元素的指針，完成插入操作。

3.2.2 刪除算法

1）鏈式存儲的線性表做刪除操作前，要從頭指針開始，通過循環(huán)語句循環(huán)查找需要刪除的第i個結點。

2）判斷第i個結點的合法性，i的合法范圍是1≤i≤n，否則不合法。

3）修改刪除數(shù)據(jù)元素的指針，完成刪除操作。

4）釋放刪除結點的存儲空間。

3.2.3 查找算法

1）單鏈表。只能從頭指針開始，一個結點接著一個結點地順序查找，不能找結點前驅(qū)，只能找結點后繼結點。

2）循環(huán)鏈表?？梢詮念^指針開始，也可以從尾指針開始順序地查找結點的后繼元素。

3）雙向鏈表。從頭指針開始順序查找結點，既可以查找結點的前驅(qū)元素，也可以查找結點的后繼元素。

4）對比分析

順序表的優(yōu)點：實現(xiàn)方法簡單。一維數(shù)組在內(nèi)存中占用的空間就是一組連續(xù)的存儲區(qū)域，因此，用一維數(shù)組來表示順序表的數(shù)據(jù)存儲是最合適的。其次，順序表中元素間的物理位置關系正好反映了線性表元素間的邏輯關系，因此，不需要增加額外的存儲開銷。另外順序表還具有按元素序號隨機訪問的特點，只要知道順序表的首地址和每個數(shù)據(jù)元素所占存儲單元的個數(shù)，就可以求出第 i個數(shù)據(jù)元素的存儲地址。

順序表的缺點：由數(shù)組來實現(xiàn)時，數(shù)組下標所標出的必須是定量，但是實際問題中，線性表中的元素個數(shù)是不固定的，線性表中的元素用順序表實現(xiàn)時，必須預先分配足夠大的存儲空間，存儲空間估計過大，可能導致順序表后部空間大量閑置，浪費存儲空間；預留分配過小，又會造成溢出。而且在順序表中做插入和刪除操作時，由于順序表中元素的物理位置必須相鄰，因此需要平均移動大約表中一半的元素，那么當順序表中的元素較多時，順序表的運行效率就會很低。

單鏈表的優(yōu)點：是一種動態(tài)的存儲結構，鏈表中每個結點占用的存儲空間不是預先分配的，而是系統(tǒng)運行時根據(jù)需求生成的，只要內(nèi)存有足夠的空間，就可以存儲任意長度的線性表，一般不會產(chǎn)生溢出。單鏈表不需要用地址連續(xù)的存儲單元來實現(xiàn)，因為它不要求邏輯上相鄰的兩個數(shù)據(jù)元素物理上也相鄰，在單鏈表中做插入和刪除操作時，由于元素間的物理位置關系是由指針實現(xiàn)的，因此只需要改變指針就可以了，不需要移動大量的數(shù)據(jù)元素，大大提高了運行效率。

單鏈表的缺點：需要對每個元素設置一個指針域，用來存儲指示其直接后繼的信息，這就增加了存儲開銷。而且，單鏈表不具有按序號隨機訪問的特點，訪問任意一個元素時都需要從表頭開始依次查找，訪問效率較低。

［1］嚴蔚敏,吳偉民.數(shù)據(jù)結構：C 語言版[M].北京：清華大學出版社,1997.

［2］李春葆.數(shù)據(jù)結構教程[M].2 版.北京：清華大學出版社,2007.

［3］從艷,任益夫,劉向玲.線性表不同存儲結構的比較與應用[J].電腦知識與技術,2007(08).