数据结构实验

·

（本文仅用于记录在本学期实验课上涉及的数据结构与考点）

摆烂一个学期了，再不复习真要寄了（）

cpp提供的数据结构

（不用记那么多具体实现，cpp万岁）

一、哈希表

1、unordered_map

unordered_map 是 C++ 标准库提供的哈希表实现，用于存储键值对。其定义在 头文件中。

插入元素

1
2
umap[key] = value;  // 插入或更新
umap.insert({key, value});  // 插入元素，若键已存在则不插入

查找元素（不支持直接通过value来查询key，如果非要只能循环）

1
2
umap.find(key);  // 返回指向该元素的迭代器，如果没有找到返回 umap.end()
umap.count(key);  // 返回键是否存在，返回 1 或 0

删除元素

1
2
umap.erase(key);  // 删除指定键的元素
umap.erase(it);   // 删除迭代器指向的元素

访问元素

1
umap[key];        // 通过 key 访问对应的 value，如果 key 不存在会插入一个默认的 value

大小与清空

1
2
3
umap.size();      // 返回哈希表中元素的个数
umap.empty();     // 如果哈希表为空，返回 true
umap.clear();     // 清空哈希表

迭代器

1
2
3
for (auto it = umap.begin(); it != umap.end(); ++it) {
    cout << it->first << ": " << it->second << endl;
}

2、unordered_set

unordered_set 是一个哈希集合，它存储唯一的键，没有对应的值。常用于查找、去重等场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
unordered_set<int> uset;

// 插入元素
uset.insert(1);
uset.insert(2);
uset.insert(3);

// 查找元素
if (uset.find(2) != uset.end()) {
    cout << "Found 2 in the set" << endl;
}

// 删除元素
uset.erase(1);

// 遍历集合
for (auto it = uset.begin(); it != uset.end(); ++it) {
    cout << *it << endl;
}

// 清空集合
uset.clear();

二、队列

先进先出

定义

1
std::queue<int> q;  // 创建一个整数队列

入队

1
q.push(10);  // 将整数 10 添加到队列尾部

出队 

1
q.pop();  // 移除队列头部的元素

访问队列头部元素 

1
int frontElement = q.front();  // 获取队列头部的元素

访问队列尾部元素 

1
int backElement = q.back();  // 获取队列尾部的元素

检查队列是否为空

1
2
3
if (q.empty()) {
    std::cout << "队列为空" << std::endl;
}//empty()返回一个布尔值，指示队列是否为空。

获取队列大小

1
std::cout << "队列大小: " << q.size() << std::endl;

三、堆

cpp使用priority_queue表示堆

push(const T& value)：向优先队列中插入一个元素。插入时会保持堆的性质。

pop()：删除堆顶元素，即优先队列中当前优先级最高的元素。删除操作后会自动重建堆。

top()：返回堆顶元素，即优先队列中当前优先级最高的元素，但不删除它。

empty()：检查优先队列是否为空，返回布尔值。

size()：返回优先队列中的元素个数。

最大堆

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>
#include <queue>
#include <vector>

