順序表和鏈?zhǔn)奖泶鎯Y(jié)構(gòu)研究

梁少剛

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

1 線性表的概述

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

1.1 線性表的邏輯結(jié)構(gòu)

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

1.2 線性表的物理結(jié)構(gòu)

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

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

2 順序線性表

2.1 順序表及其存儲結(jié)構(gòu)

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

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

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

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

2.2 順序表的基本運(yùn)算

2.2.1 插入算法

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

2）判斷線性表是否滿，若L.length≥L.listsize說明線性表滿了，不能進(jìn)行插入數(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ù)元素有序、無序沒有要求，只要把給定的關(guān)鍵字與線性表中的數(shù)據(jù)元素逐個進(jìn)行比較，若相等查找就成功，若找遍整個線性表中的數(shù)據(jù)元素都沒有找到與關(guān)鍵字相等的數(shù)據(jù)元素，則查找失敗。

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

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

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

3 鏈?zhǔn)骄€性表

3.1 單鏈表及其存儲結(jié)構(gòu)

線性表最簡單的鏈?zhǔn)酱鎯π问椒Q為單鏈表或線性鏈表，鏈表中每個結(jié)點(diǎn)僅含一個數(shù)據(jù)域和一個指針域，可描述為：

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

3.2 鏈表的基本運(yùn)算

3.2.1 插入算法

1）鏈?zhǔn)酱鎯Φ木€性表做插入操作，不判斷線性表是否滿，但是要從頭指針開始，通過循環(huán)語句循環(huán)查找第i-1個結(jié)點(diǎn)。

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

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

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

3.2.2 刪除算法

1）鏈?zhǔn)酱鎯Φ木€性表做刪除操作前，要從頭指針開始，通過循環(huán)語句循環(huán)查找需要刪除的第i個結(jié)點(diǎn)。

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

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

4）釋放刪除結(jié)點(diǎn)的存儲空間。

3.2.3 查找算法

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

2）循環(huán)鏈表。可以從頭指針開始，也可以從尾指針開始順序地查找結(jié)點(diǎn)的后繼元素。

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

4）對比分析

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

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

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

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

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

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

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