开始上手
# 简介
数据结构是计算机科学的关键内容,也是构建高效算法的必要基础。本话题旨在围绕各类数据结构的设计与实现,揭示其中的规律原理与方法技巧。
数据结构是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。
数据结构往往同高效的检索算法和索引技术有关。数据结构可以分为逻辑结构和存储结构,有四类基本逻辑结构:集合、线性结构、树形结构、图状结构。这几类结构有以下几个特点:
集合结构:除了同属于一种类型外,别无其它关系。
线性结构:元素之间存在一对一关系。常见类型有:数组、链表、队列、栈。它们之间在操作上有所区别。例如:链表可在任意位置插入或删除元素,而队列在队尾插入元素、队头删除元素,栈只能在栈顶进行插入,删除操作。
树形结构:元素之间存在一对多关系。常见类型有:树 (有许多特例:二叉树、平衡二叉树、查找树等)。
图形结构:元素之间存在多对多关系,图形结构中每个结点的前驱结点数和后续结点多个数可以任意。
# 数据结构的类型
有两种类型的数据结构:原始(Primitive)数据结构、非原始(Non-primitive)数据结构。
原始数据结构:原始数据结构是原始的数据类型。int、char、float、double 和 pointer 是可以保存单个值的原始数据结构。
非原始数据结构:非原始数据结构分为两种类型。线性数据结构、非线性数据结构。
线性数据结构:
以顺序方式排列的数据被称为线性数据结构。基于此原则的数据结构是数组、链表、堆栈和队列。在这些数据结构中,一个元素只与另一个元素以线性方式连接。
当一个元素与 "n" 个元素相连时,被称为非线性数据结构。最好的例子是树和图。在这种情况下,元素是以随机方式排列的。
数据结构也可以分为以下几种:
- 静态数据结构。这是一种数据结构,其大小是在编译时分配的。因此,最大尺寸是固定的。
- 动态数据结构。它是一种数据结构类型,其大小在运行时分配。因此,最大尺寸是灵活的。
# 主要操作
可以在数据结构上进行的主要或常见的操作是:
- 搜索:可以在一个数据结构中搜索任何元素。
- 排序。可以按照升序或降序对数据结构中的元素进行排序。
- 插入。也可以在一个数据结构中插入新的元素。
- 更新。也可以更新元素,也就是说,我们可以用另一个元素替换这个元素。
- 删除。也可以执行删除操作,将该元素从数据结构中删除。
# 如何选择数据结构
数据结构是一种组织数据的方式,以便能够有效地使用它。在这里,我们使用了高效这个词,从空间和时间两方面来说。例如,堆栈是一个 ADT(抽象数据类型),它使用数组或链接列表数据结构来实现。因此,我们得出结论,我们需要一些数据结构来实现一个特定的 ADT。
一个 ADT 告诉我们要做什么,而数据结构告诉我们如何去做。换句话说,我们可以说 ADT 给了我们蓝图,而数据结构提供了实现部分。现在问题来了:如何才能知道哪种数据结构可用于某个特定的 ADT?
因为不同的数据结构可以在一个特定的 ADT 中实现,但不同的实现方式要在时间和空间上进行比较。例如,堆栈 ADT 可以由数组和链表来实现。假设数组提供的是时间效率,而链表提供的是空间效率,那么就会选择最适合当前用户需求的那一种。
# 数据结构的优点
以下是数据结构的优点:
- 效率。如果为实现一个特定的 ADT 而选择的数据结构是恰当的,那么它将使程序在时间和空间上非常有效。
- 可重用性。数据结构提供了重用性,意味着多个客户程序可以使用该数据结构。
- 抽象性。ADT 所指定的数据结构也提供了抽象的层次。客户端不能看到数据结构的内部工作,所以它不必担心实现部分的问题。客户端只能看到接口。
# 常见数据结构
# 数组(Array)
数组是一种聚合数据类型,它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构,在各种编程语言中都有对应。一个数组可以分解为多个数组元素,按照数据元素的类型,数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。数组还可以有一维、二维以及多维等表现形式。
# 栈(Stack)
栈是一种特殊的线性表,它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据,也就是说,先插入的数据将被压入栈底,最后插入的数据在栈顶,读出数据时,从栈顶开始逐个读出。栈在汇编语言程序中,经常用于重要数据的现场保护。栈中没有数据时,称为空栈。
# 队列(Queue)
队列和栈类似,也是一种特殊的线性表。和栈不同的是,队列只允许在表的一端进行插入操作,而在另一端进行删除操作。一般来说,进行插入操作的一端称为队尾,进行删除操作的一端称为队头。队列中没有元素时,称为空队列。
# 链表(Linked List)
链表是一种数据元素按照链式存储结构进行存储的数据结构,这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成,每个数据结点包括数据域和指针域两部分。其中,指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。
# 树(Tree)
树是典型的非线性结构,它是包括,2 个结点的有穷集合 K。在树结构中,有且仅有一个根结点,该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点,而且可以有两个后继结点。
- 二叉树
- 遍历二叉树:前序(先中间,再左边,后右边);中序(先左边,再中间,后右边);后序(先左边,再右边,后中间)。
- 线索二叉树:用二插链表实现的二叉树,将那些没有使用的左右指针指向前驱和后继(前驱和后继就是遍历后(例如用中序遍历)的数据序列某一个数据的前面和后面的数据),形成的二叉树为线索二叉树。一般用在经常遍历和利用前驱和后继查找结构的情况。
- 赫夫曼树:用于压缩。
- 二叉排序树:根节点的左子树若不为空,则左子树所有节点都小于根节点。根节点的右子树若不为空,则右子树所有节点都大于根结点。根节点的左右子树不为空,则其都是二叉平衡树。
- 平衡二叉树:一颗左右子树高度差至多等于 1 的二叉排序树。添加节点的时候,根据不平衡子树左旋右,保证最后的树是平衡的。优点:查找,插入,删除时间复杂度都是:O(logn)。
- 多路查找树:结点的孩子不止为两个,结点存的值补位一个。如 2-3 树,2-3-4 树,B 树,B + 树
- 红黑树:也是二叉排序树。利用一个结点的属性表明这个结点是红是黑。查找等同于二叉排序树。插入和删除利用这个颜色属性来保证操作之后树还是平衡的。所以查找,插入和删除的时间复杂度都是:O(logn)。统计性能比平衡二叉树好。
- 堆:二叉树,分为大顶堆,小顶堆。大顶堆的要求是每个节点的值都不大于其父节点的值,小顶堆反过来。
# 图(Graph)
图是另一种非线性数据结构。在图结构中,数据结点一般称为顶点,而边是顶点的有序偶对。如果两个顶点之间存在一条边,那么就表示这两个顶点具有相邻关系。
五种构造图的方式:
- 遍历:
深度优先:一个劲的朝一个方向使劲,当重复了就返回。
广度优先:先从一个顶点触发,拿到这个顶点,再把与这个顶点相关的顶点放入队列,再从队列取数据,再把与这个新取的顶点相关的顶点(非重复过的顶点)放入队列,依次同理操作
- 最小生成树:
普里姆(Prim)算法:O (n2)
克鲁斯卡尔(Kruskal)算法:O (e*loge)
- 最短路径:
迪杰斯特拉(Dijkstra)算法 O (n3)
弗洛伊德(Floyd)算法 O (n3)
- 拓扑排序:AOV 网:用顶点表示活动,用弧表示优先关系的有向图。
拓扑排序算法:O (n+e) n 个顶点 e 条边
- 关键路径:AOE 网:用顶点表示时间,用有向边表示活动,用边的权值表示持续的时间的有向图。
关键算法路径:O (n+e)
# 堆(Heap)
堆是一种特殊的树形数据结构,一般讨论的堆都是二叉堆。堆的特点是根结点的值是所有结点中最小的或者最大的,并且根结点的两个子树也是一个堆结构。
# 散列表 (Hash)
散列表源自于散列函数 (Hash function),其思想是如果在结构中存在关键字和 T 相等的记录,那么必定在 F (T) 的存储位置可以找到该记录,这样就可以不用进行比较操作而直接取得所查记录。