基于Qt实现的B-树演示程序

Expiredlove

发布日期: 2020-06-16 13:25:08 浏览量: 382
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

1.题目

从空树出发构造一颗深度至少为 3(不包括失误结点)的 3 阶 B-树(又称 2-3 树)并 可以随时进行查找、插入、删除等操作。

要求:能够把构造和删除过程中的 B-树随时显示输出来,能给出查找是否成功的有 关信息。

2.软件功能

本软件作为数据结构中“B-树”的实现和演示软件,做到以下功能:

  • 在软件运行时内部维护一个“B-树”的数据结构,可以对其进行增加、修改、删除 结点的操作,并在程序运行完成后自行释放

  • 软件应实现一个 GUI(Graphic User Interface,图形用户界面)能够适时显示 B-树 经过改动后的结构

  • 软件的 GUI 应提供给用户对于 B-树进行上述操作的接口(按钮、文本框),以便用 户输入。用户通过输入给出指令后,软件应执行用户的指令,并在对 B-树修改 后给出显示反馈

3.设计思想

本软件的体系结构为 MVC(Model-View-Controller)式,具体分“图形用户界面”和 “内部数据结构和算法”两部分。

3.1 图形用户界面的设计思想

图形用户界面包括 Model 和 Controller 的部分。

由于本软件基于 Qt 平台,因此可以利用 Qt 提供的图形用户界面库中的类(QWidget 等)来实现图形界面。

本软件设计时优先考虑 Microsoft Windows 等 PC 平台,故 GUI 的设计是窗口式的。 GUI 包括:

  • 提供给用户的指令按钮

  • 指令配套的参数的输入框

  • 实时显示树结构的显示区域

在 Qt Creator 中设计的 GUI 窗体如下图所示。

对于 B-树的打印,由于显示空间有限而树的构造可以无限,故不采用直接的图形来 打印 B-树。Qt 提供了一个名叫 QTreeView 的控件,能以类 Windows 下文件目录结构的方 式展示树结构的内容,具有层次性强、延展性强、易于实现的特点,故采用 QTreeView 来显示树。

3.2 数据结构和算法的设计思想

本软件只涉及 B-树这一种数据结构。 在 B-树上,有“添加键值”、“删除键值”、“查找键值”三个算法。其中,添加键值算法用到了结点分裂算法、删除键值算法用到了结点合并以及关键字不足的结点的补全算 法。它们均为纯粹基于 B-树的算法。

除此之外,为使 GUI 能打印该 B-树,另有一个将 B-树映射为 QTreeView 下具有层次 的 QStandardItem(Model)对象的显示算法。

4.逻辑结构与物理结构

4.1 逻辑结构

B-树为多路平衡查找树,与二叉搜索树的不同在于:

  • 它是多路的,这要求它是多叉树(最大分支数取决于阶)且它每两个分叉之间需要 有一个搜索键值用来定位。故 n+1 叉结点存 n 个键值

  • 它的空间利用率相比较低,因为每个结点的分支数不一定达到阶(最大分支数)m, 其可能值在 m/2 + 1 和 m 之间(根节点不受最小值限制)

  • 结点和关键字在每次插入后会进行调整,以保持每个叶节点等深

以硬盘存储中使用的 B-树结构为例,逻辑结构图如下:

4.2 物理结构

B-树数据结构涉及 BTree 类(一棵树的整体)以及 BTreeNode 类(树中的结点)。为 方便内存管理,它们全都继承 Qt 提供的标准 QObject 类。它在纯 C++类之上,添加了父/ 子对象关系设置的功能以便内存管理、信号/槽的实现以便异步调用。这样,数据结构类 便能继承这些优点。

BTree 类的定义包括 B-树的阶数 m,和一个 BTreeNode *指针,用于指向树的哨兵结 点(sentinel) ,该哨兵结点的唯一孩子为 B-树的根。亦即,BTree 对象只包括一个整数成 员变量和一个指针成员变量,BTreeNode 对象与 BTree 对象分开、分散放置在内存中。

BTreeNode 对象存有该节点的键值数 n,以及键值的列表和子结点的列表。这两个列 表均用 Qt 提供的 QList\<Element>模板类实现。这个模板类实现时,将在内存的另一处维 护一个顺序表,存储键值或子节点。键值数 n 为整数 qint32 类型,键值采用可比较的 QVariant 类型,可以作为 int、double 等类型的任何一种。子结点则为指向其他 BTreeNode 的 BTreeNode *指针。当该 BTreeNode 为叶节点时,所有的子结点皆为空(nullptr)。

