引言

各位新年快乐，祝你也祝我新年依然保持一份温柔---世间温柔，不过是芳春柳摇染花香，槐序蝉鸣入深巷，白茂叶落醉故乡。

背景与前置知识

随着应用程序变得越来越复杂和数据越来越丰富，几百万、几十亿甚至几百亿的数据就会出现，而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢，数据结构就是用来解决这些问题的。

总而言之

数据结构指的是“一组数据的存储结构”，算法指的是“操作数据的一组方法”。数据结构是为算法服务的，算法是要作用再特定的数据结构上的。

需要学习

这里面有10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树；10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

数据结构三要素：逻辑结构、存储结构、数据的运算；其中逻辑结构包括线性结构（线性表、栈、队列）和非线性结构（树、图、集合）

数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据元素是数据的基本单位，可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位，数据对象是具有相同性质的数据元素的集合，是数据的一个子集

数据类型是一个值的集合和定义在此集合上的一组操作的总称

数据类型包括：原子类型、结构类型、抽象数据类型

1）原子类型。其值不可再分的数据类型。 2）结构类型。其值可以再分解为若干成分（分量）的数据类型。

3）抽象数据类型。抽象数据组织及与之相关的操作。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括逻辑结构、存储结构和数据运算三方面内容

（1）集合结构

数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。

（2）线性结构

数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。

（3）树结构

数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。

（4）图结构或网状结构

数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图形结构或网状结构。

数据的逻辑结构和存储结构是密不可分的，算法的设计取决于所选定的逻辑结构，而算法的实现依赖于采用的存储结构

数据的存储结构主要有顺序存储、链式存储、索引存储和散列存储

顺序存储：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，元素之间的关系由存储单元之间的位置关系，即相邻关系来体现。如顺序表。优点：容易实现随机存取，每个元素占用最少的存储空间。缺点：只能使用相邻的一整块存储空间，容易产生较多的外部内存碎片。链式存储：使用表示元素存储地址的指针来表示元素之间的逻辑关系，此时不要求逻辑上相邻的数据元素在物理位置上也相邻。如单链表。优点：不会出现碎片内存，能充分利用存储单元。缺点：每个元素由于存储指针而占用额外的存储空间，且只能通过遍历实现顺序存取。索引存储：在存储数据元素的同时，建立一个附加的索引表。索引表中的每一项称为索引项项，其形式通常为（关键字，地址）。优点：检索速度快。缺点：附加的索引表会占用额外的存储空间。在添加或者删除数据元素时，需要同步修改索引表，因此会花费额外的时间。散列存储：根据元素的关键字以某种方式计算出该元素的存储地址，又称为 hash 存储。如哈希表。优点：检索、添加、删除的操作速度都很快。如果散列函数（或者 hash 函数）设计不好的话，可能会出现 hash 冲突，解决冲突又会增加时间和空间开销。

施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤

在存储数据时，通常不仅要存储各数据元素的值，而且要存储数据元素之间的关系

对于两种不同的数据结构，逻辑结构或物理结构一定不同吗？

数据运算也是数据结构的一个重要方面。对于两种不同的数据结构，他们的逻辑结构和物理结构完全有可能相同（比如二叉树和二叉排序树）

链式存储设计时，各个不同结点的存储空间可以不连续，但结点内的存储单元地址必须连续

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令包括一个或多个操作。

算法的五个特性：有穷性、确定性、可行性、输入、输出（字面意思，第一遍看的话建议看看书具体概念）

通常设计一个好的算法应考虑：正确性、可读性、健壮性、效率与低存储量需求

算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质

若输入数据所占空间只取决于问题本身而和算法无关，则只需分析除输入和程序之外的额外空间

算法原地工作是指算法所需辅助空间为常量，即O(1)

一个算法应该是问题求解步骤的描述

所谓时间复杂度，是指最坏情况下估算算法执行时间的一个上界

同一个算法，实现语言的级别越高，执行效率越低

时间复杂度与空间复杂度

算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。

时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。

大O的表示法规则

时间复杂度和空间复杂度一般都使用大O的渐进表示法进行表示，大O的渐进表示法规则如下：

1、所有常数都用常数1表示。 2、只保留最高阶项。 3、如果最高阶项存在且不是1，则去除与这个项的系数，得到的结果就是大O阶。

常见的时间复杂度量级有：

常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(nlogN)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)

方法

事后统计法

T(n) = O( f(n) )

这种方法可行，但不是一个好的方法。该方法有两个缺陷：一是要想对设计的算法的运行性能进行评测，必须先依据算法编制相应的程序并实际运行；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优势。

事前分析估算的方法因事后统计方法更多的依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。在编写程序前，依据统计方法对算法进行估算。一个程序在计算机上运行时所消耗的时间取决于下列因素： (1) 算法采用的策略、方法；(2).编译产生的代码质量；(3) 问题的输入规模；(4)机器执行指令的速度。

常数阶

int i = 1;
int j = 2;
++i;
j++;

线性阶

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

对数阶

int i = 1;
while(i<n)
{
    i = i * 2;
}

线性对数阶

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

平方阶

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

一种O（m*n)

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

其余以此类推

空间复杂度

O(1)

int i = 1;
int j = 2;
++i;
j++;

O(n)

1 2	int[] m = new int[n]

ACM 时间复杂度

复杂度大小顺序

$ O(1) < O(n) < O(n) < O(n n) < O(n^2) < O(n^3) < O(2^n) < O(n!) $

不同规模 $n$ 的复杂度选择

$n < 200$：
可以选择复杂度为 $O(n^3)$ 的算法。
例：动态规划 (dp)，Floyd 算法。
$n < 5000$：
可以选择复杂度为 $O(n^2)$ 的算法。
例：动态规划 (dp)，Dijkstra 算法，朴素版 Prim 算法。
$n < 10^6$：
可以选择复杂度为 $O(n \log n)$ 或 $O(n^2 \log n)$ 的算法。
例：排序 (sort)，线段树，树状数组，集合 (set)，映射 (map)，SPFA，凸包，二分法。
$n < 10^7$：
可以选择复杂度为 $O(n)$ 的算法。
例：哈希，双指针，KMP，AC 自动机，部分排序 (sort)，树状数组，SPFA。
$n < 10^8$：
可以选择复杂度为 $O(n)$ 的算法。
例：双指针，KMP，AC 自动机，线性筛选法。
$n < 10^9$：
可以选择复杂度为 $O(\sqrt{n})$ 的算法。
例：判断质数。
$n < 10^{18}$：
可以选择复杂度为 $O(\log n)$ 的算法。
例：二分法，欧几里得算法，幂运算。

线性表

一、线性表的定义

线性表（List）：零个或多个数据元素的有限序列。

元素数据类型相同，可以是整型也可以是结构体。

有限一词的解释

有限：

表中的数据元素个数为n（也叫做线性表的长度，n>=0），是有限个元素。当线性表长度n=0时，此时线性表是一个空表。

序列

一列，一对一

线性表的数据集合为{a1,a2,…,an}，假设每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且只有一个直接后继。

a1是唯一的“第一个”元素，又称表头元素；an是唯一的“最后一个元素”，又称表尾元素。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件

注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。

基本操作

线性表的置空操作clear()：将一个已经存在的线性表置为空表；

线性表判空操作isEmpty()：判断线性表是否为空，若为空，则返回true；否则，返回为false；

求线性表的长度操作length()：求线性表中的数据元素的个数并返回其值；

取元素操作get(i)：读取并返回线性表中的第i个数据元素的值。其中i的取值范围为0≤i≤length()-1；

插入操作insert(i,x)：在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i的取值范围为0≤i≤length()。当i=0时，在表头插入x；当i=length()时，在表尾插入x；

删除操作remove(i)：删除并返回线性表中第i个数据元素。其中i的取值范围为0≤i≤length()-1；

查找操作indexOf(x)：返回线性表中首次出现的指定的数据元素的位序号，若线性表中不包含此数据元素，则返回-1；

二、线性表的存储结构

线性表的顺序表示和实现

顺序存储是用一组地址连续的存储单元依次存放线性表中各个元素的存储结构。

顺序表的特点就是逻辑顺序与物理顺序相同

在线性表中逻辑上相邻的数据元素，在物理存储上也是相邻的；

存储密度高，但要预先分配“足够应用”的存储空间，这可能会造成存储空间的浪费；

便于随机存储；

不便于插入和删除操作，这是因为在顺序表上进行的插入和删除操作会引起大量数据元素的移动；

代码实现步骤

#include <iostream>
#include <stdio.h>
//头文件部分
using namespace std;
//变量空间
#define MAXSIZE 100                  //最大值

typedef int ElemType;                //元素类型

typedef struct
{
	ElemType* elem;                  //存储空间动态申请
	int length;                      //顺序表的长度
}SeqList;

enum Status { Ok, Error };               //枚举类型

/*
创建一个空表，并将length置零，初始化存储容量
*/
Status InitSeqList(SeqList& L)
//初始化
{

	L.elem = new ElemType[MAXSIZE];

	if (!L.elem)
	{
		cout << "申请空间失败！" << endl;
		return Error;
	}
	L.length = 0;
	return Ok;
}

/*
插入操作
在顺序表L的第i（1≤i≤L.length+1）个位置插入新元素e。如果 i 的输入不合法，则返回false，表示插入失败；否则，将顺序表的第 i 个元素以及其后的所有元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。

算法思路：
1.判断 i 的值是否正确
2.判断表长是否超过数组长度
3.从后向前到第 i 个位置，分别将这些元素都向后移动一位
4.将该元素插入位置 i 并修改表长
线性表插入算法的平均时间复杂度为O(n)
*/
Status SeqListInsert(SeqList& L, int i, ElemType e)
{

	if ((i < 1) || (i > L.length + 1))
	{
		cout << "i位置不合法" << endl;
		return Error;
	}
	if (L.length == MAXSIZE)
	{
		cout << "顺序表已满" << endl;
		return Error;
	}
	for (int j = L.length-1; j >= i-1; j--) {
		L.elem[j + 1] = L.elem[j];
	}
	L.elem[i-1] = e;
	L.length++;
	return Ok;
}

/*
删除操作
删除顺序表L中第i（1≤i≤L.length）个位置的元素，成功则返回true，并将被删除的元素用引用变量e返回，否则返回false。

算法思路：
1.判断 i 的值是否正确
2.取删除的元素
3.将被删元素后面的所有元素都依次向前移动一位
4.修改表长
线性表删除算法的平均时间复杂度为O(n)
*/
Status SeqListDelete(SeqList& L, int i)
{
	if (i<1 || i>L.length)
	{
		cout << "i位置不合法" << endl;
		return Error;
	}
	//i后的元素向前移动一位
	for (int j = i; j < L.length; j++)
	{
		L.elem[j - 1] = L.elem[j];
	}
	L.length--;
	return Ok;
}


//遍历顺序表
void TraverseSeqList(SeqList L)
{
	if (L.length == 0)
	{
		cout << "顺序表为空！" << endl;
	}
	for (int i = 0; i < L.length; i++)
	{
		cout << L.elem[i] << " ";
	}
	cout << endl;
}

//清空线性表中数据
Status ClearList(SeqList& L)
{
	if (L.length == 0)
	{
		cout << "线性表为空" << endl;
		return Error;
	}
	for (int j = 0; j < L.length; j++)
	{
		L.elem[j] = 0;
	}
	L.length = 0;
	cout << "线性表已经数据已清空" << endl;
	return Ok;
}


//销毁线性表
Status DestroySeqList(SeqList& L)
{
	if (!L.elem)
	{
		cout << "线性表不存在" << endl;
		return Error;
	}
	free(L.elem);
	L.elem = NULL;
	cout << "顺序表成功销毁" << endl;
	return Ok;
}

//线性表是否为空
Status ListEmpty(SeqList& L)
{
	if (L.length == 0)
	{
		return Ok;
	}
	return Error;
}

//线性表的长度
int ListLength(SeqList& L)
{
	return L.length;
}


//返回e在线性表中的位置
/*
查询某个值在顺序表中是否存在，存在时，其位置是多少，其实就是将顺序表从第一个元素开始依次和这个值相比较。最多比较length次，最少比较一次。（表非空的情况下）
*/
int LocateElem(SeqList& L, ElemType& e)
{
	int currentIndex = -1;
	if (L.length == 0)
	{
		cout << "当前线性表为空" << endl;
		return currentIndex;
	}
	for (int i = 0; i < L.length; i++)
	{
		if (L.elem[i] == e)
		{
			currentIndex = i + 1;
			break;
		}
	}
	if (currentIndex == -1)
	{
		cout << "数据  " << e << "  不存在当前线性表中" << endl;
	}
	return currentIndex;
}



Status PriorElem(SeqList& L, ElemType cur_e, ElemType& pre_e) {
	//查找cur_e所在的位置
	int flag = LocateElem(L, cur_e);
	if (flag == -1)
	{
		return Error;
	}
	if (flag == 1)
	{
		cout << "该数据不存在直接前驱" << endl;
		return Error;
	}
	else
	{
		pre_e = L.elem[flag - 2];
		return Ok;
	}
}


//如果cur_e不是最后一个的值，就next_e返回cur_e后一个值
Status NextElem(SeqList& L, ElemType cur_e, ElemType& next_e)
{
	int flag = LocateElem(L, cur_e);
	if (flag == -1)
	{
		return Error;
	}
	if (flag == L.length)
	{
		cout << "该数据不存在直接后继" << endl;
		return Error;
	}
	else
	{
		next_e = L.elem[flag];
		return Ok;
	}
}

线性表的链式存储和实现

一、定义

链表属于一种离散的存储方式，离散是与连续相对的，数组是常见的连续存储方式。

线性的链式存储结构（链表）是指用任意的存储单元来依次存放线性表的结点，这组单元既可以是连续的，也可以是不连续的，甚至是零散的分布在内存中的任意位置上。因此，链表中的结点的逻辑次序和物理次序不一定相同。为了正确表示结点间的逻辑结构，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这两部分组成了链表中的结点结构（如图）。

链式存储的结构包含两个域：一个用于存储数据元素的信息，另一个用于存储直接后继的存储位置；存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。

其中，data是数据域，用来存放结点的值。Next是指针域（也称链域），用来存放后继结点的地址。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序连接在一起的。结点有一个链域的称为单链表

整个单链表的存取必须从头结点开始进行，头指针指向head指向第一个结点。同时，由最后一个结点无后继，故其指针域为空，即NULL。

数据结构中，在单链表的开始结点之前一般要附设一个类型相同的结点，称之为头结点。头结点的数据域可以不存储任何信息，头结点的指针域存储指向开始结点的指针，即第一个元素结点的存储位置。

头结点的好处：

便于首元结点的处理

首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;

2.便于空表和非空表的统一处理

无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

在单链表中，任何两个元素的存储位置之间没有固定的联系，每个元素的存储位置都包含在其直接前驱结点的信息中。因此，单链表，在单链表中，想要取得第i个数据元素，必须从头指针出发寻找。所以，单链表是非随机存取的存储结构。

代码演示

#include <iostream>
#include <stdio.h>
using namespace std;
#define MAXSIZE 100                  //最大值

typedef int ElemType;                //元素类型

typedef struct LNode {
	ElemType  data;               //数据域 
	struct LNode* next;          //指针域,指向一整个结点(结构体,该结构体中包含数据域和指针域) 
}LNode, * LinkList;

//为了方便，可以利用typedef 给某种数据类型起个别名；

enum Status { Ok, Error };               //枚举类型

//构造一个空的头结点
Status InitList_L(LinkList& L) {
	L = new LNode;      //产生头结点，并使L指向该头结点(L也称头指针)
	if (!L)  return Error;          //如果存储空间分配失败，返回ERROR
	L->next = NULL;                //将指针域赋值为NULL
	cout<<"空的头结点创建成功/n";
	return Ok;
}

//对线性表进行赋值 
Status ValueList_L(LinkList& L, ElemType e) {
	LinkList s, p;
	p = L;
	while (p->next) {
		p = p->next;
	}
	s = new LNode;       //生成一个新结点 
	s->data = e;                 //将e赋值给新结点的数据域 
	s->next = p->next;           //将新结点与后一个结点的地址连接
	p->next = s;
	return Ok;
}



