數據結構術語列表

數據結構術語列表是一個數據結構的列表，數據結構是抽象數據結構的物理實現，包含數據的邏輯結構：集合結構、線性結構、樹形結構和圖形結構。

基本介紹

• 中文名：數據結構術語列表
• 外文名：List of data structures
• 分類：計算機編程

數據類型

數據結構中的數據類型主要分為原始類型、複合類型和抽象數據類型這三種。

原始類型

布爾（boolean）	只有“真”和“假”兩種值的類型
字元（char）	代表一個字型，可以是一個英文字母或是一個中文字
整數（int）	可以表現有限範圍的整數
浮點數（float）	可以表示有限位數的有理數，常用來近似實數值
雙精度浮點數（double）	相對於浮點數，雙精度浮點數有兩倍的精度
枚舉（enum）	一種特定類型對象的計數

複合類型

數組	有序的元素序列
結構	特定關係
字元串	由零個或多個字元組成的有限序列
聯合體	一種由具有這樣的值的變數形成的數據結構
標籤聯合	能夠存儲一組不同但是固定的類型中某個類型的對象

抽象數據類型

容器	以一種遵循特定訪問規則的系統的方法來存儲對象
集合	一組可變數量的數據項（也可能是0個）的組合
關係數組	包含著類似於（鍵，值）的有序對
佇列	先進先出的線性表
堆疊	只能允許在鍊表或數組的一端進行加入數據和輸出數據
線性表	由多個數據元素（結點）組成的有限序列
樹狀圖	模擬具有樹狀結構性質的數據集合

線性數據結構

數組

數組	有序的元素序列
位段	把數據以位的形式緊湊的儲存
環形緩衝器	適合快取數據流
控制表	決定控制流程或是主要影響控制流程的表
查找表	用簡單的查詢操作替換運行時計算的數組
矩陣	由m行（row）n列（column）元素排列成的矩形陣列
稀疏矩陣	元素大部分為零的矩陣
可變長數組	數組對象的長度在運行時（而不是編譯時）確定
平行數組	多個數組隱式表示一個以記錄（record）為元素的數組

列表

鍊表	一種線性表，但是並不會按線性的順序存儲數據
雙向鍊表	每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅
跳躍列表	允許快速查詢一個有序連續元素的數據鍊表
異或鍊表	一種鏈式存儲結構
自由表	一種用來實現特定動態記憶體分配方案的數據結構

樹

主條目：樹 (數據結構)

二叉樹

AA樹	自平衡二叉查找樹用於高效存儲和檢索序數據
二叉搜尋樹	查找、插入的時間複雜度較低
AVL樹	最先發明的自平衡二叉查找樹
二叉樹	每個節點最多只有兩個分支的樹結構
笛卡爾樹	具有堆的有序性，中序遍歷可以輸出原數列
紅黑樹	典型的用途是實現關聯數組
平衡樹	所有葉子的深度趨於平衡
伸展樹	能在均攤O(logn)的時間內完成基於伸展（Splay）操作的插入、查找、修改和刪除操作
樹堆	實現簡單，且能基本實現隨機平衡的結構
加權平衡樹	用來實現集合、字典（映射）和序列的平衡樹

B樹

B樹	一種自平衡的樹，能夠保持數據有序
B+樹	通常用於資料庫和作業系統的檔案系統中
2-3樹	內部節點要么有2個孩子和1個數據元素，要么有3個孩子和2個數據元素
2-3-4樹	在多數程式語言中實現起來相對困難

堆

堆	通常是一個可以被看做一棵樹的數組對象
二叉堆	一種類似於二叉堆的堆結構
二項堆	可以快速合併兩個堆
斐波那契堆	有比二項式堆更好的平攤分析性能，可用於實現合併優先佇列
Treap	有一個隨機附加域滿足堆的性質的二叉搜尋樹

Trie

前綴樹	一種有序樹，用於保存關聯數組，其中的鍵通常是字元串
基數樹	一種更節省空間的Trie
後綴樹	快速解決很多關於字元串的問題
Judy array	一種高性能、低記憶體消耗的數據結構

圖

圖	圖（Graph）用於表示物件與物件之間的關係
鄰接表	表示圖中與每一個頂點相鄰的邊集的集合
鄰接矩陣	用兩個數組分別存儲數據元素（頂點）的信息和數據元素之間的關係（邊或弧）的信息
場景圖	組織和管理三維虛擬場景的一種數據結構
二元決策圖	用來表達一個布爾函式的一種數據結構
偽圖	允許有多重邊的圖
超圖	是一種廣義上的圖，它的一條邊可以連線任意數量的頂點