1、數(shù)據(jù)構(gòu)造間的縱橫聯(lián)絡(luò)摘要本文詳細闡述了數(shù)據(jù)構(gòu)造間的縱橫聯(lián)絡(luò)，所謂“橫向聯(lián)絡(luò)是對各種數(shù)據(jù)構(gòu)造研究都從邏輯構(gòu)造、存儲構(gòu)造、操作運算三方面出發(fā)的形式思想，所謂“縱向聯(lián)絡(luò)是以簡單數(shù)據(jù)構(gòu)造類型為根底來實現(xiàn)對較復(fù)雜數(shù)據(jù)構(gòu)造類型的研究。關(guān)鍵詞邏輯構(gòu)造存儲構(gòu)造操作運算橫向聯(lián)絡(luò)縱向聯(lián)絡(luò)數(shù)據(jù)構(gòu)造作為計算機核心學(xué)科，其主要研究內(nèi)容：邏輯構(gòu)造，物理存儲構(gòu)造，操作或算法1。通常，算法的設(shè)計取決于數(shù)據(jù)的邏輯構(gòu)造，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲構(gòu)造。根據(jù)數(shù)據(jù)元素之間不同特性，把數(shù)據(jù)構(gòu)造劃分四種根本構(gòu)造：1集合，2線型構(gòu)造，3樹型構(gòu)造，4圖狀構(gòu)造或網(wǎng)狀構(gòu)造。針對每種數(shù)據(jù)構(gòu)造均從邏輯構(gòu)造、存儲構(gòu)造和操作運算等方面進展研究，是貫

2、穿數(shù)據(jù)構(gòu)造研究始終的“紅線，也是數(shù)據(jù)構(gòu)造研究的共同切入點，稱之為數(shù)據(jù)構(gòu)造的“橫向聯(lián)絡(luò)。從集合、線型構(gòu)造等根本數(shù)據(jù)構(gòu)造入手，以實現(xiàn)樹形構(gòu)造、圖或網(wǎng)狀構(gòu)造等較復(fù)雜構(gòu)造研究，實現(xiàn)數(shù)據(jù)元素間的關(guān)系從簡單到復(fù)雜討論，稱之為“縱向聯(lián)絡(luò)。邏輯構(gòu)造的定義、存儲構(gòu)造的實現(xiàn)、操作運算的實現(xiàn)是對數(shù)據(jù)構(gòu)造研究的根本思想，一種數(shù)據(jù)構(gòu)造的研究首先對這三方面內(nèi)容有一個明晰的討論。集合數(shù)據(jù)構(gòu)造與數(shù)學(xué)中集合概念是一致的，其邏輯構(gòu)造元素間只是同屬關(guān)系。存儲構(gòu)造實現(xiàn)只是在計算機內(nèi)存儲，它的操作就是一些交、差、并、補等。線型構(gòu)造是N個數(shù)據(jù)元素的有限序列，至于每一個數(shù)據(jù)元素的詳細的含義在不同的情況下各不一樣，其長度可根據(jù)需要增長或縮短

3、，其邏輯構(gòu)造就是它的數(shù)據(jù)元素間的線形關(guān)系，即一個對一個，一個元素最多有一個前驅(qū)，最多有一個后繼。它的存儲構(gòu)造的實現(xiàn)一般有順序存儲和鏈?zhǔn)酱鎯煞N方法。順序表是指用一組地址連續(xù)的存儲單元依次存儲線性構(gòu)造中的數(shù)據(jù)元素，這是一種隨機存取的存儲構(gòu)造；鏈?zhǔn)酱鎯κ菙?shù)據(jù)元素之間的邏輯關(guān)系由結(jié)點中的指針來表示并且每一個結(jié)點有且只有一個指針域。線性構(gòu)造的操作中，最根本的操作是在線性構(gòu)造中插入、刪除數(shù)據(jù)元素。存儲構(gòu)造為順序存儲有線性順序表、數(shù)組、串等。存儲構(gòu)造為鏈?zhǔn)酱鎯?gòu)造時有鏈表等。根據(jù)線性表的操作的不同便產(chǎn)生了兩種重要的數(shù)據(jù)構(gòu)造即棧和隊列，這兩種數(shù)據(jù)構(gòu)造是線性構(gòu)造的典型例子2。樹型構(gòu)造是一種重要的非線性構(gòu)造，其

