基于常見(jiàn)數(shù)據(jù)結(jié)構(gòu)整理
數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)存儲(chǔ)的常用結(jié)構(gòu)有：棧、隊(duì)列、數(shù)組、鏈表和紅黑樹(shù)
棧
1.stack,又稱堆棧，它是運(yùn)算受限的線性表。
- 其限制是僅允許在標(biāo)的一端進(jìn)行插入和刪除操作，不允許在其他任何位置進(jìn)行添加、查找、刪除等操作。
先進(jìn)后出（即，存進(jìn)去的元素，要在后它后面的元素依次取出后，才能取出該元素）
- 打個(gè)比方：
1. 壓棧（存元素）：（小時(shí)候玩玩具槍的時(shí)候，先裝的子彈在最下方，后裝的子彈在最上方）。
2. 彈棧（取元素）：（最上方的子彈先打出去，然后才是下面的子彈逐個(gè)打出去）。
隊(duì)列
- queue,簡(jiǎn)稱隊(duì)，同樣也是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入， 而在表的另一端進(jìn)行刪除。
- 隊(duì)首：允許進(jìn)行刪除的一端（先進(jìn)去的）。
- 隊(duì)尾：允許進(jìn)行插入的一端（最后進(jìn)入的）。
- 隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列。
先進(jìn)先出（存進(jìn)去的元素，要在后它前面的元素依次取出后，才能取出該元素）。
例如：小火車過(guò)山洞（中間的部分不能進(jìn)行操作）
入隊(duì)：車頭先進(jìn)去，車尾后進(jìn)去；
出隊(duì)：車頭先出來(lái)，車尾后出來(lái)。
數(shù)組
有序的元素序列，數(shù)組是在內(nèi)存中開(kāi)辟一段連續(xù)的空間，并在此空間存放元素。
例如：一個(gè)班級(jí)的學(xué)號(hào)最后兩位數(shù)的，大多情況下的班級(jí)30人：都是從1到30固定到每個(gè)學(xué)生，但是數(shù)組索引只是從0開(kāi)始的。
數(shù)組的特點(diǎn)
查詢快，增刪慢。
查詢?cè)兀?/strong>
查詢數(shù)組的元素是根據(jù)索引直接查找該元素
增加元素：
增加元素時(shí)需要?jiǎng)?chuàng)建新數(shù)組，將指定新元素存儲(chǔ)在指定索引位置，再把原數(shù)組元素根 據(jù)索引，復(fù)制到新數(shù)組對(duì)應(yīng)索引的位置。
刪除元素：
指定索引位置刪除元素：需要?jiǎng)?chuàng)建一個(gè)新數(shù)組，把原數(shù)組元素根據(jù)索引，復(fù)制到新數(shù)組對(duì)應(yīng)索引的位 置，原數(shù)組中指定索引位置元素不復(fù)制到新數(shù)組中
鏈表
鏈表:linked list,由一系列結(jié)點(diǎn)node（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成。
- 結(jié)點(diǎn)可以在運(yùn)行時(shí)i動(dòng)態(tài)生成。
-
每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：
一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，
另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。
也就是說(shuō)：鏈表結(jié)構(gòu)有單向鏈表與雙向鏈表。 -
單向鏈表：
多個(gè)結(jié)點(diǎn)之間，通過(guò)地址進(jìn)行連接。
圖片.png -
例如：多個(gè)人手拉手，每個(gè)人使用自己的右手拉住下個(gè)人的左手，依次 類推，這樣多個(gè)人就連在一起了。
圖片.png
鏈表的特點(diǎn)
增刪快，查詢慢。
- 查找元素慢：
想查找某個(gè)元素，需要通過(guò)連接的節(jié)點(diǎn)，依次向后查找指定元素。（從第一個(gè)元素開(kāi)始向后逐個(gè)查詢） - 增刪元素：
1.增加元素
只需要修改連接下個(gè)元素的地址即可。
-
刪除元素：也只需要修改下一個(gè)地址即可
圖片.png
樹(shù)
1.樹(shù)的定義
n(n>=0)個(gè)結(jié)點(diǎn)的有限集T.
- n=0:空樹(shù)
- n=1:有且僅有一個(gè)結(jié)點(diǎn)的樹(shù)，稱為樹(shù)的根。
- n>=2:其余節(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1，T2，...Tm。其中每一個(gè)集合本身就是一棵樹(shù)，稱為根的子樹(shù)。
子樹(shù)： - 子樹(shù)是相交的
- 除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都只有一個(gè)父結(jié)點(diǎn)
- 一棵N個(gè)結(jié)點(diǎn)的樹(shù)，共有N-1條邊。
2.樹(shù)的基本術(shù)語(yǔ)
- 結(jié)點(diǎn)---表示樹(shù)的元素，包含數(shù)據(jù)元素及其若干指向其子樹(shù)的分支。
- 結(jié)點(diǎn)的度---結(jié)點(diǎn)擁有的子樹(shù)數(shù)。
- 葉子(終端節(jié)點(diǎn))---度為零的結(jié)點(diǎn)。
- 分支結(jié)點(diǎn)---度不為零的結(jié)點(diǎn)。
- 樹(shù)的度---一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù)。
- 孩子---結(jié)點(diǎn)子樹(shù)的根稱為該節(jié)點(diǎn)的孩子。
- 雙親---孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親。
- 兄弟---同一雙親的孩子。
- 祖先結(jié)點(diǎn)---從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上所有結(jié)點(diǎn)。
- 子孫結(jié)點(diǎn)---一個(gè)結(jié)點(diǎn)的直接后續(xù)和間接后繼。
- 結(jié)點(diǎn)的層次---從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層.......
- 深度---樹(shù)中的最大層次數(shù)。
樹(shù)型結(jié)構(gòu)與線性結(jié)構(gòu)的區(qū)別
- 線性結(jié)構(gòu)：
第一個(gè)元素（無(wú)前驅(qū)），最后一個(gè)數(shù)據(jù)元素?zé)o后繼，其他數(shù)據(jù)元素（一個(gè)前驅(qū)，一個(gè)后繼）。 - 樹(shù)型結(jié)構(gòu)：
根結(jié)點(diǎn)（無(wú)前驅(qū)），多個(gè)葉子結(jié)點(diǎn)（無(wú)后繼），其他數(shù)據(jù)元素（一個(gè)前驅(qū)，多個(gè)后繼）。
樹(shù)的存儲(chǔ)結(jié)構(gòu) 孩子表示法
- 孩子鏈表：
每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表存儲(chǔ)，在用含n個(gè)元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表。
樹(shù)的存儲(chǔ)結(jié)構(gòu) 孩子兄弟表示法
- 實(shí)現(xiàn)：設(shè)計(jì)統(tǒng)一的結(jié)點(diǎn)結(jié)構(gòu)，沒(méi)個(gè)結(jié)點(diǎn)的兩個(gè)指針域指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。
- 特點(diǎn)：
操作容易，空間浪費(fèi)少。
二叉樹(shù)：
也叫做紅黑樹(shù)，binary tree ,是每個(gè)結(jié)點(diǎn)不超過(guò)2的有序樹(shù)（tree）。
二叉樹(shù)的子樹(shù)有五種基本的形態(tài)
注意：二叉樹(shù)的子樹(shù)有左右之分
二叉樹(shù)的性質(zhì)
在二叉樹(shù)的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)(i>=1)。
深度為k的二叉樹(shù)至多有2^k -1個(gè)結(jié)點(diǎn)(k>=1)。
對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為N0，度為2的結(jié)點(diǎn)數(shù)位N2，則N0=N2+1。
具有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2 N]+1。
二叉樹(shù)的約束：
1.結(jié)點(diǎn)可以是紅色的或者黑色的
根結(jié)點(diǎn)是黑色的。
葉子結(jié)點(diǎn)(特指空結(jié)點(diǎn))是黑色的。
每個(gè)紅色結(jié)點(diǎn)的子結(jié)點(diǎn)都是黑色的。
任何一個(gè)結(jié)點(diǎn)到其每一個(gè)葉子結(jié)點(diǎn)的所有路徑上黑色結(jié)點(diǎn)數(shù)相同。
二叉樹(shù)的特點(diǎn)
速度特別快,趨近平衡樹(shù),查找葉子元素少和多次數(shù)不多于二倍。
二叉樹(shù)的存儲(chǔ)形式：
- 順序存儲(chǔ)：
完全二叉樹(shù)：對(duì)結(jié)點(diǎn)按照上至下，從左到右的次序進(jìn)行存儲(chǔ)。
- 鏈?zhǔn)酱鎯?chǔ)
二叉樹(shù)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和分別指向其左，右子樹(shù)的兩個(gè)分支構(gòu)成。
表示二叉樹(shù)的鏈表中的結(jié)點(diǎn)至少包含3個(gè)域：數(shù)據(jù)域，左，右指針域（雙向指針）
