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

目录
  • 算法分析的本质
    • 时间复杂度
      • 概念
      • 计算方法
    • 空间复杂度
      • 概念
  • 认识递归方法
    • 概念
    • 递归的本质
  • 基本的数据结构
    • 线性表
      • 顺序表
      • 链表
    • 栈与队列
      • 队列
  • 重要算法概念
    • 贪心法
    • 分治法
    • 搜索法
      • 宽度优先搜索
      • 分支限界法
  • 总结

算法分析的本质

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

时间复杂度

概念

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

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

计算方法

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

第二步:计算时间复杂度

第三步:写成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)搜索解空间。搜索前要定义判断标准(约束函数或限界雨数),如果选用优先队列

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

总结

本来想小小总结一下,但是到最后发现工作量真的大,肝了大半天,也可能是我太认真了,哈哈,真的希望可以对你们有所帮助,最后求一个小小的三连!!!

到此这篇关于C++数据结构与算法的基础知识和经典算法汇总的文章就介绍到这了,更多相关C++数据结构与算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • c/c++基础简单易懂的快速排序算法

    快速排序就是找一个基准,然后其左边要比他小,右边要比他大 int partition(int* a, int left, int right) { int pivot = left;//找最开始位置为基准 int index = left + 1; for (int i = index; i <= right; i++) { if (a[i] < a[pivot]) { swap(a, i, index); index++; } } swap(a, pivot, index - 1);//in

  • C++浅析类与对象的基础

    目录 面向过程和面向对象 类的引入 访问限定符 封装 类的作用域 类的实例化 面向过程和面向对象 类和对象是 C++ 的核心特性 我们之前的C语言就属于面向过程,关注过程,分析求解问题的步骤再通过函数调用解决问题:而现在C++是基于面向对象,关注对象,将一个问题拆分成不同对象,依靠对象之间的交互完成. 比如有一个图书馆系统,用C语言面向过程思路就是:统计图书,图书分类,同步上架图书数据,记录借阅信息.而面向对象我们会创建两个类,图书馆和用户,我们关心的是图书馆和用户之间的关系,再分别实现交互,这

  • C++入门之模板基础讲解

    目录 前言 引入 模板 函数模板 模板的匹配原则 模板的显示调用 类模板 注意1 注意2 总结 前言 今天博主将要介绍的内容是–模板,他在C++中具有非常重要的位置.至于什么是模板呢?我们请看下面的章节. 引入 我们对交换函数Swap已经非常熟悉了,但是我们经常会遇到这样的一些事,比如,很多不同的数据类型进行交换,那么我们就需要写不同的重载Swap,如下: #include <iostream> using namespace std; void Swap(int& a,int&

  • C++基础知识之运算符重载详解

    目录 运算符重载 方式一,使用成员函数重载运算符需求:把牛肉换猪肉,羊肉换猪肉 方式二,使用非成员函数[友元函数]重载运算符 两种方式的区别 两种方式的选择: 总结 运算符重载 为什么要使用运算符重载 -C/C++的运算符,支持的数据类型,仅限于基本数据类型. 问题:一头牛+一头马 = ?(牛马神兽?) 一个圆 +一个圆 = ? (想要变成一个更大的圆)一头牛 – 一只羊 = ? (想要变成4只羊,原始的以物易物:1头牛价值5只羊) 解决方案: 使用运算符重载 方式一, 使用成员函数重载运算符

  • C++详细讲解图论的基础与图的储存

    目录 一.前言 二.图的定义 三.图的储存 1.邻接矩阵 2.邻接表 3.邻接矩阵与邻接表的优缺点对比 一.前言 在算法中一般都需要把问题抽象成图论问题然后用图论的算法解决问题. 图论涉及相当多的算法,包括图DFS和BFS.连通性.拓扑排序.最小生成树.最短路径.最大流网络.图的着色问题等等 图论算法在计算机科学中扮演着很重要的角色,它提供了对很多问题都有效的一种简单而系统的建模方式.很多问题都可以转化为图论问题,然后用图论的基本算法加以解决. 二.图的定义 图(graph) 如上图是一个图G,

  • C++基础概念讲述

    目录 1.C++相关网站推荐 2.C++和C的关系 3.C++特性说明 3.1与底层硬件紧密结合 3.2对象生命周期的精确控制 3.3Zero-Overhead Abstraction 首先,通过一张最新(2021.11)的编程语言排名图来了解常见的编程语言: 从图中可以看出,C++的排名相对于Python.Java.C来说并不突出,很大的原因是因为C++难度过大,也可以说是知识点太多,我们很难说能精通C++这门语言,只能说对它的部分了解,并能在工作中使用: 1.C++相关网站推荐 1.cppr

  • C++超详细梳理基础知识

    目录 命名空间的使用 来源 命名空间的使用 不展开 部分展开 全展开 函数重载 函数重载的规则 C++如何实现函数重载 引用 命名空间的使用 来源 在了解命名空间的原理和使用之前,我们先要理解,命名空间是为了解决什么问题. C++是在C的基础上发展而形成的一种语言,完全兼容C的语法,也加入了许多新的规则和语法来解决C的缺陷. 命名空间就是为了解决C语言中的重复命名的问题. 首先我们来看看这么一个代码: #include<stdio.h> int main() { int scanf = 20;

  • C++零基础精通数据结构之带头双向循环链表

    目录 与单链表的区别 代码的实现 接口 节点的构造 初始化链表 开辟节点 销毁链表 打印链表 尾插链表 尾删链表 头插链表 头删链表 查找链表 链表pos位置的删除 总结 与单链表的区别 单向/双向 单向:只有一个next指针,只指向下一位元素 双向:有两个指针,指向上一位和下一位元素,寻找前一节点和后一节点很便利 带头/不带头 带头:在本来的头结点之前还有一个哨兵卫节点作为头节点,它的址域指针指向头节点,值域不做使用 不带头:没有哨兵卫头节点,在尾删尾插等问题中要考虑头结点的情况(局限) 循环

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

    目录 算法分析的本质 时间复杂度 概念 计算方法 空间复杂度 概念 认识递归方法 概念 递归的本质 基本的数据结构 线性表 顺序表 链表 栈与队列 栈 队列 重要算法概念 贪心法 分治法 搜索法 宽度优先搜索 分支限界法 总结 算法分析的本质 算法分析就是对时间复杂性和空间复杂性进行分析 时间复杂度 概念 时间复杂性又叫时间复杂度,是对算法运行时间长短的度量. 人们通常只考虑三种情况下的时间复杂性:最坏.最好.平均情况. 计算方法 第一步:声明哪些代码是基本运算 第二步:计算时间复杂度 第三步:

  • Java基础知识汇总

    Java基础知识 1.Java语言的优点: 1)Java是纯面向对象语言 2)与平台无关性,一次编译到处运行 3)Java提供了狠多内置类库 4)提供了对web应用的支持 5)具有较好的安全性(数组边界检测.Bytecode检测)和健壮性(强制型机制.垃圾回收器.异常处理) 6)去除c++难以理解的一些特性(头文件 指针 运算符重载 多重继承) 2.java与c++的异同: 1)Java为解释型语言,c++为编译型语言,java会慢但是跨平台 2)Jave为纯面向对象,c++既面向对象又能面向过

  • Python常用算法学习基础教程

    本节内容 算法定义 时间复杂度 空间复杂度 常用算法实例 1.算法定义 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制.也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出.如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题.不同的算法可能用不同的时间.空间或效率来完成同样的任务.一个算法的优劣可以用空间复杂度与时间复杂度来衡量. 一个算法应该具有以下七个重要的特征: ①有穷性(Fin

  • Lua教程(二):基础知识、类型与值介绍

    一.基础知识: 1. 第一个程序和函数:     在目前这个学习阶段,运行Lua程序最好的方式就是通过Lua自带的解释器程序,如:   复制代码 代码如下: /> lua     > print("Hello World")     Hello World 这样我们就可以以交互性的方式输入lua代码,并立即得到执行结果了.对于代码块较少的测试程序来说,这种方式确实是非常方便的,然而对于相对复杂的程序而言,这种方式就不是很合适了.如果是这样,我们可以将Lua代码保存到一个独立

  • PHP内核介绍及扩展开发指南—基础知识

    一. 基础知识 本章简要介绍一些Zend引擎的内部机制,这些知识和Extensions密切相关,同时也可以帮助我们写出更加高效的PHP代码. 1.1 PHP变量的存储 1.1.1 zval结构 Zend使用zval结构来存储PHP变量的值,该结构如下所示: 复制代码 代码如下: typedef union _zvalue_value { long lval; /* long value */ double dval; /* double value */ struct { char *val;

  • Google关键词广告基础知识问答

    1.google关键词广告是什么?  答:google官方对这个广告的英文描述叫adwords,它是显示在搜索结果页面右侧的网站链接广告.它是属于CPC(cost-per-click)收费--按点击次数收费的网络广告类型. 2.google关键词广告和搜索结果页面左侧网站排名是否有关系?  答:没有任何关系,搜索结果页面左侧网站排名是完全按照google自身的算法而的出来的,无法进行人工干预的(当然,可以利用它的算法的规则来提高网站排名,这部分内容不在本文讨论范围之类):而关键词广告是人工添加的

  • Cisco路由技术基础知识详解

    Cisco路由技术基础知识详解 路由器 <一> 最简单的网络可以想象成单线的总线,各个计算机可以通过向总线发送分组以互相通信.但随着网络中的计算机数目增长,这就很不可行了,会产 生许多问题: 1.带宽资源耗尽.     2.每台计算机都浪费许多时间处理无关的广播数据.     3.网络变得无法管理,任何错误都可能导致整个网络瘫痪.     4.每台计算机都可以监听到其他计算机的通信. 把网络分段可以解决这些问题,但同时你必须提供一种机制使不同网段的计算机可以互相通信,这通常涉及到在一些ISO网

  • Java异常基础知识解析

    Java程序运行的非正常现象叫做运行错误,根据其性质可分为两类:错误(Error)和异常(Exception); 他们有一个共同的父类(也是所有异常的顶级父类):Throwable. 异常类结构 Error Error(错误)由JVM生成并抛弃不做处理:此类错误通常与代码和执行的操作无关,是虚拟机中出现了比较严重的问题,程序本身无法解决(常见的错误有死循环.内存泄漏等). 一个常见的错误为Java虚拟机错误(VirtualMachineError),当JVM不再有继续执行操作所需的内存资源时,将

  • 快速学习MySQL基础知识

    这篇文章主要梳理了 SQL 的基础用法,会涉及到以下方面内容: SQL大小写的规范 数据库的类型以及适用场景 SELECT 的执行过程 WHERE 使用规范 MySQL 中常见函数 子查询分类 如何选择合适的 EXISTS 和 IN 子查询 了解 SQL SQL 是我们用来最长和数据打交道的方式之一,如果按照功能划分可分为如下 4 个部分: DDL,数据定义语言.定义数据库对象,数据表,数据列.也就是,对数据库和表结构进行增删改操作. DML,数据操作语言.对数据表的增删改. DCL,数据控制语

  • 详解Java数据库连接JDBC基础知识(操作数据库:增删改查)

    一.JDBC简介 JDBC是连接java应用程序和数据库之间的桥梁. 什么是JDBC? Java语言访问数据库的一种规范,是一套API. JDBC (Java Database Connectivity) API,即Java数据库编程接口,是一组标准的Java语言中的接口和类,使用这些接口和类,Java客户端程序可以访问各种不同类型的数据库.比如建立数据库连接.执行SQL语句进行数据的存取操作. JDBC代表Java数据库连接. JDBC库中所包含的API任务通常与数据库使用: 连接到数据库 创

随机推荐