《使用C++解决数据结构问题的实例》
数据结构是计算机科学的基石，它定义了数据的组织、存储和管理方式。C++作为一门高效的面向对象编程语言，因其对底层硬件的直接控制能力和丰富的标准库支持，成为实现数据结构的理想选择。本文将通过具体实例，展示如何使用C++解决常见的链表、树、图等数据结构问题，帮助读者深入理解数据结构的原理与应用。
一、链表操作：单链表的反转
链表是一种动态数据结构，由节点通过指针连接而成。单链表的反转是链表操作中的经典问题，要求在不创建新链表的情况下，将原链表的节点顺序完全颠倒。
问题分析：
单链表反转的核心在于调整每个节点的`next`指针，使其指向前一个节点。这需要维护三个指针：`prev`（前驱节点）、`current`（当前节点）和`next`（后继节点）。通过迭代遍历链表，逐步修改指针方向。
代码实现：
#include
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
while (current != nullptr) {
ListNode* next = current->next; // 保存后继节点
current->next = prev; // 反转指针
prev = current; // 更新前驱节点
current = next; // 移动到下一个节点
}
return prev; // 返回新头节点
}
// 测试代码
int main() {
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
ListNode* reversed = reverseList(head);
while (reversed != nullptr) {
cout val next;
}
return 0;
} 关键点：
1. 使用临时指针`next`保存后继节点，避免丢失链表。 2. 每次迭代后更新`prev`和`current`的位置。 3. 时间复杂度为O(n)，空间复杂度为O(1)。
二、树结构：二叉搜索树的插入与查找
二叉搜索树（BST）是一种特殊的二叉树，其中每个节点的值大于其左子树所有节点的值，小于其右子树所有节点的值。BST的插入和查找操作效率较高，平均时间复杂度为O(log n)。
问题分析：
插入操作需要从根节点开始，根据目标值与当前节点值的比较结果，决定向左子树或右子树递归插入。查找操作类似，通过比较值的大小逐步缩小搜索范围。
代码实现：
#include
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
return new TreeNode(val);
}
if (val val) {
root->left = insertIntoBST(root->left, val);
} else {
root->right = insertIntoBST(root->right, val);
}
return root;
}
bool searchBST(TreeNode* root, int val) {
if (root == nullptr) return false;
if (root->val == val) return true;
return val val ? searchBST(root->left, val) : searchBST(root->right, val);
}
// 测试代码
int main() {
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(3);
root->right = new TreeNode(7);
insertIntoBST(root, 4);
cout 关键点：
1. 递归实现插入和查找，简化代码逻辑。 2. BST的性质保证了查找和插入的高效性。 3. 平衡BST（如AVL树、红黑树）可进一步优化最坏情况下的性能。
三、图结构：广度优先搜索（BFS）
图是一种由顶点和边组成的非线性数据结构，广泛应用于社交网络、路径规划等领域。广度优先搜索（BFS）是一种按层级遍历图的算法，常用于寻找最短路径或检测连通性。
问题分析：
BFS使用队列实现，从起始顶点开始，依次访问其所有邻接顶点，再访问邻接顶点的邻接顶点，直到遍历完所有可达顶点。需要记录已访问的顶点以避免重复处理。
代码实现：
#include
#include
#include
using namespace std;
void bfs(vector>& graph, int start) {
vector visited(graph.size(), false);
queue q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int current = q.front();
q.pop();
cout > graph = {
{1, 2}, // 顶点0的邻接顶点
{0, 3, 4}, // 顶点1的邻接顶点
{0, 5}, // 顶点2的邻接顶点
{1}, // 顶点3的邻接顶点
{1}, // 顶点4的邻接顶点
{2} // 顶点5的邻接顶点
};
cout 关键点：
1. 使用队列实现BFS的层级遍历。 2. `visited`数组避免重复访问和无限循环。 3. 时间复杂度为O(V+E)，其中V为顶点数，E为边数。
四、动态数组：实现可变长度数组
动态数组是一种能够自动调整容量的数据结构，C++中的`std::vector`是其典型实现。手动实现动态数组有助于理解其底层机制。
问题分析：
动态数组的核心操作包括插入、删除和扩容。当数组容量不足时，需分配更大的内存空间，并将原有数据复制到新空间。
代码实现：
#include
using namespace std;
class DynamicArray {
private:
int* data;
int capacity;
int size;
void resize(int newCapacity) {
int* newData = new int[newCapacity];
for (int i = 0; i 0) {
size--;
}
}
int at(int index) {
if (index = size) {
throw out_of_range("Index out of range");
}
return data[index];
}
int getSize() { return size; }
};
// 测试代码
int main() {
DynamicArray arr;
arr.push_back(1);
arr.push_back(2);
arr.push_back(3);
for (int i = 0; i 关键点：
1. 扩容时容量通常翻倍，以摊还常数时间复杂度。 2. 使用`new`和`delete`管理动态内存。 3. 插入和删除操作的时间复杂度为O(1)（均摊），随机访问为O(1)。
五、哈希表：实现简单的键值对存储
哈希表通过哈希函数将键映射到数组索引，实现高效的插入、删除和查找操作。C++中的`std::unordered_map`是其标准实现。
问题分析：
哈希表的核心在于处理哈希冲突。常见方法包括链地址法（每个桶存储链表）和开放寻址法（线性探测、二次探测等）。
代码实现：
#include
#include
#include
using namespace std;
class HashTable {
private:
static const int TABLE_SIZE = 10;
vector>> table;
int hashFunction(int key) {
return key % TABLE_SIZE;
}
public:
HashTable() : table(TABLE_SIZE) {}
void insert(int key, string value) {
int index = hashFunction(key);
for (auto& pair : table[index]) {
if (pair.first == key) {
pair.second = value; // 更新已存在的键
return;
}
}
table[index].emplace_back(key, value); // 插入新键值对
}
string search(int key) {
int index = hashFunction(key);
for (auto& pair : table[index]) {
if (pair.first == key) {
return pair.second;
}
}
return "Key not found";
}
void remove(int key) {
int index = hashFunction(key);
for (auto it = table[index].begin(); it != table[index].end(); it++) {
if (it->first == key) {
table[index].erase(it);
return;
}
}
}
};
// 测试代码
int main() {
HashTable ht;
ht.insert(1, "Apple");
ht.insert(2, "Banana");
ht.insert(11, "Cherry"); // 哈希冲突示例
cout
关键点：
1. 链地址法解决哈希冲突，每个桶存储链表。 2. 哈希函数应尽量均匀分布键值。 3. 平均情况下，插入、删除和查找的时间复杂度为O(1)。
关键词
C++、数据结构、链表反转、二叉搜索树、广度优先搜索、动态数组、哈希表、链地址法、时间复杂度、递归
简介
本文通过五个实例展示了如何使用C++解决常见的链表、树、图等数据结构问题，包括单链表反转、二叉搜索树的插入与查找、图的广度优先搜索、动态数组的实现以及哈希表的键值对存储。代码涵盖递归、指针操作、队列使用等核心技巧，并分析了各算法的时间复杂度与空间复杂度，适合C++初学者和进阶学习者参考。
