数据结构与算法--算法

知识本

C++STL

容器

字符串函数(string容器函数)

字符串转字符

string对象调用data（）函数 会返回他的 const char* 也就是字符数组 之后取单个字符即可

算法

交换函数

swap(int a,int b)
可以交换a和b的位置 是C++的库函数 直接用即可

拿到容器或者数组的第一个最大（小）值元素的下标或者值

如果不加* 那么拿到的就是下标 （但是要减去首地址或者第一个迭代器）
如果加星 那么就会直接输出最大值

排序函数

其中的sort是排序函数 传入两个参数 第一个是字符串的第一个字符 第二个是字符串的最后一个字符 他是一个实参形参同步的函数 没有返回值 但是会把字符串进行排序 并同步实参

sort（）使用时要包含头文件#include 之后传入参数 有三个 第一个参数是待排序的第一个元素的指针 第二个参数是待排序的最后一个元素的指针 第三个是排序规则 可以不写 不写的话默认从小到大

如果想从大到小 可以传入greater()

或者也可以自定义排序规则 定义一个返回值为bool的函数 参数传入两个数
具体规则 可以将两个数想象为先后传入 想象为待排序数组（或字符串）中的相邻的两个元素 之后比较返回真假值就可以确定比较法则

求字符数组的有效长度

！！！ 对于第一种方式要包含头文件《cstring》

第二种方式 由于结尾\0的存在 输出的数会多一个 减去即可

对于非字符数组：

没有尾字符 所以数是对的

这里补充 单纯的end() 和begin()函数 会直接返回数组的首指针 和 尾指针的下一个

atoi函数（将字符串类型的数字转为真正的int型数字）

无需包含cstdlib头文件，但是要把string转为char *
使用s.c_str()即可，（无需包含文件）
其中s是字符串，如下图：

string转字符 再将数字字符转为int型数字

首先通过图中通过key得到了value 是一个string类型的字符 调用string函数 c_str()函数 转为字符数组类型 然后用atoi（字符数组）再将数字字符转为int型数字

详情可查阅算法专栏“算法知识+错题本”一文中STL部分

ceil向上取整

ceil（a），如果a是2.5，那么结果就是3；如果结果是2.0000001，那么结果还是3

int和字符、字符串的转换

根据数据范围选择对应的变量类型

注意，要估算一下一个算法题的最大值在哪个范围，而不仅仅是看题设给出的范围，因为有时候会有两个大数相加相乘出现，所以要根据一个变量的最大值选取对应的类型

数组初始化相关问题

需不需要初始化

需要

初始化的方式以及注意点

大体上可以分为，定义时初始化，
以及定义完之后，紧跟着初始化语句

注意点：
1、且定义数组必须要知道数组的最大长度（哪怕是使用初始化列表去省略中括号里的长度，那么也是在已知了完整的数据的情况下进行的，还是属于知道数组的最大长度）
2、我们知道，初始化只有“初始化参数”、“for循环一个一个元素进行初始化”、“memset”
所以，对于字符数组，如下图的初始化方式是错误的

如果想一次性初始化s，只能使用初始化参数列表的方式：char s[20]=“abcd”//等价于char s[20]={‘a’,‘b’,‘c’,‘d’,‘\0’}(注意末尾有’\0’)
否则只能先定义出来char之后，使用for循环一个一个进行赋值

定义时初始化（初始化参数列表）

（c++11标准也是这样）

定义之后初始化

memset

for循环

字符串、字符数组、字符指针辨析

字符串string，使用字符串字面值初始化，是string库的一种类型，对于现在的c++标准来说，使用极为广泛（其末尾以\0结尾，但不计入size函数）
字符数组，可以使用多个单字符初始化（结尾带不带空字符全看定义时加没加，不加的话极易引发错误但是语法合法），也可以使用字符串字面值初始化（结尾自带空字符，字符数组要预留出字符串字面值所带的空字符的位置）
字符指针，所有关于字符数组的操作，都可以转化为字符指针，实际上底层就是字符指针的运算

字符串

字符串的输出方式

使用cout（推荐）

不管是string 还是char数组 还是char指针，统一使用cout即可

使用printf

使用%s一次性输出

针对char *

针对char s【】数组类型的字符串

