刘 志，赵明珠，刘端阳
(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)
摘 要：针对当前数据结构课程存在“听得懂，不会做”的问题，分析其原因，提出面向编程能力培养的数据结构课程教学观点，即通过以存储结构为基石深入理解数据结构，在此基础上通过应用实践提升面向对象编程能力，进而解决数据结构课程“不会做”的问题。
教育期刊网 http://www.jyqkw.com
关键词 ：存储结构；面向对象编程技术；STL
0 引 言
数据结构是计算机专业的一门核心基础课程，不仅是进行高效程序设计、软件系统开发的重要基石，而且是计算机专业后续课程（如操作系统、数据库系统等）的重要前导课程，学好数据结构无疑对计算机专业的学生具有非常重要的意义。由于数据结构课程主要是研究数据在计算机中的存储、组织和访问方法，不可避免地涉及数据在内存中存储空间的申请、管理和释放等问题，正是由于数据在底层内存空间的不同存储方法，才导致了数据多种多样的访问方法；由于各种数据结构具有不同的逻辑结构，因而这些数据的访问时间也存在很大不同，通过算法复杂性分析可明确地揭示这些算法间的异同[1]。
1 教学中存在的问题
目前，教学中普遍存在如下问题。
（1）学生由于前期的C++编程能力薄弱，对面向对象的编程技术没有很好理解，而数据结构又主要以抽象数据类型进行描述和实现，体现在数据结构课程上就是眼高手低，能理解各种数据结构类的设计和实现方法，但没有能力自己构造和实现，进而导致很多作业、实验无法上手，越学越难。
（2）作为计算机专业的学生却没有真正意识到编程能力的重要性，计算机专业区别其他专业的一个很大特色就是强调实践动手能力。作为计算机专业，编程能力是最基本的专业技能，而提升编程能力的唯一有效途径就是上机实践，只有通过独立完成代码的编写、调试，才能真正掌握程序设计语言，提高问题求解能力、编程能力、调试和测试能力。数据结构课程不仅仅是理论的学习，更是理论的实践和应用，若学生不能投入地进行数据结构课程的编程实践，是很难学好这门课程的[2]。
（3）数据结构课程的理论教学内容已经非常完善了，而面向编程实现的教学内容是相对不充分的，我们在实际的教学过程中，在兼顾理论教学的基础上，通过介绍数据结构在STL中的实现，引导学生使用STL中的各种模板类，进而提升学生应用数据结构方法解决实际问题的能力。
2 编程能力培养的探索
2.1 以存储结构为基石理解数据结构
目前，数据结构教材基本都是以数据的逻辑结构为主线，从线性结构开始，依次介绍动态数组、链表、线性表、栈、队列，然后是非线性结构，包括树形结构和图形结构。在各种数据结构介绍时再讨论其存储结构以及相关算法，知识框架体系完善清晰[3]。我们的教学工作也是在这个框架下展开的。事实上，对于这样的知识脉络学生也是理解的，但在具体教学过程中，学生就陷入了混乱。刚刚进入大二的学生由于对计算机系统缺乏了解，对内存分配更是茫然无绪，老师们认为很自然的事（如数据在内存中的存储和分配过程），他们会很难理解，只能死记硬背，于是，在下一步的学习中，这些困惑会继续放大，最终使得学生产生畏难情绪，甚至有人放弃了这门课程。
针对这种情况，可以在教学过程中首先介绍计算机内存的基本管理方法，以图示说明计算机中内存的分布情况；再针对程序编译系统支持的标准数据类型和用户自定义、自行创建的数据类在内存中的分布，来解释数据结构在计算机内存中的存储和访问方法，这样，使得学生对后续各种数据结构的存储管理有了直观认识，解决了数据结构的存储瓶颈问题。
简单说，存储空间只有连续和不连续存储空间之分，但由于不少教材在实现数据结构时，还涉及连续空间中的数组结构和向量结构（动态数组），为了便于学生理解数据结构由于不同存储结构所带来的不同访问方法，我们将各种数据结构与存储方式整理归纳如表1所示。
由于数据结构中各种数据结构均以抽象数据类型来描述，即数据结构的逻辑结构以抽象数据类型描述，但不同的存储方法使得相应的操作方法实现不同，即成员方法的具体实现方法不同。如果能够理清这样的数据结构构造思路，那么所有的数据结构设计和实现方法就都很简单了。相对于具体的操作中，各种数据结构都可以先进行类声明，在私有数据中明确该数据结构的具体存储方法及相应的辅助变量，再针对各种常规访问方法进行实现，主要包括基本构造函数、头尾访问方法、插入和删除方法等。
2.2 通过构造特定数据结构，提升编程能力
在给出了基本数据结构的构造和实现方法后，可通过构造一些特定功能的数据结构来增强学生的分析、设计和实现能力。例如，可让学生利用数组和动态数组分别实现双端栈结构（即2个栈存储在同一个数据空间中）：①利用数组作为存储空间实现双端栈，是2个栈相向生长，数组的低端和高端分别作为2个栈的栈底，总的数据空间为2个栈共用，当所有空间被占满后，2个栈都满，否则，任意1个栈都可再压入元素，以便充分利用数据空间。②利用动态数组实现，不是简单利用vector实现，因为vector只是方便向后动态增长，这里使用deque（即STL中的双向队列），其实质是两端都可动态增长的动态数组，恰巧可以支持双向栈的实现，2个栈背向生长，即与双向队列的结构完全吻合，初始是2个栈均空，即双向队列为空；之后，1个栈向前生长，1个栈向后生长，对应于双向队列就是分别在头部和尾部插入元素。通过这个练习，可以让学生从分析、设计到实现全面实践，增强学生的C++编程能力。
类似的题目还有很多，包括让学生利用数组、向量、链表分别实现优先队列，也可以让学生自己动手来完成类的设计和实现。这样，既明确了各种数据结构的逻辑结构和具体实现方法，又可以在实现过程中，增强学生对面向对象技术的深入理解，更好地掌握C++程序设计方法，提升学生的编程能力。
2.3 利用STL中容器理解数据结构应用
数据结构课程主要研究各种基本数据的存储和组织方法以及相应的访问算法，但如何应用数据结构解决实际问题，也是数据结构课程重要的教学内容。在实际工作中，基本的数据结构类型都是封装好可以直接使用的，如STL中封装的各种容器，从工程化的角度讲，在项目开发中更应该基于软件复用的原理，采用高效的、封装好的代码进行项目开发，而软件复用正是提高软件生产力和质量的一种重要方法。所以，对于大多数将来从事应用系统开发的学生来讲，灵活地应用各种标准的数据结构就成为每个学生必不可少的技能。
为了使学生尽早熟悉STL规范，我们在授课过程中，各个数据结构类型的声明和实现都基于对C++STL源代码进行简化，让学生了解我们所讲授的数据结构设计和实现是最基本的实现方法，而STL中的各种数据结构则是考虑了系统效率之后的优化版本，这样，学生就能将所学的基本理论跟实际开发系统关联起来，避免了理论和实际的脱离。
同时，为了让学生深入理解STL的泛化编程，我们从一开始就基于模板进行教学，模板是泛化编程的基础。实际上，学生是很容易接受模板的概念，借助模板可以实现适用于不同数据类型的抽象算法编程，而这种抽象又恰恰是数据结构的设计和实现方法。因而，利用STL中的各种容器，学生可以灵活地应用各种数据结构来求解实际问题，这样的训练极大地加深了学生对数据结构课程的认识和理解，对提高学生的编程能力大有裨益。
2.4 通过大型实验提升问题求解能力
在数据结构课程中，除了理论教学和课内实验，我们还安排了独立的大型实验，以期通过综合性的题目，使学生能够全面、灵活地应用数据结构解决问题，同时，也对提升学生编程能力起到促进作用[4-5]。
我们设计了一道模拟系统登录的题目：用户在登录系统时，需验证用户名和密码，通过用户信息的合法性检查方可登录。为了快速查找和验证用户，以及支持新用户添加、老用户删除和用户密码更新等操作，要求系统采用动态二叉树结构实现，支持系统快速查找和更新。为了提高效率，建议学生建立AVL树，或者建立红黑树实现，为了增加题目的综合性，不可直接使用STL实现。
该题目侧重考查学生对二叉树的掌握情况，尤其是平衡二叉树，通过这样的训练，学生要完成整个系统的分析、设计、类的构造和实现、编程、调试，对学生的编程能力具有很大的促进作用。学生完成题目后，我们采用一对一的面试方式进行验收，学生不仅要介绍设计思路和实现技术，还有现场演示系统，并对系统进行边界测试以验证系统的正确性和健壮性。这样，可以很好地杜绝学生的抄袭问题，而且，通过学生的讲解，也可以快速了解学生的思路，评判其设计的优劣；对学生也是一个很好的促进，让他们有机会总结自己的设计思想，并准确地表达出来，通过演示系统，验证和证明自己的算法。在实际面试过程中，对自己系统信心满满的学生，也常会因为一些边界条件的测试导致系统崩溃，让他们大呼意想不到，现实的一幕也让他们大受教育，感慨编程百密仍有一疏，学无止境，进而也认识到软件测试的重要性。
通过这样的大型实验训练，学生不仅能深入理解和掌握这门课程，而且，通过实战练习，使得学生对面向对象编程技术的掌握有了全面的提升，极大地提高了学生的编程能力。
3 结 语
数据结构课程虽然理论性比较强，但是若结合应用开发，学生不仅能更深入地理解基本理论，而且，在实际应用中也能得心应手地利用数据结构来解决问题，尤其是对C++STL中容器的引入，为学生在今后的实际项目开发中提供了利器，使得学生眼界更开阔，在工程化的软件开发过程中，能够更好地利用软件构件来高效开发安全性更高的软件系统，这也是提高软件生产力的必由之路。因而，数据结构这门课程不仅是计算机专业的重要基础课，实际上，也是在软件开发过程中承上启下的课程，在强化了面向对象编程技术的同时也开启了软件构件复用的新历程，对培养学生的编程能力具有很重要的作用。
基金项目：浙江工业大学教改项目“以数据结构课程为主的多课程融合式教学模式的探索和研究”（JG1318）。
第一作者简介：刘志，女，教授，研究方向为图像处理、三维模型检索，lzhi@zjut.edu.cn。
教育期刊网 http://www.jyqkw.com
参考文献：
[1] 张铭， 耿国华， 陈卫卫， 等. 数据结构与算法课程教学实施方案[J]. 中国大学教学， 2011(3): 57-60.
[2] 徐慧， 周建美， 顾颀. 强化课堂编程思维 契合教学实践目标: 数据结构教学方法探析[J]. 高教论坛， 2013(1): 24-28.
[3] 张铭， 赵海燕， 王腾蛟， 等. 北京大学“数据结构与算法”教学设计[J]. 计算机教育， 2008(20): 5-11.
[4] 鹿旸. 数据结构与算法课程教学方法的思考[J]. 计算机教育， 2010(5): 88-90.
[5] 陈越， 何钦铭， 冯雁.“数据结构”综合性课程设计教学探索与实践[J]. 计算机教育， 2008(8): 54-55.
（编辑：郭田珍）
