第一节_基础知识

  • STL：C++中的标准模板库

  • define和typedef

    1
    2
    3
    #define MAXNUM 9999  //宏定义，多用来替代常量

    typedef multimap<int,int> MAP; //为复杂的类型定义取别名，简化程序，也便于修改。

  • 类型取值范围

类型 字节数 取值范围
int 4 -2^31~2^31-1(-21亿~21亿)
long long 8 -2^63~2^63-1(很大)
float 4 3.4x10^-38~3.4x10^38(绝对值)
double 8 1.7x10^-308~1.7x10^308(绝对值)
char 1 -128~127
bool 1 true/false

  • double类型比较相等：相减->是否小于一个很小的数(0.00001)。
    比大小：直接> < 比较即可。

  • 求字节数：sizeof(int)/sizeof(n)

  • 反斜杠\，转义字符、win下地址路径；正斜杠/，网址路径。

  • 字符型和整型数据可以相互转换，整型->字符型：只留最右边8位，再转成ASCII码。

  • 常用ASCII码：
    ‘0’-‘9’：48-57
    ‘A’-‘Z’：65-90
    ‘a’-‘z’：97-122

  • 十六进制常量：0x打头,0xFFA，1个十六进制位对应4个二进制位。
    表示二进制：转化为16进制。00101011->0x2b

  • 八进制整型常量：0打头，0677,1个八进制位对应3个二进制位。

  • 位运算
    单独对某些比特进行操作
    与&：将某些位置0、获取变量中的某一位
    eg：判断n的第7位是否为为0，n&0x80==ox80？

或|：将某些位置1

异或^：相同为0不同为1。将某些位按位取反，其他位不变：取反的与1异或，其他与0异或。

非~：按位取反。

左移<<：左移n位即乘2的n次方，但比乘法要快很多。

右移>>：除2的n次方，且向小取整。高位补符号位。

第二节_数据结构

数组

初始化：类型名 数组名[数量]={x1,x2,x3,x4..} 或 用for循环初始化。
数组越界编译器不会报错，会根据内存地址去访问，数组名即相当于内存地址。
编程技巧：可用数组取代复杂的switch case分支结构

字符串

  • 字符串三种形式
    1、字符串常量，双引号括起来””。
    2、存放在char数组中，以’\0’结尾，多占一个数组元素。
    3、string对象，c++标准模板库中的类。
    注：char数组比string快，但char数组没法传字符串值，只能传数组首地址。因此在一些需要传值的场合，用string更合适。

字符串在内存占的字节数等于字符数目加1(‘\0’的存在 )
读入字符串：cin或scanf，读到空格为止。空格后内容在下一次cin读入。
读一行：cin.getline(char buf[],int bufSize)，读入不超过bufsize-1个字符

结构体struct

1
2
3
4
5
6
7
8
9
10
11
struct Student{
    unsigned ID;
    char name[10];
    float fGPA;
    Student* frd;//成员可以是结构体的指针
};

Student s1 = {1234,"TOM",...};//初始化
cout<<s1.ID;
Student* s2;
cout<<s2->ID; / cout<<(*s2).ID;指针访问成员

变量

局部变量：定义在函数内部、语句块内部的变量。
全局变量：定义在函数外部(main函数外)，在所有函数中均可使用。默认初始化为0.
静态变量：全局变量和static定义的变量。生存期一直持续到整个程序结束。
PS：若未初始化，静态变量默认赋值为0，非静态变量值为随机的。

switch case

1
2
3
4
5
6
7
8
9
switch(表达式){
    case x1:
    break;  //有无中括号都可以
    case x2:
    break;
    //...
    default:
    break
}

第三节_函数与输入输出

函数

1
2
3
4
5
6
7
8
9
10
11
函数定义：
int fun(int a, char c)
{
    //函数体
    return xx ;
}

函数声明：(无函数体，常写在开头)
int fun(int a, char c);
int fun2(int a[]);//一维数组作形参，不用写大小。int a[]与int *a等价。
int fan3(int a[][3])//二维数组作形参，行数不用写，列数必须写

函数的形参是实参的拷贝，形参的改变不会影响实参。(除非形参是数组、引用或对象)
string类型也是传值
数组作形参传的是首地址，并非整个数组。

printf、scanf格式化输入输出

比cin/cout效率高，尽量使用。
%：类型占位符

格式字符 说明
%d int类型
%c char类型
%f float类型
%lf double类型
%.xlf 输出x位小数 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>   //头文件
printf("这是字符型数据%c，这是int型数据%d"，ch,i);  //格式化输出

