數(shù)據(jù)結構間縱橫聯(lián)系探究論文

數(shù)據(jù)結構間縱橫聯(lián)系探究論文1引言數(shù)據(jù)結構作為計算機核心學科，其主要研究內容：邏輯結構，物理存儲結構，操作（或算法）[1]。通常，算法的設計取決于數(shù)據(jù)的邏輯結構，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結構。邏輯結構的定義、存儲結構的實現(xiàn)、操作運算的實現(xiàn)是對數(shù)據(jù)結構研究的基本思想，一種數(shù)據(jù)結構的研究首先對這三方面內容有一個清晰的探討。集合數(shù)據(jù)結構與數(shù)學中集合概念是一致的，其邏輯結構元素間只是同屬關系。存儲結構實現(xiàn)只是在計算機內存儲，它的操作就是一些交、差、并、補等。線型結構是N個數(shù)據(jù)元素的有限序列，至于每一個數(shù)據(jù)元素的具體的含義在不同的情況下各不相同，其長度可根據(jù)需要增長或縮短，其邏輯結構就是它的數(shù)據(jù)元素間的線形關系，即一個對一個，一個元素最多有一個前驅，最多有一個后繼。它的存儲結構的實現(xiàn)一般有順序存儲和鏈式存儲兩種方法。順序表是指用一組地址連續(xù)的存儲單元依次存儲線性結構中的數(shù)據(jù)元素，這是一種隨機存取的存儲結構；鏈式存儲是數(shù)據(jù)元素之間的邏輯關系由結點中的指針來表示并且每一個結點有且只有一個指針域。線性結構的操作中，最基本的操作是在線性結構中插入、刪除數(shù)據(jù)元素。存儲結構為順序存儲有線性順序表、數(shù)組、串等。存儲結構為鏈式存儲結構時有鏈表等。根據(jù)線性表的操作的不同便產生了兩種重要的數(shù)據(jù)結構即棧和隊列，這兩種數(shù)據(jù)結構是線性結構的典型例子[2]。樹型結構是一種重要的非線性結構，其中的樹和二叉樹最為常用。直觀看來，樹是以分支關系定義的層次結構，其邏輯結構是一對多的關系，而在二叉樹中是一個根結點對應左右兩個孩子的層次關系。存儲結構的實現(xiàn)當采取順序存儲時用一組地址連續(xù)的存儲單元依上而下、自左向右存儲樹中的結點元素。在鏈式存儲結構中可采用二叉鏈表表示法即鏈表中結點的兩個鏈域分別指向該結點的第一個孩子和下一個兄弟結點，樹形結構的最基本的操作是遍歷，其它復雜的操作大部分就是遍歷操作的衍生與擴展。在樹型結構中最有特色的一種數(shù)據(jù)結構就是二叉樹，其獨特的邏輯結構是每個結點至多有二棵子樹并且還有左右之分，這就決定著它獨特的鏈式存儲結構，每個數(shù)據(jù)元素有且只有兩個指針分別指向該結點的左右孩子。二叉樹的最基本的操作是遍歷二叉樹，對每個結點的訪問是對其它復雜操作的基礎，例如統(tǒng)計結點個數(shù)、統(tǒng)計葉子結點數(shù)、交換二叉樹的左右孩子等一些復雜的操作運算均是遍歷二叉樹操作的擴展和衍生?；诙鏄涞倪f歸定義可得到遍歷二叉樹遞歸算法，前序遍歷、中序遍歷、后序遍歷二叉樹。圖狀結構是一種較線型結構和樹更復雜的數(shù)據(jù)結構，圖的邏輯結構是多對多的關系即在圖形結構中結點之間的關系是任意的。因此在存儲結構中無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示數(shù)據(jù)元素間的關系。即圖沒有順序映象但可以借助數(shù)組的數(shù)據(jù)類型表示元素之間的關系，用兩個數(shù)組分別存儲數(shù)據(jù)元素（頂點）的信息和數(shù)據(jù)元素之間的關系信息[3]。另一方面圖的存儲結構也可由多重鏈表實現(xiàn)，即一個由一個數(shù)據(jù)域和多個指針域組成的結點來表示圖中的一個頂點，其中數(shù)據(jù)域存儲該頂點的信息，指針域存儲指向鄰接點的指針，但由于圖中各個結點的度各不相同，結點的指針域設定不易確定，則圖的鏈式存儲結構可用鄰接多重表表示法，對圖中每個頂點建立一個單鏈表，第一個單鏈表的結點表示依附于頂點V的邊，每個結點由三個域組成其中鄰接點域指示頂點V的鄰接點在圖中的位置，鏈域指示下一條邊或弧的結點，數(shù)據(jù)域存儲和邊或弧相關的信息，如權值等。每個鏈表附有一個表頭結點。在表頭結點中除了設有鏈域指向鏈表中第一個結點外還設有存儲頂點的名或其它有關信息的數(shù)據(jù)域，這樣實現(xiàn)了圖的鏈式存儲。遍歷是最基本的操作也是最重要的操作運算，它是求解圖的連通性、拓撲排序和求關鍵路徑的基礎，然而圖的遍歷比樹的遍歷復雜的多，因為圖的任一頂點都有可能和其余的頂點相鄰接。所以在訪問某個頂點之后可能沿著某條路徑搜索之后又回到該頂點上。因此要設有一個輔助數(shù)組V[0..n-1]，它的初始值置為假，一旦訪問頂點Vi，便置V[i]為真，這樣避免了同一個頂點被訪問多次，對圖的遍歷有深度優(yōu)先搜索和廣度優(yōu)先搜索。圖的深度優(yōu)先搜索遍歷類似樹的先根遍歷，是樹的先根遍歷的推廣。廣度優(yōu)先搜索類似樹的按層次遍歷的過程。圖狀結構中復雜的操作大部分都是以圖的遍歷為基礎。因此無論對于線型結構、樹性結構、網狀或圖，它們都遵循著邏輯結構的定義、存儲結構的實現(xiàn)、操作運算方法的實現(xiàn)模式來實現(xiàn)每種數(shù)據(jù)結構的類型。在數(shù)據(jù)結構研究中對每種數(shù)據(jù)結構的研究只有對它的這三個方面內容的研究，才能對它進行探索、掌握、改進。這是數(shù)據(jù)結構研究中的基本思想。在數(shù)據(jù)結構研究中當前面向各專門領域特殊問題的多維數(shù)據(jù)結構和從抽象數(shù)據(jù)類型的觀點來討論數(shù)據(jù)結構，都不能背離這個思想。用棧實現(xiàn)二叉樹的前序遍歷算法：Statupreorder(bitreet){P=t;Inittack();Puh(,p);].北京：科學出版社.2002年[2]嚴蔚敏.數(shù)據(jù)結構(C語言版)[M].北京：清華大學出版社.1997年[4]藍雯飛.數(shù)據(jù)結構的面向對象描述方法研究[J].計算機工程與應用，2006;42(26)：79-80[5]劉毅.關于Treap數(shù)據(jù)結構問題的研究[J].計算機應用與軟件,2005;22(8):36-38[6]胡澤明,岳瑞生,王志剛.嵌入式GIS線要素無縫拼接的數(shù)據(jù)結及實現(xiàn)算法[J].測繪科學,2006;31(5):102-10