一、绪论

数据（data）是信息的载体，是描述客观事物的数、字符、图形、图像、声音以及所有能输入计算机中并被计算机程序识别和处理的符号的集合。

数据的最小单位的是数据项；

数据的基本单位是数据元素，一个数据元素可由若干个数据项组成。

数据结构分为两大类：线性结构和非线性结构

两类结构通常分为四类基本结构：

1）集合：结构中的数据元素之间同属于一个集合，此外没有其他关系；

2）线性结构：结构中的数据元素之间存在一种线性关系，一对一的关系；

3）树形结构：一对多的关系；

4）图形结构或网状结构：多对多的关系。

根据视点的不同又可分为：逻辑结构和物理结构：

逻辑结构：面向问题，描述数据元素之间的逻辑关系；

物理结构：又称存储结构，面向计算机，是数据结构在计算机中的表示（映像）

算法的特性：输入性、输出性、确定性、有穷性、有效性（可行性）

算法的标准：正确性（满足所要求界的问题的需求，最重要最基本）、可用性（便于用户使用，良好的界面、完备的用户文档）、可读性（易于理解）、效率（存储单元的开销和运行时间的耗费）、健壮性（对于非法数据的处理）

算法复杂度：（渐进）时间复杂度和空间复杂度

二、线性结构

1、线性表

1.1 顺序表示：顺序表

用顺序结构存储的线性表为顺序表（sequential list）。

顺序表一般用数组进行存储

类模板定义：T* elems，int length，int maxLength

1.2 链表表示

1) 单链表

分为带头结点和不带头结点的单链表；

带头结点的单链表相对不带头结点的单链表在涉及会更改头节点的任务时，操作会更加统一。

类模板定义：

（结点）T data，Node* next

（单链表）Node* head，int length

2) 双向循环链表

类模板定义：

（结点）T data，Node* prior，Node* next

（双向循环链表）Node* head，int length

*带头结点的双向循环列表只有一个元素结点的条件：head->next!=head && head->next->next==head

3) 静态链表

利用数组来模拟存储空间实现链表。

类模板定义：

（结点）T data，Node* next

（静态链表）Node* head，Node* avail

设数组a放置了一个静态链表，当链表未使用的时候，其中所有的结点都是形成了一个链表，用avail进行管理，代表未使用的结点。

当进行插入操作的时候，就从avail中取出一个头节点，进行赋值，再放入head链表之中。

在完成每一步操作之后，记得要将next域中更改

插入元素操作：

i=avail;
avail=a[avail].next;
a[i].next=a[head],next;
a[head]。next=i;

当需要释放由j所指向的结点时，只需要把结点j放到avail表的最前端，并让avail指向它即可。

所设j所指结点的前一个结点的指针是p，则

删除元素操作：

a[p].next=a[j],next;
a[j].next=avail;
avail=j;

2、栈和队列

2.1 栈

特点：先进后出 FILO

1) 顺序栈（SeqStack）

类模板定义：

int top（栈顶指针），int maxsize（栈最大容量），T* elems（元素存储空间）

初始化时top=-1

入栈操作push：elems[++top] = e

出栈操作pop：e = elems[top--];

取栈顶元素：e = elems[top];

两个顺序栈共享一个数组空间：两个栈的栈底在数组两端，只有当两个栈的栈顶指针相遇时，才会出现栈满溢出

2) 链式栈（LinkStack）

与顺序栈相比，链式栈对于同时使用多个栈的情况下可以共享存储。

类模板定义：

（链栈）Node* top

用单链表表示的栈，栈顶在head，栈底在链表的尾部

3) 应用：表达式求值

1. 后缀表达式的计算

​ 方法：栈放操作数，遇到数字入栈，遇到操作符就将对应数目的操作符出栈并进行运算。

​ 判断出错：如果操作数栈中的操作数数目不到两个，或者计算结束时栈中有多个操作数时候说明后缀式出错。

2. 中缀表达式转为后缀表达式（用栈实现）

​ 方法：栈放操作符

2. 中缀表达式转为后缀表达式的简单方法

​ 1.将中缀表达式中的每一步操作加上括号

​ 2.每个操作符一道对应该操作的右边括号外

​ 3.删除所有括号

​ 验证方法：用中缀表达式构建二叉树（注意要按照顺序来构建），用后序遍历

2.2 队列

特点：先进先出 FIFO

1) 顺序循环队列

队头：允许出队；队尾：允许入队

类模板定义：

（队头指针）int front，（队尾指针）int rear

int maxsize（最大容量），T* elems（元素存储空间）

初始化队列为空，front=rear=0；（教材上的定义是这样写的，具体在做题的时候要看是否符合题目的要求）

当队头指针front或者队尾指针rear达到maxsize-1时，就要进行求模操作。

由于队列空和队列满的状态都是rear==front，所以用少一个存储空间的方法进行解决：

循环队列满的条件为：(rear+1)%maxsize==front

循环队列空的条件为：front==rear

入队操作：rear=(rear+1)%maxsize，要先判断队列是不是满了

出队操作：front=(fornt+1)%maxsize，要先判断队列是不是已经空了

2) 链式队列

用单链表表示的链队列适合数据元素变化较大的情形。

类模板定义：（带头结点）

Node* front（指向队列的头节点），rear（指向队尾结点）

3) 应用：车厢调度

2.3 递归

尾递归

单向递归（循环）

用栈模拟递归

F(m,n)=m+n+1;
m*n=0;

栈和队列的应用：

数值转换，括号匹配，回文，车厢调度

表达式求值：中缀、后缀、前缀表达式（二叉树）先序中序后序遍历

后缀表达式求值（栈放操作数）

中缀转后缀（栈放操作符）

3、串、数组、广义表

1、字符串的模式匹配算法

定义：子串定位

1) Brute-Force算法

BF算法基本思想：从一个位置开始向后面开始比较，当匹配失败的时候回到刚开始比较的位置的下一个位置重新开始比较。

i表示ob中的下标，j表示模式串pat中的下标

相等：i++;j++;继续比较

不相等：i=i-j+1;j=0;回到原来的地方，再往前进一个位置

最坏情况下的运行时间O(m*n)，简单但是效率低下，带回溯

2) KMP算法

改进：消除了BF算法中主串下标i在对应字符中比较不相等需要回退的现象

真子串的概念：

在字符串“t0，t1，….，tn-1”中最长的相等前缀和后缀称为该字符串的真子串，也就是说在字串“t0，t1，…，tn-1”中存在一个最大的k(0<k<n),使得“t0,t1…tk-1” = “tn-k，tn-k+1，…，tn-1”，则“t0，t1，…，tk-1”就称为t0，t1，…，tn-1”的真子串。需要注意的是真子串的前缀和后缀可以有重叠部分，但不能完全重叠。

KMP算法基本思路：记录模式串每个位置前面的真子串的长度是多少，当模式串和主串在匹配的时候，遇到匹配到模式串中间部分然后不相等的情况，主串的下标i不用回溯，而模式串的下标j直接变为该位置的真子串的长度，继续比较当前的i和改变后的j。当失效函数返回-1时，表示模式串的第一个与主串中的当前对象都不相等i++;j=0;

失效函数：用函数f[j]表示模式串中tj之前的真子串的长度。即：

失效函数的求法：

根据f[j]求f[j+1]，模式串pat，设f[j]=k:

(1)pat[ j ] == pat[ k ] => f[ j+1 ] = f[ j ] + 1 = k + 1;

(2))pat[ j ] != pat[ k ] => 设f[ k ] = k’，pat[ j ] == pat[ k’ ] => f[ k ] + 1 = k’ + 1;

//失效函数的求法
void GetFailure(const string& pat, int f[])
{
	int j = 0, k = -1;               
	f[0] = -1;				// 初始f[0]的值为-1
	while (j < pat.length() - 1) {
		if (k == -1 || pat[k] == pat[j])
			f[++j] = ++k;
		else          	  	// pat[k]与pat[j]不匹配 
            k = f[k];		// 寻求新的匹配字符
	}
}

改进：先执行完普通失效函数之后，再执行下面这个函数

void GetFailurePlus(const string& pat, int f[])
{
	for (int k = 1; k < pat.length() - 1; k++) {
		while (f[k]!=-1 && pat[k] == pat[f[k]])
			f[k] = f[f[k]];
	}
}

普通的KMP函数：

int KMP_find(const String &ob, const String &pat, int p = 0)
{
       int *f = new int[pat.GetLength()]; 
       GetFailure(pat, f);	// 求模式串pat的f数组的元素值
       int i = p, j = 0;			
       while (i < ob.GetLength() && j < pat.GetLength() && pat.GetLength() - j <= ob.GetLength() - i)
		if (j == -1 || pat[j] == ob[i])  {   
            i++; 
            j++;	
        }
		else	  
            j = f[j];// 寻找新的模式串pat的匹配字符位置
        delete []f;		
        if (j < pat.GetLength())        return -1;   // 匹配失败
        else        return i - j;			    // 匹配成功
}

KMP改进后的函数：

int KMP_find_PLUS(const string& ob, const string& pat, int p)//从p位置开始查找
{
	//失效函数求解
	int*f = new int[pat.length()];
	cout << endl << setw(20) <<"原来的失效函数值：" << flush;
	GetFailure(pat, f);
	cout << endl << setw(20) << "改进后的失效函数值：" << flush;
	GetFailurePlus(pat, f);
	
	int i = p, j = 0;

	//******注意要把unsigned int（.length()方法的返回值）强制转换为int，不然会出现负数大于正数，导致判断出错********

	while (i < ob.length() && j < (int)pat.length() && pat.length() - j <= ob.length() - i)
        //当i没有到终点，j没有到终点，模式串剩余长度小于主串的剩余长度
		if (j == -1 || pat[j] == ob[i]) {
			i++;
            j++;
		}
		else j = f[j];
	delete[]f;
    
     //注意要把unsigned int（.length()方法的返回值）强制转换为int，不然会出现负数大于正数，导致判断出错
	if (j <(int) pat.length())return -1;
	else return i - j;//返回找到的起点
	return 0;
}

2、数组

二维数组：行序存储和列序存储

高维数组：行序存储和列序存储

把它当作几个面的叠加3*4*5，当成三个4*5的面

3、稀疏矩阵

1、 顺序结构存储：三元组顺序表

对于稀疏矩阵中的非零元素可以用：<row, col, value>进行描述他的位置

1) 三元组表转置函数的实现

简单转置算法：将三元组顺序表中的各个三元素的row和col内容互换，然后按照新的row中的行号从小到大进行排放。

