基本数据结构
基本数据结构是存储和访问数据的组织方式——数组、链表、哈希表、树、堆及其相关结构——它们决定了在其之上构建的操作的效率。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
数据结构是一种组织和存储数据的方式，以便其抽象数据类型定义的操作能够高效执行；基本数据结构是通用结构中的一小部分，大多数其他结构都是在此基础上构建的。
Scope
此领域涵盖抽象数据类型（列表、字典、优先队列、集合）和实现它们的具体结构，以及它们核心操作（插入、删除、搜索、更新）在最坏情况和摊还分析下的成本。它探讨了结构选择如何影响算法性能，并与依赖这些结构的设计范式以及图和字符串算法相关联。它不包括其他子领域处理的数据库和文件系统存储结构。
Sub-topics
Core questions
- 应用程序需要哪种抽象数据类型，哪种具体结构能最好地实现它？
- 给定结构上每个操作的最坏情况和摊还成本是多少？
- 结构如何在内存和时间之间，或读取速度和更新速度之间进行权衡？
- 维护不变性（有序性、平衡性、堆属性）如何限制操作成本？
- 何时简单的结构优于渐近更快但更复杂的结构？
Key concepts
- 抽象数据类型
- 数组和链表
- 栈和队列
- 哈希表
- 二叉搜索树
- 平衡树
- 堆和优先队列
- 摊还分析
- 时间-空间权衡
Key theories
- 抽象数据类型与实现
- 抽象数据类型指定了独立于表示的操作及其语义；多个具体数据结构可以用不同的性能特征实现相同的ADT，从而使设计者能够分别推理正确性和成本。
- 摊还分析
- 某些结构（动态数组、伸展树）偶尔会有昂贵的操作，但在操作序列的平均情况下是廉价的；摊还分析（聚合、记账、势能法）严格地界定了这种平均成本。
Clinical relevance
基本数据结构是几乎所有软件的基石：哈希表支持字典和数据库索引，平衡树和B树组织文件系统和数据库，优先队列驱动调度器和事件模拟，而正确的结构选择通常决定了系统是否能扩展。
History
基础数据结构在高德纳（Knuth）的《计算机程序设计艺术》中从1968年开始被编目。自平衡树（AVL树，1962年；红黑树和B树，1970年代）以及斐波那契堆和伸展树（1980年代，主要归功于塔扬及其合作者）等高级结构扩展了该领域，而摊还分析则对其性能进行了严格的解释。
Key figures
- Donald Knuth
- Robert Sedgewick
- Robert Tarjan
- Rudolf Bayer
Related topics
Seminal works
- knuth1997vol1
- cormen2009
- sedgewick2011
Frequently asked questions
- 我该如何在哈希表和平衡搜索树之间做出选择？
- 哈希表提供预期O(1)的查找和插入，但没有顺序；而平衡搜索树提供O(log n)的操作，并保持键的有序性，支持范围查询和有序遍历。对于纯粹的键查找选择哈希，当排序或范围操作很重要时选择树。
- 数据结构的摊还成本意味着什么？
- 摊还成本是在最坏情况操作序列中，每次操作的平均成本。例如，动态数组偶尔需要O(n)来调整大小，但由于调整大小相对于廉价的追加操作来说是罕见的，因此每次追加的平均成本为O(1)。