算法與數(shù)據(jù)結(jié)構(gòu)無廢話筆記（一）

??算法與數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)學(xué)生的必修課，基礎(chǔ)中的基礎(chǔ)，所以快速上手，找到學(xué)習(xí)方向和感覺十分重要。我在學(xué)習(xí)過程中遇到一本好書，《我的第一本算法書》，把算法講得很淺顯易懂，所以基于這本書的內(nèi)容，提煉出其中的精華，再加上個人的理解，旨在把最干的干貨分享給大家。推薦大家去閱讀原書！

算法簡介

算法就是計算或者解決問題的步驟。我們可以把它想象成食譜。要想做出特定的料理，就要遵循食譜上的步驟；同理，要想用計算機解決特定的問題，就要遵循算法。但是食譜有時是模糊的， 而算法是嚴謹?shù)模悄苡脭?shù)學(xué)明確描述的。

算法和程序有些相似，區(qū)別在于程序是以計算機能夠理解的編程語言編寫而成的，可以在計算機上運行，而算法是以人類能夠理解的方式描述的，用于編寫程序之前。不過，在這個過程中到哪里為止是算法、從哪里開始是程序，并沒有明確的界限。

就算使用同一個算法，編程語言不同，寫出來的程序也不同；即便使用相同的編程語言，寫程序的人不同，那么寫出來的程序也是不同的。

我們要用計算機能理解的方式構(gòu)思解法，計算機擅長高速執(zhí)行一些基本命令，但無法執(zhí)行復(fù)雜的命令。此處的“基本命令”指的是 “做加法”或者“在指定的內(nèi)存地址上保存數(shù)據(jù)”等。 計算機是以這些基本命令的組合為基礎(chǔ)運行的，面對復(fù)雜的操作，也是通過搭配組合這些基本命令來應(yīng)對的。

如何選擇算法

算法的不同會導(dǎo)致其運行時間產(chǎn)生大幅變化，用時間復(fù)雜度（是一個可以描述算法運行時間的函數(shù)，常用大O符號來表述。）表示。我們使用“步數(shù)”來描述運行時間?！? 步”就是計算的基本單位。通過測試“計算從開始到結(jié)束總共執(zhí)行了多少步”來求得算法的運行時間。

下面對這個數(shù)列進行一個排序算法：

計n為數(shù)列長度，Tc為比較一次的時間，Ts為交換一次的時間，則這個排序算法的時間為：

Tc 和 Ts 都是基本單位，與輸入無關(guān)。會根據(jù)輸入變化而變化的只有數(shù)列的長度 n，所以接下來只考慮 n 變大的情況。

通過這種表示方法，我們就能大致了解到排序算法的運行時間與輸入數(shù)據(jù)量 n 的平方成正比。

當我們知道選擇排序的時間復(fù)雜度為 O(n2)、快速排序的時間復(fù)雜度為 O(nlogn) 時，很 快能判斷出快速排序的運算更為高速。二者的運行時間根據(jù)輸入 n 產(chǎn)生的變化程度也一目了然。

數(shù)據(jù)結(jié)構(gòu)簡介

數(shù)據(jù)存儲于計算機的內(nèi)存中。內(nèi)存如右圖所示，形似排成 1 列的箱 子，1 個箱子里存儲 1 個數(shù)據(jù)。 數(shù)據(jù)存儲于內(nèi)存時，決定了數(shù)據(jù)順序和位置關(guān)系的便是“數(shù)據(jù)結(jié)構(gòu)”。

電話簿的數(shù)據(jù)結(jié)構(gòu)：

1. 從上往下順序添加。
2. 按姓名的拼音順序排列。

數(shù)據(jù)按獲取順序排列的話，雖然添加數(shù)據(jù)非常簡單，只需要把數(shù)據(jù)加在最后就可以了，但是在查詢時較為麻煩；以拼音順序來排列的話，雖然在查詢上較為簡單，但是添加數(shù)據(jù)時又會比較麻煩。

3. 將獲取順序與拼音順序結(jié)合起來。
   分別使用不同的表存儲不同的拼音首字母，因為各個表中存儲的數(shù)據(jù)依舊是沒有規(guī)律的，所以查詢時仍需從表頭開始找起，但比查詢整個電話簿來說還是要輕松多了。

