數據結構間縱橫聯系探究論文

導語：數據結構間縱橫聯系探究論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要本文詳細闡述了數據結構間的縱橫聯系，所謂“橫向聯系”是對各種數據結構研究都從邏輯結構、存儲結構、操作運算三方面出發的模式思想，所謂“縱向聯系”是以簡單數據結構類型為基礎來實現對較復雜數據結構類型的研究。

關鍵詞邏輯結構存儲結構操作運算橫向聯系縱向聯系

1引言

數據結構作為計算機核心學科，其主要研究內容：邏輯結構，物理存儲結構，操作（或算法）[1]。通常，算法的設計取決于數據的邏輯結構，算法的實現取決于數據的物理存儲結構。

根據數據元素之間不同特性，把數據結構劃分四種基本結構：（1）集合，（2）線型結構，（3）樹型結構，（4）圖狀結構或網狀結構。針對每種數據結構均從邏輯結構、存儲結構和操作運算等方面進行研究，是貫穿數據結構研究始終的“紅線”，也是數據結構研究的共同切入點，稱之為數據結構的“橫向聯系”。從集合、線型結構等基本數據結構入手，以實現樹形結構、圖或網狀結構等較復雜結構研究，實現數據元素間的關系從簡單到復雜探討，稱之為“縱向聯系”。

2邏輯結構、存儲結構、操作運算的思想模式——數據結構間的橫向聯系

邏輯結構的定義、存儲結構的實現、操作運算的實現是對數據結構研究的基本思想，一種數據結構的研究首先對這三方面內容有一個清晰的探討。

集合數據結構與數學中集合概念是一致的，其邏輯結構元素間只是同屬關系。存儲結構實現只是在計算機內存儲，它的操作就是一些交、差、并、補等。

線型結構是N個數據元素的有限序列，至于每一個數據元素的具體的含義在不同的情況下各不相同，其長度可根據需要增長或縮短，其邏輯結構就是它的數據元素間的線形關系，即一個對一個，一個元素最多有一個前驅，最多有一個后繼。它的存儲結構的實現一般有順序存儲和鏈式存儲兩種方法。順序表是指用一組地址連續的存儲單元依次存儲線性結構中的數據元素，這是一種隨機存取的存儲結構；鏈式存儲是數據元素之間的邏輯關系由結點中的指針來表示并且每一個結點有且只有一個指針域。線性結構的操作中，最基本的操作是在線性結構中插入、刪除數據元素。存儲結構為順序存儲有線性順序表、數組、串等。存儲結構為鏈式存儲結構時有鏈表等。根據線性表的操作的不同便產生了兩種重要的數據結構即棧和隊列，這兩種數據結構是線性結構的典型例子[2]。

樹型結構是一種重要的非線性結構，其中的樹和二叉樹最為常用。直觀看來，樹是以分支關系定義的層次結構，其邏輯結構是一對多的關系，而在二叉樹中是一個根結點對應左右兩個孩子的層次關系。存儲結構的實現當采取順序存儲時用一組地址連續的存儲單元依上而下、自左向右存儲樹中的結點元素。在鏈式存儲結構中可采用二叉鏈表表示法即鏈表中結點的兩個鏈域分別指向該結點的第一個孩子和下一個兄弟結點，樹形結構的最基本的操作是遍歷，其它復雜的操作大部分就是遍歷操作的衍生與擴展。在樹型結構中最有特色的一種數據結構就是二叉樹，其獨特的邏輯結構是每個結點至多有二棵子樹并且還有左右之分，這就決定著它獨特的鏈式存儲結構，每個數據元素有且只有兩個指針分別指向該結點的左右孩子。二叉樹的最基本的操作是遍歷二叉樹，對每個結點的訪問是對其它復雜操作的基礎，例如統計結點個數、統計葉子結點數、交換二叉樹的左右孩子等一些復雜的操作運算均是遍歷二叉樹操作的擴展和衍生。基于二叉樹的遞歸定義可得到遍歷二叉樹遞歸算法，前序遍歷、中序遍歷、后序遍歷二叉樹。

