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

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

算法簡(jiǎn)介

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

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

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

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

如何選擇算法

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

下面對(duì)這個(gè)數(shù)列進(jìn)行一個(gè)排序算法：

計(jì)n為數(shù)列長(zhǎng)度，Tc為比較一次的時(shí)間，Ts為交換一次的時(shí)間，則這個(gè)排序算法的時(shí)間為：

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

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

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

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

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

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

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

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

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

將數(shù)據(jù)存儲(chǔ)于內(nèi)存時(shí)，根據(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ù)的添加和刪除都較為方便，就是訪問比較耗費(fèi)時(shí)間。跟電話簿第一種same。

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

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

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

數(shù)組

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

棧

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

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

隊(duì)列

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

哈希表

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

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

堆

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

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

二叉查找樹

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

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

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

下一篇 ！加油！