C/C++编程总结

一、数据类型

1.基本类型

(1)指向void的指针和指向函数的指针支持加法和减法运算，这是通过将void或函数的大小视为1来完成的，其结果是在void和函数类型上还允许sizeof()运算，结果为1。
(2)有符号signed 无符号unsigned，char类型取值范围： -2^7 ~ 2^7-1 即 -128~127，计算机存储的是数字的补码，-0的补码用来表示负数最小的值。
(3)布尔型bool有两个值：true(1)和false(0)，能自加不能自减，最大值为1(true)

2.数组

array[M] 一维数组，数组名为一级指针，指向数组元素
array[M][N] 二维数组，数组名为二级指针，指向二维数组的一行
sizeof(array) 表示数组的长度，而非指针本身大小
p[n] 表示*(p+n)

3.字符串

char *ch1 = “abc”
char *ch2 = “abc”
字符串"abc"在内存中只有一份，ch1与ch2相等，都指向字符串常量"abc"
字符串结束符’’，ASCII值为0
strlen(ch1) 字符串长度，不包含字符串结束符
sizeof(ch1) 字符串长度，包含字符串结束符
C++字符串：string类

4.结构

(1)结构体struct
struct Student {
char name;
int age;
} student1;
struct Student *p = &student1;
student1.char = A;
p->age = 18;
结构体大小计算：
第一个成员起始地址在偏移量为0处，每一个成员的起始地址都应是自身对齐数的整数倍，自身对齐数=min(自身大小,默认对齐数)，默认对齐数：win32、win64为8，gcc32为4，gcc64、qt64无限制，结构体的总大小应为最大对齐数的整数倍，被嵌套结构体起始地址应试自身最大对齐数整数倍，结构体总的大小是总的最大对齐数的整数倍。
C和C++结构体区别:C++结构体有函数成员。
C++结构体和类的区别:类是引用类型，结构体是值类型；类是堆存储，结构体是栈存储；类成员默认属性为私有，结构体成员默认属性为公有。

(2)共用体union
union Data
{
int i;
float f;
char str[20];
};
共用体成员有相同的起始地址，则共用体总的大小为最大成员的大小。

(3)枚举类型enum
enum DAY
{
MON=1, TUE, WED, THU, FRI, SAT, SUN
};
enum DAY day;
day = TUE;
枚举类型是列出枚举变量可能的值，每一个值对应一个有符号整形数，可重复，默认从0递增，赋值后后面的递增赋值。

(4)链表list
typedef struct node {
int data;
int *pre;
int *next;
} Node;

(5)队列queue
typedef struct queue {
int data[N];
int tailed;
} Queue;

(6)栈stack
typedef struct stack {
int data[N];
int top;
} Stack;

5.指针

int p;
指针类型: int
指针基类型: int
sizeof§ = 4(32为系统)、8(64为系统)
指针进行加减运算基本单位由指针类型决定
指针数组 int *array[10];
数组指针 int (*p1)[10];
多级指针 int **p2
函数指针 int (*fp)(int a);
智能指针 auto_ptr, shared_ptr, weak_ptr, unique_ptr

二、运算符

1.算术运算符

+ - * / % ++ –

2.关系运算符

!= > >= < <=

3.逻辑运算符

&& || !

4.位运算符

& | ^ ~ << >>

5.赋值运算符

= += -= *= /= %= <<= >>= &= |= ^=

6.其它运算符

sizeof() & * ?:

7.运算符优先级(从高到低)

三、控制语句

1.if语句

if (条件1) {
执行体1;
} else if (条件2) {
执行体2;
} else {
执行体3;
}

2.switch语句

switch(整形、字符型表达式) {
case 常量表达式1:语句1;break;
case 常量表达式2:语句2;break;
default:语句3;
}

3.for语句

for (循环初始化语句; 循环条件语句; 循环控制语句) {
循环体;
}

4.while语句

while (循环条件) {
循环体;
}

5.do…while语句

do {
循环体;
} while (循环条件)

四、C标准库

1.stdio.h

