從宏觀上理解數(shù)據(jù)結(jié)構(gòu)

1、從宏觀上理解數(shù)據(jù)結(jié)構(gòu)現(xiàn)在就根據(jù)我自己的體會來為大家闡述一下數(shù)據(jù)結(jié)構(gòu) 對我們編程為什么如此重要。記得在開始學習編程的時候， 對數(shù)據(jù)結(jié)構(gòu)沒什么概念，感覺編程就是那么回事，不用數(shù)據(jù) 結(jié)構(gòu)也能編出一大堆程序，然而我只能說那都是些小孩子過 家家玩的小程序而已，程序中幾乎沒有用到多少數(shù)據(jù)，無論 你怎么存儲，程序運行起來都是很快的。然而當你為工程應 用去編寫程序的時候，那都是處理大批的數(shù)據(jù)，那時候就不 能隨便亂存儲數(shù)據(jù)了，必須根據(jù)實際情況選擇一種合適的數(shù) 據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)，從而能夠大大提高數(shù)據(jù)的處理效率。舉 個例子，我們平時經(jīng)常用到的排序也算是對數(shù)據(jù)的處理，我 們選擇不同的排序算法效率是不同的，當數(shù)據(jù)量很小

2、時，我 們感覺不出它們的差異，然而當我們對大量數(shù)據(jù)進行排序時 就能感覺出它們的效率來。當然在排序時排序策略是很重要 的，然而這些策略有時是依賴于必要的數(shù)據(jù)結(jié)構(gòu)的。如插入 排序、選擇排序、快速排序等可能依賴的只是線性表，而堆 排序就依賴于堆了。因此選擇一種好的數(shù)據(jù)結(jié)構(gòu)可能會大大 提高程序的運行效率，而且解決問題時的某中策略可能也要 依賴于具體的數(shù)據(jù)結(jié)構(gòu)。我們知道了數(shù)據(jù)結(jié)構(gòu)對編程的重要性，那究竟什么是數(shù)據(jù)結(jié)構(gòu)呢？首先來看一下數(shù)據(jù)結(jié)構(gòu)誕生的目的。在現(xiàn)實世 界中存在著大量的數(shù)據(jù)，而這些數(shù)據(jù)不管以何種方式存儲， 都需要使用一種結(jié)構(gòu)來表示，而這種結(jié)構(gòu)不僅能夠表示數(shù)據(jù) 元素本身，還能夠表示數(shù)據(jù)元素之間的關(guān)系

3、，最好這種結(jié)構(gòu) 還能占據(jù)較少的存儲空間。然而這里所說的數(shù)據(jù)結(jié)構(gòu)也只能 說是數(shù)據(jù)的邏輯結(jié)構(gòu)，即它只是抽象的存在于我們的腦海 中，而在具體的存儲中還需要將這種邏輯結(jié)構(gòu)用現(xiàn)實事物表 示出來。由于我們的計算機大部分功能都跟存儲數(shù)據(jù)和處理 數(shù)據(jù)有關(guān)，因此計算機作為數(shù)據(jù)的載體與數(shù)據(jù)結(jié)構(gòu)的關(guān)系也 就相當大了，計算機就可以根據(jù)我們要求的數(shù)據(jù)結(jié)構(gòu)來存儲 數(shù)據(jù)了。至此，我們可以給數(shù)據(jù)結(jié)構(gòu)下一個比較學術(shù)的定義: 數(shù)據(jù)結(jié)構(gòu)是用來描述數(shù)據(jù)元素集合及各個數(shù)據(jù)元素之間關(guān) 系的邏輯結(jié)構(gòu)。當然在很多數(shù)據(jù)結(jié)構(gòu)的書籍中對數(shù)據(jù)結(jié)構(gòu)的 定義是不同的，有的書籍將對數(shù)據(jù)結(jié)構(gòu)處理的簡單運算也歸 為數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，當然這看你如何理解了，畢竟數(shù)

