数据结构与算法课程笔记

2023-01-05

hits

本文共4626字，阅读完需要约16分钟。

计算机也许足够快，但并非无限快。

数据结构与算法课程笔记

intros

绪论

这门课研究什么？

非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树和图的数据结构。因此，简单地说，数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。

八股：数据、数据元素、数据项和数据对象

数据 (Data) 是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑中用到的字符串，多媒体程序处理的图形、图像、声音及动画等通过特殊编码定义后的数据。
数据元素(Data Element)是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、记录等。数据元素用千完整地描述一个对象，如前一节示例中的一名学生记录，树中棋盘的一个格局（状态），以及图中的一个顶点等。
数据项 (Data Item) 是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象 (Data Object) 是性质相同的数据元素的集合，是数据的一个子集。
……只要集合内元素的性质均相同，都可称之为一个数据对象。

八股：数据结构

逻辑结构

逻辑结构：数据的逻辑结构是从逻辑关系上描述数据，

它与数据的存储无关，是独立于计算机的。

数据的逻辑结构有两个要素：一是数据元素；二是关系。

存储结构

数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。

链式存储结构需要给每个结点附加指针字段，用于存放后继元素的存储地址。

八股：算法

五个重要特性：

有穷性
确定性
可行性
输入
输出

评价优劣的标准：

正确性
可读性
健壮性
高效性

复杂度：

设每条语句执行一次所需的时间均是单位时间，则一个算法的执行时间可用该算法中有语句频度之和来度量。

省略号：它表示随问题规模 n 的增大，算法执行时间的增长率和的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。

线性表

单链表

顺序存储结构是一种随机存取(Random Access)的存储结构。

链式表示是循序访问/顺序存取的。

下面是单链表。

#include <bits/stdc++.h>
using namespace std;
struct node{
	int value;
	node * next;
};
int main(){
	int t;
	/* Input Test */
	node * head = new node;
	node * cur = head;
	while(1){
		cin >> t;
		if(t == -1){
			break;
		}
		node * new_node = new node;
		new_node->value = t;
		cur->next = new_node;
		new_node->next = NULL;
		cur = new_node;
	}
	while(head != NULL){
		cout << head->value << endl;
		node * tmp = head;
		head = head->next;
		delete tmp;
	}
	return 0;
}

有几个需要注意的地方：

一般情况下，为了处理方便，在单链表的第一个结点之前附设一个结点，称之为头结点。
首元结点是指链表中存储第一个数据元素的结点。
头结点便于首元结点的处理，便于空表和非空表的统一处理————当链表不设头结点，假设为单链表的头指针，它应该指向首元结点，则当单链表为长度为的空表时，指针为空（判定空表的条件可记为：）但是在设置头结点的情况下，就可以用头结点的后继指针，来判断是否为空表了。

插入和删除操作：

void insert(node * prev, int number){
	node * new_node = new node;
	new_node->value = number;
	new_node->next = prev->next;
	prev->next = new_node;
}
void delete_(node * prev){
	prev->next = prev->next->next;

}

循环链表

其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点。

双向链表

#include<bits/stdc++.h>
using namespace std;
struct node{
	int value;
	node * prev;
	node * next;
};
void insert(node * p, int number){
	node * insertnode = new node;
	insertnode->value = number;
	p->next->prev = insertnode;
	insertnode->next = p->next;
	p->next = insertnode;
	insertnode->prev = p;
}
void delete_(node * cur){
	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;
}
int main(){
	node * head = new node;
	node * cur = head;
	int t;
	while(true){
		cin >> t;
		if(t == -1){
			break;
		}
		node * new_node = new node;
		new_node->value = t;
		new_node->prev = cur;
		new_node->next = NULL;
		cur->next = new_node;
		cur = new_node;
	}
	/* unit test */

	// insert(head->next->next->next->next->next->next, 1000);

	// delete_(head->next->next->next);

	cur = head->next;
	while(cur != NULL){
		cout << cur->value << endl;
		cur = cur->next;
	}

	return 0;
}

这是删除和插入操作。