4、中的樹和二叉樹最為常用。直觀看來，樹是以分支關(guān)系定義的層次構(gòu)造，其邏輯構(gòu)造是一對多的關(guān)系，而在二叉樹中是一個根結(jié)點對應(yīng)左右兩個孩子的層次關(guān)系。存儲構(gòu)造的實現(xiàn)當(dāng)采取順序存儲時用一組地址連續(xù)的存儲單元依上而下、自左向右存儲樹中的結(jié)點元素。在鏈?zhǔn)酱鎯?gòu)造中可采用二叉鏈表表示法即鏈表中結(jié)點的兩個鏈域分別指向該結(jié)點的第一個孩子和下一個兄弟結(jié)點，樹形構(gòu)造的最根本的操作是遍歷，其它復(fù)雜的操作大部分就是遍歷操作的衍生與擴展。在樹型構(gòu)造中最有特色的一種數(shù)據(jù)構(gòu)造就是二叉樹，其獨特的邏輯構(gòu)造是每個結(jié)點至多有二棵子樹并且還有左右之分，這就決定著它獨特的鏈?zhǔn)酱鎯?gòu)造，每個數(shù)據(jù)元素有且只有兩個指針分別指向該結(jié)點的左右孩子

5、。二叉樹的最根本的操作是遍歷二叉樹，對每個結(jié)點的訪問是對其它復(fù)雜操作的根底，例如統(tǒng)計結(jié)點個數(shù)、統(tǒng)計葉子結(jié)點數(shù)、交換二叉樹的左右孩子等一些復(fù)雜的操作運算均是遍歷二叉樹操作的擴展和衍生?；诙鏄涞倪f歸定義可得到遍歷二叉樹遞歸算法，前序遍歷、中序遍歷、后序遍歷二叉樹。圖狀構(gòu)造是一種較線型構(gòu)造和樹更復(fù)雜的數(shù)據(jù)構(gòu)造，圖的邏輯構(gòu)造是多對多的關(guān)系即在圖形構(gòu)造中結(jié)點之間的關(guān)系是任意的。因此在存儲構(gòu)造中無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示數(shù)據(jù)元素間的關(guān)系。即圖沒有順序映象但可以借助數(shù)組的數(shù)據(jù)類型表示元素之間的關(guān)系，用兩個數(shù)組分別存儲數(shù)據(jù)元素頂點的信息和數(shù)據(jù)元素之間的關(guān)系信息3。另一方面圖的存儲構(gòu)造也可由多

6、重鏈表實現(xiàn)，即一個由一個數(shù)據(jù)域和多個指針域組成的結(jié)點來表示圖中的一個頂點，其中數(shù)據(jù)域存儲該頂點的信息，指針域存儲指向鄰接點的指針，但由于圖中各個結(jié)點的度各不一樣，結(jié)點的指針域設(shè)定不易確定，那么圖的鏈?zhǔn)酱鎯?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)酱鎯?。遍歷是最根本的操作也是最重要的

7、操作運算，它是求解圖的連通性、拓撲排序和求關(guān)鍵途徑的根底，然而圖的遍歷比樹的遍歷復(fù)雜的多，因為圖的任一頂點都有可能和其余的頂點相鄰接。所以在訪問某個頂點之后可能沿著某條途徑搜索之后又回到該頂點上。因此要設(shè)有一個輔助數(shù)組V0.n-1，它的初始值置為假，一旦訪問頂點Vi，便置Vi為真，這樣防止了同一個頂點被訪問屢次，對圖的遍歷有深度優(yōu)先搜索和廣度優(yōu)先搜索。圖的深度優(yōu)先搜索遍歷類似樹的先根遍歷，是樹的先根遍歷的推廣。廣度優(yōu)先搜索類似樹的按層次遍歷的過程。圖狀構(gòu)造中復(fù)雜的操作大部分都是以圖的遍歷為基矗因此無論對于線型構(gòu)造、樹性構(gòu)造、網(wǎng)狀或圖，它們都遵循著邏輯構(gòu)造的定義、存儲構(gòu)造的實現(xiàn)、操作運算方法的實

