從宏觀上理解數(shù)據(jù)結(jié)構(gòu)
    1.數(shù)據(jù)結(jié)構(gòu)對(duì)編程為什么如此重要？

    現(xiàn)在就根據(jù)我自己的體會(huì)來為大家闡述一下數(shù)據(jù)結(jié)構(gòu)對(duì)我們編程為什么如此重要。記得在開始學(xué)習(xí)編程的時(shí)候，對(duì)數(shù)據(jù)結(jié)構(gòu)沒什么概念，感覺編程就是那么回事，不用數(shù)據(jù)結(jié)構(gòu)也能編出一大堆程序，然而我只能說那都是些小孩子過家家玩的小程序而已，程序中幾乎沒有用到多少數(shù)據(jù)，無論你怎么存儲(chǔ)，程序運(yùn)行起來都是很快的。然而當(dāng)你為工程應(yīng)用去編寫程序的時(shí)候，那都是處理大批的數(shù)據(jù)，那時(shí)候就不能隨便亂存儲(chǔ)數(shù)據(jù)了，必須根據(jù)實(shí)際情況選擇一種合適的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)，從而能夠大大提高數(shù)據(jù)的處理效率。舉個(gè)例子，我們平時(shí)經(jīng)常用到的排序也算是對(duì)數(shù)據(jù)的處理，我們選擇不同的排序算法效率是不同的，當(dāng)數(shù)據(jù)量很小時(shí)，我們感覺不出它們的差異，然而當(dāng)我們對(duì)大量數(shù)據(jù)進(jìn)行排序時(shí)就能感覺出它們的效率來。當(dāng)然在排序時(shí)排序策略是很重要的，然而這些策略有時(shí)是依賴于必要的數(shù)據(jù)結(jié)構(gòu)的。如插入排序、選擇排序、快速排序等可能依賴的只是線性表，而堆排序就依賴于堆了。因此選擇一種好的數(shù)據(jù)結(jié)構(gòu)可能會(huì)大大提高程序的運(yùn)行效率，而且解決問題時(shí)的某中策略可能也要依賴于具體的數(shù)據(jù)結(jié)構(gòu)。 