变量：
(1)size_t 无符号整形类型，sizeof的结果
(2)FILE 文件信息对象类型
(3)fpos_t 文件中位置对象类型
宏：
(1)NULL 空指针
(2)EOF 表示已经到达文件结束的负整数
(3)FOPEN_MAX 表示系统最多能同时打开的文件数量
(4)stderr、stdin、stdout FILE类型指针，对应标准错误、标准输入、标准输出
函数：

(1) int getchar(void) //标准输入一个字符
(2) int putchar(int char) //标准输出一个字符
(3) char *gets(char *str) //标准输入字符串
(4) int puts(const char *str) //标准输出字符串
(2) int scanf(const char *format, ...) //标准格式化输入
(3) int printf(const char *format, ...) //标准格式化输出
(4) FILE *fopen(const char *filename, const char *mode) //打开文件
(5) int fclose(FILE *stream) //关闭文件，刷新所有的缓冲区
(6) int fgetc(FILE *stream) //从文件读一个字符
(7) int fputc(int char, FILE *stream) //往文件写入一个字符
(8) char *fgets(char *str, int n, FILE *stream) //从文件读一个字符串，n大小包含字符串结束符
(9) int fputs(const char *str, FILE *stream) //往文件写入字符串
(10) size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream) //文件流读取
(11) size_t fwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream) //文件流写入
(12) int fscanf(FILE *stream, const char *format, ...) //文件格式化输入
(13) int fprintf(FILE *stream, const char *format, ...) //文件格式化输出
(14) int fgetpos(FILE *stream, fpos_t *pos) //获取文件当前位置，保存到pos
(15) int fseek(FILE *stream, long int offset, int whence) //设置文件读取位置，offset为偏移量，whence为偏移相对位置，文件开头SEEK_SET，当前位置SEEK_CUR，末尾SEEK_END
(16) int getc(FILE *stream) //类似fgetc()
(17) int putc(int char, FILE *stream) //类似fputc()

2.stdlib.h

变量：
(1)size_t 无符号整形，sizeof结果
(2)wchar_t 宽字符整数类型，一般为2或4字节
(3)div_t div函数返回的结构
(4)ldiv_t ldiv函数返回的结构
宏：
(1)NULL 空指针
(2)EXIT_FAILURE exit()失败返回值
(3)EXIT_SUCCESS exit()成功返回值
(4)RAND_MAX rand()返回的最大值
(5)MB_CUR_MAX 表示在多字节字符集中的最大字符数，不能大于 MB_LEN_MAX
函数：

(1) void *malloc(size_t size) //分配内存
(2) void *calloc(size_t nitems, size_t size) //分配内存
(3) void *realloc(void *ptr, size_t size) //尝试重新调整之前调用 malloc 或 calloc 所分配的 ptr 所指向的内存块的大小。
(4) void free(void *ptr) //释放内存
(5) void exit(int status) //正常终止程序
(6) int system(const char *string) //调用系统命令
(7) int abs(int x) //返回绝对值
(8) long int labs(long int x) //返回绝对值
(9) div_t div(int numer, int denom) //分子除以分母
(10) ldiv_t ldiv(long int numer, long int denom) //分子除以分母
(11) int rand(void) //返回一个0到RAND_MAX之间的伪随机数

3.string.h

变量：
(1)size_t 无符号整型类型，sizeof的结果
宏：
(1)NULL 空指针
函数：

(1) size_t strlen(const char *str) //计算字符串长度，不包括字符串结束符
(2) char *strcpy(char *dest, const char *src) //复制字符串
(3) char *strncpy(char *dest, const char *src, size_t n) //复制字符串，最多复制n个字符
(4) char *strcat(char *dest, const char *src) //链接字符串
(5) char *strncat(char *dest, const char *src, size_t n) //链接字符串，最多链接n个字符
(6) int strcmp(const char *str1, const char *str2) //比较字符串，str1 - str2
(7) int strncmp(const char *str1, const char *str2, size_t n) //比较字符串，str1 - str2，最多比较n个字符
(8) int memcmp(const void *str1, const void *str2, size_t n) //把 str1 和 str2 的前 n 个字节进行比较。
(9) void *memset(void *str, int c, size_t n) //复制n个c字符到字符串str
(10) void *memcpy(void *dest, const void *src, size_t n) //从 src 复制 n 个字符到 dest。
(11) void *memmove(void *dest, const void *src, size_t n) //复制src的n个字符到dest