算法思路：把原矩阵的第i列元素通过遍历找出来，放到新矩阵的第i行，直到i遍历完cols

时间复杂度为：O(clos*num)

快速转置算法：按照原三元组的次序进行转置，并将转置后的三元组放置到b中的恰当位置。

时间复杂度为：O(num)

2) 三元组表的绘制

2、链式结构存储：十字链表

如果矩阵中的非零元素的位置和个数经常变动，采用链式结构进行存储稀疏矩阵比较方便。

3、其他特殊矩阵

1、对称矩阵 Aij = Aji

矩阵的压缩存储，存储对称矩阵的上三角或者下三角，按行序存储或者按列序存储

用一维数组进行存放，注意i和j的范围，确定题目给出的i和j是在上三角还是下三角区域，按行存储还是按列存储的

k=i*(i-1)/2+j-1(i>=j)(按行存储下三角、行列存储上三角)

k=j*(j-1)/2+i-1(i<j)(按行存储下三角、行列存储上三角)

2、三对角矩阵

用一维数组B[]，Bij=B[k]，则k=2i+j-3

4、广义表

1、广义表的定义

1. 广义表的元素可以是数据元素，也可以是一个表（称为子表）

2. 概念：表头、表尾、深度、长度

​ LS=（k，（a，m，n），b，c，（x，y））

​ 表头：k，是一个元素或者子表，是原本的元素

​ 表尾：一定是个表，由 广义表中除了表头的元素 构成的一个表，在这里指的是（（a，m，n），b，c，（x，y））

​ 深度：广义表的括号重数，在这里为2；

​ 长度：广义表最高一层的元素个数，在这里为5

3. 广义表通常采取链式存储结构，简称广义链表

​ 广义链表中的结点由三个域构成：

​ ———————————————————————————-

​ tag域 ref/data/hlink域 tlink域

​ tag=HEAD(0) 广义表被引用次数* 指向表头的指针

​ tag=ATOM(1) data 指向同层下一个的指针

​ tag=LIST(2) 指向子表的指针 指向同层下一个的指针

​ ———————————————————————————-

​ *ref：包括了头指针的引用和其他广义表的引用

​ 广义链表类的只有一个数据成员：Node* head

4. 广义表的中的所有表，不论哪一层，都有一个表头结点

2、广义表的绘制

【项目调试】三元组表

1、LNK2019,LNK2005

在模板函数的在头文件的定义方面，还是应该遵守模板函数的函数体和函数声明都放在头文件里

对于出现LNK2005的错误，此次出现的问题是重载运算符函数的时候，函数体虽然是在头文件里面，但是没有在函数类体内；

因为成员函数体有自动生成的inline内联标签，而这两个重载的运算符函数都是友元函数的形式，故应当写在函数类体内

2、对于有很多if-else分支的结构

应当把情况都考虑清楚，想不清楚的时候可以画一个流程图出来，帮助理清思路。

3、判断一个串有没有遍历完

可以设置flag，当最后一次进入，在执行目标操作之前，进行判断：当此次是最后一次，flag就为true

三、树和二叉树

1、二叉树的性质

1、有n(n>0)个结点的二叉树的分支数为n-1

2、若二叉树的高度为h（h≥0），则该二叉树最少有h个结点，最多有2h-1个结点

3、含有n个结点的二叉树的高度最大值为n，最小值为log2(n+1) 。

4、具有 n 个结点的完全二叉树的高度为log2(n+1) 。

5、如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0、1、2、…、n-1。则有以下关系： （1）若i＝0，则 i 无双亲，若i＞0，则 i 的双亲为i/2-1； （2）若2i+1<n，则 i 的左孩子为2i+1； （3）若2i+2<n，则 i 的右孩子为2i+2； （4）若i为偶数，且i≥1，则 i 是其双亲的右孩子，且其有编号为i-1左兄弟； （5）若i为奇数，且i＜n-1，则 i 是其双亲的左孩子，且其有编号为i+1右兄弟。

2、二叉树的存储结构

3、遍历递归算法

1) 前序遍历

若二叉树为空，遍历结束。否则，

(1)访问根结点；

(2)先序遍历根结点的左子树；

(3)先序遍历根结点的右子树。

template<typename ElemType>
inline void BinaryTree<ElemType>::PreOrder(BinTreeNode<ElemType>* r) const
{
	if (r)
	{
		cout << r->data << " "<<flush;
		this->PreOrder(r->leftChild);
		this->PreOrder(r->rightChild);
	}
}

2) 中序遍历

若二叉树为空，遍历结束。否则，

(1)中序遍历根结点的左子树；

(2)访问根结点；

(3)中序遍历根结点的右子树。

3) 后序遍历

若二叉树为空，遍历结束。否则，

(1)后序遍历根结点的左子树；

(2)后序遍历根结点的右子树。

(3)访问根结点；

4、非递归遍历算法

中序遍历非递归算法

用栈进行处理

template<typename ElemType>
inline void BinaryTree<ElemType>::NonRecurringInOrder()
{
	SeqStack<ElemType> stack;
	BinTreeNode<ElemType>* p = root;
	while (p != NULL || !stack.empty()) {
		while (p != NULL)
		{
			stack.push(*p);
			p = p->leftChild;
		}
		if (!stack.empty())
		{
			p = new BinTreeNode<ElemType>;
			stack.Top(*p);
			stack.pop();
			cout << p->data << " ";  //出栈前输出栈顶节点的值
			p = p->rightChild;
		}
	}
}

5、线索二叉树

1) 线索二叉树的构成

2) 线索化二叉树

6、二叉树的应用

6.1 堆

1) FilterUp和FilterDown算法

6.2 哈夫曼树

1) 哈夫曼树定义

2) 构造哈夫曼树

3) 哈夫曼编码

7、确定一棵二叉树

1、中序遍历+前序遍历/后序遍历

1.1 算法思想分析

通过上面的介绍可以看到，使用两种遍历来确定一棵二叉树的时候一定要有中序遍历。其实，这和三种遍历的自身特点是有关系的，前序遍历的顺序是先根结点，然后左子树，最后右子树，所以根结点一定在遍历结果的第一个位置上；后序遍历的顺序是，先左子树，然后右子树，最后根结点，所以根结点一定是在遍历结果的最后一个位置上。通过前序遍历和后序遍历可以确定出根结点。中序遍历的顺序是，先左子树，然后根结点，最后右子树，在遍历结果中，左右子树分别在根结点的两侧，这样就可以把左右子树区分开。可以看出，前/后序遍历和中序遍历的作用分别是：

前序遍历或后序遍历用于确定根节点； 中序遍历用于区分左右子树； 通过两种遍历，找出了根结点，并区分开了左右子树，这样就可以确定一棵二叉树了，下面以前序遍历加中序遍历为例，一步步分析如何通过前序遍历结果和中序遍历结果来恢复一棵二叉树（后续+中序遍历的方法与之类似，此文不再分析）。

1.2 算法流程

首先给出两个序列

前序遍历结果：A B C D E F G

中序遍历结果：C D B A F E G

第一步：确定整棵树的根结点及左右子树 根据前序遍历结果确定整棵树的根结点为A ; 根据根结点和中序遍历确定左右子树的结点集合，因为A是整棵树的根结点，中序遍历的顺序是先左子树，然后根结点，最后右子树。所以，在中序遍历结果中，A结点的左侧为左子树结点集合{C, D, B}，A结点的右侧为右子树结点集合{F, E, G}； 根据分析，可以画出分析后的结果

这样就把问题分解为{C, D, B}和{F, E, G}两个子问题，首先分析左子树

第二步：分析左子树 找出{C, D, B}在前序遍历结果中对应的子序列A (B C D) E F G，将相应子序列拿出来{B C D}，根据前序遍历的结果可知，B为这棵子树的根结点； 找出中序遍历中该子树结点集合对应的子序列(C D B) A F E G，根据中序遍历的特点可知，{C D}为根结点B的左子树，B的右子树为空； 继续画出示意图

分析{C，D}子序列

第三步：继续分析左子树的左子树（B结点的左子树） 找出{C, D}在前序遍历结果中对应的子序列A B (C D) E F G，将相应子序列拿出来{C D}，根据前序遍历的结果可知，C为这棵子树的根结点； 找出中序遍历中该子树结点集合对应的子序列(C D) B A F E G，根据中序遍历的特点可知，{D}在根结点C的右侧，为根结点C的右子树，C的左子树为空； 继续画出示意图

至此，整棵二叉树的左子树分析完毕，再用第二、三步同样的方法分析右子树{F，E，G}。

第四步：分析右子树 找出{F，E，G}在前序遍历结果中对应的子序列A B C D (E F G)，将相应子序列拿出来{F，E，G}，根据前序遍历的特点可知，E为这棵子树的根结点； 找出中序遍历中该子树结点集合对应的子序列C D B A (F E G)，根据中序遍历的特点可知，{F}为根结点E的左子树，{G}为根结点E的右子树； 画出示意图

整棵二叉树分析完毕，并恢复出唯一的一棵二叉树，我们对该二叉树示意图进行前序遍历和中序遍历，结果分别为A B C D E F G和C D B A F E G，与题目中给的前序遍历序列和中序遍历序列一致，证明我们恢复得到树是正确的。 ———————————————— 版权声明：本文为CSDN博主「Mindtechnist」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_43471489/article/details/123967360

2、#号法确定：如果没有左右子树，则使用#号代替，遍历时用#代替NULL

2.1 算法思想分析

#号法确定一棵树的思想是，如果一个结点没有左右子树，也就是说如果左子树或右子树为NULL，就用一个#号代替，在遍历时给出带有#的遍历结果，既然没有左右子树就用一个#代替，那么连续两个#号前的结点一定是叶子结点，也就能确定一棵子树的结束，这样通过一种遍历的结点序列就能唯一确定一棵二叉树。

2.2 算法流程

首先给出一个#号法前序遍历的结点序列

前序遍历：ABC#D###EF##G##

具体步骤： 找出后面有连续两个#的结点，D F G这三个结点就是叶子结点； 根据前序遍历可知，A是整棵树的根结点； 第一个出现连续两个#的位置为D，所以D结点应该是整棵树的左子树的结束，那么左右子树就区分开了，{B C D}为左子树，{E F G}为右子树； 分析左子树{B C D}的根结点以及左子树的左右子树。先分理出左子树序列BC#D###，因为是前序遍历，B为左子树的根结点，第一个连续两个#的位置是D，所以D结点是以B为根结点的树的左子树的结束，那么剩下的一个#就是B结点的右子树。因此，B结点的左子树集合为C#D##，B结点的右子树为#； 分析子树{C#D##}，由前序遍历特点可知，C为根结点，D为子树终点，因为D前面有一个#可知，C的左子树为#，右子树为D； 分析A的右子树{EF##G##}，E为根结点，F为左子树，G为右子树；

