基于QT实现的可视化链表(单链表、循环链表、双向链表)

1.1 题目

题号1：分别以单链表、循环链表、双向链表为例，实现线性表的建立、插入、删除、查找等基本操作。

要求：能够把建立、插入、删除等基本操作的过程随时显示输出来。

1.2 软件功能

功能分为三个板块，分别是单链表、循环链表、双向链表的建立、插入、删除等基本操作的过程。

单链表

• 查看单链表定义，相应算法代码

• 建立一个带头结点的空单链表

• 指定插入位置及元素值到单链表中

• 随机插入5个元素到单链表的尾部

• 指定删除元素位置（从1开始），从单链表中删除

• 输入查找值，得到元素在单链表中位置

• 清空销毁单链表

• 能够调整演示的速度快慢

循环链表

• 查看循环链表定义，相应算法代码

• 建立一个带头结点的空循环链表

• 指定插入位置及元素值到循环链表中

• 随机插入5个元素到循环链表的尾部

• 指定删除元素位置（从1开始），从循环链表中删除

• 输入查找值，得到元素在循环链表中位置

• 清空销毁循环链表

• 能够调整演示的速度快慢

双向链表

• 查看双向链表定义，相应算法代码

• 建立一个带头结点的空双向链表

• 指定插入位置及元素值到双向链表中

• 随机插入5个元素到双向链表的尾部

• 指定删除元素位置（从1开始），从双向链表中删除

• 输入查找值，得到元素在双向链表中位置

• 清空销毁双向链表

• 能够调整演示的速度快慢

上述所有功能采用面向对象的方法通过C++语言程序结合QT框架实现，后面会详细介绍。

1.3 设计思想

• 学习相应知识，做好必要的准备工作
  由于以前都是采用控制台进行编程，即便涉及一些简单的图像界面，但是比较粗制简陋，无法入眼，并不是标准规范、人性化的用户交互界面，所以要完成本次的数据结构课程设计必须从零起步，学习可视化编程开发。在C++的一系列可视化开发框架下，我选择用Qt来实现程序的功能，因为Qt相对较为简单，容易上手入门，同时Qt是较为新兴的技术框架，并且跨平台开发，很有前景和实用性。通过几天的学习，理解掌握的Qt的必要知识，包括最为核心的信号和槽函数机制、UI控件的使用、Scene-View视图框架等核心技术。

• 自顶向下设计
  有了必要的准备知识，就可以进行程序的总体规划设计了。自顶向下分析是常用的分析方法，本次题目其实较为简单，常用的链表结构我们在学习数据结构课程时已经非常熟练，此次实现图形化界面的演示需要结合原有结构，融入图形化元素和用户界面接口，对程序的功能分析，显然程序的功能分为三个子功能模块，分别对每个模块进行设计即可完成整个任务。

• 分模块实现
  虽然程序有三个部分组成，但是每个部分的功能需要完全一样，用户界面完全一样，划分为三个模块，只要实现一个模块，其余两个模块只要非常短的时间就可完成。实际开发时，先实现单链表模块，完成以后，循环链表和双向链表只需要在前面基础上稍作修改即可。

• 自底向上实现
  具体实现时，先定义每个类的属性和相应函数，然后根据定义，设计相应算法自底向上进行实现，逐个击破，最终完成所有程序的设计。

1.4 逻辑结构与物理结构

1.4.1 单链表

节点定义

单链表

1.4.2 循环链表

节点定义

循环链表

1.4.3 双向（循环）链表

节点定义

双向循环链表

1.5 开发平台

1.5.1 开发平台

• 计算机型号：惠普Pavilion M4

• 计算机内存：4.00GB

• CPU：Intel Core i5 2.6GHz

• 操作系统：Windows 10 家庭版

• 开发语言：C++（C++11标准以上）

• 开发框架：QT

• 集成开发环境：Qt Version 5.9.1

• 编译器：MinGW 32bit

1.5.2 运行环境

• 可在上述集成环境下运行

• 通过windeployqt.exe及Enigma Virtual Box进行整合压缩为发布为了一个 LinkListVisualizer.exe 文件，可在普通 Windows 机型下运行

1.6 系统的运行结果分析说明

1.6.1 调试及开发过程

1.6.1.1 调试

本次开发采用的是新技术框架Qt，同时也是跨平台的，在Qt Creator中开发调试，Qt中包含了大量的库类，类似于java开发简便，Qt有较好的调试器，但是在本次开发中没有用到，偶尔遇到一些小麻烦或者小bug，我们只需在控制台中输出一些数据便可分析定位错误原因。

例如：

输出：

1.6.1.2 开发

本题目虽然有三个小题，但是三个子题目大同小异，架构类似，所以采用分模块逐步开发方式。先确定主窗口，控制好整体界面和架构，然后完成最简单的单链表设计和开发，单链表完成以后整个题目大部分工作已经完成，剩下循环链表和双向链表只需要简单修改就可完成。

1.6.2 成果分析

1.6.2.1 正确性

经过多次不同角度的验证，程序表现的十分优秀，与预期没有任何差错。

单链表运行样例图

循环链表运行样例图

双向（循环）链表运行样例图

1.6.2.2 稳定性

图形的大小均采用了宏定义，可根据需要随时调整。

可通过下拉框和左右拉框看到调整大小和未显示的区域。

在不同速度调节下，不同速度均表现的十分稳定。

三个小部件均能同时稳定正确运行。

1.6.2.3 容错能力

本程序有非常好的容错能力，如下：

按钮只有在能够进行操作的情况下，才会处于有效状态，例如，初始时，只能“创建”，不能“插入”、“删除”等操作；

在没有节点时，不能“删除”；

输入利用控件保证输入的正确性；插入删除位置通过选择保证正确；

输入的合理性通过输入控件保证，当要求输入数字时，输入其它非法字符将不会处理，输入范围在[-999999999, 999999999]，其它范围是无法输入的。

1.7 操作说明

本题目分为了三个部分，分别是单链表、循环链表、双向链表的基本操作演示。通过前面介绍的运行环境下进行程序的运行。

1.7.1 主界面操作

1.7.1.1 主界面

按下相应按钮进入相应功能。

将鼠标悬停在相应按钮上可得到相应提示。

1.7.2 单链表

1.7.2.1 进入功能区

点击主菜单的“单链表”进入，可以看到初始界面：

按钮或输入控件较亮表示可以点击或输入，否则处于不可编辑状态。

1.7.2.2 调节演示速度

右下角有操作后的状态提示及过程显示的速度快慢调节器，状态提示不可编辑，速度调节器可以通过鼠标直接“点击”或者点击后按“左右方向键”进行速度调节，最右段为最快速度。

1.7.2.3 创建单链表

点击创建按钮可以创建一个单链表，或者在已经创建一个单链表后销毁并重新创建新的单链表。

1.7.2.4 插入节点

插入节点有两种方式，可以手动插入，也可自动插入。

手动插入节点方式：

• 点击插入位置下拉框，选择插入位置（从1开始）
• 在插入文本框中输入插入值
• 点击插入

点击“尾端随机5个”按钮，即可自动插入五个随机值到链表尾部去。

1.7.2.5 删除节点

点击删除位置下拉框，可选择相应的删除节点位置，然后点击删除按钮。

删除后

1.7.2.5 查找节点

在查找值中输入要查找的值，点击“查找”按钮。

查找结果：

1.7.2.6 销毁链表

点击清空按钮，清空单链表，释放资源。

1.7.3 循环链表

循环链表的操作与单链表完全一样，不再赘述。

1.7.4 双向（循环）链表

双向循环链表的操作与单链表完全一样，不再赘述。