梁少剛

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

1 線性表的概述

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

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

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

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

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

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

2 順序線性表

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

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

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

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

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

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

2.2.1 插入算法

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

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

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

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

2.2.2 刪除算法

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

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

3）線性表長(zhǎng)度減 1。

2.2.3 查找算法

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

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

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

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

3 鏈?zhǔn)骄€性表

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

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

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

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

3.2.1 插入算法

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

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

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

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

3.2.2 刪除算法

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

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

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

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

3.2.3 查找算法

1）單鏈表。只能從頭指針開始，一個(gè)結(jié)點(diǎn)接著一個(gè)結(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）對(duì)比分析

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

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

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

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

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

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

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