概述

笔记介绍

本笔记是 CS106B 课程(2018 秋)的学习笔记，主要内容包括数据结构和算法的基本概念、基本算法的实现、应用、分析和复杂度分析。

为什么没有 L1 和 L2?

前两个可是主要是在介绍 c++如果有需要可以参考之前的 c++笔记.

为什么没有 L7?

L7 在 cs106b(2018 秋)的课程中没有讲解，可能是因为 L7 的内容比较复杂，而且 L7 的内容也不是很重要，所以没有讲解。

I/Ostream

fstream

在这个库中分别有两个类可供使用,分别是 ifstream 和 ofstream.

ifstream 和 ofstream 分别用来读取和写入文件,ifstream 读取文件,ofstream 写入文件.

常见的将文件中的内容读取

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <iostream>
#include <fstream>

using namespace std;

int main() {
    ifstream inputFile("input.txt"); // 打开文件
    if (!inputFile) { // 判断文件是否打开成功
        cout << "Error: unable to open input file" << endl;
        return 1;
    }

    string line;
    while (getline(inputFile, line)) { // 读取文件内容
        cout << line << endl;
    }

    inputFile.close(); // 关闭文件
    return 0;
}

常见的向文件中写入内容

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#include <iostream>
#include <fstream>

using namespace std;

int main() {
    ofstream outputFile("output.txt"); // 打开文件
    if (!outputFile) { // 判断文件是否打开成功
        cout << "Error: unable to open output file" << endl;
        return 1;
    }

    outputFile << "Hello, world!" << endl; // 写入内容
    outputFile.close(); // 关闭文件
    return 0;
}

vector and grid

#include “vector.h”

这是斯坦福库中的一个头文件,里面包含了一些常用的向量操作函数,包括向量的初始化,向量的元素的访问,向量的插入,删除,查找等.

vector 避免了 c++数组的一些缺点,比如数组的大小是固定的,而 vector 的大小可以根据需要动态调整.

vector 的 insert 和 remove：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


#include "vector.h"

int main() {
    Vector<int> v;   // 声明一个向量
    v.insert(0, 1);  // 在索引0处插入元素1
    v.insert(1, 2);  // 在索引1处插入元素2
    v.insert(2, 3);  // 在索引2处插入元素3
    v.remove(1);     // 删除索引1处的元素
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;    // 输出: 1 3
    return 0;
}

其中的原理是通过指针来实现的,通过指针可以直接访问 vector 中的元素,而不需要像数组那样通过下标来访问.

#include “grid.h”

这是斯坦福库中的另一个头文件,里面包含了一些常用的网格操作函数,包括网格的初始化,网格的元素的访问,网格的插入,删除,查找等.

grid 和 vector 类似,也是通过指针来实现的,通过指针可以直接访问网格中的元素,而不需要像数组那样通过下标来访问.

和二元数组不同的是,网格可以有多个维度,比如二维网格,三维网格等.

grid 的遍历一般使用两个循环,第一个循环遍历行,第二个循环遍历列

vector and grid 的传递

值传递会复制一遍整个向量或网格,引用传递不会复制,而是直接传递指针,因此如果需要修改向量或网格中的元素,需要使用引用传递.

 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


#include "vector.h"

int main() {
    Vector<int> v1;
    v1.insert(0, 1);
    v1.insert(1, 2);
    v1.insert(2, 3);

    Vector<int> v2(v1); // 值传递
    for (int i = 0; i < v2.size(); i++) {
        cout << v2[i] << " ";
    }
    cout << endl;    // 输出: 1 2 3

    Vector<int>& v3 = v1; // 引用传递
    for (int i = 0; i < v3.size(); i++) {
        cout << v3[i] << " ";
    }
    cout << endl;    // 输出: 1 2 3

    v3.insert(0, 4);
    for (int i = 0; i < v1.size(); i++) {
        cout << v1[i] << " ";
    }
    cout << endl;    // 输出: 4 1 2 3
    return 0;
}

而是用 const 修饰的引用传递,可以防止修改原来的对象,但是不能修改元素的值.

Abstract Data Types ADTs(抽象数据类型)

ADT 的含义就是数据集合及其可以执行的操作的规范(增删改查),通常涉及效率权衡,内存使用权衡等等问题.

描述一个集合可以做什么，而不是如何做
我们可以说，Vector 和 LinkedList 都实现了名为“列表”的抽象数据类型的操作。

其他的 ADT 实例：栈、队列、集合、映射、图。

Linkedlist(链表)

节点

数据域：存储数据元素
指针域：指向下一个节点的地址

当你想插入元素的时候，你只需要创建一个新的节点，将其数据域设置为你要插入的数据，然后将其指针域设置为指向链表中下一个节点的地址，然后将这个新的节点插入到链表中。

当你想删除元素的时候，你只需要找到你要删除的节点，然后将其前一个节点的指针域设置为指向被删除节点的下一个节点的地址，然后删除被删除节点。

在执行某些操作的时候链表往往会十分高效.这些都是运用内存换来的.

Stacks(栈)

栈是一种线性数据结构，它只允许在表尾进行插入和删除操作。栈顶元素是最近添加的元素，栈底元素是最近删除的元素。栈的操作有入栈、出栈、查看栈顶元素、查看栈底元素。

Last-In-First-Out(LIFO)：栈顶元素是最近添加的元素，栈底元素是最近删除的元素。
only add/remove/examine operations allowed at the top of the stack.只能在栈顶进行操作。

Stack 的基本函数：

push: 入栈，将元素压入栈顶
pop: 出栈，删除栈顶元素
peek: 查看栈顶元素

include “stack.h”

s.isEmpty(): 判断栈是否为空
s.peek(): 查看栈顶元素
s.pop(): 返回并删除栈顶元素
s.push(x): 入栈元素 x
s.size(): 返回栈的大小

栈在计算机中非常的常见 undo stack 撤销栈操作：

编辑器的撤销操作
编译器的错误恢复
数据库事务的回滚操作
程序的回退操作

注意事项

栈的大小是有限的，当栈满时，不能再入栈，当栈空时，不能再出栈。
中括号运算符不适用于栈，因为栈的操作是先进后出。他只允许你访问最顶部的元素

Queues(队列)

队列是一种线性数据结构，它只允许在表头进行插入和删除操作。队列的操作有入队、出队、查看队首元素、查看队尾元素。

First-In-First-Out(FIFO)：队列的头部是最先进入队列的元素，尾部是最先离开队列的元素。
Elements are stored in order of insertion.元素按照插入的顺序排列。
Can add only to end of the queue,and can only examine/remove the front 只能在队列的末尾添加元素，并且只能检查和移除队列的前端元素。

基础函数

enqueue: 入队，将元素添加到队尾
dequeue: 出队，删除队首元素
peek: 查看队首元素
isEmpty: 判断队列是否为空
size: 返回队列的大小

队列在计算机中也非常常见

打印队列：打印机、打印队列
任务调度：操作系统的进程调度
缓存：缓存的淘汰策略
排队：银行排队

注意事项

队列的大小是有限的，当队列满时，不能再入队，当队列空时，不能再出队。
队列的操作是先进先出，所以队首元素是最先进入队列的元素，队尾元素是最先离开队列的元素。

Sets, Maps

Sets(集合)

在 library 中有两种集合:

set:使用一种名为二叉树的结构实现.
- 速度相当快;元素以排序顺序存储
- 值必须有一个 “<” 操作
hashset:使用一种称为哈希表的特殊数组实现。
- 非常快速；元素以不可预测的顺序存储。
- 值必须有一个 hashCode 函数（大多数标准类型提供）。

这两种的选择取决你是否按照排序顺序存放元素

**#include "set.h"**

**#include "hashset.h"**