4.math.h

变量：
宏：
(1) HUGE_VAL 当函数的结果不可以表示为浮点数时。如果是因为结果的幅度太大以致于无法表示，则函数会设置 errno 为 ERANGE 来表示范围错误，并返回一个由宏 HUGE_VAL 或者它的否定（- HUGE_VAL）命名的一个特定的很大的值。如果结果的幅度太小，则会返回零值。在这种情况下，error 可能会被设置为 ERANGE，也有可能不会被设置为 ERANGE。
函数：

(1) double fabs(double x) //返回 x 的绝对值
(2) double pow(double x, double y) //返回 x 的 y 次幂
(3) double sqrt(double x) //返回 x 的平方根
(4) double fmod(double x, double y) //返回 x 除以 y 的余数
(5) double log(double x) //返回 x 的自然对数（基数为 e 的对数）
(6) double log10(double x) //返回 x 的常用对数（基数为 10 的对数）
(7) double acos(double x) //返回以弧度表示的 x 的反余弦
(8) double asin(double x) //返回以弧度表示的 x 的反正弦
(9) double atan(double x) //返回以弧度表示的 x 的反正切
(10) double atan2(double y, double x) //返回以弧度表示的 y/x 的反正切y 和 x 的值的符号决定了正确的象限
(11) double cos(double x) //返回弧度角 x 的余弦
(12) double cosh(double x) //返回 x 的双曲余弦
(13) double sin(double x) //返回弧度角 x 的正弦
(14) double sinh(double x) //返回 x 的双曲正弦
(15) double tanh(double x) //返回 x 的双曲正切

5.time.h

变量：
(1) size_t 是无符号整数类型，它是 sizeof 关键字的结果。
(2) clock_t 这是一个适合存储处理器时间的类型。
(3) time_t is 这是一个适合存储日历时间类型。
(4) struct tm 这是一个用来保存时间和日期的结构。
宏：
(1) NULL 这个宏是一个空指针常量的值。
(2) CLOCKS_PER_SEC 这个宏表示每秒的处理器时钟个数。
函数：

(1) clock_t clock(void) //返回程序执行起（一般为程序的开头），处理器时钟所使用的时间。
(2) char *ctime(const time_t *timer) //返回一个表示当地时间的字符串，当地时间是基于参数 timer。
(3) double difftime(time_t time1, time_t time2) //返回 time1 和 time2 之间相差的秒数 (time1-time2)。
(4) time_t time(time_t *timer) //计算当前日历时间，并把它编码成 time_t 格式。

6.其它头文件

assert.h
ctype.h
errno.h
float.h
limits.h
locale.h
setjmp.h
signal.h
stdarg.h
stddef.h

五、C++面向对象

1.头文件

(1) iostream 该文件定义了 cin、cout、cerr 和 clog 对象，分别为标准输入流、标准输出流、非缓冲标准错误流和缓冲标准错误流。

cin >> a;
cout << a << endl;

(2) fstream 该文件定义了文件流相关对象。
(3) iomanip 该文件通过所谓的参数化的流操纵器（比如 setw 和 setprecision），来声明对执行标准化 I/O 有用的服务。

2.命名空间

//使用命名空间
using namespace std;
//定义命名空间
namespace nameSpace1
{
int g_val = 100;
}
cout << nameSpace1::g_val << endl;

3.封装

(1)类的定义

class Student
{
public:
Student()
{
}
~Student()
{
cout << "~Student(1)" << endl;
}
static int count;
private:
string name;
protected:
char sex;
};
int Student::count = 0;

(2)成员属性
公有 public：本类、子类、类外对象都能访问
私有 private：本类对象能访问（默认为私有）
保护 protected：本类、子类对象能访问
this表示指向本类的指针

(3)构造函数

public:
Student():name("zhang"),age(18)
{
}
Student(&student1, int a)
{
}