//对线性表进行销毁
//注意是销毁，头节点要删除
/*
在对单链表进行销毁操作时，从头结点开始逐一释放，释放前使q指向开始释放的结点，当开始结点不为空时，执行释放过程，先释放头结点，然后将L，q都向后移，依次释放，因为q始终是L的后继，所以最后一定是L留到最后，最后释放L结点
*/
/*
为什么在delete L;之后还要将L赋值为空？

因为delete函数只是将之前动态分配给L的内存归还给系统，但是指针类型的结点L仍然存在，为了防止之后发生野指针访问，将L赋值为NULL
*/
Status DistoryList_L(LinkList& L) {
	if (!L) {            //如果线性表不存在，返回ERROR 
		printf("线性表不存在/n");
		return Error;
	}
	LinkList q = L->next;    //使q指向单链表的首元结点  
	while (q != NULL) {     //当q结点不为空时一直进入循环 
		delete L;          //释放L结点 
		L = q;            //将q结点赋值给L结点 
		q = L->next;      //将q结点赋值给L结点以后使q结点指向L的下一个结点 
	}
	delete L;    //此时q的值为NULL，L指向尾结点，将其释放
	L = NULL;
	cout<<"线性表已销毁/n";
}


//对线性表进行重置
//重置则是不销毁头结点
Status ClearList_L(LinkList& L)
{
	if (!L->next) {
		cout<<"线性表为空表，不需要重置/n";
		return Error;
	}
	LinkList p, q;
	p = L->next;          //将单链表的头结点赋值给p
	while (p) {
		q = p->next;      //将单链表的首元结点赋值给q
		delete p;
		p = q;
	}
	L->next = NULL;     //将头结点的指针域赋值为空 
	cout<<"线性表已重置/n";
	return Ok;
}


//判断线性表是否为空
Status ListEmpty_L(LinkList L)
{
	if (L) {
		if (L->next == NULL)       //如果首元结点不存在 
			cout<<"线性表是空表/n";
		else
			cout<<"线性表不是空表/n";
	}
	else {
		cout<<"线性表不存在，无法判断/n";
	}
	return Ok;
}


//获取线性表的长度
//获取线性表长度的核心思路是遍历单链表
int ListLength_L(LinkList L, int count)
{
	//L为带头结点的单链表的头指针，count为计数器
	LinkList p = L->next;    //定义p为单链表L的指针域 
	while (p) {
		p = p->next;
		count++;
	}
	return count;
}



//获取线性表某一位置对应的元素/
//与获取单链表的长度思路一样，获取单链表某一位置的元素也需要遍历单链表，只不过什么时候停止遍历由自己决定，可能不需要全部遍历。
Status GetElem_L(LinkList L, int index)
{
	LinkList p;
	p = L->next;       //使p指向L的首元结点
	int  count = 1;    //count为计数器 ，赋值等于1的原因是从首元结点开始计数 
	while (p && count < index) {    //顺着指针向后查找，直到p指向第index个元素或p为空 
		p = p->next;
		count++;        //此时p一直指向第count个元素 
	}
	if (!p || count > index) {
		cout<<"当前位置没有元素/n";
		return Error;
	}
	cout<<"第"<<index<<"个元素的值是："<< p->data<<'/n';
	return Ok;
}



//在线性表某一位置插入元素
Status ListInsert_L(LinkList& L, int index, ElemType e)
{
	LinkList p, q;
	p = L;      //将线性表的头结点赋值给p
	int count = 0;    //count为计数器 
	while (p && count < index - 1) {      //寻找第index-1个结点 
		p = p->next;         //此时的p结点指向第index-1个结点 
		count++;
	}
	if (!p || count > index - 1) {        //越界判断,index小于1或是index大于表长加1 
		cout<<"当前结点无法插入元素/n";
		return Error;
	}
	q = new LNode;
	q->data = e;            //将e赋值到q的数据域当中
	q->next = p->next;
	p->next = q;
	cout<<"元素插入成功/n";
	return Ok;
}


//删除线性表某一位置的元素
Status DeleteList_L(LinkList& L, int index)
{
	LinkList p, q;
	p = L;           //将线性表的头结点赋值给p
	int count = 0;   //计数器
	while (p->next && count < index - 1) {
		p = p->next;
		count++;            //此时p一直指向第count个结点 
	}
	if (!(p->next) || count > index - 1) {     //越界判断 
		cout<<"当前位置无法删除元素/n";
		return Error;
	}
	q = p->next;
	p->next = q->next;
	delete q;
	q = NULL;
	cout<<"当前位置元素已删除/n";
	return Ok;
}


//求线性表某一元素的前驱 
Status PriorElem_L(LinkList L, int index)
{
	LinkList p;
	int count = 0;       //count为计数器 
	p = L;
	while (p->next && count < index - 1) {       //寻找第index-1个结点 
		p = p->next;            //p一直指向第count个结点 
		count++;
	}
	if (!(p->next) || count > index - 1) {       //越界判断 
		cout<<"当前位置无法求该元素的前驱/n";
		return Error;
	}
	if (p != L)            //如果要获取第一个元素的前驱，就是获取头结点数据域的值 
		cout<<"该元素的前驱为："<<p->data<<"/n";
	else
		cout<<"该位置的前驱是头结点/n头结点的数据域中存储的值为"<< p->data<<'/n';
	return Ok;
}


//求线性表某一元素的后继 
Status NextElem_L(LinkList L, int index)
{
	LinkList p;
	int count = 0;
	p = L->next;
	while (p && count < index) {        //不断遍历寻找第index之后的结点 
		p = p->next;      //p一直指向index-1的后一个结点 
		count++;
	}
	//!p的目的是为了确保i不大于表长-1，count>index的目的是为了确保index不小于0 
	if (!p || count > index) {          //越界判断
		cout<<"当前位置无法求该元素的后继/n";
		return Error;
	}
	 cout<<"该元素的后继为："<< p->data<<'/n';
}


//打印线性表
Status PrintList_L(LinkList L)
{
	if (!L) {            //如果线性表不存在，返回ERROR 
		printf("线性表不存在，无法打印/n");
		return Error;
	}
	LinkList p;
	p = L->next;    //将L的首元结点赋值给p ,为了不将头结点打印出来 
	while (p) {
		cout << p->data << " ";   //将p结点的数据域输出 
		p = p->next;    //结点不断的向后移动 
	}
	cout<<'/n';
	return Ok;
}

介绍两种插法，头插法和尾插法

头插法

 LinkList  CreateList1(LinkList &L){

                  //从表尾到表头逆向建立单链表 L ，每次均在头结点之后插入元素

                  LNode  *s ;
                  int  x ;
                  L =new LNode  ;                 
    			 // 创建头结点
                  L->next = NULL ;                                                   
     			// 初始为空链表
                cin>>x;                                               
     			// 输入结点的值

                  while( x!= 0){                                                      
                   // 输入0 表示结束
                         s = new LNode  ;         
                    // 创建新结点
                         s->data =  x ;
                         s->next = L->next;                                          
                     // 将新结点插入表中，L为头指针
                         L->next = s ;
                      cin>>x;                                     
                  }                                                                         
                 return  L;
         }

/*采用头插法建立单链表，读入数据的顺序与生成的链表中元素的顺序是相反的。

尾插法

LinkList  CreateList2( LinkList &L)
{
                   // 从表头到表尾正向建立单链表 L ，每次均在表尾插入元素
                   int  x ;                                      // 设置元素类型为整型
                   L = new LNode  ;
                   LNode  *s , *r = L ;                    // r 为表尾指针
                cin>>x ;                 // 输入结点的值
                   while( x!= 0){                       // 输入 0 表示结束
                         s = new LNode  ;
                         s->data = x;
                         r-next = s ;
                         r = s ;                              // r 指向新的表尾结点
                         cin>>x ;
                   }
                   r->next = NULL;                     // 尾结点指针置空
                   return  L ;
           }

知识点

头指针和头结点区分：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息

采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的，每个结点插入时间为O(1)一共为O(n)

优缺点分析

优点

数据元素的个数可以自由扩充

插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高

缺点

存储密度小

存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）

其他链表

【数据结构与算法】 - 双向链表 - 详细实现思路及代码_c语言双向链表不同结构体怎么找链表数据-CSDN博客

`双向链表`

：在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

双向链表每个结点除了存储数据data外，还有两个指针记录上一个结点和下一个结点的地址，分别是前驱指针prev和后继指针next.

这两个指针使得双向链表的插入、删除等操作不需要像单向链表那样需要遍历整个链表来寻找前驱节点，提高了链表的操作效率。双向链表与单链表的区别

单向链表是一种链表，在每个节点中包含指向下一个节点的指针。这意味着在单向链表中，节点只能从头开始遍历到尾部。在单向链表中，每个节点只存储指向下一个节点的指针，而不存储指向前一个节点的指针。

双向链表是一种链表，在每个节点中包含指向下一个节点和前一个节点的指针。这意味着在双向链表中，节点可以被从头到尾或从尾到头遍历。在双向链表中，每个节点存储指向前一个节点和下一个节点的指针。

因此，双向链表可以更方便地进行双向遍历，但是需要更多的内存空间来存储每个节点的两个指针。相比之下，在单向链表中，只需要一个指针来指向下一个节点，因此内存占用量更小。

单链表

双向链表

特点

双向链表的特点：

双向链表可以反向访问到链表的结点，因为它有指向前一个结点的指针piror；

带有头结点的双向链表，为空链表时，头结点的两个指针域都指向NULL。

带有头结点的双向链表，为非空链表时，头结点的前驱指针域指向NULL，后驱指针域指向第一个结点；最后一个结点的前驱指针域指向前一个结点，后驱指针域指向NULL；其他结点的前驱指针域指向前一个结点，后驱指针域指向后一个结点；

代码综述


#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct _DoubleListNode
{
	ElemType data;
	struct _DoubleListNode* prior;	// 前驱指针
	struct _DoubleListNode* next;	// 后驱指针
}DoubleListNode,* DoubleLinkList;

enum Status { Ok, Error };               //枚举类型
/*
1、分配一个结点的存储空间作为头结点，并将头指针指向头结点；
2、让头结点的 prior指针 和 next指针 都指向NULL，头结点的数据填一个无效值；
3、将头指针返回给函数调用者。

*/

//初始化
DoubleLinkList ListInit()
{
	DoubleLinkList list = new DoubleListNode;
	list->prior = NULL;
	list->next = NULL;
	list->data = -1;
	return list;
}

//双向链表插入数据
/*
双向链表插入数据大致分为两个步骤：首先，找到插入位置n的前一个结点；其次，是插入新结点，可以：先连接新结点、再指向新结点的顺序。
先连接新结点：是先把新结点的两个指针域分别连接当前结点和下个结点，_new->prior = cur;、_new->next = cur->next;
再指向新结点：将当前节点的的指针域指向新节点，与旧节点断开，cur->next->prior = _new;、cur->next = _new;
*/
int ListInsert(DoubleLinkList list, int data, int n)// 将node插入到第n位,n从1开始
{
	if (list == NULL || n < 1) // 判断参数有效性
		return -1;

	DoubleListNode* cur = list;	// cur指向当前结点，初始化指向头结点
	int cur_i = 0;			// cur_i表示当前结点的序号,0-头结点
	while (cur && cur_i < (n - 1))// 当前结点有效，且不是插入位置的前一个结点，就后移一个
	{
		cur = cur->next;
		cur_i++;
	}
	if (!cur)			// 当前结点无效，说明已经移动到最后
	{
		cout << "链表不够长" << '/n';
		return -1;	// 链表没有 n 那么长
	}
	DoubleListNode* _new = new DoubleListNode;
	_new->data = data;
	_new->prior = cur;
	_new->next = cur->next;
	if (cur->next)		// 在最后一个结点插入时，cur->next==NULL
		cur->next->prior = _new;
	cur->next = _new;
	return 0;
}


//双向链表删除数据
// 删除第n个结点，且将删除的值通过data传出
int ListDelete(DoubleLinkList list, int* data, int n)
{
	if (list == NULL || data == NULL || n < 1)
		return -1;
	DoubleListNode* cur = list;	// cur指向当前结点，初始化指向头结点
	int cur_i = 0;				// cur_i表示当前结点的序号,0-头结点
	while (cur->next && cur_i < (n - 1))
	{// 下个结点有效，且当前位置不是删除位置的前一个，就后移一个
		cur = cur->next;
		cur_i++;
	}
	if (!cur->next)		// 下个结点无效，说明已经移动到最后
	{
		cout << "链表不够长" << '/n';
		return -1;		// 链表没有 n 那么长
	}
	DoubleListNode* _delete = cur->next;
	_delete->prior->next = _delete->next;
	_delete->next->prior = _delete->prior;
	delete _delete;
	return 0;
}


//双向链表查找数据
int ListFind(DoubleLinkList list, int* data, int n)
{
	if (list == NULL || data == NULL || n < 1)
		return -1;

	DoubleListNode* cur = list->next;// 指向第一个节点
	int cur_i = 1;			// i表示当前结点的序号
	while (cur && cur_i < n)	// 当前结点有效，且当前位置不是查找位置n，就往后移动一个
	{
		cur = cur->next;
		cur_i++;
	}
	if (!cur)			// 当前结点无效，说明已经移动到最后
	{
		cout << "链表不够长" << '/n'; 
		return -1;	// 链表没有 n 那么长
	}
	*data = cur->data;
	cout << "第" << n << "个结点值为" << *data << '/n';
	return 0;
}


//双向链表的销毁
void ListDestroy(DoubleLinkList list)
{
	DoubleListNode* cur = list->next;	// 指向第一个节点
	DoubleListNode* next = NULL;		// 用于保存下个结点地址
	while (cur)	// 当前结点有效，就往后移动
	{
		next = cur->next;		// 保存下个结点地址
		delete cur;				// 删除当前结点、并释放内存
		cur = next;				// 将当前结点指针指向下个结点
	}
	list->prior = NULL;
	list->next = NULL;
}

循环链表