8、現(xiàn)形式來實現(xiàn)每種數(shù)據(jù)構(gòu)造的類型。在數(shù)據(jù)構(gòu)造研究中對每種數(shù)據(jù)構(gòu)造的研究只有對它的這三個方面內(nèi)容的研究，才能對它進展探究、掌握、改進。這是數(shù)據(jù)構(gòu)造研究中的根本思想。在數(shù)據(jù)構(gòu)造研究中當(dāng)前面向各專門領(lǐng)域特殊問題的多維數(shù)據(jù)構(gòu)造和從抽象數(shù)據(jù)類型的觀點來討論數(shù)據(jù)構(gòu)造，都不能背離這個思想。遍歷操作對樹、圖構(gòu)造是很基儲很重要的運算，它是實現(xiàn)一個數(shù)據(jù)構(gòu)造的核心部分，雖然根據(jù)樹、圖的遞歸定義能設(shè)計出樹、圖的遍歷的遞歸算法，但從線型構(gòu)造到樹、圖的開展也是數(shù)據(jù)構(gòu)造從簡單到復(fù)雜的逐步開展過程。線型構(gòu)造中棧和隊列是兩個非常重要的數(shù)據(jù)構(gòu)造，對于樹、圖的遍歷可用棧和隊列來實現(xiàn)。對樹、圖復(fù)雜的數(shù)據(jù)構(gòu)造，可通過棧和隊列的操作來實現(xiàn)

