CPP-学习笔记(一)

C++ 基本数据结构

C++ 基本数据结构

动态数组 vector

初始化

#include <vector>

int n = 7, m = 8;

// 初始化一个 int 型的空数组 nums
vector<int> nums;

// 初始化一个大小为 n 的数组 nums，数组中的值默认都为 0
vector<int> nums(n);

// 初始化一个元素为 1, 3, 5 的数组 nums
vector<int> nums{1, 3, 5};

// 初始化一个大小为 n 的数组 nums，其值全都为 2
vector<int> nums(n, 2);

// 初始化一个二维 int 数组 dp
vector<vector<int>> dp;

// 初始化一个大小为 m * n 的布尔数组 dp，
// 其中的值都初始化为 true
vector<vector<bool>> dp(m, vector<bool>(n, true));

常用操作

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 10;
    // 数组大小为 10，元素值都为 0
    vector<int> nums(n);
    // 输出 0 (false)
    cout << nums.empty() << endl;
    // 输出：10
    cout << nums.size() << endl;

    // 在数组尾部插入一个元素 20
    nums.push_back(20);
    // 输出：11
    cout << nums.size() << endl;

    // 得到数组最后一个元素的引用
    // 输出：20
    cout << nums.back() << endl;

    // 删除数组的最后一个元素（无返回值）
    nums.pop_back();
    // 输出：10
    cout << nums.size() << endl;

    // 可以通过方括号直接取值或修改
    nums[0] = 11;
    // 输出：11
    cout << nums[0] << endl;

    // 在索引 3 处插入一个元素 99
    nums.insert(nums.begin() + 3, 99);

    // 删除索引 2 处的元素
    nums.erase(nums.begin() + 2);

    // 交换 nums[0] 和 nums[1]
    swap(nums[0], nums[1]);

    // 遍历数组
    // 0 11 99 0 0 0 0 0 0 0
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
}

双链表 list

初始化

#include <list>

int n = 7;

// 初始化一个空的双向链表 lst
std::list<int> lst;

// 初始化一个大小为 n 的链表 lst，链表中的值默认都为 0
std::list<int> lst(n);

// 初始化一个包含元素 1, 3, 5 的链表 lst
std::list<int> lst{1, 3, 5};

// 初始化一个大小为 n 的链表 lst，其中值都为 2
std::list<int> lst(n, 2);

常用操作

#include <iostream>
#include <list>
using namespace std;

int main() {
    // 初始化链表
    list<int> lst{1, 2, 3, 4, 5};

    // 检查链表是否为空，输出：false
    cout << lst.empty() << endl;

    // 获取链表的大小，输出：5
    cout << lst.size() << endl;

    // 在链表头部插入元素 0
    lst.push_front(0);
    // 在链表尾部插入元素 6
    lst.push_back(6);

    // 获取链表头部和尾部元素，输出：0 6
    cout << lst.front() << " " << lst.back() << endl;

    // 删除链表头部元素
    lst.pop_front();
    // 删除链表尾部元素
    lst.pop_back();

    // 在链表中插入元素
    auto it = lst.begin();
    // 移动到第三个位置
    advance(it, 2);
    // 在第三个位置插入 99
    lst.insert(it, 99);

    // 删除链表中某个元素
    it = lst.begin();
    // 移动到第二个位置
    advance(it, 1);
    // 删除第二个位置的元素
    lst.erase(it);

    // 遍历链表
    // 输出：1 99 3 4 5
    for (int val : lst) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

队列 queue

初始化

#include <iostream>
#include <queue>
using namespace std;

int main() {
    // 初始化一个空的整型队列 q
    queue<int> q;

    // 在队尾添加元素
    q.push(10);
    q.push(20);
    q.push(30);

    // 检查队列是否为空，输出：false
    cout << q.empty() << endl;

    // 获取队列的大小，输出：3
    cout << q.size() << endl;

    // 获取队列的队头和队尾元素，输出：10 和 30
    cout << q.front() << " " << q.back() << endl;

    // 删除队头元素
    q.pop();

    // 输出新的队头元素：20
    cout << q.front() << endl;

    return 0;
}

栈 stack

初始化

#include <iostream>
#include <stack>
using namespace std;

int main() {

    // 初始化一个空的整型栈 s
    stack<int> s;

    // 向栈顶添加元素
    s.push(10);
    s.push(20);
    s.push(30);

    // 检查栈是否为空，输出：false
    cout << s.empty() << endl;

    // 获取栈的大小，输出：3
    cout << s.size() << endl;

    // 获取栈顶元素，输出：30
    cout << s.top() << endl;

    // 删除栈顶元素
    s.pop();

    // 输出新的栈顶元素：20
    cout << s.top() << endl;

    return 0;
}

哈希表 unordered_map

初始化

#include <unordered_map>
using namespace std;

// 初始化一个空的哈希表 map
unordered_map<int, string> hashmap;

// 初始化一个包含一些键值对的哈希表 map
unordered_map<int, string> hashmap{{1, "one"}, {2, "two"}, {3, "three"}};

常用操作

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    // 初始化哈希表
    unordered_map<int, string> hashmap{{1, "one"}, {2, "two"}, {3, "three"}};

    // 检查哈希表是否为空，输出：0 (false)
    cout << hashmap.empty() << endl;

    // 获取哈希表的大小，输出：3
    cout << hashmap.size() << endl;

    // 查找指定键是否存在
    // 注意 contains 方法是 C++20 新增的
    // 输出：Key 2 -> two
    if (hashmap.contains(2)) {
        cout << "Key 2 -> " << hashmap[2] << endl;
    } else {
        cout << "Key 2 not found." << endl;
    }

    // 获取指定键对应的值，若不存在会返回默认构造的值
    // 输出空字符串
    cout << hashmap[4] << endl;

    // 插入一个新的键值对
    hashmap[4] = "four";

    // 获取新插入的值，输出：four
    cout << hashmap[4] << endl;

    // 删除键值对
    hashmap.erase(3);

    // 检查删除后键 3 是否存在
    // 输出：Key 3 not found.
    if (hashmap.contains(3)) {
        cout << "Key 3 -> " << hashmap[3] << endl;
    } else {
        cout << "Key 3 not found." << endl;
    }

    // 遍历哈希表
    // 输出（顺序可能不同）：
    // 4 -> four
    // 2 -> two
    // 1 -> one
    for (const auto &pair: hashmap) {
        cout << pair.first << " -> " << pair.second << endl;
    }

    // 特别注意，访问不存在的键会自动创建这个键
    unordered_map<int, string> hashmap2;

    // 键值对的数量是 0
    cout << hashmap2.size() << endl; // 0

    // 访问不存在的键，会自动创建这个键，对应的值是默认构造的值
    cout << hashmap2[1] << endl; // empty string
    cout << hashmap2[2] << endl; // empty string

    // 现在键值对的数量是 2
    cout << hashmap2.size() << endl; // 2

    return 0;
}

