单链表算法的动态演示系统设计与实现

谢嘉，徐勇，梁后军

（安徽财经大学计算机系，蚌埠　233030）

单链表算法的动态演示系统设计与实现

谢嘉，徐勇，梁后军

（安徽财经大学计算机系，蚌埠233030）

0　引言

《数据结构》是计算机科学与技术专业的核心课程，它着力培养学生对于数据分析和算法规划的综合能力，而传统的教学模式使得算法教学相对困难，本系统的出现正是为了解决这样一个现状，系统通过编程技术实现了《数据结构》经典算法的动态演示，使算法理解起来更为直观。本系统主要展示了单链表的插入和删除算法。

1　系统设计

本动态演示系统针对由清华大学出版社出版的C语言版《数据结构》教材进行设计与开发，由于采用C#语言来编写C语言算法的演示动画，所以需要使用C#语言按照C语言风格编写一样的算法流程来控制整个演示系统，实际运行的是C#版本的相应算法，其中变量跟踪模块显示的地址是依据GCC编译器编译的C语言的可执行文件的内存布局模拟出来的，基于这样的基本思想，本演示系统得以开发。

引入多线程的目的是为了减小本数据结构动态演示系统在并发执行时所付出的时间和空间的开销。因为父子线程的并行，所以资源的共享和互斥问题显得尤为重要。归纳起来面临的问题有：

（1）系统中的控件属于子线程，子线程也拥有自己的窗口，但在Debug版本中却不能随便修改窗口控件的属性，否则会产生跨线程操作的异常。采取的措施是在线程构造函数中设其控件属性为假。

（2）多线程编程会遇到线程的同步与互斥问题，为了简化操作，避免因为线程间异步执行而导致数据的不一致性。采取的措施是在子线程开启后，部分变量仅仅在子线程被构造时被赋值，或者只有主线程才会修改其值，这样保证了操作的原子性。

（3）主线程控制子线程的开启、挂起、恢复与停止，而C#提供的 Thread类的 Abort、Suspend、Resume方法，均有一定的缺陷，其中部分函数已经被微软淘汰，这些函数会因为资源未及时释放而异常。又不能通过约束使用者的正确操作来保证系统的健壮性，所以只能通过设置开关变量来实现。

2　系统设计

该数据结构演示系统的算法核心包括三部分，分别是C语言版本源代码的滚动、对算法中出现的栈变量和堆变量的跟踪以及动画的同步演示，由于系统中涉及的每个算法，都是由这核心的三个步骤组成，因此以单链表的插入算法为例来叙述整个实现的核心思想。

本系统首先实例化一个Model_List_Control类对象，即演示界面子窗口，通过TreeView控件选择需要演示的具体算法，不同的选择将导致以不同参数实例化的List_Thread类对象，即子线程对象的创建。在单击开始按钮时，会调用List_Thread类的t_Start函数，这是真正意义上的子线程的开启。此时子线程与主线程并行。子线程不停地演示经典算法，主线程则用于控制子线程的状态，例如挂起、恢复、停止以及设置其休眠时间。

该系统采用了面向对象的思想，封装了多个类。下面详细介绍使用的类。

（1）定义被演示的数据结构所需的对象类

由于C#指针的使用不同于C语言，所以不能直接定义结构类似的节点，取而代之的是自定义的Lin-kNode类，重要成员如下：

（2）自定义子线程类

由于系统提供的Thread类成员函数有缺陷，在使用不恰当的时候会产生异常，所以自定义子线程类List_Thread再次封装了系统的Thread类，用于控制线程的开启、停止、挂起、恢复，提高了算法的健壮性，重要成员如下：

（3）定义动态演示子模块界面类

Model_List_Control子模块是该系统的重要组成部分。算法演示过程中的元素本质是属性被修改的Label标签类型，预先定义了10个标签代表这些数据结构元素，这限制了用户最大可以控制的线性长度为10。添加用于开始、暂停、停止、重置按钮，用于调用自定义子线程的函数相应，只有在恰当的时机（例如线程只有被开启，才有可能被停止、挂起或者关闭）才会执行，这是多线程编写中比较麻烦和复杂的部分，需要严密的思考各种可能出现的情况，才能避免因为未及时释放线程资源或者多次释放导致的进程异常。重要成员如下：

从操作系统吞吐量和运行效率角度考虑，多线程无疑比传统的单线程编程模式有很大的优势。传统的单线程编程模式，处理机调度的对象是进程，当进程执行在某个函数内部时，如果希望执行同进程的其他函数是无法实现的。上文提到自定义子线程类List_Thread类中的ThreadProc函数是线程的回调函数，这是最核心的函数，一旦线程开启就意味着函数的执行，函数执行完毕也就代表线程的结束。所以在函数内部调用了阻塞函数ShowDialog，保证按条件执行完毕后线程才能结束，自定义子线程类部分源代码如下：

［1］罗福强，杨剑，张敏辉.C#程序设计经典教程［M］.北京：清华大学出版社，2012.

［2］严蔚敏.数据结构（C语言版）.北京：清华大学出版社，2005.

［3］Daniel Solis.C#图解教程：人们邮电出版社，2008.

Single Linked List;Dynamic Demonstration;C#;Multi-thread

Design and Implementation of Dynamic Demo System of Single Linked List

XIE Jia，XU Yong，LIANG Hou-jun
（Department of Computer Science&Technology，Anhui University of Finance&Economics，Bengbu 233030）

1007-1423（2015）28-0061-05

10.3969/j.issn.1007-1423.2015.28.015

徐勇（1978-），男，博士，教授，硕士生导师，研究方向为社会计算、信息安全、数据挖掘

梁后军（1979-），男，博士，副教授，研究方向为计算机网络

2015-08-04

2015-09-26

介绍了在.NET平台下，使用C#语言开发关于单链表算法的动态演示系统，算法包括单链表的插入与删除。核心部分使用了多线程技术。

单链表；动态演示；C#；多线程

安徽财经大学教研项目（No.acjyzd201433）、国家社科基金规划项目（No.15BTQ043）、教育部人文社会科学研究基金面上项目（No.12YJA630136）、安徽省自然科学基金面上项目（No.1408085MF127）、安徽省高校省级优秀青年人才基金重点项目（No.2013SQRL031ZD）、安徽财经大学学科特区“企业信息管理与数据挖掘”建设项目资助

谢嘉（1994-），本科生

Introduces the dynamic demonstration system of single linked list algorithm based on.NET platform，including insertion and deletion of single linked list.The core technology of the system is multi-thread technology.