课程设计 基于哈希表的二叉树优化
一,课程摘要
在本二叉树数据结构设计中,二叉树的存储结构设计采用链式存储结构,以及利用了哈
希表的低复杂度优化了二叉树的添加,查找,删除,修改的性能。同时设计了三种哈希函数
应对不同的数据类型,如,char 类型,int 类型以及 string 类型,三种哈希函数都能使得数
据均匀分布在内存中。另外,采用了链地址的思想解决哈希冲突。最后,为了使得程序具有
更强的可扩展性,考虑了哈希表的扩容,以及为了方便程序调试设计了一些工具函数,能够
直观体现算法的正确性和可行性,以及基于一种异常机制对程序中输出错误信息进行输出,
而非采用状态标志返回的形式,使得程序调试更简单高效。
二,设计任务
二叉树在程序设计中使用非常多,有许多其它抽象的数据结构也依赖与其实现,如,
Java 中性能强大的 HashMap 的设计思想就使用到了红黑树作为解决哈希冲突的策略,相
比于使用链地址解决哈希冲突,红黑树树能够极大的降低查找时间复杂度。然而,二叉树
也存在不足,主要体现在普通的二叉树的添加、更新和删除都依赖查找,而普通二叉树的
查找时间复杂度都是 O(n),因此对于数据的删除,添加和更新操作频率大于查找的情况
下,如,常用的缓存数据库 Redis 中数据更新就很频繁,此时对数据的操作就很耗时,会
影响程序的性能。因此如果能设计出一种特殊的数据结构去优化二叉树的添加,删除等更
新操作,使得它们的时间复杂度维持在较低的水平,那么就能应对这种更新操作频繁的情
况。因此如何设计出添加,删除,更新,查找都是低复杂的二叉树数据结构成为本课程设
计的重点。
三,实验环境
C 语言 C11 标准,CLion 2023.1.1,Windows10 操作系统。
四,数据存储结构设计
所有数据存储结构均在项目的 data_structure.h 头文件中。使用到的结构体如下:
(一) 二叉树结构体
struct BinTree{
//哈希表
BinNode ** hashTable;
//二叉树根节点
BinNode * root;
//获取元素哈希码的函数
int (*getHashCode)(BNElemType ele);
//哈希表大小,方便求二叉树的一些属性,eg.最大深度,节点数等