[[389761]]

本文轉(zhuǎn)載自微信公眾號(hào)「 牧小農(nóng)」，作者 牧小農(nóng) 。轉(zhuǎn)載本文請(qǐng)聯(lián)系 牧小農(nóng)公眾號(hào)。

一、前言

在可視化化程序設(shè)計(jì)的今天，借助于集成開(kāi)發(fā)環(huán)境可以很快地生成程序，程序設(shè)計(jì)不再是計(jì)算機(jī)專業(yè)人員的專利。很多人認(rèn)為，只要掌握幾種開(kāi)發(fā)工具就可以成為編程高手，其實(shí)，這是一種誤解。要想成為一個(gè)專業(yè)的開(kāi)發(fā)人員，至少需要以下三個(gè)條件：

1) 能夠熟練地選擇和設(shè)計(jì)各種數(shù)據(jù)結(jié)構(gòu)和算法

2) 至少要能夠熟練地掌握一門程序設(shè)計(jì)語(yǔ)言

3) 熟知所涉及的相關(guān)應(yīng)用領(lǐng)域的知識(shí)

其中，后兩個(gè)條件比較容易實(shí)現(xiàn)，而第一個(gè)條件則需要花相當(dāng)?shù)臅r(shí)間和精力才能夠達(dá)到，它是區(qū)分一個(gè)程序設(shè)計(jì)人員水平高低的一個(gè) 重要標(biāo)志，數(shù)據(jù)結(jié)構(gòu) 貫穿程序設(shè)計(jì)的始終 ，缺乏數(shù)據(jù)結(jié)構(gòu)和算法的深厚功底，很難設(shè)計(jì)出高水平的具有專業(yè)水準(zhǔn)的應(yīng)用程序。曾經(jīng)有一本經(jīng)典計(jì)算機(jī)專業(yè)書籍叫做《數(shù)據(jù)結(jié)構(gòu)+算法=程序》，也說(shuō)明了數(shù)據(jù)結(jié)構(gòu)和算法的重要性。

二、為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)

• 數(shù)據(jù)結(jié)構(gòu)是所有計(jì)算機(jī)專業(yè)的同學(xué)必學(xué)的一門課程
• 數(shù)據(jù)結(jié)構(gòu)研究的是數(shù)據(jù)如何在計(jì)算機(jī)中進(jìn)行組織和存儲(chǔ)，使得我們可以高效的獲取數(shù)據(jù)或者修改數(shù)據(jù)

計(jì)算機(jī)專業(yè)的學(xué)生都開(kāi)設(shè)過(guò)數(shù)據(jù)結(jié)構(gòu)課程，它是計(jì)算機(jī)學(xué)科知識(shí)結(jié)構(gòu)的核心和技術(shù)體系的基石。數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課程，是計(jì)算機(jī) 考研 的 必考 科目之一，如果有打算報(bào)考計(jì)算機(jī)專業(yè)的研究生，這門數(shù)據(jù)結(jié)構(gòu)你是必須要學(xué)好它的，同時(shí)，工作以后的同學(xué)，會(huì)有想去報(bào)考計(jì)算機(jī) 軟考 、計(jì)算機(jī) 等級(jí)考試 的，數(shù)據(jù)結(jié)構(gòu)也是必考的內(nèi)容之一，科學(xué)技術(shù)在飛速發(fā)展，但是作為基石的科學(xué)技術(shù)沒(méi)有動(dòng)搖，由于近年來(lái)算法工程師的高薪火爆，使得數(shù)據(jù)結(jié)構(gòu)的重視程序空前高漲，總而言之，既然我們已經(jīng)與計(jì)算機(jī)接軌就必須 掌握 好它。

三、數(shù)據(jù)結(jié)構(gòu)無(wú)處不在

不管你是IT開(kāi)發(fā)，還是其他崗位的工作人員，或者是游戲愛(ài)好者，只要你用過(guò)電腦，那么你就接觸過(guò)數(shù)據(jù)結(jié)構(gòu)，下面我們就來(lái)講一講，數(shù)據(jù)結(jié)構(gòu)究竟是如何 無(wú)處不在 的。

3.1 數(shù)據(jù)庫(kù)

不管你是從事IT工作的，還是準(zhǔn)備從事IT開(kāi)發(fā)的，數(shù)據(jù)庫(kù)一定是了解的，我們知道，數(shù)據(jù)庫(kù)查詢是數(shù)據(jù)庫(kù)的最主要功能之一。我們都希望查詢數(shù)據(jù)的速度能盡可能的快，因此數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者會(huì)從查詢算法的角度進(jìn)行優(yōu)化。最基本的查詢算法當(dāng)然是順序查找(linearsearch)，這種復(fù)雜度為 O(n)的算法在數(shù)據(jù)量很大時(shí)顯然是糟糕的，好在計(jì)算機(jī)科學(xué)的發(fā)展提供了很多更優(yōu)秀的查找算法，例如 二分查找(binary search)、二叉樹查找(binary tree search)等。如果稍微分析一下會(huì)發(fā)現(xiàn)，每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)，所以，在數(shù)據(jù)之外，數(shù)據(jù)庫(kù)系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用(指向)數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級(jí)查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是 索引 ，索引是一種幫助MySQL高效獲取數(shù)據(jù)的 排好序 的 數(shù)據(jù)結(jié)構(gòu)，其中MySQL使用的數(shù)據(jù)結(jié)構(gòu)為B+Tree。