本质上是将char *类型的变量，也就是字符串的地址传进去进行输出

针对string类型的字符串

基本思想：转为char *
方法：使用c_str（）
（无需包含头文件）

循环输出

针对char s【】数组

针对string类型的字符串

与上面的char 数组类型的一样，所以这里可以将string字符串看成字符数组

注意点

字符指针：

字符指针只能用于对字符串常量进行表达，如果直接输出指针s，那么会对其指向的整个字符串进行输出
如果只输出*s，那么只会输出首字符

同样的，用于字符数组也是这样，

而如果使用printf，且解引用输出，则会出错，什么也不会输出。

所以在输出字符指针和字符数组时，还是要直接输出指针或者数组名

字符串的四种输入方式

对于string类型

getline(从缓存区读取一行直到遇见回车)

需要包含头文件string，注意不是string.h（因为这是string库里的内容，但是c++11标准中无需再包含）

他是string库中的内容，适用于string变量，他读取一行字符串，给到参数二
但是注意，他会把一行字符中末尾的回车读取走，但是不会放入s1中

对于字符数组和字符指针

gets（从缓存区读取字符串直到遇见回车，可以用于getline的非string版本）

包含stdio.h头文件 （c++中可以不包含）

首先要定义并初始化一个字符数组，gets会读取字符之间空格，如上图

可以看到，他就是c风格字符串的“getline（）”，（c风格字符串，就是将字符串常量赋值给字符数组）
他的输出也没有换行，说明他会读取一行行末尾的回车，且遇到回车停止，但是不会将回车放入参数所代表的字符数组中

不可以用于字符指针：

虽然字符数组本质上就是字符指针，但是初始化就是一个指针的话，无法使用%s输出，也就无法进行字符串的相关操作。
但是如果是初始化时是定义好大小的字符数组，那么可以将其数组名（本质是字符指针）拿来操作

与哪种类型的字符串无关，单纯从缓冲区读取字符，放到一个char变量里

getchar（）（从缓冲区读取返回一个字符，该方法无参数）

包含stdio.h头文件（c++中可以不包含）
getchar什么字符都可以取到，可以对getchar的返回值做一些任何你想要进行的判断

可以使用下面这种方法。效果等效于gets（）

同样，与gets相同，可以读取字符之间的空格

getchar（）的应用只需要一个字符变量即可，他将读到的内容赋值给字符变量，会读到空格，会读到回车（因为这两个都是字符，是转义字符，但是其他的函数可能会将其中的某个转义字符当做标记字符并舍弃），都会拿到，但是至于是否赋值给字符变量，还是直接什么也不做（相当于只读取，也就是舍弃），取决于你自己

对于字符数组类型的补充

scanf（）（只有字符数组可以使用，string以及字符指针不可以使用）

！！！ 并且他不可以读入空格 遇见空格视为结束（cin也一样）


scanf不可以读取字符之间的空格

字符串的比较

区分大小写

string类型

compare（）

包含string头文件

s1.compare（s2）结果为0就是相等

==

s1 == s2
结果为真，就是相等

字符数组和字符指针类型

strcmp

#include

该方法同样适用于字符数组，如下：

不区分大小写

string类型

将两个string全部转为小写（或者大写）

使用c_str（）转为char指针，之后使用char指针的方法

例如使用stricmp方法
包含头文件string.h

字符数组和指针类型

stricmp函数

包含头文件string.h

线性表的结构体定义

链表

对于链表 直接定义一个结点结构体就好了 如下图

并且一般会对结构体进行两种重命名 一个是实体类型 一个是指针类型

补充：node是结点的意思
链表命名为 Listnode *LinkList
链栈命名为 StackNode *LinkStack
链队列命名为 QueueNode *LinkQueue
（以上三种均可以缩写） LNode SNode QNode

对于链队列的定义需要特殊说明

首先要明确 链表的头指针 就是指向结点的一个指针类型 也就是结构体后面的指针类型 但是链队列有两个指针要定义 所以先将结点的指针定义出来 然后将两个指针（队头尾指针）定义在一个结构体里 但是链表的表示都是用头指针来表示 所以接下来就会用LinkQueue来表示链表 （因为头指针包含在里面），如下图

