c++学习笔记

note
c++
Author

Shan Jin

Published

October 10, 2023

在力扣上学习数据结构，顺便学习下c++。原文见力扣图解算法数据结构。这里抄下了部分原文和图片并且加注了笔记，方便自己查看学习。

数据结构简介

常见数据结构

数组

数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变。例如：

// 初始化一个长度为 5 的数组 array
int array[5];
// 元素赋值
array[0] = 2;
array[1] = 3;
array[2] = 1;
array[3] = 0;
array[4] = 2;

或者直接在初始化时赋值：

int array[] = {2,3,1,0,2};

可变数组可以访问元素、添加元素、删除元素。

// 初始化可变数组
vector<int> array;

// 向尾部添加元素
array.push_back(2);
array.push_back(3);
array.push_back(1);
array.push_back(0);
array.push_back(2);

用如下方法删除可变数组的元素：

// Remove the last element
array.pop_back();

// Remove the second element (index 1)
array.erase(array.begin() + 1);

// Remove elements from index 1 to 2 (inclusive)
array.erase(array.begin() + 1, array.begin() + 3);
array.insert(array.begin(),1)

链表

链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量：「值 val」，「后继节点引用next」 。

struct ListNode {
  int val;  //节点值
  ListNode *next; //后继节点引用
  ListNode(int x) : val(x), next(NULL) {}
}

下面是一个建立链表的例子：

ListNode *n1 = new ListNode(4); //head
ListNode *n2 = new ListNode(5);
ListNode *n3 = new Listnode(1);

n1->next = n2;
n2->next = n3;

当我们定义了一个指向对象的指针时，可以用 -> 来访问对象中的成员。上面链表的例子中 n1->next 等价于 (*n1).next. 再比如：

struct MyStruct {
    int value;
    void printValue() {
        std::cout << "Value: " << value << std::endl;
    }
};

MyStruct obj;
MyStruct* ptr = &obj;

// Accessing a member variable using ->
int x = ptr->value;

// Calling a member function using ->
ptr->printValue();

struct ListNode {...} 构建了一个结构，int val 和 ListNode *next 是该结构中的两个成员，分别表示一个整数变量和指向另一个 ListNode 结构的指针。ListNode(int x) : val(x), next(NULL) {} 是构建 ListNode 结构的 constructor，用来初始化结构中的成员取值。在定义结构时 constructor 并非必需的，例如上面一条 note 的中的结构 MyStruct 就没有定义 constructor. 用它来创建对象时，对象中成员会被初始化为默认值。例如：

MyStruct obj;
obj.printValue(); // This will print "Value: 0"

可以在初始化之后给成员赋值：

MyStruct obj;
obj.value = 42;
obj.printValue(); // This will print "Value: 42"

此外，constructor 末尾的 {} 指的是 constructor 的主体，可以在里面添加额外的操作，比如：

#include <iostream>
#include <string>

class Person {
public:
    std::string name;
    int age;

    // Constructor with a non-empty body
    Person(const std::string& n, int a) : name(n), age(a) {
        std::cout << "A new person object is created with name: " << name << " and age: " << age << std::endl;
    }
};

int main() {
    // Create a Person object with the constructor
    Person person1("Alice", 30);

    // Create another Person object
    Person person2("Bob", 25);

    return 0;
}

它会输出：

A new person object is created with name: Alice and age: 30
A new person object is created with name: Bob and age: 25

这段代码中，std:: 指的是标准库中的数据类型或函数。语句 Person(const std::string& n, int a) 在 string 的末尾加 & 是指传递到类 Person 中的变量 n 为输入的 string 本身，而非其复制，用以节省内存，同时也意味着如果 constructor 中对 n 的值做出的改变，会影响原来输入进来的那个 string。

class 和 struct 都可以来定义数据类型。不同的是，class 中的成员默认是 private 的，不可从外部访问，而 struct 则默认为 public. 下面是一个例子：

class MyClass {
private:
    int data;

public:
    MyClass(int value) : data(value) {}

    int getData() {
        return data;
    }
};

struct MyStruct {
    int data;
};

在 MyClass 中，data 是 private 的，只能通过 public 的函数 getData 访问。而在 MyStruct 中，data 可以被直接访问。

栈

具有 Last-In-First-Out (LIFO) 特点的数据结构，只能访问最顶端的数据，没法直接访问中间或者底端的数据。例如：

stack<int> stk;

stk.push(1); // 元素 1 入栈
stk.push(2); // 元素 2 入栈
stk.pop();   // 出栈 -> 元素 2
stk.pop();   // 出栈 -> 元素 1

队列

具有 First-In-First-Out (FIFO) 特点的数据结构。例如：

queue<int> que;

que.push(1); // 元素 1 入队
que.push(2); // 元素 2 入队
que.pop();   // 出队 -> 元素 1
que.pop();   // 出队 -> 元素 2

树

树是一种非线性数据结构，根据子节点数量可分为 「二叉树」 和 「多叉树」，最顶层的节点称为「根节点 root」。下面是一个二叉树的例子：