Menber	Set	Hashset	description(描述)
s.add(value)	O(log N)	O(1)	添加元素到集合中
s.clear()	O(N)	O(N)	清空集合
s.contains(value)	O(log N)	O(1)	判断元素是否存在于集合中
s.isEmpty()	O(1)	O(1)	判断集合是否为空
s.isSubsetOf(set)	O(N log N)	O(N)	判断集合是否是另一个集合的子集
s.remove(value)	O(log N)	O(1)	从集合中删除元素
s.size()	O(1)	O(1)	集合中元素的数量
s.toStirng()	O(N)	O(N)	集合中元素的字符串表示

运算符

s1 == s2: 判断两个集合是否相等
s1 != s2: 判断两个集合是否不相等
s1 + s2: 合并两个集合
s1 += s2: 合并两个集合并更新第一个集合
s1 - s2: 集合 s1 中元素不在集合 s2 中的元素
s1 -= s2: 集合 s1 中元素不在集合 s2 中的元素并更新第一个集合
s1 * s2: 集合 s1 和集合 s2 的交集
s1 *= s2: 集合 s1 和集合 s2 的交集并更新第一个集合

注意: 无法使用 for 循环遍历集合中的元素，因为集合是无序的。

Lexicon(词典)

这就是以字符串构成的 Sets(集合)的例子。

Maps(映射)

Maps(映射)是键值对的集合。

组成部分:

key: 映射中的键
value: 映射中的值

映射是一种存储对集合的数据结构

**#include "map.h"** 使用一种称为二叉搜索树的链接结构实现。

所有操作速度相当快；键以排序顺序存储。
两种映射实现完全相同的操作。
值必须有一个 “<” 操作。

**#include "hashmap.h"** 使用一种称为哈希表的特殊数组实现。

速度非常快；键以不可预测的顺序存储。
值必须有一个 hashCode 函数（大多数标准类型提供）。

运算符

m.put(key, value): 添加键值对到映射中

1
2


m.put("bobo", "114-514"); //or
m["bobo"] = "114-514";

m.get(key): 获取键对应的值

1
2


string value = m.get("bobo"); //"114-514" or
string value = m["bobo"];

m.remove(key): 从映射中删除键值对

1

m.remove("bobo");

membership

成员	Map	HashMap	描述
m.clear()	O(N)	O(N)	移除所有键/值对
m.containsKey(key)	O(log N)	O(1)	如果映射中存在给定键的对，则返回 true
m[key] 或 m.get(key)	O(log N)	O(1)	返回映射到给定键的值；如果未找到，则以默认值添加
m.isEmpty()	O(1)	O(1)	如果映射不包含任何对，则为 true
m.keys()	O(N)	O(N)	返回映射中所有键的 Vector 复制
m[key] = value; 或 m.put(key, value);	O(log N)	O(1)	添加键/值对；如果键已存在，替换其值
m.remove(key)	O(log N)	O(1)	移除给定键的任何对
m.size()	O(1)	O(1)	返回映射中的对数
m.toString()	O(N)	O(N)	示例："{a:90, d:60, c:70}"
m.values()	O(N)	O(N)	返回映射中所有值的 Vector 复制
ostr « m	O(N)	O(N)	将映射打印到流中

Lotto ticket example 嵌套集合

集合之间可以相互嵌套

 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


#include <iostream>
#include <vector>
#include <set>
#include <map>

using namespace std;

int main()
{
    // Set of integers
    set<int> s1 = {1, 2, 3, 4, 5};
    set<int> s2 = {3, 4, 5, 6, 7};
    set<int> s3 = {5, 6, 7, 8, 9};

    // Map of sets
    map<string, set<int>> m;
    m["s1"] = s1;
    m["s2"] = s2;
    m["s3"] = s3;

    // Accessing values using keys
    cout << m["s1"].size() << endl; // Output: 5
    cout << m["s2"].size() << endl; // Output: 5
    cout << m["s3"].size() << endl; // Output: 5

    // Accessing values using iterators
    for(auto it = m.begin(); it != m.end(); it++) {
        cout << it->first << " : ";
        for(auto jt = it->second.begin(); jt != it->second.end(); jt++) {
            cout << *jt << " ";
        }
        cout << endl;
    }

    return 0;
}

big O notation(大 O 记法)

我们可以从不同方面来衡量一个算法的效率。

Efficiency(效率):衡量代码使用计算资源的程度。
- 可能相对速度（运行时间）、内存（空间）等。
- 最常指的是运行时间。
- 单个语句的运行时间 = 1。
- 一个函数调用的运行时间 = （函数体内语句运行时间的总和）。
- N 次迭代的循环运行时间 = (N * (循环体的运行时间))。

O(1)<O(log N)<O(N)<O(N log N)<O(N^2)<O(2^N)<O(N!)<O(N^N)<O(infinity)

Recursion

Recursion(递归)

简而言之就是自己运算自己

关键问题是:什么时候停止递归?

如果没有终止条件，递归会一直进行下去，导致栈溢出。所以，递归必须有终止条件。

递归和循环

递归和循环的区别在于：

递归是一种自上而下的计算方式，循环是一种自下而上的计算方式。
递归解决的问题一般都可以用循环来解决，但是循环解决不了的问题，这时候就需要用递归来解决。

例如：

计算机阶乘的两种实现方式：

递归：

1
2
3
4
5
6
7


int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

循环：

1
2
3
4
5
6
7


int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

递归的优点：

代码简单，容易理解。
递归可以解决很多问题，比如计算阶乘、计算二项式展开、计算组合数、计算汉诺塔、计算图的遍历等等。
递归可以代替循环，减少代码量。

递归的缺点：

递归调用栈的开销大，容易发生栈溢出。
递归容易陷入死循环。
递归代码的性能不一定比循环代码的性能好。

递归的应用

1.汉诺塔问题

汉诺塔问题是指将一堆盘子从左边移动到右边，又或者从右边移动到左边，最后移动到中间的过程。

汉诺塔问题的递归解法：

将 n-1 个盘子从左边移动到右边，中间放置一个空盘子。
将最底下的 n-1 个盘子从左边移动到中间。
将 n-1 个盘子从右边移动到中间。
将中间的空盘子放置在左边的最底下。

1
2
3
4
5
6
7
8
9


void hanoi(int n, char from, char to, char via) {
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    hanoi(n-1, from, via, to);
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    hanoi(n-1, via, to, from);
}

Recursion and Fractals

Fractals(分形)

分形： 一个自相似的数学集合，通常可以绘制为一个重复出现的图形模式。

同样形状或图案的较小实例在模式中出现。就像雪花一样
当在计算机屏幕上显示时，可以实现对分形的无限放大或缩小。

Examples of Fractals:

Sierpinski Triangle(谢尔宾斯基三角形)

Koch Snowflake(科赫雪花)

alt text

coding a fractal

使用递归函数来绘制分形。

但是在绘制之前,我们必须知道如何绘制

Stanford graphics lib

include "gwindow.h"

gw.drawline(x1, y1, x2, y2)画一条线在两点之间
gw.drawPolarLine(x,y,r,t)从 (x,y) 以角度 t 绘制长度为 r 的线段；返回线段的终点作为一个 Gpoint。
gw.getPixel(x,y) 返回 (x,y) 处的颜色值。
gw.setColor("color") 设置颜色,你可以使用颜色名称或者 RGB 值。
gw.setPixel 设置 (x,y) 处的颜色值。
gw.drawOval(x,y,w,h) 画一个椭圆。
gw.fillOval(x,y,w,h) 填充一个椭圆。 …….

实例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


#include <iostream>
#include "gwindow.h"

using namespace std;

int main()
{
    GWindow gw(300,200);
    gw.setTitle("bobo's GWindow");
    gw.setColor("red");
    gw.drawLine(20,20,100,100);
    return 0;
}

