每一種數(shù)據(jù)結(jié)構(gòu)都有著獨(dú)特的數(shù)據(jù)存儲(chǔ)方式,下面為大家介紹它們的結(jié)構(gòu)和優(yōu)缺點(diǎn)。 1、數(shù)組 數(shù)組是可以再內(nèi)存中連續(xù)存儲(chǔ)多個(gè)元素的結(jié)構(gòu),在內(nèi)存中的分配也是連續(xù)的,數(shù)組中的元素通過(guò)數(shù)組下標(biāo)進(jìn)行訪問(wèn),數(shù)組下標(biāo)從0開(kāi)始。例如下面這段代碼就是將數(shù)組的第一個(gè)元素賦值為 1。 優(yōu)點(diǎn): 1、按照索引查詢?cè)厮俣瓤?/p> 2、按照索引遍歷數(shù)組方便 缺點(diǎn): 1、數(shù)組的大小固定后就無(wú)法擴(kuò)容了 2、數(shù)組只能存儲(chǔ)一種類(lèi)型的數(shù)據(jù) 3、添加,刪除的操作慢,因?yàn)橐苿?dòng)其他的元素。 適用場(chǎng)景: 頻繁查詢,對(duì)存儲(chǔ)空間要求不大,很少增加和刪除的情況。 2、棧 棧是一種特殊的線性表,僅能在線性表的一端操作,棧頂允許操作,棧底不允許操作。 棧的特點(diǎn)是:先進(jìn)后出,或者說(shuō)是后進(jìn)先出,從棧頂放入元素的操作叫入棧,取出元素叫出棧。 棧的結(jié)構(gòu)就像一個(gè)集裝箱,越先放進(jìn)去的東西越晚才能拿出來(lái),所以,棧常應(yīng)用于實(shí)現(xiàn)遞歸功能方面的場(chǎng)景,例如斐波那契數(shù)列。 3、隊(duì)列 隊(duì)列與棧一樣,也是一種線性表,不同的是,隊(duì)列可以在一端添加元素,在另一端取出元素,也就是:先進(jìn)先出。從一端放入元素的操作稱(chēng)為入隊(duì),取出元素為出隊(duì),示例圖如下: 使用場(chǎng)景:因?yàn)殛?duì)列先進(jìn)先出的特點(diǎn),在多線程阻塞隊(duì)列管理中非常適用。 4、鏈表 鏈表是物理存儲(chǔ)單元上非連續(xù)的、非順序的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表的指針地址實(shí)現(xiàn),每個(gè)元素包含兩個(gè)結(jié)點(diǎn),一個(gè)是存儲(chǔ)元素的數(shù)據(jù)域 (內(nèi)存空間),另一個(gè)是指向下一個(gè)結(jié)點(diǎn)地址的指針域。根據(jù)指針的指向,鏈表能形成不同的結(jié)構(gòu),例如單鏈表,雙向鏈表,循環(huán)鏈表等。 鏈表的優(yōu)點(diǎn): 鏈表是很常用的一種數(shù)據(jù)結(jié)構(gòu),不需要初始化容量,可以任意加減元素; 添加或者刪除元素時(shí)只需要改變前后兩個(gè)元素結(jié)點(diǎn)的指針域指向地址即可,所以添加,刪除很快; 缺點(diǎn): 因?yàn)楹写罅康闹羔樣?,占用空間較大; 查找元素需要遍歷鏈表來(lái)查找,非常耗時(shí)。 適用場(chǎng)景: 數(shù)據(jù)量較小,需要頻繁增加,刪除操作的場(chǎng)景 5、樹(shù) 樹(shù)是一種數(shù)據(jù)結(jié)構(gòu),它是由n(n>=1)個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做 “樹(shù)” 是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù),也就是說(shuō)它是根朝上,而葉朝下的。它具有以下的特點(diǎn): 每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn); 沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn); 每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn); 除了根節(jié)點(diǎn)外,每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù); 在日常的應(yīng)用中,我們討論和用的更多的是樹(shù)的其中一種結(jié)構(gòu),就是二叉樹(shù)。 二叉樹(shù)是樹(shù)的特殊一種,具有如下特點(diǎn): 1、每個(gè)結(jié)點(diǎn)最多有兩顆子樹(shù),結(jié)點(diǎn)的度最大為2。 2、左子樹(shù)和右子樹(shù)是有順序的,次序不能顛倒。 3、即使某結(jié)點(diǎn)只有一個(gè)子樹(shù),也要區(qū)分左右子樹(shù)。 二叉樹(shù)是一種比較有用的折中方案,它添加,刪除元素都很快,并且在查找方面也有很多的算法優(yōu)化,所以,二叉樹(shù)既有鏈表的好處,也有數(shù)組的好處,是兩者的優(yōu)化方案,在處理大批量的動(dòng)態(tài)數(shù)據(jù)方面非常有用。 擴(kuò)展: 二叉樹(shù)有很多擴(kuò)展的數(shù)據(jù)結(jié)構(gòu),包括平衡二叉樹(shù)、紅黑樹(shù)、B+樹(shù)等,這些數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的基礎(chǔ)上衍生了很多的功能,在實(shí)際應(yīng)用中廣泛用到,例如mysql的數(shù)據(jù)庫(kù)索引結(jié)構(gòu)用的就是B+樹(shù),還有HashMap的底層源碼中用到了紅黑樹(shù)。這些二叉樹(shù)的功能強(qiáng)大,但算法上比較復(fù)雜,想學(xué)習(xí)的話還是需要花時(shí)間去深入的。 6、散列表 散列表,也叫哈希表,是根據(jù)關(guān)鍵碼和值 (key和value) 直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu),通過(guò)key和value來(lái)映射到集合中的一個(gè)位置,這樣就可以很快找到集合中的對(duì)應(yīng)元素。 記錄的存儲(chǔ)位置=f(key) 這里的對(duì)應(yīng)關(guān)系 f 成為散列函數(shù),又稱(chēng)為哈希 (hash函數(shù)),而散列表就是把Key通過(guò)一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字,然后就將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余,取余結(jié)果就當(dāng)作數(shù)組的下標(biāo),將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里,這種存儲(chǔ)空間可以充分利用數(shù)組的查找優(yōu)勢(shì)來(lái)查找元素,所以查找的速度很快。 哈希表在應(yīng)用中也是比較常見(jiàn)的,就如Java中有些集合類(lèi)就是借鑒了哈希原理構(gòu)造的,例如HashMap,HashTable等,利用hash表的優(yōu)勢(shì),對(duì)于集合的查找元素時(shí)非常方便的,然而,因?yàn)楣1硎腔跀?shù)組衍生的數(shù)據(jù)結(jié)構(gòu),在添加刪除元素方面是比較慢的,所以很多時(shí)候需要用到一種數(shù)組鏈表來(lái)做,也就是拉鏈法。拉鏈法是數(shù)組結(jié)合鏈表的一種結(jié)構(gòu),較早前的hashMap底層的存儲(chǔ)就是采用這種結(jié)構(gòu),直到j(luò)dk1.8之后才換成了數(shù)組加紅黑樹(shù)的結(jié)構(gòu),其示例圖如下: 從圖中可以看出,左邊很明顯是個(gè)數(shù)組,數(shù)組的每個(gè)成員包括一個(gè)指針,指向一個(gè)鏈表的頭,當(dāng)然這個(gè)鏈表可能為空,也可能元素很多。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去,也是根據(jù)這些特征,找到正確的鏈表,再?gòu)逆湵碇姓页鲞@個(gè)元素。 哈希表的應(yīng)用場(chǎng)景很多,當(dāng)然也有很多問(wèn)題要考慮,比如哈希沖突的問(wèn)題,如果處理的不好會(huì)浪費(fèi)大量的時(shí)間,導(dǎo)致應(yīng)用崩潰。 7、堆 堆是一種比較特殊的數(shù)據(jù)結(jié)構(gòu),可以被看做一棵樹(shù)的數(shù)組對(duì)象,具有以下的性質(zhì): 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值; 堆總是一棵完全二叉樹(shù)。 將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆,根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。常見(jiàn)的堆有二叉堆、斐波那契堆等。 堆的定義如下:n個(gè)元素的序列{k1,k2,ki,…,kn}當(dāng)且僅當(dāng)滿足下關(guān)系時(shí),稱(chēng)之為堆。 (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2),滿足前者的表達(dá)式的成為小頂堆,滿足后者表達(dá)式的為大頂堆,這兩者的結(jié)構(gòu)圖可以用完全二叉樹(shù)排列出來(lái),示例圖如下: 因?yàn)槎延行虻奶攸c(diǎn),一般用來(lái)做數(shù)組中的排序,稱(chēng)為堆排序。 8、圖 圖是由結(jié)點(diǎn)的有窮集合V和邊的集合E組成。其中,為了與樹(shù)形結(jié)構(gòu)加以區(qū)別,在圖結(jié)構(gòu)中常常將結(jié)點(diǎn)稱(chēng)為頂點(diǎn),邊是頂點(diǎn)的有序偶對(duì),若兩個(gè)頂點(diǎn)之間存在一條邊,就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系。 按照頂點(diǎn)指向的方向可分為無(wú)向圖和有向圖。 以上所描述的都是數(shù)據(jù)結(jié)構(gòu)的皮毛知識(shí),如果想深入了解必須靜心學(xué)習(xí)。 關(guān)注我不迷路,我是程序員小樊。 |
|