循环链表:是一种头尾相接的链表(表中最后一个结点的指针域指向头结点，整个链表形成一个环
优点: 从表中任一结点出发均可找到表中其他结点
循环链表中没有NULL指针，当遍历链表时，终止条件是最后一个结点的指针域是否等于头指针
尾指针表示单循环链表:
首元结点的存储位置: R->next->next;

最后一个结点的存储位置: R
//用尾指针表示单循环链表访问首尾结点时间复杂度都为O(1)

需要注意的是，虽然循环链表成环状，但本质上还是链表，因此在循环链表中，依然能够找到头指针和首元节点等。循环链表和普通链表相比，唯一的不同就是循环链表首尾相连，其他都完全一样。

代码综述

#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct _ListNode
{
	int data;
	struct _ListNode* next; // 指向结点的指针
}ListNode,* CyclicList;//定义链表结点：包含数据域，指针域 .定义循环链表头指针，是指向结点的指针

enum Status { Ok, Error };               //枚举类型


//循环链表初始化
CyclicList ListInit()// 创建一个头结点，让其指针域指向自己，并返回头结点地址
{
	CyclicList list = new ListNode;
	list->next = list; // 指向头结点
	list->data = -1;
	return list;
}

// 循环链表插入数据
int ListInsert(CyclicList list, int data, int n)// 将node插入到第n位,n从1开始
{
	if (list == NULL || n < 1) // 判断参数有效性
		return -1;

	ListNode* cur = list;// cur指向当前结点，初始化指向头结点
	int cur_i = 0;			// i表示当前结点的序号,0-头结点
	while (cur->next != list && cur_i < (n - 1))
	{//不是最后一个结点，且不是插入位置的前一个结点，就后移一个
		cur = cur->next;
		cur_i++;
	}
	if (cur->next == list)			// 移动到最后结点 
	{
		if (cur_i != (n - 1))		// 仍然不是插入位置前一个结点，出错
		{
			cout << "链表不够长" << '/n';
			return -1;	// 链表没有 n 那么长
		}
	}
	ListNode* _new = new ListNode;
	_new->data = data;
	_new->next = cur->next;
	cur->next = _new;
	return 0;
}

//循环链表删除数据
// 删除第n个结点，且将删除的值通过data传出
int ListDelete(CyclicList list, int* data, int n)
{
	if (list == NULL || data == NULL || n < 1)
		return -1;
	ListNode* cur = list;	// cur指向当前结点，初始化指向头结点
	int cur_i = 0;			// i表示当前结点的序号,0-头结点
	while (cur->next != list && cur_i < (n - 1))
	{//不是最后一个结点，且不是删除位置的前一个结点，就后移一个
		cur = cur->next;
		cur_i++;
	}
	if (cur->next == list)		// 移动到最后结点 
	{
		cout << "链表不够长" << '/n';
		return -1;			// 链表没有 n 那么长
	}
	ListNode* _delete = cur->next;
	cur->next = _delete->next;
	delete _delete;
	return 0;
}


//循环链表查找数据
int ListFind(CyclicList list, int* data, int n)
{
	if (list == NULL || data == NULL || n < 1)
		return -1;

	ListNode* cur = list->next;	// 指向第一个节点
	int cur_i = 1;				// i表示当前结点的序号
	if (cur == list)
	{
		cout << "链表不够长" << '/n';
		return -1;	// 链表没有 n 那么长
	}
	while (cur->next != list && cur_i < n)
	{//不是最后一个结点，且当前位置不是查找位置n，就往后移动一个
		cur = cur->next;
		cur_i++;
	}
	if (cur->next == list)			// 移动到最后结点 
	{
		if (cur_i != n)		// 仍然不是查找位置n，出错
		{
			cout << "链表不够长" << '/n';
			return -1;	// 链表没有 n 那么长
		}
	}
	*data = cur->data;
	cout << "第" << n << "个结点的值是" << *data << '/n';
	return 0;
}

//循环链表的销毁
void ListDestroy(CyclicList list)
{
	ListNode* cur = list->next;	// 指向第一个节点
	ListNode* next = NULL;		// 用于保存下个结点地址
	while (cur != list)			// 不是最后一个结点的指针域就后移
	{
		next = cur->next;		// 保存下个结点地址	
		delete cur;				// 删除当前结点、并释放内存
		cur = next;				// 将当前结点指针指向下个结点
	}
	list->next = list;
}

总结

选择数组还是链表？

1.插入、删除和随机访问的时间复杂度数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。

2.数组缺点 1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。 2）大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。 3.链表缺点 1）内存空间消耗更大，因为需要额外的空间存储指针信息。 2）对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片。 4.如何选择？数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。如果代码对内存的使用非常苛刻，那数组就更适合。

栈与队列

栈

一、栈的基本概念

1、栈的定义

栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

栈顶（Top）：线性表允许进行插入删除的那一端。栈底（Bottom）：固定的，不允许进行插入和删除的另一端。空栈：不含任何元素的空表。

栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构

二、栈的顺序存储结构

1、栈的顺序存储采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判断条件定位top等于-1。栈的基本操作

#include<iostream>
using namespace std;
#define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
typedef struct {
    ElemType data[MAXSIZE];
    int top;    //用于栈顶指针
}SqStack;

enum Status { Ok, Error };               //枚举类型



void InitStack(SqStack* S) {
    S->top = -1;    //初始化栈顶指针
}

//判断栈空
bool StackEmpty(SqStack S) {
    if (S.top == -1) {
        return true;    //栈空
    }
    else {
        return false;   //不空
    }
}


/*插入元素e为新的栈顶元素*/
Status Push(SqStack* S, ElemType e) {
    //满栈
    if (S->top == MAXSIZE - 1) {
        return Error;
    }
    S->top++;   //栈顶指针增加一
    S->data[S->top] = e;    //将新插入元素赋值给栈顶空间
    return Ok;
}

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqStack* S, ElemType* e) {
    if (S->top == -1) {
        return Error;
    }
    *e = S->data[S->top];   //将要删除的栈顶元素赋值给e
    S->top--;   //栈顶指针减一
    return Ok;
}


/*读栈顶元素*/
Status GetTop(SqStack *S, ElemType* e) {
    if (S->top == -1) {   //栈空
        return Error;
    }
    *e = S->data[S->top];   //记录栈顶元素
    return Ok;
}

偏向于ACM的栈实现

int st[N];
// 这里使用 st[0] (即 *st) 代表栈中元素数量，同时也是栈顶下标

// 压栈 ：
st[++*st] = var1;
// 取栈顶 ：
int u = st[*st];
// 弹栈 ：注意越界问题, *st == 0 时不能继续弹出
if (*st) --*st;
// 清空栈
*st = 0;

/*
C++ 中的 STL 也提供了一个容器 std::stack，使用前需要引入 stack 头文件。
STL 中的 stack 容器提供了一众成员函数以供调用，其中较为常用的有：

元素访问
st.top() 返回栈顶
修改
st.push() 插入传入的参数到栈顶
st.pop() 弹出栈顶
容量
st.empty() 返回是否为空
st.size() 返回元素数量
此外，std::stack 还提供了一些运算符。较为常用的是使用赋值运算符 = 为 stack 赋值，示例：

// 新建两个栈 st1 和 st2
std::stack<int> st1, st2;

// 为 st1 装入 1
st1.push(1);

// 将 st1 赋值给 st2
st2 = st1;

// 输出 st2 的栈顶元素
cout << st2.top() << endl;
// 输出: 1
*/

共享栈（两栈共享空间）

（1）共享栈概念

利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如下图所示：

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空；仅当两个栈顶指针相邻（top0+1=top1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减一再赋值出栈时则刚好相反。

顺序存储

#include<iostream>
using namespace std;
/*两栈共享空间结构*/
#define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
/*两栈共享空间结构*/
typedef struct {
	ElemType data[MAXSIZE];
	int top0=0;	//栈0栈顶指针
    int top1 = MAXSIZE;	//栈1栈顶指针
}SqDoubleStack;
enum Status { Ok, Error };               //枚举类型

/*插入元素e为新的栈顶元素*/
Status Push(SqDoubleStack* S, ElemType e, int stackNumber) {
    if (S->top0 + 1 == S->top1) {   //栈满
        return Error;
    }
    if (stackNumber == 0) {   //栈0有元素进栈
        S->data[++S->top0] = e; //若栈0则先top0+1后给数组元素赋值
    }
    else if (stackNumber == 1) { //栈1有元素进栈
        S->data[--S->top1] = e; //若栈1则先top1-1后给数组元素赋值
    }
    return Ok;
}


/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqDoubleStack* S, ElemType* e, int stackNumber) {
    if (stackNumber == 0) {
        if (S->top0 == -1) {
            return Error;   //说明栈0已经是空栈，溢出
        }
        *e = S->data[S->top0--]; //将栈0的栈顶元素出栈，随后栈顶指针减1
    }
    else if (stackNumber == 1) {
        if (S->top1 == MAXSIZE) {
            return Error;   //说明栈1是空栈，溢出
        }
        *e = S->data[S->top1++];    //将栈1的栈顶元素出栈，随后栈顶指针加1
    }
    return Ok;
}

三、栈的顺序存储结构

　对于链栈来说，基本不存在栈满的情况，除非内存已经没有使用空间了。

#include<iostream>
using namespace std;
/*两栈共享空间结构*/
typedef struct StackNode
{
	int data;//结点数据域
	struct StackNode* next;//结点指针域
}StackNode, * Linktop;

//链栈的数据结构
typedef struct LinkStack
{
	Linktop top;   //栈顶结点,定义了一个指向上个结构体的指针
	int count;//元素个数
}LinkStack;

//压栈:先将压入元素放入到链表表中，然后再将栈顶指针指向压入的元素，然后count+1.
int push(LinkStack* stack, int e)
{
	if (!stack)
	{
		return 0;
	}
	StackNode* node = new StackNode;
	node->next = stack->top;           //将元素加入链表中
	node->data = e;
	stack->top = node;                 //栈顶元素指向压入元素
	stack->count++;
	return 1;
}

//弹栈:栈顶指针指向要弹出元素前置结点，然后释放弹出元素内存空间，然后count-1
int pop(LinkStack* stack, int* e)
{
	if (!stack && stack->count)
	{
		return	0;
	}
	StackNode* node = stack->top;
	*e = node->data;
	stack->top = node->next;   //栈顶指针指向新的栈顶元素
	delete node;                //释放元素空间
	stack->count--;
	return 1;
}

单调栈

何为单调栈？顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。

为了描述方便，以下举例及伪代码以维护一个整数的单调递增栈为例。

insert x
while !sta.empty() && sta.top()<x
    sta.pop()
sta.push(x)

洛谷单调栈

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
int n;
const int N=5e6;
int a[N];
int stk[N];
int ans[N];
int main()
{
cin>>n;
int top=0;
rep(i,1,n)
{
	cin>>a[i];
while(top && !(a[stk[top]]>=a[i]))	
ans[stk[top--]]=i;
	stk[++top]=i;
}
//构造一个单调递减栈
rep(i,1,n)
{
	cout<<ans[i]<<' ';
}
}

队列

一、队列的基本概念

1、队列的定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队头（Front）：允许删除的一端，又称队首。 队尾（Rear）：允许插入的一端。 空队列：不包含任何元素的空表。

向队列中插入新的数据元素称为入队，新入队的元素就成为了队列的队尾元素。

从队列中删除队头元素称为出队，其后继元素成为新的队头元素。

二、队列的顺序存储结构

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front指向队头元素，队尾指针 rear 指向队尾元素的下一个位置。

但是会有假溢出的出现，因此需要另外一种队列，这种队列的这种头尾相接的顺序存储结构称为循环队列。

当队首指针Q->front = MAXSIZE-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。

初始时：Q->front = Q->rear=0。队首指针进1：Q->front = (Q->front + 1) % MAXSIZE。队尾指针进1：Q->rear = (Q->rear + 1) % MAXSIZE。队列长度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE。

#include<iostream>
using namespace std;
typedef int QElemType;
#define MAXSIZE 50	//定义队列中元素的最大个数
typedef struct {
	QElemType data[MAXSIZE];	//存放队列元素
	int front, rear;
}SqQueue;
enum Status{OK,ERROR};
Status visit(QElemType c)
{
    cout << c<<'/n';
    return OK;
}

/* 初始化一个空队列Q */
Status InitQueue(SqQueue* Q)
{
    Q->front = 0;
    Q->rear = 0;
    return  OK;
}

/* 将Q清为空队列 */
Status ClearQueue(SqQueue* Q)
{
    Q->front = Q->rear = 0;
    return OK;
}

/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(SqQueue Q)
{
    if (Q.front == Q.rear) /* 队列空的标志 */
        return OK;
    else
        return ERROR;
}