Backtracking

Exhaustive Search(穷举搜索)

现在很多方法可以进行穷举搜索，比如枚举、递归、回溯等。

但是对于某些问题,您可以用递归来进行穷举搜索，但是递归的层数太多，会导致栈溢出。

小练习:输出你想要位数的二进制数

这时候我们就会用到“树”的概念。

alt text

我们可以用递归来实现这个过程。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


void printBinaryHelper(int digits, string output) {
    if (digits == 0) {
        cout << output << endl;
    } else {
        printBinaryHelper(digits - 1, output + "0");
        printBinaryHelper(digits - 1, output + "1");
    }

}

void printBinary(int digits) {
    printBinaryHelper(digits, "");
}

这个函数的作用是输出从 0 到digits位的二进制数。

我们可以调用printBinary(3)来输出 0 到 3 位的二进制数。

Backtracking(回溯)

回溯是一种算法，它是一种穷举搜索的变体,称为回溯法

通过尝试部分解决方案来寻找解，并在不合适时放弃它们。

一种“暴力”算法技术（尝试所有路径）
通常采用递归实现

尝试多种可能性，如果进展不如意就回溯

和穷举类似,只是在其中还需要执行一个所谓的"撤销选择"的操作.

小练习:投色子游戏

例如:diceSum(2,7)

1
2
3
4
5
6


{1,6}
{2,5}
{3,4}
{4,3}
{5,2}
{6,1}

我们可以用回溯法来实现这个过程。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void diceSumHelper(int dice, int desiredSun, Vector<int>& chosen)
{
    if (dice == 0) {
        if (destiredSun == 0) {
            cout << chosen << endl;
        }
    }
    else {
        for (int i = 1; i <= 6; i++) {
            chosen.add(i);
            diceSumHelper(dice - 1, desiredSun - i,chosen);
            chosenremoveBack();
        }
    }
}

这个函数的作用是输出从 1 到 6 的骰子的组合，使得骰子的和等于desiredSun。

我们可以调用diceSumHelper(2,7)来输出 2 个骰子的组合。

1
2
3
4
5
6


{1,6}
{2,5}
{3,4}
{4,3}
{5,2}
{6,1}

可是这个算法有什么问题呢?

它会产生大量的重复计算，导致效率低下
它会产生大量的回溯，导致效率低下
它会产生大量的内存消耗，导致效率低下

总而言之效率低下

这就是所谓的暴力求解!

Backtracking 第二讲

还记得上一节所讲的回溯法投色子吗?

浪费了很多算力,产生了很多不必要的结果

那我们应该怎样改进呢?

优化

剪枝

**原理:**如果在某一时刻我们确信从此开始将无法继续,或许我会立刻撤回并且停止.

所以我们只需要在之前的选择中做出一些限制,使得之后的选择更加有利.

else if (desiredSum >= dice * 1 && desiredSum <= dice * 6) {.....}

这就被称之为"剪枝""!

回溯法的整体策略就是:

若面临选择,则处理其中一个选择,若处理后仍有选择,则回到之前的选择点继续处理,直到所有选择都处理完毕.
你进行选择,然后谈起其后每一种可能的发展,随后再撤销选择.
选择,探索,撤销选择每一种可能性

例子

问题: Permute Vector(排列向量)

编写一个名为 permute 的函数，该函数接受一个字符串的向量作为参数，并输出该向量中所有可能的字符串重排列。输出的排列顺序可以是任意的。

**示例：**如果 v 包含 { “a”, “b”, “c”, “d” }，你的函数应输出这些排列：

alt text

思路:

我们可以先将字符串向量中的每个字符串看作是一个字符,然后将其排列组合成新的字符串.
我们可以用一个循环来遍历向量中的每个字符串,然后将其与其他字符串组合成新的字符串,并将其加入到结果集中.
我们可以用一个递归函数来实现这个过程.

 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


void permuteHelper(Vector<string>& v, Vector<string>& chosen){
    if (v.isEmpty()){
        cout << chosen << endl;
    }else{
        for (int i = 0; i < v.size(); i++)
        {
            string s = v[i];
            chosen.add(v[i]);
            v.remove(i);

            permuteHelper(v,chosen);

            chosen.remove(chosen.size()-1);
            v.insert(i,s);

        }
    }
}

void permute(Vector<string>& v)
{
    Vector<string> chosen;
    permuteHelper(v, chosen);

}

这其实也是一种树状结构,我们可以用递归来实现.

回退出去以后进入 for 的下一个遍历,我们将当前的字符串加入到 chosen 中,然后将其从 v 中移除,然后递归调用 permuteHelper,直到 v 为空,此时输出 chosen.

然后我们将当前的字符串从 chosen 中移除,然后将其重新插入到 v 的相应位置,继续下一个遍历.

这样我们就实现了排列组合的过程.

Backtracking 第三讲

选择,探索,撤销选择

回顾之前的笔记,我想最重要不过是这句话:选择,探索,撤销选择

关于递归风格

一个术语叫做:arm’s length recursion(一臂之遥递归)

在人们编写递归代码的时候,他们往往回味代码添加不必要的复杂性

通常意味着那些无需存在的 if-else 语句,或者无用的变量,或者无用的函数调用

通常由另一种方式来组织这类代码结构，这也就是这门课程开设的意义

练习

所有子集

给定一个集合 S,求出 S 的所有子集。

例如: S = {1, 2, 3}

所有子集:

1
2
3
4
5
6
7
8


{1,2,3}
{1,2}
{1,3}
{1}
{2,3}
{2}
{3}
{}

这和上一节的题目比较类似,但是也有很大的不同

解法

alt text

和调用树,决策树不同,两条分支,并非四条.

我们应该这样来写

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


void sublistHelper(Vector<string>& v, Vector<string>& chosen)
{
    if (v.isEmpty())
    {
        cout << chosen << endl;
    } else {
        string s = v[0];
        v.remove(0);

        //- 选择and探索(一个有s, 另一个没有s)
        sublistHelper(v, chosen);

        chosen.add(s);

        sublistHelper(v, chosen);


        //- 撤销选择
        v.insert(0, s);
        chosen.remove(chosen.size() - 1);//删除最后一个元素
    }
}

8 皇后问题

八皇后问题是一个经典的回溯问题,它要求在一个 8x8 的棋盘上摆放八个皇后,使得任何两个皇后都不能互相攻击.

解法

首先,我们可以用一个二维数组来表示棋盘,其中每个元素的值表示皇后所在的列数.
然后,我们可以用一个数组来表示皇后所在的行数,因为每行只能放一个皇后.
我们可以用一个函数来表示是否可以放置皇后,这个函数的输入是列数,输出是是否可以放置.
我们可以用一个函数来表示是否有冲突,这个函数的输入是两个皇后所在的行数,列数,输出是是否有冲突.
我们可以用一个函数来表示摆放下一个皇后,这个函数的输入是棋盘,皇后所在的行数,输出是是否成功摆放.
我们可以用一个循环来表示所有可能的摆放,每次都调用上面的函数来尝试摆放下一个皇后,如果成功,则继续摆放下一个皇后,如果失败,则回溯到上一个皇后.
最后,我们可以用一个循环来表示所有可能的皇后位置,每次都调用上面的函数来尝试摆放八个皇后,如果成功,则输出结果,如果失败,则继续尝试下一个皇后位置.

 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


#include <iostream>
#include <vector>

using namespace std;

const int N = 8;

bool isValid(int row, int col)
{
    for (int i = 0; i < col; i++)
    {
        if (row == i || abs(row - i) == abs(col - i))
        {
            return false;
        }
    }
    return true;
}

