算法学习之C/C++篇
前言:C、C++虽然一直都在接触,但是突然发现自己好像从来没有系统地去建立对于他们的认识,也可能是因为大一的时候对于C、C++的书本式学习让我轻视了他们,但是作为无数程序员入门的程序设计语言而言,这两门语言总是有不同的意味存在。。。
当然了,在此也感谢那些年帮助过我的 网络导师/网站/网课 们,也正是这些网络资源的存在,才能让菜鸟新手更快地入手程序设计,并且进入到编程的美丽世界中 ~
快速入门
常见头文件
这里也是直接给出 C、C++ 头文件的模板
一个提醒:少用万能头文件,一般来说,非 考试/竞赛 ,最好别用
原因:会增加编译时间,其次就是有的环境可能不支持,并且还不可移植
#include <bits/stdc++.h>//万能头文件
C
常用于单片机,特别是51单片机,当然了单片机中也有自己不同于纯粹的C语言的地方所在,这就需要在实践中才能体会得到了。
#include<studio>//包含:输入scanf、输出printf等
#include<math.h>//一些常见的数学运算函数
C++
用途广泛,也能用于一些单片机,如STM32,并且具有一些C不具有的方便特性,总体来说,是向C语言兼容的,这保证了能使用C语言的许多特性。
#include<iostream>//头文件,给予使用部分功能的权限
using namespace std;//为了解决命名冲突的问题而引入的概念
//前面两行声明包含:标准输入/输出流对象(cin、cout)
问:iostream 是在 STL 之前就诞生了,为什么 iostream 也要放进 std ?
答:事实上,在当初还没有标准库的时候,iostream 库真就是直接用的。不需要加 std 。那时候的标准用法还是 #include <iostream.h> 如果你这样用,那就确实不需要加 std 。
【C++标准程序库中的所有标识符都被定义于一个名为std的namespace中(与#include<>概念上类似)】
后来有了 STL 之后,为了统一起见,就把 iostream 库也放进了 std,写法也去掉了后缀成为 #include <iostream>。
但如果你还需要兼容旧有代码,如果你的代码是在还没有发明 std namepsace 之前撰写的,那可以使用 #include <iostream.h> 这种带后缀的形式,这种形式是不需要加 std 的。
结论:现代C++,想用cin、cout都需要用到这两行声明
语法与特性
这里就不多加强调了,无非就是循环、选择等结构,再加上一些函数的调用及传参
故:在此也只重点强调我之前 忘记 或 忽略 的语法及用法
参数传递
往函数中传递参数并在函数中进行这些传递的参数的运算 是经常我们需要函数为我们做的工作,但是我们必须要充分了解 形式参数、实际参数 的概念,才能更好的掌握运用函数
在这里直接给出两个例子
//利用”指针“传递地址
void test(int *a) {
*a = 100;
}
int main(){
int b = 200;
test(&b);//&b是在求变量b的地址,此处是传入函数变量的地址(&b)到函数中
cout << b << endl; //结果为:100
}
这里不利用 ”指针“ 或 ”引用“ 方法,就不能让传递到函数内的形式参数被实际的改变值,因为不采用这两种方法时,参数值是被复制到栈区的新建数据中,等此次函数结束后就被释放了,根本就不涉及实际参数的值的变化;
而使用 ”指针“ 或 ”引用“ 方法,从本质上来说都是让函数直接涉及到传入变量的真正的地址去进行操作,自然能够对变量进行真正的改变。
//利用”引用“对变量进行操作
void test(int &a) {
a = 100;
}
int main(){
int b = 200;
test(b);//&b是在求变量b的地址,此处是传入函数变量的地址(&b)到函数中
cout << b << endl; //结果为:100
}
字符与整型
字符型与整型转换,实际上就是ascii码间的转换
且字符都是按照ASCII码来排序的【小写字母英文字母比大写英文字母大32】
//pl1
char x =‘a';
cout<< x-1 ; //输出结果是字符a的ascii码减去1
//pl2:
char c1='a' ;
char c2='A' ;
cout<<c1<<" "<<c2;//输出结果是 a A
c1=c1-32;//变为大写字符A的ascii码:小写字母a的ascii码减少32
c2=c2+32;//变成另外的字符【详情见ASCII表】
//注意:此处是由于对char型字符进行了+-运算,才使其强转为其对应ascii码并进行ascii码间的+-运算
这里再给出一个例子:
‘a’ 如果用于运算,则代表的是它所对应的ascii码之间的运算 如:
char
转换到int
的变化‘3’ - ‘0’ 代表的是字符型的 3 和 0 的ascii码之间的差值=
int
型数字的3【即两个字符的ASCII码之间的差值】而 3 + '0' 则完成了
int
转变为char
的变化
int main() {
//在此处,如果char型x为字母a,则输出的整型数h的值为a的ascii码与0的ascii码的差值
char x;
int h = 0;
char s ;
cin >> x;
h = x - '0';
//而s则为重新转换为char型的过程
s = h + '0';
cout << h << endl;
cout << s;
}
I/O
不论是实际运用中的调试,还是算法刷题,I/O可以说是不可或缺的一环,换句话说,熟练使用I/O,你至少能够做一个I/O自由的程序员,而不是做一个编程世界的“哑巴”。
cin、cout
C++独有特性
C++只要涉及输入或者输出数据,我们立马想到的就是 cin 和 cout。
其实,cin 就是 istream 类的对象,cout 是 ostream 类的对象,它们都声明在 <iostream>
头文件中,这也解释了“为什么在 C++ 程序中引入 <iostream>
就可以使用 cin 和 cout”
(当然,使用 cin 和 cout,还需要声明 std 命名空间,它们都是 C++ 标准库的开发者创建好的,可以直接拿来使用,这种在 C++ 中提前创建好的对象称为内置对象)。
cout运用
运用案例
cout<<setiosflags(ios::left|ios::showpoint); // 设左对齐,以一般实数方式显示
cout.precision(5); // 设置五位有效数字
cout<<123.456789<<endl;
cout.width(10); // 设置显示域宽10
cout.fill('*'); // 在显示区域空白处用*填充
cout<<resetiosflags(ios::left); // 清除状态左对齐
cout<<setiosflags(ios::right); // 设置右对齐
cout<<123.456789<<endl;
cout<<setiosflags(ios::left|ios::fixed); // 设左对齐,以固定小数位显示
cout.precision(3); // 设置实数显示三位小数
cout<<999.123456<<endl;
cout<<resetiosflags(ios::left|ios::fixed); //清除状态左对齐和定点格式
cout<<setiosflags(ios::left|ios::scientific); //设置左对齐,以科学技术法显示
cout.precision(3); //设置保留三位小数
cout<<123.45678<<endl;
cout << fixed << setprecision(4) << value << endl;
// 加了fixed意味着是固定点方式显示,所以这里的精度指的是小数位,输出为12.3457
输出
123.46
****123.46
999.123
1.235e+02
12.3457
cout.setself 常见的标志
cout.oct、cout.scientific等
cin运用
普通输入时:
cin>>
自动跳过“tab,回车,空格”来读取要输入的内容不想略过空白字符,那就使用 noskipws 流控制。如
cin>>noskipws>>input
的值getline(cin,test)
:将缓冲区内的内容存储到到test参数中(包括空格 换行符等)不阻塞,直接读取缓冲区的数据(如果缓冲区中有数据的话:包括换行符和空格等)cin.get
的用法char a; a = cin.get(); //或 cin.get(a); cout<<a<<endl;
只读取一个字符,可以使用
cin.get
或cin.get(var)
cin.get()
的返回值是int
类型,成功:读取字符的ASCII码值,遇到文件结束符时,返回EOF,即-1cin.get(char var)
如果成功返回的是cin
对象
说明:
(1)
cin.get()
从输入缓冲区读取单个字符时是不忽略分隔符的【包括换行符、tab、空格等】,会直接将其读取(读入缓冲区)(2)
cin.get()
和scanf("%s %s", ch1, ch2) != EOF
一个道理,如这个表达式:
scanf("%d%d",&a,&b)!=EOF;
如果a和b都被成功读入,那么上面表达式的结果为2;
如果只有一个读入,那么上面表达式的结果为1;
如果 a 和 b 都没有读入,那么上面表达式的结果为0(若a没有读入,则直接放弃b的读入);
如果遇到 错误 或 文件结尾 ,那么上面表达式的结果为EOF,对应的有符号数是 -1;
【Windows下标准输入输入文件结束符为Ctrl+z,Linux为Ctrl+d】
问:那么什么时候会输出EOF?
答:在stdio.h中
EOF
被宏定义为 -1,按照说明,scanf函数只有在第一个参数为NULL(空指针)的情况下,才可能返回EOF,否则,返回成功格式化并赋值的参数个数(>=0)。(回车就相当于第一个参数为NULL)
cin.getline
读取一行函数作用:从标准输入设备键盘读取一串字符串,并以指定的结束符结束。
cin.getline
与cin.get
的区别:cin.getline
不会将结束符或者换行符残留在输入缓冲区中。cin.getline(array,20); //或 使用下面一行来指定结束符 //cin.getline(array,20,'\n');
常见排序算法
冒泡排序
//数组a[]中有10个元素
int a[10] = {0};
int k=0;
int len = sizeof(a)/sizeof(1);
while(len--) cin>>a[k++];
//len个元素只需要len-1次排序即可排序完成
for(int i=0; i<10; i++){
for(int j=0; j<9-i; j++){
//这里是升序排序,如需降序排序则改变判断条件即可
if(a[j]>a[j+1]) swap(a[j],a[j+1]);
}
}
for(int i=0; i<10; i++) cout<<a[i]<<" ";
快速排序
//升序合并
int hebing(int a[], int l, int r){
int mid = a[l]; //保存中枢元素
while (l < r) {
while (a[r] >= mid && l < r) r--;
a[l] = a[r];//将比mid小的元素放到左端
while (a[l] <= mid && l < r) l++;
a[r] = a[l];//将比mid大的元素放到右端
}
//完成循环后l==r,即:到达了此次排序中枢元素mid的最终位置
a[l] = mid;//将此次排序中的中枢元素mid放到他的最终位置上
return l;//并返回这个最终位置【数组被这个最终位置分为两个部分:左半部分<mid,右半部分>mid】
}
//降序合并
int rhebing(int a, int l, int r){
int mid = a[l];
while (l < r) {
while (a[r] <= mid && l < r) r--;
a[l] = a[r];//将比mid大的放到左端
while (a[l] >= mid && l < r) l++;
a[r] = a[l];//将比mid小的放到右端
}
a[l] = mid;
return l;
}
//升序(递归)快速排序
void qsort(int a[], int l,int r){
if (l >= r) return;
int m = hebing(a, l, r);
qsort(a, l, m - 1);
qsort(a, m + 1, r);
}
//降序(递归)快速排序
void rqsort(int a[], int l, int r){
if (l >= r) return;
int m = rhebing(a, l, r);
rqsort(a, l, m - 1);
rqsort(a, m + 1, r);
}
int main(){
int a[] = { 40,34,201,54,11,21,20,34,6,76 };
printf("升序-排序 前:\n");
for (int i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
printf("\n");
printf("升序-排序 后:\n");
qsort(a, 0, 9);
for(int i=0; i<10; i++){
printf("%d ", a[i]);
}
printf("\n");
printf("降序-排序 后:\n");
rqsort(a, 0, 9);
for (int i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
return 0;
}
常见函数使用
向上求整数
#include<math.h>
t=ceil(s/v);
c++中默认是向下求整,即会忽略余数,而使用ceil( )函数后,会使余数进一,以达到向上取整的效果