构造函数是在创建类对象的时候调用的函数,如果一个都不定义，系统默认会创建一个无参构造函数，如果定义了带参数构造函数则系统不会自动定义无参构造函数，所以原则上必须定义一个无参构造函数以防止不带参数实例化对象时报错。构造函数名是类名，无返回值,构造函数可以有参无参重载多个函数。拷贝构造函数第一个参数为类的引用，拷贝赋值创建类对象时调用。构造函数可以使用初始化列表来初始化类的数据成员，const修饰的变量只能通过初始化列表来初始化。
(4)析构函数

public:
~Student()
{
}

析构函数名为类名前加个~，销毁类对象的时候调用，析构函数无参数,无返回值。

(5)友元

public:
friend int fun(int a);
friend int Student::print(int a);
friend class Student;

在类内public声明其它对象为本类的友元，友元可以是一般函数，类成员函数，类，友元可以访问本类的所有成员。

(6)静态数据成员、静态函数

class Solution {
public:
static int a;
//静态数据成员类内声明，类外初始化
static int fun(int a) //静态成员函数可在类内、类外定义，只能访问静态数据成员、静态函数，能通过类名访问
//非静态函数能访问所有数据成员、成员函数、this指针，不能通过类名访问。
{
return a;
}
};
int Solution::a = 1;
int Solution::fun(int a)
{
return a;
}

4.继承

(1)继承方式

class A
{
public:
int a = 1;
A(){};
~A(){};
};
class B : public A //公有继承(公有-公有,保护-保护,私有-不能)
//保护继承(公有-保护,保护-保护,私有-不能)
//私有继承(公有-私有,保护-私有,私有-不能)
{
public:
B(){};
~B(){};
};
cout << b.a << endl;

5.多态

(1)重载函数

class Solution {
public:
void print(int i) {
cout << "整数为: " << i << endl;
}
void print(double f) {
cout << "浮点数为: " << f << endl;
}
};

重载函数的函数名相同，通过参数(个数、顺序、类型)不同调用最匹配的函数，返回值类型不影响。
(2)重载运算符
Student operator+(const Student&);
重载运算符实际是具有特殊函数名的函数，函数名为operator关键字后接要重载的运算符，this是左操作数,参数是右操作数
不能重载的运算符:
. 类成员访问运算符
-> 成员指针访问运算符
:: 域运算符
sizeof 长度运算符
?: 条件运算符

(3)虚函数

#include <iostream>
using namespace std;
class A
{
public:
virtual void print()
{
cout << "A" << endl;
}
};
class B : public A
{
public:
void print()
{
cout << "B" << endl;
}
};
class C
{
public:
virtual void print() = 0;
};
int main()
{
A a;
B b;
A *p1, *p2;
p1 = &a;
p2 = &b;
p1->print(); //输出A
p2->print(); //输出B
return 0;
}

虚函数是在基类使用virtual声明的函数，可以在子类重新定义虚函数，通过类对象指针调用虚函数时指针指向什么类就调什么类的虚函数。虚函数声明后加=0则为纯虚函数，纯徐函数在基类不定义，只能在子类定义。虚函数在基类必须声明为public。

6.默认参数值的函数

void fun(int a, int b = 3, int c = 4)
{
cout << a << " " << b << " " << c << endl;
}
fun(1, 2); //输出1 2 4

类成员函数、非类成员函数在声明或者定义的时候可以指定参数默认的值，有默认值的参数在右边，没有默认值的参数在左边，函数调用时形参从左到右传值，可以覆盖参数的默认值。

7.内联函数

inline int Max(int x, int y)
{
return (x > y)? x : y;
}

函数体较小、逻辑简单的函数可以声明为内联函数(一般为类成员函数)，优点：高效; 缺点：程序变慢，代码量可能增多。内联函数本质是函数会做参数类型检查，宏只是替换不会做参数检查。

8.指针和引用

double a = 3.14;
double *b;
//指针
double &c = a;
//引用
cout << sizeof(c) << endl; //输出8
cout << c << endl;
//输出3.14

