位置：首页-资讯-后端开发

C++数据结构与算法的基础知识和经典算法汇总

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

算法分析的本质

算法分析就是对时间复杂性和空间复杂性进行分析

时间复杂度

概念

时间复杂性又叫时间复杂度，是对算法运行时间长短的度量。

人们通常只考虑三种情况下的时间复杂性：最坏、最好、平均情况。

计算方法

第一步：声明哪些代码是基本运算

第二步：计算时间复杂度

第三步：写成O(n)的形式

注：基本运算就是程序中运行最多的，最坏的情况

空间复杂度

概念

空间复杂性是对一个算法在运行过程中所占用存储空间大小的度量，一般记为S(n)，这里的n是问题规模，一般不要求计算空间复杂度，所以复习一下概念。

认识递归方法

概念

子程序(或函数)直接调用自己或通过一系列调用语句间接调用自己，称为递归。直接或间接调用自身的方法成为递归算法。

递归的本质

函数在调用时，首先在栈顶分配他的形式参数和局部变量存储空间，然后执行函数；函数返回时从栈顶释放他的形式参数和局部变量存储空间，而调用他的那个函数的形式参数和局部变量就成为了新的栈顶，任何函数运行时都只使用栈顶的那一份存储空间，如果递归深度太大，栈会溢出——栈式存储管理。

举一个具体例子：

long long fun(int n)
{
	if (n < 0)
	{
		printf("Illegal number!\n");
		return -1;
	}
	else if (n == 0)
		return 1;
	else
		return n * fun(n - 1);
}

假如传入n=3，在栈顶分配fun(3)的局部变量存储空间和他的形式参数，然后执行函数；由于n>1，所以会返回3*fun(2)；此时fun(2)成为新的栈顶，也分配形参和存储空间，再次执行函数，返回2*fun(1)；这时fun(1)成为新的栈顶元素，执行后返回结果为1*fun(0)，再次执行函数，返回fun(0)；fun(0)结果为1，栈顶的fun(0)分配的空间被释放，栈顶变为fun(1)，结果为1*1=1；然后被清理，栈顶变为fun(2)，结果为2*fun(1)=2;最后回归到fun(3)，结果为3*fun(2)=6；这就是计算机中本质上递归的过程，是通过调用堆栈完成递归的递推和回归过程的。

基本的数据结构

线性表

线性表时最简单、常用的一种数据结构，简言之，一个线性表时n(n>=0)个数据元素的有限序列。线性表分为顺序表和链表两种，而这最大的区别就是顺序表是顺序存储的，链表是随机存储。

顺序表

把线性表的元素按逻辑次序依次存放在一组地址连续的存储单元，用这种方法存储的线性表简称为顺序表。

顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 　1≤i≤n 其中，L是元素占用存储单元的长度。

由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常采用数组来描述顺序表。

链表

链表是线性表的另一种存储与方式，其特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），它由一系列结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。链表的主要形式有单链表、循环链表、和双向链表。

(1)在线性链表中，每个结点包括两个部分:一个是存储数据元素信息的数据域;另一个是存储直接后继存储位置的指针域，该域表示了元素与其直接后继元素之间的逻辑关系，

域中存储的信息称做指针或链。n个结点链接成一个链表，即为线性表的链式存储结构。由于此链表的每个结点中只包含一个指针域，故称为线性链表或单链表。用链表来表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的，逻辑上相邻的两个元素其存储的物理位置不要求紧邻。因此，在使用链表时，人们关心的是它所表示的线性表中数据元素的逻辑顺序，而不是每个数据元素在存储器中的实际位置。那么如何设计链表的逻辑结构图呢?

通常把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。例如线性表的逻辑结构图：

其中，H称为头指针，它指示链表中第一个结点的存储位置，整个链表的存取必须从头指针开始进行。由于最后一个元素a3没有直接后继，因此他的指针域设为空（NULL）。

栈与队列

栈与队列时另外两种重要的线性结构，他们可以使用上面所讲的顺序表或者链表的结构来最终实现。

栈

栈可看成是一种“特殊”的线性表，该线性表限定仅在表尾进行插人和删除操作。栈主要应用于表达式的计算、子程序嵌套调用递归调用等。

栈具有下述特殊的性质:

(1)通常称插入、删除的这一端为栈顶(Top);另一端称为栈底( Bottom)。