2.什么是數(shù)據(jù)結(jié)構(gòu)？

    我們知道了數(shù)據(jù)結(jié)構(gòu)對(duì)編程的重要性，那究竟什么是數(shù)據(jù)結(jié)構(gòu)呢？首先來看一下數(shù)據(jù)結(jié)構(gòu)誕生的目的。在現(xiàn)實(shí)世界中存在著大量的數(shù)據(jù)，而這些數(shù)據(jù)不管以何種方式存儲(chǔ)，都需要使用一種結(jié)構(gòu)來表示，而這種結(jié)構(gòu)不僅能夠表示數(shù)據(jù)元素本身，還能夠表示數(shù)據(jù)元素之間的關(guān)系，最好這種結(jié)構(gòu)還能占據(jù)較少的存儲(chǔ)空間。然而這里所說的數(shù)據(jù)結(jié)構(gòu)也只能說是數(shù)據(jù)的邏輯結(jié)構(gòu)，即它只是抽象的存在于我們的腦海中，而在具體的存儲(chǔ)中還需要將這種邏輯結(jié)構(gòu)用現(xiàn)實(shí)事物表示出來。由于我們的計(jì)算機(jī)大部分功能都跟存儲(chǔ)數(shù)據(jù)和處理數(shù)據(jù)有關(guān)，因此計(jì)算機(jī)作為數(shù)據(jù)的載體與數(shù)據(jù)結(jié)構(gòu)的關(guān)系也就相當(dāng)大了，計(jì)算機(jī)就可以根據(jù)我們要求的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)了。至此，我們可以給數(shù)據(jù)結(jié)構(gòu)下一個(gè)比較學(xué)術(shù)的定義：數(shù)據(jù)結(jié)構(gòu)是用來描述數(shù)據(jù)元素集合及各個(gè)數(shù)據(jù)元素之間關(guān)系的邏輯結(jié)構(gòu)。當(dāng)然在很多數(shù)據(jù)結(jié)構(gòu)的書籍中對(duì)數(shù)據(jù)結(jié)構(gòu)的定義是不同的，有的書籍將對(duì)數(shù)據(jù)結(jié)構(gòu)處理的簡單運(yùn)算也歸為數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，當(dāng)然這看你如何理解了，畢竟數(shù)據(jù)結(jié)構(gòu)和算法是不分家的。  

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

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

    我們都知道計(jì)算機(jī)管理內(nèi)存的方式為每個(gè)字節(jié)的空間賦予一個(gè)地址，這樣我們就可以通過地址來訪問內(nèi)存的數(shù)據(jù)了。當(dāng)我們存放數(shù)據(jù)時(shí)，我們可以通過將數(shù)據(jù)存放到指定地址的空間中去，當(dāng)我們?nèi)?shù)據(jù)時(shí)，可以根據(jù)地址找到相應(yīng)的數(shù)據(jù)，這種方式稱為直接尋址方式；另外還有間接尋址方式，這種方式我們通過地址找到的數(shù)據(jù)不是數(shù)據(jù)本身，而是數(shù)據(jù)存放的位置，通過它再去找才能找到真正的數(shù)據(jù)，當(dāng)然，間接尋址可以間接很多次，這就是多維指針的由來。說了大半天的直接尋址和間接尋址，那跟數(shù)據(jù)結(jié)構(gòu)有什么關(guān)系呢？當(dāng)然有關(guān)系了，因?yàn)檫@是計(jì)算機(jī)組織數(shù)據(jù)的兩種最基本的方式，正是通過這兩種基本方式，我們的數(shù)據(jù)才被存放到內(nèi)存中，而存放的時(shí)候可能是連續(xù)的地址空間，也可能是離散的地址空間。正因?yàn)檫@樣，才出現(xiàn)了計(jì)算機(jī)對(duì)數(shù)據(jù)的不同描述形式。常見的描述形式有：公式化描述、鏈表描述、間接描述和模擬指針。

    公式化描述是通過公式計(jì)算出元素的位置，從而能夠直接訪問到這個(gè)元素。但這種描述方式必須保證所使用的空間是連續(xù)的，因?yàn)橹挥羞B續(xù)的地址空間，才能通過一個(gè)固定的偏移量一次找到數(shù)據(jù)的地址。就拿各種編程語言實(shí)現(xiàn)的數(shù)組來說，每個(gè)數(shù)組都有一個(gè)連續(xù)的空間，而數(shù)組名又標(biāo)志著這個(gè)連續(xù)空間的首地址，因此若想訪問這個(gè)數(shù)組的某個(gè)元素直接通過首地址加偏移量就找到了。因此數(shù)組就是一種公式化描述的數(shù)據(jù)結(jié)構(gòu)，描述公式為f(i)=location(i-1)，其中i是表示數(shù)組中的第幾個(gè)元素。對(duì)于多維數(shù)組，內(nèi)存中實(shí)際也是一個(gè)連續(xù)的空間，只不過編譯器也是以公式化的方式來描述這個(gè)數(shù)據(jù)結(jié)構(gòu)的，如在C++中是采用行主映射方式來映射的，二維數(shù)組的公式為f(i,j)=i*n+j；其中i表示行號(hào)，j表示列號(hào)，n表示列數(shù)。當(dāng)然采用公式化描述的數(shù)據(jù)結(jié)構(gòu)有很多，如散列表、完全二叉樹等，這種描述方式優(yōu)點(diǎn)就是很多情況能夠節(jié)省空間，并且提高訪問數(shù)據(jù)的速度。但這種描述方式也有缺點(diǎn)就是經(jīng)常受限，畢竟很多問題是用公式?jīng)]法描述的；還有通過公式化描述需要連續(xù)的空間有時(shí)也顯得不夠靈活。例如對(duì)數(shù)據(jù)的插入刪除操作需要移動(dòng)數(shù)據(jù)。

    鏈表描述方式是將數(shù)據(jù)存儲(chǔ)在離散的空間上，既然空間是離散的，那通過固定的偏移量就沒法訪問元素了。因此可將每個(gè)元素的地址保存到上一個(gè)元素中，這樣就形成了鏈表。鏈表由于采用了離散存儲(chǔ)，因此在有些數(shù)據(jù)操作上就顯得比較靈活。但這也導(dǎo)致了它的不足，比如說不能隨機(jī)訪問某個(gè)節(jié)點(diǎn)，另外還占用了額外的指針空間等。

    間接描述方式是將數(shù)據(jù)的地址保存到一張表中，實(shí)際的數(shù)據(jù)離散的存儲(chǔ)在內(nèi)存中，當(dāng)需要訪問數(shù)據(jù)時(shí)，首先查找表找到數(shù)據(jù)的地址然后再去訪問實(shí)際數(shù)據(jù)。這種描述方式很多時(shí)候是公式化描述和鏈表描述方式的結(jié)合。當(dāng)實(shí)際的數(shù)據(jù)元素比較大時(shí)是適合用這種方式來描述的。

    模擬指針這種方式是通過用整數(shù)來模擬指針訪問數(shù)據(jù)，也算是離散存儲(chǔ)在內(nèi)存中，但這種離散是限定在一定范圍內(nèi)的，因?yàn)槲覀冊趯?shí)現(xiàn)模擬指針時(shí)需要申請一塊連續(xù)的空間模擬堆區(qū)，并根據(jù)實(shí)際需要將這塊連續(xù)的空間重新編號(hào)，以便使用整數(shù)表示它的地址。與此同時(shí)還要維護(hù)兩個(gè)鏈表，空閑鏈表和有數(shù)據(jù)的鏈表。這相當(dāng)于我們替操作系統(tǒng)為程序分配內(nèi)存的工作。 

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

    為了便于將各種數(shù)據(jù)結(jié)構(gòu)聯(lián)系起來，本人對(duì)常見的數(shù)據(jù)結(jié)構(gòu)分為了三大類：線性表，樹，圖。萬變不離其宗，其他的數(shù)據(jù)結(jié)構(gòu)都是在這三種上根據(jù)實(shí)際需要進(jìn)行的擴(kuò)展。當(dāng)然，如果三大類還覺得有點(diǎn)多，那就再來個(gè)萬劍歸綜到圖，任何數(shù)據(jù)結(jié)構(gòu)都可以說成是圖，不過各有各的特點(diǎn)罷了。下面就針對(duì)常見的數(shù)據(jù)結(jié)構(gòu)在三大類上進(jìn)行分析，由于本文只是從宏觀上理解數(shù)據(jù)結(jié)構(gòu)，因此對(duì)各種數(shù)據(jù)結(jié)構(gòu)所實(shí)現(xiàn)的細(xì)節(jié)不會(huì)做太多的說明，想要了解可參看數(shù)據(jù)結(jié)構(gòu)的相關(guān)書籍。 