/* 返回Q的元素个数，也就是队列的当前长度 */
int QueueLength(SqQueue Q)
{
    return  (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}


/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
Status GetHead(SqQueue Q, QElemType* e)
{
    if (Q.front == Q.rear) /* 队列空 */
        return ERROR;
    *e = Q.data[Q.front];
    return OK;
}

/* 若队列未满，则插入元素e为Q新的队尾元素 */
Status EnQueue(SqQueue* Q, QElemType e)
{
    if ((Q->rear + 1) % MAXSIZE == Q->front)    /* 队列满的判断 */
        return ERROR;
    Q->data[Q->rear] = e;            /* 将元素e赋值给队尾 */
    Q->rear = (Q->rear + 1) % MAXSIZE;/* rear指针向后移一位置， */
    /* 若到最后则转到数组头部 */
    return  OK;
}

/* 从队头到队尾依次对队列Q中每个元素输出 */
Status QueueTraverse(SqQueue Q)
{
    int i;
    i = Q.front;
    for (i = Q.front; i != Q.rear; i = (i + 1) % MAXSIZE) {
        visit(Q.data[i]);
    }
    cout << '/n';
    return OK;
}

ACM队列相关

队列（queue）是一种具有「先进入队列的元素一定先出队列」性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。

数组模拟队列

通常用一个数组模拟一个队列，用两个变量标记队列的首尾。

队列操作对应的代码如下：

插入元素：q[++qr] = x;

删除元素：ql++;

访问队首：q[ql]

访问队尾：q[qr]

清空队列：ql = 1; qr = 0;

STL 中的 queue 容器提供了一众成员函数以供调用。其中较为常用的有：

元素访问

q.front() 返回队首元素

q.back() 返回队尾元素

修改

q.push() 在队尾插入元素

q.pop() 弹出队首元素

容量

q.empty() 队列是否为空

q.size() 返回队列中元素的数量

STL 中的 deque 容器提供了一众成员函数以供调用。其中较为常用的有：

元素访问

q.front() 返回队首元素

q.back() 返回队尾元素

修改

q.push_back() 在队尾插入元素

q.pop_back() 弹出队尾元素

q.push_front() 在队首插入元素

q.pop_front() 弹出队首元素

q.insert() 在指定位置前插入元素（传入迭代器和元素）

q.erase() 删除指定位置的元素（传入迭代器）

容量

q.empty() 队列是否为空

q.size() 返回队列中元素的数量

三、队列的链式存储结构

链队列

队列的链式存储结构表示为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表，只不过它只能尾进头出而已。

#include<iostream>
using namespace std;
typedef int ElemType;
#define MAXSIZE 50	//定义队列中元素的最大个数
/*链式队列结点*/
typedef struct LinkNode {
	ElemType data;
	struct LinkNode* next;
}LinkNode;
/*链式队列*/
typedef struct {
	LinkNode* front, * rear;	//队列的队头和队尾指针
}LinkQueue;

enum Status{OK,ERROR};

//链队列初始化
void InitQueue(LinkQueue* Q) 
{
	Q->front = Q->rear = new LinkNode;	//建立头结点
	Q->front->next = NULL;	//初始为空
}

//链队列入队

Status EnQueue(LinkQueue* Q, ElemType e) {
	LinkNode *s = new LinkNode;
	s->data = e;
	s->next = NULL;
	Q->rear->next = s;	//把拥有元素e新结点s赋值给原队尾结点的后继
	Q->rear = s;	//把当前的s设置为新的队尾结点
	return OK;
}

/*若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR*/
Status DeQueue(LinkQueue* Q, ElemType* e) {
	LinkNode *p;
	if (Q->front == Q->rear) {
		return ERROR;
	}
	p = Q->front->next;	//将欲删除的队头结点暂存给p
	*e = p->data;	//将欲删除的队头结点的值赋值给e
	Q->front->next = p->next;	//将原队头结点的后继赋值给头结点后继
	//若删除的队头是队尾，则删除后将rear指向头结点
	if (Q->rear == p) 
	{
		Q->rear = Q->front;
	}
	delete p;
	return OK;
}

双端队列

双端队列（deque）是队列的一种变形，一般队列只能在队尾添加元素（push），在队首删除元素（pop），双端队列则同时在队首或者队尾执行添加和删除工作。C++中，使用双端队列需要包含头文件。C++中队列的基本操作如下：

push_back()：在队列尾部添加元素，无返回值。这个操作跟普通队列（queue）的push()方法类似，在队列的尾部添加一个元素； push_front()：在队列头部添加元素，无返回值； pop_back()：删除队列尾部的元素，无返回值； pop_front()：删除队列头部的元素，无返回值； front() ：获得队列头部元素。此函数返回值为队列的头部元素，常与pop_front()函数一起，先通过front()获得队列头部元素，然后用pop_front()将其从队列中删除； back()：获得队列尾部元素。此函数返回值为队列的尾部元素，常与pop_back()函数一起，先通过back()获得队列头部元素，然后用pop_back()将其从队列中删除； size()：获得队列大小。此函数返回队列的大小，返回值是“size_t”类型的数据，“size_t”是“unsigned int”的别名； empty() ：判断队列是否为空。此函数返回队列是否为空，返回值是bool类型。队列空：返回true；不空：返回false。

堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。

每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。

（小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。

单调队列

顾名思义，单调队列的重点分为「单调」和「队列」。

「单调」指的是元素的「规律」——递增（或递减）。

例如我们构造一个单调递增的队列会如下：

原序列为：

1 1 3 -1 -3 5 3 6 7

因为我们始终要维护队列保证其递增的特点，所以会有如下的事情发生：

操作队列状态

1 入队 {1}

3 比 1 大，3 入队 {1 3}

-1 比队列中所有元素小，所以清空队列 -1 入队 {-1}

-3 比队列中所有元素小，所以清空队列 -3 入队 {-3}

5 比 -3 大，直接入队 {-3 5}

3 比 5 小，5 出队，3 入队 {-3 3}

-3 已经在窗体外，所以 -3 出队；6 比 3 大，6 入队 {3 6}

7 比 6 大，7 入队 {3 6 7}

操作	队列状态
1 入队	`{1}`
3 比 1 大，3 入队	`{1 3}`
-1 比队列中所有元素小，所以清空队列 -1 入队	`{-1}`
-3 比队列中所有元素小，所以清空队列 -3 入队	`{-3}`
5 比 -3 大，直接入队	`{-3 5}`
3 比 5 小，5 出队，3 入队	`{-3 3}`
-3 已经在窗体外，所以 -3 出队；6 比 3 大，6 入队	`{3 6}`
7 比 6 大，7 入队	`{3 6 7}`

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
const int N = 1e7;
int a[N];
int q[N];
int q2[N];
int main()
{
int n,m;
cin>>n>>m;
rep(i,1,n)
{
    cin>>a[i];
}
int h=1,t=0;
rep(i,1,n)
{
while (h <= t && q[h] + m <= i)
{
    h++;
}
while (h <= t && a[i]<a[q[t]])
{
    t--;
}
q[++t] = i;
if(i>=m)
{
    cout<<a[q[h]]<<' ';
}
}
cout<<'/n';
 h = 1, t = 0;
rep(i, 1, n)
{

    while (h <= t && q2[h] + m <= i)
    {
        h++;
    }
    while (h <= t && a[i] > a[q2[t]])
    {
        t--;
    }
    q2[++t] = i;
    if (i >= m)
    {
        cout << a[q2[h]] << ' ';
    }
}
}

串

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集

串的存储结构：定长顺序存储表示、堆分配存储表示、块链存储表示

子串的定位操作通常称为串的模式匹配，它求的是子串在主串中的位置。

1、串的概念 字符串简称串，是一种特殊的线性表，它的数据元素仅由一个字符组成。

2、串的定义 串(String)是由零个或多个字符组成的有限序列，又称字符串。

其中s是串名,用双引号括起来的字符序列为串值，但引号本身并不属于串的内容。ai(1<=i<=n)是一个任意字符,它称为串的元素,是构成串的基本单位，i是它在整个串中的序号；n为串的长度,表示串中所包含的字符个数。

串的长度：串中字符的个数
空串：长度为0的串
空格串：0个或多个空格字符组成的串
子串：串中任意连续字符组成的子序列
主串：包含子串的串
位置：字符在串中的序号。子串在主串中的位置是其第一个字符在主串中的位置。
串的相等：长度和对应位置字符都相等
连接 concatenation：连接是一个重要的二进制操作。对于任意两个主串中的子串s和t，它们的连接根据放置s和t 的前后顺序来定符号序列。例如，子串s = love，t = hug，那么st 就是lovehug，ts 就是huglove。
前缀和后缀 prefixes and suffixes：字符串s 可以说是t 的前缀，如果存在一个字符串u 满足条件t =su。如果u 是非空的，那么可以说s 是t 的一个合适的前缀；相应地，串s 可以说t 的后缀如果存在一个串u 满足条件t=us。如果u 是非空的，s 可以说是t 的一个合适的后缀。前缀和后缀可以说是t 的子串。
旋转：串s = uv 可以被说成t 的旋转如果t = vu. 举个例子，当u = 00110, v = 01的时候，串0011001 是0100110 的旋转。
逆转:串的逆转就是具有相同符号单顺序相反的字符串。例如，如果s=abc（a、b和c是字母表中符号），那么s 的逆转就是cba。一个与自身相反的字符串（例如，s=madam，逆转还是madam）被称为回文 palindrome，它还包括空字符串和所有长度为1的字符串。

设A和B分别为 A=‘This is a string’ B=‘is’ 则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的位置为3。特别地，空串是任意串的子串，任意串是其自身的子串。

二、串的存储结构

1、定长顺序存储表示

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，为每个串变量分配一个固定长度的存储区，即定长数组。

#include<iostream>
using namespace std;
#define TRUE 1
#define OK 1
#define ERROR 0
#define FALSE 0
#define MAXSTRLEN 255   //串的最大存储容量定义为255
typedef unsigned char SString[MAXSTRLEN + 1];   //定义串的类型别名
typedef int status;
//创建一个串
status STrAssign(SString& T, char* chars)
{ //创建一个值等于chars的串
	int i;
	if (strlen(chars) > MAXSTRLEN)  return ERROR;
	T[0] = strlen(chars);
	for (i = 1; i <= T[0]; i++)
	{
		T[i] = *(chars + i - 1);
	}
	return OK;
}
//判断串是否为空串
status StrEmpty(SString S)
{   //判断S是否为空串
	if (S[0] == 0) return TRUE;
	else
		return FALSE;
}

//输出串
void StrPrint(SString T)
{  //输出字符串T
	int i;
	for (i = 1; i <= T[0]; i++)
		cout << T[i];
	cout << endl;
}

//返回串的元素个数
status Strlength(SString S)
{  //返回串的元素个数
	return S[0];
}

//将串清空
status ClearString(SString S)
{ //将S清为空串 
	S[0] = 0;              /* 直接令串长为零 */
	return OK;
}
//将串S复制到串T中
status StrCopy(SString& T, SString& S)
{   //由串S复制得串T
	int i;
	for (i = 1; i <= S[0]; i++)
		T[i] = S[i];
	T[0] = S[0];
	return OK;
}

//比较串S和串T
//若S > T, 则返回值 > 0; 若S = T, 则返回值 = 0; 若S < T, 则返回值 < 0
status StrCompare(SString S, SString T)
{
	if (StrEmpty(S) || StrEmpty(T)) return ERROR;
	int i;
	for (i = 1; i <= S[0] && i <= T[0]; i++)
	{
		if (S[i] != T[i]) return S[i] - T[i];    //如果不相等，直接返回不相等的值的相减
	}
	return S[0] - T[0];                          //如果字符全部相等，返回他们字符长度的差值
}

//删除串中第pos个字符起长度为len的子串
status StrDelete(SString S, int pos, int len)
{
	// 从串S中删除第pos个字符起长度为len的子串 
	int i;
	if (pos<0 || pos>S[0] - len + 1 || len < 0)
		return ERROR;
	for (i = pos + len; i <= S[0]; i++)
		S[i - len] = S[i];
	S[0] -= len;
	return OK;
}

//在串的第pos个字符之后插入串T
status StrInsert(SString& S, int pos, SString T)
{  //在串S的第pos个字符之后插入串T。完全插入返回TRUE, 部分插入返回FALSE
	int i;
	if (pos<1 || pos>MAXSTRLEN) return ERROR;
	if (S[0] + T[0] <= MAXSTRLEN)
	{
		for (i = S[0]; i >= pos; i--)
			S[i + T[0]] = S[i];
		for (i = pos; i < pos + T[0]; i++)
			S[i] = T[i - pos + 1];
		S[0] = S[0] + T[0];
		return TRUE;
	}
	else
	{  //部分插入
		for (i = MAXSTRLEN; i >= pos + T[0]; i--)
			S[i] = S[i - T[0]];
		for (i = pos; i < pos + T[0]; i++)
			S[i] = T[i - pos + 1];
		S[0] = MAXSTRLEN;
		return FALSE;
	}
}


//返回串中第pos个字符起，长度为len的子串
status SubString(SString& Sub, SString S, int pos, int len)
{//求串S中第pos个字符起，长度为len的子串
	int i;
	if (pos < 1 || pos > S[0] || len < 0 || pos + len - 1 > S[0])
		return ERROR;
	for (i = 1; i <= len; i++)
	{
		Sub[i] = S[pos+i-1];
	}
	Sub[0] = len;
	return OK;
}

//联接两个串组成新串
status Concat(SString& T, SString s1, SString s2)
//两串用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE
{
	int i;
	if (s1[0] + s2[0] <= MAXSTRLEN)  //串一和串二长度的总和小于主串的最大容量,未截断
	{
		for (i = 1; i <= s1[0]; i++)     T[i] = s1[i];
		for (i = 1; i <= s2[0]; i++)     T[s1[0] + i] = s2[i];
		T[0] = s1[0] + s2[0];
		return TRUE;
	}
	else if (s1[0] < MAXSTRLEN)    //两串的长度的总和超过最大容量，串一未超过,串二被截断
	{
		for (i = 1; i <= s1[0]; i++)   T[i] = s1[i];
		for (i = 1; i < MAXSTRLEN - s1[0]; i++)  T[s1[0] + i] = s2[i];
		T[0] = MAXSTRLEN;
		return FALSE;
	}
	else                         //两串均超过最大容量，均被截断，取串一中的元素
	{
		for (i = 1; i <= MAXSTRLEN; i++)   T[i] = s1[i];
		T[0] = MAXSTRLEN;
		return FALSE;
	}
}

//串的定长顺序存储表示，SString[0]用来存储串的元素个数

/*
串的实际长度只能小于等于MAXLEN，超过预定义长度的串值会被舍去，称为截断。
顺序存储，例如串S=”sjjg”，其中从S.ch[0]开始存放串，最后以字符’/0’来表示串值的结束，如下图：
*/

2、堆分配存储表示

堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。

typedef struct{
	char *ch;	//按串长分配存储区，ch指向串的基地址
	int length;	//串的长度
}HString;

3、块链存储表示

类似于线性表的链式存储结构，也可采用链表方式存储串值。由于串的特殊性(每个元素只有一个字符)，在具体实现时，每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。

串的模式匹配

子串的定位操作是找子串在主串中从第pos个字符后首次出现的位置，又被称为串的模式匹配

一、BF模式匹配算法

BF算法思想:Brute-Force算法又称蛮力匹配算法(简称BF算法),从主串S的第pos个字符开始，和模式串T的第一个字符进行比较，若相等，则继续比较后续字符；否则回溯到主串S的第pos+1个字符开始重新和模式串T进行比较。以此类推，直至模式串T中的每一个字符依次和主串S中的一个连续的字符序列相等，则称模式匹配成功，此时返回模式串T的第一个字符在主串S中的位置；否则主串中没有和模式串相等的字符序列，称模式匹配不成功。

算法分析:
- BF算法的思想比较简单，但当在最坏情况下，算法的时间复杂度为O(n*m),其中n和m分别是主串和模式串的长度。

/*
第一轮：子串中的第一个字符与主串中的第一个字符进行比较
若相等，则继续比较主串与子串的第二个字符
若不相等，进行第二轮比较


第二轮：子串中的第一个字符与主串中第二个字符进行比较......
第N轮：依次比较下去，直到全部匹配
*/
int ViolentMatch(char* s, char* p)  
{  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
  
    int i = 0;  
    int j = 0;  
    while (i < sLen && j < pLen)  
    {  
        if (s[i] == p[j])  
        {  
            //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++      
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0      
            i = i - j + 1;  
            j = 0;  
        }  
    }  
    //匹配成功，返回模式串p在文本串s中的位置，否则返回-1  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}

这种算法简单易懂，却存在着一个很大的缺点，那就是需要多次回溯，效率低下，若主串为 000000000001 子串为00001，这就意味着每一轮都要比较到子串的最后一个字符才会匹配失败，有没有更好的办法呢？下面的KMP模式匹配算法就很好的解决了这一问题

KMP算法

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。

朴素模式匹配算法，主串的 i 值会不断的进行回溯，但是 KMP模式匹配算法：

KMP 方法算法就利用之前判断过的信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间。

将这种没必要的回溯省略掉了，所以减少了执行次数

什么是最长公共前后缀字符串的前缀是指不包含最后一个字符的所有以第一个字符（索引为0）开头的连续子串

比如字符串 “ABABA” 的前缀有：A，AB，ABA，ABAB

字符串的后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

比如字符串 “ABABA” 的后缀有：BABA，ABA，BA，A

公共前后缀：一个字符串的所有前缀连续子串和所有后缀连续子串中相等的子串

比如字符串 “ABABA”

前缀有：A，AB，ABA，ABAB 后缀有：BABA，ABA，BA，A 因此公共前后缀有：A ，ABA

最长公共前后缀：所有公共前后缀的长度最长的那个子串

比如字符串 “ABABA” ，公共前后缀有：A ，ABA

由于 ABA 是三个字符长度，A 是一个字符长度，那么最长公共前后缀就是 ABA

再比如说一个字符串 str = “ABCABD”

对于str从索引为0 开始的子串 “A” 而言：

前缀：不包含最后一个字符A的所有以第一个字符A开头的连续子串不存在后缀：不包含第一个字符A 的所有以最后一个字符A结尾的连续子串不存在因此该子串的最长公共前后缀为 0

对于str从索引为0 开始的子串 “AB” 而言：

前缀：不包含最后一个字符B 的所有以第一个字符A开头的连续子串有 —— “A” 后缀：不包含第一个字符A 的所有以最后一个字符B结尾的连续子串有 —— “B” 因此该子串的最长公共前后缀为 0

对于str从索引为0 开始的子串 “ABC” 而言：

前缀：不包含最后一个字符C 的所有以第一个字符A开头的连续子串有 —— “A”，“AB” 后缀：不包含第一个字符A 的所有以最后一个字符C 结尾的连续子串有 —— “BC”，“C” 前缀与后缀的连续子串不存在相同的，因此该子串的最长公共前后缀为 0

对于str从索引为0 开始的子串 “ABCA” 而言：

前缀：不包含最后一个字符A 的所有以第一个字符A开头的连续子串有 —— “A”，“AB”，“ABC” 后缀：不包含第一个字符A 的所有以最后一个字符A 结尾的连续子串有 —— “BCA”，“CA”，“A” 前缀与后缀的连续子串中存在相同且最长的子串 A，因此该子串的最长公共前后缀为 1

对于str从索引为0 开始的子串 “ABCAB” 而言：

前缀：不包含最后一个字符B 的所有以第一个字符A开头的连续子串有 —— “A”，“AB”，“ABC”，“ABCA” 后缀：不包含第一个字符A 的所有以最后一个字符B 结尾的连续子串有 —— “BCAB”，“CAB”，“AB”，“B” 前缀与后缀的连续子串中存在相同且最长的子串 AB，因此该子串的最长公共前后缀为 2

对于str从索引为0 开始的子串 “ABCABD” 而言：

前缀：不包含最后一个字符D 的所有以第一个字符A开头的连续子串有 —— “A”，“AB”，“ABC”，“ABCA”，“ABCAB” 后缀：不包含第一个字符A 的所有以最后一个字符D 结尾的连续子串有 —— “BCABD”，“CABD”，“ABD”，“BD”，“D” 前缀与后缀的连续子串不存在相同的，因此该子串的最长公共前后缀为 0 https://blog.csdn.net/qq_62982856/article/details/128003067

因此kmp算法本质是求解两次最长公共前后缀的过程。

正常的算法是暴力，然后i，j开始匹配，不相同回溯，i回溯到1，j回溯到0，简单粗暴，时间复杂度高，算法时间复杂度很高。

优化就是大名鼎鼎的kmp算法。

利用匹配失败后的信息，尽量减少模式串与主串的匹配次数。

前置知识：

前缀集合

后缀集合。

kmp算法中不回溯i，只回溯j。

a子串的后缀与b子串的前缀集合相等时候就可以

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int kmp[N];
int la,lb,j; 
string a;
string b;
int main()
{
    cin>>a;
    cin>>b;
    a=" "+a;
    b=" "+b;
    la=a.length()-1;
    lb=b.length()-1;
    for (int i=2;i<=lb;i++)
	   {     
	   while(j&&b[i]!=b[j+1])
        j=kmp[j];     
       if(b[j+1]==b[i])j++;    
        kmp[i]=j;
       }
    j=0;
    for(int i=1;i<=la;i++)
	   {
          while(j>0&&b[j+1]!=a[i])
           j=kmp[j];
          if (b[j+1]==a[i]) 
           j++;
          if (j==lb) 
		  {
		  cout<<i-lb+1<<'/n';
		  j=kmp[j];
		  }
       }

    for (int i=1;i<=lb;i++)
    cout<<kmp[i]<<" ";

}

树

数据结构：树(Tree)【详解】_数据结构树-CSDN博客

存储的是具有“一对多”关系的数据元素的集合。

1、树的定义

树是n（n>=0）个结点的有限集。当n = 0时，称为空树。在任意一棵非空树中应满足：

有且仅有一个特定的称为根的结点。

当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。

树天生适合递归。

树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。

树中所有结点可以有零个或多个后继。

结点：使用树结构存储的每一个数据元素都被称为“结点”。

父结点（双亲结点）、子结点和兄弟结点

孩子结点：结点的直接后继

双亲结点：结点的直接前驱

兄弟结点：同一双亲结点的孩子结点互称兄弟结点

树根结点（简称“根结点”）：每一个非空树都有且只有一个被称为根的结点。树根的判断依据为：如果一个结点没有父结点，那么这个结点就是整棵树的根结点。

叶子结点：如果结点没有任何子结点，那么此结点称为叶子结点（叶结点）

空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有结点。

树是由根结点和若干棵子树构成的。

对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（Degree）。如图度最大值为3

结点的层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。一棵树的深度（高度）是树中结点所在的最大的层次。

如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。

由 m（m >= 0）个互不相交的树组成的集合被称为森林。

结点的深度是从根结点开始自顶向下逐层累加的。 结点的高度是从叶结点开始自底向上逐层累加的。

树的高度和深度是树中结点的最大层数。

路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。

二叉树：有限的结点的集合，由根结点和不相交的二叉子树组成

二叉树是每个节点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

n个结点的树中有n-1条边

满足以下两个条件的树形结构叫做二叉树：

每个结点至多只有两棵子树

二叉树的子树有左右之分，其次序不能颠倒。树可以有序可以无序

树的性质

树具有以下基本性质：

1. 树的结点数公式

$ = + 1 $
解释：
每个结点的度数等于其孩子结点的个数，加上根结点，便是树中的总结点数。

2. 第 $i$ 层的结点数

性质： 度为 $m$ 的树中，第 $i$ 层至多有 $m^{i-1}$ 个结点。
推导：
- 每个结点的度均为 $m$，即每个结点最多有 $m$ 个子结点。

3. 高度为 $h$ 的 $m$-叉树的最大结点数

性质： 高度为 $h$ 的 $m$-叉树至多有
$ $
推导：
- 根据性质 2，第 $i$ 层至多有 $m^{i-1}$ 个结点。
- 高度为 $h$ 的 $m$-叉树的总结点数为：
$ S = m^0 + m^1 + m^2 + + m^{h-1} $
这是一个等比数列，求和得：
$ S = $
这种树称为满 $m$-叉树。

4. $n$ 个结点的 $m$-叉树的最小高度

性质： $n$ 个结点的 $m$-叉树的最小高度为：
$ h = _m(n(m-1) + 1) $
推导：
- 最小高度对应于每层结点数最多，即该树为完全 $m$-叉树。
- 根据性质 3，有：
$ n $
解得：
$ h _m(n(m-1) + 1) $
因此：
$ h = _m(n(m-1) + 1) $

其他推导：

实际上，结点数 $n$ 满足以下关系：
$ + 1 n $
所以最小高度也可表示为：
$ h = _m((n-1)(m-1) + 1) + 1 $

二叉树的性质

性质1：在二叉树的第i层上至多有2的(i-1)次方个结点（i>=1）。

性质2：深度为k的二叉树至多有2（k）-1次方个结点（k>=1）。

性质3：具有n个结点的完全二叉树的深度为|log2(n)| + 1

性质4：包含n个结点的二叉树的高度至少为log2 (n+1)。

性质5：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

n=n0+n1+n2

n=n1+2n2+1

即可

满二叉树与完全二叉树

满二叉树：每层结点均满，每层均具有最大结点数，又称完美二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

　　国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

　　国外(国际)定义:a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.大意为：如果一棵二叉树的结点要么是叶子结点，要么它有两个孩子结点，这样的树就是满二叉树。

1、第i+1层的节点数为2^i

2、如果完美二叉树高度为n，那么总的节点数为2^n - 1

3、如果完美二叉树中叶子节点为m，非终端节点为k，那么m=k+1

4、如果完美二叉树中某节点下标为n，那么它的左节点下标为2n，右节点下标为2n+1

完全二叉树：与满二叉树的编号对应，但不要求每层均具有最大结点数

完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

若一棵二叉树至多只有最下面两层的结点的度数可以小于2，并且最下层的结点都集中在该层最左边的若干位置上，则此二叉树为完全二叉树。

若i为奇数且i>1，那么tree[i]的左兄弟为tree[i-1]；

若i为偶数且i<n，那么tree[i]的右兄弟为tree[i+1]；

若i>n/2，那么tree[i]为叶子结点

若i<(n-1)/2，那么tree必有两个孩子

完全二叉树第i层至多有2^{(i-1)个节点，共i层的完全二叉树最多有2}i-1个节点。

区别于联系：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

二叉查找树，二叉搜索树、二叉排序树、BST

定义：二叉查找树(Binary Search Tree)，又被称为二叉搜索树。设x为二叉查找树中的一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。

在二叉查找树中： (01) 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； (02) 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； (03) 任意节点的左、右子树也分别为二叉查找树。 (04) 没有键值相等的节点（no duplicate nodes）。

斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1。

平衡二叉树必定是二叉搜索树。

霍夫曼树

带权路径最短的二叉树称为哈夫曼树或最优二叉树。

树的存储结构

顺序存储结构

链式存储结构

主要有：

<1> 双亲表示法 <2> 孩子表示法 <3> 孩子兄弟表示法

双亲表示法

采用一组连续空间来存储每个结点。

根节点没有双亲，所以其在数组中存储的值为-1。

其余的节点，只需要存储其父节点对应的数组下标即可

#define MaxSize 100  //树中最多结点数
typedef struct{  //树的结点定义
    char data;  //数据元素
    int parent;  //双亲位置域
}PTNode;

typedef struct{  //树的类型定义
    PTNode nodes[MaxSize];  //双亲表示
    int n;  //结点数
}PTree;

孩子表示法

将每个节点的孩子节点都用单链表连接起来形成一个线性结构，n个节点具有n个孩子链表。

// 孩子表示法
typedef int ElemType;
#define MAX_SIZE 100
typedef struct CNode
{
    int child;
    struct CNode *next;
}CNode;

typedef struct PNode
{
    ElemType data;
    struct CNode *child;
}PNode;

typedef struct CTree
{
    PNode nodes[MAX_SIZE];
    int n;
}CTree;

孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node *FirstChild;
    struct Node *NextBrother;
    
}Node,TREE;

二叉树的遍历

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树的定义是递归式的。因此后续基本操作中，我们基本都是按照该概念来实现的

四种主要的遍历思想为：

前序遍历：根结点 ---> 左子树 ---> 右子树

中序遍历：左子树---> 根结点 ---> 右子树

后序遍历：左子树 ---> 右子树 ---> 根结点

层次遍历：只需按层次遍历即可

//前置
//递归建树
#include <stdio.h>
#include <stdlib.h>
//结构体的封装
typedef struct BiTree{
    char data;
    struct BiTree *leftchild,*rightchild;
}BiTree;
//先序建立二叉树
void CreateTree(BiTree *&T){
    char x;
cin>>x;
    if(x=='#') T=NULL;
    else{
        T=new BiTree;
        T->data=x;
        CreateTree(T->leftchild);
        CreateTree(T->rightchild);
    }
}

先序遍历

void PreOrder(BiTree T){
	if(T != NULL){
		visit(T);	//访问根节点
		PreOrder(T->lchild);	//递归遍历左子树
		PreOrder(T->rchild);	//递归遍历右子树
	}
}

中序遍历

void InOrder(BiTree T){
	if(T != NULL){
		InOrder(T->lchild);	//递归遍历左子树
		visit(T);	//访问根结点
		InOrder(T->rchild);	//递归遍历右子树
	}
}


//力扣版本
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& res) {
        if (!root) {
            return;
        }
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
};

