创新数据结构实验教学的思考与探索

摘要：该文通过选择几个典型的实验教学问题，探讨了如何进行数据结构实验教学内容创新的思路和方法，对于启发学生的学习兴趣，培养学生的实践动手能力，开拓学生的创新思维，提高实验教学的质量和效果，提供了有益的借鉴。

关键词：实验教学；创新；案例教学

中图分类号：TP3 文献标识码：A 文章编号：1009-3044（2013）19-4481-04

1 概述

数据结构是一门实践性很强的理论课，它的教学要求是：学会分析研究计算机加工的上海建工的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其响应的算法，并初步掌握算法的时间分析和空间分析的技术。同时，课程的学习过程也是复杂程序设计的训练过程，进一步提高学生的程序设计能力并培养数据抽象能力[1-4]。

数据结构课程的特点是既抽象、晦涩、看不见摸不着，同时又非常真实具体、客观存在于计算机的存储空间。如何通过合理设置课程实验内容，将抽象的逻辑概念与真实的存储状态直接关联，把课程中的前后章节的知识和技术相结合，并在课程中引入一些新的思想、知识和技术，拓展学生的形象思维和逻辑思维的能力，开拓学生的视野，激发学生的学习兴趣，增强学生的学习信心，提高教学效果，值得思考和探索。

该文拟就数据结构实验教学环节的一些典型问题进行研讨。

2 几个典型的实例

案例1：线性表的顺序映像和非顺序映像

线性表的实验作为数据结构课程实验的入门环节，实验内容的设置和选择，对于整个课程实验的教学至关重要。如何尽快培育和提高学生的信心和学习兴趣，需要精心组织和设计。一个有效的途径是，通过具体的实验过程，让学生看到线性表的顺序映像和非顺序映像在计算机存储器中的真实状态，以加深对这两个逻辑概念的理解，启发学生应用形象思维的能力。

具体方法：在实现顺序表和单链表的创建、插入和删除操作的过程中，通过同时输出数据元素的值和存储地址的方式，把数据元素在计算机中的真实存储状态及其变化呈现出来。

实例讨论：以下列线性表的创建、插入、删除和查找过程为例。

由图1可知，在顺序表结构中，数据元素连续存放在一组地址连续的存储空间，每个元素的存储位置与其序号直接关联，一旦进行了插入或删除操作，使得某个数据元素的序号发生改变，则其对应在线性表中的存储地址同步改变；而在图2中，单链表结构下数据元素的存储是任意的，并且单链表一旦建立，其每个结点的存储位置不再改变，不会因为结点的插入或删除而发生变化。

通过这样的实验训练，可以让学生看到线性表的不同存储结构在计算机存储器中的真实情况及其变化过程，从而很快进入正常的学习状态，消除畏难情绪，提高学习的积极性和主动性。

案例2：二叉树中各种类型结点的统计

二叉树的遍历是整个二叉树实验的基础，为了加深的二叉树存储状态的理解，在实现对二叉树进行先序、中序和后序遍历的递归和非递归算法及层序遍历的基础上，适当扩展实验内容，设置对二叉树中结点总数、叶子结点、单分支结点或双分支结点进行统计的实验内容，开拓学生的解题思路，培养学生的程序设计能力。

具体方法：通过归纳各种结点数计算的递推公式，直接进行递归算法的设计；也可借鉴二叉树遍历的各种算法，在进行结点遍历的过程中，通过对当前所访问的结点类型的判别，进行分类统计，实现实验的目的。

实例讨论：以二叉树结点总数的求解算法为例。

以下列出了两个具体的算法。分别描述了通过递推公式设计对应的递归算法，和利用中序非递归遍历算法进行修改实现对二叉树结点总数统计的算法代码。

算法1 利用递推公式转换的递归算法计算二叉树中的结点总数

int nodes（BiTree t） {/*利用递推公式计算二叉树的结点总数*/

int count1，count2；

if （t==NULL） return 0；/*树空*/

else

if （tlchild==NULL&&trchild==NULL） /*左子树、右子树不存在*/

return 1；

else {

count1=nodes（tlchild）；/*左子树结点数*/

count2=nodes（trchild）；/*右子树结点数*/

return count1+count2+1；/*返回结点总数*/

}

}

算法2 利用改写的二叉树中序遍历非递归算法计算二叉树中的结点总数

int nodes_inorder_n（BiTree p）{ /*利用中序遍历非递归算法统计二叉树的结点总数*/

BiTree q，stack[MAX]；int count=0；

int top=0； q=p；

do{

while（q）{ stack[top++]=q；q=qlchild；}

if（top>0）{

q=stack[—top]；

printf（"%c"，qdata）；count++； /*访问结点时统计个数*/

q=qrchild；}

}while（q||top>0）；

return count；

}

算法3 利用改写的二叉树先序遍历递归算法计算二叉树中的结点总数

void nodes（BiTree p）{ /*利用先序遍历递归算法改写的统计二叉树的结点总数*/

if （ p！= NULL ） {

printf（"%c"， pdata）；count++；

nodes（ plchild ） ；

nodes（ prchild） ；

}

}