哈希集合 unordered_set

初始化

#include <unordered_set>
using namespace std;

// 初始化一个空的哈希集合 set
unordered_set<int> uset;

// 初始化一个包含一些元素的哈希集合 set
unordered_set<int> uset{1, 2, 3, 4};

常用操作

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    // 初始化哈希集合
    unordered_set<int> hashset{1, 2, 3, 4};

    // 检查哈希集合是否为空，输出：0 (false)
    cout << hashset.empty() << endl;

    // 获取哈希集合的大小，输出：4
    cout << hashset.size() << endl;

    // 查找指定元素是否存在
    // 输出：Element 3 found.
    if (hashset.contains(3)) {
        cout << "Element 3 found." << endl;
    } else {
        cout << "Element 3 not found." << endl;
    }

    // 插入一个新的元素
    hashset.insert(5);

    // 删除一个元素
    hashset.erase(2);
    // 输出：Element 2 not found.
    if (hashset.contains(2)) {
        cout << "Element 2 found." << endl;
    } else {
        cout << "Element 2 not found." << endl;
    }

    // 遍历哈希集合
    // 输出（顺序可能不同）：
    // 1
    // 3
    // 4
    // 5
    for (const auto &element : hashset) {
        cout << element << endl;
    }

    return 0;
}

---

树

二叉树结构

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

二叉树 DFS 深度优先搜索

前序遍历（根->左->右）

void DFS_Preorder(TreeNode* root) {
    if (!root) return;
    
    cout << root->val << " "; // 处理当前节点
    DFS_Preorder(root->left);  // 遍历左子树
    DFS_Preorder(root->right); // 遍历右子树
}

中序遍历（左->根->右）

void DFS_Inorder(TreeNode* root) {
    if (!root) return;
    
    DFS_Inorder(root->left);  // 遍历左子树
    cout << root->val << " "; // 处理当前节点
    DFS_Inorder(root->right); // 遍历右子树
}

后序遍历（左->右->根）

void DFS_Postorder(TreeNode* root) {
    if (!root) return;
    
    DFS_Postorder(root->left);  // 遍历左子树
    DFS_Postorder(root->right); // 遍历右子树
    cout << root->val << " "; // 处理当前节点
}

二叉树 BFS 广度优先搜索（层序遍历）

void levelOrder(TreeNode* root) {
    if (!root) return;  // 如果根节点为空，则没有树，直接返回
    
    queue<TreeNode*> q;  // 创建一个队列，用于存储树的节点
    q.push(root);  // 将根节点入队
    
    // 队列不为空时，继续遍历
    while (!q.empty()) {
        TreeNode* node = q.front();  // 获取队列头部的节点
        q.pop();  // 弹出队列头部的节点
        
        cout << node->val << " ";  // 访问当前节点，输出其值
        
        // 如果当前节点有左子节点，将左子节点入队
        if (node->left) {
            q.push(node->left);
        }
        // 如果当前节点有右子节点，将右子节点入队
        if (node->right) {
            q.push(node->right);
        }
    }
    cout << endl;  // 输出换行，结束一层的遍历
}

---