int main() {
    // 默认最大堆
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(20);
    pq.push(5);
    pq.push(30);

    // 输出优先队列的堆顶元素（最大元素）
    std::cout << "Top element: " << pq.top() << std::endl;  // 30

    // 删除堆顶元素并输出
    pq.pop();
    std::cout << "Top element after pop: " << pq.top() << std::endl;  // 20

    // 输出优先队列的大小
    std::cout << "Size of priority_queue: " << pq.size() << std::endl;  // 3

    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
#include <iostream>
#include <queue>
#include <vector>
#include <functional>  // for std::greater，std::greater<T> 表示“大于”，std::less<T>是默认，表示“小于”

int main() {
    // 使用最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    pq.push(10);
    pq.push(20);
    pq.push(5);
    pq.push(30);

    // 输出堆顶元素（最小元素）
    std::cout << "Top element: " << pq.top() << std::endl;  // 5

    // 删除堆顶元素并输出
    pq.pop();
    std::cout << "Top element after pop: " << pq.top() << std::endl;  // 10

    // 输出优先队列的大小
    std::cout << "Size of priority_queue: " << pq.size() << std::endl;  // 3

    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
#include <iostream>
#include <queue>
#include <vector>

struct Person {
    std::string name;
    int age;

    // 自定义比较函数，按年龄从大到小排序
    bool operator<(const Person& other) const {
        return age < other.age;  // 最大堆：年龄大的优先
    }
};

int main() {
    std::priority_queue<Person> pq;

    pq.push({"Alice", 30});
    pq.push({"Bob", 25});
    pq.push({"Charlie", 35});

    // 输出堆顶元素（年龄最大的人）
    std::cout << "Top person: " << pq.top().name << ", Age: " << pq.top().age << std::endl;  // Charlie

    return 0;
}

cpp未提供的数据结构

一、并查集

常用于处理一些不交集的合并和查询问题。它的核心操作是合并两个集合（union）和查询两个元素是否属于同一个集合（find）。并查集通常应用于图的连通性问题，比如判断图中是否存在环、最小生成树等问题。

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;

class DisjointSet {//是的这个东西需要自行实现
private:
    vector<int> parent;  // 记录每个节点的父节点
    vector<int> rank;    // 记录树的深度（秩）

public:
    // 构造函数，初始化并查集
    DisjointSet(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        // 初始时，每个元素的父节点指向自己
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    // 查找操作：找到元素的根节点，并进行路径压缩
    int find(int x) {
        if (parent[x] != x) {
            // 路径压缩，将x的父节点直接指向根节点
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 合并操作：将两个集合合并
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            // 按秩合并，深度小的树挂在深度大的树下面
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;  // 如果秩相同，合并后根的秩增加
            }
        }
    }

    // 检查x和y是否在同一个集合中
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int n = 10;  // 初始化10个元素的并查集
    DisjointSet ds(n);

    ds.unionSets(1, 2);  // 合并1和2
    ds.unionSets(2, 3);  // 合并2和3
    ds.unionSets(4, 5);  // 合并4和5
    ds.unionSets(6, 7);  // 合并6和7

    // 检查是否在同一集合
    cout << "1 and 3 connected: " << ds.connected(1, 3) << endl;  // 输出1，表示1和3在同一个集合
    cout << "1 and 4 connected: " << ds.connected(1, 4) << endl;  // 输出0，表示1和4不在同一个集合

    return 0;
}

二、Trie（字典树）

主要用于处理字符串集合，特别适合：

  • 插入一个单词：insert
  • 判断某单词是否存在：search
  • 判断是否存在某个前缀：startsWith
  • 统计某个单词出现次数 / 某个前缀出现次数
  • 删除单词：erase / remove

1、Trie 类的基本实现（insert / search / startsWith）

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    // 插入单词
    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (node->children[idx] == nullptr) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
            node->prefixCount++;  // 走到这里的前缀 +1
        }
        node->isEnd = true;
        node->wordCount++;  // 这个单词计数 +1
    }

    // 查询“完整单词是否存在”
    bool search(const std::string& word) const {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (node->children[idx] == nullptr) {
                return false;
            }
            node = node->children[idx];
        }
        return node->isEnd;  // 必须是单词结尾
    }

    // 查询“是否存在以 prefix 为前缀的单词”
    bool startsWith(const std::string& prefix) const {
        TrieNode* node = root;
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (node->children[idx] == nullptr) {
                return false;
            }
            node = node->children[idx];
        }
        return true;  // 能走完说明前缀存在
    }

    // 统计：某个单词出现了多少次
    int countWordsEqualTo(const std::string& word) const {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (node->children[idx] == nullptr) return 0;
            node = node->children[idx];
        }
        return node->wordCount;
    }

    // 统计：有多少单词以 prefix 为前缀
    int countWordsStartingWith(const std::string& prefix) const {
        TrieNode* node = root;
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (node->children[idx] == nullptr) return 0;
            node = node->children[idx];
        }
        return node->prefixCount;
    }

    // 删除一个单词（次数减一）
    void erase(const std::string& word) {
        if (!search(word)) return;  // 不存在就直接返回
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            node = node->children[idx];
            node->prefixCount--;  // 路径上的前缀次数-- 
        }
        node->wordCount--;
        if (node->wordCount == 0) {
            node->isEnd = false;
        }
        // 如果想做“物理删除节点”还需要递归回溯，可以再拓展
    }
};
int main() {
    Trie trie;

    // 插入单词
    trie.insert("apple");
    trie.insert("app");
    trie.insert("apply");
    trie.insert("apple");

    // search：查询完整单词
    bool f1 = trie.search("apple"); // true
    bool f2 = trie.search("app");   // true
    bool f3 = trie.search("appl");  // false

    // startsWith：查询前缀
    bool p1 = trie.startsWith("app"); // true（apple、app、apply 都有这个前缀）
    bool p2 = trie.startsWith("apx"); // false

    // 统计单词数量
    int c1 = trie.countWordsEqualTo("apple");  // 2（插入了两次）
    int c2 = trie.countWordsEqualTo("app");    // 1

    // 统计前缀数量
    int cp = trie.countWordsStartingWith("app"); // 3（apple*2 + app + apply，如果按插入次数则更多，可以按需求设计）

    // 删除单词
    trie.erase("apple");
    bool f4 = trie.search("apple"); // 仍可能是 true（因为还有一次 apple）
    int c3 = trie.countWordsEqualTo("apple"); // 1

    return 0;
}

你可以通过这些调用大致理解每个接口的用途。

2、删除单词的更完整写法（带回收节点）

如果想让 Trie 在删除后，把“完全没有用的节点”释放掉，可以写成递归版 erase：

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
class Trie2 {
private:
    TrieNode* root;