圖狀結構是一種較線型結構和樹更復雜的數據結構，圖的邏輯結構是多對多的關系即在圖形結構中結點之間的關系是任意的。因此在存儲結構中無法以數據元素在存儲區中的物理位置來表示數據元素間的關系。即圖沒有順序映象但可以借助數組的數據類型表示元素之間的關系，用兩個數組分別存儲數據元素（頂點）的信息和數據元素之間的關系信息[3]。另一方面圖的存儲結構也可由多重鏈表實現，即一個由一個數據域和多個指針域組成的結點來表示圖中的一個頂點，其中數據域存儲該頂點的信息，指針域存儲指向鄰接點的指針，但由于圖中各個結點的度各不相同，結點的指針域設定不易確定，則圖的鏈式存儲結構可用鄰接多重表表示法，對圖中每個頂點建立一個單鏈表，第一個單鏈表的結點表示依附于頂點V的邊，每個結點由三個域組成其中鄰接點域指示頂點V的鄰接點在圖中的位置，鏈域指示下一條邊或弧的結點，數據域存儲和邊或弧相關的信息，如權值等。每個鏈表附有一個表頭結點。在表頭結點中除了設有鏈域指向鏈表中第一個結點外還設有存儲頂點的名或其它有關信息的數據域，這樣實現了圖的鏈式存儲。遍歷是最基本的操作也是最重要的操作運算，它是求解圖的連通性、拓撲排序和求關鍵路徑的基礎，然而圖的遍歷比樹的遍歷復雜的多，因為圖的任一頂點都有可能和其余的頂點相鄰接。所以在訪問某個頂點之后可能沿著某條路徑搜索之后又回到該頂點上。因此要設有一個輔助數組V[0..n-1]，它的初始值置為假，一旦訪問頂點Vi，便置V[i]為真，這樣避免了同一個頂點被訪問多次，對圖的遍歷有深度優先搜索和廣度優先搜索。圖的深度優先搜索遍歷類似樹的先根遍歷，是樹的先根遍歷的推廣。廣度優先搜索類似樹的按層次遍歷的過程。圖狀結構中復雜的操作大部分都是以圖的遍歷為基礎。

因此無論對于線型結構、樹性結構、網狀或圖，它們都遵循著邏輯結構的定義、存儲結構的實現、操作運算方法的實現模式來實現每種數據結構的類型。在數據結構研究中對每種數據結構的研究只有對它的這三個方面內容的研究，才能對它進行探索、掌握、改進。這是數據結構研究中的基本思想。在數據結構研究中當前面向各專門領域特殊問題的多維數據結構和從抽象數據類型的觀點來討論數據結構，都不能背離這個思想。

3由棧和隊列實現樹、圖的遍歷——縱向聯系

遍歷操作對樹、圖結構是很基礎、很重要的運算，它是實現一個數據結構的核心部分，雖然根據樹、圖的遞歸定義能設計出樹、圖的遍歷的遞歸算法，但從線型結構到樹、圖的發展也是數據結構從簡單到復雜的逐步發展過程。線型結構中棧和隊列是兩個非常重要的數據結構，對于樹、圖的遍歷可用棧和隊列來實現。對樹、圖復雜的數據結構，可通過棧和隊列的操作來實現復雜數據結構的操作，體現了數據結構間的“縱向聯系”。

用棧實現二叉樹的前序遍歷算法：

Statuspreorder(bitreet)

{P=t;

Initstack(s);

Push(s,p);

While(!stackempty(s)){

pop(s,p)

while(p){

visit(p);

push(s,p→rchild);

p=p-→lchild;}

}}

用棧實現二叉樹的中序遍歷算法：

Statusinorder(bitreet)

{p=t;

Initstack(s);

Push(s,p);

P=P→lchild;

while(!stackempty){

while(p){

push(s,p);

p=p-→lchild;}

pop(s,p);

visist(p);

p=p→rchild;}}

用棧來實現二叉樹的后序遍歷算法：

Statuspostorder(bitreet){

P=t;

inistack(s);

While(p||!stackempty(s)){

If(p){

push(s,p);

P=p→lchild;}

ElseIf(!stackempty(s)){

pre=null;

Gettop(s,p);

While(p→rchild==pre){pop(s,p);

Visit(p);

Pre=p;

Gettop(s,p);}

P=p→rchild;}

}}}

用隊列實現二叉樹層次遍歷算法：

