《竞赛入门经典》1-5章语言篇总结（一轮）

淡淡的烟草味﹌ 2022-02-25 04:52 130阅读 0赞

碎碎念：虽然自己学校开设了各类语言算法的课程但是真的太浅显了，而且时间一长也忘得差不多了。大三了，然而自己的算法水平几乎可以被随便一个985/211计算机专业的大一生秒杀，嗯——那就从头补吧！  
本篇blog主要是总结紫薯1-5章自己模糊的零碎知识点。

--------------------

**第一章**  
之前看的忘记做笔记了，为了赶进度，第二轮的时候再补一遍笔记。

--------------------

**第二章 循环结构**

*  浮点运算可能出现误差，一般改为四舍五入，例如int m=floor（x+0.5）  
    floor(x)表示不大于x的最大整型数，其中x的类型为double;
 *  当算法没错，答案出现问题时，很有可能时数据范围不对 比如int-long long scanf有返回值，返回的就是输入的个数
 *  循环输入：`while(scanf(“%d”,&x)==1)`
 *  文件的输入输出 freopen(“input.txt”,”r”,stdin);  
    freopen(“output.txt”,”w”,stdin); 关于重定向相关问题还不是很明白，之后写几道题体会一下。  
    某位博主的重定向相关总结：[https://blog.csdn.net/liangllhahaha/article/details/79243145][https_blog.csdn.net_liangllhahaha_article_details_79243145]

--------------------

**第三章 数组和字符串**

*  数组a\[n\]，一般声明在main（）外面，这样才能把数组开得很大，如果在里面稍大就会异常退出，且n是常数，一般比题目要求的开大5个点。
 *  将数组a的k个数复制到数组b中去：`#include<string.h> memcpy(b,a,sizeof(int)*k);`  
    //全部复制的话就省掉k即可；若 a、b都是浮点型的，复制时要写成`memcpy(b,a,sizeof(double)*k)`
 *  char s\[20\];//字符是一种特殊的整数  
    \-对比：`scanf(“%d”, &n); scanf(“%s”, s);`  
    读入一个不含空格、TAB、回车符的字符串，存入字符数组s。注意， s 前面没有&；但遇到空白字符会停下来； 可以用scanf(“%s”, s\[i\])读取第i个字符串 %5d表示按照5位数打印，不足的前面补0
 *  strchr ： 在一个字符串中查找单个字符；  
    printf：输出到屏幕  
    fprintf：输出到文件  
    sprintf：输出到字符串，且要保证写入的字符串有足够的空间->字符个数+1 strlen(s): 获取字符串的实际长度；
 *  \#include<string.h>  
    字符串数组 strcpy（a,b）  
    赋值 strcmp（a,b）  
    比较 strcat（a,b）  
    连接不要滥用++ – 容易出错
 *  fgetc(fin)  
    可以从打开的文件fin中读取一个字符。一般情况下应当在检查它不是EOF(文件结束fgetc将返回EOF特殊标记)后再将其转换为char值。从标准输入读取一个字符可以用getchar，它等价于fgetc(stdin)
 *  不同操作系统的回车换行符是不一样的，所以需要把自己的程序写得更鲁棒
 *  fgets(buf,maxn,fin) 读取完整的一行放在字符数组buf中，应当保证buf足够放下文件的一行内容。除了在文件结束前没有遇到 \\n 这种特殊情况外，buf总是以 \\n结尾。当一个字符都没有读到时，fgets返回NULL
 *  不要用gets(), C11里面已经废除了
 *  \#include<ctype.h>  
    isalpha() 判断是否为字母  
    isdigit 判断是否为数字  
    isprint 判断一个字符是否为打印字符  
    toupper\\tolower 转换大小写

--------------------

**第四章 函数和递归**

*  结构体

struct Point {double x,y;}; 
    double dist(struct Point a, struct Point){
    return hypot(a.x-b.x,a.y-b.y);}

*  转换成用typedef

typedef struct{double x,y;}Point;
    double dist(Point a,Point){
    return hypot(a.x-b.x,a.y-b.y);
    }

*  注意函数的形参和实参，记得swap那道题。
 *  C语言用调用栈Call Stack来描述函数之间的调用关系。调用栈由栈帧Stack Frame组成，每个栈帧对应着一个未运行完的函数。在gdb中可以用backtrace命令打印所有栈帧信息。若要用p命令打印一个非当前栈帧的局部变量，可以用frame命令选择另一个栈帧。//？？这里还是不懂
 *  `*a=*a+1 == (*a)++ !=*a++` //因为++优先级高于\*，会被解释成（\*a++）  
    `while(scanf("%s%s",s1,s2)==2)`//一边输入一遍计算 这个方法要记住  
    `for(int i=0;i<n;i++)c1[s1[i]-'A']++;`//统计不同字符数量 太强大了
 *  把较大的数组放在main函数外：  
    局部变量也是放在栈堆段的。栈溢出不一定是递归调用太多，也可能是局部变量太大。只要总大小超过了允许范围，就会产生栈溢出。
 *  自顶向下： 先写程序框架 再写细节

--------------------

**第五章 C++与STL入门**

*  C++中更推荐用const声明常数而不是\#define；但是 string sstream特别耗时

while(getline(cin,line))//读一行数据
        	{
        		int sum=0,x;
        		stringstream ss(line);//用这一行创建一个字符串流
        		while(ss>>x) sum+=x;//然后只要像读取cin一样读取ss
        		cout<<sum<<"\n";
        	}

*  struct this是当前指针 忘得差不多了，得敲一下代码巩固一下
 *  STL初步 `int p=lower_bound(a,a+n,x)-a;`//在已排序数组a中寻找x  
    `lower_bound`:用于查找大于或等于x的第一个位置 sort(a,a+n);
 *  vector 是一个不定长数组

sort(v.begin(),v.end());//vector 
        vector<int>a ;
        vector<double>b ;
        vector<string >c;
        a.size() //读取其大小 
        a.resize() //改变大小
        a.clear()//清空 
        a.push_back()//向尾部添加元素 
        a.pop_back()//删除最后一个元素
        b.empty（）//测试是否为空;

*  集合 set 就是数学上的集合 元素只能出现一次，但是和sort一样，如果是自定义类型，必须定义“小于”运算符？这句话没懂

while(ss>>buf) dict.insert(buf);//set集合dict是会自动从小到大排序的
    for(set<string>::iterator it=dict.begin(); it !=dict.end(); ++it)
    		cout<<*it<<"\n";

*  iterator 是迭代器 相当于指针，一般用来遍历vector数组
 *  映射 map就是从键key到值value的映射。因为重载了\[\]运算符，map像是数组的“高级版。列入可以用一个map<string,int>month\_name来表示“月份名字到月份编号的映射，然后用month\_name\[“July”\]=7 这样的方式来赋值。
 *  set头文件中的set和map头文件中的map分别是集合和映射。二者都支持insert、find、count、和remove操作，并且可以从小到大顺序循环遍历其中的元素。map还提供了\[\]运算符，使得map和数组一样使用，被称为“关联数组“  
    STL中map用法详解: [https://blog.csdn.net/DaveBobo/article/details/77801405][https_blog.csdn.net_DaveBobo_article_details_77801405]
 *  栈 STL的stack头文件提供了栈，用 `stack<int>s`方式定义，用push\{\}，pop\{\}实现出栈入栈 top\{\}取栈顶元素但不删除
 *  队列 头文件是queue 用 `queue<int>s`定义 push pop都可用 但是是front（）取队首元素
 *  优先队列 头文件也是`<queue>` 用`priority_queue<int>pq`来声明。pq是一个“越小的整数优先级越低的优先队列”，由于出队元素并不是最先进队的元素，所以出队芳芳由queue的front（）变成了top(),自定义类型也可以组成优先队列，但必须为每个元素定义一个优先级。这个优先级不需要一个确定的数字，只需要能比较大小即可

//例如 定义一个结构体cmp，重载（）运算符
    //然后用 priority_queue<int,vector<int>,cmp>pq的方式定义
    struct cmp{
    	bool operator() (const int a,const int b)const//a的优先级比b小时返回true
    		{
    			return a%10>b%10;}
    }

*  STL提供了更简单的定义方法 定义越小整数优先级越大：

priority_queue<int,vector<int>,greater<int> >pq

*  使用count，返回的是被查找元素的个数。
 *  注意：map中不存在相同元素，所以返回值只能是1或0。
 *  使用find，返回的是被查找元素的位置，没有则返回map.end()。
 *  测试STL 也可能有bug 使用之前测试库是一个好习惯 随机数发生器 头文件 cstdlib rand()  
    它生成一个闭区间\[0，rand\_max\]内的均匀随机整数  
    其中RAND\_MAX至少为32767.如果要生成更大的随机整数，在精度要求不太高的情况下可以用rand()的结果放大得到.  
    可以用cstdlib中的srand初始化随机数种子。如果需要程序每次执行时使用不同的随机数，可以用ctime中的time（NULL）为参数调用srand。一般只在程序执行的开头调用一次srand:  
    srand(time(NULL))
 *  把vector作为参数或者返回值时，应尽量改成引用方式传递参数，以避免不必要的值被复制。P123
 *  测试时往往使用assert，用法时assert(表达式)，当表达式为假时，强行终止程序并给出错误提示

--------------------

实际上这篇笔记是我3月份总结的，现在4月份来看有些地方就又看不懂了，真的算法还是得通过做题来强化知识点。  
待更新：1-5章自己不明白的算法题之后更新（原先笔记中算法的也记得总结）

[https_blog.csdn.net_liangllhahaha_article_details_79243145]: https://blog.csdn.net/liangllhahaha/article/details/79243145
[https_blog.csdn.net_DaveBobo_article_details_77801405]: https://blog.csdn.net/DaveBobo/article/details/77801405