后序遍历

void PostOrder(BiTree T){
	if(T != NULL){
		PostOrder(T->lchild);	//递归遍历左子树
		PostOrder(T->rchild);	//递归遍历右子树
		visit(T);	//访问根结点
	}
}

层次遍历

void LevelOrder(BiTree T){
	InitQueue(Q);	//初始化辅助队列
	BiTree p;
	EnQueue(Q, T);	//将根节点入队
	while(!IsEmpty(Q)){	//队列不空则循环
		DeQueue(Q, p);	//队头结点出队
		visit(p);	//访问出队结点
		if(p->lchild != NULL){
			EnQueue(Q, p->lchild);	//左子树不空，则左子树根节点入队
		}
		if(p->rchild != NULL){
			EnQueue(Q, p->rchild);	//右子树不空，则右子树根节点入队
		}
	}
}

线索二叉树

#图解数据结构：轻松搞定线索二叉树 - 知乎 (zhihu.com)

（几乎完全抄袭）

背景来源：

在n个结点的二叉树中，必定有n+1个空链域（叶子结点的左右子树空间浪费了）

解释：

在N个节点的二叉树中，每个节点有2个指针，所以一共有2N个指针，除了根节点以外，每一个节点都有一个指针从它的父节点指向它，所以一共使用了N-1个指针，所以剩下2N-(N-1)也就是N+1个空指针；

二叉树的遍历，无论是递归还是非递归算法，效率都不算高。

而知道了“前驱”和“后继”信息，就可以把二叉树看作一个链表结构，从而可以像遍历链表那样来遍历二叉树，进而提高效率。线索化 ----引出

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

定义以下规则：

ltag=0，表示指向节点的左孩子。
ltag=1，则表示lchild为线索，指向节点的直接前驱**
rtag=0，表示指向节点的右孩子。
rtag=1，则表示rchild为线索，指向节点的直接后继**

这种指向前驱和后继的指针称为线索，加上了线索的二叉树就是线索二叉树；

typedef struct TBNode
{
	char data;
	int ltag,rtag;
	struct TBNode *lchild;
	struct TBNode *rchild;
	
}TBNode;

实现思路：按某种次序遍历二叉树，在遍历过程中用线索取代空指针即可。

中序线索二叉树

#include<iostream>
using namespace std;
typedef struct Thread {
	struct Thread* left_node, *right_node;//左右指针
	int data;//需要存放的数据
	/*默认0代表左右孩子 1代表前驱或者后继*/
	int left_type;//类型标志
	int right_type;//类型标志
}Node;
 
Node* pre;//前驱结点的变量
Node* head;//头指针 指向某种遍历的第一个结点
 
void inOrderThreadTree(Node* node)
{
	//如果当前结点为NULL 直接返回
	if (node == NULL) {
		return;
	}
	//先处理左子树
	inOrderThreadTree(node->left_node);
	if (node->left_node == NULL)
	{
		//设置前驱结点
		node->left_type = 1;
		node->left_node = pre;
	}
	//如果结点的右子节点为NULL 处理前驱的右指针
	if (pre !=NULL && pre->right_node == NULL)
	{
		//设置后继
		pre->right_node = node;
		pre->right_type = 1;
	}
	//每处理一个节点 当前结点是下一个节点的前驱
	pre = node;
	//最后处理右子树
	inOrderThreadTree(node->right_node);
}
 
void inOrderTraverse(Node* root)
{
	//从根节点开始先找到最左边
	if (root == NULL)
	{
		return;
	}
	Node* temp = root;
	//先找到最左边结点 然后根据线索化直接向右遍历
	while (temp != NULL && temp->left_type == 0)
	{
		temp = temp->left_node;
	}
	while (temp != NULL)
	{
		//输出
		temp = temp->right_node;
	}
 
}

树二叉树的转化

树转换为二叉树

树转换为二义树的规则:每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟，所以对应的二叉树没有右子树。

森林实际同理，只是把每一颗树当成兄弟，除此无别

树的遍历

树的遍历的定义：以某种方式访问树中的每一个结点，且仅访问一次。树的遍历主要有先根遍历和后根遍历。

先根遍历：若树非空，则先访问根结点，再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。

后根遍历：若树非空，则按照从左到右的顺序遍历根结点的每一棵子树，之后再访问根结点。其访问顺序与这棵树对应的二叉树的中序遍历顺序相同。

二叉搜索树

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树。二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：

非空左子树的所有键值小于其根结点的键值。
非空右子树的所有键值大于其根结点的键值。
左、右子树都是二叉搜索树。

结构

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree; /* 二叉树类型 */
struct TNode{ /* 树结点定义 */
    ElementType Data; /* 结点数据 */
    BinTree Left;     /* 指向左子树 */
    BinTree Right;    /* 指向右子树 */
};

查找

递归版本

Position Find( ElementType X, BinTree BST )
{
	if( !BST ) return NULL; /*查找失败*/
	if( X > BST->Data )
		return Find( X, BST->Right ); /*在右子树中继续查找*/
	else if( X < BST->Data )
		return Find( X, BST->Left ); /*在左子树中继续查找*/
	else /* X == BST->Data */
		return BST; /*查找成功，返回结点的找到结点的地址*/
}

非递归版本

Position IterFind( ElementType X, BinTree BST )
{
	 while( BST ) 
	 {
		 if( X > BST->Data )
		 	BST = BST->Right; /*向右子树中移动，继续查找*/
		 else if( X < BST->Data )
		 	BST = BST->Left; /*向左子树中移动，继续查找*/
		 else /* X == BST->Data */
		 	return BST; /*查找成功，返回结点的找到结点的地址*/
	 }
	 return NULL; /*查找失败*/
}

查找最小值

Position FindMin( BinTree BST )
{
	 if( !BST ) 
	 	return NULL; /*空的二叉搜索树，返回NULL*/
	 else if( !BST->Left )
	 	return BST; /*找到最左叶结点并返回*/
	 else
	 	return FindMin( BST->Left ); /*沿左分支继续查找*/
}

查找最大值

Position FindMax( BinTree BST )
{
	 if(BST )
	 	while( BST->Right )  /*沿右分支继续查找，直到最右叶结点*/
	 		BST = BST->Right;
	 return BST;
}

插入：二叉搜索树在插入前，肯定要找到插入的位置。