    // 返回值表示：当前节点是否可以被删除
    bool eraseHelper(TrieNode* node, const std::string& word, int pos) {
        if (pos == (int)word.size()) {
            node->wordCount--;
            if (node->wordCount == 0) node->isEnd = false;
        } else {
            int idx = word[pos] - 'a';
            TrieNode* child = node->children[idx];
            if (child == nullptr) return false; // 理论上不会发生，前面已判断存在

            bool canDeleteChild = eraseHelper(child, word, pos + 1);
            if (canDeleteChild) {
                delete child;
                node->children[idx] = nullptr;
            }
        }

        // 更新 prefixCount（如果你用了的话，这里需要减）
        if (pos < (int)word.size()) {
            node->prefixCount--;
        }

        // 判断当前 node 是否可以删：
        if (node == root) return false; // 根节点永远不删
        if (node->isEnd) return false;  // 有单词在此结束，不删
        for (int i = 0; i < 26; ++i) {
            if (node->children[i] != nullptr) return false; // 还有子节点，不删
        }
        return true; // 没有子节点、不是单词结尾 -> 可删
    }

public:
    Trie2() { root = new TrieNode(); }

    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
            node->prefixCount++;
        }
        node->isEnd = true;
        node->wordCount++;
    }

    bool search(const std::string& word) const {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!node->children[idx]) return false;
            node = node->children[idx];
        }
        return node->isEnd;
    }

    void erase(const std::string& word) {
        if (!search(word)) return;
        eraseHelper(root, word, 0);
    }
};

3、使用 unordered_map 的节点（字符集大时用）

如果要支持不限字符（如大小写字母、数字、甚至 Unicode），可以把 children[26] 换成 unordered_map<char, TrieNode*>：

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
#include <unordered_map>

struct TrieNodeMap {
    std::unordered_map<char, TrieNodeMap*> children;
    bool isEnd;
    int wordCount;
    int prefixCount;

    TrieNodeMap() : isEnd(false), wordCount(0), prefixCount(0) {}
};

class TrieMap {
private:
    TrieNodeMap* root;

public:
    TrieMap() { root = new TrieNodeMap(); }

    void insert(const std::string& word) {
        TrieNodeMap* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                node->children[ch] = new TrieNodeMap();
            }
            node = node->children[ch];
            node->prefixCount++;
        }
        node->isEnd = true;
        node->wordCount++;
    }

    bool search(const std::string& word) const {
        TrieNodeMap* node = root;
        for (char ch : word) {
            auto it = node->children.find(ch);
            if (it == node->children.end()) return false;
            node = it->second;
        }
        return node->isEnd;
    }

    bool startsWith(const std::string& prefix) const {
        TrieNodeMap* node = root;
        for (char ch : prefix) {
            auto it = node->children.find(ch);
            if (it == node->children.end()) return false;
            node = it->second;
        }
        return true;
    }
};

函数调用方式和前面的 Trie 一样，只是内部实现不同。

  • 优点：字符集无限制。
  • 缺点：常数更大，速度相对慢一些。

4、支持通配字符的trie

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
#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
    TrieNode* children[26];
    bool isEnd;
    TrieNode() : isEnd(false) {
        for (int i = 0; i < 26; ++i) children[i] = nullptr;
    }
};

class WordDictionary {
private:
    TrieNode* root;

    // 在 Trie 上从 node 开始匹配 word[pos...]
    bool dfs(const string& word, int pos, TrieNode* node) const {
        if (node == nullptr) return false;
        // 模式串已经匹配到末尾
        if (pos == (int)word.size()) {
            return node->isEnd;
        }

        char ch = word[pos];
        if (ch == '.') {  // 通配符：可以匹配任意一个字符
            for (int i = 0; i < 26; ++i) {
                if (node->children[i] != nullptr) {
                    if (dfs(word, pos + 1, node->children[i])) {
                        return true;
                    }
                }
            }
            return false;
        } else {          // 普通字符
            int idx = ch - 'a';
            return dfs(word, pos + 1, node->children[idx]);
        }
    }

public:
    WordDictionary() {
        root = new TrieNode();
    }

    // 插入单词
    void addWord(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (node->children[idx] == nullptr) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEnd = true;
    }

    // 支持 '.' 通配符的搜索
    bool search(const string& word) const {
        return dfs(word, 0, root);
    }
};

5、Trie 和普通数据结构的对比（什么时候用它）

  • 和 unordered_set<string> 比：
    • 相同点：都可以存一堆字符串、支持插入/查找。
    • Trie 优势：前缀查询、统计前缀数量、自动补全等操作更方便、复杂度更好（按字符串长度算）。
  • 和 map<string, int> 比：
    • map 基于平衡树，字符串比较时最坏要 O(L)。
    • Trie 的查询复杂度也是 O(L)，但在前缀问题上更自然。

时间复杂度（假设字符串长度为 L）：

  • insert：O(L)
  • search：O(L)
  • startsWith：O(L)
  • 不依赖于当前有多少个单词 n，主要看字符串长度。
数据结构实验
http://example.com/2025/11/29/数据结构实验/
作者
oxygen
发布于
2025年11月29日
许可协议