3.2 操作系統(tǒng)

相信現(xiàn)在的我們常用的操作系統(tǒng)大家一定都知道吧，例如：比爾蓋茨大叔成立的微軟的 Windows操作系統(tǒng)，大神喬布斯蘋果的 MacOS，Java開(kāi)發(fā)常用的 Linux系統(tǒng)，由林納斯·本納第克特·托瓦茲開(kāi)發(fā)(百度來(lái)的)，還有redhat、Solaris、SunCobalt等等，都有使用到數(shù)據(jù)結(jié)構(gòu)中的，系統(tǒng)棧以及優(yōu)先隊(duì)列：堆

3.3 文件壓縮

比如：RAR壓縮軟件、PNG圖片、MAP3文件等等，都會(huì)使用數(shù)據(jù)結(jié)構(gòu)，對(duì)數(shù)據(jù)進(jìn)行壓縮(很怕打成了亞索，心虛)，而使用壓縮的算法是一種樹結(jié)構(gòu)叫 哈夫曼樹 。

3.4 游戲

1) 數(shù)組：需處理的元素個(gè)數(shù)確定并且需使用下標(biāo)時(shí)可以考慮，不過(guò)建議用泛型List 優(yōu)點(diǎn)：數(shù)組在內(nèi)存中是連續(xù)存儲(chǔ)的，索引和修改的速度都非常快 缺點(diǎn)：插入和刪除很慢，長(zhǎng)度開(kāi)辟過(guò)長(zhǎng)易造成內(nèi)存浪費(fèi)，長(zhǎng)度開(kāi)辟過(guò)短易造成內(nèi)存越界

2) List：List是泛型的，即List，需處理的元素個(gè)數(shù)可以不確定，不存在裝箱與拆箱，建議多用;而ArrayList：ArrayList list1 = new ArrayList(); ArrayList的元素屬于 object 類型存在裝箱與拆箱，很損耗性能。,List的底層數(shù)據(jù)結(jié)構(gòu)就是數(shù)組。

List<string> list = new List<string>(); 
 
//新增數(shù)據(jù) 
 
list.Add(“abc”);  
 
//修改數(shù)據(jù) 
 
list[0] = “def”;  
 
//移除數(shù)據(jù) 
 
list.RemoveAt(0);  
 
//錯(cuò)誤操作，因?yàn)閿?shù)據(jù)的類型不是string 
 
list.add(123); 

3) 鏈表：常用來(lái)維護(hù)、管理那些需要頻繁產(chǎn)生、消除的游戲?qū)ο螅热纾合愑螒蛑行枰膶?duì)象。

4) HashMap：底層是哈希表，是鍵值對(duì)容器，用于處理key/value鍵值對(duì);底層使用的是數(shù)組+鏈表的結(jié)構(gòu)：Map

6) 圖：A*尋路算法、DFS、BFS

游戲也是采用了大量的算法，都需要以數(shù)據(jù)結(jié)構(gòu)為基石，就最簡(jiǎn)單的功能尋路，鼠標(biāo)從A點(diǎn)到B點(diǎn)，這個(gè)角色就需要尋找一條從A點(diǎn)到B點(diǎn)的路，這條路還需要繞過(guò)所有的障礙物，甚至還需要找出最短的路徑，這就是最經(jīng)典的 圖論算法，在圖論算法中就使用了大量的數(shù)據(jù)結(jié)構(gòu)。

四、數(shù)據(jù)結(jié)構(gòu)類型

在計(jì)算機(jī)領(lǐng)域有一句名言 數(shù)據(jù)結(jié)構(gòu)+算法=程序，而數(shù)據(jù)結(jié)構(gòu)本身就是算法的基石，在近乎任何一本算法教材，都花了大量的時(shí)間講解數(shù)據(jù)結(jié)構(gòu)，學(xué)好數(shù)據(jù)結(jié)構(gòu)和算法可以讓我們?cè)谟?jì)算機(jī)這條道路上走的更遠(yuǎn)。如果數(shù)據(jù)結(jié)構(gòu)是因?yàn)樗鼰o(wú)處不在，學(xué)好數(shù)據(jù)結(jié)構(gòu)是使我們快速成長(zhǎng)的墊腳石。

在接下面的幾篇文章中，我會(huì)為大家更新數(shù)據(jù)結(jié)構(gòu)中：數(shù)組、棧、隊(duì)列、鏈表、二分搜索樹、堆、線段樹、Trie、并查集、紅黑樹以及哈希表等等...的詳細(xì)講解，感興趣的同學(xué)記得關(guān)注我，我是牧小農(nóng)，我喂自己帶鹽。