基于的数据结构课程实验教学改革

基于STL的数据结构课程实验教学改革

柳　林^[1]

（浙江工商大学信息与电子工程学院）

摘　要：数据结构是目前许多理工类专业的必修课或限制性选修课，在计算机、电子信息、通信类等专业课程中占有很重要的地位，在教学中应多采用程序设计的新技术、新概念，以尽量提高学生对课程的理解和掌握。本文重点讨论了如何把新兴的STL程序设计技术应用于数据结构课程的实验教学，以缩小课堂教学和实际应用的距离，提高学生的动手能力。

关键词：数据结构；STL；实验教学

一、引　言

当前计算机已深入到人类社会的各个领域，其应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。数据结构正是一门研究非数值计算的程序设计问题中计算机的操作、操作对象及其相互关系的学科，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课或必修课。数据结构作为一门独立的课程，在国外从1968年便开始设立，但数据结构的发展从未终结。一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来讨论数据结构，已成为一种新的趋势，越来越被人们所重视。因此，对数据结构进行教学研究，及时更新课程内容和教学方法，对高校的计算机教学有着深远的意义。

二、实验教学中存在的问题

数据结构作为计算机方向的核心课程之一，涉及很多的实践环节，需要程序设计语言作为其先修课程。现在国内大专院校的计算机类专业或者电子类理工科专业，大部分把C语言作为程序设计语言进行教学，小部分把C＋＋语言作为程序设计语言进行教学。C语言由于其面向过程的特征，不适合于写复杂的程序，其代码重用性比较差，对算法和数据结构的支持也比较差，这样导致在数据结构的教学实践中，学生需要花很多的时间去琢磨怎么用C语言来实现那些复杂的数据结构，导致无法很好地掌握数据结构本身的内容。笔者在教学实践中发觉，由于数据结构课程逻辑性强，学生课本知识掌握得比较好，但是学生在实验课上普遍表现不佳，对于稍微复杂一点的数据结构程序，就无法在三节课的时间内完成，即使有些比较认真的同学在课前进行比较认真的准备，事先写好了部分程序，但是由于他们的程序设计水平不能达到撰写逻辑复杂程序的水平，致使在后面的几章（如树、图）教学中，普遍不能很好地完成实验教学任务。数据结构课程的这种教学现状对于学生来说极为不利，主要表现在以下几个方面：

一是不利于提高学生的学习兴趣。数据结构课程本身抽象性较强，对于逻辑思维有所欠缺的同学来说，不容易掌握，如果实验教学比理论教学更难，就不容易引起他们对课程本身的兴趣，甚至使得他们视数据结构为畏途。

二是不利于掌握课程本身内容。如果没有实验对课程教学内容的验证，学生掌握的知识也只是停留在理论本身，无法扎实掌握课程知识。

三是不利于对理论知识的灵活应用。数据结构课程中所学的知识在实际的编程实践中占有非常重要的地位，能够灵活地应用这些数据结构，本身就是一个程序员水平和能力的体现。如果在学习中没有实际用过这些知识，更谈不上今后的灵活运用。

四是不利于后续课程的学习。数据结构的教学内容在后续的课程中占有很重要的地位，如在操作系统课程中，进程的调度是采用各种队列来实现的，而文件的存储是采用红黑树来实现的；而在数据库课程中，各种数据的排序也用到数据结构的排序算法，而索引和关键字的查找用到了Hash查找、树查找等各种查找算法。如果没有很好地掌握数据结构课程，对后续课程也无法得到全面的理解。

现有数据结构课程实验教学大都是以C语言作为基础的，以本校为例，是以高等教育出版社出版的耿国华教授主编的《数据结构——C语言描述》作为教材的。教材中的理论部分大多数同学都能掌握，但是对于教材中的实习题，大部分同学都不能按时完成。究其原因，主要有以下几个方面原因：

一是C语言程序设计没有学好。虽然C语言有4个小时的教学时间，但是由于大部分同学在此之前都没有接触过程序设计，所以在一个学期之内还是不能灵活地掌握C语言。

二是数据结构实习程序的复杂性。在C语言教学中，重点是讲述C语言的语法，所设计的程序以数值计算为主，没有涉及复杂的数据结构和逻辑结构；而数据结构中所要设计的程序，大都是以非数值计算为主，并且树、图等数据结构的逻辑一般都较为复杂。这种程序难度上实质性的差距，就导致大多数同学不能很好地写好数据结构的程序。

三是上机实习时间有限。由于培养成本限制，大部分非计算机专业本科生的数据结构都只有3个学分，总共45—48个学时的教学时间，由于理论教学要占据大部分时间，分配到实验教学的时间大都只有4—5次，也即12—15个学时。在有限的时间内，学生面对着复杂的程序，大部分时间内都在输入程序、查找编译错误，根本没有时间来灵活运用所学的知识来做一些复杂的应用。

三、利用STL的实验教学改革

综上所述，当前有必要对数据结构课程的教学进行必要的改革。最自然的方法是改变先修课程，改C语言为C＋＋语言，这样从C＋＋基础进行数据结构教学，可以利用C＋＋语言的结构化特征，利用重用的类来降低数据结构的实验教学的难度，提高实验教学的质量。这种方法对于计算机专业本科生来说是可行的，而且有不少高校已经在进行尝试，但是非计算机专业学生由于培养目的不一样，教学课时有限，用C＋＋取代C语言的教学方案并不现实。另一种方案是改变实验教学方法，添加新的实验手段，减少实验教学的难度，增加学生的学习兴趣，本文提出了一种基于STL的实验改革方法，可以有效地解决这些问题。

STL（Standard Template Library）是标准模板库的缩写，是利用泛型技术开发的一系列软件的总称。STL是由Alexander Stepanov和Meng Lee等人设计的，并于1994年被列入C＋＋标准库之一。同年还发布了作为STL示范的“HP（惠普）实现”。当STL刚成为C＋＋标准的组成部分时，C＋＋委员会立即承认它为一个高质量、高效率的容器类库。STL涵盖了计算机科学中的许多基本算法和数据结构，并且具有跨平台的特点。STL将算法和数据结构完全分离，互不耦合。STL库主要由算法（algorithm）、容器（container）和迭代器（iterator）构成。容器实质上是数据集合，可能是数组、栈、队列、双向列表或二叉树等。迭代器是一种特殊的指针，算法通过迭代器在容器中遍历，实施查找或进行其他数据操作。由于算法和数据结构的完全分离，原先M种算法结合N种数据结构的复杂度为O（M×N），而由于运用了泛型编程思想，理想条件下复杂度降为O（M＋N）。简而言之，STL就是一个以泛型技术完成的程序库，具有容易使用和容易学习的特点。

STL技术应用于数据结构的实验教学，有其天然的优势，首先，STL库中具有数据结构课程中所需要的大多数数据结构，如栈、队列、树等基本的数据结构在STL库中找到对应的类，这些类的使用极为方便，很容易就能利用它们构造一些基本的数据结构程序，而不用细究这些程序的细节；其次，STL库也能找到数据结构中的排序和查找算法，利用简单的一些语句，就可以得到算法的运行结果；再次，由于STL库是经过反复测试过的函数库，其正确性和完整性都得到了详细的测试和论证，只要符合使用规范，用户使用中不用担心不能得到正确的结果；最后，STL已经得到了基本上所有编译器的支持，在现有的所有主流编译器中都不存在兼容性问题。

由于STL技术极为庞杂，完全掌握STL技术对于本科生低年级同学来说不现实，而且没有必要，但是掌握STL技术中一些基本的容器类和算法，并不是很难的事情，只要在数据结构中对学生稍加点拨，多加提供例题，并提供详细的使用方法和实例，学生必能很快掌握利用STL技术进行数据结构实验。详细方案：

1．在教学内容的安排上，仍按照传统的教学方法对不同的数据结构及其相关的算法进行介绍和讲解。在学习了面向对象程序设计和STL程序设计的一般概念之后，强调学生上机的实际动手能力。在上机实践中，首先老师给出一些泛型程序设计的范例，要求学生尽可能采用STL，用VC来实现线性表、堆栈、队列、树、图等常用数据结构的相关算法，并在每章学习结束之后，挑选几个设计较好的同学的成果进行讲解，并拷贝给每一个同学。

2．针对具体的教学内容，安排学生尽量采用STL来实现，而不是采用传统的C语言的方法来实现。例如用STL的Stack类来实现寻找迷宫的出口，利用STL的deque类来实现图的遍历算法，等等。要求学生尽量学会使用STL来解决复杂的问题，而不是拘泥于具体的编程细节。

3．针对具体的问题，教师应当尽量准备详细的帮助文档，以帮助学生避开一些STL的细节问题，如对迭代器的使用，对泛型的实现方法等等，都应当尽量简化，只挑与课程相关的内容来讲，这样可以使学生尽快上手。

参考文献

［1］侯捷．STL源码剖析［M］．武汉：华中科技大学出版社，2002．

［2］斯特劳施特鲁普．C＋＋程序设计语言（特别版，影印版）［M］．北京：高等教育出版社，2001．

［3］张沙清．面向对象系统开发中的泛化与泛型分析［J］．桂林工学院学报，2003，23（4）：390—393．

［4］马林兵，张新长，伍少坤．泛型程序设计技术在传统数据结构教学中的应用［J］．教育与现代化，2006，78（1）：18—21．

【注释】

[1]柳林，副教授，博士，研究方向为图像处理、视频编码。