摘 要本文詳細闡述了數據結構間的縱橫聯繫，所謂「橫向聯繫」是對各種數據結構研究都從邏輯結構、存儲結構、操作運算三方面出發的模式思想，所謂「縱向聯繫」是以簡單數據結構類型為基礎來實現對較複雜數據結構類型的研究。
關鍵詞邏輯結構 存儲結構 操作運算 橫向聯繫 縱向聯繫
1 引言
數據結構作為計算機核心學科，其主要研究內容：邏輯結構，物理存儲結構，操作（或算法）[1]。通常，算法的設計取決於數據的邏輯結構，算法的實現取決於數據的物理存儲結構。
根據數據元素之間不同特性，把數據結構劃分四種基本結構：（1）集合，（2）線型結構，（3）樹型結構，（4）圖狀結構或網狀結構。針對每種數據結構均從邏輯結構、存儲結構和操作運算等方面進行研究，是貫穿數據結構研究始終的 「紅線」，也是數據結構研究的共同切入點，稱之為數據結構的「橫向聯繫」。從集合、線型結構等基本數據結構入手，以實現樹形結構、圖或網狀結構等較複雜結構研究，實現數據元素間的關係從簡單到複雜探討，稱之為「縱向聯繫」。
2 邏輯結構、存儲結構、操作運算的思想模式——數據結構間的橫向聯繫
邏輯結構的定義、存儲結構的實現、操作運算的實現是對數據結構研究的基本思想，一種數據結構的研究首先對這三方面內容有一個清晰的探討。
集合數據結構與數學中集合概念是一致的，其邏輯結構元素間只是同屬關係。存儲結構實現只是在計算機內存儲，它的操作就是一些交、差、並、補等。
線型結構是N個數據元素的有限序列，至於每一個數據元素的具體的含義在不同的情況下各不相同，其長度可根據需要增長或縮短，其邏輯結構就是它的數據元素間的線形關係，即一個對一個，一個元素最多有一個前驅，最多有一個後繼。它的存儲結構的實現一般有順序存儲和鏈式存儲兩種方法。順序表是指用一組地址連續的存儲單元依次存儲線性結構中的數據元素，這是一種隨機存取的存儲結構；鏈式存儲是數據元素之間的邏輯關係由結點中的指針來表示並且每一個結點有且只有一個指針域。線性結構的操作中，最基本的操作是在線性結構中插入、刪除數據元素。存儲結構為順序存儲有線性順序表、數組、串等。存儲結構為鏈式存儲結構時有鍊表等。根據線性表的操作的不同便產生了兩種重要的數據結構即棧和隊列，這兩種數據結構是線性結構的典型例子[2]。
樹型結構是一種重要的非線性結構，其中的樹和二叉樹最為常用。直觀看來，樹是以分支關係定義的層次結構，其邏輯結構是一對多的關係，而在二叉樹中是一個根結點對應左右兩個孩子的層次關係。存儲結構的實現當採取順序存儲時用一組地址連續的存儲單元依上而下、自左向右存儲樹中的結點元素。在鏈式存儲結構中可採用二叉鍊表表示法即鍊表中結點的兩個鏈域分別指向該結點的第一個孩子和下一個兄弟結點，樹形結構的最基本的操作是遍歷，其它複雜的操作大部分就是遍歷操作的衍生與擴展。在樹型結構中最有特色的一種數據結構就是二叉樹，其獨特的邏輯結構是每個結點至多有二棵子樹並且還有左右之分，這就決定著它獨特的鏈式存儲結構，每個數據元素有且只有兩個指針分別指向該結點的左右孩子。二叉樹的最基本的操作是遍歷二叉樹，對每個結點的訪問是對其它複雜操作的基礎，例如統計結點個數、統計葉子結點數、交換二叉樹的左右孩子等一些複雜的操作運算均是遍歷二叉樹操作的擴展和衍生。基於二叉樹的遞歸定義可得到遍歷二叉樹遞歸算法，前序遍歷、中序遍歷、後序遍歷二叉樹。
圖狀結構是一種較線型結構和樹更複雜的數據結構，圖的邏輯結構是多對多的關係即在圖形結構中結點之間的關係是任意的。因此在存儲結構中無法以數據元素在存儲區中的物理位置來表示數據元素間的關係。即圖沒有順序映象但可以藉助數組的數據類型表示元素之間的關係，用兩個數組分別存儲數據元素（頂點）的信息和數據元素之間的關係信息[3]。另一方面圖的存儲結構也可由多重鍊表實現，即一個由一個數據域和多個指針域組成的結點來表示圖中的一個頂點，其中數據域存儲該頂點的信息，指針域存儲指向鄰接點的指針，但由於圖中各個結點的度各不相同，結點的指針域設定不易確定，則圖的鏈式存儲結構可用鄰接多重表表示法，對圖中每個頂點建立一個單鍊表，第一個單鍊表的結點表示依附於頂點V的邊，每個結點由三個域組成其中鄰接點域指示頂點V的鄰接點在圖中的位置，鏈域指示下一條邊或弧的結點，數據域存儲和邊或弧相關的信息，如權值等。每個鍊表附有一個表頭結點。在表頭結點中除了設有鏈域指向鍊表中第一個結點外還設有存儲頂點的名或其它有關信息的數據域，這樣實現了圖的鏈式存儲。遍歷是最基本的操作也是最重要的操作運算，它是求解圖的連通性、拓撲排序和求關鍵路徑的基礎，然而圖的遍歷比樹的遍歷複雜的多，因為圖的任一頂點都有可能和其餘的頂點相鄰接。所以在訪問某個頂點之後可能沿著某條路徑搜索之後又回到該頂點上。因此要設有一個輔助數組V[0..n-1]，它的初始值置為假，一旦訪問頂點Vi，便置V[i]為真，這樣避免了同一個頂點被訪問多次，對圖的遍歷有深度優先搜索和廣度優先搜索。圖的深度優先搜索遍歷類似樹的先根遍歷，是樹的先根遍歷的推廣。廣度優先搜索類似樹的按層次遍歷的過程。圖狀結構中複雜的操作大部分都是以圖的遍歷為基礎。
因此無論對於線型結構、樹性結構、網狀或圖，它們都遵循著邏輯結構的定義、存儲結構的實現、操作運算方法的實現模式來實現每種數據結構的類型。在數據結構研究中對每種數據結構的研究只有對它的這三個方面內容的研究，才能對它進行探索、掌握、改進。這是數據結構研究中的基本思想。在數據結構研究中當前面向各專門領域特殊問題的多維數據結構和從抽象數據類型的觀點來討論數據結構，都不能背離這個思想。
3 由棧和隊列實現樹、圖的遍歷——縱向聯繫
遍歷操作對樹、圖結構是很基礎、很重要的運算 ，它是實現一個數據結構的核心部分，雖然根據樹、圖的遞歸定義能設計出樹、圖的遍歷的遞歸算法，但從線型結構到樹、圖的發展也是數據結構從簡單到複雜的逐步發展過程。線型結構中棧和隊列是兩個非常重要的數據結構，對於樹、圖的遍歷可用棧和隊列來實現。對樹、圖複雜的數據結構，可通過棧和隊列的操作來實現複雜數據結構的操作，體現了數據結構間的「縱向聯繫」。
用棧實現二叉樹的前序遍歷算法：
Status preorder (bitree t )
{ P=t;
Initstack(s);
Push(s,p);
While(!stackempty (s)){
pop(s,p)
while(p){
visit(p);
push(s,p→rchild);
p=p- →lchild; }
} }
用棧實現二叉樹的中序遍歷算法：
Status inorder (bitree t )
{p=t;
Initstack(s);
Push(s,p);
P=P→lchild;
while(!stackempty){
轉貼於論文聯盟 http://www.lwlm.com
關鍵詞邏輯結構 存儲結構 操作運算 橫向聯繫 縱向聯繫
1 引言
數據結構作為計算機核心學科，其主要研究內容：邏輯結構，物理存儲結構，操作（或算法）[1]。通常，算法的設計取決於數據的邏輯結構，算法的實現取決於數據的物理存儲結構。
根據數據元素之間不同特性，把數據結構劃分四種基本結構：（1）集合，（2）線型結構，（3）樹型結構，（4）圖狀結構或網狀結構。針對每種數據結構均從邏輯結構、存儲結構和操作運算等方面進行研究，是貫穿數據結構研究始終的 「紅線」，也是數據結構研究的共同切入點，稱之為數據結構的「橫向聯繫」。從集合、線型結構等基本數據結構入手，以實現樹形結構、圖或網狀結構等較複雜結構研究，實現數據元素間的關係從簡單到複雜探討，稱之為「縱向聯繫」。
2 邏輯結構、存儲結構、操作運算的思想模式——數據結構間的橫向聯繫
邏輯結構的定義、存儲結構的實現、操作運算的實現是對數據結構研究的基本思想，一種數據結構的研究首先對這三方面內容有一個清晰的探討。
集合數據結構與數學中集合概念是一致的，其邏輯結構元素間只是同屬關係。存儲結構實現只是在計算機內存儲，它的操作就是一些交、差、並、補等。
線型結構是N個數據元素的有限序列，至於每一個數據元素的具體的含義在不同的情況下各不相同，其長度可根據需要增長或縮短，其邏輯結構就是它的數據元素間的線形關係，即一個對一個，一個元素最多有一個前驅，最多有一個後繼。它的存儲結構的實現一般有順序存儲和鏈式存儲兩種方法。順序表是指用一組地址連續的存儲單元依次存儲線性結構中的數據元素，這是一種隨機存取的存儲結構；鏈式存儲是數據元素之間的邏輯關係由結點中的指針來表示並且每一個結點有且只有一個指針域。線性結構的操作中，最基本的操作是在線性結構中插入、刪除數據元素。存儲結構為順序存儲有線性順序表、數組、串等。存儲結構為鏈式存儲結構時有鍊表等。根據線性表的操作的不同便產生了兩種重要的數據結構即棧和隊列，這兩種數據結構是線性結構的典型例子[2]。
樹型結構是一種重要的非線性結構，其中的樹和二叉樹最為常用。直觀看來，樹是以分支關係定義的層次結構，其邏輯結構是一對多的關係，而在二叉樹中是一個根結點對應左右兩個孩子的層次關係。存儲結構的實現當採取順序存儲時用一組地址連續的存儲單元依上而下、自左向右存儲樹中的結點元素。在鏈式存儲結構中可採用二叉鍊表表示法即鍊表中結點的兩個鏈域分別指向該結點的第一個孩子和下一個兄弟結點，樹形結構的最基本的操作是遍歷，其它複雜的操作大部分就是遍歷操作的衍生與擴展。在樹型結構中最有特色的一種數據結構就是二叉樹，其獨特的邏輯結構是每個結點至多有二棵子樹並且還有左右之分，這就決定著它獨特的鏈式存儲結構，每個數據元素有且只有兩個指針分別指向該結點的左右孩子。二叉樹的最基本的操作是遍歷二叉樹，對每個結點的訪問是對其它複雜操作的基礎，例如統計結點個數、統計葉子結點數、交換二叉樹的左右孩子等一些複雜的操作運算均是遍歷二叉樹操作的擴展和衍生。基於二叉樹的遞歸定義可得到遍歷二叉樹遞歸算法，前序遍歷、中序遍歷、後序遍歷二叉樹。
圖狀結構是一種較線型結構和樹更複雜的數據結構，圖的邏輯結構是多對多的關係即在圖形結構中結點之間的關係是任意的。因此在存儲結構中無法以數據元素在存儲區中的物理位置來表示數據元素間的關係。即圖沒有順序映象但可以藉助數組的數據類型表示元素之間的關係，用兩個數組分別存儲數據元素（頂點）的信息和數據元素之間的關係信息[3]。另一方面圖的存儲結構也可由多重鍊表實現，即一個由一個數據域和多個指針域組成的結點來表示圖中的一個頂點，其中數據域存儲該頂點的信息，指針域存儲指向鄰接點的指針，但由於圖中各個結點的度各不相同，結點的指針域設定不易確定，則圖的鏈式存儲結構可用鄰接多重表表示法，對圖中每個頂點建立一個單鍊表，第一個單鍊表的結點表示依附於頂點V的邊，每個結點由三個域組成其中鄰接點域指示頂點V的鄰接點在圖中的位置，鏈域指示下一條邊或弧的結點，數據域存儲和邊或弧相關的信息，如權值等。每個鍊表附有一個表頭結點。在表頭結點中除了設有鏈域指向鍊表中第一個結點外還設有存儲頂點的名或其它有關信息的數據域，這樣實現了圖的鏈式存儲。遍歷是最基本的操作也是最重要的操作運算，它是求解圖的連通性、拓撲排序和求關鍵路徑的基礎，然而圖的遍歷比樹的遍歷複雜的多，因為圖的任一頂點都有可能和其餘的頂點相鄰接。所以在訪問某個頂點之後可能沿著某條路徑搜索之後又回到該頂點上。因此要設有一個輔助數組V[0..n-1]，它的初始值置為假，一旦訪問頂點Vi，便置V[i]為真，這樣避免了同一個頂點被訪問多次，對圖的遍歷有深度優先搜索和廣度優先搜索。圖的深度優先搜索遍歷類似樹的先根遍歷，是樹的先根遍歷的推廣。廣度優先搜索類似樹的按層次遍歷的過程。圖狀結構中複雜的操作大部分都是以圖的遍歷為基礎。
因此無論對於線型結構、樹性結構、網狀或圖，它們都遵循著邏輯結構的定義、存儲結構的實現、操作運算方法的實現模式來實現每種數據結構的類型。在數據結構研究中對每種數據結構的研究只有對它的這三個方面內容的研究，才能對它進行探索、掌握、改進。這是數據結構研究中的基本思想。在數據結構研究中當前面向各專門領域特殊問題的多維數據結構和從抽象數據類型的觀點來討論數據結構，都不能背離這個思想。
3 由棧和隊列實現樹、圖的遍歷——縱向聯繫
遍歷操作對樹、圖結構是很基礎、很重要的運算 ，它是實現一個數據結構的核心部分，雖然根據樹、圖的遞歸定義能設計出樹、圖的遍歷的遞歸算法，但從線型結構到樹、圖的發展也是數據結構從簡單到複雜的逐步發展過程。線型結構中棧和隊列是兩個非常重要的數據結構，對於樹、圖的遍歷可用棧和隊列來實現。對樹、圖複雜的數據結構，可通過棧和隊列的操作來實現複雜數據結構的操作，體現了數據結構間的「縱向聯繫」。
用棧實現二叉樹的前序遍歷算法：
Status preorder (bitree t )
{ P=t;
Initstack(s);
Push(s,p);
While(!stackempty (s)){
pop(s,p)
while(p){
visit(p);
push(s,p→rchild);
p=p- →lchild; }
} }
用棧實現二叉樹的中序遍歷算法：
Status inorder (bitree t )
{p=t;
Initstack(s);
Push(s,p);
P=P→lchild;
while(!stackempty){
轉貼於論文聯盟 http://www.lwlm.com
收藏