線性表的動態(tài)分配存儲結(jié)構(gòu)分析

曹小妹

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

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

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044（2012）30-7216-04

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

1 引入線性表動態(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ù)組實現(xiàn)線性表的順序存儲，結(jié)構(gòu)簡單，其算法也容易理解。但是，由于存儲分配只能預(yù)先定義，如果插入的數(shù)據(jù)量超出預(yù)先分配的存儲空間，那么臨時擴大就會存在很大的困難；如果按最大的可能空間進行分配，則勢必降低了存儲空間的利用率。為解決此問題，可以利用C語言動態(tài)分配內(nèi)存的機制，實現(xiàn)線性表的順序存儲。

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

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

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

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

2.2 線性表的初始化

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

2.3 線性表某個元素的插入

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

2.4 線性表中刪除某個元素

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

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

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

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

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

5 動態(tài)分配順序存儲結(jié)構(gòu)的優(yōu)缺點

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

參考文獻：

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

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

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