9、復(fù)雜數(shù)據(jù)構(gòu)造的操作，表達了數(shù)據(jù)構(gòu)造間的“縱向聯(lián)絡(luò)。用棧實現(xiàn)二叉樹的前序遍歷算法：Statusprerder(bitreet)P=t;Initstak(s);Push(s,p);hile(!stakepty(s)pp(s,p)hile(p)visit(p);push(s,prhild);p=p-lhild;用棧實現(xiàn)二叉樹的中序遍歷算法：Statusinrder(bitreet)p=t;Initstak(s);Push(s,p);P=Plhild;hile(!stakepty)hile(p)push(s,p);p=p-lhild;pp(s,p);visist(p);p=prhild;用棧來實現(xiàn)二叉

10、樹的后序遍歷算法：Statuspstrder(bitreet)P=t;inistak(s);hile(p|!stakepty(s)If(p)push(s,p);P=plhild;ElseIf(!stakepty(s)pre=null;Gettp(s,p);hile(prhild=pre)pp(s,p);Visit(p);Pre=p;Gettp(s,p);P=prhild;用隊列實現(xiàn)二叉樹層次遍歷算法：VidLayers(bitreet)if(t)p=t;Initqueue(q);Enqueue(q,t);hile(!epty(q)p=Dlqueue(q);visit(p);if(Plhild)

11、Enqueue(q,plhild);if(prhild)Enqueue(q,prhild);用隊列實現(xiàn)圖的廣度優(yōu)先搜索算法：VidBfs(Graphg,intv)Visit(v);Visitedv=true;Enqueue(q,v);hile(!eptyqueue(q)Dlqueue(g,vex);Fr(=firstadjvex(g,vex),=nextadjvex(g,vex,)If(!visited)visit();Visited=true;Enqueue(q,);VidDfs(Graphg,intv)Visit(v);Visitedv=true;Push(s,v);hile(!eptys

12、tak(s)V=gettp(s);Fr(=fistadjvex(g,v);!visited;=nextadjvex(g,v,)If(!)pp(s)Elsevisit();Visited=true;Push(s,);因為二叉樹、圖的其它的操作大部分是對遍歷根本操作的拓展或綜合應(yīng)用，靈敏運用棧和隊列可實現(xiàn)，并且算法描繪比較直觀。線性構(gòu)造是數(shù)據(jù)構(gòu)造學(xué)科的根底，樹、圖的開展在線性構(gòu)造的根底上而開展，因樹、圖開展促進著線性構(gòu)造中和一些算法的完善和改進，線型構(gòu)造、樹型構(gòu)造、圖狀構(gòu)造是嚴(yán)密相聯(lián)的。數(shù)據(jù)構(gòu)造間縱橫聯(lián)絡(luò)明顯且嚴(yán)密。運用與把握這種“縱橫聯(lián)絡(luò)，對從抽象數(shù)據(jù)類型的角度來進展數(shù)據(jù)構(gòu)造的學(xué)習(xí)與研究有著重要

13、的借鑒意義。抽象數(shù)據(jù)類型ADT的研究越來越被人所重視4-8，它可理解為數(shù)據(jù)類型的進一步抽象。即把數(shù)據(jù)類型和數(shù)據(jù)類型上的運算捆在一起，進展封裝。引入抽象數(shù)據(jù)類型的目的是把數(shù)據(jù)類型的表示和數(shù)據(jù)類型上運算的實現(xiàn)與這些數(shù)據(jù)類型和運算在程序中的引用隔開，使它們互相獨立。對于抽象數(shù)據(jù)類型的描繪，除了必須描繪它的數(shù)據(jù)構(gòu)造外，還必須描繪定義在它上面的運算(過程或函數(shù))。抽象數(shù)據(jù)類型上定義的過程和函數(shù)以該抽象數(shù)據(jù)類型的數(shù)據(jù)所應(yīng)具有的數(shù)據(jù)構(gòu)造為基矗它仍遵循邏輯構(gòu)造、存儲構(gòu)造、操作運算的數(shù)據(jù)構(gòu)造根本思想，所有的抽象數(shù)據(jù)類型都可有簡單的分類策略獲得，這個策略就是抽象數(shù)據(jù)類型對象像什么和對它們做些什么。邏輯構(gòu)造定義、存

14、儲構(gòu)造表示、操作的實如今抽象類型中它們被稱為數(shù)據(jù)類型說明、抽象數(shù)據(jù)類型的表示和抽象數(shù)據(jù)類型的實現(xiàn)3。抽象數(shù)據(jù)類型詳細的表示和實現(xiàn)依賴所采用的語言,用戶可以用某高級語言的固有數(shù)據(jù)類型和自定義類型并借助于過程和函數(shù)來表示和實現(xiàn)抽象數(shù)據(jù)類型。邏輯構(gòu)造、存儲構(gòu)造、操作運算等核心方面是貫穿數(shù)據(jù)構(gòu)造研究與開展的一條根本線，也是數(shù)據(jù)構(gòu)造研究中所看到數(shù)據(jù)構(gòu)造間的“橫向聯(lián)絡(luò)。應(yīng)用根本數(shù)據(jù)結(jié)來實現(xiàn)復(fù)雜數(shù)據(jù)構(gòu)造的方法與途徑，這是對數(shù)據(jù)元素之間關(guān)系從簡單到復(fù)雜的討論，即為“縱向聯(lián)絡(luò)。數(shù)據(jù)構(gòu)造聯(lián)絡(luò)是對數(shù)據(jù)構(gòu)造的整體把握，表達在這種“橫向聯(lián)絡(luò)和“縱向聯(lián)絡(luò)之中。靈敏運用與把握這種數(shù)據(jù)構(gòu)造間的關(guān)系，對抽象數(shù)據(jù)構(gòu)造類型的研究有重要的借鑒意義，同時對數(shù)據(jù)構(gòu)造的實際教學(xué)過程有著一定的指導(dǎo)意義。1陸松年.數(shù)據(jù)構(gòu)造教程.北京：科學(xué)出版社.2002年2嚴(yán)蔚敏.數(shù)據(jù)構(gòu)造(語言版).北京：清華大學(xué)出版社.1997年3帥訓(xùn)波.數(shù)據(jù)構(gòu)造間普遍整體聯(lián)絡(luò)D.曲阜：曲阜師范大學(xué)計算機科學(xué)學(xué)院.2022年4藍雯飛.數(shù)據(jù)構(gòu)造的面向?qū)ο竺枥L方法研究J.計算機工程與應(yīng)用，20