bool placeQueen(vector<int>& queens, int row)
{
    for (int col = 0; col < N; col++)
    {
        if (isValid(row, col))
        {
            queens[row] = col;
            if (row == N - 1)
            {
                return true;
            }
            if (placeQueen(queens, row + 1))
            {
                return true;
            }
        }
    }
    return false;
}

void printQueens(vector<int>& queens)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (queens[i] == j)
            {
                cout << "Q ";
            } else {
                cout << "* ";
            }
        cout << endl;
    }
}

int main()
{
    vector<int> queens(N, -1);
    for (int i = 0; i < N; i++)
    {
        if (placeQueen(queens, i))
        {
            printQueens(queens);
            return 0;
        }
    }
    cout << "No solution found." << endl;
    return 0;
}

总结

回溯算法是一种非常强大的算法,它可以用来解决很多问题,但是它的实现方式却很有特点,需要我们对递归的理解更加深刻.

Classes, Arrays

引言

到目前为止，在本课程中，我们使用了许多集合类：

向量、网格、栈、队列、映射、集合、哈希映射、哈希集合、词汇表等。

从现在开始让我们探索它们是如何实现的。

我们将从实现自己的栈类版本开始。

为此，我们必须学习有关类、数组和内存分配的知识。

Classes

在面向对象编程中，类是创建对象的蓝图。类定义了对象的属性和方法。

而那些 c++中的数据结构，比如栈、队列、映射、集合等，都是使用类来编写的.

关于类的详解,可以去到前面的笔记c++.oop 类与对象编程

Interface vs.code(C++实现)

C++将类分为两种代码文件：

.h: 一个包含接口（声明）的“头文件”。
.cpp: 一个包含定义（方法体）的“源文件”。
class Foo => 必须同时编写 Foo.h 和 Foo.cpp。

.h 文件的内容会被 #include 进 .cpp 文件中：

使其能够识别在其他地方实现的代码声明。
在编译时，所有定义会被链接在一起形成可执行文件。

Arrays(数组)

数组是一种存储相同类型元素的固定大小的内存块。

数组的两种实现:

静态数组(Static Array): 静态数组在编译时就已经分配好了内存空间，数组的大小在编译时就已经确定了。

1

int arr[10]; // 10个整数数组

动态数组(Dynamic Array): 动态数组在运行时才分配内存空间，数组的大小可以根据需要增加或减少。

1
2


int* arr = new int[10]; // 10个整数数组
int* arr = new int[10](); // 10个默认初始化的整数数组

Memory Allocation(内存分配)

在 C++中，内存分配是通过 new 和 delete 关键字来完成的。

当我们使用 new 关键字申请内存时，系统会从堆中分配一块内存，并返回一个指向这块内存的指针。

当我们使用 delete 关键字释放内存时，系统会回收这块内存。

注意：当我们使用 new 关键字申请内存时，系统会自动调用构造函数来初始化这块内存。

注意：当我们使用 delete 关键字释放内存时，系统会自动调用析构函数来销毁这块内存。

How Vector/Stack works(向量/栈的实现原理)

向量内部是一个存储你添加的元素的数组。

通常，数组的大小大于目前添加的数据，以便有一些额外的槽位来放置后面的新元素。

我们称之为未填充数组。

如果数组随着你的增加从而增加他的存储这会使得效率非常的低下

因为在 C++中,数组实际上并不容易进行大小的调整

若想扩展数组,实际上就需要创建一个新的数组并将所有元素一一复制过去,这是一个很慢的过程

所以,有了"未填充数组"的概念,使其拥有额外的槽位.

ArrayStack(用数组实现栈)

在头文件里面我们需要命名变量和函数,然后在源文件里面实现函数的具体实现.

 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


#ifndef _ARRAYSTACK_H
#define _ARRAYSTACK_H

#include<iostream>
using namespace std;


class ArrayStack{
public:

    //构造函数
    ArrayStack();

    //函数
    void push(int n);

    int pop();

    int peek();

    //成员

    int* element;
    int size;
    int capacity;
};

#endif // ARRAYSTACK_H

 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"ArrayStack.h"

ArrayStack::ArrayStack()
{
    element = new int[10]();
    size = 0;
    capacity = 10;
}

void ArrayStack::push(int n)
{
    element[size] = n;
    size++;
}

int ArrayStack::pop()
{
    int s = element[size-1];
    element[size-1] = 0;
    return s;
}

int ArrayStack::peek()
{
    return element[size-1];
}

Pointers and Linked Lists

Linked data structures(链表数据结构)

一些集合使用节点的链接序列来存储数据。

每个节点存储一个元素及一个指向其他节点的链接。

例子：集合（Set）、映射（Map）、链表（LinkedList）

优点:在任何位置添加/删除速度快；不需要移动、不需要调整大小。

缺点:需要额外的内存空间来存储链接。访问列表的某些部分较慢。

Structs(结构体)

结构体是一种数据类型，它可以包含多个成员变量。

结构体就是一个小型的类，它可以包含数据成员和函数成员。

但是一般用来存放数据，而不是用来定义行为。

例如我们定义一个名为 date 的结构体:

1
2
3
4


struct Date{
    int month;
    int day;
};

Memory addresses(内存地址)

内存地址是一个数字，它唯一地标识一个内存位置。

在 C++中，可以使用&运算符来获取变量的内存地址。

十六进制表示法:内存地址以十六进制表示，以0x开头。

例如，0x7fff0000是一个常用的地址，表示系统的堆栈区。

有趣的是:结构体的内存地址和结构体变量的第一个成员的内存地址是一样的。而,第二个变量比前地址向前偏移了若干字节.

Pointers(指针)

type* name = address

指针是一个变量，它存储着另一个变量的内存地址。

引用是指针的简化版本，它只存储一个变量的内存地址。

指针可以指向任意类型的变量，包括结构体。

指针可以用来访问变量的值，也可以用来修改变量的值。

几种指针的变体:

空指针(null pointer): 指针变量没有指向任何内存地址。

如果你想输出一个*空指针,那么你的程序会崩溃.

未初始化指针(uninitialized pointer): 指针变量没有被初始化。

如果你试图使用一个未初始化的指针,那么你的程序也会崩溃.

1
2
3
4
5


int* p1 = nullptr; // 空指针

if(p1 == nullptr)// true
if(p1) // false
if(!p1) // true

野指针(dangling pointer): 指针变量指向一个已经被释放的内存地址。

Point to a struct(指向结构体):

type* name = new type(parameters);

符号->用来访问结构体的成员变量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


struct Person{
    string name;
    int age;
};

int main(){
    Person* p = new Person;
    p->name = "John";
    p->age = 25;
    cout << p->name << " " << p->age << endl;
    delete p;
    return 0;
}

我们来进行一个比较:

1
2
3
4
5
6
7
8
9


// 1) non-pointer
Date d1;
d1.month = 7;
d1.day = 13;

// 2) pointer
Date* d2 = new Date();
d2->month = 7;
d2->day = 13;

很线性第一种语法更为简洁,有时我们会采用这种语法.

该问题和作用域有关,第一种在函数中定义的变量,其生命周期只在函数内,而在函数外,其生命周期则是整个程序的生命周期.

但是第二种就不会被销毁,直到程序结束.或是我们主动 delete

A list node structure(链表节点结构)

1
2
3
4


struct ListNode{
    int date;
    ListNode* next;
};

每一个链表节点都包含:

一个整数值(date)
一个指向下一个节点的指针(next)

你会发现,如果你将链表连起来,指针就可以连起来.就是可以如图所示

Linked Lists 第二课时

引用传递：

在编写添加函数的时候我们会遇到一个问题

1
2
3
4
5


void addFront(ListNode* front, int value){
    ListNode* temp = new ListNode(value);
    temp->next = front;
    front = temp;
}

你会发现,这段代码没有任何作用;

