首發(fā)公眾號(hào)：Android程序員日記
作者：賢榆的榆
如果喜歡括细，請(qǐng)關(guān)注僚楞、贊賞岸裙、點(diǎn)在看
閱讀時(shí)間：2155字 5分鐘
前言
先說說為什么想要寫數(shù)據(jù)結(jié)構(gòu)與算法這個(gè)系列文章建芙，主要出于兩方面考慮：
- 第一個(gè)是面試的需要来累，大廠和外企尤大多數(shù)都會(huì)問到關(guān)于算法和數(shù)據(jù)結(jié)構(gòu)方面的問題砚作，而每次都考背，那其實(shí)也很難形成長(zhǎng)期記憶嘹锁，也不能與面試官進(jìn)一步深入探究偎巢。
- 其二就是工作的需要了，作為一個(gè)初級(jí)的程序員用ArrayList和HashMap可能就幾乎可以解決大部分問題了兼耀，因?yàn)槲覀兊腁pp用戶量不算大压昼，業(yè)務(wù)邏輯不算復(fù)雜求冷，所以浪費(fèi)一點(diǎn)性能和手機(jī)資源也不會(huì)有太大的問題暴露出來，但是當(dāng)App變得越來越大窍霞，業(yè)務(wù)邏輯也越來越復(fù)雜時(shí)匠题，我們就需要去考慮用在某些場(chǎng)景下LinkedList是不是會(huì)更好，TreeMap會(huì)不會(huì)比HashMap的使用成本更低但金？我知道很多同學(xué)會(huì)馬上說出他們之間兩兩的區(qū)別韭山。但如果不知道其背后的實(shí)現(xiàn)原理和邏輯，還真的不太可能會(huì)考慮到使用別的去代替一個(gè)我們常用的冷溃。
數(shù)據(jù)結(jié)構(gòu)入門
針對(duì)自己自學(xué)《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》這門課程钱磅，真的是有一種感觸就是——出來混的總是要還的。高中玩過去了似枕，混過去了盖淡，現(xiàn)在招聘市場(chǎng)上也會(huì)對(duì)本科學(xué)歷有要求，像我這種正在專升本的凿歼，其實(shí)以后可能也是沒什么用了褪迟。因?yàn)槿思铱赡軙?huì)寫明需要統(tǒng)招本科。那為什么我還想要自考去拿一個(gè)計(jì)算機(jī)的本科學(xué)歷答憔∥对撸可能也是因?yàn)橄裼?jì)算機(jī)原理、網(wǎng)絡(luò)原理虐拓、數(shù)據(jù)機(jī)構(gòu)心俗、算法等，這些編程很底層很基礎(chǔ)的課程蓉驹，確實(shí)可能會(huì)在某個(gè)技能爬升的階段稱為我們這些半路出家的程序員的瓶頸另凌。所以說出來混的總是要還的。下面我們先從數(shù)據(jù)結(jié)構(gòu)的一些基本概念和術(shù)語開始吧戒幔。
1、數(shù)據(jù)土童、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)
- 數(shù)據(jù)：所有被計(jì)算機(jī)存儲(chǔ)诗茎、處理的對(duì)象。包括但不限于數(shù)值献汗、布爾值敢订、字符串、表格罢吃、圖像楚午、聲音。
- 數(shù)據(jù)元素：數(shù)據(jù)的基本單位尿招，同事也是運(yùn)算的基本單位矾柜，在程序中作為一個(gè)整體加以考慮和處理阱驾。通常具有完整且確定的實(shí)際意義。
- 數(shù)據(jù)項(xiàng)：它是數(shù)據(jù)的不可分割的最小標(biāo)識(shí)單位怪蔑。數(shù)據(jù)元素一般都由數(shù)據(jù)項(xiàng)組成里覆。在數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)又稱之為字段或者域。
| 學(xué)號(hào) | 姓名 | 性別 | 成績(jī) |
|---|---|---|---|
| 1 | Jack | 男 | 98 |
| 2 | Alice | 女 | 99 |
| 3 | Tony | 男 | 90 |
這里舉個(gè)例子比如上面這份表格缆瓣，它就是可以說是一份數(shù)據(jù)喧枷，而其中的每一個(gè)記錄如“1、Jack弓坞、男隧甚、98”就是一個(gè)數(shù)據(jù)元素，而這條數(shù)據(jù)元素由學(xué)號(hào)渡冻、姓名戚扳、性別和成績(jī)這四個(gè)具體的數(shù)據(jù)項(xiàng)組成。我們?cè)谟?jì)算機(jī)中處理時(shí)基本都是以一條數(shù)據(jù)元素為單位進(jìn)行處理的菩帝。這也就很好好理解了咖城，因?yàn)閱为?dú)拎出一個(gè)98來運(yùn)算其實(shí)是沒什么意義。但是在一些特殊場(chǎng)景下呼奢，一個(gè)數(shù)據(jù)元素也可能只由一個(gè)數(shù)據(jù)項(xiàng)組成宜雀，此時(shí)數(shù)據(jù)項(xiàng)就是數(shù)據(jù)元素自身。
2握础、數(shù)據(jù)的邏輯結(jié)構(gòu)
數(shù)據(jù)的邏輯結(jié)構(gòu)就是指數(shù)據(jù)元素之間的邏輯關(guān)系辐董。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”。而多條數(shù)據(jù)元素之間邏輯關(guān)系的整體呈現(xiàn)稱之為邏輯結(jié)構(gòu)禀综。
- 線性結(jié)構(gòu)：元素之間只存在一對(duì)一的關(guān)系
- 樹形結(jié)構(gòu)：元素之間存在著一對(duì)多的關(guān)系
- 圖結(jié)構(gòu)：元素之間存在著多堆多的關(guān)系（呈現(xiàn)出來的像是網(wǎng)简烘，所以也的稱為網(wǎng)結(jié)構(gòu)。）
- 集合：除了這些元素同屬于同一個(gè)集合之外定枷，元素之間并沒有其他關(guān)系
3孤澎、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
順序存儲(chǔ)：在內(nèi)存中申請(qǐng)一塊地址值連續(xù)的內(nèi)存空間，依次將各個(gè)數(shù)據(jù)元素存儲(chǔ)進(jìn)去欠窒，利用了存儲(chǔ)節(jié)點(diǎn)在內(nèi)存中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系覆旭。其優(yōu)點(diǎn)是可以實(shí)現(xiàn)隨機(jī)訪問，且每個(gè)數(shù)據(jù)元素占用了最少的空間岖妄；但缺點(diǎn)也顯而易見型将，它每次需要一整塊的存儲(chǔ)單元，容易造成內(nèi)存的碎片化荐虐，無法更加充分的利用內(nèi)存空間七兜，同時(shí)插入和刪除操作也需要移動(dòng)元素。
鏈?zhǔn)酱鎯?chǔ)：不要求在內(nèi)存中有一塊連續(xù)的存儲(chǔ)空間福扬，它可以通過讓元素節(jié)點(diǎn)存儲(chǔ)地址的指針來表示元素之間的邏輯關(guān)系腕铸。其優(yōu)點(diǎn)自然是可以充分利用內(nèi)存空間惜犀，避免了內(nèi)存的碎片化，增刪元素比較靈活（不用一定元素恬惯，只需要改變節(jié)點(diǎn)的）向拆；缺點(diǎn)是元素因?yàn)榇鎯?chǔ)了指針而占用了除存儲(chǔ)元素本身以外的更多內(nèi)存空間，并且它也只能實(shí)現(xiàn)順序訪問元素酪耳。
-
索引存儲(chǔ)：該存儲(chǔ)方式是在存儲(chǔ)元素的同時(shí)還增加了一個(gè)索引表浓恳，索引表中的每一項(xiàng)由<關(guān)鍵字+地址>的形式進(jìn)行存儲(chǔ)的，關(guān)鍵字是能夠標(biāo)識(shí)一個(gè)數(shù)據(jù)元素唯一的數(shù)據(jù)項(xiàng)碗暗，而地址則指示了數(shù)據(jù)元素存儲(chǔ)的地址值或者存儲(chǔ)區(qū)域的首地址值颈将。其優(yōu)點(diǎn)是檢索速度快，缺點(diǎn)是附加的索引表占用了較多的內(nèi)存空間言疗，增加和刪除數(shù)據(jù)時(shí)也要修改索引表晴圾，因此增加了時(shí)間的開銷。
注：關(guān)于索引存儲(chǔ)想更深入的了解的可以查看該鏈接：《快速理解索引原理》
-
散列存儲(chǔ)：通過一個(gè)散列（哈希）函數(shù)將元素的關(guān)鍵字與存儲(chǔ)的地址值建立起一種對(duì)應(yīng)關(guān)系噪奄。因此每一個(gè)數(shù)據(jù)元素的具體存儲(chǔ)位置都可以通過該算法直接計(jì)算出來死姚。其優(yōu)點(diǎn)是檢索、增加勤篮、刪除的速度都很快都毒，缺點(diǎn)是一般都需要比其他結(jié)構(gòu)更多的存儲(chǔ)空間，關(guān)鍵字也不能重復(fù)碰缔，還需要解決hash沖突的問題账劲。
注：關(guān)于散列存儲(chǔ)或散列表想了解更多的可以看該連接：哈希表知識(shí)點(diǎn)總結(jié)
4、數(shù)據(jù)邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系
數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)其實(shí)就是數(shù)據(jù)邏輯結(jié)構(gòu)在計(jì)算機(jī)里的實(shí)現(xiàn)金抡。不過一種邏輯結(jié)構(gòu)可以采用一種或多種數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)來表達(dá)數(shù)據(jù)元素之間的邏輯關(guān)系瀑焦。
數(shù)據(jù)結(jié)構(gòu)和算法，其實(shí)在一個(gè)程序員的生涯中梗肝，算是一個(gè)很重要的地基吧榛瓮，想要起高樓，這個(gè)地基是無論如何是無法略過的巫击。所以在10月份自考了《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》科目之后禀晓，就一直想著把這塊的東西再總結(jié)一下分享出去，下一篇”入門二“會(huì)介紹算法和算法分析（及時(shí)間和空間復(fù)雜度）喘鸟，如果覺得有幫助歡迎關(guān)注我或點(diǎn)個(gè)在看！
