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

導(dǎo)語(yǔ)：數(shù)據(jù)結(jié)構(gòu)間縱橫聯(lián)系探究論文一文來(lái)源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要本文詳細(xì)闡述了數(shù)據(jù)結(jié)構(gòu)間的縱橫聯(lián)系，所謂“橫向聯(lián)系”是對(duì)各種數(shù)據(jù)結(jié)構(gòu)研究都從邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、操作運(yùn)算三方面出發(fā)的模式思想，所謂“縱向聯(lián)系”是以簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)類型為基礎(chǔ)來(lái)實(shí)現(xiàn)對(duì)較復(fù)雜數(shù)據(jù)結(jié)構(gòu)類型的研究。

關(guān)鍵詞邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)操作運(yùn)算橫向聯(lián)系縱向聯(lián)系

1引言

數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)核心學(xué)科，其主要研究?jī)?nèi)容：邏輯結(jié)構(gòu)，物理存儲(chǔ)結(jié)構(gòu)，操作（或算法）[1]。通常，算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)。

根據(jù)數(shù)據(jù)元素之間不同特性，把數(shù)據(jù)結(jié)構(gòu)劃分四種基本結(jié)構(gòu)：（1）集合，（2）線型結(jié)構(gòu)，（3）樹型結(jié)構(gòu)，（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。針對(duì)每種數(shù)據(jù)結(jié)構(gòu)均從邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作運(yùn)算等方面進(jìn)行研究，是貫穿數(shù)據(jù)結(jié)構(gòu)研究始終的“紅線”，也是數(shù)據(jù)結(jié)構(gòu)研究的共同切入點(diǎn)，稱之為數(shù)據(jù)結(jié)構(gòu)的“橫向聯(lián)系”。從集合、線型結(jié)構(gòu)等基本數(shù)據(jù)結(jié)構(gòu)入手，以實(shí)現(xiàn)樹形結(jié)構(gòu)、圖或網(wǎng)狀結(jié)構(gòu)等較復(fù)雜結(jié)構(gòu)研究，實(shí)現(xiàn)數(shù)據(jù)元素間的關(guān)系從簡(jiǎn)單到復(fù)雜探討，稱之為“縱向聯(lián)系”。

2邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、操作運(yùn)算的思想模式——數(shù)據(jù)結(jié)構(gòu)間的橫向聯(lián)系

邏輯結(jié)構(gòu)的定義、存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)、操作運(yùn)算的實(shí)現(xiàn)是對(duì)數(shù)據(jù)結(jié)構(gòu)研究的基本思想，一種數(shù)據(jù)結(jié)構(gòu)的研究首先對(duì)這三方面內(nèi)容有一個(gè)清晰的探討。

集合數(shù)據(jù)結(jié)構(gòu)與數(shù)學(xué)中集合概念是一致的，其邏輯結(jié)構(gòu)元素間只是同屬關(guān)系。存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)只是在計(jì)算機(jī)內(nèi)存儲(chǔ)，它的操作就是一些交、差、并、補(bǔ)等。

線型結(jié)構(gòu)是N個(gè)數(shù)據(jù)元素的有限序列，至于每一個(gè)數(shù)據(jù)元素的具體的含義在不同的情況下各不相同，其長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短，其邏輯結(jié)構(gòu)就是它的數(shù)據(jù)元素間的線形關(guān)系，即一個(gè)對(duì)一個(gè)，一個(gè)元素最多有一個(gè)前驅(qū)，最多有一個(gè)后繼。它的存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)一般有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種方法。順序表是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性結(jié)構(gòu)中的數(shù)據(jù)元素，這是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)；鏈?zhǔn)酱鎯?chǔ)是數(shù)據(jù)元素之間的邏輯關(guān)系由結(jié)點(diǎn)中的指針來(lái)表示并且每一個(gè)結(jié)點(diǎn)有且只有一個(gè)指針域。線性結(jié)構(gòu)的操作中，最基本的操作是在線性結(jié)構(gòu)中插入、刪除數(shù)據(jù)元素。存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)有線性順序表、數(shù)組、串等。存儲(chǔ)結(jié)構(gòu)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)有鏈表等。根據(jù)線性表的操作的不同便產(chǎn)生了兩種重要的數(shù)據(jù)結(jié)構(gòu)即棧和隊(duì)列，這兩種數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)的典型例子[2]。

