数据结构基础知识: 表 栈 队列 树 散列 堆
- 2019 年 11 月 21 日
- 筆記
1. 表,栈和队列
表,栈和队列是计算机科学中最简单和最基本的三种底层数据结构。事实上,每一个有意义的程序都将明晰地至少使用一种这样的数据结构,而栈则在程序中总是要间接地用到,不管你在程序中是否做了声明。
1.1 抽象数据类型(ADT)
在计算机软件编程中,我们会接触到诸如整型,浮点型,字符型,布尔型等基本数据类型,也有一些更为复杂的复合数据类型,如数组,字典(散列表),元组等。如果我们抛开这些数据类型具体实现,进一步抽象,给出更一般的定义,即每一种数据类型实际是一些特定操作
的集合。我们称这些操作的集合
为抽象数据类型
(abstract data type, ADT
)。ADT 是数学意义上的抽象,它不约束各个操作的具体实现,对于每种 ADT 并不存在什么法则来告诉我们必须要有哪些操作,这只是一个设计决策。
1.2 表ADT
表是一种形如 A_1, A_2, A_3, ldots, A_N 的数据结构。我们说这个表的大小是 N 。我们称大小为 0 的表为空表(empty list)。对于除空表以外的任何表,我们说 A_{i+1}(i<N) 后继 A_i (或继 A_i 之后)并称 A_{i-1}(i>1) 前驱 A_i 。定义表ADT的操作集合通常包含:
- PrintList: 打印表
- MakeEmpty: 返回空表
- Find: 返回关键字(key)首次出现的位置
- Insert: 从表的指定位置插入关键字(key)
- Delelte: 从表的指定位置删除关键字(key)
- FindKth: 返回指定位置上的元素
1.2.1 简单数组实现
我们最容易想到实现表的方法就是数组。使用数组实现表的各项操作,显而易见的时间复杂度是:
- PrintList: O(N)
- Find: O(N)
- FindKth: O(1)
- Insert: O(N)
- Delete: O(N)
我们不难发现,当插入和删除 N 个元素时,需要花费 O(N^2) 的时间,运行慢且表的大小必须事先已知。因此当需要具有插入和删除操作时,通常不使用简单数组来实现。
1.2.2 链表实现
为了避免插入和删除的线性开销,我们需要允许表可以不连续存储,否则表的部分或全部需要整体移动。因此,这种情况下更好的实现方式是链表(linked list)。
链表由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的结构的指针。我们称之为Next
指针。最后一个单元的Next
指针指向Null
。链表分为:单链表,双链表,循环链表。
链表的 C 语言实现:
#include <stdlib.h> struct Node { int Element; Node* Next; }; int IsEmpty(Node* L) { return L->Next == NULL; } int IsLast(Node* P, Node* L) { return P->Next == NULL; } Node* Find(int x, Node* L) { Node* P; P = L->Next; while(P != NULL && P->Element != x) P = P->Next; return P; } Node* FindPrevious(int x, Node* L) { Node* P; P = L; while(P->Next != NULL && P->Next->Element != x) P = P->Next; return P; } void Delete(int x, Node* L) { Node* P; Node* TmpCell; P = FindPrevious(x, L); if (!IsLast(P, L)) { TmpCell = P->Next; P->Next = TmpCell->Next; free(TmpCell); } } void Insert(int x, Node* L, Node* P) { Node* TmpCell; TmpCell = (Node*)malloc(sizeof(struct Node)); if (TmpCell != NULL) printf("Out of space!!!"); TmpCell->Element = x; TmpCell->Next = P->Next; P->Next = TmpCell; } void DeleteList(Node* L) { Node* P; Node* Tmp; P = L->Next; L->Next = NULL; while(P != NULL) { Tmp = P->Next; free(P); P = Tmp; } }
1.2 栈ADT
栈(stack)是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈的顶(top)。对栈的基本操作有Push
(进栈)和Pop
(出栈),前者相当于插入,后者则是删除最后插入的元素。最后插入的元素可以通过使用Top
操作在执行Pop
之前读取。
由于栈是一个表,因此任何实现表的方法都能实现栈。通常使用数组是一个较为简便的方法。
1.3 队列ADT
和栈一样,队列(queue)也是表。不同的是,使用队列时插入在一端进行而删除则在另一端进行。
队列的基本操作是Enqueue
(入队),它是在表的末端(rear 队尾)插入一个元素,还有 Dequeue
(出队),它是删除(或返回)在表的开头(front 对头)的元素。
2. 树
2.1 基础知识
对于大量的输入数据,链表的线性访问时间太慢,不宜使用。而“树”大部分操作的运行时间平均为 O(log N) 。
一课树是 N 个节点 N-1 条边的集合,其中的一个节点叫做根。
路径
从节点 n_1 到 n_k 的路径(path)定义为节点 n_1, n_2, …, n_k 的一个序列,使得对于 1 le i < k ,节点 n_i 是 n_{i+1} 的父亲。这个路径的长(length)为该路径上的边的条数,即 k-1 。从每一个节点到它自己都有一条长为 0 的路径。从根到每个节点有且仅有一条路径。
深度
对于任意节点 n_i , n_i 的深度(depth)为从根到 n_i 的唯一路径的长。因此,根的深度为 0 。
高度
n_i 的高(height)是从 n_i 到一片树叶的最长路径的长。因此,所有树叶的高度都是 0 。
祖先(ancestor)和后裔(descendant)
如果存在从 n_1 到 n_2 的一条路径,那么 n_1 是 n_2 的一位祖先而 n_2 是 n_1 的一个后裔。如果 n_1 ne n_2 ,那么 n_1 是 n_2 的一位真祖先(proper ancestor
)而 n_2 是 n_1 的一个真后裔(proper descendant
)。
2.2 树的实现
将每个节点的所有儿子都放在树节点的链表中。FirstChild
是指向第一个儿子的指针,NextSibling
指向下一个兄弟节点。
typedef struct TreeNode *PtrToNode; struct TreeNode { ElementType Element; PtrToNode FirstChild; PtrToNode NextSibling; }
2.3 树的遍历
先序遍历(preorder traversal)
在先序遍历中,对节点的处理工作是在它的诸儿子节点被处理之前进行的。例如:打印目录树形结构图,先打印父节点,再递归打印子节点。
后序遍历(postorder traversal)
在后序遍历中,在一个节点处的工作是在它的诸儿子节点被计算后进行的。例如:计算目录所占磁盘空间,在得到父节点占用空间前,需要先递归计算子节点所占用的磁盘空间,最后才能逐级向上得到根节点的磁盘总占用空间。
中序遍历(inorder traversal)
用于二叉树。遍历顺序:左子树,节点,右子树。
2.4 二叉树(binary tree)
在二叉树中,每个节点最多只有两个儿子。
二叉树的平均深度为 O(sqrt{N}) ,而对于特殊类型的二叉树,如二叉查找树(binary search tree),其平均深度是 O(log N) 。
2.4.1 二叉树实现
因为一棵二叉树最多有两个儿子,所以我们可以用指针直接指向它们。树节点的声明在结构上类似于双链表的声明。在声明中,一个节点就是由Key信息加上两个指向其他节点的指针(Left 和 Right)组成的结构。
typedef struct TreeNode *PtrToNode; typedef struct PtrToNode Tree; struct TreeNode { ElementType Element; Tree Left; Tree Right; }
二叉树有许多与搜索无关的重要应用。二叉树的主要用处之一是在编译器的设计领域。如二元表达式树。
2.4.2 查找树ADT——二叉查找树
二叉树的一个重要的应用是它们在查找中的使用。使二叉树成为二叉查找树的性质是,对于树中的每个节点 X ,它的左子树所有关键字的值小于 X ,而它右子树中所有关键字值大于 X 的关键字值。
操作集合:
- MakeEmpty
- Find
- FindMin 和 FindMax
- Insert
- Delete
2.4.3 AVL 树
AVL(Adelson-Velskii 和 Landis)树是带有平衡条件的二叉查找树。这个平衡条件必须要容易保持,而且它必须保证树的深度是 O(log N) 。最简单的想法是要求左右子树具有相同的高度。另一种平衡条件是要求每个节点都必须要有相同高度的左子树和右子树。虽然这种平衡条件保证了树的深度小,但是它太严格,难以使用,需要放宽条件。
一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。
单旋转
双旋转
2.4.4 伸展树(splay tree)
伸展树保证从空树开始任意连续 M 次对树的操作最多花费 O(M log N) 的时间。
2.5 B-树
虽然迄今为止我们所看到的查找树都是二叉树,但是还有一种常用的查找树不是二叉树。这种树叫做B-树(B-tree)。
阶为 M 的B-树是一棵具有下列结构特性的树:
- 树的根或者是一片树叶,或者其儿子数在2和M之间。
- 除根外,所有非树叶节点的儿子数在[ M/2 ]和 M 之间。
- 所有的树叶都在相同的深度上。
B-树实际用于数据库系统,在那里树被存储在物理的磁盘上而不是主存中。一般来说,对磁盘的访问要比任何的主存操作慢几个数量级。如果我们使用M阶B-树,那么磁盘访问的次数是 O(log_{M}N)
3. 散列
散列表的实现常常叫做散列(hashing)。散列是一种用于以常数平均时间执行插入,删除和查找的技术。但是,那些需要元素间任何排序信息的操作将不会得到有效的支持。因此,诸如 FindMin,FindMax 以及以线性时间按排序顺序将整个表进行打印的操作都是散列所不支持的。
3.1 一般想法
理想的散列表数据结构只不过是一个包含关键字(key)的具有固定大小的数组。典型情况下,一个关键字就是一个带有相关值(例如工资信息)的字符串。我们把表的大小记作Table-Size
,并将其理解为散列数据结构的一部分而不仅仅是浮动于全局的某个变量。通常的习惯是让表从0
到Table-Size - 1
变化。
每个关键字被映射到从0
到Table-Size - 1
这个范围中的某个数,并且被放到适当的单元中。这个映射就叫做散列函数
(hash function
)。理想情况下它应该运算简单
并且应该保证任何两个不同的关键字映射到不同的单元。不过,这是不可能的,因为单元的数目是有限的,而关键字实际上是用不完的。因此,我们寻找一个散列函数,该函数要在单元之间均匀
地分配关键字。这就是散列的基本想法。剩下的问题则是选择一个函数,决定当两个关键字散列到同一个值的时候(称为冲突collision
)应该做什么以及如何确定散列表的大小。
3.2 散列函数
3.2.1 输入整数关键字
如果输入的关键字是整数,则一般合理的方法就是直接返回“Key mod TableSize”
(关键字对表大小取模)的结果,除非Key
碰巧具有某些不理想的性质。例如,若表的大小是10
,而关键字都以0
为个位,这意味所有关键字取模运算的结果都是0
(都能被10整除)。这种情况,好的办法通常是保证表的大小是素数(也叫质数,只能被1和自身整除)。当输入的关键字是随机的整数时,散列函数不仅算起来简单
而且关键字的分配也很均匀
。
3.2.2 输入字符串关键字
通常,关键字是字符串;在这种情形下,散列函数需要仔细地选择。
一种方法是把字符串中字符的ASCII
码值加起来。以下该方法的C语言实现。
typedef unsigned int Index; Index Hash(const char *Key, int TableSize) { unsigned int HashVal = 0; while(*Key != '