從宏觀上理解數(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ù)，無論你怎么存儲，程序運行起來都是很快的。然而當你為工程應(yīng)用去編寫程序的時候，那都是處理大批的數(shù)據(jù)，那時候就不能隨便亂存儲數(shù)據(jù)了，必須根據(jù)實際情況選擇一種合適的數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)，從而能夠大大提高數(shù)據(jù)的處理效率。舉個例子，我們平時經(jīng)常用到的排序也算是對數(shù)據(jù)的處理，我們選擇不同的排序算法效率是不同的，當數(shù)據(jù)量很小時，我們感覺不出它們的差異，然而當我們對大量數(shù)據(jù)進行排序時就能感覺出它們的效率來。當然在排序時排序策略是很重要的，然而這些策略有時是依賴于必要的數(shù)據(jù)結(jié)構(gòu)的。如插入排序、選擇排序、快速排序等可能依賴的只是線性表，而堆排序就依賴于堆了。因此選擇一種好的數(shù)據(jù)結(jié)構(gòu)可能會大大提高程序的運行效率，而且解決問題時的某中策略可能也要依賴于具體的數(shù)據(jù)結(jié)構(gòu)。 

2.什么是數(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)系，最好這種結(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ù)據(jù)結(jié)構(gòu)和算法是不分家的。  

3.計算機描述數(shù)據(jù)的方式

    前邊描述了什么是數(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ù)的存儲，我們程序員都應(yīng)該知道，我們的程序在計算機上運行需要一定的內(nèi)存空間，該空間可以簡單分為代碼區(qū)和數(shù)據(jù)區(qū)。代碼區(qū)是存放我們程序代碼的地方，那部分空間我們無法管理。但是數(shù)據(jù)區(qū)是存放我們程序需要處理的數(shù)據(jù)的地方，而我們就是采取合理的方式將數(shù)據(jù)存儲到那個地方。

    我們都知道計算機管理內(nèi)存的方式為每個字節(jié)的空間賦予一個地址，這樣我們就可以通過地址來訪問內(nèi)存的數(shù)據(jù)了。當我們存放數(shù)據(jù)時，我們可以通過將數(shù)據(jù)存放到指定地址的空間中去，當我們?nèi)?shù)據(jù)時，可以根據(jù)地址找到相應(yīng)的數(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ù)的地址空間，也可能是離散的地址空間。正因為這樣，才出現(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-1)，其中i是表示數(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ù)存儲在離散的空間上，既然空間是離散的，那通過固定的偏移量就沒法訪問元素了。因此可將每個元素的地址保存到上一個元素中，這樣就形成了鏈表。鏈表由于采用了離散存儲，因此在有些數(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)的，因為我們在實現(xiàn)模擬指針時需要申請一塊連續(xù)的空間模擬堆區(qū)，并根據(jù)實際需要將這塊連續(xù)的空間重新編號，以便使用整數(shù)表示它的地址。與此同時還要維護兩個鏈表，空閑鏈表和有數(shù)據(jù)的鏈表。這相當于我們替操作系統(tǒng)為程序分配內(nèi)存的工作。 

4.各種數(shù)據(jù)結(jié)構(gòu)的宏觀理解

    為了便于將各種數(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é)不會做太多的說明，想要了解可參看數(shù)據(jù)結(jié)構(gòu)的相關(guān)書籍。 