樹型結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)，其中的樹和二叉樹最為常用。直觀看來(lái)，樹是以分支關(guān)系定義的層次結(jié)構(gòu)，其邏輯結(jié)構(gòu)是一對(duì)多的關(guān)系，而在二叉樹中是一個(gè)根結(jié)點(diǎn)對(duì)應(yīng)左右兩個(gè)孩子的層次關(guān)系。存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)當(dāng)采取順序存儲(chǔ)時(shí)用一組地址連續(xù)的存儲(chǔ)單元依上而下、自左向右存儲(chǔ)樹中的結(jié)點(diǎn)元素。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中可采用二叉鏈表表示法即鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子和下一個(gè)兄弟結(jié)點(diǎn)，樹形結(jié)構(gòu)的最基本的操作是遍歷，其它復(fù)雜的操作大部分就是遍歷操作的衍生與擴(kuò)展。在樹型結(jié)構(gòu)中最有特色的一種數(shù)據(jù)結(jié)構(gòu)就是二叉樹，其獨(dú)特的邏輯結(jié)構(gòu)是每個(gè)結(jié)點(diǎn)至多有二棵子樹并且還有左右之分，這就決定著它獨(dú)特的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素有且只有兩個(gè)指針分別指向該結(jié)點(diǎn)的左右孩子。二叉樹的最基本的操作是遍歷二叉樹，對(duì)每個(gè)結(jié)點(diǎn)的訪問是對(duì)其它復(fù)雜操作的基礎(chǔ)，例如統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)、統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)、交換二叉樹的左右孩子等一些復(fù)雜的操作運(yùn)算均是遍歷二叉樹操作的擴(kuò)展和衍生。基于二叉樹的遞歸定義可得到遍歷二叉樹遞歸算法，前序遍歷、中序遍歷、后序遍歷二叉樹。

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

因此無(wú)論對(duì)于線型結(jié)構(gòu)、樹性結(jié)構(gòu)、網(wǎng)狀或圖，它們都遵循著邏輯結(jié)構(gòu)的定義、存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)、操作運(yùn)算方法的實(shí)現(xiàn)模式來(lái)實(shí)現(xiàn)每種數(shù)據(jù)結(jié)構(gòu)的類型。在數(shù)據(jù)結(jié)構(gòu)研究中對(duì)每種數(shù)據(jù)結(jié)構(gòu)的研究只有對(duì)它的這三個(gè)方面內(nèi)容的研究，才能對(duì)它進(jìn)行探索、掌握、改進(jìn)。這是數(shù)據(jù)結(jié)構(gòu)研究中的基本思想。在數(shù)據(jù)結(jié)構(gòu)研究中當(dāng)前面向各專門領(lǐng)域特殊問題的多維數(shù)據(jù)結(jié)構(gòu)和從抽象數(shù)據(jù)類型的觀點(diǎn)來(lái)討論數(shù)據(jù)結(jié)構(gòu)，都不能背離這個(gè)思想。

3由棧和隊(duì)列實(shí)現(xiàn)樹、圖的遍歷——縱向聯(lián)系

遍歷操作對(duì)樹、圖結(jié)構(gòu)是很基礎(chǔ)、很重要的運(yùn)算，它是實(shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu)的核心部分，雖然根據(jù)樹、圖的遞歸定義能設(shè)計(jì)出樹、圖的遍歷的遞歸算法，但從線型結(jié)構(gòu)到樹、圖的發(fā)展也是數(shù)據(jù)結(jié)構(gòu)從簡(jiǎn)單到復(fù)雜的逐步發(fā)展過程。線型結(jié)構(gòu)中棧和隊(duì)列是兩個(gè)非常重要的數(shù)據(jù)結(jié)構(gòu)，對(duì)于樹、圖的遍歷可用棧和隊(duì)列來(lái)實(shí)現(xiàn)。對(duì)樹、圖復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，可通過棧和隊(duì)列的操作來(lái)實(shí)現(xiàn)復(fù)雜數(shù)據(jù)結(jié)構(gòu)的操作，體現(xiàn)了數(shù)據(jù)結(jié)構(gòu)間的“縱向聯(lián)系”。

用棧實(shí)現(xiàn)二叉樹的前序遍歷算法：

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;}

}}