scanf("%d%d", &n, &m);  //记得加&，返回值是接收变量的个数
char c[20];
scanf("%s",c); //读入字符串，检测到/0结束

//返回值为EOF(-1)时说明输入结束
while(scanf(xxx) != EOF){
    //循环读入数据
}

cin.peek()   //看一个字符不取走
cin.putback(c)  //把字符放回输入流头部

scanf函数读空格和换行：
如果是%d、%f数值类型，会自动跳过多余的空格和换行，如果是%c会读入空格和换行。

freopen重定向

将输入由键盘重定向为文件(不用每次都输入测试数据)

1
2
3
4
freopen("c:\\xxx.txt"，"r",stdin);
while(scanf(...)!=EOF){
    //从txt文件中输入
}

cin函数

cin >> n >> m;
返回True(成功接收所有输入)或false()
while(cin >> n){
//循环读入数据
}
注：cin读入的格式由后面的变量决定，若为char即读入一个字符，int则读入一个整数(遇到空格/换行为止)

第四节_指针

  • 指针
    1
    2
    3
    4
    5
    6
    指针变量，4个字节，内容表示一个内存地址。
    int *p; //p类型：int *，*p的类型：int
    char c1 = 'A';
    char *pc = &c1; //pc指向变量c1
    //*：间接引用运算符。&：取地址运算符。
    //&x：变量x的地址，就是指向x的指针，类型是 T*。

指针的意义：不需要通过变量，即可自由访问内存空间。

  • 指针互相赋值
    不同类型的指针，如果不经过强制类型转换，不能直接相互赋值。 (每个指针类型还代表着一次向内存读/写多少字节)
    char c = ‘A’;
    int     p = (int )c; p=122; //此时’A’后面三个字节的值也会被改变。

  • 指针的运算

  1. 指针比大小：比p1和p2地址的大小
  2. 指针相减：p1-p2=(地址p1-地址p2)/sizeof(T)
  3. p+n=p+n*sizeof(T)，结果还是指针。
  4. p[n]=*(p+n)

  • 空指针
    指向地址0的指针，int *pn=NULL;

  • 指针和字符串
    字符串常量、字符数组的类型都是char*。

  • void指针

    1
    2
    3
    4
    可以用任何类型的指针对void指针进行赋值
    int a = 3;
    void *p = &a;
    但*p、P+n、p++等均无意义

  • void*自动匹配

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    memset函数
    void* memset(void* dest,int ch,int n)：将dest开始的n个字节都设置为ch(取其最低位字节)，初始化数组。
    //对char数组赋值时，结尾要加'\0'

    memcpy函数
    void* memcpy(void* dest,void* src,int n)：将n个字节拷贝src->dest。

    char a1[10]="";
    char a2[10]="";
    memset(a1, 'a', sizeof(a1)-1);
    memcpy(a2, a1, sizeof(a2));
    cout << a2 << endl; //输出aaaaaaaaaa

  • 函数指针

    1
    2
    3
    //指向函数入口地址的指针
    int (*Pf)(int,char)
    pf = fun_name;

第五节_基本STL

  • 库函数和头文件
    库函数：编译器自带的函数
    头文件：包含许多库函数的声明

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>

//排序
//sort(数组名+n1,数组名+n2)，对数组[n1,n2)区间排序，默认从小到大

int a[] = {15,4,3,9,2,6}
sort(a,a+sizeof(int)/sizeof(int))  //从小到大排序

//从大到小排序
//#include <functional>头文件
sort(a,a+7,greater<T>())  

//自定义排序规则
bool cmp(const int & a1,const int & a2) {
    return a1 > a2;
    //若a1应排在a2前面，则返回true。否则返回false
}
int a[] = {15,4,3,9,2,6}
sort(a,a+sizeof(a)/sizeof(int),cmp());

二分查找

  • 前提条件
    所有的二分查找，都是应用在有序列表中的。

  • binary_search函数
    两种使用方法：
    bool binary_search(数组名+n1,数组名+n2,值)
    bool binary_search(数组名+n1,数组名+n2,值,排序规则结构名())，查找时的规则必须和排序时的规则一致。
    对排好序的数组进行二分查找，返回值true：找到，false：没找到。
    查找的本质：查找x，即找到一个元素y，使得“x必须排在y前面”和“y必须排在x前面”都不成立（和 == 的含义不一样），这样就算找到了；没有找到元素y，就是没找到。
    所以不存在的元素同样有可能查的到（eg：按个位排序，查找的元素只要个位相等就能查到，十位/百位不一定会相等），因此查找的结果要视具体排序规则来分析。

  • lower_bound函数
    T* lower_bound(数组名+n1,数组名+n2,值)
    返回序号p，使得[n1,p)中元素都小于查找值。
    若比所有元素都小/大，则指向n1/n2。
    为避免返回序号为n1时的歧义，查前要确保值在数组范围内。

  • upper_bound函数
    T* upper_bound(数组名+n1,数组名+n2,值)
    返回指针p，使得[p,n2)中元素都大于查找值。