(1)指针是内存地址，用*声明，引用是别名，用&声明
(2)指针定义时可先不初始化且后面可以改变指针的指向，引用定义时必须初始化且后面无法改变绑定的对象
(3)引用作函数实参时相对于变量是地址传递，相对于指针更安全
(4)const修饰常引用，不能通过常引用修改绑定对象的值，常量只能跟常引用绑定
(5)指针大小一般为4字节(32为系统)或8字节(64为系统)，引用实际是绑定对象的别名，对引用的所有操作实际是对绑定对象的操作(包括sizeof)，使用引用与直接使用变量名的区别是引用作为函数参数时是地址传递，形参的改变会影响实参。

9.模板

//模板函数
template <typename T, typename O>
T Max(T a, T b, O c)
{
cout << c << endl;
return a > b ? a : b;
}
cout << Max(2, 9, "output") << endl;
//输出output 9
cout << Max(3.5, 1.2, "output") << endl;
//输出output 3.5
//模板类
template <typename T>
class Solution {
public:
T data;
Solution() {};
Solution(T a)
{
this->data = a;
}
};
Solution<int> s1(2); //T类型确定为int，s1.data初始化为2

(1)泛型编程使用template声明T、O为类型名，后面可使用T、O来定义模板函数或模板类
(2)T、O类型在调用函数或实例化类对象时确定，声明后面不加分号，此次声明仅对接下来的一个模板函数或模板类有效
(3)模板函数的本质是把函数的参数类型作为函数参数，函数调用时才确定参数类型
(4)模板函数的T类型在函数调用时由传入的实参类型确定，模板类的T类型在实例化类对象时使用<>指定

六、C++标准模板库STL

1.容器container

(1)向量vector

#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int>::iterator it;
//定义vector类型的迭代器
vector<int> v1 = {1,2,3,4,5,6};
//定义并初始化一维vector
vector<int> v2(3,99);
//定义vector并初始化为3个99
vector<vector<int>> v3;
//定义二维vector
it = v1.begin();
//begin()是第一个元素的迭代器, end()是最后一个元素的下一个迭代器
cout << *it << endl;
//*v1.begin()值为1
cout << v1.empty() << endl;
//判断vector是否为空，为空返回1，不为空返回0
cout << v1.size() << endl;
//v1长度为6
cout << v1.max_size() << endl;
//v1最大长度4611686018427387903
cout << v1[0] << endl;
//下标为0的元素值为1
cout << v1.at(1) << endl;
//下标为1的元素值为2
v1.push_back(7);
//末尾插入一个元素
v1.pop_back();
//末尾删除一个元素
v1.insert(v1.begin()+1, 100);
//在位置v1.begin()+1处插入一个元素100，此处原来的元素往后移
v1.erase(v1.begin()+1);
//删除位置v1.begin()+1处的元素，后面的元素往前移
v1.erase(v1.begin(), v1.begin()+3);
//删除位置v1.begin()到v1.begin()+3(包含前面不包含后面)的元素，后面的元素往前移
v1.clear();
//清空v1所有元素
return 0;
}

(2)列表list
链表list与向量vector类似，区别在于：

list<int> list1 = {1,2,3,4,5,6};
//定义链表list1
list<int> list2(3, 99);
list1.push_front(1);
//从链表头部插入节点1
list1.pop_front();
//删除链表头节点
cout << list1.front() << endl;
//输出链表头节点
cout << list1.back() << endl;
//输出链表尾节点
list1.swap(list2);
//交换两个链表，或者swap(list1, list2)
reverse(list1.begin(), list1.end());
//反转链表

a. vector是顺序存储，底层是数组；list是链式存储，底层是双向链表；list不能使用方括号v[0]和v.at(1)访问元素。
b. vector可以直接访问任意元素，list只能快速访问头节点和尾结点，其它节点的迭代器可以通过头尾节点迭代器加减得到
c. vector在中间节点进行插入删除会导致内存拷贝，list不会。
d. vector一次性分配好内存，不够时才进行2倍扩容；list每次插入新节点都会进行内存申请。
e. vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好。
f. vector的end()是向量最后一个元素的下一个迭代器，而list的是链表的最后一个元素的迭代器。