4、據(jù)結(jié)構(gòu) 和算法是不分家的。前邊描述了什么是數(shù)據(jù)結(jié)構(gòu)，那計算機都可以通過哪 些基本的手段來描述我們的數(shù)據(jù)呢？首先我們知道在計算 機中大部分數(shù)據(jù)都存在于磁盤上和內(nèi)存里，而cpu處理數(shù)據(jù) 又必須將數(shù)據(jù)從磁盤讀取到內(nèi)存中，由于內(nèi)存資源比較珍 貴，我們采取合適的數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中存儲數(shù)據(jù)以節(jié)省內(nèi)存 空間是必要的。談到內(nèi)存對數(shù)據(jù)的存儲，我們程序員都應該 知道，我們的程序在計算機上運行需要一定的內(nèi)存空間，該 空間可以簡單分為代碼區(qū)和數(shù)據(jù)區(qū)。代碼區(qū)是存放我們程序 代碼的地方，那部分空間我們無法管理。但是數(shù)據(jù)區(qū)是存放 我們程序需要處理的數(shù)據(jù)的地方，而我們就是采取合理的方 式將數(shù)據(jù)存儲到那個地方。我們都知道計算機管

5、理內(nèi)存的方式為每個字節(jié)的空 間賦予一個地址，這樣我們就可以通過地址來訪問內(nèi)存的數(shù) 據(jù)了。當我們存放數(shù)據(jù)時，我們可以通過將數(shù)據(jù)存放到指定 地址的空間中去，當我們?nèi)?shù)據(jù)時，可以根據(jù)地址找到相應 的數(shù)據(jù)，這種方式稱為直接尋址方式；另外還有間接尋址方 式，這種方式我們通過地址找到的數(shù)據(jù)不是數(shù)據(jù)本身，而是 數(shù)據(jù)存放的位置，通過它再去找才能找到真正的數(shù)據(jù)，當然, 間接尋址可以間接很多次，這就是多維指針的由來。說了大 半天的直接尋址和間接尋址，那跟數(shù)據(jù)結(jié)構(gòu)有什么關(guān)系呢？ 當然有關(guān)系了，因為這是計算機組織數(shù)據(jù)的兩種最基本的方 式，正是通過這兩種基本方式，我們的數(shù)據(jù)才被存放到內(nèi)存 中，而存放的時候可能是連續(xù)的地

6、址空間，也可能是離散的 地址空間。正因為這樣，才出現(xiàn)了計算機對數(shù)據(jù)的不同描述 形式。常見的描述形式有：公式化描述、鏈表描述、間接描 述和模擬指針。公式化描述是通過公式計算出元素的位置，從而能夠 直接訪問到這個元素。但這種描述方式必須保證所使用的空 間是連續(xù)的，因為只有連續(xù)的地址空間，才能通過一個固定 的偏移量一次找到數(shù)據(jù)的地址。就拿各種編程語言實現(xiàn)的數(shù) 組來說，每個數(shù)組都有一個連續(xù)的空間，而數(shù)組名又標志著 這個連續(xù)空間的首地址，因此若想訪問這個數(shù)組的某個元素 直接通過首地址加偏移量就找到了。因此數(shù)組就是一種公式 化描述的數(shù)據(jù)結(jié)構(gòu)，描述公式為f (i)=location(i-l),其中 i是表示

7、數(shù)組中的第幾個元素。對于多維數(shù)組，內(nèi)存中實際 也是一個連續(xù)的空間，只不過編譯器也是以公式化的方式來 描述這個數(shù)據(jù)結(jié)構(gòu)的，如在c+中是采用行主映射方式來映 射的，二維數(shù)組的公式為f (i, j)二i*n+j；其中i表示行號， j表示列號，n表示列數(shù)。當然采用公式化描述的數(shù)據(jù)結(jié)構(gòu) 有很多，如散列表、完全二叉樹等，這種描述方式優(yōu)點就是 很多情況能夠節(jié)省空間，并且提高訪問數(shù)據(jù)的速度。但這種 描述方式也有缺點就是經(jīng)常受限，畢竟很多問題是用公式?jīng)] 法描述的；還有通過公式化描述需要連續(xù)的空間有時也顯得 不夠靈活。例如對數(shù)據(jù)的插入刪除操作需要移動數(shù)據(jù)。鏈表描述方式是將數(shù)據(jù)存儲在離散的空間上，既然空 間是離散的

