Adslv ·1. 前言
程序員的一天是怎樣開啟的？
清晨打開儲(chǔ)存著各種結(jié)構(gòu)數(shù)據(jù)的冰箱，從雞蛋集 “盒” 中提取了一枚數(shù)據(jù)扔進(jìn)煎鍋，從西蘭花樹形結(jié)構(gòu)上查找最新鮮的一支跟雞蛋一起煎熟，從袋裝切片面包數(shù)組中取出兩片，用圖形結(jié)構(gòu)的花生醬數(shù)據(jù)涂抹均勻，撕開新買的養(yǎng)樂多隊(duì)列 get (0)，想要清爽一點(diǎn)可以再從腌黃瓜的棧里 pop () 兩片昨天剛放進(jìn)去的鮮嫩數(shù)據(jù)。
程序員的世界離不開數(shù)據(jù)結(jié)構(gòu)，畢竟我們的主要工作內(nèi)容之一就是用邏輯和算法來處理數(shù)據(jù)，而合理地使用數(shù)據(jù)結(jié)構(gòu)就像冰箱里使用恰當(dāng)?shù)娜萜鱽戆b食物一樣重要。
2. 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)既是各類考試的必考部分，也是各類公司面試題里的?？停侨绻麅H僅是為了以上兩點(diǎn)來學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，那就未免顧此失彼了。其實(shí)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)對(duì)我們的工作和學(xué)習(xí)有著很大的幫助，我大概總結(jié)出來我個(gè)人感受比較深的幾個(gè)點(diǎn)跟大家分享：
- 幫助我們有更多更好的手段來使用數(shù)據(jù)，特別是了解各種數(shù)據(jù)結(jié)構(gòu)的原理能夠幫助我們?cè)趯?shí)際開發(fā)工作中遇到大數(shù)據(jù)、高性能、大并發(fā)等業(yè)務(wù)場(chǎng)景時(shí)選擇正確的處理方式；
- 充分發(fā)揮計(jì)算機(jī)的性能，使我們的代碼更加高效，在代碼優(yōu)化的過程中可以更明確的在時(shí)間維度和空間維度之間做出平衡或選擇；
- 學(xué)習(xí)的過程本身又是提升我們思考問題能力的過程，可以提升我們對(duì)算法的了解和認(rèn)識(shí)，拓寬設(shè)計(jì)思路，同時(shí)提升對(duì)全局問題思考的格局和高度；
3. 數(shù)據(jù)結(jié)構(gòu)的定義
百度詞條對(duì)數(shù)據(jù)結(jié)構(gòu)（data structure）的定義是：
帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，并確保經(jīng)過這些運(yùn)算以后所得到的新結(jié)構(gòu)仍保持原來的結(jié)構(gòu)類型。
通俗地講，就是數(shù)據(jù)元素是以何種形式在計(jì)算機(jī)上存儲(chǔ)，又是以何種形式被程序員使用，它們之間的關(guān)系以及我們可以使用的算法。
4. 數(shù)據(jù)結(jié)構(gòu)的分類
數(shù)據(jù)結(jié)構(gòu)的分類一般有兩種維度，一種是根據(jù)數(shù)據(jù)結(jié)構(gòu)的原理從它們的邏輯結(jié)構(gòu)來區(qū)分，一種是從數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)時(shí)的物理結(jié)構(gòu)來區(qū)分。
邏輯結(jié)構(gòu)，是針對(duì)數(shù)據(jù)之間的相互關(guān)系而言的，通?？梢苑譃榫€性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系，非線性結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)多或者多對(duì)多的關(guān)系，而數(shù)組中的數(shù)據(jù)元素相互之間沒有任何關(guān)系，他們只是同一類型數(shù)據(jù)的集合。
物理結(jié)構(gòu)，是針對(duì)數(shù)據(jù)在存儲(chǔ)器中的存儲(chǔ)方法而言的，通?？梢苑譃?strong>順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。順序存儲(chǔ)的數(shù)據(jù)是在一段連續(xù)的空間中，靠相對(duì)位置來表示元素之間的相互關(guān)系，像在一個(gè)小教室上課的同班同學(xué)靠前后座關(guān)系就能建立聯(lián)系；鏈?zhǔn)酱鎯?chǔ)的數(shù)據(jù)內(nèi)存地址不一定是連續(xù)的，每一個(gè)節(jié)點(diǎn)上都有一個(gè)指針存儲(chǔ)域，靠指針來建立元素之間的相互關(guān)系，像幾個(gè)班級(jí)的同學(xué)同時(shí)上公選課時(shí)分散在一個(gè)大教室里，同一個(gè)班級(jí)的同學(xué)之間需要靠學(xué)號(hào)來建立聯(lián)系。
5. Java 中常用的數(shù)據(jù)結(jié)構(gòu)
Java 中常用的數(shù)據(jù)結(jié)構(gòu)都在 java.util 包下，都是對(duì) Collection 和 Map 兩個(gè)頂級(jí)接口的實(shí)現(xiàn)類。這里要注意不是 java.util.Collections，Collections 是一個(gè)對(duì)集合中元素進(jìn)行查詢、排序等操作的工具類，我們下面還會(huì)提到。
讀源代碼是我們最準(zhǔn)確高效的學(xué)習(xí)手段之一，上圖就是 java.util.Collection 源代碼的截圖，注釋中紅標(biāo)分別列舉了實(shí)現(xiàn)該接口的幾種數(shù)據(jù)類型 List、LinkedList、ArrayList、Vector、Set、SortedSet、HashSet、TreeSet、AbstractCollection，藍(lán)標(biāo)是 Map 接口和實(shí)現(xiàn)該接口的 SortedMap，此外實(shí)現(xiàn) Map 接口的還有 HashMap、TreeMap、Hashtable、SortedMap。另外還有 Collections、Arrays 兩個(gè)工具類。從源代碼中我們可以梳理出各種數(shù)據(jù)類型之間的關(guān)系，如下圖：
6. 常用的算法
算法是我們處理數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)步驟，一個(gè)好的算法評(píng)價(jià)標(biāo)準(zhǔn)是效率足夠高、存儲(chǔ)足夠低。我們可以簡單地分成增、刪、改、查，外加排序五類，排序又可以分為插入排序，交換排序、選擇排序、歸并排序、分配排序等，而具體實(shí)現(xiàn)根據(jù)結(jié)構(gòu)和算法的不同，執(zhí)行的效率也會(huì)不同。
好在我們有很多現(xiàn)成的工具可以用可以使我們不必從零開始設(shè)計(jì)一個(gè)健壯、高效、可讀性好的優(yōu)秀的算法。這時(shí)候我們可以祭出一個(gè)利器 ——java.util.Collections，它實(shí)現(xiàn)了對(duì)于數(shù)據(jù)結(jié)構(gòu)的各種靜態(tài)多態(tài)方法來對(duì)集合實(shí)現(xiàn)搜索、排序、線程安全化等等操作。我們可以從源代碼或者官方 API 中了解它都提供了哪些方法。
7. 小結(jié)
本節(jié)我們簡要介紹了數(shù)據(jù)結(jié)構(gòu)的定義、分類及其算法。大家可以把數(shù)據(jù)結(jié)構(gòu)理解成我們封裝數(shù)據(jù)的容器，而算法就像是我們對(duì)容器中的物品進(jìn)行查看、添加、使用和整理的思路及方法。本節(jié)的內(nèi)容更多的是需要大家了解和熟悉，后面我們會(huì)結(jié)合 Java 源碼來介紹各類數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)和用法。
2025 imooc.com All Rights Reserved |