曹小妹

摘要：線性表是由數(shù)據(jù)類型相同的若干個(gè)數(shù)據(jù)元素組成的有限序列，其特點(diǎn)和算法容易理解，是學(xué)習(xí)其它數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。該文主要介紹了線性表、線性表的應(yīng)用、線性表的常用算法和線性表的優(yōu)缺點(diǎn)。

關(guān)鍵詞：線性表；動(dòng)態(tài)分配；插入；刪除

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044（2012）30-7216-04

隨著計(jì)算機(jī)產(chǎn)業(yè)的迅速發(fā)展和計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷擴(kuò)大，計(jì)算機(jī)應(yīng)用已不僅僅局限于早期的科學(xué)計(jì)算，而是更多地用于控制、管理和數(shù)據(jù)處理等方面。所以，隨之而來的便是處理的數(shù)據(jù)量越來越大，數(shù)據(jù)類型越來越多，數(shù)據(jù)結(jié)構(gòu)越來越復(fù)雜。因此，針對(duì)實(shí)際問題，例如編制一個(gè)高效率的處理程序，那么就需要解決如何合理地組織數(shù)據(jù)，建立合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)好的算法，來提高程序執(zhí)行的效率這樣的問題。

1 引入線性表動(dòng)態(tài)分配的源由

在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，非線性結(jié)構(gòu)中又以線性表為典型代表，線性表的邏輯結(jié)構(gòu)是通過元素之間的相鄰關(guān)系體現(xiàn)的。因此利用數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)，結(jié)構(gòu)簡單，其算法也容易理解。但是，由于存儲(chǔ)分配只能預(yù)先定義，如果插入的數(shù)據(jù)量超出預(yù)先分配的存儲(chǔ)空間，那么臨時(shí)擴(kuò)大就會(huì)存在很大的困難；如果按最大的可能空間進(jìn)行分配，則勢必降低了存儲(chǔ)空間的利用率。為解決此問題，可以利用C語言動(dòng)態(tài)分配內(nèi)存的機(jī)制，實(shí)現(xiàn)線性表的順序存儲(chǔ)。

2 動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)的基本操作

2.1 動(dòng)態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)的描述

線性表的順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。線性表是一個(gè)相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，它的長度可根據(jù)需要增長或縮短，即對(duì)線性表的數(shù)據(jù)元素不僅可以進(jìn)行訪問，還可以進(jìn)行插入和刪除等。由于高級(jí)程序設(shè)計(jì)語言中的數(shù)據(jù)類型也有隨機(jī)存取的特性，因此，通常都用數(shù)組來描述數(shù)據(jù)結(jié)構(gòu)中的順序存儲(chǔ)結(jié)構(gòu)。在此，由于線性表的長度可變，且所需最大存儲(chǔ)空間隨問題的不同而不同，則在C語言中可用動(dòng)態(tài)分配的一維數(shù)組，如下描述。

在上述定義中，順序表的初始化操作就是為順序表分配一個(gè)預(yù)定義大小的數(shù)組空間，并將線性表的當(dāng)前長度設(shè)為“0”。Listsize指示順序表當(dāng)前分配的存儲(chǔ)空間大小，一旦因插入元素而空間不足時(shí)，可進(jìn)行再分配，即為順序表增加一個(gè)大小為LISTINCREMENT個(gè)數(shù)據(jù)元素的空間。

2.2 線性表的初始化

根據(jù)線性表結(jié)構(gòu)的基本描述，為完成對(duì)一組數(shù)據(jù)的處理，用戶根據(jù)需要定義線性表供程序使用，則為線性表的初始化。初始化線性表是為線性表分配一個(gè)預(yù)定義的存儲(chǔ)空間，并將線性表的當(dāng)前長度定義為零。分配一個(gè)預(yù)定的存儲(chǔ)空間可以通過調(diào)用C語言的動(dòng)態(tài)分配庫函數(shù)malloc來實(shí)現(xiàn)。具體算法如下：

2.3 線性表某個(gè)元素的插入