BinTree Insert( BinTree BST, ElementType X )
{
    if( !BST ){ /* 若原树为空，生成并返回一个结点的二叉搜索树 */
        BST =new TNode;
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    else { /* 开始找要插入元素的位置 */
        if( X < BST->Data )
            BST->Left = Insert( BST->Left, X );   /*递归插入左子树*/
        else  if( X > BST->Data )
            BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/
        /* else X已经存在，什么都不做 */
    }
    return BST;
}

删除：

BinTree Delete( BinTree BST, ElementType X ) 
{ 
    Position Tmp; 
    if( !BST ) 
        printf("要删除的元素未找到"); 
    else {
        if( X < BST->Data ) 
            BST->Left = Delete( BST->Left, X );   /* 从左子树递归删除 */
        else if( X > BST->Data ) 
            BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
        else 
        { /* BST就是要删除的结点 */
            /* 如果被删除结点有左右两个子结点 */ 
            if( BST->Left && BST->Right ) 
            {
                /* 从右子树中找最小的元素填充删除结点 */
                Tmp = FindMin( BST->Right );
                BST->Data = Tmp->Data;
                /* 从右子树中删除最小元素 */
                BST->Right = Delete( BST->Right, BST->Data );
            }
            else 
            { /* 被删除结点有一个或无子结点 */
                //想象一下，如果删除的结点原来相对于父结点是左子树，而且它只有一个孩子结点，那这个孩子结点是不是一定会比当前结点的父亲结点小
                //同理，如果删除的结点原来相对于父结点是右子树，那么则大，因此直接指向子结点就是对的
                Tmp = BST; 
                if( !BST->Left )       /* 只有右孩子或无子结点 */
                    BST = BST->Right; 
                else                   /* 只有左孩子 */
                    BST = BST->Left;
                delete Tmp ;
            }
        }
    }
    return BST;
}

总结为：对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。因此取决于二叉搜索树的形状，不能太极端，不然无法近似为二分，因此我们希望构建出一颗平衡二叉树。

平衡二叉树

二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，很容易使得二叉树退化成单链表，搜索效率降低为 O(n)。

毫无疑问

保持树的左右两端保持平衡，树的查找效率最高。

调平衡

平衡因子

定义：某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于 1 的节点。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。

实际上只有LL和RR

结点结构

typedef struct AVLNode *Tree;
typedef int ElementType;
struct AVLNode{
    int depth; //深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡
    Tree parent; //该结点的父节点
    ElementType val; //结点值
    Tree lchild;
    Tree rchild;
    AVLNode(int val=0) {
        parent = NULL;
        depth = 0;
        lchild = rchild = NULL;
        this->val=val;
    }
};

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。

根据旋转的方向有两种处理方式，左旋 与 右旋 。

LL	在 A 的左子树根节点的左子树上插入节点而破坏平衡	右旋转
RR	在 A 的右子树根节点的右子树上插入节点而破坏平衡	左旋转
LR	在A的左子树根节点的右子树上插入节点而破坏平衡	先左旋后右旋
RL	在 A 的右子树根节点的左子树上插入节点而破坏平衡	先右旋后左旋

右旋

（1）将失衡结点变为其左孩子的右孩子（2）将其原本的左孩子的右孩子变为的左孩子

左旋

（1）将失衡结点变为其右孩子的左孩子（2）将其原本的右孩子的左孩子变为的右孩子

总结：

1.RR型和LL型，以被破坏节点为基础进行其反向的旋转即可，即RR型进行左旋，LL型进行右旋。

2.RL型和LR型，先以被破坏节点的LR或RL首字母的节点进行LR或RL首字母旋转，再以被破坏节点为基础进行LR或RL尾字母旋转，即RL型先以被破坏节点的R（右）节点为基础进行一次R（右）选，再以被破坏节点为基础进行一次L（左）旋；LR旋先以被破坏节点的L（左）节点为基础进行一次L（左）选，再以被破坏节点为基础进行一次R（右）旋。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>

typedef int ElenmentType; 
//平衡二叉树的结构 
typedef struct AVLNode{
	int depth;//深度
	struct AVLNode *left;
	struct AVLNode *right;
	struct AVLNode *parent;
	ElenmentType value; 
	//构造器 
	AVLNode(ElenmentType value=0){
		parent = NULL;
        depth = 0;
        left = right = NULL;
        this->value=value;
	}
}AVLtree,Tree;
//LL型调整函数
//返回根结点
Tree* LL_rotate(Tree *root){//LL执行右旋 
	//root是原来的平衡二叉树的根结点
	Tree *temp;//临时变量
	
	//获取根结点的左孩子
	temp = root->left;
	//根结点的左孩子变更为其原来左孩子的右孩子
	root->left = temp->right;
	
	//原来的根结点的左孩子变为了根结点
	temp->right = root;
	return temp; 
   
}
//RR型调整函数
//返回根结点 
Tree* RR_rotate(Tree * root){//RR执行左旋 
    Tree* temp;
    temp = root->right;//获取根结点的右孩子 
    root->right = temp->left;//根结点的右孩子变为其原来右孩子的左孩子 
    temp->left = root;//原来的根结点的右孩子变为了新的根结点 
    return temp;
}
//1、LR型，先左旋转，再右旋转
//返回：新父节点
Tree* LR_rotate(Tree* root){
	 Tree* temp;
	 temp = root->left;
    root->left =RR_rotate(temp);
    return LL_rotate(root);
} 
//2RL型，先右旋转，再左旋转
//返回:新父节点
Tree* RL_rotate(Tree* root){
	 Tree* temp;
	 temp = root->right;
    root->right=LL_rotate(temp);
    return RR_rotate(root);
} 

//树高
int height(const Tree* root)//求树高，递归 
{
    if (root == NULL)
        return 0;
    return std::max(height(root->left) , 
	
	height(root->right)) + 1;
}
//平衡因子
int diff(const Tree* root)//求平衡因子，即当前节点左右子树的差
{
    return height(root->left) - height(root->right);
}

//平衡操作
Tree* Balance(Tree* root)
{
	//	printf("平衡函数");
    int balanceFactor = diff(root);//diff用来计算平衡因子（左右子树高度差）
    if (balanceFactor > 1)//左子树高于右子树
    {
        if (diff(root->left) > 0)//LL的情况 
            root=LL_rotate(root);
        else//LR的情况 
            root=LR_rotate(root);
    }
    else if (balanceFactor < -1)//右子树高于左子树
    {
        if (diff(root->right) > 0)//RL的情况 
            root=RL_rotate(root);
        else//RR的情况 
            root=RR_rotate(root);
    }
    return root;
} 
//插入结点
Tree* Insert(Tree* root,ElenmentType k )
{
    if (NULL == root)
    {
        root = new AVLNode(k);//如果根结点为null，则直接将值为根结点 
        if(root==NULL)
        	printf("创建失败");
        return root;
    }//递归返回条件
    else if (k < root->value)
    {
        root->left = Insert(root->left, k);//递归左子树
        //balance operation
        root = Balance(root);//平衡操作包含了四种旋转
    }
    else if (k>root->value)
    {
        root->right = Insert(root->right, k);//递归右子树
        //balance operation
        root = Balance(root);//平衡操作包含了四种旋转
    }
    return root;
} 
//中序遍历,获取的数列是有序的 
void displayTree(Tree* node){
        if(node == NULL) return;
 
        if(node->left != NULL){
                displayTree(node->left);
        }
 
        printf("%d ",node->value);
 
        if(node->right != NULL){
                displayTree(node->right);
        }
}
//查找value，成功则返回该结点 
Tree* binaryTreeSearch(Tree *node,int value){
	if(node->value==value)
		return node;
	else if(node->value>value){
		if(node->left!=NULL)
			return binaryTreeSearch(node->left,value);
		else return NULL;
	}else{
		if(node->right!=NULL)
			return binaryTreeSearch(node->right,value);
		else
			return NULL;
	}
}

哈夫曼树

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。

通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

节点的权和带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

树的路径长度：从树根到每一个结点的路径长度之和．记作：TL

树的的带权路径长度：树中所有叶子结点的带权路径长度之和．记作:WPL(Weighted Path Length)

WPL 最小的二叉树 称为 霍夫曼树（Huffman Tree）。

哈夫曼算法

（１）根据n个给定的权值构成n棵二叉树的森林，森林中每一棵树只有一个带权的根结点（构造森林全是根）

（２）在森林中，选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根结点的权值之和．（选用两小造新树）

（３）在森林中删除这两棵树，同时将新得到的二叉树加入到森林中．（删除两小添新人）

（４）重复（２）和（３），直到森林中只有一棵树为止，这棵树即为哈夫曼树．（重复２，３剩单根）

为哈夫曼树进行编码

将二叉树分支中的左分支编为 0，右分支编为 1：

可以发现每个字符都在树的叶子节点上，因此要获取每个字符的哈夫曼编码，就通过根节点遍历到对应的子节点所经历的路径就是这个字符的编码：

代码

对于未建好的霍夫曼树，直接求其 WPL

int getWPL(int arr[], int n) {  // 对于未建好的霍夫曼树，直接求其 WPL
  priority_queue<int, vector<int>, greater<int>> huffman;  // 小根堆
  for (int i = 0; i < n; i++) huffman.push(arr[i]);

  int res = 0;
  for (int i = 0; i < n - 1; i++) 
  {
    int x = huffman.top();
    huffman.pop();
    int y = huffman.top();
    huffman.pop();
    int temp = x + y;
    res += temp;
    huffman.push(temp);
  }
  return res;
}

构建哈夫曼树

排序

哈夫曼树是一个带权的二叉树，而在哈夫曼编码中，字符的出现频率就是字符的权重。因此要根据字符的频率放入优先队列中进行排序。然后根据这些字符构建一棵哈夫曼树。

将队列中的每一个元素都看成一棵树。

合并

进行迭代，每次都去除队列中的前面两个元素，也就是权值最小的两棵子树进行合并成一棵子树。直到最终所有的元素合并成一棵树。这棵树就是哈夫曼树。

为哈夫曼树进行编码

将二叉树分支中的左分支编为 0，右分支编为 1：

霍夫曼树 - OI Wiki (oi-wiki.org)

typedef struct HNode {
  int weight;
  HNode *lchild, *rchild;
} * Htree;

Htree createHuffmanTree(int arr[], int n) {
  Htree forest[N];
  Htree root = NULL;
  for (int i = 0; i < n; i++) {  // 将所有点存入森林
    Htree temp;
    temp = new HNode;
    temp->weight = arr[i];
    temp->lchild = temp->rchild = NULL;
    forest[i] = temp;
  }
/*
在每次循环中，动态分配了一个 HNode 类型的结构体，并将其权重初始化为数组 arr[] 的第 i 个元素，左右子节点指针初始化为 NULL。然后将该结构体的指针赋值给 forest[i]。
*/
    
  for (int i = 1; i < n; i++) {  // n-1 次循环建哈夫曼树
    int minn = -1, minnSub;  // minn 为最小值树根下标，minnsub 为次小值树根下标
    for (int j = 0; j < n; j++) {
      if (forest[j] != NULL && minn == -1) {
        minn = j;
        continue;
      }
      if (forest[j] != NULL) {
        minnSub = j;
        break;
      }
    }
      /*
      这段代码的目的是初始化两个变量 minn 和 minnSub，以便后续在森林中找到权重最小和次小的两颗树。
      */

    for (int j = minnSub; j < n; j++) {  // 根据 minn 与 minnSub 赋值
      if (forest[j] != NULL) {
        if (forest[j]->weight < forest[minn]->weight) {
          minnSub = minn;
          minn = j;
        } else if (forest[j]->weight < forest[minnSub]->weight) {
          minnSub = j;
        }
      }
    }
      /*
      for (int j = minnSub; j < n; j++) {  // 根据 minn 与 minnSub 赋值
开始一个循环，从 minnSub 开始遍历 forest 数组中的剩余元素。


if (forest[j] != NULL) {
在每次循环中，首先检查当前位置的 forest[j] 是否不为 NULL。


if (forest[j]->weight < forest[minn]->weight) {
  minnSub = minn;
  minn = j;
}
如果当前位置的树的权重小于 minn 所指示的树的权重，那么将 minnSub 更新为 minn，表示原来的 minn 变成了次小的树，然后将 minn 更新为 j，表示当前的树是最小的树。


else if (forest[j]->weight < forest[minnSub]->weight) {
  minnSub = j;
}
否则，如果当前位置的树的权重小于 minnSub 所指示的树的权重，那么将 minnSub 更新为 j，表示找到了比当前 minnSub 指示的树更小的树。

这段代码的目的是在剩余的非空树中找到权重最小和次小的两颗树，并将它们的下标分别存储在 minn 和 minnSub 中。
*/
      
      
      

    // 建新树
    root = new HNode;
    root->weight = forest[minn]->weight + forest[minnSub]->weight;
    root->lchild = forest[minn];
    root->rchild = forest[minnSub];

    forest[minn] = root;     // 指向新树的指针赋给 minn 位置
    forest[minnSub] = NULL;  // minnSub 位置为空
  }
  return root;
}

计算构成霍夫曼树的 WPL

typedef struct HNode {
  int weight;
  HNode *lchild, *rchild;
} * Htree;

int getWPL(Htree root, int len) {  // 递归实现，对于已经建好的霍夫曼树，求 WPL
  if (root == NULL)
    return 0;
  else {
    if (root->lchild == NULL && root->rchild == NULL)  // 叶节点
      return root->weight * len;
    else {
      int left = getWPL(root->lchild, len + 1);
      int right = getWPL(root->rchild, len + 1);
      return left + right;
    }
  }
}

对于给定序列，计算霍夫曼编码

typedef struct HNode {
  int weight;
  HNode *lchild, *rchild;
} * Htree;

void huffmanCoding(Htree root, int len, int arr[]) {  // 计算霍夫曼编码
  if (root != NULL) {
    if (root->lchild == NULL && root->rchild == NULL) {
     cout<<"结点为"<<root->weight<<"的字符的编码为: ";
      for (int i = 0; i < len; i++) printf("%d", arr[i]);
    cout<<'/n';
    } else {
      arr[len] = 0;
      huffmanCoding(root->lchild, len + 1, arr);
      arr[len] = 1;
      huffmanCoding(root->rchild, len + 1, arr);
    }
  }
}

图

图论（Graph Theory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些实体之间的某种特定关系，用点代表实体，用连接两点的线表示两个实体间具有的某种关系。图是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

图的定义：

一个图（Graph）G是一个有序对(G,V)，其中V是一些顶点的集合，G是一个连接这些顶点的边的集合。边可以是有向的（连接两个顶点的有序对）或者是无向的（连接两个顶点的无序对）。

顶点和边：

图中的每个元素称为顶点（Vertex），通常用字母表示，如V、W、X等。
顶点之间的连接称为边（Edge），它可以是有向的或者是无向的。

图可以被表示为 G={V, E}，其中 V={v1, ... , vN}，E= {e1, ... , eM}。

V表示图G中顶点的个数，也称图G的阶

E代表图G边的条数

图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空

图可能是无向的，这意味着图中的边在连接顶点时无需区分方向。否则，称图是有向的

有向图和无向图：

如果图中的边具有方向，则称该图为有向图（Directed Graph）。

如果图中的边没有方向，则称该图为无向图（Undirected Graph）。

路径和环：

路径（Path）是图中连接顶点的一个序列，其中顶点之间通过边相连。
环（Cycle）是指图中的一个路径，起始顶点和结束顶点相同。
若一个图有n个顶点，并且有大于n − 1条边，则此图一定有环。
简单路径是指图中不包含重复顶点的路径
简单路径满足以下条件：
1. 顶点不重复：路径中的所有顶点各不相同。
2. 边不重复：路径中的所有边各不相同。
简单回路（简单环）：除路径起点和终点相同外，其余顶点均不相同的路径。

树：

如果一个无向图是一个连通图且没有环，则称该图为树（Tree）。
树是一种特殊的图结构，它没有回路，并且任意两个顶点之间只有一条简单路径。

子图：

子图（Subgraph）是原始图的一个子集，它包含原始图中的一些顶点和边，这些顶点和边之间的连接关系和方向（如果是有向图）保持不变。
例如，如果原始图有5个顶点和7条边，而子图中只选择了其中的3个顶点和5条边，那么这个子图就是原始图的一个子图。

生成子图：

如果一个子图包含了原始图中的所有顶点，那么这个子图被称为原始图的生成子图（Spanning Subgraph）。
生成子图通常是指包含了原始图中所有顶点的最小连通子图，如果是无向图，通常是最小生成树。

图的连通性：在图论中，连通图基于连通的概念。在一个无向图 G 中，若从顶点 i 到顶点 j 有路径相连（当然从j到i也一定有路径），则称 i 和 j 是连通的。如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。图的连通性是图的基本性质。

连通：

在一个图中，如果任意两个顶点之间都存在路径，那么该图被称为是连通的。换句话说，对于图中的任意两个顶点u和v，都存在一条从顶点u到顶点v的路径。如果一个图不是连通的，则被称为是非连通的。

在上图中，图是连通的，因为任意两个顶点之间都存在路径。例如，顶点A和顶点E之间存在路径A -> B -> C -> E。

连通图：

如果一个图是连通的，即图中的任意两个顶点之间都存在路径，那么该图被称为是连通图。换句话说，一个图是连通图，当且仅当该图是一个连通的子图，即该图包含原始图中的所有顶点，并且顶点之间的连接关系和方向（如果是有向图）保持不变。

上图中的图是一个非连通图，因为它包含了两个不连通的子图：左侧的子图包含了顶点A、B、C，右侧的子图包含了顶点D、E、F。

A---B    D---E
  |  /       /
  | /         /
  C            F

连通分量：

在一个非连通图中，如果将该图分解为多个连通子图，且每个子图都是连通的，那么这些连通的子图被称为是该图的连通分量。换句话说，连通分量是将一个非连通图分割为连通子图的过程，其中每个连通子图都是极大连通子图（即无法再添加顶点或边使得其保持连通性）。

A---B    D---E
|           /
|            /
C             F

上图中的非连通图被分解为了两个连通分量：左侧的连通分量包含了顶点A、B、C，右侧的连通分量包含了顶点D、E、F。

无权图和有权图

连接节点与节点的边是否有数值与之对应，有的话就是有权图，否则就是无权图。 无权图（Unweighted Graph）： - 无权图是指图中的边没有赋予任何权重或者成本的图。 - 在无权图中，边只表示顶点之间的连接关系，而不包含额外的信息。 - 通常用于表示简单的关系或者连接情况，例如社交网络中的好友关系图。 有权图（Weighted Graph）： - 有权图是指图中的边具有特定的权重或者成本的图。 - 在有权图中，每条边都被赋予了一个权重值，表示连接两个顶点之间的成本、距离或者其他衡量标准。 - 有权图可以用于模拟现实世界中的各种情况，例如道路网络中的距离、通信网络中的传输延迟等。

生成树（Spanning Tree）：

一个连通图的生成树是指一个包含图中所有顶点且无环的子图。
换句话说，生成树是一个树形结构，它包含了图中所有的顶点，并且用最少的边来连接所有的顶点，从而保持图的连通性。
如果一个图是连通的，则一定存在至少一棵生成树。而对于非连通图，可以通过计算每个连通分量的生成树来得到整个图的生成树。

度

顶点的度（Degree）：顶点的度是指与该顶点相邻的边的数量。对于无向图来说，顶点的度等于与该顶点相邻的边的数量；对于有向图来说，顶点的度等于该顶点的出度和入度之和。
出度（Out-degree）：对于有向图中的一个顶点，其出度是指从该顶点出发的边的数量。换句话说，出度表示了从该顶点指向其他顶点的边的数量。
入度（In-degree）：对于有向图中的一个顶点，其入度是指指向该顶点的边的数量。换句话说，入度表示了指向该顶点的边的数量。在有向图中，顶点的度可以进一步分为出度和入度，这是因为有向图中的边具有方向性，从而导致了边的起点和终点的区别。而在无向图中，顶点的度只有一个值，即与该顶点相邻的边的数量。

对于无向图中的一个顶点，其度等于与该顶点相邻的边的数量。

对于有向图中的一个顶点，其出度等于从该顶点出发的边的数量，入度等于指向该顶点的边的数量。

稠密图、稀疏图

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图G满足∣ E ∣ < ∣ V ∣ l o g ∣ V ∣时，可以将G视为稀疏图。其他一些知识

完全图：完全是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。

自环边：一条边的起点终点是一个点。

平行边：两个顶点之间存在多条边相连接。

简单图：一个图G若满足:①不存在重复边;②不存在顶点到自身的边，则称图G为简单图。

多重图

若图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图。

图的存储结构

直接存边

方法

使用一个数组来存边，数组中的每个元素都包含一条边的起点与终点（带边权的图还包含边权）。（或者使用多个数组分别存起点，终点和边权。）

struct Edge {
  int u, v;
};

int n, m;
vector<Edge> e;

 for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v;

邻接矩阵

方法

使用一个二维数组 adj 来存边，其中 adj[u][v] 为 1 表示存在到的边，为 0 表示不存在。如果是带边权的图，可以在 adj[u][v] 中存储到的边的边权。

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<vector<bool> > adj;

bool find_edge(int u, int v) { return adj[u][v]; }

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int v = 1; v <= n; ++v) {
    if (adj[u][v]) {
      dfs(v);
    }
  }
}

