【数据结构】八种常见数据结构介绍
相似文章推薦:
- 算法簡介
- 七大查找算法的理解與實現
- 路徑規劃中的Dijkstra(狄克斯特拉)與A星算法
- 八大經典排序算法的理解、動圖演示和C++方法實現
零. 總覽
數據結構是計算機存儲、組織數據的方式。一種好的數據結構可以帶來更高的運行或者存儲效率。數據在內存中是呈線性排列的,但是我們可以使用指針等道具,構造出類似“樹形”的復雜結構。下面介紹八個常見的數據結構。
一. 數組
數組是一種線性結構,而且在物理內存中也占據著一塊連續空間。
- 優點:訪問數據簡單。
- 缺點:添加和刪除數據比較耗時間。
- 使用場景:頻繁查詢,對存儲空間要求不大,很少增加和刪除的情況。
數據訪問:由于數據是存儲在連續空間內,所以每個數據的內存地址都是通過數據小標算出,所以可以直接訪問目標數據。(這叫做“隨機訪問”)。比如下方,可以直接使用a[2]訪問Red。
數據添加:數據添加需要移動其他數據。首先增加足夠的空間,然后把已有的數據一個個移開。
數據刪除:反過來,如果想要輸出數據Green,也是一樣挨個把數據往反方向移動。
二. 鏈表
鏈表是物理存儲單元上非連續的、非順序的存儲結構,數據元素的邏輯順序是通過鏈表的指針地址實現,每個元素包含兩個結點,一個是存儲元素的數據域 (內存空間),另一個是指向下一個結點地址的指針域。
- 優點:數據添加和刪除方便
- 缺點:訪問比較耗費時間
- 適用場景:數據量較小,需要頻繁增加,刪除操作的場景
數組和鏈表數據結構對比列表如下:
數據訪問:因為數據都是分散存儲的,所以想要訪問數據,只能從第一個數據開始,順著指針的指向逐一往下訪問。
數據添加:將Blue的指針指向的位置變成Green,然后再把Green的指針指向Yellow。
數據刪除:只要改變指針的指向就可以了,比如刪除Yellow,只需把Green指針指向的位置從Yellow編程Red即可。
雖然Yellow本身還存儲在內存中,但是不管從哪里都無法訪問這個數據,所以也就沒有特意去刪除它的必要了。今后需要用到Yellow所在的存儲空間時,只要用新數據覆蓋掉就可以了。
三. 棧
棧也是一種數據呈線性排列的數據結構,不過在這種結構中,我們只能訪問最新添加的數
據。從棧頂放入元素的操作叫入棧,取出元素叫出棧。
特點:后進先出(Last In First Out,簡稱LIFO)
四. 隊列
隊列中的添加和刪除數據的操作分別是在兩端進行的。隊列可以在一端添加元素,在另一端取出元素,也就是:先進先出(First In First Out,簡稱FIFO)
五. 哈希表
哈希表,也叫散列表,是根據關鍵碼和值 (key和value) 直接進行訪問的數據結構,通過key和value來映射到集合中的一個位置,這樣就可以很快找到集合中的對應元素。例如,下列鍵(key)為人名,value為性別。
一般來說,我們可以把鍵當作數據的標識符,把值當作數據的內容。
- 數據存儲
假設我們需要存儲5個元素,首先使用哈希函數(Hash)計算Joe的鍵,也就是字符串"Joe"的哈希值,得到4928,然后將哈希值除以數組長度5(mod運算),求得其余數。因此,我們將Joe的數據存進數組的3號箱子中。
- 沖突
如果兩個哈希值取余的結果相同,我們稱這種情況為“沖突”。假設Nell鍵的哈希值為6276,mod 5的結果為1。但此時1號箱已經存儲了Sue的數據,可使用鏈表在已有的數據的后面繼續存儲新的數據。
- 查詢
假設最終的哈希表為:
如果要查找Ally的性別,首先算出Alley鍵的哈希值,然后對它進行mod運算。最終結果為3。
然而3號箱中數據的鍵是Joe而不是Ally。此時便需要對Joe所在的鏈表進行線性查找。找到了鍵為Ally的數據。取出其對應的值,便知道了Ally的性別為女(F)。
- 特點
可以利用哈希函數快速訪問到數組的目標數據。如果發生哈希沖突,就使用鏈表進行存儲。
如果數組的空間太小,使用哈希表的時候就容易發生沖突,線性查找的使用頻率也會更高;反過來,如果數組的空間太大,就會出現很多空箱子,造成內存的浪費。因此,給數組設定合適的空間非常重要。
在存儲數據的過程中,如果發生沖突,可以利用鏈表在已有數據的后面插入新數據來解決沖突。這種方法被稱為“鏈地址法”。除了鏈地址法以外,還有幾種解決沖突的方法。其中,應用較為廣泛的是“開放地址法”。
六. 堆
堆是一種圖的樹形結構,被用于實現“優先隊列”(priority queues)。優先隊列是一種數據結構,可以自由添加數據,但取出數據時要從最小值開始按順序取出。在堆的樹形結構中,各個頂點被稱為“結點”(node),數據就存儲在這些結點中。堆有下列特點:
- 每個節點最多有兩個子節點
- 排列順序必須從上到下,同一行從左到右
- 堆中某個節點的值總是不大于或不小于其父節點的值;
- 存放數據時,一般會把新數據放在最下面一行靠左的位置。如果最下面一行沒有多余空間時,就再往下另起一行,并把數據添加到這一行的最左端。
堆的性質:
- 堆是一個完全二叉樹
- 堆中某個結點的值總是不大于或不小于其父結點的值;
- 將根結點最大的堆叫做最大堆或大根堆,根結點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。
- 一棵深度為k的有n個結點的二叉樹,對樹中的結點按從上至下、從左到右的順序進行編號,如果編號為i(1≤i≤n)的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同,則這棵二叉樹稱為完全二叉樹。
- 一棵深度為kkk且有2k?12^k - 12k?1個結點的二叉樹稱為滿二叉樹。也就是說除了葉子節點都有2個子節點,且所有的葉子節點都在同一層。
七. 樹
它是由n(n>=1)個有限節點組成一個具有層次關系的集合。把它叫做 “樹” 是因為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。它具有以下的特點:
- 每個節點有零個或多個子節點;
- 沒有父節點的節點稱為根節點;
- 每一個非根節點有且只有一個父節點;
- 除了根節點外,每個子節點可以分為多個不相交的子樹;
在日常的應用中,我們討論和用的更多的是樹的其中一種結構,就是二叉樹。二叉樹是樹的特殊一種,具有如下特點:
- 每個結點最多有兩顆子結點。
- 左子樹和右子樹是有順序的,次序不能顛倒。
- 即使某結點只有一個子樹,也要區分左右子樹。
二叉樹是一種比較有用的折中方案,它添加,刪除元素都很快,并且在查找方面也有很多的算法優化,所以,二叉樹既有鏈表的好處,也有數組的好處,是兩者的優化方案,在處理大批量的動態數據方面非常有用。
二叉樹有很多擴展的數據結構,包括平衡二叉樹、紅黑樹、B+樹等,這些數據結構在二叉樹的基礎上衍生了很多的功能,在實際應用中廣泛用到,例如mysql的數據庫索引結構用的就是B+樹,還有HashMap的底層源碼中用到了紅黑樹。這些二叉樹的功能強大,但算法上比較復雜,想學習的話還是需要花時間去深入的。
八. 圖
圖是由結點的有窮集合V和邊的集合E組成。其中,為了與樹形結構加以區別,在圖結構中常常將結點稱為頂點,邊是頂點的有序偶對,若兩個頂點之間存在一條邊,就表示這兩個頂點具有相鄰關系。按照頂點指向的方向可分為無向圖和有向圖:
無向圖:
有向圖:
參考:《我的第一本算法書》
總結
以上是生活随笔為你收集整理的【数据结构】八种常见数据结构介绍的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 钉钉微应用怎么进入_蓝凌携手钉钉走进越秀
- 下一篇: [bzoj1036]树的统计