程序設(shè)計的本質(zhì)是對確定問題選擇一個好的數(shù)據(jù)結(jié)構(gòu)，加上設(shè)計一個好的算法，程序設(shè)計 = 數(shù)據(jù)結(jié)構(gòu) + 算法
本文出自門心叼龍的博客，屬于原創(chuàng)類容，轉(zhuǎn)載請注明出處。https://menxindiaolong.blog.csdn.net/article/details/96620117
上個月我在公司面試了兩個Android程序員，都是工作了四五年的程序員，面試一開始就問到了數(shù)據(jù)結(jié)構(gòu)問題，常用的數(shù)據(jù)結(jié)構(gòu)都有哪些？小伙子直接說數(shù)據(jù)結(jié)構(gòu)在自己平時開發(fā)的時候根本就用不上。
在我們?nèi)粘ｉ_發(fā)過程中，很多時候只關(guān)注界面和用戶體驗，對數(shù)據(jù)結(jié)構(gòu)和算法這塊要求并不高，很多程序員codeing能力很強，但一問到一些底層基礎(chǔ)知識就發(fā)蒙，很多程序員抱怨面試造飛機，實際工作擰螺絲，面試問的基礎(chǔ)知識與實際工作毫無聯(lián)系，但公司的真正目的是在考察你的基本功，以此來判斷你之后能否成長為他們最終需要的高級人才，數(shù)據(jù)結(jié)構(gòu)與算法這是編程基礎(chǔ)，基礎(chǔ)不牢，地動山搖。
可能有些人會質(zhì)疑：數(shù)據(jù)底層存儲結(jié)構(gòu)都不理解，codeing能力能很強？其實這也見怪不怪，就好比有人他的開車技術(shù)很高超，開的很溜，但是發(fā)動機的工作原理它懂嗎？他不懂，但是他車開的確實很好，寫程序也是一樣的道理，有的程序員他就停留在用的階段，用的很熟練，但是底層原理他不一定知道，再之干這一樣非科班出身、轉(zhuǎn)行做技術(shù)的程序員也不在少數(shù)，有的培訓(xùn)機構(gòu)出來的，他們不一定都會先去專業(yè)的去學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法，這就會導(dǎo)致有些人工作好幾年了，但是對數(shù)據(jù)結(jié)構(gòu)這塊的知識還是一知半解。
在去年的9月份，阿里巴巴搞了一個全球數(shù)學(xué)競賽，一石激起千層浪，各路豪杰紛紛參戰(zhàn)，移動互聯(lián)網(wǎng)的狂潮已經(jīng)結(jié)束了，下一個風(fēng)口將是人工智能，搞人工智能就離不開數(shù)學(xué)算法，阿里醉翁之意不在酒，而在搶奪全球的頂尖級數(shù)學(xué)人才，可見算法的重要性。
在后移動互聯(lián)網(wǎng)時代我的一些思考這篇文章我曾說過，初級程序員寫UI，中級程序員寫框架，高級程序員寫算法，寫程序?qū)懙阶詈蠖际窃趯懰惴?，程序員最后拼的都是算法，在人類發(fā)展的歷史長河中，我們的前輩給我們留下了很多很經(jīng)典的算法，這都是人類智慧的結(jié)晶，有人寫了一篇文章細數(shù)二十世紀最偉大的10大算法，感興趣的可以去看一看。既然數(shù)據(jù)結(jié)構(gòu)和算法這么重要，那么今天我決定寫一篇關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的入門文章，起到拋磚引玉的作用，希望你能夠喜歡上數(shù)據(jù)結(jié)構(gòu)和算法。
什么是數(shù)據(jù)
說到數(shù)據(jù)我們很容易就會想到：整型，浮點型，還包括音頻，視頻，圖像，這都是數(shù)據(jù)，整型，浮點型可以進行數(shù)值運算，音頻，視頻，圖像數(shù)據(jù)可以通過編碼手段手段變成字符數(shù)據(jù)來處理，他們都有一個共同的特點，可以輸入到計算機當中，能被計算機程序處理。
什么是數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，這是數(shù)據(jù)結(jié)構(gòu)的概念，我們可以概括為四個字就是“數(shù)據(jù)集合”，他是一堆數(shù)據(jù)，而不是一個數(shù)據(jù)，另外數(shù)據(jù)和數(shù)據(jù)之間存在一定的關(guān)系，這種關(guān)系是指一對一的關(guān)系，或一對多的關(guān)系，或者多對對的關(guān)系，編寫一個好的程序必須要分析待處理數(shù)據(jù)對象的特性以及各處理數(shù)據(jù)對象之間存在的關(guān)系，這也是就研究數(shù)據(jù)結(jié)構(gòu)的意義所在。
數(shù)據(jù)結(jié)構(gòu)的分類
數(shù)據(jù)結(jié)構(gòu)分為邏輯機構(gòu)和物理結(jié)構(gòu)
邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間存在的關(guān)系
-
1.集合結(jié)構(gòu)：集合結(jié)構(gòu)中的元素除了屬于一個集合之外，他們之間沒有其他的關(guān)系，各個數(shù)據(jù)元素是平等的，他們共同的屬性就是“屬于同一個集合”
在這里插入圖片描述 -
2.線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對一的關(guān)系
在這里插入圖片描述 -
3.樹形結(jié)構(gòu)：樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間是一種一對多的層次關(guān)系
在這里插入圖片描述 -
4.圖形結(jié)構(gòu)：圖形結(jié)構(gòu)中的數(shù)據(jù)元素之間是一種多對多的關(guān)系
在這里插入圖片描述
物理結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲形式
-
1.順序存儲結(jié)構(gòu)：是把元素存在地址連續(xù)的存儲單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的，這種數(shù)據(jù)結(jié)構(gòu)很簡單，就是排隊站位，大家都按照順序排好，每個人占一小段空間，大家誰也別插誰的隊，數(shù)組就是這樣的數(shù)據(jù)結(jié)構(gòu)。當你告訴計算機，你要建立一個有9個元素的數(shù)組時，計算式就在內(nèi)存中找了片空地，按照一個整形所占位置的大小乘以9，開辟一段連續(xù)的內(nèi)存空間，于是第一個數(shù)組元素就放在第一個位置，第二個元素放在第二個位置，這樣依次擺放。
在這里插入圖片描述 - 2.鏈式存儲結(jié)構(gòu)
在日常生活有很多這樣的情況，我們?nèi)ャy行辦理業(yè)務(wù)，或者去火車站去買票，都有這樣的經(jīng)歷，一會兒有人插隊，一會兒有人上廁所放棄排隊，這樣隊伍當中就會添加新的成員，也有可能去掉老的元素，整個結(jié)構(gòu)時刻都處于變化當中，顯然，面對這樣時長要變化的數(shù)據(jù)結(jié)構(gòu)，順序存儲是不科學(xué)的。
于是現(xiàn)在的銀行，醫(yī)院等地方，設(shè)置了排隊系統(tǒng)，也就是每個人去了，先領(lǐng)一個號，等著叫號，叫到時再去辦理業(yè)務(wù)或看病。在等待的時候，你愛在哪在哪，可以坐著，可以站著，甚至可以出去轉(zhuǎn)一圈，只要及時回來就可以，你關(guān)注的是前一個號有沒有叫到，叫到了，下一個就輪到你了。
而鏈式結(jié)構(gòu)和上面據(jù)的例子非常的類似，把數(shù)據(jù)元素存儲在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。數(shù)據(jù)元素的存儲關(guān)系并不能反映數(shù)據(jù)元素的邏輯關(guān)系，因此需要一個指針在存儲元素的地址，這樣通過地址就可以找到相關(guān)聯(lián)數(shù)據(jù)元素的位置。很顯然，鏈式存儲就靈活多了， 數(shù)據(jù)存在哪里并不重要，只要有一個指針存放了相應(yīng)的地址就能找到它了。
邏輯結(jié)構(gòu)是面向問題的，而物理結(jié)構(gòu)是面向計算機的，其基本的目標就要要把數(shù)據(jù)及邏輯關(guān)系存儲存儲到計算機內(nèi)存當中。
數(shù)據(jù)類型
上面我們談到了數(shù)據(jù)的存儲問題，在計算機當中，內(nèi)存也不是無限大的，你要計算一個1+1=2這樣的整形數(shù)字的加法問題，顯然不需要開辟很大的內(nèi)存空間，于是就需要對數(shù)據(jù)進行分類，不同的數(shù)據(jù)類型占用了不同的存儲空間大小。
java中八種基本數(shù)據(jù)類型所分配的存儲空間大?。?/p>
基本數(shù)據(jù)類型的取值范圍：
算法
講完了數(shù)據(jù)結(jié)構(gòu)的概念和分類，我們再來看看什么是算法，我們都聽過高斯的故事，高斯9歲的時候，用很短的時間計算出了小學(xué)老師布置的任務(wù)：對自然數(shù)從1到100的求和。他所使用的方法是：對50對構(gòu)造成和為101的數(shù)列求和（1+100，2+99，3+98……），同時得到結(jié)果：5050，高斯的求解的過程就是算法實現(xiàn)的過程，算法即“計算方法”，是解決特定問題所需要的步驟，在計算機中表現(xiàn)為指令的有限序列，每條指令表示一個或者多個操作。
int sum = 0;
for(int i = 0; i < = 100; i++) {
sum += i;
}
上面這段代碼就是1到100求和在計算機中的求解過程
算法特性
算法具有五個基本特性：輸入、輸出、有窮性、確定性和可行性，輸入和出處比較容易理解的
- 輸入：算法具有零個或者多個輸入
- 輸出：算法至少有一個或者多個輸出。
- 有窮性：是指算法在執(zhí)行有限的步驟之后，自動結(jié)束而不會出現(xiàn)無限循環(huán)，并且每一個步驟都在可以接受的時間內(nèi)完成
- 確定性：算法的每一步都有確定的含義，不會產(chǎn)生二義性
- 可行性：算法的每一步都能通過有限的次數(shù)完成
算法的性能
衡量一個算法好壞的標準就是算法復(fù)雜度，算法復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度，時間復(fù)雜度是指執(zhí)行算法所需要的時間 ；而空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。
1. 時間復(fù)雜度：
- 常數(shù)階：
int num = 0，n = 100;
sum = (1+n)*n/2;
System.out.println("value:"+sum);
無論n為多少，這段程序的執(zhí)行次數(shù)始終是3，所以他的時間復(fù)雜度為常數(shù)階：O(1)
- 線性階：
for(int i = 0; i < n ; i++){
System.out.println("value:"+i);
}
這段代碼，他的循環(huán)時間復(fù)雜度為O(n),因為循環(huán)體中的代碼需要執(zhí)行n次
- 對數(shù)階：
int count = 1；
while(count < n){
count = count * 2;
}
由于每次count乘以2之后，就距離n更近了一些，也就是說，有多少個2相乘以后大于n，則會退出循環(huán)，2的x次方 = n 得到 x = log2n，所以這個循環(huán)的復(fù)雜度為O(logn);
- 平方階
int i ,j;
for(i = 0; i < n ; i++){
for(j = 0; j < n ; j++){
System.out.println("");
}
}
外層循環(huán)的次數(shù)為n次，外層每循環(huán)一次內(nèi)層循環(huán)的次數(shù)為n次，所以這段代碼的時間復(fù)雜度為O(n2)
常見的時間復(fù)雜度列表
| 名稱 | 運行時間 |
|---|---|
| 常數(shù)階 | O(1) |
| 對數(shù)階 | O(logn) |
| 線性階 | O(n) |
| nlogn階 | O(nlogn) |
| 平方階 | O(n2) |
| 立方階 | O(n3) |
| 指數(shù)階 | O(2?) |
常用的時間復(fù)雜度所耗費的時間由小到大依次是：
O(1) <O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2?)
2. 空間復(fù)雜度：
空間復(fù)雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度，記做S(n)=O(f(n))。比如直接插入排序的時間復(fù)雜度是O(n^2),空間復(fù)雜度是O(1) 。而一般的遞歸算法就要有O(n)的空間復(fù)雜度了，因為每次遞歸都要存儲返回信息。一個算法的優(yōu)劣主要從算法的執(zhí)行時間和所需要占用的存儲空間兩個方面衡量。
3.時間復(fù)雜度和空間復(fù)雜度的相互關(guān)系
對于一個算法，時間復(fù)雜度和空間復(fù)雜度往往是相互影響的。當追求一個較好的時間復(fù)雜度時，可能會使空間復(fù)雜度的性能變差，即可能導(dǎo)致占用較多的存儲空間；反之，當追求一個較好的空間復(fù)雜度時，可能會使時間復(fù)雜度的性能變差，即可能導(dǎo)致占用較長的運行時間。另外，算法的所有性能之間都存在著或多或少的相互影響。因此，當設(shè)計一個算法(特別是大型算法)時，要綜合考慮算法的各項性能，算法的使用頻率，算法處理的數(shù)據(jù)量的大小，算法描述語言的特性，算法運行的機器系統(tǒng)環(huán)境等各方面因素，才能夠設(shè)計出比較好的算法。
數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系
數(shù)據(jù)結(jié)構(gòu)是算法實現(xiàn)的基礎(chǔ)，算法總是要依賴于某種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的。往往是在發(fā)展一種算法的時候，構(gòu)建了適合于這種算法的數(shù)據(jù)結(jié)構(gòu)。 算法的操作對象是數(shù)據(jù)結(jié)構(gòu)。算法的設(shè)計和選擇要同時結(jié)合數(shù)據(jù)結(jié)構(gòu)，簡單地說數(shù)據(jù)結(jié)構(gòu)的設(shè)計就是選擇存儲方式。算法設(shè)計的實質(zhì)就是對實際問題要處理的數(shù)據(jù)選擇一種恰當?shù)拇鎯Y(jié)構(gòu)，并在選定的存儲結(jié)構(gòu)上設(shè)計一個好的算法。算法設(shè)計必須考慮到數(shù)據(jù)結(jié)構(gòu)，算法設(shè)計是不可能獨立于數(shù)據(jù)結(jié)構(gòu)的。
常見的數(shù)據(jù)結(jié)構(gòu)
1.線性表
| 存儲方式 | 概念 | 時間性能 | 空間性能 |
|---|---|---|---|
| 順序存儲 | 一段連續(xù)的存儲單元 | 查找快，插入慢，刪除慢 查找：常數(shù)階O(1) 插入：線性階O(n) 刪除：線性階O(n) |
需要事先分配存儲空間 分大了浪費，分小了容易溢出 |
| 鏈式存儲 | 一組任意的存儲單元 | 查找慢，插入快，刪除快 查找：線性階O(n) 插入：常數(shù)階O(1) 刪除：常數(shù)階O(1) |
有需要的時候分配存儲空間 元素個數(shù)不受限制 |
2.棧和隊列
| 存儲方式 | 概念 | 時間性能 | 空間性能 |
|---|---|---|---|
| 棧 | 只能在表尾進行 添加和刪除的線性數(shù)據(jù)結(jié)構(gòu) |
根據(jù)存儲結(jié)構(gòu)決定 | 根據(jù)存儲結(jié)構(gòu)決定 |
| 隊列 | 只能在一端進行插入操作 另一端進行刪除操作的線性數(shù)據(jù)結(jié)構(gòu) |
根據(jù)存儲結(jié)構(gòu)決定 | 根據(jù)存儲結(jié)構(gòu)決定 |
3.樹
前面我們一直在講一對一的線程數(shù)據(jù)結(jié)構(gòu)，現(xiàn)實中還有很多一對多的情況，具有一定層次關(guān)系的數(shù)據(jù)元素的集合就是樹，我覺得如果你不是做很底層的開發(fā)（比如操作系統(tǒng)文件管理，數(shù)據(jù)庫之類的），也不是專門搞算法的，用處不會很大，事實上很多高級樹結(jié)構(gòu)都是為了數(shù)據(jù)庫而開發(fā)的，因為數(shù)據(jù)庫要很高的效率。
4.圖
在線性表中，數(shù)據(jù)元素之間是被串起來的，僅有線性關(guān)系，每個元素只有一個直接前驅(qū)和直接后繼。在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有明顯的層次關(guān)系并且每一層上的數(shù)據(jù)元素可能和下一層多個元素有關(guān)，但只能和上一層中的一個元素相關(guān)。這和一對父母可以有多個孩子，但每個孩子卻只能有一對父母是一個道理?？涩F(xiàn)實中，人與人之間的關(guān)系非常復(fù)雜，比如我認識的朋友，他們之間也可能相互認知，這就不是簡單的一對一，一對多的關(guān)系了，研究人際關(guān)系自然會考慮多對多的情況，這種數(shù)據(jù)結(jié)構(gòu)就是圖，圖是一種比線性表和樹更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，在圖的數(shù)據(jù)結(jié)構(gòu)中，節(jié)點之間的關(guān)系可以是任意的，圖中的任意兩個元素之間都有可能有關(guān)。
Java數(shù)據(jù)結(jié)構(gòu)框架類圖
1.單列表
2.雙列表
我們在前面提到的集合其實是有很多用途的，散列表也算是集合的一種，為什么需要散列表呢？實際上順序存儲結(jié)構(gòu)需要一個一個的按順序訪問元素，當數(shù)據(jù)總量比較大，而且這個元素比較靠后的，性能就會降低。那么散列表是一種空間換時間的存儲結(jié)構(gòu)，我們想一下，若在手機的通訊錄中查找一個人，那我們應(yīng)該不會從第一個人一直找下去，因為這樣實在太慢了。我們其實是這樣做的，首先看這個人的首字母是什么，比如姓張，那么我們一定會滑倒最后，因為“Z”姓的名字都在后面，還有在查字典時，要查找一個單詞，肯定不會從頭翻到尾，而是首先通過這個單詞的首字母，找到第二個字母，第三個字母......這樣可以快速的跳到那個單詞所在的頁。其實這就是散列表的思想，散列表，又叫哈希表，是能夠通過給定的關(guān)鍵字的值直接訪問到具體對應(yīng)值得一個數(shù)據(jù)結(jié)構(gòu)。也就是說，把關(guān)鍵字映射到一個表中的位置來直接訪問記錄，以加快訪問的速度。
總結(jié)
我們從數(shù)據(jù)，數(shù)據(jù)結(jié)構(gòu)，算法，數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系，常見的數(shù)據(jù)結(jié)構(gòu)，Java數(shù)據(jù)結(jié)構(gòu)框架這六個方面，循序漸進把把數(shù)據(jù)結(jié)構(gòu)和算法基本就講完了，大家也有個大致的了解，其實數(shù)據(jù)結(jié)構(gòu)和算法涉及到的知識點遠遠不止這一點，我只是挑了一些工作實戰(zhàn)中常用的數(shù)據(jù)結(jié)構(gòu)講了一下，以后還需要大量的算法練習(xí)來提升自己的算法內(nèi)功修煉，做了這么多年技術(shù)，我一直在思考，我們每天在codeing到底在做什么？其實程序設(shè)計的本質(zhì)是對確定問題選擇一個好的數(shù)據(jù)結(jié)構(gòu)，加上設(shè)計一個好的算法，就這么簡單，程序設(shè)計 = 數(shù)據(jù)結(jié)構(gòu) + 算法。