———————————————— 版权声明：本文为CSDN博主「Mindtechnist」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_43471489/article/details/123967360

2.3算法实现

template<class ElemType>
inline BinTreeNode<ElemType>* BinaryTree<ElemType>::buildTree(const string& s,int& i)
{
	if (i >= s.size() || s[i] == '#') {
		i++;
		return NULL;
	}
	BinTreeNode<ElemType>* root = new BinTreeNode<ElemType>(s[i]);
	i++;
	root->leftChild = buildTree(s, i);
	root->rightChild= buildTree(s, i);
	this->root = root;
	return root;
}

二叉树的树形显示

【原创】二叉树的树形显示步骤：设置好二叉树各个节点的X,Y坐标，再根据结点的xy坐标进行相关输出比较方便。

1、在二叉树结点的成员中增加x,y坐标的数据成员

template<class ElemType>
struct BinTreeNode
{
	//数据成员
	ElemType data;						//数据域
	BinTreeNode<ElemType>* leftChild;	//左孩子指针域
	BinTreeNode<ElemType>* rightChild;	//右孩子指针域
	int x;
	int y;

	//函数成员
	BinTreeNode();//无参数的构造函数
	BinTreeNode(const ElemType& d, BinTreeNode<ElemType>* lChild = NULL, BinTreeNode<ElemType>* rChild = NULL);//已知数据元素值，指向左右孩子的指针构造一个结点
	
};

2、编写设置二叉树坐标的函数

思路：保证二叉树最底层的元素间隔三个位置，往上递推间隔。

记录第一层i=1,第二层i=2…

x坐标轴从左上向右延展，y坐标轴从左上向下延展

根据数学演算推理得：

y=(i-1)*2

公式表示，该层中首个结点的x坐标+该层中每个节点之间的空格*该结点是该层中的第几个节点

h为二叉树的高度；

i表示层数，从根节点1开始；

binary表示二进制到达该节点的路径，从根节点出发，访问左孩子的操作记为0，访问右孩子的操作记为1，最后将得到的二进制数转换为十进制数，再减1就是该节点的是该层中的第几个结点。

template<typename ElemType>// 设置二叉树坐标
inline void BinaryTree<ElemType>::SetXY()
{
	int i = 1;
	int location[10] = {0};
	this->PreSet(root, location, i);	
}

template<typename ElemType>
inline bool BinaryTree<ElemType>::PreSet(BinTreeNode<ElemType>* r, int* location, int& i)
// 操作结果：二叉树的每一个节点都用坐标XY标记
{
	if (r != NULL)
	{
	//标记当前节点的坐标信息
		//设置y的坐标
		r->y = 2 * (i - 1);

		//设置x的坐标
		int h = this->Height();//h表示整个二叉树的高度
		int sum = 0;
		int binary = 0;
		int interval = 0;
		for (int k = 1; k <= h - i; k++)
			sum += pow(2, k);
		for (int k = 2; k <= i; k++)
			binary = binary * 2 + location[k];
		for (int k = 2; k <= h - i + 1; k++)
			interval += pow(2, k);
		interval += 3;
		r->x = sum + binary * (interval + 1);

	//标记左子树的坐标信息
		//当下面的结点不为空时，location[i]来记录从根节点走到当前节点是怎么走的，0表示走左边，1表示走右边
		if (r->leftChild != NULL) {
			i++;
			location[i] = 0;
			this->PreSet(r->leftChild,location,i);
			i--;
		}
		
		
	//标记右子树的坐标信息
		if (r->rightChild != NULL) {
			i++;
			location[i] = 1;
			this->PreSet(r->rightChild,location,i);
			i--;
		}
		return true;
	}
	return false;
}

3、通过二叉树的层次遍历，配合x,y坐标进行输出

文本中注释的代码是还没有写好的，本来是想要把二叉树的左右分支“/“‘\”显示出来的，发现还有一些其他的问题需要解决，期末周比较紧，就没有花时间去研究了。

主要的问题：

1.打印树枝"/""\“时需要分清楚左右孩子才能准确打印（可以通过增加状态量isRightchild进行判断）

2.（未解决）打印一个“/”最合适的位置是在上下两排结点中最居中的位置，但是需要同时知道上下两个结点的x坐标，才能够进行计算，但实际上，实现要输出上一排结点，再输出”/“或者”\"，最后再输出下一排结点。当输出“/”无法知道下面的结点，还要顾及旁边的子树是否有节点等问题。

预想的解决方法是：

​ 1.把现有的结点坐标信息都输入到数组或者向量中去，转换为一个比较方便计算位置的数据结构

​ 2.在队列中，将除根结点以外的其他节点进行两次进栈操作，按层序为单位。第一次出栈的时候打印“/”，第二次出栈打印元素值。但此方法需要记录上一层元素的x坐标值（可能含有多个x坐标），操作起来感觉也比较麻烦。

template<typename ElemType>
inline void BinaryTree<ElemType>::printTree()
{
	this->SetXY();
	
	LinkQueue<BinTreeNode<ElemType>*> q;		//定义队列q
	BinTreeNode<ElemType>* p;
	if (root != NULL)q.EnQueue(root);			//如果根非空，则入队
	int x = 0, y = 0;							//x和y记录上一结点的坐标信息
//	int xx = 0, yy = 0;							//控制打印"/""\"
//	bool isRightChild = true;					//记录当前节点是不是双亲结点的右孩子
//	bool flag_twice = false;					//标记当前节点是不是打印过
	while (!q.IsEmpty()) {					    //q非空，说明还有结点未访问
		q.DelQueue(p);							//队头元素出队，并访问它
		
		//打印"/"和" \"
		/*
		if (p!=root && flag_twice==false) {
			xx = (x + p->x) / 2;
			for (int i = p->y == y ? x : 0; i < p->x; i++)			//打印前导空格
				cout << " ";
			if (isRightChild)
				cout << "/" << flush;
			else cout << "\\" << flush;
			
		}*/

		//打印元素值
//		if (flag_twice == true) {
			if (p->y != y)cout << endl;				//控制元素的换行
			for (int i = p->y == y ? x : 0; i < p->x; i++)			//打印前导空格
				cout << " ";
			cout << p->data << flush;				//打印结点值

			x = p->x;
			y = p->y;
//		}

//		if (flag_twice == false) {
//			q.EnQueue(p);
//			flag_twice = true;
//		}

		if (p->leftChild != NULL) {				//队头元素左孩子非空
			q.EnQueue(p->leftChild);			//左孩子入队
//			isRightChild = false;
		}
		if (p->rightChild != NULL) {				//队头元素右孩子非空
			q.EnQueue(p->rightChild);			//右孩子入队
//			isRightChild = true;
		}
	}
}

4.输出结果

8、树和森林的实现

1、树的存储

1） 双亲数组表示法

​ n个结点，type a[n]表示，每个结点有两个域data和parent，分别表示结点本身信息和父结点序号。

2）孩子结点为单链表 （孩子表示法）

​ 把每个结点的孩子排列起来，看作以单链表作存储结构的线性表。n个结点有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表。

3）带双亲的孩子链表 （双亲-孩子表示法）

结点前面的数字代表他的双亲

4）双重链表（孩子-兄弟表示法）

​ n个结点，每个结点有一个域data和两个指针域，分别表示结点本身信息、指向第一个孩子及指向第一个【下一个】兄弟。

2、树、森林、二叉树的转换

1）树转换为二叉树

条件： 树无序，二叉树左、右孩子结点有区别的。约定树中每一个结点的孩子结点按从左到右的次序顺序编号(有序树)。

方法：

（1）连线：树中所有相邻兄弟结点之间加一条线；

（2）删线：对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其他孩子结点之间的连线。

（3）美化：以树的根结点为轴心，将这棵树顺时针转动45度使其层次分明。

2）森林转换为二叉树

森林转化为二义树的方法：

（1）依次将森林中的每棵树转化成相应的二叉树；

（2）从第二棵二叉树开始，依次把当前的二叉树作为前一棵二叉树根结点的右子树，此时所得到的二叉树就是由森林转化得到的二叉树。

树和森林都可以转化成二叉树，两者的不同之处：

树转化成的二叉树，他的根节点是没有右子树的；

森林转化的二叉树，其根节点是有右子树的。

可以根据二叉树根节点是否有右子树，将其转化为树或者森林。

3）二叉树转化为树

（1）加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来

（2）抹线：抹掉原二叉树中双亲与右孩子之间的连线

（3）调整：将结点按层次排列，形成树结构

4）二叉树转化为森林

(1) **连线：**若结点P是其双亲结点F的左孩子，则把从结点P沿右分支所找到的所有结点和结点F用线连起来；

(2) **删线：**删除二叉树中所有结点和其右孩子结点之间的连线；

(3) **美化：**整理由前两步所得到的树或森林，使之结构层次分明。

3、树的遍历

先根遍历、后根遍历和层次遍历。

1）先根遍历

树的先根遍历与二叉树的先序遍历相同

树的先根遍历的定义：若树为空，遍历结束。否则，

​ (1) 访问根结点；

​ (2) 按照从左到右的顺序先根遍历根结点的每一棵子树。

结果序列：A、B、E、F、K、L、C、G、D、H、I、M、N、J。

2）后根遍历

树的后根遍历与二叉树的中序遍历相同

树的后根遍历的定义：若树为空，遍历结束。否则，

​ (1) 按照从左到右的顺序后根遍历根结点的每一棵子树；

​ (2) 访问根结点。

结果序列： E、K、L、F、B、G、C、H、M、N、I、J、D、A。

3）层次遍历

定义

树的层序遍历也称为树的广度遍历，就是从树的第一层(根结点)开始，自上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。

遍历序列为：A、B、C、D、E、F、G、H、I、J、K、L、M、N。

算法思想

设置一个队列结构，并按下述步骤层序遍历树：

​ 1) 初始化队列，并将根结点入队。

​ 2) 当队列非空时，取出队头结点p，转步骤3；如果队列为空，则结束遍历。

​ 3) 访问取出的结点p；如果结点p有孩子，则依次将它们入队列。

