非重点院校的数据结构课程教学改革.doc

非重点院校的数据结构课程教学改革 程裕强，周国军，吴庆军，张茂胜 （玉林师范学院数学与信息科学学院，广西玉林537000） 摘要：提出在主流数据结构教材基础上进行课程改革，包括降低课程难度、充实核心章节、精简次要部分、引入面向对象思想描述抽象数据模型、增加4类习题和上机任务等。 关键词：数据结构；抽象数据类型；教学改革 基金项目：xx年广西高等教育教学改革工程项目（一般项目A类）“移动互联网背景下信息与计算科学专业应用型人才培养模式的研究与实践”（xxJGA207）。 第一作者简介：程裕强，男，讲师，研究方向为中文信息处理、本体论、语义网，chegnyuqiangqq.。 0引言 人类解决问题有三种途径，一是理论分析，二是计算（也称算法），三是实验。数据结构课程属于第二种计算范畴。数据结构的学习有利于培养学生的模型抽象能力和算法设计能力以及创新性思维。现在越来越多的专业开始将数据结构课程设置为核心专业课程，数学类、经管类等专业也设置数据结构为选修课。数据结构是数据库、操作系统、计算机网络等课程的先修课程，数据结构课程的学习效果对后继课程有着重要的影响。 1数据结构教学中存在的问题 与其他专业课程不同，国内高校选择的数据结构课程教材相对单一，主要是1997年严蔚敏和吴伟民主编的数据结构（C语言版）1。该教材的最大优点是数据结构描述较为全面、言简意赅，适合学习能力较强的985和211等重点高校相关专业的学生使用。对于非重点本科高校以及高职高专的学生而言，该教材具有一定难度，存在如下问题：该教材使用类C来描述数据结构，使用了部分C+特性，而大部分非重点高校的学生在学习数据结构之前没有学习过C+语言，让他们将类C描述的数据结构转换为具体的C语言代码时具有一定难度。C语言在描述数据结构时表述不方便。由于C+语法较为复杂，如果引入C+相关语法，又会大大增加数据结构课程的教学难度。该教材于1997年编写，至今已过去将近20年，有些章节没有更新过。该教材每章结束处缺少习题，虽然编者提供了另一本配套的习题参考书2，但在实际中需要重新购买，且该习题参考书所设计的习题难度较大，不适合非重点院校使用。 2数据结构教学改革措施 2.1使用纯C语言描述，降低难度 1）删除&参数传递。 在描述数据结构操作算法时，可能需要实现参数双向传递。教学实践中，我们将C+的&参数全部转换为C语言的指针操作，虽然增加了算法表达的复杂性，但是在算法具体实现时带来了极大方便。 2）减少复杂的动态内存分配操作。 在构建数据结构时，不宜面面俱到，应做到主次分明，重点分析问题的核心流程，次要问题的处理点到为止即可，不需作深入描述。比如对于数据存储结构中关于存储空间扩展问题，在数据结构设计中可以简单说明或者注释一下，不宜使用大量代码来处理这个问题，容易造成代码结构复杂，主次混乱，增加学生理解的难度。例如，严蔚敏主编的数据结构教材出现最多的顺序存储结构的代码如下： 这种结构对于数据结构的初始化操作和添加新元素的操作带来了复杂性，虽然考虑问题周全，但是算法语句的主次情况不清晰，可读性差，算法逻辑结构复杂。比如对于添加新元素的操作算法，需要考虑“当前存储空间已满，增加空间”的问题，在算法中需要增加如下代码： 可以使用数组来描述顺序存储结构，这样做的好处有两个：一是大部分二本院校的学生C语言基础不扎实，特别是对于指针操作，采用数组可以减少指针的使用，降低数据结构表述的难度；二是数组描述的顺序存储结构不会改变相关操作算法的本质。比如对于栈使用顺序存储结构描述时，简化后的代码如下： 其他代码省略。对于栈满情况，只是简单判定，没有进行存储空间扩展操作，这样对于进栈操作push()的核心流程更加清晰。 3）删除指针函数。 在数据结构设计中，较多涉及数据元素的比较问题，而对于不同类型元素的值比较，C语言没有通用的函数。严蔚敏主编教材中引用函数指针来解决这个问题，对指针函数，学生大多望而生畏。可以在教学中暂时删去指针函数，不会改变算法设计的本质。 4）统一数组下标。 与C语言保持一致，数据结构中涉及数组，其下标统一从0开始。 2.2引入面向对象思想描述数据结构 数据结构课程的主要任务是培养学生对模型的抽象能力，可是C语言在数据模型抽象时存在先天不足。在实际教学中，甚至出现学生编写的数据结构代码不能运行的情况，因为学生没有理解数据结构的本质，没有明白数据结构代码实现是对某一数据模型的实现，不知道对该数据模型的测试需要再提供一个主函数。 面向对象语言具有较强的数据模型抽象能力，但是数据结构课程开设时学生还没有学习面向对象语言，这也是国内数据结构教学主要使用C语言或类C的原因。我们提出使用面向对象思想来描述抽象数据类型ADT，在算法具体描述时使用纯C语言，最后在数据结构实现时提供纯C语言版和Java语言版3。两种不同语言实现的数据结构，通过纯C语言版代码可以方便阅读Java语言版代码，反过来通过阅读Java语言版代码又可以加深对纯C语言版代码的理解。 我们以顺序存储结构的栈为例来说明，首先从抽象数据类型角度来看待数据结构Stack。 抽象数据类型的描述以及面向过程语言和面向对象语言实现对比，可以让学生更好地从抽象数据类型角度来思考数据结构。 2.3删除次要章节，充实核心章节 首先，增加“预备知识”一章，复习C语言的主要语法，补充Java语言的简单语法部分（不涉及Java语言高级特性）。对于非重点院校来说，部分学生的C语言基础不扎实，需要复习一下C语言的核心语法。由于采用面向对象思想来描述抽象数据类型，需要引入简单的面向对象语法。而C+语言本身语法较为复杂，没有C+语言基础的学生难以看懂C+描述的数据结构算法，Java语言在C+语言基础上进行了简化，在C语言的基础上，学生只需了解简单的Java语言即可掌握使用Java语言来描述数据结构4。Java语言最大的特点是有完善的描述抽象数据类型的类定义机制5。 其次，对于栈与队列一章，栈与队列是一类特殊的线性结构，重点不是链式结构而是顺序存储结构，补充共享栈和两类循环队列以及递归机制的描述。 第三，对于串一章，使用合并定长与堆两种描述的优点，统一使用数组存储结构描述。 第四，简化数组与广义表一章，删去m元多项式与广义表相关内容。 第五，简化哈夫曼树问题和最短路径问题等非线性结构的描述。哈夫曼树算法较为复杂，如果引入堆结构进行描述，可以降低其算法难度。对于多源点最短路径，可以增加矩阵计算过程来降低算法理解的难度。 第六，充实快速排序相关内容。快速排序以及改进方案是IT企业面试中最常问到的问题，这部分内容需要充实。 第七，删去动态存储管理和文件两章内容。 2.4增加习题与上机任务 单独提供与数据结构教材配套的习题集和上机指导参考书，虽然可以有足够的空间来展现丰富的习题和详细的上机指导，但是独立的参考书使用不方便。我们提出在数据结构教材中适当添加具有阶梯难度的习题和上机任务。 1）增加习题。 在每章内容结束时，增加相关习题，习题内容需要涵盖基础概念题、全国二级等级考试题、经典考研试题和企业面试题。每章习题平均为10道，对于不同章节可以适度调整，比如关于树与图两章，相关内容较多，可以增加题目数；关于排序一章，企业面试题较多。总体习题设置见表1。 2）上机任务。 由于教材版面限制，每一章提供两道精选的上机任务。比如对于栈，设计一道上机任务：编码实现抽象数据类型栈Stack，并利用Stack求解一个整数的2进制形式。该上机任务包含了栈Stack基本概念与编码实现，进而进行简单应用。上机指导教师可以根据所在院校上机报告具体形式和实际的教学效果进行指导。 3结语 多年的数据结构教学实践表明，我们提出的数据结构课程改革方案，对于非重点院校来说是急需的、可行的。新的教学方案一方面降低了课程教学难度，方便学生自学，提高了学生的学习兴趣；另一方面增强了前后课程的联系，特别是C语言、数据结构和面向对象程序设计语言。下一步工作是总结教学经验，编写适合广大非重点二本院校以及高职高专院校的数据结构教材。 参考文献： 1严蔚敏,吴伟民.数据结构（C语言版）M.北京:清华大学出版社,1997. 2严蔚敏,吴