將數(shù)據(jù)存儲于內(nèi)存時，根據(jù)使用目的選擇合適的數(shù)據(jù)結(jié)構(gòu)，可以提高內(nèi)存的利用率。數(shù)據(jù)在內(nèi)存中是呈線性排列的，但是我們也可以使用指針等道具，構(gòu)造出類似“樹形”的復(fù)雜結(jié)構(gòu)。

鏈表

鏈表是數(shù)據(jù)結(jié)構(gòu)之一，其中的數(shù)據(jù)呈線性排列。在鏈表中，數(shù)據(jù)的添加和刪除都較為方便，就是訪問比較耗費時間。跟電話簿第一種same。

在鏈表中，數(shù)據(jù)一般都是分散存儲于內(nèi)存中的，無須存儲在連續(xù)空間內(nèi)。因為數(shù)據(jù)都是分散存儲的，所以如果想要訪問數(shù)據(jù)，只能從第1個數(shù)據(jù)開始，順著指針的指向一一往下訪問（這便是順序訪問），所以不利于訪問，但很方便增減。

下面為順序訪問，增加數(shù)據(jù)

刪除黃色時，繞過它就行，雖然 Yellow 本身還存儲在內(nèi)存中，但是不管從哪里都無法訪問這個數(shù)據(jù)，所以也就沒有特意去刪除它的必要了。今后需要用到Y(jié)ellow所在的存儲空間時，只要用新數(shù)據(jù)覆蓋掉就可以了。

數(shù)組

數(shù)組也是數(shù)據(jù)呈線性排列的一種數(shù)據(jù)結(jié)構(gòu)。與前一節(jié)中的鏈表不同，在數(shù)組中，訪問數(shù)據(jù)十分簡單，而添加和刪除數(shù)據(jù)比較耗工夫。與電話簿第二種same！

棧

棧也是一種數(shù)據(jù)呈線性排列的數(shù)據(jù)結(jié)構(gòu)，不過在這種結(jié)構(gòu)中，我們只能訪問最新添加的數(shù)據(jù)。后進先出LIFO。

棧只能在一端操作這一點看起來似乎十分不便，但在只需要訪問最新數(shù)據(jù)時，使用它就比較方便了。

隊列

隊列中的數(shù)據(jù)也呈線性排列。雖然與棧有些相似，但隊列中添加和刪除數(shù)據(jù)的操作分別是在兩端進行的。就和“隊列”這個名字一樣，把它想象成排成一隊的人更容易理解。在隊列中，處理總是從第一名開始往后進行，而新來的人只能排在隊尾。先進先出FIFO。

哈希表

在哈希表這種數(shù)據(jù)結(jié)構(gòu)中，使用之后介紹的“哈希函數(shù)”，可以使數(shù)據(jù)的查詢效率得到顯著提升。

所以很像電話簿第三種情況，用多個鏈表來存儲，鏈表之中順序訪問。

堆

堆是一種圖的樹形結(jié)構(gòu)，被用于實現(xiàn)“優(yōu)先隊列”（priority queues），優(yōu)先隊列是一種數(shù)據(jù)結(jié)構(gòu)，可以自由添加數(shù)據(jù)，但取出數(shù)據(jù)時要從最小值開始按順序取出。在堆的樹形結(jié)構(gòu)中，各個頂點被稱為“結(jié)點”（node），數(shù)據(jù)就存儲在這些結(jié)點中。

如果需要頻繁地從管理的數(shù)據(jù)中取出最小值，那么使用堆來操作會非常方便。

二叉查找樹

二叉查找樹（又叫作二叉搜索樹或二叉排序樹）是一種數(shù)據(jù)結(jié)構(gòu)，采用了圖的樹形結(jié)構(gòu)。

所以二叉查找樹的最小結(jié)點要從頂端開始，往其左下的末端尋找。反過來，二叉查找樹的最大結(jié)點要從頂端開始，往其右下的末端尋找。

查找也同理，小于就往左找，大于就往右找。

下一篇 ！加油！