​ 4) 重复步骤2)、3)，直到队列为空。

4、森林的遍历

方式：先根遍历、中根遍历和后根遍历。

1.先根遍历

小结：每一棵树先根遍历，下一颗树

若森林为空，返回；否则

(1) 访问森林中第一棵树的根结点；

(2) 先根遍历第一棵树的根结点的子树森林；

(3) 先根遍历除第一棵外其它树组成的森林。

结果序列：A、B、 E、 C、D、F、G、H、I 、 J、K 。

2.中根遍历

小结：中序遍历访问完第一棵树的所有子树后访问根节点，再下一颗树。

若森林为空，返回；否则

(1) 中根遍历第一棵树的根结点的子树森林；

(2) 访问森林中第一棵树的根结点；

(3) 中根遍历除第一棵外其它树组成的森林。

结果序列：E、B、C、D、A 、G、F、I、K、J 、H 。

3.后根遍历

小结：对同一层次的结点从顺序上来看是同一棵树下的从右到左访问，优先更深层次的访问，是一层一层回来的。

若森林为空，返回；否则

(1) 后根遍历第一棵树的根结点的子树森林；

(2) 后根遍历除第一棵外其它树组成的森林；

(3) 访问森林中第一棵树的根结点。

结果序列：E、D 、 C、 B、G、K、J、 I、 H、F、A 。（易错）

根据森林与二叉树的转化关系以及森林和二叉树的遍历定义可以得知，

森林的先根遍历与其转化后相应二叉树的前序遍历的结果序列相同；

森林的中根遍历与其转化后相应二叉树的中序遍历的结果序列相同；

森林的后根遍历与其转化后相应二叉树的后序遍历的结果序列相同。

因此，森林的遍历算法也可采用相应的二叉树的遍历算法实现。

9、等价类及其表示

1、等价关系与等价类

利用等价关系把集合S划分成若干等价类的算法步骤：

​ 1）首先把S中的每一个对象看成是一个等价类；

​ 2）依次处理各个等价对（x等价y）：若x属于Si、y属于Sj，且Si不等于Sj，则把集合Si、Sj合并成一个集合。

2、并查集

1. 定义

能够完成以上功能(首先把每一个对象看成是一个单元素集合，然后依次将属于同一个等价类的元素所在的集合合并)的集合就是并查集。

2. 操作

并查集支持以下三种操作：

（1） Ufsets(n)：构造函数，将并查集中n个元素初始化为n个 只有一个单元素的子集合。

（2） Find(d)：查找单元素d所在的集合，并返回该集合的名 字或id之类的标识。

（3） Union(S1，S2)：把集合S2并入集合S1中。要求S1与S2互 不相交，否则没有结果。

【拓展】布隆过滤器 Bloom Filter

编译和反编译

C++

编译

1. 在终端中导航到存储C++源代码的目录中。

2. 使用以下命令将C++源代码汇编为汇编文件：

   g++ -S -fverbose-asm -g BloomFilter.cpp -o BloomFilter-cpp.s
   

   这个命令将使用g++编译器将BloomFilter.cpp文件汇编为汇编文件BloomFilter-cpp.asm。

​ 3.使用as命令查看汇编代码，并重定向输出保存为 asm 文件

as -alhnd BloomFilter-cpp.s > BloomFilter-cpp-front.asm

反编译

将C++程序转换为汇编代码的过程可以分为两个步骤：首先将C++程序编译为目标文件，然后将目标文件反汇编为汇编代码。以下是详细的步骤：

编译C++程序为目标文件

编译器将C++源代码编译为目标文件，这是一个二进制文件，它包含了程序的机器代码以及其他与程序执行有关的元数据。

对于C++程序，通常使用GCC编译器。可以使用以下命令将C++源代码编译为目标文件：

g++ -c BloomFilter.cpp -o BloomFilter.o

g++ -g BloomFilter.cpp -o executable

其中，.cpp是C++源代码文件的名称，.o是目标文件的名称。-c选项表示只进行编译而不进行链接，因此生成的文件是目标文件而不是可执行文件。

反汇编目标文件为汇编代码

反汇编目标文件的过程将机器代码转换回汇编语言，以便更容易地阅读和理解程序的工作原理。

可以使用objdump命令反汇编目标文件。例如，以下命令将.o目标文件反汇编为汇编代码：

objdump -d BloomFilter.o > BloomFilter-c.asm

objdump -S executable > BloomFilter-cpp-back.asm

其中，-d选项表示反汇编代码段，>运算符将输出重定向到.asm文件。

此时，.asm文件中包含了C++程序的汇编代码，可以使用文本编辑器或其他工具来查看和编辑它。

Java

在Java中，源代码需要先经过编译器的处理转换成Java字节码，然后由Java虚拟机（JVM）进行解释执行。因此，在Java中进行汇编和反汇编操作，实际上是针对Java字节码进行的。

Java字节码是一种类似于汇编代码的中间语言，它可以通过Java虚拟机（JVM）转换成机器码并执行。Java提供了javap命令来反汇编Java字节码文件，以下是详细步骤：

编译Java源代码

使用javac命令将Java源代码编译成Java字节码文件，例如：

javac BloomFilter.java

反汇编Java字节码文件

使用javap命令反汇编Java字节码文件，例如：

javap -c BloomFilter.class > BloomFilter-java.asm

其中，-c选项表示将反汇编结果输出为字节码指令，.class是编译生成的Java字节码文件名，>运算符表示将结果输出到一个文件中，此处输出到.asm文件中。

python

四、图

1. 图的基本概念

图(Graph)—非线性关系，关系任意，多个前驱多个后继

图的限制

1. 图中不能有从顶点自身到自身的边(即自身环)，就是说不应有形如(x，x)或＜x，x＞的边。如图(a)所示的带自身环的图不讨论。
2. 两个顶点v和w之间相关联的边不能多于一条。如图(b)所示的多重图也不讨论。

​

图的术语

1．完全图(complete graph)：n个顶点有n(n-1)/2条边的图 2．权(weight)：带权图也被称为网络network 3．邻接点(adjacent vertex) 4．子图(subgraph)

5．顶点的度 6．路径 7．路径长度 8．简单路径与回路：简单路径是路径上顶点各不相同的路径 9．连通图与连通分量 10．强连通图与强连通分量 11．生成树（连通图）

2. 图的存储结构

2.1 邻接矩阵

邻接矩阵（Adjacency Matrix）涉及到了两个数据结构。

• 第一个是一个顶点数组，用来存放图当中的顶点信息。

  举例：比如下面的A图中，顶点有ABCD，那这个顶点数组vertexes就依次存放ABCD

• 第二个是一个存放边的二维数组，之所以要用二维数组，就是用来描述是从哪一个点到哪一个点的边，是否存在。

​ 举例：AC之间有一边，并且是无向边，也就是说从A到C和从C到A都有一条边。在边数组中的体现就是，arcs[0][2]和arcs[2][0]的数都是1，（1表示边存在， 0表示没有边，0和2分别对应顶点数组中的A和C的下标）

这样，通过顶点数组和边数组，就能清楚描述一个图了，这就是邻接矩阵存储一个图，简单吧~

邻接矩阵的Arcs数组中：

对于带权图（网络）：

2.2 邻接表

邻接表中总体的概念是将每一个点都放到一个数组中，以表示顶点的信息，边的信息则是通过这些顶点所指来进行表示。

头节点

把顶点放到数组中存放，其存储方式是通过构造了“头结点”结构体，这个结构体中包含了：

• 顶点的信息
• 顶点指向的下一个顶点（也就是边的信息）

边结点/表结点

再来看存放边信息的表结点中，有一个边结点就代表这个头结点还有边。

• 那么从这个头结点中指出来的边到底是和哪个顶点连成的边呢？这个信息就需要存放在表结点中。也就是adjvex（邻接点），表示头节点和这个邻接点形成了一条边；
• 在表结点中还有一个域，是nextarc（下一条边），这是一个指针，用来指向下一个表结点的位置。

这样，一个头节点和所有从他出发的边就表示好了。

对每一个结点都这样做，都把他们作为头节点存放在一个数组中，再添加上从他们出发的边信息的链表，这一个图就描述清楚了。，

对于带权图(网络)，须在邻接表的边结点中增加一个存放边上的权值的域weight（即info域，它可以表示相关信息）。如下图所示的是一个带权图的邻接表表示。

2.3 邻接矩阵和邻接表的比较

试想一下，如果一个顶点很多边很少的图用邻接矩阵来存储，是不是他表示边的二维数组中，就会有很多的0，这就会造成内存的浪费。所以对于稀疏图，最好的存储办法是采用邻接表来存储，邻接表是有一条边存一条边，就可以避免这个问题。

同样的，如果图的边非常的稠密，用邻接表存储也会有很多指针等额外的开销，所以性能还不如邻接矩阵。

所以才会有这两种给存储方式，同时他们的遍历方式也不太相同，有时候也会针对所关注的图的某一方面进行选择存储方式。

比如如果我很关注从某一顶点出发，有哪些边？邻接矩阵就从该顶点的行和列进行搜寻1；邻接表就直接从该头结点向后面找就行。

• 在邻接表/逆邻接表的边表 相当于 邻接矩阵的一行/一列。
• 求顶点的度/出度/入度
• 判断(vi，vj)或＜vi，vj＞是否为图的边
• 求图的边数
• ……
• n个顶点e条边的图G，无向图的邻接表：n个顶点表结点和2e个边表结点；有向图邻接表/逆邻接表：n个顶点表结点和e个边表结点。因此邻接表或逆邻接表表示的空间复杂度为S(n，e)＝O(n+e)。
• 稀疏图—邻接表；稠密图—邻接矩阵。

2.4 无向图的邻接多重表

​ 邻接多重表是无向图的另一种链式存储结构.每一条边用一个结点表示,每一个顶点也用一个结点表示。

2.5 有向表的十字链表

​ 十字链表是有向图的另一种链式存储结构。在有向图的十字链表中，图中的每一条弧用一个弧结点表示。对有向图中的每一个顶点也用一个顶点结点表示。

3. 图的遍历与连通性

DFS和BFS的时间复杂度：

如果存储结构是邻接表，则时间复杂度为O(n+e)

存储结构是邻接矩阵，时间复杂度为O(n^2)

3.1 深度优先搜索

基本步骤

（1）访问结点v，并标记v已被访问； （2）取顶点v的第一个邻接顶点w； （3）若顶点w不存在，返回；否则继续步骤（4） （4）若顶点w未被访问，则访问结点w，并标记w已被访问；否则转步骤（5） （5）使w为顶点v的在原来w之后的下一个邻接顶点，转到步骤（3）。