这两个类的头文件(列出了成员变量和成员函数):

  1. class BTree : public QObject
  2. {
  3. Q_OBJECT
  4. public:
  5. // 显式构造函数
  6. explicit BTree(QObject *parent, qint32 m);
  7. // 哨兵结点
  8. BTreeNode *sentinel;
  9. // 阶
  10. qint32 m;
  11. // 获取该树的根结点
  12. BTreeNode *root();
  13. const BTreeNode *croot() const;
  14. // 树中搜索
  15. const QVector<QVariant> search(const QVariant &x);
  16. // 树中添加键值
  17. bool add(const QVariant &x);
  18. // 树中删除键值
  19. bool del(const QVariant &x);
  20. signals:
  21. // 信号函数,当树的内容更新时会释放该信号
  22. void updated();
  23. public slots:
  24. };
  1. class BTreeNode : public QObject
  2. {
  3. Q_OBJECT
  4. private:
  5. // 拆分结点的算法
  6. static void split(BTreeNode *toBeSplitted, qint32 m);
  7. // 在叶结点删除一个键值
  8. void delAtLeaf(qint32 m, qint32 searchIndex);
  9. // 处理结点缺少足够的键值的算法
  10. static void dealWithKeywordShortage(BTreeNode *me, qint32 m, qint32 keyWordBackup);
  11. // 插入键值的算法
  12. bool insertKey(const QVariant *x, BTreeNode *childNodeLeft, BTreeNode *childNodeRight, qint32 m, qint32 searchIndex = -1);
  13. // 获取父结点
  14. BTreeNode *parentNode();
  15. // 根据键值在本结点的索引来删除键值的算法
  16. void delByIndex(qint32 m, qint32 searchIndex);
  17. public:
  18. // 显式的构造函数
  19. explicit BTreeNode(QObject *parentNode = nullptr);
  20. // 结点的键值数,等于 keyWords 的长度
  21. qint32 n;
  22. // 键值表
  23. QList<QVariant> keyWords;
  24. // 子结点表
  25. QList<BTreeNode *> childNodes;
  26. // 在以该结点为根的子树中查找
  27. const QVector<QVariant> search(const QVariant *x);
  28. // 在以该结点为根的子树中添加键值
  29. bool add(const QVariant *x, qint32 m);
  30. // 在以该结点为根的子树中删除键值
  31. bool del(const QVariant *x, qint32 m);
  32. signals:
  33. public slots:
  34. };

5.开发平台

采用 Qt 5 5.11.1 作为开发框架,利用 Qt Creator 作为 IDE,构建套件为适用于桌面 Windows 的 MSVC2017 64 位工具链。最终构建产物为可在 Windows 上运行的.exe 应用程 序。

6.系统的运行结果分析说明

6.1 开发、调试过程

使用 Qt Creator 开发,其文件架构如下:

调试的方法采用编写代码-运行-查看结果-启动调试器-设置断点,运行-查看运行时变 量内容-调整代码-运行的流程。

6.2 开发成果

完整、无缺陷地实现了软件应有的功能。

6.3 创建新树

打开软件,在文本框中输入树的阶,单击“清空树”,会自动创建一棵指定阶的 B树。软件打开时也会默认创建 3 阶 B-树。在没有任何关键字时,新的 B-树为只有空的根 结点。

树的阶和结构已经在 GUI 上反馈:

6.4 添加键值

在文本框中输入整数,点击“添加键值”可以将这个整数作为键值添加到 B-树中, 同时显示会更新。添加了 15 个键值后,就构造了一颗深度为 4 层的 B-树。使用“全部展 开”和“收起到根节点”按钮,观察 B-树的整体和细节,如下:

观察 B-树的整体 观察 B-树的细节

可见,这个树结构符合 3 阶 B-树的定义。

6.5 查找键值

在输入框中输入要查找的键值,点击“查找键值”就会返回树的查找结果。

查询成功时 查询失败时

6.6 删除键值

在文本框中输入树中已有的键值,点击“删除键值”按钮,将会从树中删除该键值, 同时显示会更新。在删除过程中,树的结构仍然满足 B-树定义。

删除“8”和“12”后的树 删除更多结点后的树 删除所有键值,只剩空根节点的树

7.操作说明

7.1 基本操作说明

  • 打开软件,在文本框中输入树的阶,单击“清空树”,会自动创建一棵指定阶的 B树。软件打开时也会默认创建 3 阶 B-树

  • 在文本框中输入整数,点击“添加键值”可以将这个整数作为键值添加到 B-树中, 同时显示会更新

  • 在输入框中输入要查找的键值,点击“查找键值”就会返回树的查找结果

  • 在文本框中输入树中已有的键值,点击“删除键值”按钮,将会从树中删除该键值, 同时显示会更新

7.2 树的显示、查看

  • 树的显示方式为类 Windows 下的文件目录视图

  • 点击“收起到根结点”时,树会收起到根节点,方便整理查看

  • 单击每个“文件夹”项(对应数据结构中的结点)侧边的箭头(或双击该项),可 展开/收起该结点

  • “键值”项对应数据结构中结点中的键值,与同一结点的子结点并列

  • 叶结点中的键值之间会出现“查找失败”项,同时给出待查找键值所在的范围。“查找失败”项对应数据结构结点中的空指针(或失误结点),搜索到“查找失败” 时,说明键值不存在于这棵树内

  • 点击“全部展开”时,所有的项全部展开,方便观察树的细节

  • 软件会记住当前的状态是为“全部展开”还是“收起到根结点”,并在树更新时根 据当前状态重新构造目录项
上传的附件 cloud_download 基于Qt实现的B-树演示程序.7z ( 695.03kb, 3次下载 )
error_outline 下载需要13点积分

发送私信

你最美丽的时光陪我度过那些年

8
文章数
5
评论数
最近文章
eject