(3)栈stack
栈从栈顶入栈顶出，先入后出

#include <iostream>
#include <stack>
using namespace std;
int main()
{
stack<int> s;
//定义并初始化一个栈stack
s.push(1);
//入栈
s.push(2);
//入栈
s.pop();
//出栈
cout << s.empty() << endl;
//查看栈是否为空
cout << s.size() << endl;
//查看栈的元素个数
cout << s.top() << endl;
//返回栈顶元素
return 0;
}

(4)队列queue
队列从队尾入队头出，先入先出

#include <iostream>
#include <queue>
using namespace std;
int main()
{
queue<int> q;
//定义并初始化一个队列queue
q.push(1);
//入队
q.push(2);
//入队
q.push(3);
//入队
q.pop();
//出队
cout << q.empty() << endl;
//查看队列是否为空
cout << q.size() << endl;
//查看队列的元素个数
cout << q.front() << endl;
//返回队头元素
cout << q.back() << endl;
//返回队尾元素
return 0;
}

(5)双队列deque
双对列除了具有vector和queue的特点外，还可以反向遍历

#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int> c = {1,2,3,4,5,6};
deque<int>::reverse_iterator rit;
for(rit = c.rbegin();rit != c.rend(); rit++) {
cout << *rit << " ";
}
cout << endl;
return 0;
}

(6)集合set
set是统一类型数据的集合，余vector类似，与vector不同的是，在set中每个元素的值都是唯一的，而且set插入数据时，能够自动排序，set中数元素的值并不能直接被改变。
begin() //返回set容器的第一个迭代器
end() //返回set容器的最后一个迭代器
clear() //删除set容器中的所有的元素
empty() //判断set容器是否为空
max_size() //返回set容器可能包含的元素最大个数
size() //返回当前set容器中的元素个数
rbegin //返回的值和end()相同
rend() //返回的值和rbegin()相同

(7)映射map
man是一种关联容器，实际是键值对

#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> m;
//定义map，map的键是唯一的，不同的键对应的值可以相同
map<char, int> n;
map<char, int>::iterator mit;
//定义map类型迭代器
m['a'] = 1;
//键'a'对应的值赋值为1，若键'a'不存在则插入键值对a,1
m['b'] = 2;
//键'b'对应的值赋值为2，若键'b'不存在则插入键值对b,2
m['c'] = 3;
//键'c'对应的值赋值为3，若键'c'不存在则插入键值对c,3
cout << m['a'] << endl;
//输出键'b'对应的值
cout << m.empty() << endl;
//是否为空
cout << m.size() << endl;
//元素个数
cout << m.max_size() << endl;
//最大元素个数
cout << m.count('a') << endl;
//是否有键为'a'的成员，有则返回1，否则返回0
mit = m.begin();
//起始元素的迭代器
mit = m.end();
//最后元素的迭代器
m.insert(pair<char, int> ('a', 101)); //插入键值对d,4，如果键d已经存在则不插入、值不覆盖也不报错
mit = m.find('b');
m.erase('a');
//删除键为'a'的元素
m.erase(mit);
//删除迭代器mit对应的元素
m.swap(m);
//交换mn
m.clear();
//清空m
return 0;
}

2.算法algorithm

(1)algorithm

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void fun1(int a)
{
cout << a << " ";
}
int fun2(int a)
{
return a * 10;
}
int fun3(int a, int b)
{
return a > b ? a : b;
}
int main()
{
int array[3] = {11,22,33};
int a = 1;
int b = 2;
vector<int> v1 = {5,3,9,7,1};
vector<int> v2 = {2,4,6,8,10};
cout << max(a, b) << endl;
//1.返回较大的值
cout << min(a, b) << endl;
//2.返回较小的值
cout << abs(a) << endl;
//3.返回绝对值
swap(a, b);
//4.交换两个变量的值
//5.默认升序排序，可以指定比较函数，前两个参数可以是迭代器或指针，顾前不顾后
sort(v1.begin(), v1.end());
sort(array, array + 3, fun3);
cout << array[0] << " " << array[1] << " " << array[2] << endl;
//6.遍历迭代器v1.begin()到v1.end()，遍历的每个元素作为参数执行函数fun2，返回结果覆盖到起始迭代器为v2.begin()的容器
transform(v1.begin(), v1.end(), v2.begin(), fun2);
//7.遍历迭代器v1.begin()到v1.end()，顾前不顾后，遍历的每一个元素作为fun1函数的参数执行函数，无法修改元素
for_each(v1.begin(), v1.end(), fun1);
cout << endl;
for_each(v2.begin(), v2.end(), fun1);
cout << endl;
return 0;
}