平衡二叉树

在log(n)内快速添加、删除、查找元素
应用了平衡二叉树的四种排序容器：multiset、set、multimap、map

multiset容器

  • 主要作用
    自动对集合内元素排序(默认从小到大)，且允许元素重复，在一些需要动态增加、删除元素的排序场景下使用很方便。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #include <set>  //头文件
    multiset<T> st;
    T a[5] = {1,2,3,4,5}
    multiset<T> st2(a,a+5); //用数组初始化
    st.insert(a); //插入元素a，自动排序。插入的是复制值，并非引用。
    st.erase(a);  //删除元素a

    //遍历集合，用迭代器
    multiset<int>::iterator it;  //定义迭代器，类似指针
    for (it = st.begin(); it != st.end(); it++) {
        cout << *it << " ";
        //end()为末尾指针，指向最后一个元素的后面
    }

    it = st.find(a);   //查找元素a，返回迭代器,没找到返回end()

    st.lower_bound(a);  //返回迭代器it,使得[begin(),it)中元素都比a小，注意是前闭后开区间

    st.upper_bound(a)  //返回迭代器it,使得[it,end())中元素都比a大

  • 自定义排序规则的multiset
    1、自定义规则结构体Rule，实现bool operator()(const & T,const & T)函数
    2、定义容器multiset<T,Rule>
    3、定义迭代器muliset<T,Rule>::iterator

    1
    2
    3
    4
    5
    6
    //自定义规则结构体Rule方法
    struct Rule{
        bool operator()(const & T,const & T){
            //比较函数
        }
    };

set容器

与multiset容器区别：不能有重复元素，其他都一样。
a和b重复的含义：a排在b前面、b排在a前面都不成立
注：因为不能重复，所以插入元素有可能不成功。

1
2
pair<set<T>::iterator,bool> result = set.insert(n);  
//result.second==true，插入成功；否则失败。

multimap容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
键值对形式，multimap中的元素都是pair形式。
按first进行排序，一般不自定义排序。

pair模板：pair<T1,T2>
等价于
struct{
    T1 first;  //关键字
    T2 second; //值 
};

#include <map>
multimap<T1,T2> mp;
mp.insert(make_pair(T1变量,T2变量))  //make_pair为转换pair模板的函数
multima<T1,T2>::iterator it  //迭代器

map容器

和multimap区别：不能有关键字重复的元素
可以使用[first]查找second值；若first不存在，则创建一个。
插入可能失败(first重复)。

camath数学库

  1. abs(int x)：整数绝对值
  2. fabs(double x)：浮点数绝对值
  3. sqrt(double x)：求平方根
  4. ceil(double x)：不小于x的最小整数(上取整)
  5. sin(double x)/cos(double x)：x(弧度)的正/余弦

cstring字符串库

函数都是根据’\0’来判断字符串是否结束的。

  1. 形参常为char c[]，实参可以为char数组或字符串常量。
  2. int strcmp(char c1[],char c2[])：比较字符串，相等返回0，c1小返回负数。
  3. char* strcpy(char dest[],char src[])：拷贝字符串src->dest，返回dest首地址。
  4. int strlen(char c[])：求字符串长度
  5. char strchr(char str,char c)：str中查字符c是否在str中，返回指向位置的指针，未查到为NULL。
  6. char strstr(char str1,char *str2)：str1中查子串str2位置，返回指向位置的指针，未查到为NULL。
  7. cbar strtok(char str1,char* str2)：str1中抽取被str2分隔的子串。(将str1中的分隔符用’/0’代替了)
    1
    2
    3
    4
    5
    char *p = strtok(str1, str2);
    	while (p != NULL) {
    		cout << p << endl;
    		p = strtok(NULL, str2);
    	}

ctype.h字符库

  1. bool isdigit(int c)：判断c是否是数字字符
  2. bool isalpha(int c)：判断c是否是字母字符

Post Date： 2018-09-13

版权声明： 本文为原创文章，转载请注明出处