三個例子解釋什麼是數據結構

最新 07-04

給大家推薦一門來自浙江大學的非常優秀的精品課--數據結構，本文是它的第一課視頻筆記，後附視頻鏈接。

什麼是數據結構？三個例子解釋？

例子1：如何在書架上擺放圖書？

不科學的問題：給你一些書架，然後又有一堆書進來，你要把他們怎麼放到書架上去呢？換言之我給了你一堆數據，然後給了你一些存儲空間，你要如何把數據存儲起來呢？

第一：沒有告訴書架長什麼樣，其實問你一個關於數據存儲的問題的時候，是和這個問題的規模是有關係的，不一樣規模的問題，它處理起來的難度就不一樣，難不在於說你要把它怎麼放，而在於放這個書是為了做事情用的？其實圖書擺放是和兩個操作是直接相關的即圖書的擺放要使得2個相關操作方便實現：

操作1：新書怎麼插入？

操作2：怎麼找到某本指定的書？

三個不一樣的辦法：

1. 最簡單最直接的方法：隨便放，隨便放的一個好處：新書怎麼插入？這個操作是非常簡單的，那有空就放哪？最簡單的就是把所有的書一本一本挨著放。

方法1：隨便放

操作1：新書怎麼插入？

哪裡有空放哪裡，一步到位！那查找怎麼辦呢？

操作2：怎麼找到某本指定的書？

累死（如果書架很小，累不死，如果是巨型圖書館書架，累死）

2. 怎麼讓找書找的方便呢？第二個方法就是按照書名的拼音字母順序放，這樣查找就方便多了，一個最聰明的辦法是二分法查找

方法2：按照書名的拼音字母順序排放

操作2：怎麼找到某本指定的書？

二分查找

那麼第二個比較麻煩的問題就是新書來了怎麼插入？

操作1：新書怎麼插入？

比較麻煩。

2. 方法3：把書架劃分成幾塊區域，每塊區域指定擺放某種類別的圖書：在每種類別內，按照書名的拼音字母順序擺放

這種問題的最大好處就是，不管我在每一個類裡面做什麼樣的操作，總歸來說，這個圖書的規模都小了很多，跟整個書城的書的規模相比，我是某一類的，那麼無論是查找還是插入，都會方便一點

操作1：新書怎麼插入？

先定類別，二分查找確定位置，移出空位。

操作2：怎麼找到某本指定的書？

先定類別，再二分查找。

但是還是有兩個方面的問題：空間如何分配？類別應該分多細？

這個例子告訴我們：解決問題方法的效率，跟數據的組織方式有關

例子2：寫程序實現一個函數PrintN，使得傳入一個正整數為N的參數後，能順序列印從1到N的全部正整數。

兩種不同的實現方法：第一種循環實現非常直截了當

void PrintN（int N）