8、，那通過固定的偏移量就沒法訪問元素了。因此 可將每個元素的地址保存到上一個元素中，這樣就形成了鏈 表。鏈表由于采用了離散存儲，因此在有些數(shù)據(jù)操作上就顯 得比較靈活。但這也導致了它的不足，比如說不能隨機訪問 某個節(jié)點，另外還占用了額外的指針空間等。間接描述方式是將數(shù)據(jù)的地址保存到一張表中，實際 的數(shù)據(jù)離散的存儲在內(nèi)存中，當需要訪問數(shù)據(jù)時，首先查找 表找到數(shù)據(jù)的地址然后再去訪問實際數(shù)據(jù)。這種描述方式很 多時候是公式化描述和鏈表描述方式的結(jié)合。當實際的數(shù)據(jù) 元素比較大時是適合用這種方式來描述的。模擬指針這種方式是通過用整數(shù)來模擬指針訪問數(shù) 據(jù)，也算是離散存儲在內(nèi)存中，但這種離散是限定在一定范 圍內(nèi)的

9、，因為我們在實現(xiàn)模擬指針時需要申請一塊連續(xù)的空 間模擬堆區(qū)，并根據(jù)實際需要將這塊連續(xù)的空間重新編號， 以便使用整數(shù)表示它的地址。與此同時還要維護兩個鏈表， 空閑鏈表和有數(shù)據(jù)的鏈表。這相當于我們替操作系統(tǒng)為程序 分配內(nèi)存的工作。為了便于將各種數(shù)據(jù)結(jié)構(gòu)聯(lián)系起來，本人對常見的數(shù) 據(jù)結(jié)構(gòu)分為了三大類：線性表，樹，圖。萬變不離其宗，其 他的數(shù)據(jù)結(jié)構(gòu)都是在這三種上根據(jù)實際需要進行的擴展。當 然，如果三大類還覺得有點多，那就再來個萬劍歸綜到圖， 任何數(shù)據(jù)結(jié)構(gòu)都可以說成是圖，不過各有各的特點罷了。下 面就針對常見的數(shù)據(jù)結(jié)構(gòu)在三大類上進行分析，由于本文只 是從宏觀上理解數(shù)據(jù)結(jié)構(gòu)，因此對各種數(shù)據(jù)結(jié)構(gòu)所實現(xiàn)的細 節(jié)

10、不會做太多的說明，想要了解可參看數(shù)據(jù)結(jié)構(gòu)的相關(guān)書 籍。線性表線性表的數(shù)據(jù)結(jié)構(gòu)有很多，如數(shù)組、矩陣、鏈表、堆 棧、隊列、跳表、散列表等。一維數(shù)組是典型的線性表，多 維數(shù)組可以看成是多個線性表的組合，數(shù)組的描述方式一般 采用公式化描述方式。對于矩陣可以看成是二維數(shù)組，但是 由于矩陣有很多種，比如三角矩陣，稀疏矩陣，像對這樣矩 陣的描述為了節(jié)省空間，可采用合理的描述方式，如采用鏈 表的方式，只將非零元素保存到節(jié)點上。堆棧和隊列實際上 是對線性表添加某種限制而形成的，堆棧是后進先出，隊 列是先進先出，實際上它們是一種特殊的優(yōu)先隊列，只不過 對優(yōu)先權(quán)的規(guī)定是不一樣的?？梢允褂霉交枋鏊鼈円部?以使用鏈

