引言
C++作为一种高效、强大的编程语言，在软件开发中扮演着重要角色。数据结构是C++编程中不可或缺的一部分，它直接影响着程序的性能和可维护性。本文将详细介绍50个实战代码示例，帮助读者轻松掌握C++数据结构的编程精髓。
1. 数组
数组是C++中最基本的数据结构之一，用于存储相同类型的数据。
#include
using namespace std;
int main() {
int arr[5] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
return 0;
}
2. 向量
向量是C++标准库中的动态数组，可以自动扩展容量。
#include
#include
using namespace std;
int main() {
vector
for (int i = 0; i < vec.size(); i++) {
cout << vec[i] << " ";
}
return 0;
}
3. 链表
链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
#include
using namespace std;
struct Node {
int data;
Node* next;
};
void insert(Node*& head, int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = head;
head = newNode;
}
void display(Node* head) {
while (head != nullptr) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
Node* head = nullptr;
insert(head, 5);
insert(head, 4);
insert(head, 3);
insert(head, 2);
insert(head, 1);
display(head);
return 0;
}
4. 栈
栈是一种后进先出（LIFO）的数据结构。
#include
#include
using namespace std;
int main() {
stack
s.push(1);
s.push(2);
s.push(3);
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
return 0;
}
5. 队列
队列是一种先进先出（FIFO）的数据结构。
#include
#include
using namespace std;
int main() {
queue
q.push(1);
q.push(2);
q.push(3);
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
return 0;
}
6. 树
树是一种非线性数据结构，由节点组成，每个节点有零个或多个子节点。
#include
#include
using namespace std;
struct Node {
int data;
vector
};
void printTree(Node* root) {
if (root == nullptr) return;
cout << root->data << " ";
for (Node* child : root->children) {
printTree(child);
}
}
int main() {
Node* root = new Node();
root->data = 1;
Node* child1 = new Node();
child1->data = 2;
Node* child2 = new Node();
child2->data = 3;
root->children.push_back(child1);
root->children.push_back(child2);
printTree(root);
return 0;
}
7. 图
图是一种由节点（称为顶点）和边组成的数据结构。
#include
#include
using namespace std;
struct Graph {
int numVertices;
vector
};
void addEdge(Graph& g, int src, int dest) {
g.adjList[src].push_back(dest);
g.adjList[dest].push_back(src);
}
void printGraph(Graph& g) {
for (int i = 0; i < g.numVertices; i++) {
for (int j : g.adjList[i]) {
cout << i << " -> ” << j << endl;
}
}
}
int main() {
Graph g(4);
addEdge(g, 0, 1);
addEdge(g, 0, 2);
addEdge(g, 1, 3);
addEdge(g, 2, 3);
printGraph(g);
return 0;
}
8. 并查集
并查集是一种用于处理一些不交集的合并及查询问题的数据结构。
#include
#include
using namespace std;
struct UnionFind {
vector
vector
UnionFind(int size) : parent(size), rank(size, 0) {
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
};
int main() {
UnionFind uf(5);
uf.unite(0, 1);
uf.unite(2, 3);
uf.unite(1, 3);
cout << uf.find(0) << " " << uf.find(1) << " " << uf.find(2) << " " << uf.find(3) << " " << uf.find(4) << endl;
return 0;
}
9. 哈希表
哈希表是一种基于散列函数的数据结构，用于存储键值对。
#include
#include
using namespace std;
int main() {
unordered_map
map[1] = “apple”;
map[2] = “banana”;
map[3] = “cherry”;
for (auto& pair : map) {
cout << pair.first << " " << pair.second << endl;
}
return 0;
}
10. 字典树（Trie）
字典树是一种用于快速检索字符串数据集中的键的数据结构。
#include
#include
using namespace std;
struct TrieNode {
vector
bool isEndOfWord;
};
void insert(TrieNode* root, const string& key) {
TrieNode* curr = root;
for (char c : key) {
int index = c – ‘a’;
if (curr->children[index] == nullptr) {
curr->children[index] = new TrieNode();
}
curr = curr->children[index];
}
curr->isEndOfWord = true;
}
bool search(TrieNode* root, const string& key) {
TrieNode* curr = root;
for (char c : key) {
int index = c – ‘a’;
if (curr->children[index] == nullptr) {
return false;
}
curr = curr->children[index];
}
return curr->isEndOfWord;
}
int main() {
TrieNode* root = new TrieNode();
insert(root, “apple”);
insert(root, “banana”);
insert(root, “cherry”);
cout << search(root, "apple") << endl;
cout << search(root, "grape") << endl;
return 0;
}
总结
通过以上50个实战代码示例，读者可以深入了解C++数据结构的编程精髓。在学习和实践过程中，请结合实际需求，灵活运用各种数据结构，为您的C++编程之路保驾护航。