实际上 第二个结构体定义只是对第一个结构体里面的第二个重命名（也就是*Queueptr）做一个拓展 本质上还是第一个结构体即可 第二个结构体均属于指向第一个结构体的指针类型 没有第二个结构体的话 在程序里仍然可以定义指向第一个结构体的指针

顺序表

对于顺序表 因为数组本身就是一个顺序表 所以 结构体定义时着重定义整体（定义一个顺序表会用到哪些数据 不同于链表只定义结点 ） 数组只是其中的一个属性

第一个指针 用来接收数组的首地址 也就是new数组时 接收new出来的地址 而该指针也就是数组名了
第二个元素是数组长度

补充：Sq是顺序的意思
顺序表命名为 SqList
顺序栈命名为 SqStack
顺序队列命名为 SqQueue

顺序表

链表

插入删除算法

步骤
1.通过循环到达指定位置的前一个位置
2.新建目标结点 (或删除目标结点)
3.建立新的结点联系

插入

因为可以在尾部追加 所以要考虑指定位置的前一个位置 如果前一个位置有值 那么就合法 所以while循环以及if循环里条件都是p 因为p是指定位置的前一个位置

删除

而删除算法没有追加 所指定的位置必须有值 才合法 所以考虑前一个位置p的后继 也就是p->next 所以while和if的条件都是p->next;

!!!总结
可以理解为if里面的条件 整体对while取反 因为while里的条件都是满足步骤1的条件 所以取反 也就意味着不满足步骤1条件的
当执行完while以及if之后 步骤1才算真正的结束
注意 p初始位置是L j初始值为0

栈

辅助栈 可以使在栈中寻找最小值的时间复杂度为o（1）

队列

对于链表栈出队时的一个注意点

双或运算符

双或 只有全部是假的时候 整体才是假 只要有一个真 那整体就为真

字符运算(实质为ascii表的运算)

字符可以直接加减 012345这些字符的ASCII码都是挨着的 直接减即可 但是因为数字本身就有一定基础的ASCII数值 比如’0’的ASCII码并不是0 所以 进行加减的时候 要减去一个’0’ 这样才会符合数字的运算

求长度函数

对于普通数组 可以用sizeof（num）/sizeof（num【0】）

注意：sizeof的办法不能求已经定义好的数组的长度 因为这样的话 sizeof（数组）就是你定义的长度的字节数

二分算法

详细解答：https://blog.csdn.net/qq_45978890/article/details/116094046

冒泡排序

选择排序

下面两张图是优化

可以通过交换函数进一步优化 如下图

因为每次外层循环后 都将i的值赋值给了max 所以比较时 用arr【max】还是max【i】都一样
注意数组的长度 在不用容器的前提下 只能通过参数传进去函数 而不能计算出 因为一旦传入数组 数组就变成了指针 就丢失了原本的长度

递归

简介

例1：

找到出口 以及递归的规则
出口：包括可以返回true的条件
可以返回flase的条件

递归规则：要返回函数递归 传入参数时 要传入依次递归规则下的结果值
如上图
例2：

当函数返回值为数时 或者说题目是一个数的计算的递归
那么考虑出口是最基本的不可再分的单元数 并返回其对应的值

+1

如果递归不是计算数 而是每一步要有一个操作时 这些操作放在递的部分 最终归的时候 可以随便返回一个值 无所谓 因为不牵扯到数 只要不再进行函数自身调用即可
一般操作类递归 该操作部分可以没有返回值 但是归的部分必须按上一行所说执行

+2

考虑两点：
一是出口
一般一些不符合条件可以跳出
基本单位无法再分时的情况可以跳出

二是递归规则：
只需要将其归纳概括为几个大的部分 从最大层考虑是怎么样的规则

new二维数组

方式1

！！ 记得释放之后 把指针指向NULL
定义一个指针类型为基本元素的数组,再对每个元素分别都new一个数组并且用数组的元素名接住

注意 最后析构的时候 也要把每个数组名的数组都析构掉 并且析构掉大数组

(可以参照new一维数组的方法来对照着记二维数组)

new后面是每个元素的数据类型 当数据类型加了一个星星的时候 每个元素的数据类型就变成了指针 这样就可以对每个元素再次进行new了
当看到后面加了星星 前面补一个*就可以

方式1的初始化