11、表描述它們，但是效率是不同的。對于堆棧采取公 式化描述是比較好的，進出效率都為0(1),若用鏈表描述就 顯得有點浪費空間了，不過如果是多個堆棧的話，用鏈表描 述是比較好的。對于隊列適合用鏈表來描述，因為對于鏈表 無論是從頭部添加元素還是從尾部刪除元素效率都是0(1), 然而如果采用公式化描述的話，每次刪除需要移動元素，無 疑增加了開銷。跳表和散列表是經(jīng)常用來描述字典的兩種數(shù)據(jù)結(jié)構(gòu)。 字典常見的操作有查找、插入、刪除、按序輸出等。雖然字 典也能用普通的數(shù)組鏈表實現(xiàn)，但效率不髙。跳表是對鏈表 的一種改進。鏈表本身優(yōu)點就是插入、刪除效率比數(shù)組高， 然而查找效率低，因此可以通過添加額外的指針來提高查找

12、 效率。跳表的原理是根據(jù)二分查找的思想，我們知道在一個 有序數(shù)組上二分查找的時間復雜度為o(logn),因此可以通 過在有序鏈表上添加額外的指針來實現(xiàn)這樣的搜索方法。然 而仔細分析，我們會發(fā)現(xiàn)，要想實現(xiàn)真正的二分查找并非易 事，因為跳表中的元素并非是一成不變的，因此該在哪個元 素上添加額外的指針并且把該元素應該視為幾級鏈表上的 元素，都是不可預測的，因此這就增加了實現(xiàn)跳表的復雜度, 在實際中可采用隨機的方式將某一個元素定為幾級鏈上的 元素，具體的實現(xiàn)細節(jié)可參看數(shù)據(jù)結(jié)構(gòu)的相關(guān)書籍。散列表是通過散列函數(shù)根據(jù)關(guān)鍵字來確定元素的位 置，也算是公式化的描述方式。在理想情況下，散列表在查 找、插入、刪除的

13、時間復雜度都能達到0(1),然而在現(xiàn)實中 由于關(guān)鍵字的變化范圍實在太大，理想散列表實現(xiàn)需要大量 的空間，造成嚴重浪費，因此出現(xiàn)了可以將不同的關(guān)鍵字映 射到同一位置的散列函數(shù)，那么問題就又來了，既然將不同 的關(guān)鍵字映射到了同一位置，那么該如何處理這種沖突呢？ 處理這種沖突的兩種常見方式是線性開型尋址散列和鏈表 散列，線性開型尋址散列是將相同關(guān)鍵字的元素盡可能的放 到函數(shù)映射的位置上，如果該位置已存在，則向后查找最近 的空桶；而鏈表散列是將沖突的元素放到一個鏈表上，這兩 種方式各有自己的優(yōu)缺點。對于描述字典的這兩種數(shù)據(jù)結(jié)構(gòu)進行性能分析，跳表 在最好狀態(tài)下查找、插入、刪除的時間復雜度都為o(k+lo

14、gn) 其中k為鏈的級數(shù)，最差則為0(k+n),而對于釆取了將多個關(guān) 鍵字映射到同一位置的散列表來說，最好狀態(tài)下查找、插入、 刪除的時間復雜度都為0(1),然而最差狀態(tài)卻達到0(n),這 么來說散列表是否都一直優(yōu)于跳表呢，當然還得依賴于實際 的問題，例如在按序輸出時，跳表明顯優(yōu)于散列表。在線性表這幾種數(shù)據(jù)結(jié)構(gòu)中會發(fā)現(xiàn)，他們都是對普通 的線性表改造而成，有的是添加規(guī)則上的限制，有的是添加 額外的輔助信息，還有的是對多個線性表的組合。但無論怎 樣變化，終究還是線性表。因此我們在實際開發(fā)中，可以根 據(jù)不同數(shù)據(jù)結(jié)構(gòu)的特點來選擇他們。樹樹可以用來描述具有層次結(jié)構(gòu)的事物，樹這種結(jié)構(gòu)真 是太神奇了，通過對樹

