数据结构描述的是数据之间的关系。C++数据结构的存储方式有顺序、链接、索引、散列等形式,对数据的处理通常包括输入、输出、查找、更新、排序、插入、删除等,当数据的存储方式不同时,相应的处理实现算法也不尽相同。
如何采用一种简便明了的方法分析C++的数据结构特点及各种存储方式、处理方式之间的异同成为了计算机应用专业教育的一个难点。针对远程开放教学学生大多数通过网络课件自学这一特点,采用当今流行的跨平台程序设计语言java实现对C++数据结构算法的模拟,可以很好地解决对数据存储方式、处理方式的具体化问题。利用java语言程序设计的灵活性及交互性,实现数据的动态输入,自动、分步、循环执行存储处理过程,并在internet上发布。
1、实现的功能
使用Java技术编写的Java applet 程序,在网页上发布,可以方便与用户交互,用户可以初始化算法元素,可以选择执行方式(自动执行或单步执行);可以起止程序的执行;显示当前程序运行的状态;同步显示算法描述与算法过程的变化。这里我们以直接选择排序(升序)为例子,来分析采用Java技术实现算法的摸拟演示。效果图:
说明:"直接排序数据",文本框用来接收用户输入的数据。"排序数据个数",显示用户输入的数据数。"当前最小值",当前程序执行时的最小值。"运行状态",显示当前程序运行状态。"确定输入",接收用户的输入。"自动执行",根据用户的输入自动进行排序演示。"单步执行",根据用户的输入,用户可以手动控制程序的执行过程。"结束演示",结束演示,等待下一次演示。"列表框",在程序执行过程中与图形变化同步显示相对应的算法描述。
2、分析算法并将其转化为图形符号
直接选择排序的基本思想是:每一趟 (例如第 i 趟,i = 0, 1, …, n-2) 在后面 n-i 个待排序对象中选出要害码最小的对象, 作为有序对象序列的第 i 个对象。待到第 n-2 趟作完,待排序对象只剩下1个,就不用再选了。
它的基本步骤是:在一组对象v[i]~v[n-1]中选择具有最小要害码的对象;若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调; 在这组对象中剔除这个具有最小要害码的对象,在剩下的对象v[i+1]~v[n-1]中重复执行前两步,直到剩余对象只有一个为止。
下面将用一系列的图形符号表示出该算法的执行过程。假设将对
36 25 48 12 65 43 20 58
这一组数据进行直接排序
向上箭头前面为已排好序的数据,为一有序表;向上箭头后面的数据为待排序区间,是一无序表;双向向下箭头表示两数据交换。根据对排序过程分析,可以用下面图形符号表示算法中的元素:
其中,向下箭头表示当前正在排序区间内查找的元素,向上箭头为当前排序区间的开始位置。
3、输入输出处理的实现
为了增强模拟程序的交互性,在程序中将引入元素的用户输入、程序执行过程中算法描述同步执行、程序运行状态的显示。在程序界面上定义一个单行文本框来让用户输入元素,并将定义初始元素(定义可以放在init()中):
TextField edit1;
edit1 = new TextField(22);
add(edit1);
edit1.setText("36 25 48 12 65 43 20 58");
在程序中定义StreamTokenizer类和array[]数组来接收用户输入的数据。 StreamTokenizer即令牌化输入流的作用是将一个输入流变成令牌流。这里使用的是StreamTokenizer.TT_NUMBER: 表示读到的令牌是数字,数字的值是double型,可以从实例变量nval中读取。
StringTokenizer stringt = new StringTokenizer(edit1.getText());
array = new int[stringt.countTokens() + 1];//定义数组
for(int i = 1; stringt.hasMoreTokens(); i++)//数组赋值
array[i] =Integer.valueOf(stringt.nextToken()).intValue();