提高组知识点查漏补缺

xzh7 · 2025-08-23 17:03:25 · 个人记录

考纲

Linux 终端常用文件与目录操作命令

掌握这些命令是熟练使用 Linux 的基础。

目录操作

文件操作

文件内容处理与查找

权限与所有权

其他实用命令

使用技巧与注意事项

1. 路径补全 (Tab Completion)：按 Tab 键自动补全路径，按两次 Tab 列出所有选项
2. 上下箭头：快速调用历史命令
3. 通配符：
   • * 代表任意多个字符（如 *.txt）
   • ? 代表任意一个字符（如 file?.log）
   • [abc] 匹配括号内任意一个字符（如 file[123].txt）
4. 超级用户权限：需要时在命令前加 sudo
5. 谨慎使用 rm：Linux 删除文件不会进入回收站，直接永久删除

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>

using namespace std;

// 打印容器内容的通用函数（使用迭代器）
template<typename Container>
void printContainer(const string& name, const Container& c) {
    cout << name << ": ";
    for (auto it = c.begin(); it != c.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

// 针对map的打印特化版本
template<typename Key, typename Value>
void printContainer(const string& name, const map<Key, Value>& m) {
    cout << name << ": ";
    for (auto it = m.begin(); it != m.end(); ++it) {
        cout << "(" << it->first << ":" << it->second << ") ";
    }
    cout << endl;
}

// 针对unordered_map的打印特化版本
template<typename Key, typename Value>
void printContainer(const string& name, const unordered_map<Key, Value>& m) {
    cout << name << ": ";
    for (auto it = m.begin(); it != m.end(); ++it) {
        cout << "(" << it->first << ":" << it->second << ") ";
    }
    cout << endl;
}

int main() {
    cout << "=== STL 容器与迭代器示例 ===" << endl << endl;

    // 1. 序列容器示例
    cout << "1. 序列容器" << endl;

    // vector - 动态数组
    vector<int> vec = {5, 2, 8, 1, 9};
    vec.push_back(7); // 在末尾添加元素
    printContainer("vector", vec);
    cout << "vector 大小: " << vec.size() << ", 容量: " << vec.capacity() << endl;

    // list - 双向链表
    list<int> lst = {5, 2, 8, 1, 9};
    lst.push_front(0); // 在开头添加元素
    lst.sort(); // 链表有自己的sort方法
    printContainer("list", lst);

    // deque - 双端队列
    deque<int> dq = {5, 2, 8, 1, 9};
    dq.push_front(0);
    dq.push_back(7);
    printContainer("deque", dq);

    cout << endl;

    // 2. 关联容器示例
    cout << "2. 关联容器" << endl;

    // set - 有序唯一集合
    set<int> s = {5, 2, 8, 1, 9, 2, 5}; // 重复元素会被忽略
    s.insert(3);
    printContainer("set", s);

    // map - 键值对映射
    map<string, int> m = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 35}
    };
    m["David"] = 28; // 添加新元素
    printContainer("map", m);

    // multiset - 允许重复键的集合
    multiset<int> ms = {5, 2, 8, 1, 9, 2, 5};
    printContainer("multiset", ms);

    cout << endl;

    // 3. 无序关联容器示例 (C++11)
    cout << "3. 无序关联容器 (哈希表)" << endl;

    // unordered_set - 哈希集合
    unordered_set<int> us = {5, 2, 8, 1, 9, 2, 5};
    printContainer("unordered_set", us);

    // unordered_map - 哈希映射
    unordered_map<string, int> um = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 35}
    };
    printContainer("unordered_map", um);

    cout << endl;

    // 4. 容器适配器示例
    cout << "4. 容器适配器" << endl;

    // stack - 后进先出
    stack<int> st;
    for (int n : {1, 2, 3, 4, 5}) {
        st.push(n);
    }
    cout << "stack: ";
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;

    // queue - 先进先出
    queue<int> q;
    for (int n : {1, 2, 3, 4, 5}) {
        q.push(n);
    }
    cout << "queue: ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    // priority_queue - 优先级队列（默认最大堆）
    priority_queue<int> pq;
    for (int n : {5, 2, 8, 1, 9}) {
        pq.push(n);
    }
    cout << "priority_queue: ";
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;

    cout << endl;

    // 5. 迭代器示例
    cout << "5. 迭代器使用示例" << endl;

    vector<int> numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    // 使用迭代器遍历
    cout << "使用迭代器遍历: ";
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 使用反向迭代器
    cout << "使用反向迭代器: ";
    for (auto rit = numbers.rbegin(); rit != numbers.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;

    // 使用迭代器和算法
    auto min_it = min_element(numbers.begin(), numbers.end());
    auto max_it = max_element(numbers.begin(), numbers.end());
    cout << "最小值: " << *min_it << ", 最大值: " << *max_it << endl;

    // 使用迭代器插入元素
    auto insert_it = numbers.begin();
    advance(insert_it, 3); // 将迭代器前进3个位置
    numbers.insert(insert_it, 99);
    cout << "在位置3插入99后: ";
    printContainer("numbers", numbers);

    // 使用迭代器删除元素
    auto remove_it = numbers.begin();
    advance(remove_it, 5); // 将迭代器前进5个位置
    numbers.erase(remove_it);
    cout << "删除位置5的元素后: ";
    printContainer("numbers", numbers);

    // 使用迭代器范围排序
    sort(numbers.begin(), numbers.end());
    cout << "排序后: ";
    printContainer("numbers", numbers);

    // 使用const迭代器（只读访问）
    cout << "使用const迭代器: ";
    for (auto cit = numbers.cbegin(); cit != numbers.cend(); ++cit) {
        // *cit = 10; // 错误：不能修改const迭代器指向的值
        cout << *cit << " ";
    }
    cout << endl;

    return 0;
}

欧拉图（Eulerian Graph） 欧拉图是图论中的一个重要概念，得名于瑞士数学家莱昂哈德·欧拉。欧拉图与著名的"七桥问题"密切相关，欧拉在解决这个问题时开创了图论的研究。

欧拉图的定义 欧拉路径（Eulerian Path） 通过图中每条边恰好一次的路径称为欧拉路径。

欧拉回路（Eulerian Circuit） 通过图中每条边恰好一次且起点和终点相同的路径称为欧拉回路。

欧拉图（Eulerian Graph） 包含欧拉回路的图称为欧拉图。

半欧拉图（Semi-Eulerian Graph） 包含欧拉路径但不包含欧拉回路的图称为半欧拉图。

欧拉图的判定条件 无向图 欧拉回路存在条件：当且仅当图是连通的，且每个顶点的度数都是偶数。

欧拉路径存在条件：当且仅当图是连通的，且恰好有两个顶点的度数是奇数（这两个顶点分别是路径的起点和终点）。

有向图 欧拉回路存在条件：当且仅当图是连通的，且每个顶点的入度等于出度。

欧拉路径存在条件：当且仅当图是连通的，且恰好有一个顶点的出度比入度大1（起点），恰好有一个顶点的入度比出度大1（终点），其余顶点的入度等于出度。

原码、反码、补码

原码：最高位（最左边一位）表示符号，0为正，1为负；其余位表示数值的绝对值。

反码：正数的反码与其原码相同，负数的反码为符号位为1，其余位与其原码按位取反。

补码：正数的补码与其原码相同，负数的补码为其反码加一。