C++ 数据结构实现
2025-10-07 12:33:29
发布于：安徽
C++ 数据结构实现
这是一个包含常见数据结构的C++实现集合，每个数据结构都有完整的功能实现和测试代码。
包含的数据结构
链表 (Linked List)
单链表实现
支持插入、删除、查找等操作
栈 (Stack)
数组实现的栈
链表实现的栈
支持push、pop、top等操作
队列 (Queue)
循环队列（数组实现）
链式队列
支持enqueue、dequeue等操作
二叉树 (Binary Tree)
基本二叉树实现
支持前序、中序、后序、层序遍历
支持插入、查找等操作
哈希表 (Hash Table)
链地址法处理冲突
自动扩容功能
支持插入、删除、查找等操作
文件结构
data_structures/
├── linked_list.cpp # 链表实现
├── stack.cpp # 栈实现
├── queue.cpp # 队列实现
├── binary_tree.cpp # 二叉树实现
├── hash_table.cpp # 哈希表实现
├── main.cpp # 演示程序
├── Makefile # 编译脚本
└── README.md # 说明文档
编译和运行
编译所有程序
make all
运行单个数据结构的测试
./linked_list
./stack
./queue
./binary_tree
./hash_table
运行交互式演示程序
./main
演示程序提供了一个菜单界面，可以以交互式交互式5种数据结构的功能。
清理编译文件
make clean
数据结构详细说明
- 链表 (LinkedList)
实现了一个模板化的单链表，支持以下操作：
push_back(data) - 在链表末尾添加元素
push_front(data) - 在链表开头添加元素
insert(index, data) - 在指定位置插入元素
remove(index) - 删除指定位置的元素
get(index) - 获取指定位置的元素
set(index, data) - 修改指定位置的元素
find(data) - 查找元素并返回索引
is_empty() - 检查链表是否为空
get_size() - 获取链表大小
clear() - 清空链表
print() - 打印链表
2. 栈 (Stack)
提供了两种两种实现：
数组栈 (Stack)：使用动态数组实现，支持自动扩容
链表栈 (LinkedStack)：使用链表实现
主要操作：
push(data) - 入栈
pop() - 出栈
top() - 获取栈顶元素
is_empty() - 检查栈是否为空
size() - 获取栈的大小
clear() - 清空栈
3. 队列 (Queue)
提供了两种实现：
循环队列 (CircularQueue)：使用数组实现，支持自动扩容
链式队列 (LinkedQueue)：使用链表实现
主要操作：
enqueue(data) - 入队
dequeue() - 出队
front_element() - 获取队首元素
rear_element() - 获取队尾元素
is_empty() - 检查队列是否为空
size() - 获取队列的大小
clear() - 清空队列
4. 二叉树 (BinaryTree)
实现了一个基本的二叉树，支持以下操作：
set_root(data) - 设置根节点
insert_left(parent_data, data) - 插入左左子节点
insert_right(parent_data, data) - 插入右子节点
preorder() - 前序遍历
inorder() - 中序遍历
postorder() - 后序遍历
level_order() - 层序遍历
search(data) - 查找节点
height() - 获取树的高度
size() - 获取树的节点数
print_tree() - 打印树的结构
5. 哈希表 (HashTable)
使用链地址法处理冲突的哈希表实现，支持以下操作：
insert(key, value) - 插入键值对
get(key) - 获取值
remove(key) - 删除键值对
contains(key) - 检查键是否存在
get_size() - 获取哈希表的大小
get_capacity() - 获取哈希表的容量
is_empty() - 检查哈希表是否为空
clear() - 清空哈希表
get_keys() - 获取所有键
get_values() - 获取所有值
get_pairs() - 获取所有键值对
示例代码
每个数据结构文件都包含一个main函数用于测试。例如，链表的测试代码：
LinkedList<int> list;
list.push_back(10);
list.push_back(20);
list.push_front(5);
list.print(); // 输出: 5 10 20
注意事项
所有数据结构都使用模板实现，可以以支持不同的数据类型
代码使用C11标准，编译时请确保启用C11或更高版本
每个数据结构都包含异常处理，以处理无效操作
自动扩容功能会在负载因子达到超过阈值时触发
这里空空如也
有帮助，赞一个