15、添加不同的限制就形成了不同的數(shù)據(jù) 結(jié)構(gòu)。如對只有左右孩子的樹我們稱之為二叉樹，在二叉樹 下通過添加各種限制又產(chǎn)生了很多數(shù)據(jù)結(jié)構(gòu)，如完全二叉 樹、堆、左高樹、avl樹、紅黑樹、二叉搜索樹等。下面就 來詳細描述一下這些關(guān)于樹的數(shù)據(jù)結(jié)構(gòu)。首先考慮一個問題在計算機內(nèi)存中為什么多采用二 叉樹來存儲數(shù)據(jù)，而不采用多叉樹呢？當然也是為了提高速 度處理效率，在搜索二叉樹的一個節(jié)點時當然是比較的次數(shù) 越少越好。試考慮在一個有序數(shù)組中進行二分查找要比三分 查找、四分查找乃至更多分的查找效率更高呢？這個問題自 然也就明白了。完全二叉樹是對二叉樹結(jié)構(gòu)層次限制比較大的數(shù)據(jù) 結(jié)構(gòu)，那這種數(shù)據(jù)結(jié)構(gòu)有什么好處呢，其中一個好處

16、是這種 數(shù)據(jù)結(jié)構(gòu)采用公式化描述是非常方便的，而且大大的節(jié)省空 間。將完全二叉樹限制為最大樹就形成了堆，而堆這種數(shù) 據(jù)結(jié)構(gòu)對于描述優(yōu)先隊列是非常高效的，使用堆來描述優(yōu)先 隊列插入、刪除的效率都為o(logn),而且采用公式化描述 的話非常節(jié)省空間。當然優(yōu)先隊列還可以用線性表來描述， 然而那畢竟是低效的。然而如果想將兩個優(yōu)先隊列合并，用 堆來描述就非常低效了，就需要選擇另外一種數(shù)據(jù)結(jié)構(gòu)。左 高樹是對左右子樹進行優(yōu)先權(quán)限制的二叉樹，至于選擇什么 作為優(yōu)先權(quán)的評價因素，可以把高度作為評價因素，也可以 把節(jié)點數(shù)量作為評價因素，那就分別形成了高度優(yōu)先左高樹 和重量優(yōu)先左高樹。之所以對左右的子樹進行優(yōu)先權(quán)限

17、制， 那是因為進行了這樣的限制后，將兩棵左高樹合并為一棵左 高樹就很容易了。將左高樹再次添加最大樹的限制條件就形 成了最大左高樹，最大(小)左高樹同樣可以描述優(yōu)先隊列， 而且適合兩棵樹的合并，不過在存儲效率方面不如堆節(jié)省空 間了。接下來討論一下搜索樹，搜索樹是另一種可以描述字 典的高效的數(shù)據(jù)結(jié)構(gòu)。先來分析一下二叉搜索樹，二叉搜索 樹是對二叉樹節(jié)點上的值進行限制，要求每個節(jié)點的值比左 子樹的值大并且比右子樹的小，加上這一限制，對某一元素 的搜索效率就比較高了，在最好情況下查找，插入，刪除操 作的時間復雜度都能夠達到o(logn),然而最壞情況下達到 了 0(n),導致最壞情況是由于二叉樹的極度不平衡造成的， 為了解決這個問題，平衡樹又摻和進來了，平衡二叉搜索樹 不就很好的解決了這個問題嗎？然而在每次插入刪除操作 后avl樹為了維持平衡的特性需要進行多次旋轉(zhuǎn)，因而這又 降低了效率。紅黑樹的出現(xiàn)就很好的解決了這個問題，紅黑 樹雖然不是完全平衡的二叉樹但也算的上是基本平衡，然而 紅黑樹對于插入刪除操作后維持紅黑樹的特性花費的代價 并不高。在現(xiàn)實應用中，很多字典都是用紅黑樹來進行描述 的。除了二叉搜索樹，多叉搜索樹在很多地方也有應用，例