♻️ 资源大小41.1MB➡️资源下载https://download.csdn.net/download/s1t16/87425415线性表节点的存储结构综合应用设计说明在关系数据库中所有数据对象都以表的形式存储如需在关系数据库中存储树结构需设置一指向父节点的属性来实现该过程可以通过如下线性表节点的存储结构模拟struct Node { int id;//该线性表中所有节点的 ID 都唯一 Elemtype data;//节点的值自定义数据类型 int pid;//表示该节点的父节点值为 0 表示根对应线性表中其他节点的 id 值 Node *next;//指向线性表下一个节点 }代码 2.1 线性表节点的存储结构请设计一个算法根据线性表中 pid 的指向将该线性表中存储的节点转换为树形结构。在树结构中插入一个节点自动将其加入到线性表中。在树结构中删除一个节点自动更新线性表的结构。软件功能软件功能设计能够将 txt 存储的数据导入到软件中能够将树形结构和线性表结构用较好的视觉控件表达在对树形结构的数据进行删除和增加子节点操作时线性表要能自动更新功能实现方式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] 中我们知道一棵树有三种表达方式双亲表示法孩子表示法孩子兄弟表示法双亲表示法在求节点的孩子时需要遍历整个结构而 pid 就相当于双亲信息孩子表示法将每个节点的孩子节点排列起来看成线性表但是不适用于求父节点的操作。孩子兄弟表示法这种存储结构便于实现各种树的操作在这里就需要新增两个指针structNode*firstchild,nextsbling;综合这三种传统方法以及从代码的复杂程度上考虑如果使用双亲表示 孩子表示法较为合理。int pid 已经给出了父节点信息而孩子的表示可以使用 Vector 数据结构。除此之外我通过网上搜索还看了许多其它语言如 Python、Javascript[2] 等的线性结构转树结构的代码它们都使用了类似列表的数据结构来记录子节点如以下代码第 17 行function Tree(datas){ var tree{}, parent_id; for(var i0;idatas.length;i){ var itemdatas[i]; tree[item.id]item } var rootnull; for(var i0;idatas.length;i){ var objdatas[i]; if(obj.innull) { roottree[obj.id] } else { parent_idobj.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 最后选取的线性表存储结构相对于题目要求的数据结构新增了 vectorNode*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 QTreeWidgetItemclass 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。pid0 表示为根。从第三行开始是其它节点信息依次为 iddatapid。如 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 的节点及其 id9 和 7 的节点都被删除了。添加子节点在要添加子节点的节点上右键选择添加子节点节点如 2.10(a)。之后会弹出对话框输入 id 和 data用空格分割如 2.10(b)。这里我们输入 20def点击 OK。然后就可以看到树结构中 id2 的节点有了 id20datadef 的节点右侧线性表的尾部新增了一个 id20datadef 的节点如 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]大大地方便了我的学习。这次课设还帮我复习了很多数据结构的知识我认为我在这次课设中收获很大。