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

# 线性表节点的存储结构综合应用设计说明 在关系数据库中，所有数据对象都以表的形式存储，如需在关系数据库中存储树结构，需设置一指向父节点的属性来实现，该过程可以通过如下线性表节点的存储结构模拟： ```c++ 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 的控件有比较好的包装，故通过如下代码配置： ```c++ 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 小菜单设置代码以及： ```c++ 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++ 方式的一一对应。 而第二步又可以分为两步：一、导入数据文件，将线性表型数据文件转为树形结构并显示；二、在树形结构上完成添加和删除操作时，同步对线性表执行该操作。 数据结构的选用与设计思想 题目已经限制了数据结构为树形和线性。但注意到，我需要一种方式来记录转换后的树。否则通过了链表生成了一颗树后，每当我们想用一种图形化界面来展现树的时候，都需要重新生成一遍，这是十分不合理的。 题目要求的线性表的节点存储结构如下： ```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 行： ```c++ 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 线性结构转树结构代码 由以上分析，我认为，我使用双亲表示 + 孩子表示法是合理的。最后我选取的存储结构如下： ```c++ struct Node { int id;//该线性表中所有节点的 ID 都唯一 Elemtype data; //节点的值，自定义数据类型 int pid;//表示该节点的父节点，值为 0 表示根，对应线性表中其他节点的 id 值 Node *next; //指向线性表下一个节点 vector <Node *> children; // 指向孩子的指针 } ``` 代码 2.6 最后选取的线性表存储结构相对于题目要求的数据结构，新增了 vector<Node*>children 这一成员来记录指向孩子的指针。 **算法设计基本流程** 我设计了四个函数，分别针对我们需要的四个操作。 **线性链表初始化** t 课程设计报 ```c++ 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) 将线性链表转为树形结构，记录子节点信息 ```c++ 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) 添加节点