周世平+武秀川+卢云宏

摘 要 文章针对数据结构课程的特点，分析了该门课程实践环节面临的问题，提出了学生实践应由简单验证、设计、到综合创新的观点，对实践环节的实验课和课程设计两个阶段分别规划了验证型、设计型和综合型实验。并且设计型实验相互关联，有助于学生过渡到综合实验。两个年级的教学试验表明，这样的实践规划帮助学生理解课程，增强学生的数据结构和算法的设计能力，提高了学生的综合分析、合作完成项目的能力。

关键词 数据结构 实践环节 实验课 课程设计

中图分类号：G424 文献标识码：A

数据结构课程是计算机科学技术、软件工程专业的专业核心基础课。其范畴涉及数学、计算机硬件、计算机软件、数据存储器分配、数据组织及查找。数据结构课程是程序设计提高的基础，也是操作系统、编译系统和数据库系统等系统程序的重要基础，尤其对于进行高效率的计算机程序开发非常重要。

计算机专业的数据结构课程通常设置在大学的一、二年级，它包括两个环节：课堂教学和实践环节。实践环节设置的目的：首先是让学生学会将抽象的数据结构表示为具体的物理存储并使用，将算法转化为程序，加强对算法的理解；其次，学生要在实践环节实现算法设计、进一步理解算法；最后，学生在实践环节完成算法的测试和比较，理解算法的复杂性。对于仅仅学了一门程序设计课程的学生，不习惯在抽象的层次上解决问题。难以建立数据结构的概念、算法的思想。这样，实践环节在数据结构课程中占据着极其重要的地位。近年来，人们在实践环节上进行了一些理论方面的探讨，①②实践环节有专门的实践教程，③课程设计不再是一个小项目的实现，也有专门的指导。④多年的教学实践，我们深切体会到，数据结构课程能否顺畅进行，很大程度上取决于实践环节的有效实现。

1 实践环节面临的问题

实践环节由实验课和课程设计两个阶段组成。其中实验课与理论课同步进行，与所学章节内容密切相关；课程设计是在课堂教学和实验课结束之后进行的集中的综合设计，内容可涵盖课程的全部内容。目前各高校通常在实验课程阶段采用验证型实验，即针对给定的数据结构，将教科书中的算法转化为程序，验证算法的正确性；在课程设计阶段采用设计型实验，给出若干个题目，让学生自行考虑所使用的数据结构并设计算法完成题目。我们对这样的实践课程进行了分析，并结合学生的反馈信息，总结出实践环节中面临的主要问题是：（1）数据结构的选择问题。传统的实验课阶段是以章节内容为核心，验证算法为主，忽略了抽象化的训练，导致学生在课程设计阶段及应用程序开发中数据结构选择方面的不足。（2）算法应用的问题。实验课阶段的验证型实验误导学生将算法与程序视为等同，忽略了算法的重要性，看不到算法的应用，直接导致学生在项目设计中很少应用算法设计。还有算法测试部分的缺乏导致学生较少地分析和比较算法。（3）课程设计阶段的问题。课程设计往往是单独一个项目，缺少综合性。还有，由于实验课阶段与课程设计阶段的内容缺少衔接，学生由被动的验证型实验过渡到综合型实验呈现困难， 丧失完成课程设计的信心，趋于抄袭。（4）实践环节的设计。本文对数据结构课程实践环节的教学内容进行了设计。对实验课和课程设计两个阶段的内容重新进行了规划。强调了实验阶段的设计性和课程设计的综合性。两个阶段进行有效衔接是数据结构课程实践教学环节任务完成的保障。

2 实践环节的设计思想

实践环节由实验课和课程设计两个阶段组成。实验课程阶段与理论课同步进行，其内容与教学章节紧密相关。实验课阶段的实验可分为验证型实验和设计型试验。验证型实验的目的是促进学生对于所学的数据结构与算法的理解，并学会将算法程序实现。设计型实验的目的是通过具体实例，训练学生将具体问题进行抽象，设计数据结构和算法。为了向课程设计阶段过渡，设计型实验的题目相互关联，比如可采用一个综合项目的子项目作为一个设计型实验。

