/*1.分析已知与未知 2.数据定义
3.输入 4.算法实现 5.输出*/
#include<bits/stdc++.h> //万能头
using namespace std; //命名空间
int main() { //主函数
cout<<"授课笔记完整版";
return 0;
}
一、基本数据类型
int a1=6,a2=int(6.9999); //整型
long long l=6666666666; //长整型
float f=3.14; //单精度
double d=3.1415926; //双精度
char c1='A',c2=char(90); //字符类型
bool b1=false,b2=true; //true真 false假
二、变量的定义与使用
int _2a; //字母、数字、下划线
数字不能开头;不能用关键字;
变量的作用域：
循环中定义的变量，只能在循环中用
三、运算符
//算术运算 加减乘除 整除 求余（模）
a+b;a-b;a*b;a/b;a%b;
//逻辑运算 与或非
与（有0则0，无0才1）
或（有1则1，无1才0）
a&&b;a||b;!a;
//关系运算 大于、小于、等于...
a>b;a<b;a==b;a>=b;a<=b;a!=b;
//自增自减
a++;b--;
i++;先用后加；
++i;先加后用；
//三目运算 A？B:C
//if(A) {B} else{C}
四、基本语句
int a; double b; char c;
//输入输出语句
cin>>a>>b>>c;//>>向右是输入
scanf("%d %f %c",&a,&b,&c);
//格式串 d十进制整数，f浮点数，c字符
cout<<a<<b<<c;//<<向左是输出
cout<<fixed<<setprecision(2)<<b;
printf("%d %.2f %c",a,b,c);
// %.2f 代表保留2位小数
//分支语句：条件"不重复 且 不遗漏"
if...else...
if...else if...
switch(整数){
case 1: 语句;break;
case 2: 语句;break;
default: 语句;
}
从冒号:开始向下执行，遇break跳出
//循环语句 for while do...while
循环三要素：条件、初始/步长、循环体
for(初始i=1;条件i<n;步长i++){
循环体 s++;
}
初始
while(条件){
循环体;
步长;
}
初始
do{
循环体;
步长;
} while(条件)
break; 跳出本层循环
continue; 跳过本次循环
打表法解题：
表头列出关键变量，纵向变量变化过程）
五、数组：一维/二维/字符数组
1.定义（初始化） 下标从0开始
类型 数组名[长度] ={元素1,元素2...}
类型 数组名[行长][列长] ={元素1,元素2...}
int a[5]={2,4,6,8,10};
int b[5][5]={{1,2,3,4,5},{6,7,8},{}}
char c[5]={'l','w','l','$'}
2.引用
数组名[下标]
数组名[行号][列号]
a[0]=666;
b[0][0]=888;
b[1][3]=9;
c[0]='w';
3.场景
循环输入/输出 数组每个元素
//一维数组：一层循环
for(int i=1;i<=5;i++){
cin>>a[i];
cout<<a[i]<<" ";
}
//二维数组：二层循环
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
cin>>a[i][j];
cout<<a[i][j]<<" ";
}
}
六、字符数组 与 字符串类
1. 定义（初始化）
1)字符数组 写法：
char c[20]="Hello World "; //字符串 赋值
cin.getline(字符串名,长度);//输入含空格字符串
cin.getline(c,5);
2)字符串类 写法：
string c="Hello"; //字符串 赋值 默认尾部加'\0'
getline(cin,字符串名);//输入含空格字符串
getline(cin,c);
2.相关函数与操作
1)字符数组 函数：
char c1[20]="hello",c2[20]="World";
strcat(c1,c2);//拼接concatenate
strcpy(c1,c2);//复制copy
strcmp(c1,c2);//比较compare
strlen(c1);//字符串长度length
strlwr(c1);//转小写 low 非标准库函数
strupr(c1);//转大写 up 非标准库函数
2)字符串类 操作
string s1,s2;
s1=s1;//赋值
s1+=s2;//拼接
s1==s2;s1!=s2;//判断是否相等
s1<s2;//判断大小
s1.empty();//是否为空
s1.length();//返回字符串长度
七、函数
（一）标准函数：
abs() 求绝对值 abs(-4) 返回4
sqrt() 开平方根
max() 求最大值 max(5,6); //返回6
min() 求最小值
ceil() 向上取整
floor() 向下取整
（二）自定义函数：
1.函数的定义：
返回类型 函数名（参数列表）{
函数体 //执行语句
}
int add(int a,int b){
return a+b;
}
2.声明与引用；
函数名(参数列表);
传值/传址；
作用域
八、结构体与sort排序
1.定义（初始化）
struct 结构体类型名{
类型 要素1名;
类型 要素2名;
...
};
struct stu{
int num;
char male;
};
stu j;
2.引用 变量名.要素名
j.num=666;
3.场景
与sort排序结合运用
4.sort排序
sort(数组起始下标,数组结束下标+1,自定义排序规则)
bool cmp(int a,int b){
return a<b;
}
int a[6]={3,1,4,2,7,8};
sort(a+0,a+5+1,cmp);
九、指针（变量）
1. 定义（初始化）
类型名 *变量名
int *p=NULL;
int a;
p=&a; //&取地址
*p=20; //*取值
2.引用
3.场景（数组、字符串、函数...）
设有数组 a，指向 a 的指针变量为 pa，
则有以下关系：
pa、a、&a[0]均指向同一单元
指针与字符串：
const char* s = "program";
for (int i = 0; i < 7; i++)
cout << *(s + i);
十、进制转换
（一）R进制>十进制：按权展开求和
位高权重
一个数的负数次幂=该数的正数次幂的倒数
任何数的零次幂=1
pow(x,y)=x的y次幂
(1101)2 = (13)10
（二）十进制>R进制：整数(取余倒序)
异或
进制（满几进位）
十一、算法：自然语言、流程图、伪代码
赋值：箭头
十二、队列
1.定义：只能一端插入另一端删除的线性表
2.特点：先进先出
3. STL：
声明：queue<数据类型>队名，
例如：queue<int>q
相关函数：
q.push(); 添加元素
q.front(); 获取队首元素
q.pop(); 删除队首元素
q.size(); 获取元素个数
q.empty(); 判断队列为空
优先队列:
priority_queue<数据类型> q; //声明一个用来存某数据类型的优先队列，名字叫q
相关函数（其他同队列）：
q.top(); 获取队首元素，队列用的是q.front();
priority_queue<int>q; //默认是大的先出来
priority_queue<int,vector<int>,less<int> >q1; //大的先出来
priority_queue<int,vector<int>,greater<int> >q2; //小的先出来
4.自己写：（详见后附）
十三、栈
1.定义：只能一端插入或删除的线性表
2.特点：先进后出
3. STL：
声明：stack<数据类型>栈名，
例如：stack<int>s
相关函数：
s.push(); 元素入栈
s.top(); 获取栈顶元素
s.pop(); 删除栈顶元素
s.size(); 获取元素个数
s.empty(); 判断栈为空
4.自己写： （详见后附）
十四、顺序表
//顺序表基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef int ElemType;
typedef struct
{ ElemType data[MaxSize]; //存放顺序表元素
int length; //存放顺序表的长度
} SqList; //顺序表的类型
void CreateList(SqList *&L,ElemType a[],int n)
//建立顺序表
{
L=(SqList *)malloc(sizeof(SqList));
for (int i=0;i<n;i++)
L->data[i]=a[i];
L->length=n;
}
void InitList(SqList *&L)
{
L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间
L->length=0;
}
void DestroyList(SqList *&L)
{
free(L);
}
bool ListEmpty(SqList *L)
{
return(L->length==0);
}
int ListLength(SqList *L)
{
return(L->length);
}
void DispList(SqList *L)
{
for (int i=0;i<L->length;i++)
printf("%d ",L->data[i]);
printf("\n");
}
bool GetElem(SqList *L,int i,ElemType &e)
{
if (i<1 || i>L->length)
return false;
e=L->data[i-1];
return true;
}
int LocateElem(SqList *L, ElemType e)
{
int i=0;
while (i<L->length && L->data[i]!=e) i++;
if (i>=L->length)
return 0;
else
return i+1;
}
bool ListInsert(SqList *&L,int i,ElemType e)
{
int j;
if (i<1 || i>L->length+1 || L->length==MaxSize)
return false;
i--; //将顺序表位序转化为elem下标
for (j=L->length;j>i;j--) //将data[i]及后面元素后移一个位置
L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++; //顺序表长度增1
return true;
}
bool ListDelete(SqList *&L,int i,ElemType &e)
{
int j;
if (i<1 || i>L->length)
return false;
i--; //将顺序表位序转化为elem下标
e=L->data[i];
for (j=i;j<L->length-1;j++) //将data[i]之后的元素前移一个位置
L->data[j]=L->data[j+1];
L->length--; //顺序表长度减1
return true;
}
十五、二分法
使用前提：有序性
核心代码：
mid=l+(r-l)/2; //取中点值
r=mid-1; //向左半找
l=mid+1; //向右半找
典型题目：
二分查找：P2249
二分答案：
P1873 砍树
P2440 木材加工
P1577 切绳子
P1102 A-B数对
P1824 进击的奶牛
P1182 数列分段 Section II