用棧實(shí)現(xiàn)二叉樹的中序遍歷算法：

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;}}

用棧來(lái)實(shí)現(xiàn)二叉樹的后序遍歷算法：

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;}

}}}

用隊(duì)列實(shí)現(xiàn)二叉樹層次遍歷算法：

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);}

}

用隊(duì)列實(shí)現(xiàn)圖的廣度優(yōu)先搜索算法：

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);}}

因?yàn)槎鏄洹D的其它的操作大部分是對(duì)遍歷基本操作的拓展或綜合應(yīng)用，靈活運(yùn)用棧和隊(duì)列可實(shí)現(xiàn)，并且算法描述比較直觀。線性結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)學(xué)科的基礎(chǔ)，樹、圖的發(fā)展在線性結(jié)構(gòu)的基礎(chǔ)上而發(fā)展，因樹、圖發(fā)展促進(jìn)著線性結(jié)構(gòu)中和一些算法的完善和改進(jìn)，線型結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)是緊密相聯(lián)的。

4抽象數(shù)據(jù)類型的研究

數(shù)據(jù)結(jié)構(gòu)間縱橫聯(lián)系明顯且緊密。運(yùn)用與把握這種“縱橫聯(lián)系”，對(duì)從抽象數(shù)據(jù)類型的角度來(lái)進(jìn)行數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)與研究有著重要的借鑒意義。

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

5結(jié)論

邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、操作運(yùn)算等核心方面是貫穿數(shù)據(jù)結(jié)構(gòu)研究與發(fā)展的一條基本線，也是數(shù)據(jù)結(jié)構(gòu)研究中所看到數(shù)據(jù)結(jié)構(gòu)間的“橫向聯(lián)系”。應(yīng)用基本數(shù)據(jù)結(jié)來(lái)實(shí)現(xiàn)復(fù)雜數(shù)據(jù)結(jié)構(gòu)的方法與途徑，這是對(duì)數(shù)據(jù)元素之間關(guān)系從簡(jiǎn)單到復(fù)雜的探討，即為“縱向聯(lián)系”。數(shù)據(jù)結(jié)構(gòu)聯(lián)系是對(duì)數(shù)據(jù)結(jié)構(gòu)的整體把握，體現(xiàn)在這種“橫向聯(lián)系”和“縱向聯(lián)系”之中。靈活運(yùn)用與把握這種數(shù)據(jù)結(jié)構(gòu)間的關(guān)系，對(duì)抽象數(shù)據(jù)結(jié)構(gòu)類型的研究有重要的借鑒意義，同時(shí)對(duì)數(shù)據(jù)結(jié)構(gòu)的實(shí)際教學(xué)過程有著一定的指導(dǎo)意義。

參考文獻(xiàn)

[1]陸松年.數(shù)據(jù)結(jié)構(gòu)教程[M].北京：科學(xué)出版社.2002年

[2]嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M].北京：清華大學(xué)出版社.1997年

[3]帥訓(xùn)波.數(shù)據(jù)結(jié)構(gòu)間普遍整體聯(lián)系[D].曲阜：曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院.2003年

[4]藍(lán)雯飛.數(shù)據(jù)結(jié)構(gòu)的面向?qū)ο竺枋龇椒ㄑ芯縖J].計(jì)算機(jī)工程與應(yīng)用，2006;42(26)：79-80

[5]劉毅.關(guān)于Treap數(shù)據(jù)結(jié)構(gòu)問題的研究[J].計(jì)算機(jī)應(yīng)用與軟件,2005;22(8):36-38

[6]胡澤明,岳瑞生,王志剛.嵌入式GIS線要素?zé)o縫拼接的數(shù)據(jù)結(jié)及實(shí)現(xiàn)算法[J].測(cè)繪科學(xué),2006;31(5):102-103

[7]戴堅(jiān)鋒,邵雷兵.一種新型的可擴(kuò)展分布式數(shù)據(jù)結(jié)構(gòu)[J].計(jì)算機(jī)應(yīng)用研究,2005;22(8):170-171

[8]李先國(guó),梁涌.一種高效的適用于字詞檢索的數(shù)據(jù)結(jié)構(gòu)[J].微電子學(xué)與計(jì)算機(jī),2006;23(12):157-160