(2)functional

(3)numeric

3.迭代器iterator

(1)iterator

(2)memory

(3)utility

七、算法

1.时间空间复杂度

复杂度从小到大：
(1) O(1) 常数阶
(2) O(logN) 对数阶
(3) O(n) 线性阶
(4) O(nlogN) 线性对数阶
(5) O(n²) 平方阶
(6) O(n³) 立方阶
(7) O(n^k) k次方阶
(8) (2^n) 指数阶

2.排序算法

(1)选择排序
从n个数据中选出最小或最大的数据与第一个数据交换，则第一个数据排好序，剩下的数据执行相同操作直到全部排好序

int sort1(int *array, int array_size)
{
for (int i = 0; i < array_size - 1; i++) {
for (int j = i + 1; j < array_size; j++) {
if (array[i] > array[j]) {
array[i] = array[i] + array[j];
array[j] = array[i] - array[j];
array[i] = array[i] - array[j];
}
}
}
return 0;
}

(2)插入排序
把第一个数据当做是已排好序，将剩下的数据一个一个插入到他们应该在的位置

int sort2(int *array, int array_size)
{
for (int i = 0; i < array_size - 1; i++) {
int j = i + 1;
while (array[j] < array[j - 1] && j > 0) {
int temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
j--;
}
}
return 0;
}

(3)冒泡排序
遍历所有数据把最小或最大的数据推到最后一个位置，则最后一个数据已排好序，剩下的数据进行同样的操作直到所有数据排好序

int sort3(int *array, int array_size) //i表示未排序的元素中最大的下标
{
for (int i = array_size - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return 0;
}

(4)快速排序
把最后一个数据当做中值，其它数据小于或等于中值的放左边，大于中值的放右边，左右两部分数据进行相同的操作直到所有数据排好序

int sort4(int *array, int begin, int end)
{
int middle = array[end];
int left = begin;
int right = end;
while (left < right) {
while ((left < right) && (array[left] <= middle)) {
left++;
}
if (left < right) array[right] = array[left];
while ((left < right) && (array[right] > middle)) {
right--;
}
if (left < right) array[left] = array[right];
}
array[left] = middle;
if (left > begin) sort4(array, begin, left - 1);
if (right < end) sort4(array, right + 1, end);
return 0;
}

3.查找算法

(1)二分查找
从有序序列中查找一个数据，用查找的值跟中间值比较，若小于中间值则在中间值左边用同样的方法继续查找，若大于中间值则在右边用同样的方法继续查找，直到找到或者找完。

4.经典算法

(1)动态规划
最优解或者最优路径一般可以用动态规划解决
a.分析状态，定义一个多维数组来存储状态
b.分析状态间的关系，确定状态转换方程
c.可以用递归方法将一个大规模复杂的问题分解为多个小规模简单的问题，解决简单问题退出复杂问题的解
d.递归可以转换为递推，使得多维数组可以用多个变量替换，减小空间复杂度

//1.买卖股票的最佳时机，不限交易次数
int maxProfit(vector<int>& prices) {
const int n = prices.size();
if (n == 0) return 0;
int last_sell = 0;
int last_hold = -prices[0];
for (int i = 1; i < n; i++) {
last_sell = max(last_sell, last_hold + prices[i]);
last_hold = max(last_sell - prices[i], last_hold);
}
return last_sell;
}
//2.买卖股票的最佳时机，最多交易k次
int maxProfit(int k, vector<int>& prices) {
if (prices.empty() || k == 0) {
return 0;
}
const int n = prices.size();
k = min(k, n / 2);
vector<vector<int>> sell(n, vector<int>(k + 1));
vector<vector<int>> buy(n, vector<int>(k + 1));
for (int i = 1; i < k + 1; i++) {
sell[0][i] = 0;
buy[0][i] = -prices[0];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < k + 1; j++) {
sell[i][j] = max(sell[i-1][j], buy[i - 1][j] + prices[i]);
buy[i][j] = max(buy[i-1][j], sell[i - 1][j - 1] - prices[i]);
}
}
return sell[n - 1][k];
}