通过上述各种算法的设计实践，可以开拓学生进行算法设计的思维，提高学生的分析问题和解决问题的能力和水平。

案例3：图的拓扑排序的算法设计

在各种教材关于图的拓扑排序的论述中，大都采用借助栈结构作为辅助工具进行零入度顶点的收集和控制，从而实现算法设计。对此，不妨换一个思路，队列是否同样可以实现实现这个目的？

具体方法：在进行拓扑排序的实验时，可以同时要求学生分别使用栈或队列来完成算法设计。进行这样的处理，一方面对算法设计的内容作了有益的补充，同时也将课程中前后的知识有机联系在一起。

实例讨论：以下列有向图的拓扑排序过程为例。

图3和图4分别给出了使用顺序栈和顺序队列的拓扑排序结果。由于栈和队列的特点不同，因此，对于同一个有向图，使用同样的存储结构，因为在进行零入度顶点的收集和控制顺序不同，最终得到了完全不同的两个拓扑有序序列。

案例4：非等概率查找问题

在国内许多的数据结构课程教材中，查找技术的介绍很少涉及非等概率算法的具体内容[1-4]，即使是国外的优秀教材中，也只介绍了一些基本思想和原理[5]。实际工程应用领域有关信息检索的应用系统中，大多采用非等概率查找技术来实现信息的快速查询。因此，可以通过在查找算法设计的实验环节引入非等概率查找的内容，以开拓学生的视野。

具体方法是：补充有关自组织线性表的知识和原理，并通过相应的算法设计实验，观察和分析非等概率查找的性能、特点和效率。

实例讨论：标准的顺序查找和采用自组织线性表的动态查找。

图5给出了采用标准的顺序查找算法和采用自组织线性表的查找算法，在一个包含25个记录的查找表中对应同一组查找序列进行500查找后的查找表终态。在查找序列中，每5个记录为一组，按照80/20规则设置，包含4个频繁查找项和一个非频繁查找项；图5中每三行表示一种查找算法的结果，其中第一行no为累计查找次数，k为本次查找进行的关键词的比较次数，compare1为累计比较次数；第二行的第一个元素为当前查找的元素，此后为经过本次查找后的查找表状态；第三行的第一个元素表示第几次查找，此后的数据为对应上一行的各个记录的累计查找次数。第1-3行是标准的顺序查找，第4-6行是采用计数策略的自组织线性表，第7-9行是采用移至前端策略的自组织线性表，第10-12行是采用转置策略的自组织线性表的最终结果。

由图5可知，采用自组织线性表动态调整查找表中元素的顺序，可以大大减少总的查找过程中进行的记录的累计比较次数，实现快速查找的目的。

案例5：内部排序的算法设计

通常，有关内部排序的算法设计按照插入类、交换类、选择类、归并和基数排序五大类进行系统介绍，一般大都采用线性表的存储结构进行讨论。也可以思考一下，有没有其它的方法，例如利用二叉链表的存储结构，基于二叉排序树或平衡二叉树的构造方法进行排序？

具体方法：通过构造二叉排序树或平衡二叉树的过程实现排序。二叉排序树或平衡二叉树的特点是，中序遍历一棵二叉排序树或平衡二叉树，可以得到一个按关键词递增排列的有序序列。

实例讨论：利用平衡二叉树构造的算法对一组记录进行排序，算法代码略。

由图6可知，对于给定的一组记录，通过给定的次序逐个插入到一棵平衡二叉树中，并且每当由于一个新纪录导致平衡二叉树失去平衡，则通过相应的平衡化处理策略恢复平衡；待整个记录序列全部插入完毕，只需进行一次中序遍历，即可得到最终的排序结果。

由于在一棵平衡二叉树中插入一个新结点需要进行的比较次数不超过该树的深度，而平衡二叉树的深度与对应的完全二叉树的深度相同，因此，这种排序方法的时间复杂度同样是O（nlogn），并且可以通过增加插入值相同的新结点的约定来保证其稳定性。

3 结束语

本文讨论了在数据结构实验教学环节进行实验内容改革和创新的若干典型案例，通过这些实验案例的设置和实施，必将大大提高课程实验教学的质量和效果，激发学生的学习主动性和学习兴趣，强化理论与实践的结合与联系，开拓学生的解题思路，培养发散思维和创新意识，从而整体提升课程教学的质量。

参考文献：

[1] 严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2011.11.

[2] 邹永林，周蓓等.数据结构与算法教程[M].北京：机械工业出版社，2004.9.

[3] 马睿，孙丽云.数据结构（C语言版）[M].北京：北京邮电大学出版社，2009.8.

[4] 周桂红.数据结构[M].北京：北京邮电大学出版社，2010.9.

[5] Clifford A.Shaffer：A Practical Intruduction to DATA STRUCTURES AND ALGORITHM ANALYSIS[M].Prentice-Hall Inc.，1997.