2019-11-04-23:03:13 目錄: 1.常用的數據結構 2.棧 3.隊列 4.數組 5.鏈表 6.紅黑樹 常用的數據結構: 包含:棧、隊列、數組、鏈表和紅黑樹 棧: 棧:stack,又稱堆棧,它是運算受限的線性表,其限制是僅允許在標的一端進行插入和刪除操作,不允許在其 他任何位置進行添加 ...
2019-11-04-23:03:13
目錄:
1.常用的數據結構
2.棧
3.隊列
4.數組
5.鏈表
6.紅黑樹
常用的數據結構:
包含:棧、隊列、數組、鏈表和紅黑樹
棧:
棧:stack,又稱堆棧,它是運算受限的線性表,其限制是僅允許在標的一端進行插入和刪除操作,不允許在其 他任何位置進行添加、查找、刪除等操作
特點:
1.先進後出(即,存進去的元素,要在後它後面的元素依次取出後,才能取出該元素)。例如,子彈壓進彈 夾,先壓進去的子彈在下麵,後壓進去的子彈在上面,當開槍時,先彈出上面的子彈,然後才能彈出下麵的 子彈。
2.棧的入口、出口的都是棧的頂端位置。
名詞註意:
1.壓棧:就是存元素。即,把元素存儲到棧的頂端位置,棧中已有元素依次向棧底方向移動一個位置
2.彈棧:就是取元素。即,把棧的頂端位置元素取出,棧中已有元素依次向棧頂方向移動一個位置。
隊列:
隊列:queue,簡稱隊,它同堆棧一樣,也是一種運算受限的線性表,其限制是僅允許在表的一端進行插入, 而在表的另一端進行刪除。
特點:
1.先進先出(即,存進去的元素,要在它前面的元素依次取出後,才能取出該元素)。例如,小火車過山洞,車頭先進去,車尾後進去;車頭先出來,車尾後出來。
2.隊列的入口、出口各占一側。例如,下圖中的左側為入口,右側為出口
數組:
數組:Array,是有序的元素序列,數組是在記憶體中開闢一段連續的空間,併在此空間存放元素。就像是一排出 租屋,有100個房間,從001到100每個房間都有固定編號,通過編號就可以快速找到租房子的人。
特點:
1.查找元素快:通過索引,可以快速訪問指定位置的元素
2.增刪元素慢 :
指定索引位置增加元素:需要創建一個新數組,將指定新元素存儲在指定索引位置,再把原數組元素根據索引,複製到新數組對應索引的位置。如下圖
指定索引位置刪除元素:需要創建一個新數組,把原數組元素根據索引,複製到新數組對應索引的位 置,原數組中指定索引位置元素不複製到新數組中。如下圖
鏈表:
鏈表:linked list,由一系列結點node(鏈表中每一個元素稱為結點)組成,結點可以在運行時i動態生成
結點:
1.一個是存儲數據元素的數據域
2.一個是存儲下一個結點地址的指針域。
特點:
1.多個結點之間,通過地址進行連接。例如,多個人手拉手,每個人使用自己的右手拉住下個人的左手,依次 類推,這樣多個人就連在一起了。
2.查找元素慢:想查找某個元素,需要通過連接的節點,依次向後查找指定元素
3.增刪元素快
增加元素:只需要修改連接下個元素的地址即可
刪除元素:只需要修改連接下個元素的地址即可
紅黑樹:
二叉樹:binary tree ,是每個結點不超過2的有序樹(tree)
特點:
1.二叉樹是每個節點多有兩個子樹的樹結構。頂上的叫根結點,兩邊被稱作“左子樹”和“右子樹”。
紅黑樹:二叉樹的一種比較有意思的叫做紅黑樹,紅黑樹本身就是一顆二叉查找樹,將節點插入後,該樹仍然 是一顆二叉查找樹。也就意味著,樹的鍵值仍然是有序的
紅黑樹的約束:
1. 節點可以是紅色的或者黑色的
2. 根節點是黑色的
3. 葉子節點(特指空節點)是黑色的
4. 每個紅色節點的子節點都是黑色的
5. 任何一個節點到其每一個葉子節點的所有路徑上黑色節點數相同
紅黑樹的特點:
速度特別快,趨近平衡樹,查找葉子元素少和多次數不多於二倍