基本概念

  1. 什么是C++?
    C++是C语言的继承，即兼容了C语言面向过程的程序设计能力，又能做面向对象的程序设计。
  • 源代码->编译器->目标代码->链接程序(启动代码、库代码)->可执行代码
  1. C++的一些基本特点：

（1）C++文件一般以 .cpp 结尾(c plus plus) .cc .C
（2）编译（Linux环境）：

1
g++ xxx.cpp -o app

（3）C++头文件

C++标准的头文件是没有 .h的

1
#include <iostream>

C++兼容C语言的头文件： 

1
2
#include <cstdlib>
#include <stdlib.h>
  1. C++兼容大部分C语言(不完全兼容) C++编译器更严格

比如 void * 类型转换成 int * ，在C语言中，无需显性的指定，默认是允许的，在C++中，编译检查的更严格，不允许

C++中main函数的返回值必须为 int

输入和输出

第一个程序 hello world

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>    // 输入输出流的头文件
 
int main(){            // 要求main函数的返回值必须为int
 
    std::cout << "hello" << "　world" << std::endl
                      
    /* std 命名空间
     * :: 是C++ 特有的，叫 作用域限定符
     * cout C++给我们提供的输出流对象
     * << 流输出运算符，表示向输出流对象输出数据（可以级联使用）
     *endl 换行 end line
     */
 
    return 0;
 
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

// 函数头
int main(void)
// ( )内为参数，没有参数为void
// { } 为代码块
{
	using namespace std; // iostream包含std命名空间 std包含cin，cout，endl
	// using std::cin;
	// using std::cout;
	// using std::endl;

	int carrots; // int 整型 carrots 变量名(胡萝卜) 声明语句

	cout << "How many corrots do you have?" << endl; //  cout 输出 endl表示回车换行符
	cin >> carrots; // cin 输入
	cout << "Here are two more." << endl;
	carrots = carrots + 2;
	cout << "Now you have " << carrots << " carrots." << endl;

	return 0;
}

命名空间（名字空间）

  1. 作用：在大型项目的开发中，一般都是多个人同时开发，经常会出现命名冲突,这种冲突，称之为命名污染.

命名空间的作用，就是防止命名污染

  1. 用法：

(1) std::cout

在名字前面加上 命名空间和作用域限定符 std::

C++中标准的名字都是std命名空间中的

(2) using std::cout

在使用前，加上 using 命名空间::名字

在其作用域中，后面使用名字时就不用每次都加了

(3) using namespace std;

表示整个文件中都可以使用 std 命名空间中的所有名字

Visual Studio
多行注释:选中,Ctrl + K,Ctrl + C
取消注释:选中,Ctrl + K,Ctrl + U

处理数据

面向对象编程的本质是设计并扩展自己的数据类型

整型 short int long longlong

计算机内存的基本单元是位(bit),8位单元可以表示0到255或者-128到127

字节(byte)通常指8位的内存单元 1byte = 8bit

符号常量与sizeof()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <climits>

int main(void)
{
	using namespace std;
	int n_int = INT_MAX; // 符号常量 整型的最大数值
	short n_short = SHRT_MAX;
	long n_long = LONG_MAX;
	long long n_llong = LLONG_MAX;

	cout << "int is " << sizeof(int) << " bytes." << endl; // sizeof()返回int数据类型的长度
	// sizeof()不是函数，是运算符 计算类型名必须加括号，变量名可不加括号
	cout << "short is " << sizeof n_short << " bytes." << endl;
	cout << "long is " << sizeof (n_long) << " bytes." << endl;
	cout << "long long is " << sizeof (n_llong) << " bytes." << endl;
	cout << endl;

	cout << "Maximum values: " << endl;
	cout << "int: " << n_int << endl;
	cout << "short: " << n_short << endl;
	cout << "long: " << n_long << endl;
	cout << "long long: " << n_llong << endl;

	cout << "--------" << endl;
	int a{ 5 }; // 列表标识符
	cout << a;

	return 0;
}
  • 有无符号类型 short -32768~+32767 0-65535
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <climits>

#define ZERO 0;

int main() {
	using namespace std;

	short sam = SHRT_MAX; // 有符号短整型最大值
	unsigned short sue = sam;

	cout << "sam = " << sam << endl;
	cout << "sue = " << sue << endl;
	
	sam = sam + 1;
	sue = sue + 1;

	cout << "sam = " << sam << endl;
	cout << "sue = " << sue << endl;

	sam = ZERO;
	sue = ZERO;

	sam = sam - 1;
	sue = sue - 1;

	cout << "sam = " << sam << endl;
	cout << "sue = " << sue << endl;`

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>

int main()
{
	using namespace std;

	cout << "\aOperation \"Hyperhupe\" is now activated:\n";
	cout << "Enter your agent code:______\b\b\b\b\b\b";
	long code;
	cin >> code;
	cout << "\aYour entered " << code << "...\n";
	cout << "\aCode verified! Proceed with plan Z3!\n";

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

int main()
{
	using namespace std;

	cout.setf(ios_base::fixed, ios_base::floatfield); // 小数以定点模式输出
	float tub = 10.0 / 3.0;
	const float million = 1.0e6;

	cout << "tub = " << tub;
	cout << ", a million tubs = " << million * tub << "   ";
	cout << 10 * million * tub << endl;

	double mint = 10.0 / 3.0;
	cout << "mint = " << mint << "   ";
	cout << "a million mints = " << million * mint << endl;


	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>

int main()
{
	using namespace std;
	float a = 2.34E+22f;
	float b = a + 1.0F;
	cout << "a = " << a << endl;
	cout << "b - a = " << b - a << endl;

	return 0;
}

C++中的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>

int main()
{
	using namespace std;
	char charr1[20];
	char charr2[20] = "jaguar";
	string str1;
	string str2 = "panther";

	cout << "Enter another kond of feline: ";
	cin >> charr1;
	cout << "Enter another kond of feline: ";
	cin >> str1;
	cout << "Here are some felines: \n";
	cout << charr1 << " " << charr2 << " " << str1 << " " << str2 << endl;

	cout << "The third letter in " << charr2 << " is " << charr2[2] << endl;
	cout << "The third letter in " << str2 << " is " << str2[2] << endl;
	return 0;
}

结构数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

struct inflatable
{
	char name[20];
	float volume;
	double price;
};

int main()
{
	using namespace std;

	inflatable guest[2] =
	{
		{"bambi", 0.5, 21.99},
		{ "godzilia", 0.4, 12.99 }
	};
	
	cout << guest[0].name <<  " " << guest[1].name << endl;
	cout << guest[0].volume << " " << guest[1].volume << endl;
	return 0;
}

bool类型

C++新增了bool类型， bool是 基本类型

  1. 表示真或者假的 0 为假 非0为真
    1
    2
    3
    bool 变量可赋 true false
     
    bool b = true; //防止魔鬼数字
  2. 大小 1个字节
    例：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    int main(){ 
     
    bool b1 = true; 
    bool b2 = false;                        //bool类型的变量 可以用 false 和 true 赋值 
    bool b3 = 10;                           //bool类型的变量也可以赋值数字 
    bool b4 = 0; bool b5 = -10;             //0为假 非0为真 （即使是负数，也为真） 
     
    cout<<"bool_size : "<<sizeof(b1)<<endl; //bool类型大小为 1 字节 
    cout<<"b1 : "<<b1<<endl;                //输出bool变量的值 输出时， 
    cout<<"b2 : "<<b2<<endl;                //真为 1 假为0 
    cout<<"b3 : "<<b3<<endl; 
    cout<<"b4 : "<<b4<<endl; 
    cout<<"b5 : "<<b5<<endl; 
    cout<<"b5 : "<<boolalpha<<b5<<endl;     //以字母的形式输出（true和false） 
                                            //一旦设置后，后面的输出全是字母类型 
    cout<<"b2 : "<<b2<<endl; 
    cout<<"b5 : "<<noboolalpha<<b5<<endl;   //改回以 0 1 的方式输出 
                                            //一旦设置后，后面的输出全是0 1 方式 
    cout<<"b2 : "<<b2<<endl; 
    bool sex = 0;                           //女 
    cout<<"sex:"<<(sex?"帅哥":"美女")<<endl; //bool变量用在三目运算符中
     
    return 0; 
     
    }

数组选择排序及冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>

using namespace std;

int main()
{
	int arr[] = { 5, 9, 2, 7, 4, 3, 12, 6, 1, 5, 7 };

	int size = sizeof(arr) / sizeof(arr[0]);

	// 选择排序
		for (int i = 0; i < size; i++) {
			for (int j = i + 1; j < size; j++) {
				if (arr[j] < arr[i]) {
					int temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}
	for (int num : arr) {
		cout << num << "\t";
	}

	cout << endl;

	cin.get();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

using namespace std;

int main()
{
	int arr[] = { 5, 9, 2, 7, 4, 3, 12, 6, 1, 5, 7 };

	int size = sizeof(arr) / sizeof(arr[0]);

	// 冒泡排序
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size - i -1; j++) {
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}

	for (int num : arr) {
		cout << num << "\t";
	}

	cout << endl;

	cin.get();
		
}

vector的基本用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	// 默认初始化
	vector<int> v1;

	// 列表初始化(拷贝初始化)
	vector<char> v2 = { 'a', 'b', 'c' };
	vector<char> v3 = { 'a', 'b', 'c' };
		
	// 直接初始化
	vector<short> v4(5);
	vector<long> v5(5, 100); // 有5个值 都是100

	// 访问元素
	cout << v5[3] << endl;
	v5[3] = 25;
	cout << v5[3] << endl;
	// cout << v5[6] << endl; // 错误

	cout << "v5的长度为：" << v5.size() << endl; // v5.size()获取长度


	// 遍历所有元素
	for (int i = 0; i < v5.size(); i++) {
		cout << v5[i] << "\t";
	}

	cout << endl;

	// 添加元素
	v5.push_back(69);

	for (int num : v5) {
		cout << num << "\t";
	}

	cout << endl;

	// 向容器中添加倒叙的元素
	for (int i = 10; i > 0; i--) {
		v1.push_back(i);
	}
	for (int num : v1) {
		cout << num << "\t";
	}
	
	cout << endl;

	cin.get();
}

数组是更加底层的数据类型;长度固定，功能较少，安全性没有保证，但性能更好，运行更高效:
vector是模板类，是数组的上层抽象;长度不定，功能强大;缺点是运行效率较低;

简单读写文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int main()
{
	ifstream input("input.txt");
	ofstream output("output.txt");

	// 按照单词逐个读取
	string word;
	while (input >> word)
	{
		cout << word << endl;
	}

	// 逐行读取
	string line;
	while (getline(input, line)) {
		cout << line << endl;
	}

	// 逐个字符读取
	char ch;
	while (input.get(ch)) {
		// cout << ch << endl;
		output << ch << endl;
	}
	cin.get();
}

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>

using namespace std;

// 定义一个结构体
struct StudentInfo
{
	string name;
	int age;
	double score;
}stu2, stu3 = { "小明", 19, 65.0 };


// 输出一个数据对象的完整信息
void printInfo(StudentInfo stu) {
	// 访问数据
	cout << "学生姓名:" << stu.name << "\t 年龄：" << stu.age << "\t 成绩：" << stu.score << endl;
}

int main()
{
	// 创建数据对象并做初始化
	StudentInfo stu = { "张三", 18, 75.0 };
	StudentInfo stu1 = { "李四", 20, 82 };

	// 使用另一结构体对象进行赋值
	StudentInfo stu4 = stu3; 

	// 赋值
	stu2.name = "王五";
	stu2.age = 22;
	stu2.score = 60.0;

	printInfo(stu);
	printInfo(stu1);
	printInfo(stu2);
	printInfo(stu3);

	// 结构体数组
	StudentInfo s[3] = {
		{"小红", 17, 85.5},
		{"小白", 18, 72.5},
		{"小黄", 20, 66.5}
	};

	printInfo(s[1]);
	s[2].age = 21;
	cout << s[2].age << endl;

	for (StudentInfo stu: s)
	{
		printInfo(stu);
	}

	cin.get();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>

struct inflatable
{
	char name[20];
	float volume;
	double price;	
};

int main()
{
	using namespace std;
	inflatable* ps = new inflatable;
	cout << "Enter name of inflatable item: ";
	cin.get(ps->name, 20);
	cout << "Enter volume in cubic feet: ";
	cin >> (*ps).volume;
	cout << "Enter price: $";
	cin >> ps->price;
	cout << "Name: " << (*ps).name << endl;
	cout << "Vlolume: " << ps->volume << endl;
	cout << "Price: " << ps->price << endl;

	delete ps;
	return 0;
}

枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>

using namespace std;

// 定义一个枚举类型
enum Week
{
	Mon, Tue, Wed, Thu = 10, Fri, Sat, Sun
};

int main()
{
	Week w1 = Mon, w2 = Tue;
	// Week w3 = 3; 错误

	Week w3 = Week(3);
	Week w4 = Fri;
	Week w5 = Week(20);

	cout << "w1 = " << w1 << endl;
	cout << "w2 = " << w2 << endl;
	cout << "w3 = " << w3 << endl;
	cout << "w4 = " << w4 << endl;
	cout << "w5 = " << w5 << endl;

	cin.get();

}

引用（quote）

  1. 概念：

C++对C的一个重要的扩充，相当于给变量起别名。 —-相当于硬链接

  1. 定义引用：

& 引用的声明符

类型名 &引用变量名 = 被引用的变量名

例：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio> 
 
int main(){ 
 
    int a = 100; 
    int &b = a; 
    cout<<"a : "<<a<<endl;//100 
    cout<<"b : "<<b<<endl;//100 
    printf("&a : %p\n",&a);// 
    printf("&b : %p\n",&b);//和a的地址相同 
    return 0; 
 
}

使用引用的要求：

  1. 定义引用时必须指定被引用的目标 —-定义引用必须要初始化

  2. 引用类型必须和被引用的类型保持一致

  3. 引用一旦被初始化，后面便不能修改引用的目标了

  4. 引用做形参 —-不用考虑值传递地址传递的问题了

例1：引用变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream> 
using namespace std; 
 
void function(int &aa){ 
 
    aa = 200; 
 
} 
 
int main(){ 
 
    int a = 100; 
    cout<<"a:"<<a<<endl; 
    function(a); 
    cout<<"a:"<<a<<endl; 
    return 0; 
 
}

例2：引用指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream> 
using namespace std; 
#include <cstdio> 
#include <cstdlib> 
 
void function(int* &aa){ 
 
    aa = (int *)malloc(sizeof(int)); 
    
} 
 
int main(){ 
    
    int *p = NULL; 
    function(p); 
    *p = 100; 
    cout<<*p<<endl; 
    return 0; 
 
}

  1. 常引用

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int main(){ 
     
        int a = 100; 
        const int &q = a; 
        a = 200;            //正确的，可以通过a修改值 
        q = 200;            //错误的，q是被const修饰的引用（是只读的） 
                            //不能通过q修改值 
        const int &q1 = 200;//const修饰的引用 可以引用常量 
        return 0; 
     
    }

  2. 引用做函数的返回值

    1. 不可以返回局部变量的引用

    2. 可以返回全局变量或者static修饰的局部变量的引用

    3. 引用作为返回值，函数的返回值是一个左值

为了防止对函数的返回值进行乱改，一般返回 const 修饰的引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream> 
using namespace std; 
 
const int &find_max(int x,int y){ 
 
    static int temp = x>y?x:y; 
    return temp; 
 
} 
 
int main(){ 
 
    int ret = 5; 
    find_max(10,20) = ret;    //如果返回的不是const 修饰的引用， 
                              //那么此处函数的返回值可以被修改 
    return 0; 
 
}
  1. 结构体中定义引用:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    struct __STU{ 
     
        int &q; 
     
    }; 
     
    int main(){ 
     
        int a = 100; 
        struct __STU s1;        //错误 
        struct __STU s2 = {a};  //如果结构体中有引用成员，定义变量时，必须初始化 
        return 0; 
     
    }

引用和指针的区别

  1. 引用必须初始化，指针可以不初始化；

  2. 指针可以改变指向，引用不能改变引用的对象；

  3. 存在指向NULL的指针，不存在引用NULL的引用；

  4. 指针使用时需要做非NULL检查，引用不用；

  5. 可以定义指针数组、不可以定义引用数组

int a = 10,b = 20;`

int *arr[2] = {&a, &b} //正确`

int &arr[2] = {a, b} //错误`

  1. 可以定义数组指针，也可以定义数组引用 (但是有点区别:数组引用不能指向二维数组，如下例子)

int arr[2][2] = {10,20,30,40};

int (*arr_p)[2] = arr;

int arr[2] = {10,20};

int (&arr_p)[2] = arr;

  1. 可以定义指针函数，也可以定义引用函数

int *func_p(int a, int b){}

int &func_p(int a, int b){}

  1. 可以定义函数指针，也可以定义函数引用

int func(int a, int b){}

int (*func_p)(int a, int b);

func_p = func;

int (&func_r)(int a, int b) = func;

  1. 可以定义指针的指针(二级指针) 不可以定义引用的引用(二级引用)

int a = 100;

int *p = &a;

int **pp = &p;

int a= 100;

int &r = a;

int &&rr = r; //错误

int &&r = 100; // 可以 叫做右值引用，（常引用）

C++11以上版本的编译器才支持这种用法

g++ ***.cpp -std=c++11

有的同学的电脑是

g++ ***.cpp -std=c++0x

翻转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include "list_node.h"

using namespace std;

int main() {
	// 定义链表 1 -> 2 -> 3 -> 4 -> 5 ->NULL
	ListNode node5 = { 5, nullptr };
	ListNode node4 = { 4, &node5 };
	ListNode node3 = { 3, &node4 };
	ListNode node2 = { 2, &node3 };
	ListNode node1 = { 1, &node2 };

	ListNode* list = &node1;

	// 打印链表
	ListNode* np = list;
	while (np) {
		cout << (*np).value << " -> ";
		np = (*np).next;
	}

	cout << " NULL " << endl;

	// 定义两个指针，一个指向当前遍历的节点，另一个指向之前的节点
	ListNode* curr = list;
	ListNode* prev = nullptr;

	// 翻转链表
	while (curr)
	{
		// 先临时保存指向下一个节点的指针
		ListNode* temp = (*curr).next;
		(*curr).next = prev;

		// 两个指针都向前移动
		prev = curr;
		curr = temp;
	}
	
	ListNode* newList = prev;

	np = newList;
	while (np) {
		cout << (*np).value << " -> ";
		np = (*np).next;
	}

	cout << " NULL " << endl;

	cin.get();
}

函数-递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

using namespace std;

// 用递归的方式定义阶乘函数
int factorial(int n) {

	// 基准情况
	if (n == 1)
		return 1;
	return factorial(n - 1) * n;
}

// 用递归的方式实现斐波那契数列的计算
int fib(int n){

	//基准情况
	if (n == 1 || n == 2)
		return 1;

	return fib(n - 1) + fib(n - 2);
}

int main() {

	cout << "5! = " << factorial(5) << endl;

	cout << "fib(9) = " << fib(9) << endl;
	cin.get();
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>

using namespace std;

// 定义一个二分查找函数，递归调用
int search(const int(&a)[10], int start, int end, int target) {
	// 基准情况, 如果数组已经没有元素，或者target超出了范围，没有找到, 直接返回 -1
	if (start > end || target < a[start] || target > a[end])
		return -1;

	// 计算中间位置坐标
	int mid = (start + end) / 2;

	// 比较中间位置数据和目标值的大小
	if (a[mid] == target)
		return mid;
	else if (a[mid] > target)
		return search(a, start, mid - 1, target); // 中间值比目标值大，搜索前半部分
	else
		return search(a, mid + 1, end, target); // 中间值比目标值小，搜索后半部分
}

int main() {
	int arr[10] = { 1, 2, 3, 4, 5, 6, 9, 12, 25, 38 };

	int key = 9;
	
	int size = sizeof(arr) / sizeof(arr[0]);

	int result = search(arr, 0, size - 1, key);

	result == -1 ?
		cout << "在数组中没有找到" << key << "!" << endl :
		cout << "在数组中找到" << key << ", 索引下标为：" << result << endl;
		
	cin.get();
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>

using namespace std;

int partition(int(&)[10], int, int);
void quickSort(int(&)[10], int, int);

void swap(int(&)[10], int, int);
void printArray(const int(&)[10]);

int main() {
	int arr[10] = { 23, 45, 18, 6, 11, 19, 22, 18, 12, 9 };

	printArray(arr);

	int size = sizeof(arr) / sizeof(arr[0]);

	quickSort(arr, 0, size - 1);

	printArray(arr);

	cin.get();
}

// 定义快速排序函数,递归实现
void quickSort(int(&a)[10], int start, int end) {

	// 基准情况
	if (start >= end)
		return;

	int mid = partition(a, start, end);

	// 递归调用，分别对两部分继续排序
	quickSort(a, start, mid - 1);
	quickSort(a, mid + 1, end);
}

// 按照支点分区的函数
int partition(int(&a)[10], int start, int end) {

	// 选取支点
	int pivot = a[start];

	// 指定指向数组头尾元素的“指针”
	int left = start, right = end;

	// 如果左右指针没有相遇，就继续移动
	while (left < right) {
		// 左指针不停右移，直到找到一个比支点大的值；右指针不停左移，直到找到一个小的值
		while (a[left] <= pivot && left < right)
			++left;
		while (a[right] >= pivot && left < right)
			--right;

		// 判断指针相遇位置的值，跟支点值的大小关系
		if (left < right) {
			// 左右互换
			swap(a, left, right);
		}
	}

	// 将支点值放到正确的位置上
	swap(a, start, left);

	return left;
}

// 交换数组中的两个元素
void swap(int(&a)[10], int i, int j) {
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

// 打印输出数组
void printArray(const int(&a)[10]) {
	for (int num : a)
		cout << num << "\t";

	cout << endl;
}

遍历二叉树

  • tree_node.h

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #pragma once
    #include<iostream>

    using namespace std;

    struct TreeNode
    {
    	string name;
    	TreeNode* left;
    	TreeNode* right;
    };

    void printTreePreOrder(TreeNode* root);
    void printTreeInOrder(TreeNode* root);
    void printTreePostOrder(TreeNode* root);

  • print_tree.cpp

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    #include <iostream>
    #include "tree_node.h"

    // 利用递归实现二叉树的先序遍历打印输出
    void printTreePreOrder(TreeNode* root) {
    	// 基准情况：如果是空树，就直接返回
    	if (root == nullptr) return;

    	// 先打印根节点的值
    	cout << root->name << "\t";

    	// 递归打印左右子树
    	printTreePreOrder(root->left);
    	printTreePreOrder(root->right);
    }

    // 中序遍历
    void printTreeInOrder(TreeNode* root) {
    	// 基准情况：如果是空树，就直接返回
    	if (root == nullptr) return;

    	// 先打印根左子树的值
    	printTreeInOrder(root->left);
    	// 打印根节点
    	cout << root->name << "\t";

    	// 递归打印右子树
    	printTreeInOrder(root->right);
    }

    // 后序遍历
    void printTreePostOrder(TreeNode* root) {
    	// 基准情况：如果是空树，就直接返回
    	if (root == nullptr) return;

    	// 先打印左右子树
    	printTreePostOrder(root->left);
    	printTreePostOrder(root->right);

    	// 再打印根节点的值
    	cout << root->name << "\t";

    }

  • traversal_tree.cpp

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    #include <iostream>
    #include "tree_node.h"


    int main() {
    	// 定义一棵二叉树
    	TreeNode nodeG = { "G", nullptr, nullptr };
    	TreeNode nodeF = { "F", nullptr, nullptr };
    	TreeNode nodeE = { "E", &nodeG, nullptr };
    	TreeNode nodeD = { "D", nullptr, nullptr };
    	TreeNode nodeC = { "C", nullptr, &nodeF };
    	TreeNode nodeB = { "B", &nodeD, &nodeE};
    	TreeNode nodeA = { "A", &nodeB, &nodeC };
    		
    	TreeNode* tree = &nodeA;

    	printTreePreOrder(tree);

    	cout << endl;

    	printTreeInOrder(tree);

    	cout << endl;

    	printTreePostOrder(tree);

    	cin.get();
    }