直接在对行进行new的时候 最后加上一个中括号 可以啥也不写 或者填个0 就可以把数组整个初始化为0

方式2（推荐）必须指定出列数

一个指针数组 来new出来一个二维数组
new出来之后 就可以直接使用

补充：数组指针 也就是指向数组的指针

数组指针就是定义一个指针 他指向一个数组
格式： 数据类型 + （*指针名） 【所指向的数组的元素个数】
例如 int （*p） 【3】
意为一个指针p 指向一个具有三个元素的数组 同时p也被称为二级指针

通常使用数组指针来指向二维数组的某一行，于是可以用该指针来表示二维数组

代码示例：

int a[2][3] ={4,5,6,7,8,9};
int (*p)[3]=a;

for(int i=0;i<2;i++){
	for(int j=0;j<3;j++){
		cout<<"p[i][j]"<<endl;
	}
}
1
2
3
4
5
6
7
8

p指向二维数组的首元素 那么就可以用p来表示二维数组了

也可以理解为p指向了二维数组的第一行 但是指针可以递增 所以p可以++ 意为移到第二行 依次类推 p可以指向二维数组的任意一个元素

初始化问题

在C++11标准中 直接定义一个变量 那么自动初始化为0

在C++20（vs2022）标准中 定义一个变量 就必须初始化 或者后续赋值

输入字符问题

在main函数的while循环中
这里注意 读取char类型时 用字符串的方式来读入 且定义字符数组时 要定义一个以上 才能被称为数组 读取用%s 后面对应数组名 这样在读取时可以去除空格或者回车 不然要是用%c读入 会读进来空格或者回车

错题本

一组数据以0为结束标记，如何输入到数组中，并计数

输入时，先将nums[0]输入，然后进行循环，循环时，定义ij 两个循环变量 i初始化为0，j初始化为1，之后i j都要递增，结束条件是nums[i]!=0，这样可以确保结束条件的生效，不然如果只用 i 的话，nums[i]还没被赋值就拿去判断是否等于0了。
总结：循环外输入nums[0], i 始终比 j 小一，结束条件用i判断，输入语句用 j

多个数据进行比较

可以先设一个很大的数（超过本题数据范围的数）
在一个循环里，将每个数据依次在一次循环中得出，每次循环得到的结果是x，将x与ans取min，赋值给ans，这样多次循环之后，就是多个数据的最小值

链表删除重复元素的启发

图中 1、对于链表 可能系统会传入空指针进去 所以要考虑到 要加上空指针判断
2、对于while条件的设置 因为p不可以指到空指针 不然出错 所以不可以设置为p！=NULL 但是p必须最终指向最后一个结点来结束循环 所以可以设置为p->next！=NULL;
3、因为执行完if中的内容之后 还要再比较一遍处理过后的当前结点的情况 所以 在if为真时 不设置p后移
而是在else里设置p后移 这样既可以再比较一遍 还符合运行逻辑

循环体里谨慎写类型定义并初始化（一般写上就是错）

上图中 在循环里 不要定义int i = 0 ；
这样的话每次循环都会使其为0；
低级错误 只能在for循环里设置为int i= 0；

队列中读取队尾元素

数组当做形参传递到函数里之后 就不可以进行数组元素的计算了

sizeof（nums）/sizeof（nums【0】） 可以算出数组的元素个数
但是仅限于在定义数组的函数内才可以
注意：sizeof的办法不能求已经定义好的数组的长度 因为这样的话 sizeof（数组）就是你定义的长度的字节数

如果将数组作为形参 传递到函数里 那么就不可以用这种方法 因为一旦当做形参传递数组 数组就变成了指针 就不会传入整个数组的大小 所以不可以在函数里求函数外的数组的元素个数 只能在函数外求出 然后当做形参传递进去

当数组定义好了长度 如何求有效长度

利用for循环 计数器++ 求长度
终止条件（跳出循环条件）：

可以看到定义好了数组之后 不赋值的地方 就是乱码 以此为终止条件

读取字符串越界位置

越界位置为NULL

返回值是一个容器

当返回值是一个容器时 就要返回一个同类型的容器 可以定义一个函数 在函数里进行操作 之后的输出替换成向容器里面加入元素即可

ps 适用于某个算法在递归输出 而没有返回值时 可能会遇到这种情况