当前位置：首页 > news >正文

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

news 2026/4/28 23:44:13

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

时间复杂度

概念

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

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

计算方法

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

第二步：计算时间复杂度

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

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

空间复杂度

概念

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

认识递归方法

概念

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

递归的本质

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

举一个具体例子：

longlongfun(intn)

{

if(n < 0)

{

printf("Illegal number!\n");

return-1;

}

elseif(n == 0)

return1;

else

returnn * 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）。