從線性表的特點(diǎn)中我們得到一個(gè)結(jié)論，在一個(gè)表中有且僅有唯一的根結(jié)點(diǎn)和終端結(jié)點(diǎn)，除了根結(jié)點(diǎn)和終端結(jié)點(diǎn)，其余結(jié)點(diǎn)都有唯一的前驅(qū)和唯一的后繼，只有滿足這樣的條件才稱為線性表，故此線性表是一個(gè)連續(xù)的有限的存儲(chǔ)空間。我們要在一個(gè)線性表的某個(gè)元素前、后插入一個(gè)元素，其數(shù)據(jù)元素在存儲(chǔ)空間中的位置有所變化，為了不破壞線性表的特征，我們就要采取一定的措施進(jìn)行位置的變化，這就是線性表元素的插入。例如，某一長度為n的線性表，為了在線性表的第i個(gè)和第i+1個(gè)元素之間插入一個(gè)值為x的數(shù)據(jù)元素，則需要從第i個(gè)至第n個(gè)數(shù)據(jù)元素依次往后移動(dòng)一個(gè)位置。一般情況下，所需要移動(dòng)的元素次數(shù)為n-i+1。在具體的移動(dòng)過程中為移出一個(gè)元素，則從尾部向前部依次向后移動(dòng)至第i-1的位置處。具體算法如下：

2.4 線性表中刪除某個(gè)元素

線性表的刪除操作是使長度為n的線性表變成長度為n-1的線性表，數(shù)據(jù)元素之間的邏輯關(guān)系發(fā)生了變化，為了在存儲(chǔ)結(jié)構(gòu)上反映這個(gè)變化，同樣需要移動(dòng)元素。在移動(dòng)過程中，必須將從第i+1個(gè)元素至n個(gè)元素依次前移一位，一般情況下，刪除第i個(gè)元素時(shí)需從第i+1至第n個(gè)元素依次向前移動(dòng)一個(gè)位置。具體算法如下：

3 動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)的應(yīng)用

在日常生活中，我們只要注意觀察，留意我們的生活，我們就不難發(fā)現(xiàn)，其實(shí)很多時(shí)候我們都會(huì)用到線性表的順序存儲(chǔ)結(jié)構(gòu)，例如在學(xué)校對(duì)學(xué)生信息的管理、病人在醫(yī)院掛號(hào)、數(shù)學(xué)集合的合并，其中兩個(gè)線性表的合并操作是線性表處理的典型例子。今天我們以其作為綜合應(yīng)用。具體算法如下：

4 動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)的主函數(shù)

線性表動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)的基本操作共四個(gè)，包括線性表的初始化、插入、刪除、合并。要將這些算法融合為一體成為一個(gè)完整的程序，我們必須從程序的入口點(diǎn)開始執(zhí)行，即主函數(shù)main（）。下面就在主函數(shù)中調(diào)入以上的四個(gè)子程序，使程序結(jié)構(gòu)化、合理化、正確化、實(shí)用化。程序如下：

5 動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)

在數(shù)據(jù)結(jié)構(gòu)中，我們通過時(shí)間復(fù)雜度和空間復(fù)雜度來評(píng)價(jià)一個(gè)算法的好壞，既要考慮程序所占的空間又要考慮程序執(zhí)行的次數(shù)，所占空間越小，執(zhí)行次數(shù)越少，又能得出正確答案，這是每個(gè)程序員所希望的，所以當(dāng)我們?cè)谑褂镁€性表的時(shí)候，我們不需要為表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間，而且可以快速的存取表中任意位置的元素。但是，如果我們要插入或者刪除的元素是在第一個(gè)位置，那么無疑的，我們需要移動(dòng)大量的元素來完成這樣的操作，而且限于線性表長度必須小于數(shù)組長度，如果我們需要插入大量數(shù)據(jù)，那么很難保證空間是否充足，而如果我們要?jiǎng)h除大量數(shù)據(jù)的時(shí)候，無疑又會(huì)造成空間的浪費(fèi)。故順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)為：具有簡單、運(yùn)算方便等優(yōu)點(diǎn)，特別是對(duì)于小線性表或長度固定的線性表，采用順序存儲(chǔ)結(jié)構(gòu)的優(yōu)越性更為突出；缺點(diǎn)為：順序存儲(chǔ)插入與刪除一個(gè)元素，必須移動(dòng)大了的數(shù)據(jù)元素，以此對(duì)大的線性表，特別是在元素的插入和刪除很頻繁的情況下，采取順序存儲(chǔ)很是不方便，效率低；順序存儲(chǔ)空間容易滿，出現(xiàn)上溢，程序訪問容易出問題，順序存儲(chǔ)結(jié)構(gòu)下，存儲(chǔ)空間不便擴(kuò)充；順序存儲(chǔ)空間的分配問題，分多了浪費(fèi)，分少了空間不足上溢。

參考文獻(xiàn)：

[1] 秦玉平，馬靖善.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2005.

[2] 譚浩強(qiáng).C程序設(shè)計(jì)[M].3版.北京：清華大學(xué)出版社，2005.

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