template <class ElemType>
void DFS(const AdjMatrixUndirGraph<ElemType> &g, int v, void(*Visit) (const ElemType &)){	
	ElemType e;	
	g.SetTag(v, VISITED);
	g.GetElem(v, e);	
	Visit(e);
	for (int w=g.FirstAdjVex(v); w != -1;  w=g.NextAdjVex(v, w))
	      if (g.GetTag(w) == UNVISITED)
              DFS(g, w, Visit);
}

template <class ElemType>
void DFSTraverse(const AdjMatrixUndirGraph<ElemType> &g, void (*Visit)(const ElemType &)){
	int v;
	for (v=0; v < g.GetVexNum(); v++)
		g.SetTag(v, UNVISITED);
	for (v=0; v < g.GetVexNum(); v++)
		if (g.GetTag(v) == UNVISITED)
			DFS(g, v, Visit);
}

3.2 广度优先搜索

基本思想

​ 从图中的某一顶点v出发，在访问顶点v后访问v的各个未曾被访问过的邻接顶点w1,w2,..,wk，再依次访问它们的所有未被访问过的邻接顶点…..直到所有的和顶点v联通的顶点都被访问过为止。

​ BFS是一个分层的搜索过程，像树的层次遍历，不像深度搜索那样有回退的过程，所以它不是一个递归的过程。算法中使用了一个队列，用来记录刚才访问过的上一层和本层的结点，以便于向下一层访问。

基本步骤

（1）访问结点v，并标记v已被访问，同时顶点v入队列； （2）当队列空时算法结束，否则继续步骤（3）； （3）队头顶点出队列为v； （4）取顶点v的第一个邻接顶点w； （5）若顶点w不存在，转步骤（3）；否则继续步骤（6） （6）若顶点w未被访问，则访问顶点w，并标记w已被访问，同时顶点w入队列；否则继续步骤（7）； （7）使w为顶点v的在原来w之后的下一邻接点，转到步骤（5）。

特点

先进先出,非递归,队列辅助

template <class ElemType>
void BFS(const  AdjMatrixUndirGraph<ElemType> &g, int v, void (*Visit)(const ElemType &))
{	
    LinkQueue<int> q;
    int u, w;
    ElemType e;   
    g.SetTag(v, VISITED); 
    g.GetElem(v, e);
    Visit(e);
    q.EnQueue(v);
    while (!q.IsEmpty())  {
        q.DelQueue(u);
        for (w=g.FirstAdjVex(u); w != -1; w=g.NextAdjVex(u, w))
           if (g.GetTag(w) == UNVISITED){ 
              g.SetTag(w, VISITED);  
              g.GetElem(w, e);	
			  Visit(e); 
              q.EnQueue(w);
            }	
     }
}

template <class ElemType>
void BFSTraverse(const AdjMatrixUndirGraph<ElemType> &g, void (*Visit)(const ElemType &)) 
{
	int v;
	for (v=0; v < g.GetVexNum(); v++)
	     g.SetTag(v, UNVISITED);
	for (v=0; v < g.GetVexNum(); v++)
		if (g.GetTag(v) == UNVISITED) 
			BFS(g, v, Visit);
}

3.3 连通分量

4. 最小生成树

MST, minimum cost spanning tree

• 定义(Spanning Tree) 连通图的极小连通子图，有且仅有n个顶点n-1条边 连通, 无环
• 特点
  • 任意两顶点有且仅有一条路径；
  • n个顶点的连通图的生成树具有n-1条边；
  • 生成树不唯一， n 个顶点的完全图有n(n-2)种不同的生成树；
  • 不同遍历方法/不同顶点出发/不同存储结构，生成树不同；
  • 含n个顶点n-1条边的图不一定是生成树
• 如何求得生成树 深度优先搜索树、广度优先搜索树

4.1 Kruskal算法

（1）算法思想

​ F＝{T0、T1、…、Tn-1}。向F中加入最小权值&不构成环的边（v、u），重复n—1次。

（2）主要问题

（1）最小，排序，如何实现排序——最小堆可以实现 （2）两端点在不同连通分量上的边，如何判断边(u,v)已经构成环？——并查集可以实现

（3）主要步骤

（1）初始化，在并查集中，连通网络的每一个顶点独立成一个等价类，连通网络的所有的边建立最小堆，最小生成树T中没有任何边，T中边的条数计数器i为0； （2）如果T中边的条数计数器i等于顶点数减1，则算法结束；否则继续步骤（3）； （3）选取堆顶元素代表的边（v，u），同时调整堆； （4）利用并查集的运算检查依附于边（v，u）的两个顶点v和u是否在同一个连通分量(即并查集的同一个子集合)上，如果是则转步骤（2）；否则继续步骤（5）； （5）将边（v，u）加入到最小生成树T中，同时将这两个顶点所在的连通分量合并成一个连通分量(即并查集中的相应两个子集合并成一个子集)，继续步骤（2）。

（4）举例

在初始建堆时，边的输入顺序为： （ A、B）34 （A、C）46 （A、F）19 （B、E）12 （C、D）17 （C、F）25 （D、E）38 （D、F）25 （E，F） 26

4.2 Prim算法

（1）算法思想

​ G＝(V，E)；

​ 最小生成树T＝(U，TE）；

​ 初始U={u0}（u0∈U），TE=Φ ；

​ 在所有一个端点u己在T(即u∈U)、另一个端点v还未在T(即v∈V—U)的边中找权最小的边(u，v)，边/v并入TE/U；

​ 重复到所有顶点进U。

​ MST性质保证最小，特点–无环？

（2）主要问题

每次选出权值最小且两端点在不同集合上的边。

（1）两端点在不同集合上，如何记录/修改集合【并查集、0/1状态】？

（2）如何判断在哪些边中找最小，如何实现排序？用堆的概念能否简单解决该问题？

（3）主要步骤

（1）初始化辅助数组closearc[]； （2）重复下列步骤（3）和（4）n-1次； （3）在closearc[]中选择lowweight ≠ 0 && lowweight最小的顶点v，即选中的权值最小的边为 ( closearc[v].nearvertex,v ) 。 将closearc[v].lowweight改为0，表示顶点v已加入顶点集U中。并将边(closearc[v]. nearvertex、v)加入生成树T的边集合。 （4）对V-U中的每一个顶点j，如果依附于顶点j和刚加入U集合的新顶点v的边的权值Arcs[v] [j]小于原来依附于j和生成树顶点集合中顶点的边的最短距离closearc[j].lowweight，则修改closearc[j]，使其lowweight = Arcs[v] [j]}，nearvertex = v。

选择最小的非零且权值的边，如果这个顶点的邻接点的权值通过这个点变小了，就更新表中与他相关的顶点的信息。这样做n-1次。

4.3 Prim与Kruskal算法的性能比较

(1) 时间复杂性:

​ Prim: O(n*n)

​ Kruskal: O(e log e)

(2) 适用场合:

​ Prim: 稠密图

​ Kruskal: 稀疏图

5. 最短路径

最短路径类型 单源点最短路径：弧上权值非负（Dijkstra算法），弧上权值为任意值（贝尔曼-福特算法） 多源点最短路径：所有顶点之间的最短路径（Floyd算法）

最短路径和最小生成树的区别

最短路径是求两点之间的最小值，最小生成树是求整个图的代价最小问题

5.1 Dijkstra算法

时间复杂度：O(n^2)

（1）算法定义

按路径长度递增的次序产生最短路径。

（2）算法思想

1.每次从未标记的节点中选择距离出发点最近的节点，标记，收录到最优路径集合中； 2.计算刚加入节点A的邻近节点B的距离（不包含标记的节点）， 若(节点A的距离 +节点A到节点B的边长)<节点B的距离，就更新节点B的距离和前面点。

直到目的点被标记。

思考： （1）如何记录最短路径[值，路径上顶点集]？ （2）如何记录已求得路径的“终点”集？ （3）如何参照“最短”求“次短”？

引进辅助向量dist[] dist[i]表示当前所找到的从始点v0到每个终点vi的最短路径长度。

引入辅助数组path[] path[i] 表示从源点v0到顶点vi的最短路径上的顶点vi的直接前驱顶点。

下一条长度次短的路径是哪一条? 假设该次短路径的终点是vk,则这条路径或者是(v,vk),或者是(v,vj,vk) dist[j] = Min{dist[i]|vi∈V-S}

（3）算法图解

（4）C++代码

template <class ElemType, class WeightType>  
void ShortestPathDij(const AdjListDirNetwork<ElemType, WeightType> &g, int v0, int *path, WeightType *dist) {
    WeightType minVal, infinity=g.GetInfinity();
    int v, u;
   //初始化dist和path数组
    for (v=0; v < g.GetVexNum(); v++)  {
        dist[v]=g.GetWeight(v0, v);
        if (dist[v] == infinity)   path[v]=-1;
        else path[v]=v0;
        g.SetTag(v, UNVISITED);
    }
    g.SetTag(v0, VISITED);
    for (int i=1; i < g.GetVexNum(); i++){	 //找n-1个终点
        minVal=infinity;     
        u=v0;
        for (v=0; v < g.GetVexNum(); v++) //找最短的路径
		if (g.GetTag(v) == UNVISITED && dist[v] < minVal)  {
	  		u=v; 	
       		minVal=dist[v];
		}
    	g.SetTag(u, VISITED);
		//对u的邻接点，修改路径和路径长度
    	for (v=g.FirstAdjVex(u); v != -1; v=g.NextAdjVex(u, v))
		if (g.GetTag(v) == UNVISITED && minVal + g.GetWeight(u, v) < dist[v])
    	{
            dist[v]=minVal + g.GetWeight(u, v);
	    	path[v]=u;
		}
  	}
}

5.2 Bellnam-Ford算法

用邻接矩阵作为存储结构，时间复杂度为O(n^3)

问题的解决：

​ 贝尔曼（Bellnam）和福特（Ford）提出了从源点逐次经过其它顶点，以缩短到达终点的最短路径长度的方法。该方法有一个限制条件：要求图中不能有路径长度为负值的回路。

​ 当图中没有路径长度为负值的回路时，有n个顶点的图中任意两个顶点之间如果存在最短路径，此路径最多有n-1条弧。

