基于QT（C++）实现线性表节点的存储结构综合应用设计

♻️ 资源

大小：41.1MB

➡️资源下载：https://download.csdn.net/download/s1t16/87425415

线性表节点的存储结构综合应用设计说明

在关系数据库中，所有数据对象都以表的形式存储，如需在关系数据库中存储树结构，需设置一指向父节点的属性来实现，该过程可以通过如下线性表节点的存储结构模拟：

struct Node { int id;//该线性表中所有节点的 ID 都唯一 Elemtype data;//节点的值，自定义数据类型 int pid;//表示该节点的父节点，值为 0 表示根，对应线性表中其他节点的 id 值 Node *next;//指向线性表下一个节点 }

代码 2.1 线性表节点的存储结构

1. 请设计一个算法，根据线性表中 pid 的指向，将该线性表中存储的节点转换为树形结构。
2. 在树结构中插入一个节点，自动将其加入到线性表中。
3. 在树结构中删除一个节点，自动更新线性表的结构。

软件功能

软件功能设计

1. 能够将 txt 存储的数据导入到软件中
2. 能够将树形结构和线性表结构用较好的视觉控件表达
3. 在对树形结构的数据进行删除和增加子节点操作时，线性表要能自动更新

功能实现方式

QT 下的控件有 QTreeWidget 和 QTableWidget 分别能较好地从视觉上表达树形（左侧）和线性（右侧）结构，如 2.1 所示。

图 2.1 用户界面

因为 QT 的控件有比较好的包装，故通过如下代码配置：

deleteNodeAction addChildNodeAction = new QAction("&添加子节点", this); deleteNodeAction = new QAction("&删除节点", this); connect(addChildNodeAction,SIGNAL(triggered()),this,SLOT(addChildNode())); connect(deleteNodeAction,SIGNAL(triggered()),this,SLOT(deleteNode()));

代码 2.2 小菜单设置代码以及：

void MainWindow::on_treeWidget_customContextMenuRequested(const QPoint &pos ) { curItem = ui->treeWidget->itemAt(pos); //获取当前被点击的节点 if(curItem != nullptr){ QVariant var = curItem->data(0,Qt::UserRole); QMenu *popMenu =new QMenu(this); popMenu->addAction(addChildNodeAction); popMenu->addAction(deleteNodeAction); popMenu->exec(QCursor::pos()); } }

代码 2.3 小菜单设置代码

用以上两段代码就可以右键显示具体操作的菜单，如 2.2 所示。

图 2.2 小菜单

还有其它的操作已经在上一章的算法实现中说明。

设计思想

软件实现思路

软件的实现主要分两部走：第一步，我先用纯 C++ 方式完整实现算法。环境是 VisualStudio2017。

第二步，使用 QT 下的控件实现标准交互式图形界面，加载输入框、按钮、功能菜单等内容。QT 控件较

root 课程设计报

好地封装了一些查找、插入、删除的函数，可供我们使用。我们可以将接下来的代码看作是和纯 C++ 方式的一一对应。

而第二步又可以分为两步：一、导入数据文件，将线性表型数据文件转为树形结构并显示；二、在树形结构上完成添加和删除操作时，同步对线性表执行该操作。

数据结构的选用与设计思想

题目已经限制了数据结构为树形和线性。但注意到，我需要一种方式来记录转换后的树。否则通过了链表生成了一颗树后，每当我们想用一种图形化界面来展现树的时候，都需要重新生成一遍，这是十分不合理的。

题目要求的线性表的节点存储结构如下：

struct Node { int id;//该线性表中所有节点的 ID 都唯一 Elemtype data;//节点的值，自定义数据类型 int pid;//表示该节点的父节点，值为 0 表示根，对应线性表中其他节点的 id 值 Node *next;//指向线性表下一个节点 }

代码 2.4 线性表节点的存储结构

我经过思考，认为仅仅有这些属性是没有足够的信息一次性记录一颗树的父子节点信息，使得能在

的时间打印一颗树。

接下来，我们考虑选取哪种结构存储一棵树。在《数据结构》这门课[1] 中，我们知道一棵树有三种表达方式：

1. 双亲表示法
2. 孩子表示法
3. 孩子兄弟表示法

双亲表示法在求节点的孩子时需要遍历整个结构，而 pid 就相当于双亲信息；孩子表示法将每个节点的孩子节点排列起来，看成线性表，但是不适用于求父节点的操作。孩子兄弟表示法这种存储结构便于实现各种树的操作，在这里就需要新增两个指针：structNode*firstchild,nextsbling;

综合这三种传统方法，以及从代码的复杂程度上考虑，如果使用双亲表示 + 孩子表示法较为合理。int pid 已经给出了父节点信息，而孩子的表示可以使用 Vector 数据结构。

除此之外，我通过网上搜索，还看了许多其它语言如 Python、Javascript[2] 等的线性结构转树结构的代码，它们都使用了类似列表的数据结构来记录子节点，如以下代码第 17 行：

function Tree(datas){ var tree={}, parent_id; for(var i=0;i<datas.length;i++){ var item=datas[i]; tree[item.id]=item } var root=null; for(var i=0;i<datas.length;i++){ var obj=datas[i]; if(obj.in==null) { root=tree[obj.id] } else { parent_id=obj.in; if(!tree[parent_id].children) { tree[parent_id].children=[] } tree[parent_id].children.push(tree[obj.id]) } } return root; }

代码 2.5 JavaScript 线性结构转树结构代码

由以上分析，我认为，我使用双亲表示 + 孩子表示法是合理的。最后我选取的存储结构如下：

struct Node { int id;//该线性表中所有节点的 ID 都唯一 Elemtype data; //节点的值，自定义数据类型 int pid;//表示该节点的父节点，值为 0 表示根，对应线性表中其他节点的 id 值 Node *next; //指向线性表下一个节点 vector <Node *> children; // 指向孩子的指针 }

代码 2.6 最后选取的线性表存储结构相对于题目要求的数据结构，新增了 vector<Node*>children 这一成员来记录指向孩子的指针。

算法设计基本流程

我设计了四个函数，分别针对我们需要的四个操作。

线性链表初始化

t 课程设计报

int initLinearList(Node *L) { int n; //个数 Node *p = L; int i; cin >> n; for (i = 0; i < n; i++) { p->next = new Node; p = p->next; cin >> p->id >> p->pid; } p->next = NULL; return 0; }

代码 2.7 纯 C++ 实现的算法

这一部分主要是将输入的线性数据记录下来，生成一个链表。没有其它特殊的地方。

算法复杂度：O(n)

将线性链表转为树形结构，记录子节点信息

int list2tree(Node *L) { Node *p = L->next; Node *q; int cur_pid; while (p) { cur_pid = p->pid; if (cur_pid == 0) { = p->next; continue; } = L->next; while (q) { // 找到父亲节点 if (q->id == cur_pid) { q->children.push_back(p);//将子节点的指针记录下来 } q = q->next; } p = p->next; } return 0; }

代码 2.8 纯 C++ 实现的算法

算法说明：主要部分是两个 while 循环。对于每一个节点，都遍历一次链表，将它的子节点的指针加入到 children 里。

算法复杂度：O(n2)

添加节点

int addNode(Node *L, Node &e) { Node *p; Node *t = new Node; memcpy(&(t->data), &(e.data), sizeof(ElemType)); t->id = e.id; t->pid = e.pid; t->next = L->next->next; L->next->next = t; p = t->next; while (p) { if (p->id == e.pid) { p->children.push_back(t); return 0; } p = p->next; } return 0; }

代码 2.9 纯 C++ 实现的算法

算法说明：主要部分是 while 循环。先将要添加的节点用头插法加入到链表中；再根据要添加的节点的 pid，遍历一次链表，找到它的父节点，然后将要添加的节点的指针加入到它的父节点的 children 里。

算法复杂度：O(n)

删除节点

int deleteNode(Node *L, int id) { Node *q = L; Node *p = L->next; while (p) { if (p->id == id) { q->next = p->next; for (auto i : p->children) { deleteNode(L, i->id); } delete p; = q->next; } else { = q->next; p = q->next; }

代码 2.10 纯 C++ 实现的算法

算法说明：主要部分是 while 循环和 for 循环。注意删除一个树节点的话，要连带着删除它的子节点，故在 for 循环中遍历要删除的节点的子节点，递归调用 deleteNode 删除它的子节点。

算法复杂度：O(n2)

展示树结构

int printTree(Node *p, int level) { if (p->children.size() == 0) { return 0; } for (auto i : p->children) { for (int j = 0; j < level; j++) { cout << " "; } cout << i->id << endl; printTree(i, level + 1); } return 0; }

代码 2.11 纯 C++ 实现的算法

算法说明：递归调用，通过 id 号前面的空格的多少来展示层级关系。

算法复杂度：O(n) 控制台效果如 2.3：

图 2.3 展示树结构

逻辑结构与物理结构

同样，这部分我分为两块说明，一部分是纯 C++ 方式，另一部分是 QT 方式。

纯 C++ 方式

逻辑结构：树形结构。因为题目要求是将线性表转为树形结构。

物理结构：链式结构。结构如下：

struct Node { int id;//该线性表中所有节点的 ID 都唯一 Elemtype data;//节点的值，自定义数据类型 int pid;//表示该节点的父节点，值为 0 表示根，对应线性表中其他节点的 id 值 Node *next;//指向线性表下一个节点 vector <Node *> children;// 指向孩子的指针 }

代码 2.12 线性表节点的存储结构

QT 方式

逻辑结构：树形结构和线性结构。因为题目要求是将线性表转为树形结构，并且我需要展示线性结构。

物理结构：链式结构。主要是 QTableWidgetItem 和 QTreeWidgetItem，它们主要的成员如下：

class QTreeWidgetItem { QTreeWidgetItem * parent; QList <QTreeWidgetItem *> children; QString text; }

代码 2.13 QTreeWidgetItem

class QTableWidgetItem { int row; int column; QString text; }

代码 2.14 QTableWidgetItem

开发平台

开发平台：QT5.13.0(MSVC2017)

运行环境：QTCreator4.9.2Community

其它的库：CSTL(纯 C 方式实现时)

系统的运行结果分析说明

应用开发工具进行调试及开发

QT 提供了非常方便的 QDebug 库，可以很方便地在控制台输出结果，例如在一些关键位置写下以下这些代码等：

qDebug() << "Err";qDebug() << "deleteNode";

代码 2.15 应用开发工具进行调试及开发然后打开 debug 调试[3]，就可以看到如 2.4 这些提示：

图 2.4 调试

这大大加快了开发的速度。

开发中比较重要的 QT 控件是 QTreeWidget 和 QTableWidget[4]，以及 QT 的核心信号与槽机制[5]。

但由于不是本课设核心知识点，故不作说明，仅列出参考文献。

开发软件到达的成果

由于本项目较为简单，运行结果的正确性和稳定性可以得到较为直观的说明。

容错能力中，主要有以下几点：

输入文件存在 id 重复

插入的节点 id 重复

当遇到以上这两种情况时，会跳出错误提示，如 2.5。

源文件出现重复 (b) 插入节点 id 重复

图 2.5 错误提示

运行案例的方式说明运行结果

首先，我们先要准备一个 txt 文件，格式如下：第一行是节点个数，第二行是根节点的 id,data,pid。

pid=0 表示为根。从第三行开始是其它节点信息，依次为 id，data，pid。如 2.6。

图 2.6 导入数据格式

选中准备好的 txt 文件，如 2.7(a)。点击文件-> 从 txt 文件导入，在导航中选择准备好的 txt 文件，如 2.7(b)。

选中 txt 文件 (b) 通过 txt 文件导入链表数据图 2.7 删除节点

然后就可以看到如 2.8 界面。可通过拖拉窗口使控件显示完整。

图 2.8 导入后的结果

删除节点

在要删除的节点上右键，选择删除节点，如 2.10(a)。单击删除节点后，可以看到左侧树结构中，所有该节点以及该节点的子节点都删除了；而在右侧，对应的节点也都同步删除了。如 2.9(b)，id 为 2 的节点及其 id=9 和 7 的节点都被删除了。

添加子节点

在要添加子节点的节点上右键，选择添加子节点节点，如 2.10(a)。之后会弹出对话框，输入 id 和 data，用空格分割，如 2.10(b)。

这里我们输入 20def，点击 OK。然后就可以看到树结构中 id=2 的节点有了 id=20，data=def 的节点，右侧线性表的尾部新增了一个 id=20，data=def 的节点，如 2.11 中红圈中所示，从而做到线性表和树形结构同步变化。

选择删除节点 (b) 删除节点后图 2.9 删除节点

选择添加节点 (b) 添加子节点图 2.10 添加子节点

图 2.11 添加子节点

操作说明

具体的操作说明已经在上一节 2.6.3 运行案例的方式说明运行结果中，较详细地列出。

实践总结

所做的工作

在这次课程设计中，我主要完成了两款软件。一款能够模拟哈希表的建立、删除、新增、查找操作。一款能够模拟线性表转为树形结构的操作。

在实践过程中，我复习了哈希表的各种哈希函数的选取和冲突的解决方法；哈希表的建立、查找、插入和删除操作。我通过查阅资料，分析选取了较好的线性表转树形结构的数据结构和方法。

还有就是自学了 QT，了解掌握了 QT 的基本信号与槽的原理，以及部分关键控件如 QTreeWidget、

QTableWidget 等的操作。

总结与收获

这是我第一次自己动手完成一款软件。在一开始选取平台的时候我纠结了很久。QT 相对来说上手比较慢，学习曲线较为陡峭。但是考录到 QT 良好的跨平台的特性，我还是选择了 QT。我在前期花了大量的时间熟悉 QT，了解 QT 的基本原理和核心机制。在后续的实现中，我又陆陆续续碰到不少问题。

比如，综合应用当中，我做的是 QTreeWidget 和 QTableWidget 时时保持同步，这就牵扯到信号的传递问题。我原来各个自定义控件封装较好，但是为了能够保证同步，而个人水平又有限，还是把一些封装的东西拆开了。

最后该份报告是使用同济大学本科毕业论文 latex 模板[6] 完成的，在图片的位置调整上花了挺大的功夫，就目前而言图片往往会和它的说明文字相隔较远的距离。这是 latex 的内部机制导致的; 另外还存在引用的代码会侵占页眉和页脚的问题，我一直尝试解决，但恕水平有限，无法完全解决，仍不美观，望老师见谅！

该套同济大学本科毕业论文 latex 模板中，加载了开源的参考文献的国标。所以只需手动把必要的信息放上即可。在我们的《数据结构》课程设计计划及题目当中，参考文献没有符号标明文献类别，是不规范的，也不符合《同济大学毕业设计（论文）模板（理工类）》的规定。

经过此次课设后，我自学能力提高了很多。从完全不懂 QT 到基本掌握 QT，其实是搜索了无数次网页的。另外 QT 还有较为完善的文档[4]，大大地方便了我的学习。这次课设还帮我复习了很多数据结构的知识，我认为我在这次课设中收获很大。