这是因为这段代码用的是值传递;

值传递的本质是:

拷贝函数参数的副本
对副本进行修改
原参数不受影响

因此我们需要使用引用传递:

1
2
3
4
5


void addFront(ListNode*& front, int value){
    ListNode* temp = new ListNode(value);
    temp->next = front;
    front = temp;
}

没错,我们在函数声明中添加了一个引用符号&,这意味着我们传递的是引用而不是副本.

况且,引用传递更加快速和灵活,因为它可以直接修改原参数,而不需要拷贝副本.

在结尾处添加元素

根据思路我们写出了第一版代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


void add(ListNode*& front, int value) {
    ListNode* current = front;
    while (current->next != nullptr) {
        current = current->next;
    }

    // current points to the last node
    ListNode* newNode = new ListNode(value);
    newNode->next = nullptr;
    current->next = newNode;
}

此时你会发现,这段代码会报错:

alt text

大致长这样

这是因为:执行过程中尝试解引用了一个为 NULL 或无效的指针,这段函数并不适用于链表为空的时候.

所以

指针是由为危险的!!!!!!!!!!!!!!!!!!!

那么我们如何解决他呢?

解决方法:

我们可以先判断链表是否为空,如果为空,我们直接创建一个新的节点,然后将其作为链表的头节点.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


void add(ListNode*& front, int value) {
    if (front == nullptr) {
        // empty list
        front = new ListNode(value);
    } else {
        // non-empty list; general case
        ListNode* current = front;
        while (current->next != nullptr) {
            current = current->next;
        }
        // current points to the last node
        ListNode* newNode = new ListNode(value);
        newNode->next = nullptr;
        current->next = newNode;
    }
}

这种模板可以用于几乎任何链表的问题

Fristremove(删除第一个)

删除数据如果处理的不到位,那么就会造成内存泄漏

所以我们需要delete掉要删除的节点

然后我们就需要考虑各种情况:

链表是否存在
链表是否有第二个 node

….

Links List Stack Classes

还记得几节课之前的的 ArrayStack 吗？

这节课我们继续学习.

但是在这之前我们还需要了解 c++中的一些东西

`Const`

const关键字是用来修饰变量的，用来表示这个变量是常量，不能被修改。

const 的意思就是恒定不变,即无法更改的事物.

一个 const 引用参数不能被函数修改：

1
2
3
4


void f(const int& x) {
    // x is a const reference to a const object
    // x cannot be modified
}

一个 const 成员函数不能改变对象的状态：

1
2
3
4


class BankAccount {
    ...
    double getBalance() const;
};

ArrayStack

那么 ArrayStack 里面那些函数使用const关键字呢?

大概有这几个:

int peek() const
int isEmpty() const
int toString() const

Operator Overloading(重载运算符)

运算符重载是指在已有的运算符的基础上,定义新的运算符,使得其作用在特定的数据类型上.

是的但是这就是 C++,自由而又危险.

operator«

详情可见:c++.opp/运算符重载

Destructor(析构函数)

析构函数是用来释放内存的,当对象被销毁时,析构函数就会被调用.

详情请见:c++.oop/构造函数和析构函数

A LinkedIntlist class

内存的释放

我们不够使用front = nullptr;来释放内存,因为这样做会导致内存泄漏.

正确的做法是使用delete来释放内存.

1
2
3
4
5
6
7


LinkIntList::~LinkIntList() {
    while (front!= nullptr) {
        LinkInt* temp = front;
        front = front->next;
        delete temp;
    }
}

Priority Queue and Heaps(优先队列和堆)

优先级问题

打印任务：实验室打印机接受来自整个大楼的任务。教师的打印任务优先于工作人员，然后是研究生和本科生的任务。
急救调度：枪伤受害者应优先于感冒患者进行处理，无论到达时间如何。

我们想要一个“队列”，功能包括：

添加一个元素（打印任务、患者等）
获取/移除最“重要”或“紧急”的元素

优先队列

提供对其最高优先级元素的快速访问。

enqueu：以给定优先级添加一个元素
peek：返回最高优先级值
dequeue：移除/返回最高优先级值

Heaps(堆)

堆必须是完全二叉树.

那么什么是完全二叉树呢:

除了最底层,其他层的节点都有两个子节点
从左到右,节点的索引是其在数组中的位置
最后一行元素之间不能有间隔

堆的性质:

堆序性:

我们可以把堆分为两类:

- 大根堆:每个节点的值都大于或等于其子节点的值
- 小根堆:每个节点的值都小于或等于其子节点的值

把堆看作一棵树,根节点的值是最小的或最大的,并且树的结构保持堆序性.

对可以用数组来实现的堆来说,父节点的索引是i/2,左子节点的索引是2i+1,右子节点的索引是2i+2.

堆的基本操作

上滤: 将一个元素添加到堆中,我们需要将其与父节点比较,如果父节点的值比新元素小,我们就交换它们的位置,直到新元素的位置被找到.
下滤: 当我们从堆中移除一个元素时,我们需要将其与最后一个元素交换,然后将它与新的最后一个元素比较,直到它被放到正确的位置.

建堆

自下而上建堆法:

从最后一个非叶子节点开始,对每个节点执行下滤操作
最后一个非叶子节点的索引是n/2-1,其中n是堆的大小
时间复杂度:O(n)

堆排序

如果你想排出来是正序,那么请使用大根堆,反之,请使用小根堆.

建堆
交换堆顶元素和最后一个元素
下滤最后一个元素
重复步骤 2 和 3,直到堆为空
时间复杂度:O(nlogn)

Binary Trees(二叉树)

他是涉及如何高效实现一个集合的问题

Tree(树)

一种有向的、无环的链接节点结构。

什么是有向？:

节点之间有单向链接。
什么是无环？:

没有路径会回绕到同一节点两次。

最常见的树结构是二叉树。

Binary Tree(二叉树)

二叉树就是每个节点最多有两个子节点的树。

树要么是空,要么是一个根节点

空: 树中没有节点(nullptr)
根节点: 树的顶端节点
- 数据
- 左子树
- 右子树

tree node

1
2
3
4
5
6


struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

print tree

1
2
3
4
5
6
7
8
9


void print(TreeNode* node) {
    cout << node->date << endl;
    if (node->left != nullptr) {
        print(node->left);
    }
    if (node->right != nullptr) {
        print(node->right);
    }
}

但是这段代码有个小问题: 就是根节点如果为空，那么就会崩溃。

1
2
3
4
5
6
7


void print(TreeNode* node) {
    if (node != nullptr) {
        cout << node->date << endl;
        print(node->left);
        print(node->right);
    }
}

size of tree

1
2
3
4
5
6
7


int size(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }else {
        return 1 + size(node->left) + size(node->right);
    }
}

Binary Search Trees(二叉搜索树)

Traversals(遍历)

遍历可谓是任何数问题的最佳途径

对于任何的树型问题,你都需要进行一种操作,即审视节点及其子节点.

常见的遍历有三种:

前序遍历(Preorder Traversal): 先访问根节点,再访问左子树,最后访问右子树.
中序遍历(Inorder Traversal): 先访问左子树,再访问根节点,最后访问右子树.
后序遍历(Postorder Traversal): 先访问左子树,再访问右子树,最后访问根节点.

实例:

alt text

前序排列:17 41 29 6 9 81 40
中序排列:29 41 6 17 81 9 40
后续排列:29 6 41 81 40 9 17

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


void preorder(Node* root) {
    if (root == NULL) return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}//前序遍历

void inorder(Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}//中序遍历

void postorder(Node* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}//后序遍历

Contains(查找)

查找操作是二叉搜索树的基本操作之一.

解决方法依旧是使用遍历

1
2
3
4
5
6
7
8