(2)当表中没有元素时称为空栈。

(3)栈的修改是按“后进先出”的原则进行，因此栈简称为LIFO表(LastInFirstOut)。

每次删除(退栈)的总是当前栈中“最新”的元素，即最后插人 (进栈)的元素，而最先插人的元素是被放在栈的底部，要到最后才能删除。

队列

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

队列有下述特殊性质:

(1)允许删除的一端称为队头(Front)。

(2)允许插人的端称为队尾(Rear)。

(3)当队列中没有元素时称为空队列。

(4)队列的结构特点是先进队的元素先出队。

(5)队列的修改时依先进先出的原则进行的。新来的成员总是加入队尾，每次离开的成员总时队头元素，而不允许中途离队。

重要算法概念

贪心法

通过局部最优来得到全局最优

结论：

贪心法在面临选择时，都做出对眼前来讲最有利的选择，不考虑该选择对将来是否有影响。

该算法不允许回溯

该算法的好坏在于正确的选择贪心策略

贪心法具有高效性和不稳定性，这个解不一定时最优解，但是一定是最优解的近似解。

分治法

分治法,字面上的解释是“分而治之”，就是把个复杂的问题分成两个或更多的相同子

问题，再把子问题分成更小的子问题，直到最后各个子问题可以简单地直接求解,对各个子问题的解进行合并即得原问题的解。

可见，分治法的基本思想是将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各个击破，分而治之。

那么,何时能、何时应该采用分治法来解决问题呢?即分治法所能解决的问题应该具备哪些特征?从许多可以用分治法求解的问题中，我们看到这些问题一般具有以下几个特征:

(1)问题的规模缩小到一定程度就可以容易地解决。

(2)问题可以分解为若干个规模较小的相同子问题。（递归）

(3)问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

(4)问题分解出的子问题的解可以合并为原问题的解（分治法的根本依据）

搜索法

宽度优先搜索

给定图G=(V,E),它的初始状态是所有顶点均未被访问过，在图G中任选-个顶点u作为源点，则宽度优先搜索的思想为:先访问顶点U,并将其标记为已访问过:然后从v出发,依次访问V的邻接点(孩子节点)w.w...,w,如果w,(i= .2..t)未访问过，则标记w;为已访问过,将其插人到队列中;然后再依次从队列中取出wI ,w.*,w,，访问它们的邻接点。依次类推,直到图中所有和源点U有路径相通的顶点均已访问过为止;若此时图G中仍然存在未被访问过的顶点，则另选一个尚未访问过的顶点作为新的源点。重复上述过程，直到图中所有顶点均已访问过为止。

分支限界法

分支限界法是一种在问题的解空间树中搜索问题解的算法，它常以宽度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。

分支限界法首先将根结点加人活结点表(用于存放活结点的数据结构)，接着从活结点表中取出粮结点，使其成为当前扩展结点，一次性生成其所有孩子结点，判断孩子结点是含弃还是保留，含弃那些导致不可行解或导致非最优解的孩子结点,其余的被保留在活结点表中。再从活结点表中取出一个活结点作为当前扩展结点,重复上述扩展过程，一直持续到找到所需的解或活结点表为空时为止。由此可见，每一个活结点最多只有一次机会成为扩展结点。

可见，分支限界法搜索过程的关键在于判断孩子结点是舍弃还是保留。因此,在搜索之前要设定孩子结点是舍弃还是保留的判断标准，这个判断标准与回溯法搜索过程中用到的约束条件和限界条件含义相同。活结点表的实现通常有两种方法:一是先进先出队列，二是优先级队列，它们对应的分支限界法分别称为队列式(FIFO)分支限界法和优先队列式分队列式分支限界法按照队列先进先出(FIFO)的原则选取下一个结点作为当前扩展结点。优先队列式分支限界法按照规定的优先级选取队列中优先级最高的结点作为当前扩展结点。优先队列一般用二叉堆来实现:最大堆实现最大优先队列，体现最大效益优先:最小堆实现最小优先队列，体现最小费用优先。

分支限界法的般解题步骤为:

(1)定义问题的解空间。

(2)确定问题的解空间组织结构(树或图)。

(3)搜索解空间。搜索前要定义判断标准(约束函数或限界雨数)，如果选用优先队列

式分支限界法，则必须确定优先级。