构造一个最短路径长度的数组序列：dist1[]、dist2[]、…、distn-1[]。 dist1[u]表示从源点v0直接到终点u的最短路径的长度，即dist1[u]＝Arcs[v0] [u]； dist2[u]表示从源点v0出发最多经过两条弧（一个中间顶点）到达终点u的最短路径的长度， …， distk[u]是从源点v0出发最多经过不构成带负长度回路的k条弧（k-1个中间顶点）到达终点u的最短路径的长度。 算法的结果就是计算出distn-1[u]。 思考： （1）dist维数？ （2）能否用二维数组表示dist？ （3）dist值如何变化？

可以用递推方式计算distn-1[]。设已经求出distk-1[i]，i＝0，1，…，n-1，此即从源点v0出发最多经过不构成带负长度回路的k-1条到达终点i的最短路径的长度。 从图的邻接矩阵中可以找到从任一顶点i直接到达另一顶点u的距离Arcs[i] [u]，利用递推公式： dist1[u]＝Arcs [v0] [u]； distk[u]=min{ distk-1[u] ，min{ distk-1[i]+ Arcs[i] [u]}}

算法图解

C++代码

template <class ElemType, class WeightType>  
void ShortestPathBellmanFord(const AdjListDirNetwork<ElemType,WeightType> &g, int v0, int *path, WeightType *dist){
    WeightType *distTemp, minVal, infinity=g.GetInfinity();
    int v, u, vexNum=g.GetVexNum();
    distTemp=new WeightType[vexNum];
    for (v=0; v < vexNum; v++){	// 初始化path和dist
       dist[v]=(v0 != v) ? g.GetWeight(v0, v) : 0;
       if (dist[v] == infinity)
            path[v]=-1;
       else
            path[v]=v0;
    }
    for ( int  k=2; k < vexNum ; k++) {	 // 根据递推公式求dist[k]
        for (v=0; v < vexNum; v++)
    	distTemp[v]=dist[v];			 // 放dist[k]
     	for (u=0; u < vexNum ; u++) 	 // u列
      	    if (u != v0)
       	        for (v=0; v < vexNum; v++) 	 // v行
        		if (v != v0 && distTemp[u] 
                                         > dist[v] + g.GetWeight(v, u)) {
             	     distTemp[u]= dist[v]+g.GetWeight(v, u);
            	     path[u]=v;
		}
     	for (v=0; v < vexNum; v++)
    		dist[v]=distTemp[v];
    }
}

5.3 Floyd算法

时间复杂度：O(n^3)

​ 所有顶点对之间的最短路径是指：对于给定的有向网G=(V,E)，要对G中任意一对顶点有序对V、W(V≠W)，找出V到W的最短距离和W到V的最短距离。

b站视频传送：https://www.bilibili.com/video/BV1LE411R7CS/?spm_id_from=333.337.search-card.all.click

基本思想

设n×n方阵序列A(k)（k=0、1、……、n-1）。
	  A (k)[i][i] = 0; // 对角线的矩阵元素都等于0
	  A(k)[i][j]：//从顶点i到顶点j经过的中间顶点序号不超过k的
			 	 // 最短有向路径长度
	  初始： A(-1) [i][j] = Arcs [i][j];
	  Steps:  逐步尝试在原路径中依次加入其它顶点作为中间顶点。如果增加中间顶点后，得到的路径长度比原来的路径长度减少了，则以此新路径代替原路径，并修改相应的矩阵元素，代入新的更短的路径长度。

求最短路径步骤

初始时设置一个n阶方阵a，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素a[i][j]为权值, 即A (0)[i][j] = arcs[i][j] ；否则a[i][j]为∞。
逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值。具体做法为：
	(1)让所有边上加入中间顶点1，取a[i][j]与a[i][1]+a[1][j]中较小的值作a[i][j]的值，完成后得到A(1)
	(2)让所有边上加入中间顶点2，取a[i][j]与a[i][2]+a[2][j]中较小的值，完成后得到A(2) 
	(3)…，如此进行下去，当第n步完成后，得到A(n)，A(n)即为我们所求结果，A(n)[i][j]表示顶点i到顶点j的最短距离。
所有顶点试探完毕，算法结束。 

C++代码

template <class ElemType, class WeightType> 
void ShortestPathFloyd(const AdjListDirNetwork<ElemType, WeightType> &g, int **path, WeightType **dist)  {
    for (int u=0; u < g.GetVexNum(); u++)    //初始化
       for (int v=0; v < g.GetVexNum(); v++){
	dist[u][v]=(u != v) ? g.GetWeight(u, v) : 0;
	if (u != v && dist[u][v] < g.GetInfinity()) path[u][v]=u;
	else   path[u][v]=-1;
        }
     for (int k=0; k < g.GetVexNum(); k++)	 //求A(k)
	for (int i=0; i < g.GetVexNum(); i++)	//加入k为中间顶点
	     for (int j=0; j < g.GetVexNum(); j++)
		if (dist[i][k] + dist[k][j] < dist[i][j]) {
		  dist[i][j]=dist[i][k] + dist[k][j]; 
          path[i][j]=path[k][j];
		}
}

6. 活动网络, Active Network

6.1 用顶点表示的活动网络 AOV，Activity on Vertex

在这种有向图中，顶点表示活动，弧表示活动的次序。

AOV网络中不能出现有向回路。(意味着某项活动的开始要以自己的完成作为先决条件)

拓扑排序

邻接表的拓扑排序时间复杂度为O(n+e)

把AOV网络中的各个顶点，按照他们的优先次序排列成一个线性序列的过程。

• 检测AOV网中有无有向环的方法：构造其顶点的拓扑有序序列，若网中的所有顶点都在他的拓扑排序序列中，则无有向环。

拓扑排序的方法：

1. 在有向图中选择一个没有前驱的结点输出
2. 从图中删除该顶点和所有以他为尾的弧
3. 重复上述两步，直至所有的顶点均已输出；或者当图中不存在无前驱的顶点为止。

(略)

6.2 边表示的活动网络，AOE, Activity on Edges

有向边表示一个工程中的各项活动，边上的权值表示活动持续的时间(duration)。

顶点表示事件(event)，事件的发生说明在它之前的活动已完成，而在它之后的活动可以开始.

(略)

五、查找

静态查找就是只负责查找就行，动态查找不光要负责找，还要比如说查找的这个元素不存在需要补上。

平均查找长度（ASL）

1. pi 是查找到某个元素的概率（probability）
2. ci 是查找到这个元素时已经比较的次数，如，查找在 10 个数中查找第 5 个数，其比较的次数是多少（包括和第 5 个数比较的次数）

装载因子

​ 设数据表的长度为m，表中元素个数为n，则数据表的装载因子是n/m(<1)

5.1 静态查找

5.1.1 顺序查找

Sequential search

顺序查找特点

优点：算法简单、适应面广，对表的结构或关键字是否有序无任何要求。 缺点：查找效率低，特别是当n较大时，查找效率较低，不宜采用。

查找成功的平均查找长度 ASL=(n+1)/2

查找失败的平均查找长度 ASL=n+1

5.1.2 二分查找/折半查找

Binary search

算法要求

​ （1）数据在线性表中按查找的关键字域有序排列。 ​ （2）数据表是顺序存储结构。

算法动图演示

算法实现

// 折半查找的递归实现
int BinarySearch(int elems[], int low, int high, int key)
{
    int mid = (low + high) / 2;
    if(low > high)
        return -1;
    if (elems[mid] == key)
        return mid;
    else if (elems[mid] < key)
        BinarySearch(elems, mid + 1, high, key);
    else if (elems[mid] > key)
        BinarySearch(elems, low, mid - 1, key);
    else
        return -1;
}

// 折半查找的迭代实现
int BinarySearch(int elems[],int n,int key){
    int mid;
    int low=0,high=n-1;
    while(low <= high){
        mid = (low + high) / 2;
        if(elems[mid] == key)
            return mid;
        else if(elems[mid] < key)
            low = mid + 1;
        else if(elems[mid] > key)
            high = mid - 1;
    }
}

对于有序表，还能够使用斐波那契查找和插值查找

拓展：斐波那契查找和插值查找

斐波那契查找

斐波那契查找原理仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1，（F代表斐波那契数列），如下图所示。

插值查找

插值查找的算法思想和折半查找类似，区别在于求中间位置的公式。其求中间点的公式为:

Mid = low + ((key - data[low]) / (data[high] - data[low])) * (high - low)

他的查找性能在关键字分布较均匀的情况下优于折半查找

平均查找长度

成功：log2(n+1)-1,O(log2n)

折半查找的二叉查找树：

5.2 动态查找

5.2.1 二叉排序树

BST, Binary Sort/Search Tree

1 定义

二叉排序/搜索树或者是一棵空树，或者是具有下列性质的二叉树：

1. 左子树(如果存在)上所有结点的关键字都小于根结点的关键字。
2. 右子树(如果存在)上所有结点的关键字都大于根结点的关键字。
3. 左子树和右子树也是二叉排序树。

2 二叉排序树上的查找

算法性能分析

当二叉排序树是完全二叉树时，其平均查找性能最佳为log2n，与有序表的折半查找相同。

当二叉排序树退化为一棵单支树时，二叉排序树的平均查找性能最差为：（n+1）/2，与顺序表的平均查找长度相同。

template <class ElemType>
BinTreeNode<ElemType> *BinarySortTree<ElemType>::Find(const ElemType &key, 
	BinTreeNode<ElemType> *&f) const
// 操作结果: 求指向关键字为key的数据元素的指针,用f返回其双亲
{
	BinTreeNode< ElemType> *p = GetRoot();	// 指向当前结点
	f = NULL;								// 指向p的双亲
	while (p != NULL && p->data != key)	{	// 查找关键字为key的结点
		if (key < p->data)	{				// key更小,在左子树上进行查找
			f = p;
			p = p->leftChild;
		}
		else{								// key更大,在右子树上进行查找
			f = p;
			p = p->rightChild;
		}
	}
	return p;
}

3 二叉排序树上的插入

1.方法

• 先搜索BST中有无该结点，只有无才插入

• 插入是作为叶子插入，插入后仍满足BST

• 插入位置应是搜索操作停止 的地方(在进行查找之后，f指针指向的就是需要插入的位置)

2.算法实现

template <class ElemType>
bool BinarySortTree<ElemType>::Insert(const ElemType& e) {
	BinTreeNode<ElemType>* f;
	if (Find(e, f) == NULL) {
		BinTreeNode<ElemType>* p;
		p = new BinTreeNode<ElemType>(e);
		if (IsEmpty())	  	
			root = p;
		else if (e < f->data)	
			f->leftChild = p;
		else		
			f->rightChild = p;
		return true;
	}
	else
		return false;
}