4.1線性表

    線性表的數(shù)據(jù)結(jié)構(gòu)有很多，如數(shù)組、矩陣、鏈表、堆棧、隊列、跳表、散列表等。一維數(shù)組是典型的線性表，多維數(shù)組可以看成是多個線性表的組合，數(shù)組的描述方式一般采用公式化描述方式。對于矩陣可以看成是二維數(shù)組，但是由于矩陣有很多種，比如三角矩陣，稀疏矩陣，像對這樣矩陣的描述為了節(jié)省空間，可采用合理的描述方式，如采用鏈表的方式，只將非零元素保存到節(jié)點上。堆棧和隊列實際上是對線性表添加某種限制而形成的， 堆棧是后進先出，隊列是先進先出，實際上它們是一種特殊的優(yōu)先隊列，只不過對優(yōu)先權(quán)的規(guī)定是不一樣的?？梢允褂霉交枋鏊鼈円部梢允褂面湵砻枋鏊鼈?，但是效率是不同的。對于堆棧采取公式化描述是比較好的，進出效率都為O(1)，若用鏈表描述就顯得有點浪費空間了，不過如果是多個堆棧的話，用鏈表描述是比較好的。對于隊列適合用鏈表來描述，因為對于鏈表無論是從頭部添加元素還是從尾部刪除元素效率都是O(1)，然而如果采用公式化描述的話，每次刪除需要移動元素，無疑增加了開銷。

    跳表和散列表是經(jīng)常用來描述字典的兩種數(shù)據(jù)結(jié)構(gòu)。字典常見的操作有查找、插入、刪除、按序輸出等。雖然字典也能用普通的數(shù)組鏈表實現(xiàn)，但效率不高。跳表是對鏈表的一種改進。鏈表本身優(yōu)點就是插入、刪除效率比數(shù)組高，然而查找效率低，因此可以通過添加額外的指針來提高查找效率。跳表的原理是根據(jù)二分查找的思想，我們知道在一個有序數(shù)組上二分查找的時間復(fù)雜度為O(logn),因此可以通過在有序鏈表上添加額外的指針來實現(xiàn)這樣的搜索方法。然而仔細分析，我們會發(fā)現(xiàn)，要想實現(xiàn)真正的二分查找并非易事，因為跳表中的元素并非是一成不變的，因此該在哪個元素上添加額外的指針并且把該元素應(yīng)該視為幾級鏈表上的元素，都是不可預(yù)測的，因此這就增加了實現(xiàn)跳表的復(fù)雜度，在實際中可采用隨機的方式將某一個元素定為幾級鏈上的元素，具體的實現(xiàn)細節(jié)可參看數(shù)據(jù)結(jié)構(gòu)的相關(guān)書籍。

    散列表是通過散列函數(shù)根據(jù)關(guān)鍵字來確定元素的位置，也算是公式化的描述方式。在理想情況下，散列表在查找、插入、刪除的時間復(fù)雜度都能達到O(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)下查找、插入、刪除的時間復(fù)雜度都為O(k+logn)其中k為鏈的級數(shù),最差則為O(k+n),而對于采取了將多個關(guān)鍵字映射到同一位置的散列表來說，最好狀態(tài)下查找、插入、刪除的時間復(fù)雜度都為O(1)，然而最差狀態(tài)卻達到O(n),這么來說散列表是否都一直優(yōu)于跳表呢，當然還得依賴于實際的問題，例如在按序輸出時，跳表明顯優(yōu)于散列表。

    在線性表這幾種數(shù)據(jù)結(jié)構(gòu)中會發(fā)現(xiàn)，他們都是對普通的線性表改造而成，有的是添加規(guī)則上的限制，有的是添加額外的輔助信息，還有的是對多個線性表的組合。但無論怎樣變化，終究還是線性表。因此我們在實際開發(fā)中，可以根據(jù)不同數(shù)據(jù)結(jié)構(gòu)的特點來選擇他們。  

  4.2樹

    樹可以用來描述具有層次結(jié)構(gòu)的事物，樹這種結(jié)構(gòu)真是太神奇了，通過對樹添加不同的限制就形成了不同的數(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)有什么好處呢，其中一個好處是這種數(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)限制，那是因為進行了這樣的限制后，將兩棵左高樹合并為一棵左高樹就很容易了。將左高樹再次添加最大樹的限制條件就形成了最大左高樹，最大(小)左高樹同樣可以描述優(yōu)先隊列，而且適合兩棵樹的合并，不過在存儲效率方面不如堆節(jié)省空間了。

    接下來討論一下搜索樹，搜索樹是另一種可以描述字典的高效的數(shù)據(jù)結(jié)構(gòu)。先來分析一下二叉搜索樹，二叉搜索樹是對二叉樹節(jié)點上的值進行限制，要求每個節(jié)點的值比左子樹的值大并且比右子樹的小，加上這一限制，對某一元素的搜索效率就比較高了，在最好情況下查找，插入，刪除操作的時間復(fù)雜度都能夠達到O(logn)，然而最壞情況下達到了O(n)，導致最壞情況是由于二叉樹的極度不平衡造成的，為了解決這個問題，平衡樹又摻和進來了，平衡二叉搜索樹不就很好的解決了這個問題嗎？然而在每次插入刪除操作后AVL樹為了維持平衡的特性需要進行多次旋轉(zhuǎn)，因而這又降低了效率。紅黑樹的出現(xiàn)就很好的解決了這個問題，紅黑樹雖然不是完全平衡的二叉樹但也算的上是基本平衡，然而紅黑樹對于插入刪除操作后維持紅黑樹的特性花費的代價并不高。在現(xiàn)實應(yīng)用中，很多字典都是用紅黑樹來進行描述的。除了二叉搜索樹，多叉搜索樹在很多地方也有應(yīng)用，例如在讀取磁盤數(shù)據(jù)時，可以采用B-樹來建立索引，由于每次讀取磁盤花費的代價比較大，因此讀取的磁盤次數(shù)越少越好，從理論上也就是說樹的高度越矮越好。又如為了提高索引速度，很多數(shù)據(jù)庫采用B+樹建立索引。另外，由于英語單詞一般是用字母拼湊而成，因此將英語單詞存放在多叉樹中可以大大提高搜索單詞的效率，這就是著名的Trie樹。

    通過以上對各種由樹產(chǎn)生的數(shù)據(jù)結(jié)構(gòu)來看，通過對樹添加各種限制來維持一種固定的數(shù)據(jù)結(jié)構(gòu)對解決某些特定的問題是非常高效的，因此在現(xiàn)實應(yīng)用中，我們應(yīng)該根據(jù)實際的需要選擇合適的數(shù)據(jù)結(jié)構(gòu)或?qū)δ承?shù)據(jù)結(jié)構(gòu)進行改造，變成真正適合自己的數(shù)據(jù)結(jié)構(gòu)。 

 4.3圖

    用圖來描述萬千事物極其聯(lián)系是最方便不過的了，然而根據(jù)具體的問題所產(chǎn)生的圖也是不一樣的，如有的事物用有向圖描述比較合適，有的用無向圖描述比較合適，有的用完全圖描述比較合適，有的用連通圖描述比較合適，有的用二分圖描述比較合適，不管怎樣要根據(jù)實際的問題使用不同的方式，當然在解決實際問題時，往往需要結(jié)合必要的算法。

    對于圖的描述經(jīng)常采用的是鄰接矩陣和鄰接鏈表來描述。