當前位置：首頁 > 人文社科 > 生活经验 >内容正文

生活经验

数据结构|-常见数据结构整理

發布時間：2023/11/27 生活经验 31 豆豆

生活随笔收集整理的這篇文章主要介紹了数据结构|-常见数据结构整理小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

歸納總結了一下數據機構的常用類型，個人理解常用的數據機構可以分為線性表、棧、隊列、樹，線性表包括順序表和鏈表，棧和隊列應當屬于特殊的線性表，有幾個概念和誤區需要先說一下

順序表和線性表的關系：

- 線性表是邏輯概念，只要所有的數據在邏輯上是一維的便算是線性表，線性表中數據元素之間的關系是一對一的關系（每個元素首尾相接），比如數組和鏈表，都是數據一個接一個的線性表。與線性表對應的是樹、堆等。
- 順序表是空間概念，是線性表的順序存儲結構，指的是數據在存儲空間上順序排列，比如數組，數組便是劃分一塊連續的內存區域用于存儲，與順序表相對應的是鏈表。

隊列、棧和線性表的關系：

- 線性表可以在表中任意位置進行插入、刪除等操作。
- 棧是一種特殊的線性表，其邏輯結構和線性表相同，但也有差別，棧被限定為只能在其一端進行插入刪除的操作。
- 隊列也是一種特殊的線性表，邏輯結構與線性表相同，但操作上有限制，隊列限制在表的一端進行插入，在表的另一端進行刪除。

數組、鏈表、棧、隊列、哈希表、樹、圖、堆

數組

數組是可以在內存中連續存儲多個元素的結構，在內存中的分配也是連續的，數組中的元素通過數組下標進行訪問，數組下標從0開始。

優點：

- 按照索引查詢元素速度快
- 按照索引遍歷數組方便

缺點：

- 數組的大小固定后就無法擴容了
- 數組只能存儲一種類型的數據
- 添加，刪除的操作慢，因為要移動其他的元素。

適用場景：
頻繁查詢，對存儲空間要求不大，很少增加和刪除的情況。

鏈表

鏈表是物理存儲單元上非連續的、非順序的存儲結構，數據元素的邏輯順序是通過鏈表的指針地址實現，每個元素包含兩個結點，一個是存儲元素的數據域 (內存空間)，另一個是指向下一個結點地址的指針域。根據指針的指向，鏈表能形成不同的結構，例如單鏈表，雙向鏈表，循環鏈表等。?

鏈表的優點：

- 鏈表是很常用的一種數據結構，不需要初始化容量，可以任意加減元素；
- 添加或者刪除元素時只需要改變前后兩個元素結點的指針域指向地址即可，所以添加，刪除很快；

缺點：

- 因為含有大量的指針域，占用空間較大；
- 查找元素需要遍歷鏈表來查找，非常耗時。

適用場景：
數據量較小，需要頻繁增加，刪除操作的場景

?　　PS：C#中沒有鏈表，根本原因是 .net 框架中出于安全考慮取消了指針類型，因此也就沒有鏈表了。而事實上，數組和哈希表的組合在各方面都不輸鏈表，鏈表也就沒有存在空間了。

棧

棧是一種特殊的線性表，僅能在線性表的一端操作，棧頂允許操作，棧底不允許操作。棧的特點是：先進后出，或者說是后進先出，從棧頂放入元素的操作叫入棧，取出元素叫出棧。

棧的結構就像一個集裝箱，越先放進去的東西越晚才能拿出來，所以，棧常應用于實現遞歸功能方面的場景，例如斐波那契數列。

?隊列

隊列與棧一樣，也是一種線性表，不同的是，隊列可以在一端添加元素，在另一端取出元素，也就是：先進先出。從一端放入元素的操作稱為入隊，取出元素為出隊，示例圖如下：

使用場景：因為隊列先進先出的特點，在多線程阻塞隊列管理中非常適用。

哈希表

散列表，也叫哈希表，是根據關鍵碼和值 (key和value) 直接進行訪問的數據結構，通過key和value來映射到集合中的一個位置，這樣就可以很快找到集合中的對應元素。

記錄的存儲位置=f(key)

從圖中可以看出，左邊很明顯是個數組，數組的每個成員包括一個指針，指向一個鏈表的頭，當然這個鏈表可能為空，也可能元素很多。我們根據元素的一些特征把元素分配到不同的鏈表中去，也是根據這些特征，找到正確的鏈表，再從鏈表中找出這個元素。

可以看作是數組和鏈表的組合。

?樹

這里僅討論二叉樹，以圖加深印象

相關性質

- 二叉樹的每個結點至多只有2棵子樹(不存在度大于2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。
- 二叉樹的第i層至多有2^(i-1)個結點；深度為k的二叉樹至多有2^k-1個結點。
- 一棵深度為k，且有2^k-1個節點的二叉樹稱之為?滿二叉樹?；
- 深度為k，有n個節點的二叉樹，當且僅當其每一個節點都與深度為k的滿二叉樹中，序號為1至n的節點對應時，稱之為?完全二叉樹?。（簡單來理解就是依次從左子樹一直排過去，有任何一個結點只有右子沒左子便不是完全二叉樹）

三種遍歷（三種遍歷很容易搞混，其實只需要顧名思義，先序中序后序就是指的父結點遍歷的先后次序，先序：先根后左再右，中序：左根右，后序：左右根）下面的圖多跟著走幾遍就理解透徹了

圖

未完待續……

堆

未完待續……

參考來源：https://blog.csdn.net/yeyazhishang/article/details/82353846、https://www.cnblogs.com/wanghuaijun/p/7302303.html

轉載于:https://www.cnblogs.com/wq-KingStrong/p/10278303.html

總結

以上是生活随笔為你收集整理的数据结构|-常见数据结构整理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。