4 二叉排序树上的删除

原则

• 删除结点所断开的链要重新接起来[保持树性质]

• 删除链接后仍是BST[保持排序/搜索性质]

• 重新链接后树的高度不增加[保证效率]

方法

• 被删结点为叶子，只需将双亲结点的相应指针置为空

• 被删结点无右子树，拿左孩子结点顶替它的位置

• 被删结点无左子树，拿右孩子结点顶替它的位置

• 被删结点左右子树都有，有两种处理方法：

  • 在他的左子树中寻找中序遍历的最后一个（关键字最大，一定没有右孩子），将他的值赋给目标删除的结点，再删去这个叶子；
  • 在他的右子树中寻找中序遍历的第一个结点（关键字最小，一定没有左孩子），将他的值赋给目标删除节点，再删去这个叶子。

算法实现

template <class ElemType>
void BinarySortTree<ElemType>::Delete(BinTreeNode<ElemType> *&p)
// 操作结果: 删除p指向的结点
{
	BinTreeNode<ElemType> *tmpPtr, *tmpF;  
	if (p->leftChild == NULL && p->rightChild == NULL)	{	// p为叶结点
		delete p;
		p = NULL;
	}
	else if (p->leftChild == NULL)	{	// p只有左子树为空
		tmpPtr = p;
		p = p->rightChild;
		delete tmpPtr;
	}
	else if (p->rightChild == NULL)	{	// p只有右子树非空
		tmpPtr = p;
		p = p->leftChild;
		delete tmpPtr;
	}
	else	{	// p左右子非空
		tmpF = p;
		tmpPtr = p->leftChild;
		while (tmpPtr->rightChild != NULL)	{	// 查找p在中序序列中直接前驱tmpPtr及其双亲tmpF,直到tmpPtr右子树为空
			tmpF = tmpPtr;
			tmpPtr = tmpPtr->rightChild;
		}
		p->data = tmpPtr->data;					// 将tmpPtr指向结点的数据元素值赋值给被删除结点的数据元素值

		// 删除tmpPtr指向的结点
		if (tmpF->rightChild == tmpPtr)	// 删除tmpF的右孩子
			Delete(tmpF->rightChild);
		else							// 删除tmpF的左孩子
			Delete(tmpF->leftChild);
	}
}

5.2.2 平衡二叉树

AVL树

1 定义

又称AVL树, 或是空树、或是具有下列性质的二叉树： 它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

平衡因子（balance factor,BF）：

结点右子树高度减去左子树高度所得高度差 AVL树中结点的平衡因子值只能是-1，0，1 AVL树的ASL可保持在O(log2n)

2 平衡旋转

LL：顺时针

RR：逆时针

LR：逆时针，顺时针

RL：顺时针，逆时针

2.1 LL平衡旋转—右单旋转

如果在A的左孩子B的左子树插入了新的结点，使A的平衡因子从-1变到了-2，则需要进行LL旋转。

2.2 RR平衡旋转—左单旋转

如果在A的右孩子B的右子树插入了新的结点，使A的平衡因子从1变到了2，则需要进行RR旋转。

2.3 LR平衡旋转—先左后右双旋转

如果在A的左孩子B的右子树插入了新的结点，使A的平衡因子从-1变到了-2，则需要进行LR旋转。

2.4 RL平衡旋转—先右后左双旋转

如果在A的右孩子B的左子树插入了新的结点，使A的平衡因子从1变到了2，则需要进行RL旋转。

3 平衡二叉树的插入

1. 平衡二叉树插入结点的算法思想 （1）按二叉排序树的性质插入结点。 （2）如果插入结点之后出现不平衡的结点，则继续步骤（3）；否则插入完成。 （3）找到失去平衡的最小子树。 （4）判断平衡旋转的类型作相应平衡化处理。
2. 关键问题 （1）发现“不平衡的结点”； （3）确定“失去平衡的最小子树”； （4）判断“平衡旋转的类型”。

例题 依次插入{11,39,23,68,85,8,3,46,27,50}，过程如图：

4 平衡二叉树的删除

4.1 平衡二叉树删除结点的算法思想

• ​ 如果被删结点x是叶子；
• ​ 如果被删结点x只有一个孩子；
• ​ 如果被删结点x有左、右孩子

4.2 如何知道是否破坏了平衡？

用布尔变量shorter来记录子树的高度是否被缩短 从结点x的双亲到根结点的路径上的每一个结点的shorter为true时，根据以下三种不同的情况操作，直到shorter为false。

（1）情况一： 结点p的平衡因子为0，如果它的左子树或右子树被缩短（shorter的值为true），则它的平衡因子改为1或-1，由于此时以结点p为根的子树高度没有缩短，所以置shorter的值为false。如图a

（2）情况二： 结点p的平衡因子不为0，且其较高的子树被缩短，则P的平衡因子改为0。由于此时以结点p为根的子树高度被缩短，所以shorter的值仍为true。如图b

（3）情况三：

​ 结点p的平衡因子不为0，且较矮的子树又被缩短，则在结点p发生不平衡。此时，将进行平衡化旋转来恢复平衡。

​ ①如果q的平衡因子为0，则只要执行一个单旋转就可恢复结点p的平衡，由于旋转后被处理子树的高度没有缩短，所以置shorter的 值为false；如图c

​ ②如果q的平衡因子与p的平衡因子相同，则只要执行一个单旋转就可恢复结点p的平衡。由于此时被处理子树的高度被缩短，所以 shorter的值仍为true。最后，结点p和q的平衡因子均改为0。如图d

​ ③如果p与q的平衡因子的符号相反，则需要执行一个双旋转来恢复平衡，先围绕q转、再围绕p转。由于此时被处理子树的高度被缩 短，所以shorter的值仍为true，新的根结点的平衡因子置为0，其它结点的平衡因子作相应处理。如图e

平衡二叉树删除结点 小结

• p= 0； 无影响； shorter=false
• p=±1； 删较高子树结点； p=0，shorter=true
• p=±1； 删较矮子树结点； p不平衡：

​ ① q=0； 单旋转； shorter=false

​ ② p，q同号； 单旋转； shorter=true

​ ③ p，q异号； 双旋转； shorter=true

5.2.3 B-树

1 动态的m路查找树

结点的格式为（n,p0,k1,p1,k2,p2,…,kn,pn）

如结点A的格式为：（2,b,20,c,40,a）

如果要查找关键字为35的数据元素，就要先从根开始，沿着20~40找到结点c，读入结点c再沿着25~30找到结点e，读入结点e在其中找到35.

2 B-树

定义

一颗m阶的B-树是一颗平衡的m路查找树，具有以下特性：

• 根节点至少有两个孩子；
• 除根结点以外的所有结点（不包括失败结点）至少都有⌈m/2⌉个孩子；
• 所有的失败结点都在同一层上。

B-树中的每个非失败结点的关键字个数都在（⌈m/2⌉-1）~（m-1），超出这个范围就需要分裂（插入操作），低于这个范围需要合并（删除操作）

B-树的插入

结点分裂的方法：取这个关键字数组的中间关键字作为新的结点，然后其他关键字作为新结点的左右孩子。

查找过程还是和二叉排序树一样的，插的位置也差不多。

实例: 跟据关键字{20、30、50、52、60、69、70}，创建一棵3阶B树 由于m=3，所以除了根结点以外，非叶子结点至少有⌈3/2⌉-1个关键字，至多有3-1=2个关键字，所以

B-树的删除

概念: B树中的删除操作与插入操作类似，但要复杂一些，要使得删除后的结点中关键字个数≥⌈m/2⌉-1，因此将涉及结点的“合并”问题。由于删除的关键字位置不同，可以分为关键字在终端结点和不在终端结点两种情况。

①： 如果删除的关键字在终端结点上（最底层的叶子结点）:

• 结点内关键字数量大于⌈m/2⌉-1，这时删除这个关键字不会破坏B树的定义要求，所以直接删除

• 结点内关键字等于⌈m/2⌉-1，并且左右兄弟结点中存在关键字大于⌈m/2⌉-1，则去兄弟结点中借关键字

• 结点内关键字等于⌈m/2⌉-1，并且左右兄弟结点中存在关键字不大于⌈m/2⌉-1，则需要进行结点合并

②: 如果删除的关键字不在终端结点上（最底层的非叶子结点）:需要先转换成终端结点上，再按照在终端结点上的情况来分别考虑应对方法。

第一种情况:存在关键字大于⌈m/2⌉-1结点的左子树或者右子树，在对应子树上找到该关键字的相邻关键字，然后将相邻关键字替换成待删除的关键字

• 何为相邻关键字:对于不在终端结点上的关键字，它的相邻关键字是其左子树中值最大的关键字或者右子树中值最小的关键字。
• 找出这个待删除关键字的相邻关键字，比如说下图中10的相邻关键字就是9和11，其实就是这个大小序列中该关键字的直接前驱或者直接后驱关键字。
• 将这个待删除关键字和某个相邻关键字互换，然后删除这个关键字

第二种情况:左右子树的关键字数量均等于⌈m/2⌉-1，则将这两个左右子树结点合并，然后删除待删除关键字，14.

3 B+树

概念:B+树是常用于数据库和操作系统的文件系统中的一种用于查找的数据结构

m阶的B+树与m阶的B树的主要差异在于:

1. 在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一颗子树，在B树中，具有n个关键字的结点含有(n+1)棵子树。
2. 在B+树中，每个结点（非根内部结点）关键字个数n的范围是⌈m/2⌉≤n≤m（根结点1≤n≤m），在B树中，每个结点（非根内部结点）关键字个数n的范围是⌈m/2⌉-1≤n≤m-1（根结点1≤n≤m-1）。
3. 在B+树中，叶结点包含信息，所有非叶结点仅起到索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含该关键字对应记录的存储地址。
4. 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶节点包含的关键字和其他结点包含的关键字是不重复的。

5.3 散列表

1 散列表的基本概念

2 散列函数

• 直接定址法

• 数字分析法

• 除留余数法

• 乘余取整法

3 处理冲突的方法

3.1 闭散列——开放地址法

存在的问题：在闭散列的情形下不能随便物理地删除表中的数据，因为会影响表中其他元素的查找。如果散列表经常变动，就是用开散列的方法来处理哈希冲突。

• 线性探测法

​ 每当发生冲突，就探测下一个桶。当循环m-1次之后就会回到开始探测时的位置，说明待查元素不在表中，而且表已满，不能再进行插入。

