1、引言
數據結構作為計算機核心學科,其主要研究內容:邏輯結構,物理存儲結構、算法。通常,算法的設計取決于數據的邏輯結構,算法的實現取決于數據的物理存儲結構。
根據數據元素之間的不同特性,把數據結構劃分四種基本結構:集合、線型結構、樹型結構、圖狀結構。針對每種數據結構均從邏輯結構、存儲結構和操作運算等方面進行研究,是數據結構研究的共同切入點,稱為數據結構的“橫向聯系”。從集合、線型結構等基本數據結構入手,以實現樹形結構、圖或網狀結構等較復雜結構研究,實現數據元素間的關系,稱為“縱向聯系”。
2、數據據結構間的徽向聯系.邏輯結構、存儲結構、操作運算的思想棋式
邏輯結構的定義、存儲結構的實現、操作運算的實現是對數據結構研究的基本思想,一種數據結構的研究首先對這三方面內容有一個清晰的探討。
1.集合數據結構與數學中集合概念是一致的,其邏輯結構元素間只是同屬關系。存儲結構實現就是在計算機內如何存儲,它的操作就是一些交、差、并、補等。
2.線型結構是N個數據元素的有限序列,至于每一個數據元素的具體的含義,在不同的情況下各不相同,其長度可根據需要增長或縮短,其邏輯結構就是它的數據元素間的線形關系,即一對一,一個元素最多有一個直接前驅,最多有一個直接后繼。它的存儲結構的實現一般有順序存儲和鏈式存儲兩種方法。順序表是指用一組地址連續的存儲單元依次存儲線性結構中的數據元素,這是一種隨機存取的存儲結構;鏈式存儲是數據元素之間的邏輯關系由結點中的指針來表示并且每一個結點有且只有一個指針域。線性結構的操作中,最基本的操作是在線性結構中插入、刪除數據元素。存儲結構為順序存儲有線性順序表、數組、串等。存儲結構為鏈式存儲結構時有鏈表等。根據線性表的操作的不同便產生了兩種重要的數據結構即棧和隊列,這兩種數據結構是線性結構的典型例子。
3.樹型結構是一種重要的非線性結構,其中的樹和二叉樹最為常用。
樹是以分支關系定義的層次結構,其邏輯結構是一對多的關系,而在三叉樹中是一個根結點對應左右兩個孩子的層次關系。存儲結構的實現當采取順序存儲時用一組地址連續的存儲單元依上而下、自左向右存儲樹中的結點元素。在鏈式存儲結構中可采用二叉鏈表表示即鏈表中結點的兩個鏈域分別指向該結點的第一個孩子和下一個兄弟結點,樹形結構最基本的操作是遍歷。在樹型結構中最有特色的一種數據結構就是二叉樹,二叉樹的最基本的操作是遍歷二叉樹,對每個結點的訪問是對其它復雜操作的基礎。基于二叉樹的遞歸定義可得到遍歷二叉樹遞歸算法,前序遍歷、中序遍歷、后序遍歷二叉樹。
4.圖狀結構是一種較線型結構和樹更復雜的數據結構,圖的邏輯結構是多對多的關系即在圖形結構中結點之間的關系是任意的。因此在存儲結構中無法以數據元素在存儲區中的物理位置來表示數據元素間的關系。即圖沒有順序映象但可以借助數組的數據類型表示元素之間的關系,用兩個數組分別存儲數據元素(頂點)的信息和數據元素之間的關系信息。另一方面圖的存儲結構也可由多重鏈表實現,即一個由一個數據域和多個指針域組成的結點來表示圖中的一個頂點,其中數據域存儲該頂點的信息,指針域存儲指向鄰接點的指針,但由于圖中各個結點的度各不相同,結點的指針域設定不易確定,則圖的鏈式存儲結構可用鄰接多重表表示法,對圖中每個頂點建立一個單鏈表,第一個單鏈表的結點表示依附于頂點V的邊,每個結點由三個域組成,其中鄰接點域指示頂點V的鄰接點在圖中的位置,鏈域指示下一條邊或弧的結點,數據域存儲和邊或弧相關的信息,如權值等。每個鏈表附有一個表頭結點。在表頭結點中除了設有鏈域指向鏈表中第一個結點外還設有存儲頂點的名或其它有關信息的數據域,這樣實現了圖的鏈式存儲。遍歷是最基本的操作也是最重要的操作運算,它是求解圖的連通性、拓撲排序和求關鍵路徑的基礎,然而圖的遍歷比樹的遍歷復雜的多,因為圖的任一頂點都有可能和其余的頂點相鄰接。所以在訪問某個頂點之后可能沿著某條路徑搜索之后又回到該頂點上。因此要設有一個輔助數組V[0.. n-1],它的初始值置為假,一旦訪問頂點Vi,便置V[i」為真,這樣避免了同一個頂點被訪問多次,對圖的遍歷有深度優先搜索和廣度優先搜索。圖的深度優先搜索遍歷類似樹的先根遍歷,是樹的先根遍歷的推廣,廣度優先搜索類似樹的按層次遍歷的過程。
因此無論對于線型結構、樹性結構、圖結構,它們都遵循著邏輯結構的定義、存儲結構的實現、操作運算方法的實現模式來實現每種數據結構的類型。在數據結構中對每種數據結構的研究只有對它的這三個方面內容的研究,才能對它進行探索、掌握、改進。
3、縱向聯系是由錢和隊列實現樹、圖的遍歷
遍歷操作對樹、圖結構是最基礎、最重要的運算,它是實現一個數據結構的核心部分。雖然根據樹、圖的遞歸定義能設計出樹、圖的遍歷的遞歸算法,但從線型結構到樹、圖的發展也是數據結構從簡單到復雜的逐步發展過程。線型結構中棧和隊列是兩個非常重要的數據結構,對于樹、圖的遍歷可用棧和隊列來實現,體現了數據結構間的“縱向聯系”,例如:用棧實現二叉樹的前序遍歷算法:
因為二叉樹、圖的其它的操作大部分是對遍歷基本操作的拓展或綜合應用,靈活運用棧和隊列可實現,并且算法描述比較直觀。線性結構是數據結構學科的基礎,樹、圖的是在線性結構的基礎上發展,因此樹、圖發展促進著線性結構中和一些算法的完善和改進,線型結構、樹型結構、圖狀結構是緊密相聯的。
結語
邏輯結構、存儲結構、操作運算等核心方面是貫穿數據結構研究與發展的一條基本線,也是數據結構研究中所看到數據結構間的“橫向聯系”,應用基本數據結來實現復雜數據結構的方法與途徑,這是對數據元素之間關系從簡單到復雜的探討,即為“縱向聯系”。數據結構聯系是對數據結構的整體把握,體現在這種“橫向聯系”和“縱向聯系”之中。靈活運用與把握這種數據結構間的關系,對抽象數據結構類型的研究有重要的借鑒意義,同時對數據結構的實際教學過程有著一定的指導意義。
核心關注:拓步ERP系統平臺是覆蓋了眾多的業務領域、行業應用,蘊涵了豐富的ERP管理思想,集成了ERP軟件業務管理理念,功能涉及供應鏈、成本、制造、CRM、HR等眾多業務領域的管理,全面涵蓋了企業關注ERP管理系統的核心領域,是眾多中小企業信息化建設首選的ERP管理軟件信賴品牌。
轉載請注明出處:拓步ERP資訊網http://www.guhuozai8.cn/
本文標題:數據結構間的橫向和縱向聯系