{ int i ；

for (i=1; i

{ printf(%d
", i) ;

}

return;

}

第二種方法遞歸實現：判斷N不是0的話，遞歸的調用printN函數，然後傳入進去的參數是N-1，遞歸地把1到N-1這些數，用這個遞歸函數列印出來，最後再列印當前的第N個數。

void PrintN（int N)

{ if (N)

{ PrintN(N-1);

printf("%d
", N) ; }

}

return;

}

但是遞歸運行很慢，當N取100000，程序就會罷工，因為遞歸對空間的佔用有的時候是非常恐怖的，它把它能用的空間全部吃掉，還不夠吃，然後它就爆掉了，這是一個非正常的終止，它還來不及打出任何一個數字，它就非正常終止，跳出了。

這個例子告訴我們：解決問題方法的效率，也跟空間的利用效率是有關的。

例子3 寫程序計算給定多項式在給定點x處的值

第一個函數要遭到鄙視，因為它運行速度很慢，第一個演算法的運行速度差不多比第二慢了一個數量級。

這個例子告訴我們：解決問題方法的效率，跟演算法的巧妙程度有關係。

什麼是數據結構？

首先數據結構是關於數據對象在計算機中的組織方式，也就是我們在書店裡怎麼放書的問題，另外一方面數據對象不是孤立的，它必定與一系列加在其上的操作相關聯，而實現這些操作所用的方法，就叫做演算法。

在介紹數據對象的組織方式的時候，有兩個概念在這裡，一個是關於數據對象的邏輯結構，什麼是邏輯結構，比如說，我們如果一開始把這個書架想像成簡單的一長條，這麼一層的架子，然後所有的書是一個挨著一個放著，除了一頭一尾的書以外，每一本書它前面只有一本書，後面只有一本，如果給每一本書一個編號的話，那麼這一個編號對應的就是一本書，這種結構是一對一的結構，我們管它叫做『線性結構』。

另外一種組織方法，是我們的第三個方法，就是先把圖書來分類，如果給每一類一個編號的話，那麼這一個類別的編號裡邊，對應著很多本書，那麼這是一個一對多的邏輯結構，這種結構有個名字叫『樹』。

圖是什麼東西呢？假設我們還統計這樣的一些信息：這本書都有哪些人買過，買了這本書的人還買過其它的什麼書？於是呢，其實就是一本書對應著很多人，而一個人又對應了很多書本，這是一個多對多的，很複雜的一個關係網，這個關係網對應的就是一個『圖』的結構。

除了邏輯結構之外，我們還有數據對象在計算機裡面的物理存儲結構，也就是我們說的這些邏輯結構在機器的內存裡面到底要怎麼一個放法，是連續放著呢？還是東一個西一個隔開放著呢？也就是說，是用一個數組來存它呢？還是用一個鏈表來存它呢？這個就是屬於物理存儲結構。

描述數據結構我們有一個很好的方法叫做『抽象數據類型』，這裡面有兩個關鍵詞，一個是數據類型，一個是抽象。

數據類型，其實包含了兩個東西，一個是數據對象集，一個是數據集合相關聯的操作集，就像我們說，我們不能單純地講怎麼去處理圖書，我們是要對圖書要做操作的，這兩件事：圖書的擺放跟它的操作是緊密結合在一起的，這兩件事在C語言里，它是獨立處理的，但是在一些面向對象的語言裡邊，比如說如果你會C++，如果你會java，它們很好的為這個數據類型專門設計了這樣的機制，就是一個「類」，把這個數據集跟和它相關的操作集封裝在一個類裡面。

什麼是抽象呢，就是不具體，也就是說，描述數據類型的方法不依賴於具體的實現的，對一個數據的描述，它應該是跟存放數據的機器無關，跟數據存儲的物理結構無關，跟實現操作的演算法和編程語言都是沒有關係的，總體來說，我們只描述數據對象集和相關的操作集是什麼，我們不關心它是怎麼做到的。舉一個例子：關於一個矩陣的抽象數據類型的定義

為什麼上面就叫做抽象的表示呢？抽象在那裡呢？

首先我們來看，在描述數據對象集的時候，說a是矩陣元素的值，這個值可能是一個float、double也可能是int，我們在這個抽象數據類型描述中間是不關心的。相應地，當需要對它的元素值進行操作的時候，我們返回的是一個通用的elementtype（元素類型），我們在實現這個矩陣相關的所有函數的時候。在頭上寫一個define，你需要什麼，就把它define成什麼樣子，這樣的話，實現這一堆函數，跟你那個矩陣元素到底是哪種類型是沒有關係的，哪一個類型都是可以做運算的，就避免了你對int實現了一遍，對變了矩陣為double類型再實現一遍的麻煩，這是其中一個抽象。

另外是M*N矩陣，我們只是說這是一個M*N矩陣，至於在程序里是怎麼個存法，是用一個二維數組去存它？還是一維數組？還是甚至用一個十字鏈表？這個在抽象數據類型定義的時候，都是不關心的，不管它是怎麼實現的，我只是知道它實現的是一個矩陣。

還有，就是我們在描述Add矩陣加法這個函數的時候，只是說，如果它們可以相加的話，我要返回它們的和，但沒有說在算矩陣加法的時候，到底是先按行加？還是先按列加呢？到底是用什麼語言去實現這個函數呢？統統不管，這就是所謂的抽象。

演算法：

1.一個有限的指令集；

2.接受一些輸入（有些情況下不需要輸入）；

3. 產生輸出；

4.一定在有限步驟之後終止；

5. 每一條指令必須有充分明確的目標，不可以有歧義，要在計算機能處理的範圍之內的；

6. 描述要抽象即描述應不依賴於任何一種計算機語言以及具體的實現手段。

上面的例子就是一個演算法。

什麼是好的演算法？

通常有兩個指標：（時間和空間都是和數據規模n有直接的關係）

1.空間複雜度S(n)---根據演算法寫成的程序在執行時佔用存儲單元的長度。這個長度往往與輸入數據的規模有關。空間複雜度過高的演算法可能導致使用的內存超限，造成程序非正常中斷。

2.時間複雜度T(n)---根據演算法寫成的程序在執行時耗費時間的長度。這個長度往往也與輸入數據的規模有關。時間複雜度過高的低效演算法可能導致我們在有生之年都等不到運行結果。

解決的方法有很多，在設計這個方法的時候，一定要把這兩個要素考慮清楚，一不小心，如果空間複雜度太大的話，程序可能非正常中斷，時間複雜度如果太大的話，你就可能等了太長時間等不出結果。

機器運算加減法的速度比乘除法的速度要快很多

在分析一般演算法的效率時，我們經常關注下面兩種複雜度：1，最壞情況複雜度；平均複雜度。很顯然，平均複雜度要比最壞情況複雜度小。最常用的是最壞情況複雜度。

複雜度的漸進表示法：

當我們在分析一個演算法的複雜度時候，我們沒有必要一步一步去數，說它把哪個操作做了多少次，我們關心的只是說，隨著要處理的數據的規模的增大，它這個複雜度增長的性質會怎麼樣？當我們在比較前面兩個演算法的時候，我們只要知道第一個演算法它的時間複雜度當n很大的時候，基本上就是n平方在起主要作用的，第二個演算法，當n很大的時候，是n在起主要的作用，當n很大的時候，第一個演算法的速度肯定比第二個演算法要慢，知道這個就可以了，所以我們從來不對演算法做非常精細的分析，我們只粗略的知道它的增長趨勢就可以了，於是就有了我們複雜度的『漸進表示法』。

太大的上界和太小的下界，對我們分析演算法的效率是沒有幫助的，我們在分析演算法的效率的時候，總歸希望不管是上界還是下界，都儘可能地跟它的真實情況貼得越近越好，所以我們在寫大O（）的時候，我們一般取的是我們能找到的、最小的那個上界，當我們在寫大Ω（）的時候，通常寫的是我們能力範圍內找到的、最大的那個下屆。

下面的圖表，可以增加一些對不同複雜度函數的感性理解。