Van Emde Boas樹
van Emde Boas樹（或稱vEB樹或van Emde Boas優先隊列）是一個在電腦科學中的資料結構，也是一種關聯陣列，也是一種樹，由荷蘭電腦科學家 Peter van Emde Boas領導的團隊於 1975 年發明，可以儲存鍵值範圍在 m 位以內的二進制整數，也就是 u= 2^m 是樹中可以儲存的最大數字時，它可以在 O(\log m) 時間內執行所有種類的基本操作（假設對 m 的位元操作可以在常數時間內執行），也就是 O(…
标签：#数据结构
共 69 篇文章
链表
在電腦科學中，链表（）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(n)和O(1)。 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的…
动态数组
），而某些插入因为需要内存分配而缓慢（时间，标示了乌龟)。展示了最终数组的“逻辑大小”和“容量”。]] 在计算机科学中，动态数组（dynamic array），也称为：可增长数组（growable array）、可调大小数组（ resizable array）、动态表格（ dynamic table）、可变化数组（mutable array）或数组列表（array list），是一种随机访问的、大小可变的列表数据结构，它允许增加或移除元…
二元决策图
在计算机科学中，二元决策图（），或译为二元判定图，是被用来表达一个布尔函数的一种数据结构。 延伸阅读 D. E. Knuth, "The Art of Computer Programming Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams" (Addison–Wesley Professional, March 27, 2009) …
红黑树
红黑树（）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为「对称二叉B树」，它现代的名字源于利奧尼達斯·J·吉巴斯和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在\text{O}(\log n)时间内完成查找、插入和删除，这里的n是树中元素的数目。 歷史 1972年，鲁道夫·拜尔發明了…
数据结构术语列表
这是一个数据结构的列表。更详细的内容请参考数据结构与算法列表。 資料型別 原始类型}- 布林：只有「真」和「假」兩種值的類型。 字符}-：代表一個字型，可以是一個英文字母或是一個中文字。 整數：可以表現有限範圍的整數。 浮點數：可以表示有限位數的有理數，常用來近似實數值。 双精度浮点数：相對於浮点数，双精度浮点数有兩倍的精度。 枚举：一个命名不重复的值的集合。 复合类型}- 陣列 結構 字符串 联合体 標籤聯合 參照 抽象数据类型 容器…
链 (数据结构)
计算机科学中，链数据结构是一种由许多记录 (节点)通过引用 (链接或指针)进行链接所构成的数据结构。 在链数据结构中，链接通常被视为一种特殊的、只能被解除引用或进行比较的数据类型。因此，链数据结构通常会与数组等需要对指针进行运算的数据结构进行对比。即使节点是以单个数组的形式实现的、且引用的是数组索引，链仍与数组等数据类型有区别：只要不对其索引进行算术运算，该数据结构本质上就仍是一个链表数据结构。 有两种进行连接的方式使用动态分配连接或使…
哈希表
散列表（）是根据键而直接访问在記憶體儲存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来讓人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。 一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名x到首字母F(x)的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取…
并查集
在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作： 查询（find）：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。 合并（unite/merge）：将两个集合合并为一个。 *添加：添加一个…
不透明数据类型
在计算机科学中，不透明数据类型是一种未在接口中定义其具体数据结构的数据类型。用户只能通过定义好的接口或子程序来操作这些数据类型，而无法直接访问其内部结构。表示可见的数据类型称为透明。不透明数据类型经常用于实现抽象数据类型。 不透明数据类型的典型示例包括作系统向应用程序软件提供的资源句柄。 不透明指针是不透明数据类型的一种特殊情况，该数据类型被声明为指向某些未指定数据类型的记录或数据结构的指针。例如，构成 C 编程语言规范一部分的标准库提…
優先佇列
优先队列（priority queue）是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列通常使用「堆積」（heap）实现。 操作 优先队列至少需要支持下述操作： 插入带优先级的元素（insert_with_priority） 取出具有最高优先级的元素（pull_highest_priority_element） 查看最高优先级…
霍夫曼编码
霍夫曼編碼（），又譯為哈夫曼编码、赫夫曼编码，是一種用於无损数据压缩的熵編碼（權編碼）演算法。由美國計算機科學家大衛·霍夫曼於1952年發明。 簡介 在计算机资讯处理中，霍夫曼編碼使用變長編碼表對源符號（如文件中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符號出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字符串的平均長度、期望值降低，從而達到無損壓縮數據的目的。 例如，…
符号表
在计算机科学中，符号表是一种用于语言翻译器（例如编译器和解释器）中的数据结构。在符号表中，程序源代码中的每个标识符都和它的声明或使用信息绑定在一起，比如其数据类型、作用域以及内存地址。 实现 散列表是用来实现符号表的一种常用技术。编译器可能会使用一个很大的符号表来包含所有的符号，或是针对不同的作用域使用层次结构的多个独立的符号表。 使用 目标文件中通常会有一个包含了所有外部可见标识符的符号表。在链接不同的目标文件时，链接器会使用这些文件…
八叉树
。右：對應的八叉樹]] 八叉树（）是一种树形数据结构，每个内部节点都正好有八个子节点。八叉树常用于分割三维空间，将其递归细分为八个卦限。八叉树是四叉树在三维空间中的对应，在三维图形、三维游戏引擎等领域有很多应用。 表示空间 八叉树的每个节点都可以代表一个空间，对应的八个子节点则将这个空间细分为八个卦限。点域（，简称PR）八叉树的节点中都存储着一个三维点，即该节点对应区域的「中心」，也是八个子节点对应区域中的一个角落。矩阵（，简称MX）八…
平衡树
平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。]] 在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。 ]] 基本操作 旋转（rotate）：几乎所有平衡树的操作都基于树旋转操作（也有部分基于重构，如替罪羊树），通过旋转操作可以使得树趋于平…
最短路问题
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： 确定起点的最短路径问题 - 也叫单源最短路问题，即已知起始结点，求最短路径的问题。在边权非负时适合使用Dijkstra算法，若边权为负时则适合使用Bellman-ford算法或者SPFA算法。 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完…
邻接矩阵
在图论和計算機科學中，邻接矩阵（）是一種方块矩阵，用來表示有限图。它的每個元素代表各点之间是否有边相连。 作爲特例，簡單圖的鄰接矩陣是(0,1)矩陣並且對角線元素都爲0。無向圖的鄰接矩陣是對稱矩陣。圖和其鄰接矩陣的特徵值和特徵向量之間的關系是譜圖理論的研究對象。 圖的關聯矩陣}-需要和鄰接矩陣區分。它是圖的另一種矩陣表示方式，它的元素表示各個节点-邊對是否相關。還有圖的度數矩陣，含有每個結點的度數信息。 距離矩陣可算是鄰接矩陣的擴充。 …
線段樹 (儲存區間)
線段樹（）是一種二元樹形資料結構，1977年由喬恩·本特利發明，用以儲存區間或線段，並且允許快速查詢結構內包含某一點的所有區間。 一個包含n個區間的線段樹，空間複雜度為O(n)，查詢的時間複雜度則為O(\log n+k)，其中k是符合條件的區間數量。 此資料結構亦可推廣到高維度。 結構 線段樹是一個平衡的二叉树，它将每个长度不为1的区间划分成左右两个区间递归求解。令整個區間的長度為N，則其有N個葉節點，每個葉節點代表一個單位區間，每個內…
关联数组
在计算机科学中，关联数组（），又称映射（）、字典（）是一个抽象的数据结构，它包含着类似于（键，值）的有序对。一个关联数组中的有序对可以重复（如C++中的multimap）也可以不重复（如C++中的map）。 这种数据结构包含以下几种常见的操作： 向关联数组添加配对 从关联数组内删除配对 修改关联数组内的配对 根据已知的键寻找配对 字典问题是设计一种能够具备关联数组特性的数据结构。解决字典问题的常用方法，是利用散列表或搜索树。有些情况下，…
環形緩衝區
圆形缓冲区（circular buffer），也称作圆形队列（circular queue），循环缓冲区（cyclic buffer），环形缓冲区（ring buffer），是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构，适合缓存数据流。 用法 圆形缓冲区的一个有用特性是：当一个数据元素被用掉后，其余数据元素不需要移动其存储位置。相反，一个非圆形缓冲区（例如一个普通的队列）在用掉一个数据元素后，其余数据元素需要向前搬移。换句话说…