论文部分内容阅读
● 引言
《数据结构》这门课程对于大多数初学者来说十分抽象，枯燥无味，尤其是实验内容里面关于各种数据结构的算法程序较以前学过的程序设计内容更复杂，也不容易被理解，学生学起来十分吃力，所以我们希望有一种工具辅助实验教学，使抽象的内容形象化，改善实验教学环境，并使学生加深对程序的理解，提高学生学习的兴趣。
基于以上两个原因，我们开发了智能化数据结构实验教学辅助演示系统，它可以满足学生的这种需要，把数据结构中那些复杂的算法以直观生动的形式呈现出来，并且能生成适合个别化学习的教学内容和策略，给出系统建议，从而辅助教师更好地把知识传授给学生。
● 系统功能简介
1.系统的功能简介
智能化数据结构实验教学辅助演示系统的最大特点是具有智能性，它可根据学生以前的学习情况，给出系统建议和相应水平的测试题。它采用建构主义学习方法，以学生为中心，以测试题为驱动，引导学生自主学习，使学生能更加深刻地理解所学的内容。
这一系统从总体上可分为前端和后端，前端包括人机交互子系统，后端包括学习环境子系统、教学决策子系统和领域知识库。人机交互子系统向用户提供了友好的学习界面，其由用户注册登录界面、学习主界面、系统给出建议界面等组成。学习环境子系统围绕各种典型算法，展开讲解，它是这个教学辅助系统最基础最主要的内容。教学决策子系统根据一些决策原则和学生以前的学习情况给出适合学生当前水平的系统建议和测试题，这个子系统是本系统智能化的核心。领域知识库存储与演示算法相关的知识点、知识单元等内容，为教学决策子系统提供了决策的依据。图1是该子系统的系统功能图。
2.学习环境子系统简介
子系统以用克鲁斯卡尔算法生成最小生成树为例探讨数据结构中典型算法的演示过程，以此作为标准模板，逐步完善系统的实现，下面以克鲁斯卡尔为例来介绍学习环境子系统的主要功能。
（1）输入数据：先输入图的顶点个数，然后依次输入每一条边，这样系统就记下了原始的图。
（2）连续运行：输入数据后，界面上显示连续运行后原始图、原始图的临界矩阵、最小生成树、最小生成树的邻接矩阵及源程序代码。
（3）单步运行：连续运行后，就可以单步运行，每次只执行一行代码，同时与每行代码相关的变量也显示在界面上，最小生成树、其邻接矩阵和相关变量也随着程序的执行相应的发生变化。
（4）设置断点：如果想要程序执行到某条语句停下来，就可以设置相应的断点，接着与单步运行执行过程一样，直至执行到设置断点的位置。
● 实现过程中的技术难点
1.克鲁斯卡尔算法类模型的设计和实现
我们之所以选择克鲁斯卡尔算法作为模板，是因为在数据结构中，用克鲁斯卡尔算法生成最小生成树这个算法仅凭老师在黑板上讲不够直观，因此不容易被理解。此外它是非常经典的算法，基本不会随着时间的推移而修改。在本系统中我们把克鲁斯卡尔算法设计成一个类，克鲁斯卡尔算法类包括四个成员变量，它们分别是顶点个数、顶点的连通分量数组、原始图的邻接矩阵及图的最小生成树邻接矩阵；包括三个成员函数，分别是获得顶点数函数、原始图的初始化函数、将图转化成最小生成树的函数。具体实现过程如下：
（1）原始图的初始化函数：从前端接受顶点个数、原始图的邻接矩阵，并把最小生成树的邻接矩阵和原始图的邻接矩阵中无权值的位置都赋为-1，把各顶点的连通分量设为各不相同。
（2）把图转化成最小生成树的函数流程如图2所示。
2.读写文件
为了达到算法演示直观动态的效果，需要给出算法的动态演示环境。但由于系统运行时脱离算法程序的调试环境，需在连续运行时把运行过程每一步的结果写入文件，在单步运行和设置断点时从文件中把每一步结果一条条地读出，然后给学生。在这一过程中，就要频繁地读写文件。常用读写文件的函数如下：
（1）fopen：打开一个文件，以一个文件指针名称代表此文件，设置此文件属性并在主存储器规划一个缓冲区来暂时存放数据。其语法说明如下：FILE *fopen（const char *filename，const *mode）；即以一个指定属性打开文件。
（2）flose：关闭此文件，并释放所用缓冲区。其语法说明如下：int fclose（FILE *stream）；即将文件指针所对应的数据文件关闭。
（3）fprintf：以格式化将数据写于文件中，只能用于循环文件。其语法说明如下：Intfprintf（FILE*stream，const char * format[，argument，…]）。
（4）fscanf：以格式化将文件中数据读取，并存于变量中，只能用于循环文件，其语法说明如下： Int fscanf（FILE *stream，const char *format[，address，…]）。
在本系统中主要使用以下两条写语句：①fprintf（order，“%d”，flag）；②fprintf（data1，“%d…”，flag，…）；其中order文件存储源程序编号，data文件存储order文件中每一个编号对应的一行源程序中的变量及其值，flag表示每一行源程序的编号。
3.单步运行和设置断点
为了让学生更加清晰地认识程序的执行过程和最小生成树是怎样从原始图中一步步获得的，本系统除了能够连续运行外，还设置了单步运行，在单步运行时，程序执行到哪一步，相应的源代码就被亮条覆盖，以示区别，同时与本条代码相关的变量也被显示出来了。这里需要再次强调的是，单步运行时并不是程序真的在一步步执行，亮条覆盖的语句也不是正在执行的语句。算法程序脱离了程序的调试环境，不能够真正实现这些功能，真正执行程序是在连续运行时，单步执行只不过是把连续运行时写入文件的执行结果以单步的形式显示给学生，以达到更直观明了的目的。为了实现这个功能，需要在连续运行时写两个文件order和文件data1，order中只写入源程序每一条语句的编号，从零开始；文件data1写入order文件中的每一个编号对应的一行源程序变量及其值。单步运行时，首先从order文件中读出源程序的标号，同时到data1文件中读出此标号对应的变量和它的值，判断如果没有到文件尾，把标号对应的一行程序加亮条显示，同时显示相应的变量和它的值。
如果学生想看到程序从开始到某一固定位置的单步运行过程，就需要设置断点，设置断点时，首先应让系统记住要执行到的位置，点击源程序中的任意条语句，系统就会把这个位置记下，用一条语句（x=listbox->itemindex）即可，以后就用x控制程序的执行，直到完成，这里所用到的技术同单步运行时基本相同。
● 结论
本系统借助MySQL4.0数据库，运用Borland C Builder 6.0这种编程工具开发，并在Windows 2000 server环境下调试成功。
《数据结构》这门课程对于大多数初学者来说十分抽象，枯燥无味，尤其是实验内容里面关于各种数据结构的算法程序较以前学过的程序设计内容更复杂，也不容易被理解，学生学起来十分吃力，所以我们希望有一种工具辅助实验教学，使抽象的内容形象化，改善实验教学环境，并使学生加深对程序的理解，提高学生学习的兴趣。
基于以上两个原因，我们开发了智能化数据结构实验教学辅助演示系统，它可以满足学生的这种需要，把数据结构中那些复杂的算法以直观生动的形式呈现出来，并且能生成适合个别化学习的教学内容和策略，给出系统建议，从而辅助教师更好地把知识传授给学生。
● 系统功能简介
1.系统的功能简介
智能化数据结构实验教学辅助演示系统的最大特点是具有智能性，它可根据学生以前的学习情况，给出系统建议和相应水平的测试题。它采用建构主义学习方法，以学生为中心，以测试题为驱动，引导学生自主学习，使学生能更加深刻地理解所学的内容。
这一系统从总体上可分为前端和后端，前端包括人机交互子系统，后端包括学习环境子系统、教学决策子系统和领域知识库。人机交互子系统向用户提供了友好的学习界面，其由用户注册登录界面、学习主界面、系统给出建议界面等组成。学习环境子系统围绕各种典型算法，展开讲解，它是这个教学辅助系统最基础最主要的内容。教学决策子系统根据一些决策原则和学生以前的学习情况给出适合学生当前水平的系统建议和测试题，这个子系统是本系统智能化的核心。领域知识库存储与演示算法相关的知识点、知识单元等内容，为教学决策子系统提供了决策的依据。图1是该子系统的系统功能图。
2.学习环境子系统简介
子系统以用克鲁斯卡尔算法生成最小生成树为例探讨数据结构中典型算法的演示过程，以此作为标准模板，逐步完善系统的实现，下面以克鲁斯卡尔为例来介绍学习环境子系统的主要功能。
（1）输入数据：先输入图的顶点个数，然后依次输入每一条边，这样系统就记下了原始的图。
（2）连续运行：输入数据后，界面上显示连续运行后原始图、原始图的临界矩阵、最小生成树、最小生成树的邻接矩阵及源程序代码。
（3）单步运行：连续运行后，就可以单步运行，每次只执行一行代码，同时与每行代码相关的变量也显示在界面上，最小生成树、其邻接矩阵和相关变量也随着程序的执行相应的发生变化。
（4）设置断点：如果想要程序执行到某条语句停下来，就可以设置相应的断点，接着与单步运行执行过程一样，直至执行到设置断点的位置。
● 实现过程中的技术难点
1.克鲁斯卡尔算法类模型的设计和实现
我们之所以选择克鲁斯卡尔算法作为模板，是因为在数据结构中，用克鲁斯卡尔算法生成最小生成树这个算法仅凭老师在黑板上讲不够直观，因此不容易被理解。此外它是非常经典的算法，基本不会随着时间的推移而修改。在本系统中我们把克鲁斯卡尔算法设计成一个类，克鲁斯卡尔算法类包括四个成员变量，它们分别是顶点个数、顶点的连通分量数组、原始图的邻接矩阵及图的最小生成树邻接矩阵；包括三个成员函数，分别是获得顶点数函数、原始图的初始化函数、将图转化成最小生成树的函数。具体实现过程如下：
（1）原始图的初始化函数：从前端接受顶点个数、原始图的邻接矩阵，并把最小生成树的邻接矩阵和原始图的邻接矩阵中无权值的位置都赋为-1，把各顶点的连通分量设为各不相同。
（2）把图转化成最小生成树的函数流程如图2所示。
2.读写文件
为了达到算法演示直观动态的效果，需要给出算法的动态演示环境。但由于系统运行时脱离算法程序的调试环境，需在连续运行时把运行过程每一步的结果写入文件，在单步运行和设置断点时从文件中把每一步结果一条条地读出，然后给学生。在这一过程中，就要频繁地读写文件。常用读写文件的函数如下：
（1）fopen：打开一个文件，以一个文件指针名称代表此文件，设置此文件属性并在主存储器规划一个缓冲区来暂时存放数据。其语法说明如下：FILE *fopen（const char *filename，const *mode）；即以一个指定属性打开文件。
（2）flose：关闭此文件，并释放所用缓冲区。其语法说明如下：int fclose（FILE *stream）；即将文件指针所对应的数据文件关闭。
（3）fprintf：以格式化将数据写于文件中，只能用于循环文件。其语法说明如下：Intfprintf（FILE*stream，const char * format[，argument，…]）。
（4）fscanf：以格式化将文件中数据读取，并存于变量中，只能用于循环文件，其语法说明如下： Int fscanf（FILE *stream，const char *format[，address，…]）。
在本系统中主要使用以下两条写语句：①fprintf（order，“%d”，flag）；②fprintf（data1，“%d…”，flag，…）；其中order文件存储源程序编号，data文件存储order文件中每一个编号对应的一行源程序中的变量及其值，flag表示每一行源程序的编号。
3.单步运行和设置断点
为了让学生更加清晰地认识程序的执行过程和最小生成树是怎样从原始图中一步步获得的，本系统除了能够连续运行外，还设置了单步运行，在单步运行时，程序执行到哪一步，相应的源代码就被亮条覆盖，以示区别，同时与本条代码相关的变量也被显示出来了。这里需要再次强调的是，单步运行时并不是程序真的在一步步执行，亮条覆盖的语句也不是正在执行的语句。算法程序脱离了程序的调试环境，不能够真正实现这些功能，真正执行程序是在连续运行时，单步执行只不过是把连续运行时写入文件的执行结果以单步的形式显示给学生，以达到更直观明了的目的。为了实现这个功能，需要在连续运行时写两个文件order和文件data1，order中只写入源程序每一条语句的编号，从零开始；文件data1写入order文件中的每一个编号对应的一行源程序变量及其值。单步运行时，首先从order文件中读出源程序的标号，同时到data1文件中读出此标号对应的变量和它的值，判断如果没有到文件尾，把标号对应的一行程序加亮条显示，同时显示相应的变量和它的值。
如果学生想看到程序从开始到某一固定位置的单步运行过程，就需要设置断点，设置断点时，首先应让系统记住要执行到的位置，点击源程序中的任意条语句，系统就会把这个位置记下，用一条语句（x=listbox->itemindex）即可，以后就用x控制程序的执行，直到完成，这里所用到的技术同单步运行时基本相同。
● 结论
本系统借助MySQL4.0数据库，运用Borland C Builder 6.0这种编程工具开发，并在Windows 2000 server环境下调试成功。