int main() {
  cin >> n >> m;

  vis.resize(n + 1, false);
  adj.resize(n + 1, vector<bool>(n + 1, false));

  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u][v] = true;
  }

  return 0;
}

//双向有权
 void add(int u, int v, int w)
{
    mat[u][v] = w;
    mat[v][u] = w;
}

邻接矩阵只适用于没有重边（或重边可以忽略）的情况。

其最显著的优点是可以 O(1)查询一条边是否存在。

由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。

如果有权值没有边的就不能设置为0，而是应该设置为无穷参数

邻接表

方法

使用一个支持动态增加元素的数据结构构成的数组，如 vector<int> adj[n + 1] 来存边，其中 adj[u] 存储的是点 u的所有出边的相关信息（终点、边权等)。

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<vector<int> > adj;

bool find_edge(int u, int v) {
  for (int i = 0; i < adj[u].size(); ++i) {
    if (adj[u][i] == v) {
      return true;
    }
  }
  return false;
}

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int i = 0; i < adj[u].size(); ++i) dfs(adj[u][i]);
}

int main() {
  cin >> n >> m;

  vis.resize(n + 1, false);
  adj.resize(n + 1);

  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
  }

  return 0;
}

如果有权值，即是

struct Edge
{
    int to, w;
};
vector<Edge> edges[MAXN];
void add(int from, int to, int w)
{
    Edge e = {to, w};
    edges[from].push_back(e);  //向vector的最后添加一条边
}
//无向图
void add2(int u, int v, int w)
{
    add(u, v, w);
    add(v, u, w);
}

链式前向星

逃避了很久这个东西，终究还是逃不过了（）

链式前向星--最通俗易懂的讲解-CSDN博客

讲的很好，一看就很清晰了。

void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权
{
    edge[cnt].to = v; //终点
    edge[cnt].w = w; //权值
    edge[cnt].next = head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[u] = cnt++;//更新以u为起点上一条边的编号
}

比如说我们

1 2 1

1 3 5

1 5 6

这三条边，他们出现的顺序依次是0，3，5

那么我们head[1]就从一开始的-1---0---3----5

最后我们得到的就是从5，开始的

而5的next就是3

3的next就是0

0的next就是-1，也就是我们的遍历的终止条件。

感觉链式前向星就是邻接表的静态版本，也就是为什么快的原因

遍历方式——————

for(int i = 1; i <= n; i++)//n个起点
    {
        cout << i << endl;
        for(int j = head[i]; j != -1; j = edge[j].next)//遍历以i为起点的边
        {
            cout << i << " " << edge[j].to << " " << edge[j].w << endl;
        }
        cout << endl;
    }

感谢那位大佬，讲的真的好。

图的遍历

【深基18.例3】查找文献

题目描述

小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小 K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。

假设洛谷博客里面一共有 n篇文章（编号为 1 到 n）以及 m 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。

请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。

样例输出 #1