4.1線性表

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

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

    散列表是通過散列函數(shù)根據(jù)關(guān)鍵字來確定元素的位置，也算是公式化的描述方式。在理想情況下，散列表在查找、插入、刪除的時(shí)間復(fù)雜度都能達(dá)到O(1)，然而在現(xiàn)實(shí)中由于關(guān)鍵字的變化范圍實(shí)在太大，理想散列表實(shí)現(xiàn)需要大量的空間，造成嚴(yán)重浪費(fèi)，因此出現(xiàn)了可以將不同的關(guān)鍵字映射到同一位置的散列函數(shù)，那么問題就又來了，既然將不同的關(guān)鍵字映射到了同一位置，那么該如何處理這種沖突呢？處理這種沖突的兩種常見方式是線性開型尋址散列和鏈表散列，線性開型尋址散列是將相同關(guān)鍵字的元素盡可能的放到函數(shù)映射的位置上，如果該位置已存在，則向后查找最近的空桶；而鏈表散列是將沖突的元素放到一個(gè)鏈表上，這兩種方式各有自己的優(yōu)缺點(diǎn)。

    對(duì)于描述字典的這兩種數(shù)據(jù)結(jié)構(gòu)進(jìn)行性能分析，跳表在最好狀態(tài)下查找、插入、刪除的時(shí)間復(fù)雜度都為O(k+logn)其中k為鏈的級(jí)數(shù),最差則為O(k+n),而對(duì)于采取了將多個(gè)關(guān)鍵字映射到同一位置的散列表來說，最好狀態(tài)下查找、插入、刪除的時(shí)間復(fù)雜度都為O(1)，然而最差狀態(tài)卻達(dá)到O(n),這么來說散列表是否都一直優(yōu)于跳表呢，當(dāng)然還得依賴于實(shí)際的問題，例如在按序輸出時(shí)，跳表明顯優(yōu)于散列表。

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

  4.2樹

    樹可以用來描述具有層次結(jié)構(gòu)的事物，樹這種結(jié)構(gòu)真是太神奇了，通過對(duì)樹添加不同的限制就形成了不同的數(shù)據(jù)結(jié)構(gòu)。如對(duì)只有左右孩子的樹我們稱之為二叉樹，在二叉樹下通過添加各種限制又產(chǎn)生了很多數(shù)據(jù)結(jié)構(gòu)，如完全二叉樹、堆、左高樹、AVL樹、紅黑樹、二叉搜索樹等。下面就來詳細(xì)描述一下這些關(guān)于樹的數(shù)據(jù)結(jié)構(gòu)。

    首先考慮一個(gè)問題在計(jì)算機(jī)內(nèi)存中為什么多采用二叉樹來存儲(chǔ)數(shù)據(jù)，而不采用多叉樹呢？當(dāng)然也是為了提高速度處理效率，在搜索二叉樹的一個(gè)節(jié)點(diǎn)時(shí)當(dāng)然是比較的次數(shù)越少越好。試考慮在一個(gè)有序數(shù)組中進(jìn)行二分查找要比三分查找、四分查找乃至更多分的查找效率更高呢？這個(gè)問題自然也就明白了。

    完全二叉樹是對(duì)二叉樹結(jié)構(gòu)層次限制比較大的數(shù)據(jù)結(jié)構(gòu)，那這種數(shù)據(jù)結(jié)構(gòu)有什么好處呢，其中一個(gè)好處是這種數(shù)據(jù)結(jié)構(gòu)采用公式化描述是非常方便的，而且大大的節(jié)省空間。

    將完全二叉樹限制為最大樹就形成了堆，而堆這種數(shù)據(jù)結(jié)構(gòu)對(duì)于描述優(yōu)先隊(duì)列是非常高效的，使用堆來描述優(yōu)先隊(duì)列插入、刪除的效率都為O(logn)，而且采用公式化描述的話非常節(jié)省空間。當(dāng)然優(yōu)先隊(duì)列還可以用線性表來描述，然而那畢竟是低效的。然而如果想將兩個(gè)優(yōu)先隊(duì)列合并，用堆來描述就非常低效了，就需要選擇另外一種數(shù)據(jù)結(jié)構(gòu)。左高樹是對(duì)左右子樹進(jìn)行優(yōu)先權(quán)限制的二叉樹，至于選擇什么作為優(yōu)先權(quán)的評(píng)價(jià)因素，可以把高度作為評(píng)價(jià)因素，也可以把節(jié)點(diǎn)數(shù)量作為評(píng)價(jià)因素，那就分別形成了高度優(yōu)先左高樹和重量優(yōu)先左高樹。之所以對(duì)左右的子樹進(jìn)行優(yōu)先權(quán)限制，那是因?yàn)檫M(jìn)行了這樣的限制后，將兩棵左高樹合并為一棵左高樹就很容易了。將左高樹再次添加最大樹的限制條件就形成了最大左高樹，最大(小)左高樹同樣可以描述優(yōu)先隊(duì)列，而且適合兩棵樹的合并，不過在存儲(chǔ)效率方面不如堆節(jié)省空間了。

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

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

 4.3圖

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

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

最新評(píng)論