來源 | http://suo.im/6oo92L
8種常用資料結構
資料結構是一種特殊的組織和存盤資料的方式，可以使我們可以更高效地對存盤的資料執行操作，資料結構在計算機科學和軟體工程領域具有廣泛而多樣的用途，
?
幾乎所有已開發的程式或軟體系統都使用資料結構，此外，資料結構屬于計算機科學和軟體工程的基礎，當涉及軟體工程面試問題時，這是一個關鍵主題，因此，作為開發人員，我們必須對資料結構有充分的了解，
在本文中，我將簡要解釋每個程式員必須知道的8種常用資料結構，
C/C++的學習裙【七一二 二八四 七零五 】，無論你是小白還是進階者，是想轉行還是想入行都可以來了解一起進步一起學習！裙內有開發工具，很多干貨和技術資料分享！
1.陣列
陣列是固定大小的結構，可以容納相同資料型別的專案，它可以是整數陣列，浮點數陣列，字串陣列或什至是陣列陣列（例如二維陣列），陣列已建立索引，這意味著可以進行隨機訪問，
?
Fig 1. Visualization of basic Terminology of Arrays
陣列運算
· 遍歷：遍歷所有元素并進行列印，
· 插入：將一個或多個元素插入陣列，
· 洗掉：從陣列中洗掉元素
· 搜索：在陣列中搜索元素，您可以按元素的值或索引搜索元素
· 更新：在給定索引處更新現有元素的值
陣列的應用
· 用作構建其他資料結構的基礎，例如陣列串列，堆，哈希表，向量和矩陣，
· 用于不同的排序演算法，例如插入排序，快速排序，冒泡排序和合并排序，
2.鏈表
鏈表是一種順序結構，由相互鏈接的線性順序專案序列組成，因此，您必須順序訪問資料，并且無法進行隨機訪問，鏈接串列提供了動態集的簡單靈活的表示形式，
讓我們考慮以下有關鏈表的術語，您可以通過參考圖2來獲得一個清晰的主意，
· 鏈表中的元素稱為節點，
· 每個節點都包含一個密鑰和一個指向其后繼節點（稱為next）的指標，
· 名為head的屬性指向鏈接串列的第一個元素，
· 鏈表的最后一個元素稱為尾，
?
Fig 2. Visualization of basic Terminology of Linked Lists
以下是可用的各種型別的鏈表，
· 單鏈串列—只能沿正向遍歷專案，
· 雙鏈表-可以在前進和后退方向上遍歷專案，節點由一個稱為上一個的附加指標組成，指向上一個節點，
· 回圈鏈接串列—鏈接串列，其中頭的上一個指標指向尾部，尾號的下一個指標指向頭，
?
鏈表操作
· 搜索：通過簡單的線性搜索在給定的鏈表中找到鍵為k的第一個元素，并回傳指向該元素的指標
· 插入：在鏈接串列中插入一個密鑰，插入可以通過3種不同的方式完成；在串列的開頭插入，在串列的末尾插入，然后在串列的中間插入，
· 洗掉：從給定的鏈表中洗掉元素x，您不能單步洗掉節點，洗掉可以通過3種不同方式完成；從串列的開頭洗掉，從串列的末尾洗掉，然后從串列的中間洗掉，
鏈表的應用
· 用于編譯器設計中的符號表管理，
· 用于在使用Alt Tab（使用回圈鏈表實作）的程式之間進行切換，
3.堆疊
堆疊是一種LIFO（后進先出-最后放置的元素可以首先訪問）結構，該結構通常在許多編程語言中都可以找到，該結構被稱為"堆疊"，因為它類似于真實世界的堆疊-板的堆疊，
?
Image Source: pixabay
堆疊操作
下面給出了可以在堆疊上執行的2個基本操作，請參考圖3，以更好地了解堆疊操作，
· Push 推送：在堆疊頂部插入一個元素，
· Pop 彈出：洗掉最上面的元素并回傳，
?
Fig 3. Visualization of basic Operations of Stacks
此外，為堆疊提供了以下附加功能，以檢查其狀態，
· Peep 窺視：回傳堆疊的頂部元素而不洗掉它，
· isEmpty：檢查堆疊是否為空，
· isFull：檢查堆疊是否已滿，
堆疊的應用
· 用于運算式評估（例如：用于決議和評估數學運算式的調車場演算法），
· 用于在遞回編程中實作函式呼叫，
4.佇列
佇列是一種FIFO（先進先出-首先放置的元素可以首先訪問）結構，該結構通常在許多編程語言中都可以找到，該結構被稱為"佇列"，因為它類似于現實世界中的佇列-人們在佇列中等待，
?
Image Source: pixabay
佇列操作
下面給出了可以在佇列上執行的2個基本操作，請參考圖4，以更好地了解堆疊操作，
· 進隊：將元素插入佇列的末尾，
· 出隊：從佇列的開頭洗掉元素，
?
Fig 4. Visualization of Basic Operations of Queues
佇列的應用
· 用于管理多執行緒中的執行緒，
· 用于實施排隊系統（例如：優先級佇列），
5.哈希表
哈希表是一種資料結構，用于存盤具有與每個鍵相關聯的鍵的值，此外，如果我們知道與值關聯的鍵，則它有效地支持查找，因此，無論資料大小如何，插入和搜索都非常有效，
當存盤在表中時，直接尋址使用值和鍵之間的一對一映射，但是，當存在大量鍵值對時，此方法存在問題，該表將具有很多記錄，并且非常龐大，考慮到典型計算機上的可用記憶體，該表可能不切實際甚至無法存盤，為避免此問題，我們使用哈希表，關于哈希表的詳細介紹可以在python入門與進階公眾號領取演算法電子書
哈希函式
名為哈希函式（h）的特殊函式用于克服直接尋址中的上述問題，
在直接訪問中，帶有密鑰k的值存盤在插槽k中，使用哈希函式，我們可以計算出每個值都指向的表（插槽）的索引，使用給定鍵的哈希函式計算的值稱為哈希值，它表示該值映射到的表的索引，
· h：哈希函式
· k：應確定其哈希值的鍵
· m：哈希表的大小（可用插槽數），一個不接近2的精確乘方的素數是m的一個不錯的選擇，
?
Fig 5. Representation of a Hash Function
· 1→1→1
· 5→5→5
· 23→23→3
· 63→63→3
從上面給出的最后兩個示例中，我們可以看到，當哈希函式為多個鍵生成相同的索引時，就會發生沖突，我們可以通過選擇合適的哈希函式h并使用鏈接和開放式尋址等技術來解決沖突，
哈希表的應用
· 用于實作資料庫索引，
· 用于實作關聯陣列，
· 用于實作"設定"資料結構，
6.樹
樹是一種層次結構，其中資料按層次進行組織并鏈接在一起，此結構與鏈接串列不同，而在鏈接串列中，專案以線性順序鏈接，
在過去的幾十年中，已經開發出各種型別的樹木，以適合某些應用并滿足某些限制，一些示例是二叉搜索樹，B樹，紅黑樹，展開樹，AVL樹和n元樹，
二叉搜索樹
顧名思義，二進制搜索樹（BST）是一種二進制樹，其中資料以分層結構進行組織，此資料結構按排序順序存盤值，我們將在本課程中詳細研究這些值，
二叉搜索樹中的每個節點都包含以下屬性，
· key：存盤在節點中的值，
· left：指向左孩子的指標，
· 右：指向正確孩子的指標，
· p：指向父節點的指標，
二叉搜索樹具有獨特的屬性，可將其與其他樹區分開，此屬性稱為binary-search-tree屬性，
令x為二叉搜索樹中的一個節點，
· 如果y是x左子樹中的一個節點，則y.key≤x.key
· 如果y是x的右子樹中的節點，則y.key≥x.key
?
Fig 6. Visualization of Basic Terminology of Trees.
樹的應用
· 二叉樹：用于實作運算式決議器和運算式求解器，
· 二進制搜索樹：用于許多不斷輸入和輸出資料的搜索應用程式中，
· 堆：由JVM（Java虛擬機）用來存盤Java物件，
· Trap：用于無線網路，
7.堆
堆是二叉樹的一種特殊情況，其中將父節點與其子節點的值進行比較，并對其進行相應排列，
讓我們看看如何表示堆，堆可以使用樹和陣串列示，圖7和8顯示了我們如何使用二叉樹和陣列來表示二叉堆，
?
Fig 7. Binary Tree Representation of a Heap
?
Fig 8. Array Representation of a Heap
堆可以有2種型別，
· 最小堆-父項的密鑰小于或等于子項的密鑰，這稱為min-heap屬性，根將包含堆的最小值，
· 最大堆數-父項的密鑰大于或等于子項的密鑰，這稱為max-heap屬性，根將包含堆的最大值，
堆的應用
· 用于實作優先級佇列，因為可以根據堆屬性對優先級值進行排序，
· 可以在O（log n）時間內使用堆來實作佇列功能，
· 用于查找給定陣列中k個最小（或最大）的值，
· 用于堆排序演算法，
8.圖
一個圖由一組有限的頂點或節點以及一組連接這些頂點的邊組成，
圖的順序是圖中的頂點數，圖的大小是圖中的邊數，
如果兩個節點通過同一邊彼此連接，則稱它們為相鄰節點，
有向圖
如果圖形G的所有邊緣都具有指示什么是起始頂點和什么是終止頂點的方向，則稱該圖形為有向圖，
我們說（u，v）從頂點u入射或離開頂點u，然后入射到或進入頂點v，
自環：從頂點到自身的邊，
無向圖
如果圖G的所有邊緣均無方向，則稱其為無向圖，它可以在兩個頂點之間以兩種方式傳播，
如果頂點未連接到圖中的任何其他節點，則稱該頂點為孤立的，
?
Fig 9. Visualization of Terminology of Graphs
圖的應用
· 用于表示社交媒體網路，每個用戶都是一個頂點，并且在用戶連接時會創建一條邊，
· 用于表示搜索引擎的網頁和鏈接，互聯網上的網頁通過超鏈接相互鏈接，每頁是一個頂點，兩頁之間的超鏈接是一條邊，用于Google中的頁面排名，
· 用于表示GPS中的位置和路線，位置是頂點，連接位置的路線是邊，用于計算兩個位置之間的最短路徑，
參考文獻
[1]演算法簡介，第三版，作者：托馬斯·H·科門（Thomas H. Cormen），查爾斯·E·雷森（Charles E. Leiserson），羅納德·L·里維斯特（Ronald L. Rivest）和克利福德·斯坦（Clifford Stein），
[2]來自Wikipedia的資料結構串列
(本文翻譯自Vijini Mallawaarachchi的文章《8 Common Data Structures every Programmer must know》，參考：https://towardsdatascience.com/8-common-data-structures-every-programmer-must-know-171acf6a1a42)
如果你對C/C++感興趣，想學編程，小編推薦一個C/C++技術交流群【點擊進入】！
涉及到了：編程入門、游戲編程、網路編程、Windows編程、Linux編程、Qt界面開發、黑客等等......
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/212693.html
標籤：其他