八、其它

1.main()函数参数

int main(int argc, char **argv)
argc为参数个数不包括执行文件名本身，argv为字符型二级指针，argv[0]为执行文件名，argv[1]为第一个参数。

2.const关键词

const int a; //常量,只读
const int *p; //常量指针,不能通过该指针改变所指向的内容
int * const p1; //指针常量,不能改变该指针的指向
const int * const p2; //常量指针常量,都不可改变

3.mutable

mutable用来修饰数据成员:在常函数中也能改变;常函数:类内函数定义后加const，不能改变类内飞静态数据成员

九、笔记

1.文件包含预处理命令不一定要写在代码开头，可以写在代码其它地方，函数内也可以
2.共用体长度不一定等于最大元素的长度，要考虑字节对齐
3.用户可以重新定义标准库函数，原来的将失去意义
4.需要通过初始化列表来初始化的对象：const修饰的成员、引用类型的成员、包含这两种的类对象；static声明的除外，静态成员必须是类内声明，类外初始化
5.类成员的初始化顺序是声明的顺序，与初始化列表中的顺序无关
6.派生类会继承基类的private成员，只是不能直接访问，基类可以有多个派生类，派生类也可以有多个基类
7.单目运算符++和–重载是需要一个int型参数
8.static变量是加了访问控制的全局变量，全局只有一个，不被继承，基类和派生类都能访问(除了基类私有的static变量)
9.派生类能直接访问直接基类的公有成员和保护成员，不能访问间接基类(爷爷或祖父或祖先)的保护成员
10.被初始化为NULL的类成员指针可以安全访问不涉及类数据成员的函数
11.do…while语句的条件语句执行次数跟循环体执行次数关系不确定，因为break、continue、return语句的存在
12.后加三个数字是一个转义字符，/123
13.char ch[2][3]={“a”,“b”};是正确的初始化
14.直接创建对象会创建在栈内存，new创建会创建在堆内存，为了使对象只能用new创建即只能创建在堆内存中，可以把析构函数设为私有类型（在栈内存创建对象时会先检查是否能访问析构函数，不能访问则不能创建在栈内存中）
15.变量赋值溢出会循环赋值，即正向溢出1会赋值到最小的值
16.没有引用的指针，对引用&运算实际是对引用对象的运算；有指针的引用int *&q = p
17.二叉查找树：中序遍历是递增有序序列
18.平衡二叉树：所有左右子树深度差小于或等于1
19.红黑树本质是接近平衡的二叉查找树，为了使高度、时间复杂度控制在logn，红黑树有5个性质：
(1)每个结点要么是红的要么是黑的
(2)根结点是黑的
(3)NULL结点都是黑的
(4)如果一个结点是红的，那么它的子结点是黑的
(5)对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点
20.c++中NULL为0，可以表示空指针，但是NULL作为重载函数时有二意(空指针和整形0)，所以建议用nullptr替代NULL表示空指针
21.int *a = new int; int *b = new int(2); int *c = new int[3]; delete a, b; delete[] c; malloc(), calloc(), free()
22.容器遍历：for(int i: v1) {cout << i << endl;}
23.设两个指针，一个单步走，一个2步走，若两个指针能相遇则证明链表有环；寻找入环点：链表起点到入环节点距离与相遇点到入环点距离(可能包含n圈)相等

最后

以上就是懵懂火龙果为你收集整理的C/C++编程总结的全部内容，希望文章能够帮你解决C/C++编程总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。