bool contains(TreeNode* node, int value){
    if(node == nullptr) return false;
    else if (node->date == value) return true;
    else{
        return contains(node->left, value);
        return contains(node->right, value);
    }
}

这是如果运行你姐会发现问题

在递归调用的 else 分支中，您分别调用了 contains(node->left, value) 和 contains(node->right, value)，但它们是分开写的 return 语句。由于函数遇到第一个 return 语句后会直接返回，导致对右子树的检查永远不会执行。

1
2
3
4
5
6
7



bool contains(TreeNode* node, int value) {
    if (node == nullptr) return false;
    if (node->date == value) return true;
    // 如果左子树中找到，返回 true；否则检查右子树
    return contains(node->left, value) || contains(node->right, value);
}

如果这样写就不会有问题

Binary Search Tree (二叉搜索树)

简称 BST,是一种二叉树，其中每个非空节点 R 具有以下属性：

R 的左子树中的每个元素包含的数据小于 R 的数据，
R 的右子树中的每个元素包含的数据大于 R 的数据。
R 的左子树和右子树也是二叉搜索树。

使用二叉搜索树可以实现快速查找、插入和删除操作，时间复杂度为 O(log n)。

为什么呢?

如果使用二叉搜索树,我们就可以用类似于二分法的方式来查找元素。

只需要查找树的一次,这样的查找自然比遍历整个树要快得多。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


bool contains(TreeNode* node, int value) {
    if (node != nullptr) {
        if (node->data == value) {
            return true;
        } else if (node->data > value) {
            return contains(node->left, value);
        } else {
            return contains(node->right, value);
        }
    }
    return false;
}

二叉搜索树获取最大最小值非常的容易,只需要分别从根节点的左右子树中进行查找即可。

Adding To BST(添加)

和查找类似,我们只需要找到合适的位置,然后插入即可。

1
2
3
4
5
6
7
8
9


void add(TreeNode*& node, int value) {
    if (node == nullptr) {
        node = new TreeNode(value);
    } else if (node->data > value) {
        add(node->left, value);
    } else if (node->data < value) {
        add(node->right, value);
    }
}

Deleting From BST(删除)

删除操作也很简单,只需要找到要删除的节点,然后将其替换为它的后继节点,或者它的前驱节点。

如果要删除的节点没有子节点,那么直接将其删除即可。

如果要删除的节点只有一个子节点,那么直接将其子节点替换为其位置即可。

如果要删除的节点有两个子节点,那么找到后继节点,然后将其替换为要删除的节点,然后删除后继节点。

 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


void deleteNode(TreeNode*& node, int value) {
    if (node == nullptr) return;
    if (node->data == value) {
        if (node->left == nullptr && node->right == nullptr) {
            delete node;
            node = nullptr;
        } else if (node->left == nullptr) {
            TreeNode* temp = node;
            node = node->right;
            delete temp;
        } else if (node->right == nullptr) {
            TreeNode* temp = node;
            node = node->left;
            delete temp;
        } else {
            TreeNode* temp = getSuccessor(node->right);
            node->data = temp->data;
            delete temp;
        }
    } else if (node->data > value) {
        deleteNode(node->left, value);
    } else {
        deleteNode(node->right, value);
    }
}

