[[389761]]

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

一、前言

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

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

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

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

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

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

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

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

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

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

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

不管你是從事IT工作的，還是準備從事IT開發(fā)的，數(shù)據(jù)庫一定是了解的，我們知道，數(shù)據(jù)庫查詢是數(shù)據(jù)庫的最主要功能之一。我們都希望查詢數(shù)據(jù)的速度能盡可能的快，因此數(shù)據(jù)庫系統(tǒng)的設(shè)計者會從查詢算法的角度進行優(yōu)化。最基本的查詢算法當然是順序查找(linearsearch)，這種復雜度為 O(n)的算法在數(shù)據(jù)量很大時顯然是糟糕的，好在計算機科學的發(fā)展提供了很多更優(yōu)秀的查找算法，例如 二分查找(binary search)、二叉樹查找(binary tree search)等。如果稍微分析一下會發(fā)現(xiàn)，每種查找算法都只能應用于特定的數(shù)據(jù)結(jié)構(gòu)之上，但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)，所以，在數(shù)據(jù)之外，數(shù)據(jù)庫系統(tǒng)還維護著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用(指向)數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)高級查找算法。這種數(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開發(fā)常用的 Linux系統(tǒng)，由林納斯·本納第克特·托瓦茲開發(fā)(百度來的)，還有redhat、Solaris、SunCobalt等等，都有使用到數(shù)據(jù)結(jié)構(gòu)中的，系統(tǒng)棧以及優(yōu)先隊列：堆

3.3 文件壓縮

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

3.4 游戲

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

2) List：List是泛型的，即List，需處理的元素個數(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);  
 
//錯誤操作，因為數(shù)據(jù)的類型不是string 
 
list.add(123); 

3) 鏈表：常用來維護、管理那些需要頻繁產(chǎn)生、消除的游戲?qū)ο?，比如：消除類游戲中需要消除的對象?/p>

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

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

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

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

在計算機領(lǐng)域有一句名言 數(shù)據(jù)結(jié)構(gòu)+算法=程序，而數(shù)據(jù)結(jié)構(gòu)本身就是算法的基石，在近乎任何一本算法教材，都花了大量的時間講解數(shù)據(jù)結(jié)構(gòu)，學好數(shù)據(jù)結(jié)構(gòu)和算法可以讓我們在計算機這條道路上走的更遠。如果數(shù)據(jù)結(jié)構(gòu)是因為它無處不在，學好數(shù)據(jù)結(jié)構(gòu)是使我們快速成長的墊腳石。

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