课程设计阶段采用综合型实验，其目的是训练学生对于比较大的项目能够进行综合设计，从项目总体需求设计数据结构和算法，将项目划分为若干个独立的子项目。学生可借用前期的设计型实验，综合成较大的项目。

3 实验课阶段的实验设计

实验课阶段的实验包含验证型和设计型实验。下面样例是关于链表的实验。

3.1 验证型实验样例

【内容】链表的实现和基本操作。

【要求】定义链表结点，假设链表的元素为int类型数据。

（1）程序实现链表的基本操作

（a）初始化LinkedListInit（）

（b）创建链表LinkedListCreate（）

（c）求表长LinkedListLenth（LinkedList L）

（d）按值查找 LinkedListLocate（LinkedList L， Elemtype x）

（e）插入一个元素 LinkedListInsert（LinkedList L，int i， Elemtype x）

（f）删除一个元素 LinkedListDelete（LinkedList L，int i）

（g）遍历顺序表 LinkedListInsertTraverse（LinkedList L）

（2）编写main（）函数，给出实例测试各个基本操作。

3.2 设计型实验样例

【内容】链表的应用。

已知本市的某一线路公共汽车在早晨高峰期间极其拥挤，乘客要求汽车公司增加早班车的数量。现在公司派你去调查该线路汽车的乘客数目变化情况，报告上午7：00-8：00该线路在各站的乘客流量。

【要求】创建BusStop类型的结点用以表示站点。用链表Line表示该线路。

（1）设计站点的数据结构；endprint

（2）设计线路的数据结构；

（3）设计算法；

（4）程序设计与实现；

（5）选定正常值和边界值进行测试。

3.3 验证型实验与设计型实验对比分析

我们对验证型实验和设计型实验进行了分析比较，结果如表1所示。

另外，所有设计型实验均是围绕市公交系统，相互关联，为学生的课程设计做准备。

4 课程设计阶段的实验设计

课程设计阶段的实验采用综合性实验。

4.1 综合型实验样例

【内容】设计烟台公交系统。本系统分为三个模块：乘客查询模块、管理模块和统计模块。

【要求】三个学生合作完成该系统。对系统进行综合分析，选择所用的数据结构和算法。要求用到所学的数据结构至少3个。每个学生选一个模块，相互测试，共同完成课程设计的实验报告。

4.2 涉及的数据结构与算法

可选择的数据结构有：线性表、栈、队列、稀疏矩阵、二叉树与树、图、查找集合等，以及在这些数据结构上实施的算法。

4.3 设计型实验和综合型实验对比分析

我们对设计型实验和综合型实验进行了分析比较，结果如表2所示。

5 结语

本文论述的数据结构课程实践环节的教学改革设计，于2012年在烟台大学计算机学院软件工程专业和烟台大学文经学院计算机科学与技术专业实施。我们将受惠于该设计方案的学生（试验学生）与其他学生进行了对比，对比结果显示他们在很多方面表现出优势，见表3。

总之，我们进行的数据结构实践环节的设计是以学生为主体，变学生被动学习为主动学习，重视实践环节中数据结构与算法的设计，强调实验课阶段与课程设计阶段的衔接。验证型、设计型和综合型三种实验是由简单验证型、构造设计型到综合分析设计型，循序渐进地培养了学生的实践能力。两个年级教学试验证明其效果良好，值得我们进一步探讨、完善，整理出合适的数据结构实践教材并推广使用。

注释

① 张英彦.论实践教学的理论基础[J].教育科学，2006.22（4）：34-36.

② 张英彦.论高校实践教学目标[J].教育研究，2006（5）：46-49.

③ 徐惠.数据结构实践教程[M].北京：清华大学出版社，2010.

④ 何钦铭，冯雁，陈越.数据结构课程设计.杭州：浙江大学出版社，2007.endprint