void insert(node * p, int number){
	node * insertnode = new node;
	insertnode->value = number;
	p->next->prev = insertnode;
	insertnode->next = p->next;
	p->next = insertnode;
	insertnode->prev = p;
}
void delete_(node * cur){
	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;
}

顺序 vs. 链表

空间性能：存储空间的分配；存储密度的大小
时间性能：Access, insert, delete

栈与队列

栈 (stack) 是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶 (top), 相应地，表头端称为栈底 (bottom)。不含元素的空表称为空栈。

队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。它只允许在表的一端进行插入，而在另一端删除元素。

实现

顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置。

一般我们可能会用C++ STL stack和C++ STL queue来实现栈和队列的操作。

循环队列

怎样解决这种 “假溢出” 问题呢？一个较巧妙的办法是将顺序队列变为一个环状的空间，如图 3.13 所示，称之为循环队列。

图 3.13

串、数组和广义表

串

串(string)(或字符串）是由零个或多个字符组成的有限序列，一般记为

KMP算法

出于我本人对中国计算机教科书的了解，这一段我使用了阮行止师傅博客中的笔记和OI Wiki对应页面上的说明作为我的参考资料。

数组

数组是由类型相同的数据元素构成的有序集合，每个元素称为数组元素，每个元素受个线性关系的约束，每个元素在个线性关系中的序号儿称为该元素的下标，可以通过下标访问该数据元素。因为数组中每个元素处于个关系中，故称该数组为维数组。数组可以看成是线性表的推广，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。

数组的顺序存储

由于存储单元是一维的结构，而数组可能是多维的结构，则用一组连续存储单元存放数组的数据元素就有次序约定问题。

C语言用的是以行序为主序的存储结构。也就是说，。

容易看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组各维的长度，就是常数。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等，即数组是一种随机存取结构。

特殊数组的压缩

以对称矩阵为例。

满足时，可以建立映射，将任何组合的映射到一维数组中去。

显然在时足以表示矩阵的所有数。

广义表

空表也是广义表。

取表头 GetHead(LS): 取出的表头为非空广义表的第一个元素，它可以是一个单原子，也可以是一个子表。
取表尾 GetTail(LS): 取出的表尾为除去表头之外，由其余元素构成的表。即表尾一定是一个广义表。比如说，如果该表只有一个元素，那么表尾就是空表。

按照表头和表尾可以非常方便地递归式表达广义表。

树和二叉树

定义 & 基本术语

树(Tree)是个结点的有限集，它或为空树; 或为非空树，对于非空树T:

有且仅有一个称之为根的结点；
除根结点以外的其余结点可分为个互不相交的有限集其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。
节点：树这一数据结构的数据元素。
节点的度：结点拥有的子树数称为结点的度。
树的度：树的度是树内各结点度的最大值
叶子：度为 0 的结点称为叶子或终端结点
非终端结点：度不为 0 的结点称为非终端结点或分支结点。除根结点之外，非终端结点也称为内部结点。
双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。
兄弟：同一个双亲的孩子之间互称兄弟
祖先：从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。
层次：根的层次为1，树中任一结点的层次等千其双亲结点的层次加 l
堂兄弟：双亲在同一层的结点互为堂兄弟。
树的深度：树中结点的最大层次称为树的深度或高度。
森林：是棵互不相交的树的集合。

二叉树的递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。由千这两棵子树也是二叉树，则由二叉树的定义，它们也可以是空树。由此，二叉树可以有5种基本形态。

特殊形态二叉树

满二叉树：深度为且含有个结点的二叉树。

完全二叉树：深度为的，有个结点的二叉树，当且仅当其每一个结点都与深度为的满二叉树中编号从至的结点一一对应时，称之为完全二叉树。

除第层外，其它各层的结点数都达到最大个数，第层所有的结点都连续集中在最左边。

存储

顺序存储结构使用一组地址连续的存储单元来存储数据元素，为了能够在存储结构中反映出结点之间的逻辑关系，必须将二叉树中的结点依照一定的规律安排在这组单元中。对千完全二叉树，只要从根起按层序存储即可，依次自上而下、自左至右存储结点元素，即将完全二叉树上编号为的结点元素存储在如上定义的一维数组中下标为的分量中。

由此可见，这种顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下，一个深度为且只有个结点的单支树（树中不存在度为 2 的结点）却需要长度为的一维数组。这造成了存储空间的极大浪费，所以对于一般二叉树，更适合采取下面的链式存储结构。

#include <bits/stdc++.h>
using namespace std;
struct node{
	int value;
	node * lchild, * rchild;
	node * parent; // opional
};
int main(){
	return 0;
}

遍历

指按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。

主要有三种：

先序遍历：根左右
中序遍历：左根右
后序遍历：左右根

由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树。

但是，由一棵二叉树的先序序列和后序序列不能唯一确定一棵二叉树，因为无法确定左右子树两部分。

线索化

所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继，所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱。^[1]

树 & 森林

存储：双亲表示法（仅表示data和parent）；孩子表示法（同构或不同构、线性表）；孩子兄弟表示法（这种存储结构的优点是它和二叉树的二叉链表表示完全一样，便千将一般的树结构转换为二叉树进行处理，利用二叉树的算法来实现对树的操作。因此孩子兄弟表示法是应用较为普遍的一种树的存储表示方法。）

哈夫曼树

哈夫曼(Huffman)树又称最优树，是一类带权路径长度最短的树。

哈夫曼编码

在5.2节提出的案例5.1中已经讨论，在进行数据压缩时，为了使压缩后的数据文件尽可能短，可采用不定长编码。其基本思想是：为出现次数较多的字符编以较短的编码。为确保对数据文件进行有效的压缩和对压缩文件进行正确的解码，可以利用哈夫曼树来设计二进制编码。

图

$图由两个集合和组成，记为其中是顶点的有穷非空集合，是中顶点偶对的有穷集合，这些顶点偶对称为边。和通常分别表示图的顶点集合和边集合，可以为空集。若为空，则图只有顶点而没有边。$

查找

概念表和术语

查找表：查找表是由同一类型的数据元素（或记录）构成的集合。
关键字：关键字是数据元素（或记录）中某个数据项的值。
查找：查找是指根据给定的某个值，在查找表中确定一个其关键字等千给定值的记录或数据元素。
动态与静态查找：若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表，否则称之为静态查找表。
平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度（ASL）。

查找方式

顺序查找，时间复杂度为。

二分查找，时间复杂度为。

折半查找的优点是：比较次数少，查找效率高。其缺点是：对表结构要求高，只能用于顺序存储的有序表。查找前需要排序，而排序本身是一种费时的运算。同时为了保持顺序表的有序性，对有序表进行插入和删除时，平均比较和移动表中一半元素，这也是一种费时的运算。因此，折半查找不适用于数据元素经常变动的线性表。

分块查找 (Blocking Search) 又称索引顺序查找，这是一种性能介于顺序查找和折半查找之间的一种查找方法。时间复杂度为。

要求：

分块有序；构建索引表

分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。其缺点是：要增加一个索引表的存储空间并对初始索引表进行排序运算。

树表查找

二叉排序树 (Binary Sort Tree) 又称二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。

平衡树查找

如何创建一棵平衡二叉树呢？插入结点时，首先按照二叉排序树处理，若插入结点后破坏了平衡二叉树的特性，需对平衡二叉树进行调整。调整方法是：找到离插入结点最近且平衡因子绝对值超过1的祖先结点，以该结点为根的子树称为最小不平衡子树，可将重新平衡的范围局限于这棵子树。

B树查找

散列表查找

如果能在元素的存储位置和其关键字之间建立某种直接关系，那么在进行查找时，就无需做比较或做很少次的比较，按照这种关系直接由关键字找到相应的记录。这就是散列查找法 (Hash Search) 的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址，即使用关键字到地址的直接转换方法，而不需要反复比较。因此，散列查找法又叫杂凑法或散列法。

散列查找法主要研究以下两方面的问题：

如何构造散列函数；
如何处理冲突。

处理散列表的冲突

线性探测法的优点是：只要散列表未填满，总能找到一个不发生冲突的地址。缺点是：会产生 ”二次聚集“ 现象。
链地址法的基本思想是：把具有相同散列地址的记录放在同一个单链表中，称为同义词链表。

排序

References

1.#图解数据结构：轻松搞定线索二叉树 - 知乎 ↩