TreeNode* getSuccessor(TreeNode* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

Free Tree(释放树)

为了避免在丢弃树时泄漏内存，我们必须释放每个节点的内存。

像大多数树问题一样，通常是递归地编写。

必须释放节点本身及其左/右子树。

这也是树的另一种遍历。

1
2
3
4
5
6


void freeTree(TreeNode* node) {
    if (node == nullptr) return;
    freeTree(node->left);
    freeTree(node->right);
    delete node;
}

Advanced Trees(高级树)

remove from a BST(删除 BST 中的节点)

如果要删除的节点没有子节点,那么直接将其删除即可。

如果要删除的节点只有一个子节点,那么直接将其子节点替换为其位置即可。

如果要删除的节点有两个子节点,那么找到后继节点,然后将其替换为要删除的节点,然后删除后继节点。

 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


void deleteNode(TreeNode*& node, int value) {
    if (node == nullptr) return;
    if (node->data == value) {
        if (node->left == nullptr && node->right == nullptr) {
            delete node;
            node = nullptr;
        } else if (node->left == nullptr) {
            TreeNode* temp = node;
            node = node->right;
            delete temp;
        } else if (node->right == nullptr) {
            TreeNode* temp = node;
            node = node->left;
            delete temp;
        } else {
            TreeNode* temp = getSuccessor(node->right);
            node->data = temp->data;
            delete temp;
        }
    } else if (node->data > value) {
        deleteNode(node->left, value);
    } else {
        deleteNode(node->right, value);
    }
}

TreeNode* getSuccessor(TreeNode* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

Stanford Set(斯坦福集合)

使用（略微修改的）二叉树实现

有序元素
O(log N)时间搜索、添加和删除元素

树成员模板

1
2
3
4
5
6
7
8


returnType TreeSet::functionName(parameters)
{
    helper(root, parameters);
}

returnType helperName(TreeNode* node, parameters){
    ...
}

Tree maps(树映射)

每个树节点将同时存储一个键（key）和一个值（value）
树是按其键(key)的二叉搜索树（BST）顺序排列
键必须是可比较的（具备 < 运算符）以便进行排序

1
2
3
4
5
6


struct TreeMapNode {
    string key;
    int value;
    TreeMapNode* left;
    TreeMapNode* right;
};

Balanced Trees(平衡树)

当你的二叉搜索树不平衡的时候,你将会失去(log n)的性质.

就像如果你存入了 10000 个元素,但是你却只用了 100 个,那么你就失去了对这 100 个元素的快速查找的能力.

为了解决这个问题,我们需要使用一种平衡树,比如 AVL 树,红黑树,或者伸展树.

Red-Black Trees(红黑树)

给每个节点赋予红色或黑色的“颜色”。

根节点是黑色。根节点的直接子节点是红色。所有叶子节点是黑色。
如果一个节点是红色，则它的所有子节点必须都是黑色。
从一个节点向下到最底部的每条路径必须包含相同数量的“黑色”节点。

树旋转(Tree Rotations)

左旋(Left Rotation)：将一个节点的右子树上移，使其成为父节点的左子树。
右旋(Right Rotation)：将一个节点的左子树上移，使其成为父节点的右子树。
左右旋(Left-Right Rotation)：先左旋，再右旋。
右左旋(Right-Left Rotation)：先右旋，再左旋。

Tries(Prefix Trees)

非常适合用于查找前缀或作为字典使用

每个节点对应于一个单词的字母，通过遍历树来追溯这个单词
每个节点知道到该节点的字母是否能拼成一个单词

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


struct TrieNode{
    bool isWord;
    trieNode* children[26];
};

## 扩展(哈夫曼树)

哈夫曼树（Huffman Tree）是一种用于数据压缩的树形结构，主要用于生成哈夫曼编码。其主要特点和构建方法如下：

1. 构造一棵二叉树，每个节点对应于一个字符，树的高度为字符的个数。

2. 构造一棵带权路径最短的二叉树，权值即字符出现的频率。

3. 合并两个二叉树，权值较大的树作为左子树，权值较小的树作为右子树。

4. 重复步骤3，直到得到一棵只有一个节点的树，即哈夫曼树。

Graphs

Graphs(图)

一组顶点（有时称为节点）
一组边（有时称为弧），表示两个顶点之间的连接。

Paths(路径)

路径：从顶点 a 到 b 的路径是一系列边，可以从 a 开始沿着 c,d,f 这些边到达。

可以表示为经过的顶点或所经过的边。

路径长度:路径中包含的顶点或边的数量。
链接或者相邻:两个顶点通过一条边直接连接.
可达性:从顶点 a 到顶点 b 是否存在路径。
连通性:如果每个顶点都可以从其他每个顶点到达，那么一个图是连通的。
完全图:如果每个顶点与其他每个顶点都有一条直接边，则该图是完全的
循环:如果路径中包含一个顶点，则该路径是循环的。
循环图: 图中至少存在一条回路。
环: 回路中除了起点和终点之外的部分。

Weighted graphs(加权图)

这意味着边上附有权重或成本

Directed graphs(有向图)

这意味着边上有方向。

边也就是向量

它具有指向性

Linked Lists, Trees, graphs

其实之前所说的二叉树, 链表, 树都是图的一种特殊形式。

Stanford BasicGraph

Stanford BasicGraph 是一种图数据结构，它提供了一些基本的操作，如创建图、添加顶点、添加边、删除顶点、删除边、查找顶点、查找边、打印图、深度优先搜索、广度优先搜索、最小生成树、最短路径等。

**# include “basicgraph.h”

g.addEdge(v1, v2); 在两个顶点之间添加一条边
g.addVertex(name); 向图中添加一个顶点
g.clear(); 从图中移除所有顶点和边
g.getEdgeSet(); 返回图中所有边，或者返回从顶点 v 开始的所有边，以指针集合的形式
g.getNeighbors(v); 返回顶点 v 连接的所有顶点集合
g.getVertex(name); 返回具有给定名字的顶点的指针
g.getVertexSet(); 返回图中所有顶点的集合
g.isNeighbor(v1, v2); 如果从顶点 v1 到 v2 存在一条边，则返回 true
g.isEmpty(); 如果图中没有顶点和边，则返回 true
g.removeEdge(v1, v2); 从图中移除一条边
g.removeVertex(name); 从图中移除一个顶点
g.size(); 返回图中顶点的数量
g.toString(); 返回一个字符串，例如 “{a, b, c, a -> b}"，描述图的结构

Depth-first search, Breadth-first search

深度优先搜索 (DFS) 与广度优先搜索 (BFS) 是图的两个最基本的搜索算法。

Depth-first search

你选择一个"邻居"顶点，然后尽可能地跟随他,看看这是否可以将你到达目的地.如果到达那么就停止, 否则你就回去重新尝试另一个

这边有一段伪代码:

1
2
3
4


dfs from v1 to v2:
    mark v1 as visited, and add to path
    perform a dfs from each of v1's unvisited neighbors n to v2
    if dfs(n,v2)succeeds: a path is found!

Breadth-first search

该算法会从根节点开始，逐层访问节点，即先访问根节点，然后访问根节点的所有邻居节点，接着访问这些邻居节点的未访问过的邻居节点，以此类推，直到所有节点都被访问。

优点: 适用于寻找最短路径

缺点: 相较于 DFS，BFS 算法需要更多的内存，因为它需要维护一个队列来存储未访问的顶点。

Dijkstra’s and A

BFS

我们继续回到 BFS 广度优先算法

其中的思想就是，将你所有正在查找到节点存储在一个队列之中

总是找到最短路径（最少边）。

在无权图中，找到最优成本路径。

在有权图中，不总是找到最优成本。

一旦找到路径，重建实际顶点或边的顺序更难。

从概念上讲，宽度优先搜索（BFS）并行探索许多可能路径，因此不易在进行中存储路径数组/列表。

解决方案：我们可以通过存储每个顶点的前驱来跟踪路径。

深度优先搜索（DFS）使用的内存少于 BFS，更容易重建找到的路径；但 DFS 并不总是找到最短路径，而 BFS 可以。

DFS, BFS, runtime and weight

DFS: O(V+E)
BFS: O(V+E)
runtime: O(V+E)

Dijkstra’s algorithm

该算法一般在加权有向图中使用，其思想是：

选择一个源点，并将其距离设为 0，其他顶点的距离设为无穷大。
选择距离源点最近的顶点，并将其标记为已访问。
对于该顶点的每一个邻居顶点，更新其距离。
重复步骤 2 和 3，直到所有顶点都被访问。

算法的运行时间为 O(ElogV)，其中 E 为图中的边数，V 为顶点数。

伪代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


Dijkstra(G, s):
    for each vertex v in G:
        v.distance = infinity
        v.predecessor = null
    s.distance = 0
    Q = priority queue of vertices
    Q.enqueue(s)
    while Q is not empty:
        u = Q.dequeue()
        for each neighbor v of u:
            if v.distance > u.distance + weight(u, v):
                v.distance = u.distance + weight(u, v)
                v.predecessor = u
                Q.decrease_key(v)

A* algorithm

A*算法是 Dijkstra 算法的扩展，其思想是：

选择一个源点，并将其距离设为 0，其他顶点的距离设为无穷大。
选择距离源点最近的顶点，并将其标记为已访问。
对于该顶点的每一个邻居顶点，更新其距离。
对于距离源点最近的顶点，更新其距离。
重复步骤 2-4，直到所有顶点都被访问。

相比与 Dijkstra 算法，A*算法在选择下一个顶点时，考虑了到达该顶点的实际距离。

算法的运行时间为 O(ElogV)，其中 E 为图中的边数，V 为顶点数。

伪代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


A_star(G, s):
    for each vertex v in G:
        v.distance = infinity
        v.predecessor = null
    s.distance = 0
    Q = priority queue of vertices
    Q.enqueue(s)
    while Q is not empty:
        u = Q.dequeue()
        for each neighbor v of u:
            if v.distance > u.distance + weight(u, v):
                v.distance = u.distance + weight(u, v)
                v.predecessor = u
                Q.decrease_key(v)
        for each neighbor v of u:
            if v.distance > u.distance + weight(u, v) + heuristic(v, s):
                v.distance = u.distance + weight(u, v) + heuristic(v, s)
                v.predecessor = u
                Q.decrease_key(v)

其中，heuristic(v, s)表示从顶点 v 到源点 s 的估计距离。

A*算法的运行时间比 Dijkstra 算法的运行时间更长，但其在有权图中更加准确。

MSTs

最小生成树

最小生成树（Minimum Spanning Tree, MST）是一种用来连接所有顶点的无环连通图的树，它具有以下两个性质：

连接所有顶点的最小权重的边。
树中任意两个顶点间的路径上边的权重之和最小。

Kruskal 算法

Kruskal 算法是一种贪心算法，它通过按权重从小到大选择边，并保证所选边不形成回路，来构造最小生成树。具体步骤如下：

按权重从小到大排序所有边。
选择权重最小的边
如果该边不形成回路，则将其加入最小生成树中，否则舍弃该边。

Graph Implementation

Edge list

图中所有边的无序列表。

它可以是一个数组，向量，链表或者结合

每条边存储起始/结束顶点。

顶点并没有被明确地存储在任何地方；顶点集 V 隐式包含在边缘列表中。

使用边缘列表你可以做到

给定顶点的所有邻居？一个给定顶点的度数？
是否存在从 A 到 B 的边？
是否存在自环（自边）？

Adjacency list

图中每个顶点的邻居列表。

就像这样：

alt text

每条边存储起始/结束顶点，以及权重。

和上面的 Edge list 相比

Adjacency matrix

图中每个顶点的邻居矩阵。

k[i][j] 表示顶点 i 到顶点 j 的权重。

0 表示不存在边。

1 表示存在边。

如果是无向图，则 k[i][j] = k[j][i]。

如果边存在权重，这数组内部存储权重，不连接就取无限(也有的取无限大)

Hashing

introduction

在正常情况下,set 中查找的时间复杂度为 O(n),而在 hashset 中查找的时间复杂度为 O(1).

其中的原理就是:

首先,将 set 中的元素通过 hash 函数映射到一个有限的空间中,得到一个索引值.
然后,通过索引值,在 hashset 中查找元素.

就相当于,不需要遍历,你就知道数据存储在哪个位置

hashing

hash这个单词在计算机科学中被广泛使用

定义: 一个函数,它接受一个输入,并返回一个固定大小的输出值,该输出值被称为hash value或hash code
特点:
- 一致性: 对于相同的输入,得到的输出值必须相同
- 高效性: 计算 hash 值的时间复杂度应该尽可能低
- 均匀性: 对于不同的输入,得到的输出值应该尽可能均匀分布

常见的方法有取绝对值

可是这样做会有一个问题

这个问题就是碰撞: 不同的输入得到相同的输出值

处理方法:

探测: 当碰撞发生时,通过另一个函数来计算下一个索引值,直到找到一个空的位置

但是我十分不认同这个方法

如果这样的话,你的程序随着数据越来越多,就会原来越慢,组件的趋向于 O(n)

分离链接法: 在这里数组的每一个索引处,并非存储单一的值而是存储了一个链表

1
2
3
4


struct HsahNode {
    int data;
    HashNode* next;
}

这个方法的好处就在于,你永远不会用完空间

rehashing

当 hashset 中的元素越来越多时,hashset 的性能会下降,这时就需要进行rehashing操作

rehashing的过程就是,将原来的 hashset 中的元素重新 hash 到新的 hashset 中

扩容: 原来的 hashset 的大小变为原来的两倍,并重新 hash
收缩: 原来的 hashset 的大小变为原来的一半,并重新 hash

以下是伪代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


rehashing(hashset):
    if size > 2 * capacity:
        new_capacity = 2 * capacity
    else:
        new_capacity = capacity
    new_hashset = create_hashset(new_capacity)
    for i in range(capacity):
        if hashset[i]!= NULL:
            for j in hashset[i]:
                insert(new_hashset, j)
    return new_hashset

Advanced Hashing

rehashing

我们为什么要进行 rehashing？

解决碰撞问题
扩大 hash table 的大小
我们希望的是让链表尽量变小,仅仅包含几个元素

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


void rehash()
{
    int oldCapacity = capacity;
    HashNode** oldTable = hashTable;
    capacity *= 2;
    hashTable = new HashNode*[capacity]();
    for (int i = 0; i < oldCapacity; i++)
    {
        HashNode* curr = oldTable[i];
        while (curr!= nullptr)
        {
            HashNode* next = curr->next;
            int hash = hashCode(curr->data);
            curr->next = hashTable[hash];
            hashTable[hash] = curr;
            curr = next;
        }
    }
    delete[] oldTable;
}

首先，我们将原来的 hash table 的大小扩大为原来的两倍。
然后，我们创建一个新的 hash table，大小为原来的两倍。
我们遍历原来的 hash table，将每个元素重新插入到新的 hash table 中。
最后，我们删除原来的 hash table。

hashCode and equality

一个 hashCode 函数应该具有以下特点:

输入同一个 date,返回的值一定要是一样的
输出不同的 date,返回的值一定是不一样的

一个 good hashcode 函数应该具有以下特点:

简单
均匀分布
避免碰撞
快速

hash string

对于字符的 hashing,稍微复杂一点,对于二十六个字母,出现的频次并不相同

我们加入加权会显得更好一点

就像这样:

alt text

1
2
3
4
5
6
7
8
9


int hashCode(string str)
{
    int hash = 5381;
    for (int i = 0; i < str.length(); i++)
    {
        hash = 31 * hash + (int)str[i];
    }
    return hash;
}

这是其实就是 java 中的 hashing string

这明显减少了碰撞的发生

但是其中也是有代价的:计算量大,时间复杂度高

Another use

不仅在计算机界 hashing 的作用很大,在密码学届 hashing 的作用也很大

加密: 加密算法的目的就是为了防止信息被窃取,所以加密算法的 hash 函数的设计就需要考虑到安全性
密码学: 密码学的 hash 函数的设计就需要考虑到安全性,因为密码学的应用场景就是保密性

拓展:cuckoo hashing(布谷鸟哈希)

这是一种高效的哈希表实现方法，旨在减少哈希冲突并提高查找、插入和删除操作的效率。布谷鸟哈希的核心思想来源于布谷鸟在筑巢时的行为，即如果一个位置被占用，布谷鸟会将那个位置的原有鸟蛋移走，然后在移走的鸟蛋的位置继续寻找空位或再次移走现有的鸟蛋。这种机制被用来管理哈希表中的冲突。

Sort

Sorting(排序)

排序是指将一组数据按照一定的顺序排列的过程。排序算法是计算机科学中最基础的算法之一，它是对数据进行排列、整理的一种有效的方法。排序算法可以分为内部排序和外部排序。

Bogo sort(猴子排序)

Bogo sort(猴子排序)是一种非常简单的排序算法，它不断随机打乱数组，直到数组排序完成。它的平均时间复杂度为 O(n!), 最坏情况时间复杂度为 O(∞)。

这种排序过于随机, 所以很少有人使用它。

其代码也是十分的简单

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


void bogoSort(Vector<int>& v){
    while (!isSorted(v)){
        shuffle(v)
    }
}

bool isSorted(Vector<int>& v)
{
    for (int i = 0; i < v.size() - 1; i ++)
    {
        if(v[i] >v[i+1]){
            return false;
        }
    }
    return true;
}

Selection sort(选择排序)

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

选择排序的平均时间复杂度为 O(n^2), 最坏情况时间复杂度为 O(n^2)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void selectionSort(Vector<int>& v){
    for (int i = 0; i < v.size() - 1; i ++)
    {
        int minIndex = i;
        for (int j = i + 1; j < v.size(); j ++)
        {
            if (v[j] < v[minIndex])
            {
                minIndex = j;
            }
        swap(v[i], v[minIndex]);
        }
    }
}

Insertion sort(插入排序)

插入排序(Insertion sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的平均时间复杂度为 O(n^2), 最坏情况时间复杂度为 O(n^2)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


void insertionSort(Vector<int>& v){
    for (int i = 1; i < v.size(); i ++)
    {
        int j = i - 1;
        int temp = v[i];
        while (j >= 0 && v[j] > temp)
        {
            v[j + 1] = v[j];
            j --;
        }
        v[j + 1] = temp;
    }
}

Merge sort(归并排序)

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序的平均时间复杂度为 O(nlogn), 最坏情况时间复杂度为 O(nlogn)。

 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


void mergeSort(Vector<int>& v){
    if (v.size() <= 1)   // 基线条件
        return;
    int mid = v.size() / 2;
    Vector<int> left(v.begin(), v.begin() + mid);
    Vector<int> right(v.begin() + mid, v.end());
    mergeSort(left);
    mergeSort(right);
    merge(left, right, v);
}

void merge(Vector<int>& v, const Vector<int>& left, const Vector<int>& right) {
    int i = 0;  // 原数组 v 的索引
    int i1 = 0; // 左半部分 left 的索引
    int i2 = 0; // 右半部分 right 的索引

    // 遍历合并到原数组 v
    while (i < v.size()) {
        // 选择较小的元素：若右半部分已用完，或左半部分元素更小且未用完
        if (i2 >= right.size() || (i1 < left.size() && left[i1] < right[i2])) {
            v[i] = left[i1];
            i1++;
        } else {
            v[i] = right[i2];
            i2++;
        }
        i++;
    }
}

另外一点,归并排序的很大优势在于它可以多线程并行处理, 因此在某些情况下, 归并排序的效率要比其他排序算法更高。比如在大型计算机上

总结

好了,到目前为止 CS06B 数据结构与算法的排序部分就介绍完了,希望大家能有所收获.

关于后面两节课是介绍继承和多态,如果有兴趣可以去看笔记前面的 C++.oop 教学

最后,感谢大家的阅读,希望大家能有所收获.