文章目录

Cpp编程(写于19年5月)

由 笔尖 发布

1、(-8)/5=-1

2、%.2f输出中,.2代表保留两位小数部分。

5、c语言创建Π:

const float pi = acos(-1);

6、sin、cos函数参数传入弧度制。

7、可以通过输出中间结果的方式观察程序会在哪一步出错,使用计时函数分析时间复杂度。

printf("Time used = %.2fn",(double)clock()/CLOCKS_PER_SEC);

8、window下scanf输入可以通过ctrl+z、回车结束,linux下ctrl+d结束。

9、通过修改输出输出重定向的方式可以更加方便的进行数据的测试。

10、使用下面两条语句用于重定向标准输入、标准输出。

freopen("data.in", "r", stdin);

freopen("data.out", "w", stdout);

如果不允许重定向,就使用文件读取的方式。

fin = fopen("data.in", "rb");

fout = fopen("data.out", "wb");

fscanf(fin, "%d", &x);

fprintf(fout, "%d %d %.3f", min, max, (double)s / n);

11、空间比较大的数组应声明在main函数外部,否则会异常退出。

12、printf,fprintf,sprintf,分别代表标准输出,文件输出,字符串输出。输入同理。

13、fgetc、getchar代表从文件、标准输入读取一字符fgetc(stdin)=getchar()

14、fgets(buf,maxn,fin)从文件读取maxn-1个字符到buf,其兄弟函数gets因没有指明读取多少个字符,所以被废除,可以改用fgets(buf,maxn,stdin).

15、从标准输入或者文件输入都可以使用fgetc,fgets,前者判断末尾为EOF,后者为NULL

16、scanf与fgetc,fgets的区别在于前者不会读取空串,后者会读取诸如回车、tab、空格,因此当题目输入中不含空字符串时,可以安全的使用scanf,而当一行中有空格时,只能使用后者。另外,scanf判读输入结束时使用EOF.注意scanf读取单个字符会读取空字符,因此使用该方法时,一般要在%c前加空格以匹配多个空字符。

17、c++使用sort函数(自定)快速排序,头文件为algorithm,并且需要使用变量命名空间,using namespace std,c++基本都会使用命名空间,库里的标识符位于此下。

18、isalpha等判断元类型,头文件为ctype

19、机考时间效率一般不超过1s,即时间复杂度不能高于百万级别,10^6,特别的,冒泡排序时间复杂度n^2,快速排序为nlogn。线性查找n,二分查找logn。因此一般为了节省时间,有空间换时间的hash思想。

20、C++标准模板提供栈stack<int>,头文件stack

21、优先队列可以以logn时间复杂度求得最值元素,使用C++标准模板,priority_queue<int>Q,默认为大顶队列。及取最大值。小顶队列为priority_queue<int,vector<int>,greater<int>>,头文件queue。普通队列直接使用queue初始化。

22、数据结构封装包含stack、priority_queue、queue、vector。

23、二叉树遍历分为前中后序,均可通过递归调用函数进行读取。而关于二叉树的建立则通过确定前序、中序建立。

24、二叉有序树的中序遍历一定是从小到大顺序。判断两棵树是否相同,只需比较包括中序遍历的两种遍历顺序是否相同即可。

25、a%b模运算结果符号与a保持一致,与b无关。

26、如果数据会溢出,则使用long long,在scanf和printf中使用%lld,double比float能够精确到更多位,使用%lf。

27、进制转换类问题,采用n进制转10进制(权值累乘),再转换m进制(求模取余)

28、最大公约数,a,b->b,a%b

29、最小公倍数,两数积除以最大公约数。

30、素数判断,时间复杂度为sqrt(n)

31、素数筛选法用于快速给连续区间整数标注素数。

32、搜索算法相比普通查找效率更高,也更有技巧性,BFS为广度优先搜索,需要使用到队列queue操作。状态搜索一类问题使用BFS较好,广度优先算法适合寻找最优值。