VoidLayers(bitreet){

if(t){

p=t;

Initqueue(q);

Enqueue(q,t);

while(!empty(q)){

p=Dlqueue(q);

visit(p);

if(P→lchild)Enqueue(q,p→lchild);

if(p→rchild)Enqueue(q,p→rchild);}

}

用隊列實現圖的廣度優先搜索算法：

VoidBfs(Graphg,intv){

Visit(v);

Visited[v]=true;

Enqueue(q,v);

While(!emptyqueue(q)){

Dlqueue(g,vex);

For(w=firstadjvex(g,vex),w,w=nextadjvex(g,vex,w)){

If(!visited[w]){visit(w);

Visited[w]=true;

Enqueue(q,w);}}

}}

VoidDfs(Graphg,intv){

Visit(v);

Visited[v]=true;

Push(s,v);

While(!emptystack(s)){V=gettop(s);

For(w=fistadjvex(g,v);w&&!visited[w];w=nextadjvex(g,v,w))

If(!w)pop(s)

Else{visit(w);

Visited[w]=true;

Push(s,w);}}

因為二叉樹、圖的其它的操作大部分是對遍歷基本操作的拓展或綜合應用，靈活運用棧和隊列可實現，并且算法描述比較直觀。線性結構是數據結構學科的基礎，樹、圖的發展在線性結構的基礎上而發展，因樹、圖發展促進著線性結構中和一些算法的完善和改進，線型結構、樹型結構、圖狀結構是緊密相聯的。

4抽象數據類型的研究

數據結構間縱橫聯系明顯且緊密。運用與把握這種“縱橫聯系”，對從抽象數據類型的角度來進行數據結構的學習與研究有著重要的借鑒意義。

抽象數據類型（ADT）的研究越來越被人所重視[4-8]，它可理解為數據類型的進一步抽象。即把數據類型和數據類型上的運算捆在一起，進行封裝。引入抽象數據類型的目的是把數據類型的表示和數據類型上運算的實現與這些數據類型和運算在程序中的引用隔開，使它們相互獨立。對于抽象數據類型的描述，除了必須描述它的數據結構外，還必須描述定義在它上面的運算(過程或函數)。抽象數據類型上定義的過程和函數以該抽象數據類型的數據所應具有的數據結構為基礎。它仍遵循邏輯結構、存儲結構、操作運算的數據結構基本思想，所有的抽象數據類型都可有簡單的分類策略獲得，這個策略就是抽象數據類型對象像什么和對它們做些什么。邏輯結構定義、存儲結構表示、操作的實現在抽象類型中它們被稱為數據類型說明、抽象數據類型的表示和抽象數據類型的實現[3]。抽象數據類型具體的表示和實現依賴所采用的語言,用戶可以用某高級語言的固有數據類型和自定義類型并借助于過程和函數來表示和實現抽象數據類型。

5結論

邏輯結構、存儲結構、操作運算等核心方面是貫穿數據結構研究與發展的一條基本線，也是數據結構研究中所看到數據結構間的“橫向聯系”。應用基本數據結來實現復雜數據結構的方法與途徑，這是對數據元素之間關系從簡單到復雜的探討，即為“縱向聯系”。數據結構聯系是對數據結構的整體把握，體現在這種“橫向聯系”和“縱向聯系”之中。靈活運用與把握這種數據結構間的關系，對抽象數據結構類型的研究有重要的借鑒意義，同時對數據結構的實際教學過程有著一定的指導意義。

參考文獻

[1]陸松年.數據結構教程[M].北京：科學出版社.2002年

[2]嚴蔚敏.數據結構(C語言版)[M].北京：清華大學出版社.1997年

[3]帥訓波.數據結構間普遍整體聯系[D].曲阜：曲阜師范大學計算機科學學院.2003年

[4]藍雯飛.數據結構的面向對象描述方法研究[J].計算機工程與應用，2006;42(26)：79-80

[5]劉毅.關于Treap數據結構問題的研究[J].計算機應用與軟件,2005;22(8):36-38

[6]胡澤明,岳瑞生,王志剛.嵌入式GIS線要素無縫拼接的數據結及實現算法[J].測繪科學,2006;31(5):102-103

[7]戴堅鋒,邵雷兵.一種新型的可擴展分布式數據結構[J].計算機應用研究,2005;22(8):170-171

[8]李先國,梁涌.一種高效的適用于字詞檢索的數據結構[J].微電子學與計算機,2006;23(12):157-160