浙江大學-數據結構-基本概念 什麼是數據結構-1.1.1(補前面的章節)

來自專欄 Excalibur

由於第一章比較簡單，就不會寫的很詳細了...

什麼是數據結構

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

問題：空間如何分配？類別應該分多細？

遞歸函數跑出來的結果，前面100000是輸入，它什麼都沒做，直接罷工了。到底發生了什麼？遞歸程序對空間的佔用是很恐怖的。。。

為什麼說第二種演算法比第一種要好呢？因為第一種演算法慢很多

這兩個函數跑的實在是太快了，解決方法就是在循環中重複多跑幾次

第一個演算法比第二個演算法慢了一個數量級的樣子

什麼是邏輯結構，比如說我們一開始把書架想像成一個一長條一層的架子，然後所有的書是一個挨著一個放的，除了一頭一尾的書以外呢，每一本書它前面只有一本書，後面只有一本書，如果我給每一本書有一個編號的話，那麼這一個編號對應的就是一本書，那麼這種結構呢是一對一的結構，我們管它叫線性結構，另外一種組織方式，是我們的第三個方法，就是先把圖書來分類，那如果我給每一類一個編號的話，那麼這一個類別的編號裡面對應著很多本書，那麼這是一個一對多的邏輯結構，那這種結構有個名字叫作樹，樹(一對多)，前面講的就是線性結構和樹型結構。後面就會講圖，假設我們還會統計這些信息，這本書都會有哪些人買過？買了這本書的人他還買過其它的什麼書？於是呢，其實就是一本書對應著很多人，而一個人又對應了很多本書，這是一個多對多的很複雜的關係網，那麼這個關係網對應的就是一個圖的結構，除了邏輯結構之外，我們還有數據對象在計算機裡面的物理存儲結構，我們說的這些邏輯結構在機器的內存裡面到底要怎麼樣一個放法，是連續放呢？還是東一個，西一個隔開放呢？也就是用一個數組來存它呢？還是用一個鏈表來存它呢？這個就屬於物理存儲結構

數據對象集就是我們在說的什麼東西，第二個是數據集合相關聯的操作集，就像我們說不能單純的講怎麼去處理圖書，我們是要對這些圖書去做操作的，這兩件事情，圖書的擺放跟它的操作是緊密結合在一起的，那麼這兩個東西在C語言裡頭，它們是獨立處理的，但是在一些面向對象的語言裡面，你就會發現它們很好的為數據類型專門設計了機制，就是一個類把數據集跟它相關的操作集封裝在一個類裡面

在描述數據對象集的時候，我們說a是矩陣元素的值，這個值是個什麼值呢？它是一個float,還是一個double,還是int,我們在抽象數據類型描述中間是不關心的，相應的當需要對它的元素值進行操作的時候，我們返回的也是ElementType,實現的函數跟矩陣元素到底是哪種類型是沒有關係的，哪種類型都是可以做運算的，就避免了你對int實現了一遍，又要對double重新寫一遍，當然說可以將所有的int全部換成double, 但有些時候的int是真的int,不能換成double,所以就很有可能出錯，總的來說，就是一個一個的去替換元素的類型的話，會是一件很麻煩的事情，而抽象一下就是有這個好處，這是一個地方的抽象，另外像這個矩陣，我們只是說M*N的矩陣，至於在程序裡面怎麼樣一個存法，我們是用二維數組去存它，還是一維數組，還是十字鏈表，這個我們在抽象數據類型定義的時候，都是不關心的，我不管它是怎麼實現的，我只是說我要實現的是一個矩陣，另外我在描述這個Add,矩陣加法這個函數的時候，我只是說如果它們可以相加的話，我要返回它們的和，那我可沒說在算矩陣加法的時候，到底是先按行加，還是先按列加，我到底是用什麼語言去實現？通通不管，這就是所謂的抽象。