​ 线性探测法容易产生“堆积”的问题，改进：二次探测法。

• 二次探测法

​ 在发生冲突的时候，寻找下一个空桶的公式为：Hi=（H0+di+m）%m，式中di=1^2,-1^2,2^2,-2^2,…(i-1,2,…,(m-1)/2)；H0=hash(key)，他是通过某一个hash函数对数据元素的关键字key进行计算得到的桶号，是一个非负整数，m是表的大小。

​ 举例：

​ 当出现哈希冲突的时候，使用二次探测，H=hash(H0+1)，H=hash(H0-1)，H=hash(H0+4)，…，一直到找到，或者探测到空，或者是 i = (m-1)/2

​ 当表的长度为质数，且表的装载因子不超过0.5时，新的数据元素一定能够插入到散列表中。

• 双散列法

​ 该方法需要两个散列函数进行实现。第一个散列函数按照数据元素的关键字key计算出数据元素存放的桶号；当发生冲突的时候，使用第二个散列函数计算下一个空桶的位移量，他的取值和key的值有关，且与表的大小互质。

3.2 开散列——链地址法

六、排序

排序思想、排序过程、排序算法、排序性能、每种算法的优缺点

各个排序算法的性能比较

稳定的排序算法：冒泡、插入、归并、基数

空间复杂度：

​ 归并排序是O(n)

​ 快速排序是O(logn)

​ 基数排序是O(radix)

时间复杂度为O(nlogn)：希尔、归并、快速、堆排序

时间复杂度为O(n^2)：冒泡、选择、插入

交换排序

1 冒泡排序

排序性能和优缺点

时间复杂度：最坏情况：O(N^2)       最好情况：O(N) 空间复杂度：O(1)

稳定性：稳定

排序思想

左边大于右边就交换，一趟排下来最大的在右边

排序过程

排序算法

//冒泡排序
void BubbleSort(int* arr, int n)
{
	int end = n;
	while (end)
	{
		int flag = 0;
		for (int i = 1; i < end; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				int tem = arr[i];
				arr[i] = arr[i - 1];
				arr[i - 1] = tem;
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
		--end;
	}
}

2 快速排序

排序性能和优缺点

时间复杂度：平均情况：O(nlogn)

​ 最坏情况：O(n^2)       最好情况：O(nlogn) 空间复杂度：O(logn)

稳定性：不稳定

排序思想

特点：排完一趟之后，那个元素就已经处于最后的位置了。

递归的过程；

任取数据表中的某个数据作为基准值，将整个数据表划分为比基准值大的和比他小的；

重复对左右子表执行上述过程，直到所有子表的长度为1.

排序过程

排序算法

// 快速排序
void QuickSort(int elem[], int left, int right)
{
    if (left < right)
    {
        int i = left, j = right, x = elem[left];
        while (i < j)
        {
            while (i < j && elem[j] >= x)
                j--;
            if (i < j)
                elem[i++] = elem[j];
            while (i < j && elem[i] < x)
                i++;
            if (i < j)
                elem[j--] = elem[i];
        }
        elem[i] = x;
        QuickSort(elem, left, i - 1);
        QuickSort(elem, i + 1, right);
    }
}

插入排序

3 直接插入排序

排序性能和优缺点

时间复杂度：

​ 平均：O(n^2)

​ 最好：O(n)

​ 最坏：O(n^2)

空间复杂度：O(1)

稳定性：稳定

排序思想

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

排序过程

排序算法

// 插入排序
void InsertSort(int elems[], int n)
{
    int i, j;
    for (i = 1; i < n; i++)
    {
        int temp = elems[i];
        for (j = i - 1; j >= 0 && elems[j] > temp; j--)
            elems[j + 1] = elems[j];
        elems[j + 1] = temp;
    }
}

改进： 折半插入排序

排序思想

在插入elem[i]的时候，先利用折半查找寻找elem[i]的插入位置，然后把插入位置后面的元素依次后移一个元素空间，最后把elem[i]插入到对应位置。

4 希尔排序

排序性能和优缺点

时间复杂度：

​ 平均：O(nlogn)

​ 最好：O(nlog^2n)

​ 最坏：O(nlog^2n)

空间复杂度：O(1)

稳定性：不稳定

排序思想

希尔排序又叫缩小增量排序。

• 首先取一个整数d<n作为间隔，将全部元素分成d个组，在每一个组中进行直接插入排序；
• 缩小d的值，重新分组，重新做直接插入排序；
• 直到d=1，将所有元素放在一个组中进行直接插入排序。

排序过程

排序算法

// 希尔排序
void ShellSort(int elems[], int n)
{
    int i, j, gap;
    for (gap = n / 2; gap > 0; gap /= 2)
        // 在每个组中做直接插入排序
        for (i = gap; i < n; i++)
        {
            int temp = elems[i];
            for (j = i - gap; j >= 0 && elems[j] > temp; j -= gap)
                elems[j + gap] = elems[j];
            elems[j + gap] = temp;
        }
}

选择排序

5 简单选择排序

排序性能和优缺点

时间复杂度：

​ 平均：O(n^2)

​ 最好：O(n^2)

​ 最坏：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

排序思想

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1…n]，有序区为空；
• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• n-1趟结束，数组有序化了。

排序过程

排序算法

// 简单选择排序
void SelectSort(int elems[], int n)
{
    int i, j, min;
    for (i = 0; i < n - 1; i++)     // 第i躺排序
    {
        min = i;                    // min记录最小元素下标
        for (j = i + 1; j < n; j++)
            if (elems[j] < elems[min])
                min = j;
        if (min != i)               // 如果min不是当前元素，则交换之
        {
            int temp = elems[i];
            elems[i] = elems[min];
            elems[min] = temp;
        }
    }
}

6 锦标赛排序

排序性能和优缺点

排序思想

排序过程

排序算法

7 堆排序

排序性能和优缺点

时间复杂度：

​ 平均：O(nlogn)

​ 最好：O(nlogn)

​ 最坏：O(nlogn)

空间复杂度：O(1)

稳定性：不稳定

排序思想

1. 对数据表中的数据元素，利用堆的调整算法形成初始堆；
2. 输出堆顶元素；
3. 对剩余的元素重新调整形成堆；
4. 重复执行2、3步，直到所有的元素都被输出。

排序过程

排序算法

// 堆的最大堆调整算法
void FilterDown(int elem[], int low, int high)
{
    int i = low, j = 2 * i + 1; 			// i为要调整结点，j为i的左孩子
    int temp = elem[i];         			// 当前结点
    while (j <= high)
    {                                          // 沿较大的孩子结点向下筛选
        if (j < high && elem[j] < elem[j + 1]) // 如果右孩子较大，把j指向右孩子
            j++;
        if (temp >= elem[j]) 				// 如果当前结点比孩子结点大，则筛选结束
            break;
        else
        { 									// 否则，将孩子结点上移，i、j下降
            elem[i] = elem[j];
            i = j;
            j = 2 * i + 1;
        }
    }
    elem[i] = temp; // 回放temp中暂存的元素
}

// 堆排序
void HeapSort(int elem[], int n)
{
    int i;
    for (i = n / 2 - 1; i >= 0; i--) // 建立堆
        FilterDown(elem, i, n);
    for (i = n - 1; i > 0; i--)
    { // 交换堆顶和最后一个元素
        int temp = elem[0];
        elem[0] = elem[i];
        elem[i] = temp;
        FilterDown(elem, 0, i); // 调整堆
    }
}

归并排序

归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

8 两路归并排序

排序性能和优缺点

时间复杂度：

​ 平均：O(nlogn)

​ 最好：O(nlogn)

​ 最坏：O(nlogn)

空间复杂度：O(n)

稳定性：稳定

排序思想

假设初始数据表有n个数据元素，首先把它看成长度为1的归并项，先做两两归并；

得到n/2（向上取整）个归并项，再做两两归并；

直到最后得到一个长度为n的有序序列。

排序过程

归并操作的理解

迭代归并

递归归并

排序算法

迭代方式 和 递归方式

// 归并排序
void Merge(int elem[], int low, int mid, int high)
{
    int *temp = new int[high - low + 1]; // 辅助空间
    int i = low, j = mid + 1, k = 0;     // i、j是两段有序序列的下标，k是temp的下标
    while (i <= mid && j <= high)
    { // 两段有序序列归并
        if (elem[i] <= elem[j])
            temp[k++] = elem[i++];
        else
            temp[k++] = elem[j++];
    }
    while (i <= mid)
        temp[k++] = elem[i++]; // 复制第一段有序序列剩余部分
    while (j <= high)
        temp[k++] = elem[j++]; // 复制第二段有序序列剩余部分
    for (i = 0; i < k; i++)
        elem[low + i] = temp[i]; // 复制回去
    delete[] temp;
}

// 迭代实现
void MergeSort(int elem[], int n)
{
    int len = 1, i;
    while (len < n)
    {
        i = 0;
        while (i + 2 * len - 1 <= n)
        {
            Merge(elem, i, i + len - 1, i + 2 * len - 1);
            i = i + 2 * len;
        }
        if (i + len < n)
            Merge(elem, i, i + len - 1, n - 1);
        len = 2 * len;
    }
}

// 递归实现
void MergeSort(int elem[], int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) / 2; // 分解
        MergeSort(elem, low, mid);  // 求解
        MergeSort(elem, mid + 1, high);
        Merge(elem, low, mid, high); // 合并
    }
}

基数排序

9 链式基数排序

排序性能和优缺点

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

排序思想

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）

排序过程

排序算法

#include <math.h>
struct Node
{
    int key;
    int next;
};

// 链式基数排序
void RadixSort(Node elem[], const int d, const int radix)
{
    int rear[radix], front[radix], p, i, j, k, power;
    for (i = 0; i < d; i++)
    {
        for (j = 0; j < radix; j++)
            front[j] = 0;
        power = int(pow(double(radix), i));
        p = elem[0].next;
        while (p != -1)
        {
            k = (elem[p].key / power) % radix;
            if (front[k] == 0)
                front[k] = p;
            else
                elem[rear[k]].next = p;
            rear[k] = p;
            p = elem[p].next;
        }
        j = 0;
        while (front[j] == 0)
            j++;
        elem[0].next = front[j];
        p = rear[j];
        for (k = j + 1; k < radix; k++)
            if (front[k] != 0)
            {
                elem[p].next = front[k];
                p = rear[k];
            }
        elem[p].next = -1;
    }
}