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