数据结构课程设计----查找算法一需求和规格说明问题描述实现多种查找算法(顺序表、树表、散列表三种数据类型不小于2 类)并进行对比分析。用户输入查找数据界面动态演示基于查找过程的图形化显示。编程任务(1)将图形化界面的基本布局设计好根据选择的数据类型数目进行适当调整(2)选取并完成所选取的查找算法即在底层完成查找算法的代码逻辑为后续的图形化做准备这里我选取了 5 种算法分别是二分查找索引表查找平衡二叉树B 树散列表的拉链法。(3)根据 QT 的 paintEvent 事件的特性完成底层算法的实时动态展示。(4)完成 4 大按钮的功能分别是开始演示暂停演示终止演示重新初始化。(5)对用户可能出现的不规范操作进行处理准备防止程序的崩溃。二设计1设计思想首先此次设计重点除了对于不同结构种类的查找算法实现还在于如何体现不同查找算法的查找过程。这里我选取的是 QT 来做可视化处理利用重写 QT 的 paint 事件该事件会在一开始就被自动调用此后每一次更新需要自己手动更新该事件。利用此特性我决定在某一块白板组件上展现算法的动态将应的算法数据处理完后在查找过程中同步调用更新函数这样便达成了算法查找的同步图形化展示。2.设计表示1部分共同成员数据成员数据类型成员名描述Intlength随机生成数据的长度Inttarget查找的目标值intcurrentIndex当前搜索点的值int*nums随机生成的数据intcount查询次数2图形化界面类名成员类别类型成员名描述MainWindow函数voidgenerate()生成数据函数voidresult()查询结果消息弹窗voidstart(SearchcurrentSearch,BtnGroupbtngroup,intpage)开始按钮功能的封装voidpause(SearchcurrentSearch,BtnGroupbtngroup)暂停按钮功能封装voidterminate(SearchcurrentSearch,BtnGroupbtngroup)终止按钮功能封装voidreinitialize(SearchcurrentSearch,BtnGroupbtngroup,intpage)重新初始化功能封装voidinitChcek()切换页面时初始化所有算法的选择voidsetTarget()获取用户输入的查找值数据boolisProper查找目标是否合法boolisready是否已生成数据intrandMax随机数据的范围最大值intrandMin随机数据的范围最小值intmax随机数据中的最小值intmin随机数据中的最大值intrandLengthMax随机数据长度的范围最大值intrandLengthMin随机数据长度的范围最小值3Search 类所有算法类的父类用于存放一些所有算法类都会用到的封装函数类名成员类别类型成员名描述Search函数voidrepaint()更新绘画voidSleep(intmsec)自定义延时器数据boolispause是否点击暂停按钮boolisterminate是否点击终止按钮4HashSearch 类拉链法查找结构体名称成员数据类型成员名描述nodeIntdata存储的单词node*next下一个结点boolisSearched是否被搜索过类名成员类别类型成员名描述HashSearch函数voidpaintEvent(QPaintEvent*)绘画事件voidhashSearch()散列表查找对数据的处理voidgetsignal(boolisHashSearch,intlength,inttarget,int*nums)获取图形化界面点击的信号并对其解析处理voidsearchBucket(bucket*t,intindex)从 buckets 中找到指定的节点数据boolisfirst是否是第一次绘图boolishash是否选择了 hash 查找bucket*firstBucket指向第一个 bucket 的指针5ListSearch 类二分查找索引表查找类名成员类别类型成员名描述ListSearch函数voidpaintEvent(QPaintEvent*)绘画事件voidbinarySearch()二分查找对数据的处理voidgetsignal(boolbinary,boolindexed,intlength,inttarget,int*nums)获取图形化界面点击的信号并对其解析处理voidindexedSearch()索引表查找对数据的处理数据boolisBinary是否选择的是二分查找boolisIndexed是否选择的是索引查找int*indexList每个索引项其中的最大值int*starts每个索引项的起始索引值int*lengths每个索引项的长度6TreeSearch 类平衡树查找B 树查找结构体名称成员数据类型成员名描述bnodeIntdata存储数据bnode*leftC左儿子节点bnode*rightC右儿子节点intlevel节点的层数intbf平衡因子Bnodeintkeynum结点关键字个数intkey关键字数组key[0]不使用Bnode*parent双亲结点指针Bnode*[]ptr孩子结点指针数组类名成员类别类型成员名描述TreeSearch函数voidpaintEvent()绘图事件voidbalancedTreeSearch()平衡二叉树查找数据处理voidBTreeSearch()B 树查找数据处理voidgetsignal(boolisBTree,boolisbalancedTree,intlength,inttarget,int*nums)接收信号决定演示哪种算法intSearchNode(bnode*target,intdata)查找到 data 数据的父节点voidpaint(intx,inty,bnode*n)给当前节点画左右两个儿子节点的图voidBpaint(intx,inty,intpx,intpy,intindex,Bnode*b)给 B 树的当前节点画儿子节点的图intgetHeight(bnode*t)获取以当前节点为根的二叉树的高度voidsetBF(bnode*t)更新整棵树每个节点的平衡因子voidgetBf(bnode*target)获取平衡因子绝对值超过 1 的最高层次的那个节点注意这里我没有采用找层次最低的平衡点因为有个 BUG 实在无法定位修复所以采取了消耗更大的找层次最高的平衡点voidcorrect(bnodebegin,bnodetarget)判断当前错误属于什么型并执行相应的修复函数voidgetLevel(bnode*t)更新所有节点的层次数voidsetIndex(Bnode*b,intnum)给新关键字找到合适的位置插入voidreset(Bnode*b)重置调整 B 树voidSplitBnode(Bnodep,Bnodeq)将结点 p 分裂成两个结点,前一半保留,后一半移入结点 qvoiddfs(doublex,doubley,doublepx,doublepy,intindex,intlevel,Bnode*b)深度优先遍历 B 树,并逐层调用绘画voidgetMaxLevel(Bnode*b)获取 B 树的最大深度voidLL(bnode*t)平衡二叉树 LL 型问题voidRR(bnode*t)平衡二叉树 RR 型问题voidLR(bnode*t)平衡二叉树 LR 型问题voidRL(bnode*t)平衡二叉树 RL 型问题数据boolisbalancedTree是否选择平衡二叉树按钮boolisBTree是否选择 B 树按钮intr圆的半径doubleangle平衡二叉树儿子节点的初始偏转角度doubleaddangel每一层改变的偏转角度量QQueueq存储每个节点的 x,y 坐标QQueuebnode*node存储节点QQueuebnode*node_2存储节点用于广度优先遍历intwB 树关键字节点的宽度inthB 树关键字节点的高度intmaxLevelB 树的最大深度3.核心算法此次课设的核心算法主要是 5 个不同的查找算法和各个不同的算法类重写的 paint 绘图事件。首先用户在点击生成数据按钮后会触发 generate 函数根据设定的参数随机生成数据并记录下数据的最大值最小值和查找目标值。当然根据题目的要求我们在图形界面展示出随机数据的长度最大值最小值和查找目标因为必须兼容用户可以自己设定查找目标用户可以在展示页面直接对查找目标进行更改。用户选择对应算法后点击开始演示按钮触发 start 函数该函数根据用户选择的算法和生成的数据触发不同算法类的 getsignal 函数。在触发对应的算法之后因为像二分查找和索引表对数据要求必须是排序完的所以就需要对数据进行排序处理这里采用的冒泡排序。5 种算法诸如 binarySearch,balancedTreeSearchBtreeSearchindexedSearchhashSearch 函数便是对各自算法的所需对数据进行相应的处理比如树类的查找算法就需要重头构建相应的树都在对应的 Search 算法中进行数据处理。处理完后即开始查找不同于普通的算法查找为了动态图形化显示当前查找的进度我们通过 currentIndex 来表示当前查找节点的值同时只要 currentIndex 变化我们就手动调用 update 函数经过我们设置的短暂延迟便重新绘画整个图如此便完成了动态实时展示查找过程的效果。逻辑实现过程部分查找算法流程图如下所示二分查找算法平衡二叉树三用户手册程序运行将会显示出图形化界面用户首先需要点击生成数据按钮底层代码根据事先设定好的参数会随机生成数据并且将其显示到图形化界面上。为了满足用户自定义查找目标的要求除了查找目标可以自行设置其他数据都是 readOnly不可更改。然后用户需要选择对应的数据类型根据所选择的数据类型左下角的算法会有不同的显示比如选择树表那么左下角就会显示平衡二叉树和 B 树查找一共 5 种算法供用户选择。生成完数据并且选择好对应的算法后用户可以点击开始演示按钮根据对应的算法选择便会在对应的空白处显示不同的动态图形化显示。暂停演示按钮只有在点击开始演示按钮后才可以点击它会暂停整个查找过程使动态图形暂停演示。终止演示会直接情况整个图变化空白状态。重新初始化则会先清空当前演示并自动重新生成数据一次然后开始根据新的数据立马演示。四调试及测试1.测试数据点击生成数据按钮2.演示示例二分查找索引表查找B 树查找平衡树查找散列表查找查找成功以索引表为例查找成功以平衡二叉树为例查找失败以平衡二叉树为例(五)感想一开始写此课设的时候自己有很多代码重复性比较大但是发现的时候已经比较晚了重新进行封装后代码量大大减少并且逻辑更加清晰但是的确也费了不少力气。对于此次设计我最大的遗憾是没有结合多线程去实现而没有了多线程在实现一些功能上的确比较麻烦例如终止演示或重复点击相同的按钮等这些操作会造成各种各样的 bug虽然经过我的改进以单线程也可以完成这些功能但总体比较遗憾因为这应该是一次难得的多线程应用机会。再者因为一开始图形界面的设计问题布局过于小导致展示空间有限这就使得我不得不限定随机生成数据的数目最大值不能让用户去随意设置因为再怎么优化展示的算法空间始终无法满足太多的数据展示。不过此次课设我也收获颇多首先是对于 bfsdfs 的不同应用场景有了更深的理解其次自己去查了网上的资料独立写出了平衡二叉树和 B 树查找并且将他们图形化让我对于这两种的算法的理解更加深刻同时不再像以往一样对于树结构总有种陌生感不熟悉各种操作。并且通过此次课设我体会到了合理的函数封装与类的继承关系设计的重要性如果只是一味的按照逻辑想到哪写到哪那当代码量逐渐庞大起来时便会造成自己也看不懂的困境。虽然此次对于自己的设计与封装还有很多很多的不足之处但是经过此次的尝试我相信自己能在下一次的程序设计种设计出更合理的程序结构。♻️ 资源大小20.2MB➡️资源下载https://download.csdn.net/download/s1t16/87415908注更多内容可关注微信公众号【神仙别闹】如当前文章或代码侵犯了您的权益请私信作者删除
基于QT（C++）实现查找算法图形化（数据结构课程设计）
数据结构课程设计----查找算法一需求和规格说明问题描述实现多种查找算法(顺序表、树表、散列表三种数据类型不小于2 类)并进行对比分析。用户输入查找数据界面动态演示基于查找过程的图形化显示。编程任务(1)将图形化界面的基本布局设计好根据选择的数据类型数目进行适当调整(2)选取并完成所选取的查找算法即在底层完成查找算法的代码逻辑为后续的图形化做准备这里我选取了 5 种算法分别是二分查找索引表查找平衡二叉树B 树散列表的拉链法。(3)根据 QT 的 paintEvent 事件的特性完成底层算法的实时动态展示。(4)完成 4 大按钮的功能分别是开始演示暂停演示终止演示重新初始化。(5)对用户可能出现的不规范操作进行处理准备防止程序的崩溃。二设计1设计思想首先此次设计重点除了对于不同结构种类的查找算法实现还在于如何体现不同查找算法的查找过程。这里我选取的是 QT 来做可视化处理利用重写 QT 的 paint 事件该事件会在一开始就被自动调用此后每一次更新需要自己手动更新该事件。利用此特性我决定在某一块白板组件上展现算法的动态将应的算法数据处理完后在查找过程中同步调用更新函数这样便达成了算法查找的同步图形化展示。2.设计表示1部分共同成员数据成员数据类型成员名描述Intlength随机生成数据的长度Inttarget查找的目标值intcurrentIndex当前搜索点的值int*nums随机生成的数据intcount查询次数2图形化界面类名成员类别类型成员名描述MainWindow函数voidgenerate()生成数据函数voidresult()查询结果消息弹窗voidstart(SearchcurrentSearch,BtnGroupbtngroup,intpage)开始按钮功能的封装voidpause(SearchcurrentSearch,BtnGroupbtngroup)暂停按钮功能封装voidterminate(SearchcurrentSearch,BtnGroupbtngroup)终止按钮功能封装voidreinitialize(SearchcurrentSearch,BtnGroupbtngroup,intpage)重新初始化功能封装voidinitChcek()切换页面时初始化所有算法的选择voidsetTarget()获取用户输入的查找值数据boolisProper查找目标是否合法boolisready是否已生成数据intrandMax随机数据的范围最大值intrandMin随机数据的范围最小值intmax随机数据中的最小值intmin随机数据中的最大值intrandLengthMax随机数据长度的范围最大值intrandLengthMin随机数据长度的范围最小值3Search 类所有算法类的父类用于存放一些所有算法类都会用到的封装函数类名成员类别类型成员名描述Search函数voidrepaint()更新绘画voidSleep(intmsec)自定义延时器数据boolispause是否点击暂停按钮boolisterminate是否点击终止按钮4HashSearch 类拉链法查找结构体名称成员数据类型成员名描述nodeIntdata存储的单词node*next下一个结点boolisSearched是否被搜索过类名成员类别类型成员名描述HashSearch函数voidpaintEvent(QPaintEvent*)绘画事件voidhashSearch()散列表查找对数据的处理voidgetsignal(boolisHashSearch,intlength,inttarget,int*nums)获取图形化界面点击的信号并对其解析处理voidsearchBucket(bucket*t,intindex)从 buckets 中找到指定的节点数据boolisfirst是否是第一次绘图boolishash是否选择了 hash 查找bucket*firstBucket指向第一个 bucket 的指针5ListSearch 类二分查找索引表查找类名成员类别类型成员名描述ListSearch函数voidpaintEvent(QPaintEvent*)绘画事件voidbinarySearch()二分查找对数据的处理voidgetsignal(boolbinary,boolindexed,intlength,inttarget,int*nums)获取图形化界面点击的信号并对其解析处理voidindexedSearch()索引表查找对数据的处理数据boolisBinary是否选择的是二分查找boolisIndexed是否选择的是索引查找int*indexList每个索引项其中的最大值int*starts每个索引项的起始索引值int*lengths每个索引项的长度6TreeSearch 类平衡树查找B 树查找结构体名称成员数据类型成员名描述bnodeIntdata存储数据bnode*leftC左儿子节点bnode*rightC右儿子节点intlevel节点的层数intbf平衡因子Bnodeintkeynum结点关键字个数intkey关键字数组key[0]不使用Bnode*parent双亲结点指针Bnode*[]ptr孩子结点指针数组类名成员类别类型成员名描述TreeSearch函数voidpaintEvent()绘图事件voidbalancedTreeSearch()平衡二叉树查找数据处理voidBTreeSearch()B 树查找数据处理voidgetsignal(boolisBTree,boolisbalancedTree,intlength,inttarget,int*nums)接收信号决定演示哪种算法intSearchNode(bnode*target,intdata)查找到 data 数据的父节点voidpaint(intx,inty,bnode*n)给当前节点画左右两个儿子节点的图voidBpaint(intx,inty,intpx,intpy,intindex,Bnode*b)给 B 树的当前节点画儿子节点的图intgetHeight(bnode*t)获取以当前节点为根的二叉树的高度voidsetBF(bnode*t)更新整棵树每个节点的平衡因子voidgetBf(bnode*target)获取平衡因子绝对值超过 1 的最高层次的那个节点注意这里我没有采用找层次最低的平衡点因为有个 BUG 实在无法定位修复所以采取了消耗更大的找层次最高的平衡点voidcorrect(bnodebegin,bnodetarget)判断当前错误属于什么型并执行相应的修复函数voidgetLevel(bnode*t)更新所有节点的层次数voidsetIndex(Bnode*b,intnum)给新关键字找到合适的位置插入voidreset(Bnode*b)重置调整 B 树voidSplitBnode(Bnodep,Bnodeq)将结点 p 分裂成两个结点,前一半保留,后一半移入结点 qvoiddfs(doublex,doubley,doublepx,doublepy,intindex,intlevel,Bnode*b)深度优先遍历 B 树,并逐层调用绘画voidgetMaxLevel(Bnode*b)获取 B 树的最大深度voidLL(bnode*t)平衡二叉树 LL 型问题voidRR(bnode*t)平衡二叉树 RR 型问题voidLR(bnode*t)平衡二叉树 LR 型问题voidRL(bnode*t)平衡二叉树 RL 型问题数据boolisbalancedTree是否选择平衡二叉树按钮boolisBTree是否选择 B 树按钮intr圆的半径doubleangle平衡二叉树儿子节点的初始偏转角度doubleaddangel每一层改变的偏转角度量QQueueq存储每个节点的 x,y 坐标QQueuebnode*node存储节点QQueuebnode*node_2存储节点用于广度优先遍历intwB 树关键字节点的宽度inthB 树关键字节点的高度intmaxLevelB 树的最大深度3.核心算法此次课设的核心算法主要是 5 个不同的查找算法和各个不同的算法类重写的 paint 绘图事件。首先用户在点击生成数据按钮后会触发 generate 函数根据设定的参数随机生成数据并记录下数据的最大值最小值和查找目标值。当然根据题目的要求我们在图形界面展示出随机数据的长度最大值最小值和查找目标因为必须兼容用户可以自己设定查找目标用户可以在展示页面直接对查找目标进行更改。用户选择对应算法后点击开始演示按钮触发 start 函数该函数根据用户选择的算法和生成的数据触发不同算法类的 getsignal 函数。在触发对应的算法之后因为像二分查找和索引表对数据要求必须是排序完的所以就需要对数据进行排序处理这里采用的冒泡排序。5 种算法诸如 binarySearch,balancedTreeSearchBtreeSearchindexedSearchhashSearch 函数便是对各自算法的所需对数据进行相应的处理比如树类的查找算法就需要重头构建相应的树都在对应的 Search 算法中进行数据处理。处理完后即开始查找不同于普通的算法查找为了动态图形化显示当前查找的进度我们通过 currentIndex 来表示当前查找节点的值同时只要 currentIndex 变化我们就手动调用 update 函数经过我们设置的短暂延迟便重新绘画整个图如此便完成了动态实时展示查找过程的效果。逻辑实现过程部分查找算法流程图如下所示二分查找算法平衡二叉树三用户手册程序运行将会显示出图形化界面用户首先需要点击生成数据按钮底层代码根据事先设定好的参数会随机生成数据并且将其显示到图形化界面上。为了满足用户自定义查找目标的要求除了查找目标可以自行设置其他数据都是 readOnly不可更改。然后用户需要选择对应的数据类型根据所选择的数据类型左下角的算法会有不同的显示比如选择树表那么左下角就会显示平衡二叉树和 B 树查找一共 5 种算法供用户选择。生成完数据并且选择好对应的算法后用户可以点击开始演示按钮根据对应的算法选择便会在对应的空白处显示不同的动态图形化显示。暂停演示按钮只有在点击开始演示按钮后才可以点击它会暂停整个查找过程使动态图形暂停演示。终止演示会直接情况整个图变化空白状态。重新初始化则会先清空当前演示并自动重新生成数据一次然后开始根据新的数据立马演示。四调试及测试1.测试数据点击生成数据按钮2.演示示例二分查找索引表查找B 树查找平衡树查找散列表查找查找成功以索引表为例查找成功以平衡二叉树为例查找失败以平衡二叉树为例(五)感想一开始写此课设的时候自己有很多代码重复性比较大但是发现的时候已经比较晚了重新进行封装后代码量大大减少并且逻辑更加清晰但是的确也费了不少力气。对于此次设计我最大的遗憾是没有结合多线程去实现而没有了多线程在实现一些功能上的确比较麻烦例如终止演示或重复点击相同的按钮等这些操作会造成各种各样的 bug虽然经过我的改进以单线程也可以完成这些功能但总体比较遗憾因为这应该是一次难得的多线程应用机会。再者因为一开始图形界面的设计问题布局过于小导致展示空间有限这就使得我不得不限定随机生成数据的数目最大值不能让用户去随意设置因为再怎么优化展示的算法空间始终无法满足太多的数据展示。不过此次课设我也收获颇多首先是对于 bfsdfs 的不同应用场景有了更深的理解其次自己去查了网上的资料独立写出了平衡二叉树和 B 树查找并且将他们图形化让我对于这两种的算法的理解更加深刻同时不再像以往一样对于树结构总有种陌生感不熟悉各种操作。并且通过此次课设我体会到了合理的函数封装与类的继承关系设计的重要性如果只是一味的按照逻辑想到哪写到哪那当代码量逐渐庞大起来时便会造成自己也看不懂的困境。虽然此次对于自己的设计与封装还有很多很多的不足之处但是经过此次的尝试我相信自己能在下一次的程序设计种设计出更合理的程序结构。♻️ 资源大小20.2MB➡️资源下载https://download.csdn.net/download/s1t16/87415908注更多内容可关注微信公众号【神仙别闹】如当前文章或代码侵犯了您的权益请私信作者删除
