线性表动态演示系统的设计

陈 宏

西安欧亚学院信息工程学院，陕西西安 710065

数据结构是介于数学、计算机硬件、软件之间的一门核心课程，其任务是讨论现实世界中数据的各种逻辑结构、在计算机中的存储结构以及各种操作的实现等问题。其中，线性表是一种最简单、最基本，也是最常用的数据结构，是学习者最先接触到的一种数据结构，但由于初学者对线性表在内存中是如何存储的，数据在计算机中是如何处理的，都不是很明确，所以刚开始学习该课程就产生了畏惧心理。因此，开发一个线性表的动态演示系统是有必要的。

线性表动态演示系统主要包括顺序表和单链表两种存储结构，通过演示为学生提供了形象生动、内容丰富、直观具体的感性认识材料，使学生不再凭空想象，有利于调动学生的学习积极性，有利于培养学生的思维能力及解决问题的能力。本系统在Windows平台上采用Visual C++可视化编程工具进行开发，具体方法如下。

1 主菜单设计

线性表动态演示系统的主菜单包含三个菜单项，分别是“文件”菜单，“目录”菜单和“帮助”菜单。“文件”菜单含有一个“退出”子菜单。“目录”菜单有三个子菜单，分别是线性表定义子菜单、顺序表子菜单和单链表子菜单。“帮助”菜单含有一个“用户使用说明”子菜单。

2 线性表定义

功能：描述了线性表的定义和特点。

绘图算法：每输出一行文字，输出位置的Y轴坐标移动固定的值，可以将多行文字显示在客户区。

3 顺序表

1）顺序表存储结构

功能：描述了线性表的顺序存储结构并显示了线性表的顺序存储结构示意图。

绘图算法：每输出一行文字，输出位置的Y轴坐标移动固定的值。

2）顺序表插入数据演示

功能：将用户输入的数据元素插入到某个用户给定数据串序列的固定位置上。

算法：

（1）顺序表插入算法：顺序表的插入位置不能小于0或大于顺序表元素的个数，若插入位置不在此区间，弹出插入位置错误警告。当插入位置大于顺序表的存储空间在该程序中就是屏幕能显示矩形的个数，弹出错误警告。当参数输入正确时，顺序表的插入算法是：首先把存储单元长度（size）-1（因为顺序表的存储单元是从0开始编号）至插入位置（i）中的存储单元的数据元素依次后移一个存储单元，然后把数据元素x插入到存储单元i中，最后顺序表数据元素的个数加1。

（2）绘图算法

在绘图过程中，需要画一个顺序表，在程序中顺序表的存储结构是用矩形表示的。首先获取用户输入的串序列的数据个数（length），然后计算每个存储单元的长度即矩形的长度（table），最后画一个长度为100＋table×（length＋2）的矩形，并将其分割成length+2个等份，表示顺序表的存储单元。

3）顺序表删除数据演示

功能：将用户输入删除位置上的数据从顺序表中删除的过程。

算法：

（1）顺序表的删除算法

删除位置参数应该满足大于等于0且小于等于顺序表的长度减1，当参数不在此区间时，弹出参数输入错误警告。当参数输入正确时，删除步骤是：首先把删除位置对应的存储单元的数据元素存放到一个变量中，然后把插入位置对应的存储单元的后一个存储单元至顺序表长度-1存储单元的数据元素依次前移，最后把顺序表数据元素的个数-1。

（2）绘图算法

该模块的绘图算法和顺序表的插入算法类似，在此就不在獒述。

4 单链表

1）单链表的存储结构

功能：描述单链表的存储结构，单链表的表示方法，单链表的存储结构示意图。

绘图算法：每输出一行文字，输出位置的Y轴坐标移动固定的值。

2）单链表插入操作演示

功能：动态演示在单链表中插入一个数据元素的全过程。

算法描述：

（1）向链表中插入数据元素的算法：要在带头结点的单链表数据元素ai（i大于等于0且小于链表的数据元素的个数）结点前插入一个存放数据元素x的结点，首先要在单链表中寻找到存放数据元素ai-1的结点并由指针p指示，然后动态申请一个结点存储空间并由指针q指示，并把数据元素x的值赋予新结点的数据元素域，最后修改新结点的指针域指向数据元素ai结点，并修改数据元素ai-1结点的指针域指向新结点q。

（2）绘图算法：在（50，160）的位置画一个矩形作为头结点。以后每隔50个像素画一个矩形作为链表的元素结点，直到矩形的个数等于链表数据元素的个数。待插结点的x轴坐标是以插入位置结点x轴坐标作为基准的，y轴坐标为260。

3）单链表删除操作演示

功能：用户输入要删除的位置，系统就会将要删除位置的结点从链表中去掉。

算法：

（1）从链表中删除数据元素的算法：要在带头结点的单链表中删除数据元素ai所在结点，首先需要在单链表中寻找到存放数据元素ai-1的结点并由指针p指示，然后让指针s指向被删结点，并把数据元素ai的值赋予x，最后删除ai所在结点，并动态释放该结点的存储空间。

（2）绘图算法：从（50，160）的位置每隔50个像素依次绘制一个矩形，直到矩形个数等于链表元素个数加1，链表绘制完成。动态演示删除过程时，用红色笔画线将待删元素位置的前一个矩形和待删元素位置的后一个矩形连接起来，再用白色笔画线将原来待删位置与前一矩形之间的连线和待删位置与后一矩形之间的连线用白色笔重绘。

基于VC的线性表动态演示系统易用、灵活，具有良好的安全性。由于采用了面向对象编程，所以易于扩充。该系统界面友好、功能完善，生成的算法图直观、正确，为教学提供了有益的参考。

[1]朱站立.数据结构[M].西安：西安电子科技大学出版社，2003，1：256.

[2]齐舒创作室.Visual C++6.0开发技巧及实例剖析[M].北京：清华大学出版社，1999，2：130.