1 2	1 2 5 6 3 7 8 4 1 2 3 4 5 6 7 8

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
vector< int >g[1000000];
bool visit[10000000];
int n, m;
int u, v;
void dfs(int x, int cur)
{
	visit[x] = 1;
	cout << x<<" ";
	if (cur==n)
	{
		return;
	}
	for (int i = 0; i < g[x].size(); i++)
	{
		if (!visit[g[x][i]])
		{
			dfs(g[x][i], cur + 1);
		}
	}
}
queue<int>q;
void bfs(int x)
{
	memset(visit, 0, sizeof(visit));
	visit[x] = 1;
	q.push(x);
	while (!q.empty())
	{
		int v = q.front();
		q.pop();
		cout << v << ' ';
		for (int i = 0; i < g[v].size(); i++)
		{
			if (!visit[g[v][i]])
			{
				visit[g[v][i]] = 1;
				q.push(g[v][i]);
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <=m ; i++)
	{
		cin >> u >> v;
		g[u].push_back(v);
	}
	for (int i = 1; i <=n ; i++)
	{
		sort(g[i].begin(), g[i].end());
	}
	dfs(1, 0);
	cout << '/n';
	bfs(1);
	return 0;
}

最小生成树

如果一个无向连通图不包含回路(连通图中不存在环),那么就是一个树。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

prim(普里姆算法)

Prim算法是采用从点方面考虑来构建MST的一种算法，Prim 算法在稠密图中比Kruskal优，通常步骤如下

1.从源点出发，将所有与源点连接的点加入一个待处理的集合中 2.从集合中找出与源点的边中权重最小的点，从待处理的集合中移除标记为确定的点 3.将找到的点按照步骤1的方式处理 4.重复2，3步直到所有的点都被标记

#include <iostream>
#include <algorithm>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 505;

int a[maxn][maxn];

int vis[maxn],dist[maxn];

int n,m;

int u,v,w;

long long sum = 0;

int prim(int pos) {
	dist[pos] = 0;
	// 一共有 n 个点,就需要 遍历 n 次,每次寻找一个权值最小的点,记录其下标
	for(int i = 1; i <= n; i ++) {
		int cur = -1;
		for(int j = 1; j <= n; j ++) {
			if(!vis[j] && (cur == -1 || dist[j] < dist[cur])) {
				cur = j;
			}
		}
		// 这里需要提前终止
		if(dist[cur] >= INF) return INF;
		sum += dist[cur];
		vis[cur] = 1;
		for(int k = 1; k <= n; k ++) {
		    // 只更新还没有找到的最小权值
			if(!vis[k]) dist[k] = min(dist[k],a[cur][k]);
		}
	}
	return sum;
}

int main(void) {
	cin>>n>>m;
	memset(a,0x3f,sizeof(a));
	memset(dist,0x3f,sizeof(dist));
	for(int i = 1; i <= m; i ++) {
		cin>>u>>v>>w;
		a[u][v] = min(a[u][v],w);
		a[v][u] = min(a[v][u],w);
	}
	int value = prim(1);
	if(value >= INF) puts("impossible");
	else cout<<sum;
	return 0;
}

kruskal (克鲁斯卡尔算法)

一种巧妙利用并查集来求最小生成树的算法。

对于图G(V,E)，以下是算法描述：

输入：图G 输出：图G的最小生成树具体流程： (1)将图G看做一个森林，每个顶点为一棵独立的树 (2)将所有的边加入集合S，即一开始S = E (3)从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E' (4)重复(3)直到所有点属于同一棵树，边集E'就是一棵最小生成树

#include < bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10; 

struct node {
	int x,y,z;
}edge[maxn];

bool cmp(node a,node b) {
	return a.z < b.z;
}

int fa[maxn];

int n,m;

int u,v,w; 

long long sum;

int get(int x) {
	return x == fa[x] ? x : fa[x] = get(fa[x]);
}

int main() {
	cin>>n>>m;
	for(int i = 1; i <= m; i ++) {
		cin>>edge[i].x>>edge[i].y>>edge[i].z);
	}
	for(int i = 0; i <= n; i ++) {
		fa[i] = i;
	}
	sort(edge + 1,edge + 1 + m,cmp);
	// 每次加入一条最短的边
	for(int i = 1; i <= m; i ++) {
		int x = get(edge[i].x);
		int y = get(edge[i].y);
		if(x == y) continue;
		fa[y] = x;
		sum += edge[i].z;
	}
	int ans = 0;
	for(int i = 1; i <= n; i ++) {
		if(i == fa[i]) ans ++;
	}
	if(ans > 1) puts("impossible");
	else cout<<sum;
	return 0;
}

最短路径

Dijkstra算法

Dijkstra 算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法，时间复杂度 O(n2)

什么是dijkstra?

1.算法介绍

Dijkstra算法通常是求解单源最短路中最快的算法，但它无法处理存在负权边的情况。Dijkstra本质上是一种贪心算法，通过不断调整每个点的“当前距离”最终得到最优结果，

dijkstra的算法思想是从以上最短距离数组中每次选择一个最近的点，将其作为下一个点，然后重新计算从起始点经过该点到其他所有点的距离，更新最短距离数据。已经选取过的点就是确定了最短路径的点，不再参与下一次计算。

堆优化找最短路径的过程

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int ,int>
const int INF=1e10;
const int N=1000010;
int n,m,s;
int dis[N];
int vis[N];
vector<PII>E[N];
void dj(int s)
{
	for(int i=1;i<=n;i++)
	{
		dis[i]=INF;
		vis[i]=0;
	}
	dis[s]=0;
	priority_queue<PII,vector<PII>,greater<PII> >q;
	q.push({0,s});
	while(!q.empty())
{
int t=q.top().second;
	q.pop();
		if(vis[t]){
			continue;
		}
		vis[t]=1;		
	for(int i=0,l=E[t].size();i<l;i++)
	{
		int v=E[t][i].first;
		int w=E[t][i].second;
	
		if(dis[v]>dis[t]+w)
		{		
			dis[v]=dis[t]+w;
			q.push({dis[v],v});
		}
		}	
	}	
}
int main()
{
cin>>n>>m>>s;
int u,v,w;
for(int i=0;i<m;i++)
{
	cin>>u>>v>>w;
	E[u].push_back({v,w});
	}	
	dj(s);
	for(int i=1;i<=n;i++)
	{
		cout<<dis[i]<<" ";
	}
	return 0;
	
}

Floyd算法

Floyd算法是基于动态规划的，从结点 i 到结点 j 的最短路径只有两种： 1、直接 i 到 j 2、i 经过若干个结点到 k 再到 j 对于每一个k，我们都判断 d[i][j] 是否大于 d[i][k] + d[k][j]，如果大于，就可以更新d[i][j]了。

void floyd()
{
 for(int k=1; k<=n; k++)
   for(int i=1; i<=n; i++)
     for(int j=1; j<=n; j++)
      d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

拓补排序

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。

有向无环图（DAG）才有拓扑排序

步骤：

从 DAG 图中选择一个没有前驱（即入度为0）的顶点并输出。

从图中删除该顶点和所有以它为起点的有向边。

重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

一个有向无环图可以有一个或多个拓扑排序序列

//by dpcc
//世间温柔
//不过是芳春柳摇染花香
//槐序蝉鸣入深巷
//白茂叶落醉故乡
#include<bits/stdc++.h>
using namespace std;
using ll=long long ;
#define re register
#define in inline
#define rep(i,a,n)  for(re int i=a;i<=n;i++)
#define frep(i,a,n) for(re int i=a;i>=n;i--)
int n;
vector<int>a[110];
int du[110];
int b[110];
int n2;
inline void bfs()
{
	queue<int>q;
rep(i,1,n)
{
	if(!du[i])
{
	q.push(i);

	}
		}			
while(!q.empty())
{
	int x=q.front();
	b[++n2]=x;
	q.pop();
	int t=a[x].size()-1;
	rep(i,0,t)
	{
	du[a[x][i]]--;
	if(!du[a[x][i]])
	{
		q.push(a[x][i]);
	}
	}	
}	
frep(i,n2,1)
{
	cout<<b[i]<<' ';
}
}
signed main()
{
cin>>n;
rep(i,1,n)
{
	int t;
	cin>>t;
	while(t!=0)
	{
	a[t].push_back(i);
		du[i]++;
		cin>>t;
	}
	}		
bfs();
return 0;
}

查找

一、查找的基本概念 查找定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

查找表(Search Table)：是由同一类型的数据元素(或记录)构成的集合。

关键字(Key)：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

静态查找表(Static Search Table)：只作查找操作的查找表。 动态查找表(Dynamic Search Table)：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。

平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

　　对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。　　Pi：查找表中第i个数据元素的概率。　　Ci：找到第i个数据元素时已经比较过的次数。

顺序查找

//顺序查找
int SequenceSearch(int a[], int value, int n)
{
    int i;
    for(i=0; i<n; i++)
        if(a[i]==value)
            return i;
    return -1;
}

O（N）

二分查找

元素必须是有序的，如果是无序的则要先进行排序操作。

折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

int BinarySearch1(int a[], int value, int n)
{
    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}



int binary_search(int start, int end, int key) {
  int ret = -1;  // 未搜索到数据返回-1下标
  int mid;
  while (start <= end) {
    mid = start + ((end - start) >> 1);  // 直接平均可能会溢出，所以用这个算法
    if (arr[mid] < key)
      start = mid + 1;
    else if (arr[mid] > key)
      end = mid - 1;
    else {  // 最后检测相等是因为多数搜索情况不是大于就是小于
      ret = mid;
      break;
    }
  }
  return ret;  // 单一出口
}

插值查找

背景：

当我们从字典中查找 “apple” 这个单词的时候，我们肯定不会傻傻地像二分查找一样首先从中间开始。相反，**我们会从首字母为 a 的地方开始查找。

插值查找是一种在有序数组（前提条件）中查找某一特定元素的查找算法。插值查找基于二分查找，不同的是插值查找每次从自适应mid处开始查找，提高查找效率。

归根到底只是Mid不同罢了

插值查找的平均复杂度为 Θ(log⁡log⁡n) ，

//插值查找
int InsertionSearch(int a[], int value, int low, int high)
{
    int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return InsertionSearch(a, value, low, mid-1);
    if(a[mid]<value)
        return InsertionSearch(a, value, mid+1, high);
}

（1）对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找时速度较快。（2）在关键字分布不均匀的情况下，插值查找不一定比折半查找好。

斐波那契查找

斐波那契查找原理与二分查找相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近。

前置n = Fu - 1

若相等，则查找成功
若key < a[Fu-1] ，则继续在 a[1] 至 a[Fu-1 - 1] 的子表中进行查找
若key > a[Fu-1] ，则继续在 a[Fu-1 + 1] 至 a[Fu - 1] 的子表中进行查找。该子表的长度为 Fu-2 -1

// 斐波那契查找.cpp 

#include "stdafx.h"
#include <memory>
#include  <iostream>
using namespace std;

const int max_size=20;//斐波那契数组的长度

/*构造一个斐波那契数组*/ 
void Fibonacci(int * F)
{
    F[0]=0;
    F[1]=1;
    for(int i=2;i<max_size;++i)
        F[i]=F[i-1]+F[i-2];
}

/*定义斐波那契查找法*/  
int FibonacciSearch(int *a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
{
  int low=0;
  int high=n-1;
  
  int F[max_size];
  Fibonacci(F);//构造一个斐波那契数组F 

  int k=0;
  while(n>F[k]-1)//计算n位于斐波那契数列的位置
      ++k;

  int  * temp;//将数组a扩展到F[k]-1的长度
  temp=new int [F[k]-1];
  memcpy(temp,a,n*sizeof(int));

  for(int i=n;i<F[k]-1;++i)
     temp[i]=a[n-1];
  
  while(low<=high)
  {
    int mid=low+F[k-1]-1;
    if(key<temp[mid])
    {
      high=mid-1;
      k-=1;
    }
    else if(key>temp[mid])
    {
     low=mid+1;
     k-=2;
    }
    else
    {
       if(mid<n)
           return mid; //若相等则说明mid即为查找到的位置
       else
           return n-1; //若mid>=n则说明是扩展的数值,返回n-1
    }
  }  
  delete [] temp;
  return -1;
}

int main()
{
    int a[] = {0,16,24,35,47,59,62,73,88,99};
    int key=100;
    int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
    cout<<key<<" is located at:"<<index;
    return 0;
}

分块查找

索引查找又称为分块查找，是一种介于顺序查找和二分查找之间的一种查找方法，索引查找的基本思想是：首先查找索引表，可用二分查找或顺序查找，然后在确定的块中进行顺序查找。

在实现索引查找算法前需要弄清楚以下三个术语。

（1）主表：即要查找的序列。

（2）查找表：一般我们会将主表分成几个块，每个块中的元素被称为是查找表。

（3）索引表：即索引项的集合。

在利用索引查找时，需要先对数据进行分块。

就是分块然后进行查找

int search(int key, int a[])
{
　　int i, startValue;
　　i = 0;
　　while (i<3 && key>newIndex[i].key) 
　　{ 
　　　　// 确定在哪个块中，遍历每个块，确定key在哪个块中
　　　　i++;
　　}
　　if (i>=3) 
　　{ 
　　　　//大于分得的块数，则返回0
　　　　return -1;
　　}
　　startValue = newIndex[i].start; //startValue等于块范围的起始值
　　while (startValue <= startValue+5 && a[startValue]!=key)
　　{
　　　　startValue++;
　　}
　　if (startValue>startValue+5) 
　　{ 
　　　　//如果大于块范围的结束值，则说明没有要查找的数
　　　　return -1;
　　}

　　return startValue;
}

哈希查找

哈希表又称散列表，一种以「key-value」形式存储数据的数据结构。所谓以「key-value」形式存储数据，是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值，就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组，这种数组的下标可以是很大的整数，浮点数，字符串甚至结构体。

冲突：key1≠key2; Hash（key1）==Hash（key2），即两个不同关键字，具有相同地址时，就叫发生冲突。

1、直接定址法

哈希地址：f(key) = a*key+b (a,b为常数)

这种方法的优点是：简单，均匀，不会产生冲突。但是需要事先知道 key 的分布情况，适合查找表较小并且连续的情况。

2、数字分析法

若我们现在要存储某家公司员工登记表，如果用手机号码作为 key，那么极有可能前7位都是相同的，所以我们选择最后四位作为 f(key) 就是不错的选择。

3、平方取中法

故名思义，比如 key 是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为 f(key) 。

4、折叠法

折叠法是将 key 从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些)，然后将这几部分叠加求和，并按哈希表的表长，取后几位作为 f(key) 。

比如我们的 key 是 9876543210，哈希表的表长为3位，我们将 key 分为4组，987|654|321|0 ，然后将它们叠加求和 987+654+321+0=1962，再取后3位即得到 f(key) = 962 。

5、除留余数法

哈希地址：f(key) = key mod p (p<=m) m为哈希表表长。

这种方法是最常用的哈希函数构造方法。

处理冲突

1.开放地址法（闭散列法）：

核心思想是，把发生冲突的元素放到哈希表中的另外一个位置。线性探测法：发生冲突时，逐位往后挪动，寻找合适位置，只要哈希表没满，就一定能找到一个不发生冲突的位置。 addressi=( Hash(key) + di )，其中 di = 1，2，3··

二次探测法：发生冲突时，每次向后挪动k2个单位（k为挪动次数）。 addressi=( Hash(key) + di )，其中 di = 12，22，32···

伪随机探测法：发生冲突时，每次向后挪动k个单位（k为伪随机生成数）。

线性探测法的优点是：只要散列表未填满，总能找到一个不发生冲突的地址。缺点是：会产生 ”二次聚集“ 现象。而二次探测法和伪随机探测法的优点是：可以避免 “二次聚集“ 现象。缺点也很显然：不能保证一定找到不发生冲突的地址。

2.链地址法（开散列法）：

链地址法的基本思想是：把具有相同散列地址的记录放在同一个单链表中，称为同义词链表。有 m个散列地址就有 m个单链表，同时用数组 HT[0…m-1]存放各个链表的头指针，凡是散列地址为 i 的记录都以结点方式插入到以HT[i]为头结点的单链表中。

排序

冒泡排序

（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

//交换函数
void Swap(int* pa, int* pb) {
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

//冒泡排序
void BubbleSort(int* a, int n) {
	for (int j = 0; j < n; ++j) {
		//单趟
		for (int i = 1; i < n - j; ++i) {
			//前一个数大于后一个数，就交换
			if (a[i - 1] > a[i]) {
				Swap(&a[i - 1], &a[i]);
			}
		}
	}
}

选择排序

选择排序（ Selection sort）是一种简单直观的排序算法。它的工作原理是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

void Select_Sort(int* arr, int n)   //arr为数据数组，n为数组长度
{
	for (int i = 0; i < n-1; i++) {
		int min = i;
		for (int j = i+1; j < n; j++) {
			if (arr[min] > arr[j]) {
				min = j;
			}
		}
		if (min != i) {
			swap(arr[i], arr[min]);
		}
	}
}

插入排序

排序：即将一组混乱的数据按从小到大或者从大到小的顺序进行有序的排列出来。

void InsertSort(int *beauties, int len) {
	int index;	// 存储待比较的的索引
	int ret;	// 保存待插入数据

	for (int i = 1; i < len; i++) {
		index = i - 1;		// 保存待插入数据的前一个数据的索引
		ret = beauties[i];	// 保存待插入数据

		// 当索引大于等于零，且所有对应的数值大于待插入数据
		while (index >= 0 && beauties[index] > ret) {
			beauties[index + 1] = beauties[index];	// 将当前索引的数值往后移动一个位置
			index--;	// 索引减一
		}

		// 当索引为-1或者索引对应的值要比ret小时，就可以退出循环，ret就可以插入到索引加一的位置了
		beauties[index + 1] = ret;	
	}
}

插入排序是一个稳定的排序方法。

希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。希尔排序是记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

1. 时间复杂度：最坏情况下，每两个数都要比较并交换一次，则最坏情况下的时间复杂度为O（n2）, 最好情况下，数组是有序的，不需要交换，只需要比较，则最好情况下的时间复杂度为O（n）。

经大量人研究，希尔排序的平均时间复杂度为O（n1.3）

2. 空间复杂度：希尔排序，只需要一个变量用于两数交换，与n的大小无关，所以空间复杂度为：O（1）。

void ShellSort(int *arr, int len) {
	int grp = len / 2;		// 计算增量

	for (; grp > 0; grp = grp / 2) {	// 每次计算完一轮，增量再除以二

		// 选择排序
		for (int i = grp; i < len; i++) {	
			int cur = arr[i];	// 先空出第二个数的位置
			int j = 0;

			// 根据增量往前比较，小的在前，大的在后
			for (j = i - grp; j >= 0 && arr[j] > cur; j = j - grp) {
				arr[j + grp] = arr[j];	// 符合条件将前面的数据移动到空出的位置
			}
			arr[j + grp] = cur;	// 最后将待插入数据cur插入到前面空出的位置
		}
	}
	
}

归并排序

归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。

将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。

void merge_sort(int a[],int l,int r)
{
    if(l==r)
{
    return ;
}
int mid=l+r>>1;
merge_sort(a,l,mid),merge_sort(a,mid+1,r);
for(int i=l,j=l,k=mid+1;i<=r;i++)
{
    if(j==mid+1)
    {
        t[i]=a[k++];
    }
    else if(k==r+1)
    {
        t[i]=a[j++];
    }
    else if(a[j]<=a[k])
    {
        t[i]=a[j++];
    }
    else
    {
        t[i]=a[k++];
    }
}
for (int i = l; i <= r; i++)
{
    a[i] = t[i];
}
}

算法性能

速度仅次于快速排序。

时间复杂度

O(nlogn)。

空间复杂度

O(N)，归并排序需要一个与原数组相同长度的数组做辅助来排序。

稳定性

稳定。

快速排序

采用“分治”的思想，对于一组数据，选择一个基准元素（base），通常选择第一个或最后一个元素，通过第一轮扫描，比base小的元素都在base左边，比base大的元素都在base右边，再有同样的方法递归排序这两部分，直到序列中所有数据均有序为止。

void qSortArray(int array[], int start, int last)
{
	int low = start;
	int high = last;
	if (low < high)
	{
		while (low < high)
		{
			while (array[low] <= array[start] && low < last)
			{
				low++;//满足小于基准的条件，指针右移
			}
			while (array[high] >= array[start] && high > start)
			{
				high--;//满足大于基准的条件，指针左移
			}
			if (low < high)
			{
				swap(array[low], array[high]);//交换两个不满足条件的元素
			}
			else
			{
				break;
			}
		}
		swap(array[start], array[high]);//插入基准元素
		qSortArray(array, start, high - 1);
		qSortArray(array, high + 1, last);
	}
}

堆排序

堆结构

解释在代码里

这是大根堆

#include<bits/stdc++.h>
using namespace std;
const int N=1e7;
int w[N];
int tot;
#define rep(i,a,n) for(int i=a;i<=n;i++)
//一个是数组，一个是最后一个节点所在位置
//1.top操作
int top()
{
    return w[1];
    //返回堆顶也就是最大值
}
void modify(int x)
{
if(x==1||w[x]<w[x/2])
{
    return ;
    //就是你已经到达根顶了，或者你已经小于你的父节点了
    //这样就行了实际上
}
swap(w[x],w[x/2]);
//这也正是没有达到上述情况，那么你就要交换
modify(x/2);
//交换完继续处理上一个节点
//递归处理
}
void push(int x)
{
    w[++tot]=x;//加入元素直接在尾部进行加入
    modify(tot);//自底向上修复
}
void repair(int x)
{
if(x*2>tot)
{
    return ;
    //已经到达叶子节点，和上个modify操作一样
}
int tar=2*x;
if(x*2+1<=tot)
{
    tar=w[x*2]>w[x*2+1]?x*2:x*2+1;
}
if(w[x]<w[tar])
{
    swap(w[x],w[tar]);
    repair(tar);
}
}
void pop()
{
    swap(w[1],w[tot--]);
    //这一步有两个操作，第一个是交换头尾，第二个是删除尾部
   //接下来我们要修复头部
   repair(1); 
}
int main()
{
int n;
cin>>n;
rep(i,1,n)
{
    int x;
    cin>>x;
    push(-x);
}
rep(i,1,n)
{
    cout<<-top()<<' ';
    pop();
}
return 0;
}

计数排序

#include<iostream>
#include<vector>
#include<ctime>
using namespace std;
const int MAX = 101;

void CountingSort(vector<int> &a){
    vector<int> count(MAX, 0);           //统计每个数字出现的次数
    for(auto &x : a)
	count[x]++;
    
    int k = 0;
    for(int num = 0; num < MAX; num++){
    	while(count[num]){
    	    a[k++] = num;
    	    count[num]--;
    	}
    }

    vector<int>().swap(count);           //相当于用一个空直接换掉
}


void show(vector<int> &v){
    for(auto &x : v)
        cout<<x<<" ";
    cout<<endl;
}


 int main(){
    vector<int> a;
    int n = 100;
    srand((int)time(0));
    while(n--)
        a.push_back(rand() % 100 + 1);
    show(a);
    CountingSort(a);
    cout<<endl<<endl;
    show(a);
}

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

过程

桶排序按下列步骤进行：

设置一个定量的数组当作空桶；
遍历序列，并将元素一个个放到对应的桶中；
对每个不是空的桶进行排序；
从不是空的桶里把元素再放回原来的序列中。

const int N = 100010;

int n, w, a[N];
vector<int> bucket[N];

void insertion_sort(vector<int>& A) {
  for (int i = 1; i < A.size(); ++i) {
    int key = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > key) {
      A[j + 1] = A[j];
      --j;
    }
    A[j + 1] = key;
  }
}

void bucket_sort() {
  int bucket_size = w / n + 1;
  for (int i = 0; i < n; ++i) {
    bucket[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    bucket[a[i] / bucket_size].push_back(a[i]);
  }
  int p = 0;
  for (int i = 0; i < n; ++i) {
    insertion_sort(bucket[i]);
    for (int j = 0; j < bucket[i].size(); ++j) {
      a[++p] = bucket[i][j];
    }
  }
}

STLsort

// a[0] .. a[n - 1] 为需要排序的数列
// 对 a 原地排序，将其按从小到大的顺序排列
std::sort(a, a + n);

// cmp 为自定义的比较函数
std::sort(a, a + n, cmp);


//自定义
struct data {
  int a, b;

  bool operator<(const data rhs) const {
    return (a == rhs.a) ? (b < rhs.b) : (a < rhs.a);
  }
} da[1009];

bool cmp(const data u1, const data u2) {
  return (u1.a == u2.a) ? (u1.b > u2.b) : (u1.a > u2.a);
}

// ...
std::sort(da + 1, da + 1 + 10);  // 使用结构体中定义的 < 运算符，从小到大排序
std::sort(da + 1, da + 1 + 10, cmp);  // 使用 cmp 函数进行比较，从大到小排序

本文的主要参考（抄袭对象）

数据结构_UniqueUnit的博客-CSDN博客

引言

背景与前置知识

数据的存储结构主要有顺序存储、链式存储、索引存储和散列存储

时间复杂度与空间复杂度

算法效率

大O的表示法规则

方法

事后统计法

ACM 时间复杂度

复杂度大小顺序

不同规模 \(n\) 的复杂度选择

线性表

一、线性表的定义

有限：

序列

基本操作

二、线性表的存储结构

线性表的顺序表示和实现

代码实现步骤

线性表的链式存储和实现

代码演示

介绍两种插法，头插法和尾插法

优缺点分析

优点

缺点

其他链表

双向链表

代码综述

循环链表

代码综述

总结

栈与队列

栈

一、栈的基本概念

1、栈的定义

二、栈的顺序存储结构

偏向于ACM的栈实现

共享栈（两栈共享空间）

（1）共享栈概念

顺序存储

三、栈的顺序存储结构

单调栈

洛谷单调栈

队列

一、队列的基本概念

1、队列的定义

二、队列的顺序存储结构

ACM队列相关

数组模拟队列

三、队列的链式存储结构

链队列

双端队列

单调队列

串

二、串的存储结构

1、定长顺序存储表示

2、堆分配存储表示

3、块链存储表示

串的模式匹配

一、BF模式匹配算法

KMP算法

树

1、树的定义

树的性质

1. 树的结点数公式

2. 第 \(i\) 层的结点数

3. 高度为 \(h\) 的 \(m\)-叉树的最大结点数

4. \(n\) 个结点的 \(m\)-叉树的最小高度

其他推导：

二叉树的性质

满二叉树与完全二叉树

斜树

平衡二叉树

树的存储结构

二叉树的遍历

先序遍历

中序遍历

后序遍历

层次遍历

线索二叉树

`双向链表`