34、图可通过邻接矩阵或者邻接链表表示。矩阵适合非稀疏矩阵以及查找某节点对之间的关系建议使用邻接矩阵表示;链表的空间使用率较高,且寻找单节点的邻接节点速度快。邻接链表使用标准库vector(头文件),使用clear进行初始化,push_back尾接一个节点,erase删除指定节点。vector使用形式与数组类似(支持随机访问),且vector是动态变化的。

35、图最基础的数据结构是集合,一个集合包含了互相形成通路的所有结点,即并查集。

36、关于图论的基础操作包含:

并查集:求节点的根节点,并将在一个集合的节点根节点合一

最小生成树(kruskal算法):连通所有节点的权值最小值,根据权值由小到大依次遍历所有边,若不在一个集合,则合并两节点,该边入围。

最短路径(Floyd算法):该算法通过邻接矩阵表示节点之间的连通性和距离,并依次通过各个点判断通过该点能否找到更短的有连接关系的点。算法时间复杂度为n^3,空间复杂度为n^2,n代表节点个数,并且该算法可以一次性找完任意两点间的最短距离。

最短路径(dijkstra算法):该算法思想是通过每次在集合K中寻找下一个延申路径最短的点,每次计算都会得到一个最短路径,因此该算法时间复杂度为n^2,如果要进行多组数据测试,时间复杂度上再乘以一个n,空间复杂度为n,因此,该算法比floyd算法优异。该算法为单点源计算。

37、若判断一个图是否为有向无环图,则优先采用拓扑序列判断法,即每次剔除一个入度为0的节点,如最后所有点都去掉了,则说明是无环图。
38、关于图的搜索多数采用DFS递归调用方式,即先以一个点开始,在图中发散式搜索,再在主循环中遍历下一个点。

39、DFS相较BFS搜索方式变为立即扩展新的状态,由于这一特性使得DFS的结果不再具有最优性,因此适合解决有没有解或者多少个解这类问题。而BFS是查找最优解的方法。

40、动态规划适用于寻找递推关系,例如斐波那契数列本项是前两项数值的和,就形成了F[n]=F[n-1]+F[n-2]的递推关系。动态规划问题三要素:所有状态的表示方法、初始条件、转移过程。确定了以后,即可完成任意状态的求解,再根据题目要求得出所要结果即可。即用数组的形式表示任意状态结果,并进行状态转移。

41、数据结构封装包含stack、priority_queue、queue、vector、string和map

42、c++可直接操控string对象,头文件<string>,可直接进行+、+=操作,大小判断,使用printf输出使用string.c_str(),使用find(string,pos),在pos位置开始寻找string相等字符串,无返回-1,erase(a,b)在a位置开始往后删除b长度的字符串。

43、map内部封装了红黑树,可以帮助进行类型映射,比如map<string,int>就是将string类型变量与整型变量一一映射起来,clear进行初始化,find(str)用于寻找str是否有对应的整数,只有没找到的情况才会返回有意义的M.end(),若有,则通过[]获取整数。

标准输入输出:

while(scanf()!=EOF),while(gets()),getchar()!= EOF

scanf读取字符串时,会跳过空串;读取单个字符,读取所有

gets读取字符串,所有读取,除了最后的回车

getchar(),读取单个字符,读取所有

排序:

c++基本库sort,可以使用自定义排序规则,也可以在结构体中使用重载运算符。

霍夫曼树:

使用小顶队列,依次弹出最小的元素,每次累加,得到数的带权最短路径。

二叉树:

通过前序、中序或者中序、后序遍历可以唯一确定树的构造。

二叉排序树:

左子树<中间节点<右子树,不同的插入顺序导致前后序不同,但中序遍历结果唯一。

进制转换:

任意进制转10进制,采用权值累乘,10进制转任意进制,采用求余取模(顺序颠倒)

最大公约数:

a,b->b,a%b,直到b=0

最小公倍数:

a*b/最大公约数

素数筛选法:

通过素数的整倍数不是素数,可以一次遍历完范围内所有素数

分解素因数:

使用素数筛选法,确定范围内所有素数,然后依次遍历,得到每个素数所对应的幂次。特别的,对n!求素数,采用求商取商的方法可以得到每个素数的幂指数。

二分求幂:

高次幂的一般方法为循环幂次数,当幂次太大时,该方法不可采用,故采用对2取商求余,再累乘的办法求高次幂。

并查集:

通过双亲表示法,快速查找某些元素是否属于同一集合,并可修改。

最小生成树:

kruskal,按照边权值递增顺序选择边,同时需要满足两点不在同一个集合。

全源最短路径:

Floyd,三层循环,依次求各个点之间的最短距离,时间复杂度n3。

单源最短路径:

Dijsktral,每次从可达边选择最短的一条。

拓扑排序:

每次选择入度为0的点,去除该点,相应的点入度数量减一,重复步骤,使得最后所有点都去除掉。

广度优先搜索BFS:

顾名思义,按照一定优先级搜索结果,从待定状态中搜索最优解。

递归:

汉诺塔问题,将复杂问题转变成较小且同属性的问题。

深度优先搜索:

使用递归调用的方式,一旦扩展得到新的状态,就立即调用函数,需要注意题目是否需要回溯。除了递归,也可使用堆栈的方式。

动态规划:

通过将问题划归为最简单问题的组合,进而得到复杂问题的求解过程。用数组表示所有结果,数组索引为状态,值为结果,再通过状态转移规则和初始化的结果得到全部的状态求解

最长递增子序列:

将第i个数依次与之前的数比较,若比其大,则序列长度+1,最后,取这区间上最大的长度。

最长公共子串:

与上体类似,先求出基本元素的解,再根据两个后一元素是否相同得出递推公式。

malloc用法:

#include<malloc.h>

student node = (student)malloc(sizeof(student));

排序:

方法时间复杂度描述
冒泡排序n*n每次将最值右移
选择排序n*n每次选择最值放在头/尾
插入排序n*n每次将下一个数插在已经排好序的数组中
希尔排序
归并排序
快速排序(sort)nlogn每次选择最后的数作为基准,小的放左边,大的放右边,如此循环

查找:

方法时间复杂度空间复杂度
线性查找n
二分查找(有序)logn

素数(0,1不是素数):

方法时间复杂度空间复杂度
普通判别式n
sqrt平方根查找sqrt(n)
素数筛选法n,全部预处理

表达式求值,中缀表达式->后缀表达式:

操作符*,/+,-
栈内1536
栈外6421

数据结构(STL):

#include

stack<int> s;

S.push(i);

x = S.top();

S.pop();

S.empty();

#include

priority_queue<int> Q; priority_queue<int,vector<int>,greater<int>> Q;

Q.push(x);

x = Q.top();

Q.pop();

Q.empty();

#include

queue<int> Q;

Q.push();

x = Q.front();

Q.pop();

Q.empty();

备注:优先级队列还可适用于结构体,但需要重载>、<运算符

struct node {

int cost;

bool operator <(node a) const {

​ return cost < a.cost;

}

};

#include

vector<edge> v;

v.clear();

v.push_back(edge a);

for(i=0;i<v.size();i++){

v[i]....;

}

v.erase(v.begin()+i, v.begin()+i+1);

c++转c注意事项:原本的STL以及一些方法无法实现,需要手动实现。

1sort(快速排序)——>qsort,参数依次为:数组起始地址、需要排序的长度、元素大小、比较方法

比较方法强制要求,且有固定写法:

int cmp(const void a,const void b) {

int age1 = ((node)a).age;

int age2 = ((node)b).age;

return age1-age2;

}

2、数据结构-stack

使用struct变量+方法间接实现压栈、出栈、判空、取栈顶操作。

3、队列-queue

使用队头+队尾指针方式进行队列的入队、出队、判空、取对顶操作。

4、优先级队列-priority_queue

直接使用单链表即可。

5、邻接链表-vector

直接使用单链表即可重构。

string

1、include string

string s;

char c[]="test";

s+=c;

s+="string"

string b;

b<=s;b==s;

printf("%s",s.c_str());

for(i in s.size());

s.erase(10,8)删除

string a="abcd";

string b="abc";

int startpos=0;

pos=a.find(b,startpos); pos != string::npos

string a="aaa";

string b="bbb";

a.insert(2,b);

tolower('a');


暂无评论

发表评论