struct TreeNode {
    int val;         // 节点值
    TreeNode *left;  // 左子节点
    TreeNode *right; // 右子节点
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

如下图所示，建立此二叉树需要实例化每个节点，并构建各节点的引用指向。

// 初始化节点
TreeNode *n1 = new TreeNode(3); // 根节点 root
TreeNode *n2 = new TreeNode(4);
TreeNode *n3 = new TreeNode(5);
TreeNode *n4 = new TreeNode(1);
TreeNode *n5 = new TreeNode(2);

// 构建引用指向
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;

图

图是一种非线性数据结构，由「节点（顶点）vertex」和「边 edge」组成，每条边连接一对顶点。根据边的方向有无，图可分为「有向图」和「无向图」。本文 以无向图为例 开展介绍。

如下图所示，此无向图的 顶点 和 边 集合分别为：

  • 顶点集合： vertices = {1, 2, 3, 4, 5}

  • 边集合： edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}

表示图的方法通常有两种：

  1. 邻接矩阵：使用数组 vettices 储存顶点，邻接矩阵 edges 储存边。 edges[i][j] 代表节点 i+1 和 j+1 之间是否有边。
int vertices[5] = {1, 2, 3, 4, 5};
int edges[5][5] = {{0, 1, 1, 1, 1},
                   {1, 0, 0, 1, 0},
                   {1, 0, 0, 0, 1},
                   {1, 1, 0, 0, 1},
                   {1, 0, 1, 1, 0}};
  1. 邻接表：使用数组 vettices 储存顶点，邻接矩阵 edges 储存边。edges[i] 存储顶点 vertices[i] 对应的边集和
int vertices[5] = {1, 2, 3, 4, 5};
vector<vector<int>> edges;

vector<int> edge_1 = {1, 2, 3, 4};
vector<int> edge_2 = {0, 3};
vector<int> edge_3 = {0, 4};
vector<int> edge_4 = {0, 1, 4};
vector<int> edge_5 = {0, 2, 3};
edges.push_back(edge_1);
edges.push_back(edge_2);
edges.push_back(edge_3);
edges.push_back(edge_4);
edges.push_back(edge_5);

邻接矩阵 VS 邻接表 ：邻接表适合存储稀疏图（顶点较多、边较少）；邻接矩阵适合存储稠密图（顶点较少、边较多）。

散列表

散列表是一种非线性数据结构，通过利用 Hash 函数将指定的「键 key」映射至对应的「值 value」，以实现高效的元素查找。

设想一个简单场景：小力、小特、小扣的学号分别为 10001, 10002, 10003. 现需求从「姓名」查找「学号」。

则可通过建立姓名为 key ，学号为 value 的散列表实现此需求，代码如下：

// 初始化散列表
unordered_map<string, int> dic;

// 添加 key -> value 键值对
dic["小力"] = 10001;
dic["小特"] = 10002;
dic["小扣"] = 10003;

// 从姓名查找学号
dic.find("小力")->second; // -> 10001
dic.find("小特")->second; // -> 10002
dic.find("小扣")->second; // -> 10003

Hash 函数设计 Demo ： > 假设需求：从「学号」查找「姓名」。 将三人的姓名存储至以下数组中，则各姓名在数组中的索引分别为 0, 1, 2 。

string names[] = { "小力", "小特", "小扣" };

此时，我们构造一个简单的 Hash 函数（ % 为取余符号 ），公式和封装函数如下所示：

\[ hash(key)=(key-1)%10000 \]

int hash(int id) {
    int index = (id - 1) % 10000;
    return index;
}

则我们构建了以学号为 key 、姓名对应的数组索引为 value 的散列表。利用此 Hash 函数，则可在 O(1) 时间复杂度下通过学号查找到对应姓名，即：

names[hash(10001)] // 小力
names[hash(10002)] // 小特
names[hash(10003)] // 小扣

堆

堆是一种基于「完全二叉树」的数据结构，可使用数组实现。以堆为原理的排序算法称为「堆排序」，基于堆实现的数据结构为「优先队列」。堆分为「大顶堆」和「小顶堆」，大（小）顶堆：任意节点的值不大于（小于）其父节点的值

完全二叉树定义： 设二叉树深度为 k ，若二叉树除第 k 层外的其它各层（第 1 至 k−1 层）的节点达到最大个数，且处于第 k 层的节点都连续集中在最左边，则称此二叉树为完全二叉树。

如下图所示，为包含 1, 4, 2, 6, 8 元素的小顶堆。将堆（完全二叉树）中的结点按层编号，即可映射到右边的数组存储形式。

通过使用「优先队列」的「压入 push()」和「弹出 pop()」操作，即可完成堆排序，实现代码如下：

// 初始化小顶堆
priority_queue<int, vector<int>, greater<int>> heap;

// 元素入堆
heap.push(1);
heap.push(4);
heap.push(2);
heap.push(6);
heap.push(8);

// 元素出堆（从小到大）
heap.pop(); // -> 1
heap.pop(); // -> 2
heap.pop(); // -> 4
heap.pop(); // -> 6
heap.pop(); // -> 8

Explore more: