数据结构课程案例式教学方法探讨＊

孙 悦，苏利敏，江 静

(北京联合大学智慧城市学院，北京 100101)

0 引言

数据结构课程既涉及硬件存储又涉及软件算法，对学生抽象思维及编程能力要求较高[1]。目前其教学方式以教师讲授为主，讲授内容为基本概念和基本算法，教师将大部分时间投入到内容的讲解中，而学生处于被动接收地位，其主动研究、探索的机会受到很大限制。而且数据结构这门课程教学上缺少实例，不能使学生融会贯通，当面对具体问题时，不知该如何运用学过的知识给出切实可行的解决方案。如何改善数据结构课程的教学效果，提高学生学习兴趣，是目前任课老师要迫切解决的问题。本文主要考虑学生编程能力的一般情况，转变传统的教学模式，对案例式教学方法展开探讨。

1 存在问题

1.1 学生基础薄弱

目前我校使用的数据结构课程教材以类C语言为描述工具，多数普通高校的学生，没有编程基础，大学一年级只修了C 语言程序设计这一门高级语言课程，由于教学计划等原因，C语言的课时安排往往不够用，通常只有48 学时理论，16 学时上机实验，多数学生学完后仅达到入门水平。另外，C 语言程序设计和数据结构这两门课程通常由不同任课教师担任，导致两门课程在教学内容上出现知识衔接的断层。数据结构课程对C语言中的结构体和指针等知识涉及较多，而这部分内容在C语言课程授课过程中由于学时有限，往往被一笔带过，学生对该部分内容无法熟练应用，例如当遇到大量的C语言伪代码时，学生就会觉得难懂，生出畏难情绪，给授课教师也带来重重困难。

1.2 学时设置

目前，大多数高校数据结构课程的上机实践学时短缺，学生实践机会偏少，教学是以利用伪代码描述数据结构和算法为主，以编程实践为辅，实践教学不能支撑起理论教学，上机实践过少，学生在理解算法时只停留在表面[2]。本校数据结构课程开设学时数为64 学时，其中理论48 学时，实验16 学时，另外设置课程设计1 周。如果依靠课内理论学时，是没有办法既讲解数据结构基本概念和算法，又讲解足够的案例，不得已需要借助课外学时及实践学时来弥补，而在学生主动性不够的情况下，需要老师做出合理的安排和引导，准备的完整案例程序来讲解，帮助学生尽快补足所缺知识。

2 各章案例选择

教师选择典型且难度适宜的案例，引导学生利用已有的知识背景，在实现案例的过程中发现问题、分析问题和解决问题。通过案例式教学紧紧围绕所学知识点，借助项目案例使理论和实践紧密结合，不但提高学生学习兴趣，帮助学生理解相关知识点，而且提高学生编程能力，培养学生解决实际问题能力，让学生在学完本课程后不仅仅是知道几种数据结构的特点，了解一些算法，而是能做到学以致用，解决问题。

2.1 案例选择要求

根据学生水平差异，设置难度级别不同的案例，将难度较高的案例留给学生课后完成。在这里，案例选择时应该满足以下条件。

⑴案例要能最大限度地调动学生的参与度，接近学生生活，让学生很容易进入案例情景。

⑵案例要具有代表性，与准备讲解的知识点高度相关。

⑶案例要有助于学生深刻理解数据结构模型，并引起学生的探究和思考，能对所学数据结构加以变形应用。

⑷案例难易程度和学生水平相当，学生学习后，能够独立实现该案例。

⑸授课过程中，注意课程的衔接性，适当选用后续课程中会应用到的数据结构类型相关案例，以此提升学生的关注度。

2.2 各章案例选择注意事项

⑴线性表

线性表是数据结构课程引入的第一个数据结构类型，也是最基础的，针对顺序表，保证学生能够熟练地操作数组元素，链表部分由于会涉及大量指针操作，要重点讲解。作为初学章节，此章案例不易过难，以多项式求和及合并有序表为例即可，要求完成线性表的创建、插入、删除和遍历等基本操作。本部分教学是解决学生基础薄弱的关键一步，太难的案例会让学生产生挫败感，甚至因实现困难而再次放弃学习。所以，理论课学时部分可以补充结构体和指针相关知识点，案例实现时需要给学生完整程序，并详细讲解所有语句，或者实践课上带着学生做，让学生在原有C语言基础上，对数组、结构体和指针等知识点能够完全掌握，保证后面教学的正常进行。

⑵栈和队列

栈与队列，在计算机教学过程中是比较常用的两个数据结构。借此章节，进一步巩固对线性表的操作，同时强调这两个数据结构的特点。栈最大的特点是先进后出，逆序输出是栈经常用到的一个应用场景。其他主要应用包括数值转换、括号匹配、表达式求值和迷宫求解等，前两个案例较为简单，只讲算法即可。可以选取表达式求值为完整实现案例，后面介绍二叉树内容时，用创建表达式树的内容与之相呼应。另外，要重点介绍栈在函数调用过程中的作用和栈在递归调用中的作用，如果学生对递归算法不是很熟悉，选择一个案例，采用递归和非递归两种方法来实现，阐明递归存在的缺点，以及用栈来实现递归的方法。队列是一种特殊的线性表，遵循先进先出的原则。凡是用到先进先出的场合，比如日常生活中各种采用先来先服务的场合都可以采用队列。其中较为特殊的是循环队列的应用，后续操作系统课程教学过程中涉及的生产者与消费者问题，使用循环队列解决循环使用缓冲区，这里可以提前引入讲解。除此以外，在计算机领域，编译器中表达式的处理、函数的调用要用到栈；操作系统中的作业和进程排队、内存分配、设备管理均要用到队列；数据库中使用线性表、索引表等进行数据管理[3]。这些应用和后续课程密切相关，可以在举例时提出，提高学生的兴趣。

⑶树

树结构本身是递归定义的，对二叉树的各种操作也是在遍历过程中实现的，所以这一章的重点内容是二叉树的遍历算法，此章案例可选取一些简单的递归算法帮助学生进一步理解递归，比如：统计叶子结点个数、计算树的深度等，课内学时就可以实现。实际应用中，课内教学多数教材以哈夫曼编码为重点[4-5]，因此，可以选择哈夫曼树的创建、哈夫曼编码和译码为典型案例，介绍整体实现，这样更有助于学生加深对哈夫曼树的创建和编码译码过程的理解。这个案例相对规模较大，学生学到这一章时，编程能力应该已经有较大提高，可以编制一些更为复杂的案例。其他与树结构相关的应用主要是查找和排序，查找算法中有二叉排序树的创建和查找，排序算法中有堆排序。后续课程中树结构的典型应用主要用于文件系统。

⑷图

图结构中以遍历图的两种算法作为重点，即深度优先搜索和广度优先搜索。深度优先搜索算法类似树的先序遍历，本质上也是使用栈实现，常用于解决类似迷宫的问题，此处可结合前面的迷宫算法。广度优先算法的原理类似于树的层次遍历，并且算法使用了队列。所以这部分案例的实现，可以结合前面所学内容，进行对比，并且尝试将不同数据结构的应用统一到一个案例中。拓扑排序的应用包括课程选修的先决条件、检测死锁、计算作业的流水线、解析电子表格中的公式等[6]，可以选择学生最熟悉的课程选修的先决条件案例。最短路径算法的应用包括查找一个地方到另一个地方的最快方式，查找一个城市到另一个城市的最便宜交通方式或类似问题[6]，可选择应用广泛的最短路径问题。工程关键路径相关问题难度较高，可安排学生课后选择完成。

3 教学实施过程

讲授每个数据结构时，通过讲解一个完整的案例，分析如何利用所学知识解决实际问题，具体的实施过程可按照“案例引入——数据结构及其操作——案例分析与实现”的思路来展开教学，通过案例式教学强化学生对该知识体系的认识，从而降低学习的难度。课程的学习过程也是学生进行复杂程序设计的训练过程，从而达到培养学生分析解决实际问题的能力，切实提高学生利用所学数据结构编制复杂算法程序的水平。

3.1 案例引入

每类数据结构引入时使用一个有趣的“问题案例”开头，由该案例逐步引入新的数据结构，然后给出该数据结构的存储表示及各种基本操作的实现，对重点难点和抽象的内容增加图示进行讲解，突出其结构的实用性和应用性。教师把事先选择好的案例实现要求发给学生，让学生带着案例所提出的问题去理解和运用教材中的理论知识，这样不仅提高了学生分析问题和解决问题的能力，而且激发了学生的学习热情。讲解这些案例时，首先分析需要实现的功能，然后选择并构造数据结构，使用与特定数据结构相应的算法来实现具体功能。案例的分析解决过程，就是一个实践软件工程思想的过程。

3.2 数据结构及其操作

传统的数据结构教学方法主要注重数据结构的基本概念和各种数据结构相关的常用算法，引入案例式教学方法后，这部分仍然是教学的重点，并且要结合案例实现，分析需要用到的算法，有针对性地引入，作为重点部分先介绍。还可以考虑案例的特殊性，补充一些通用的操作算法。

3.3 案例分析与实现

从解决实际问题出发，精选实用案例，注重学以致用，案例实现采用定义规范、流程清楚、可读性强、具备参考价值的代码案例，促使学生养成良好的编程习惯。教师针对精选的案例，分析解决方案，引导学生积极思考，最后对案例进行实现，将这部分内容作为教学中的重点部分，通过对典型案例的讲授，教给学生解决实际问题的方法，解决学生基础薄弱问题，帮助学生找到突破口，通过自己的努力完成实践任务，改进教学效果，提高学生解决实际问题的能力。

实施过程中采用课前引入、课堂讲授和课下实现的方式。充分利用实践教学环节和课外时间，解决学时紧张问题，利用实践学时补充讲解案例，利用课外学时督促学生完成案例。根据学生水平，给出不同案例，如果学生整体水平较低，可以在实验课上详细讲解，带着学生完成一部分内容，其余的要求学生充分利用课外时间完成，为保证完成的效果，课上要进行检查，并安排部分案例由学生独立完成。

教学过程中采用循序渐进的方式，除了前面两章的内容讲解完整案例外，后面的案例不再给出完整程序，只需提供程序框架，将数据结构的表示、构建和操作实现的程序框架搭建好提供给学生，根据学生编程能力进展程度，选择合适时机布置完全由学生独立完成的案例。

4 结束语

数据结构的教学内容较为抽象，所以对于课程中比较抽象的概念可以尽量先从学生熟知的案例讲起，老师引导学生讨论案例，通过案例分析引入相关知识，并用所学知识解决案例，最后通过实践环节完成案例。通过实践过程中真正实现不同的案例，才能让学生在学习过程中不再是简单的阅读算法，摆脱水中看月的感觉，最终使得学生在软件开发的过程中，能够为求解的具体问题选择合理的数据结构，能够应用高级语言编写和实现结构清晰、正确、易读的有效算法，达到学习数据结构课程的目标。