数据结构课程中栈和队列实验教学方案设计

摘要：数据结构是计算机专业的核心课程，对培养计算机专业设计与创新型人才起着关键作用。该课程是理论性和实践性很强的一门课程。实验教学是其教学中的一个重要环节。栈和队列是两种非常重要的线性结构，它们有很多实际应用。为了帮助学生充分理解、掌握和灵活运用这两种数据结构，本文给出一种栈和队列的实验教学方案。

关键词：数据结构；实验教学方案；栈；队列

中图分类号：G642.0 文献标志码：A 文章编号：1674-9324（2016）24-0274-03

一、引言

实验教学是学生从学习理论知识到走向社会的桥梁，对提高学生综合素质、培养学生创新精神和实践能力有着理论教学不可替代的特殊作用[1]。特别是主干课程的实践教学，它是应用型人才培养中的关键环节[2]。课内实验是指与理论课相捆绑的实践教学，即嵌入到专业基础课或专业课内的实验实践教学[3]。它是与理论教学并行实施的实践教学环节，能够帮助学生深入理解和掌握所学的专业知识。

数据结构是随着处理对象的复杂性不断增加而发展起来的一门课程，作为计算机专业的核心课程，在专业人才培养链条中占有举足轻重的地位[4-7]。数据结构主要研究数据在抽象视图和实现视图中的表示和处理方法[8，9]。抽象视图涉及的是数据结构的理论性部分，实现视图主要体现的是数据结构的实践性，理论指导实践，实践支撑理论，因此设计有助于课堂理论教学的实验教学方案是非常有必要的[10]。它可以解决学生对所学知识缺乏必要感性认识的问题，将知识传授、技能训练、能力培养融于一体，使所学理论知识在实验中得到验证和应用[11]。

栈和队列是两种非常重要的数据结构，它们有非常多的实际应用并且是实现其他复杂结构的基础，因此为了帮助学生掌握并灵活运用这两种结构，本文给出一种栈和队列的实验教学方案。该方案的设计思路也可以应用于其他数据结构或课程的实验教学方案的设计。

二、认识两种重要的数据结构——栈和队列

栈和队列是两种运算受限的线性表，它们的插入和删除运算都被限制在表的端点处进行，只是具体的受限规则不一样[12，13]。

（一）学习对象

栈（stack）是运算受限的线性表，它被限制在表的一端进行插入和删除操作。能进行插入和删除的一端称为栈顶，另一端称为栈底。正是由于它插入和删除操作上的限制使得它具有了一种独特的“后进先出”（LIFO）的特性。栈的LIFO特性使得它具有非常多的应用，如：符号平衡问题、中缀表达式转换为后缀表达式问题、后缀表达式的计算问题、函数调用的实现（包括递归函数的实现）、在股票市场中查找划分、Web浏览器中的网页访问历史、文本编辑器中的撤销序列等。此外，栈还是其他很多算法的辅助数据结构和其他数据结构的组成部分。

队列（queue）也是一种运算受限的线性表，它被限制在表的一端进行插入操作，在表的另一端进行删除操作。进行插入操作的一端称为队尾，进行删除操作的一端称为队首。正是由于它插入和删除操作上的限制使得它具有了一种独特的“先进先出”（FIFO）的特性。队列的FIFO特性使得它具有非常多的应用，如：操作系统中的作业调度、异步数据转换、多道程序设计等。此外，队列还是其他很多算法的辅助数据结构和其他数据结构的组成部分。

（二）学习目标

学习这两种重要的线性结构需要学生重点消化的知识点有：（1）栈/队列的概念、类型定义及基本操作的定义和实现；（2）栈/队列的结构特性；（3）栈/队列的灵活应用。

为了配合栈和队列的理论教学，帮助学生理解和掌握上述知识点，我们需要精心设计栈和队列的实验教学方案。

三、栈和队列的实验教学方案设计

（一）实验题目设计

根据栈和队列的学习目标和遵循循序渐进的学习和教学原则，实验题目被分为以下三个层次：基础型实验题目、设计型实验题目和加强理解型实验题目。

所谓基础型实验是指围绕课程讲授的栈/队列的物理实现和其基本运算的实现来设置的实验题目。设计基础型实验的目的是，通过实践的方式验证课堂上讲授的重要知识点，给学生切身的感受，摆脱“纸上谈兵”的感觉，这种立体的感受有助于学生深入理解和掌握这些知识点。设计型实验要求学生能分别运用栈/队列解决简单应用问题。这类实验题目主要是用来引导和加强学生对栈/队列的灵活运用。设计加强理解型实验的目的是强化学生对栈和队列的结构特性的理解和体会。为了达到这个目的，加强理解型实验题目的设计思路有两个方面：（1）引导学生去思考并解决这样两个问题：能否利用栈的LIFO特性来实现队列的FIFO特性？能否利用队列的FIFO特性来实现栈的LIFO特性？（2）让学生实现其他更为复杂的栈和队列。

在栈的理论教学过程中可以开设栈的基础型实验，在栈的理论教学结束后可以开设栈的设计型实验，在队列的理论教学过程中可以开设队列的基础型实验，在队列的理论教学结束后可以开设队列的设计型实验和加强理解型实验题目。表1给出了具体的实验安排。

学生必须在相关内容的理论教学过程中利用自己的课外时间完成全部基础型实验题目，教师根据学时安排选择1～2道设计型实验题目让学生在上机课上完成，未选择的题目应向学生提供完整的源代码和设计说明。相关内容的理论教学结束后，学生必须利用自己的课外时间完成加强理解型实验题目中的第1题和第2题，剩下两题可以选做。

（二）教学方法

因为三种类型实验的要求、难易程度不同，因此在学生参与形式、教师参与程度、教师参与方式等方面需要区别对待。表2给出了对三种类型实验在上述这几个方面的设计。

基础型实验要求每位学生利用课外时间独立完成，教师全程参与指导。所谓全程参与指导是指从算法基本思想到算法实现的各个环节（包括编程技巧、程序调试与测试等）都要参与指导。参与方式多种多样，例如利用QQ等即时通讯工具进行指导，约定时间和地点进行答疑，等等。

设计型实验要求每位学生在上机课上独立完成，教师前期参与指导。所谓前期参与指导是指教师参与学生在算法设计环节的讨论，教师可以给出提示，同时鼓励学生设计不同的算法。参与方式是面对面的交流。

加强理解型实验要求每位学生利用课外时间独立完成，教师后期参与指导。所谓后期参与指导是指教师在收齐学生提交的源码和设计报告后，对其进行分析总结，并将总结结果以班级为单位采用面对面的方式反馈给学生。

（三）考核方法

对三种类型的实验采用不同的考核办法。表3给出了这方面的设计。

对基础型实验不做专门考核的原因是学生基础型实验完成的好坏会直接影响设计型实验和加强理解型实验的完成，因此对其他两种类型实验的考核间接考核了基础型实验。

对设计型实验的考核分两个部分：一是本次上机课上实验的完成情况，包括程序是否调试成功、程序的运行结果是否正确，代码编写的质量等；二是本次上机课结束后提交的实验报告的完成情况，包括内容是否完成、书写是否规范等。

对加强理解型实验的考核主要是考核学生提交的源代码和设计报告的完成质量。

设计型实验的成绩占总实验成绩的70%，加强理解型实验的成绩占总实验成绩的30%。

四、结语

数据结构是一门理论性和实践性很强的课程，其理论教学环节与实验教学环节相辅相成。栈和队列是两种重要的线性结构，为了提高它们的教学效果，增强实验教学对其理论教学的促进作用，本文提出了一种栈和队列的实验教学方案。该方案的设计思路同样适用于其他数据结构或课程的实验教学方案设计。

参考文献：

[1]朱金秀，金纪东，周妍，等.实践教学与就业能力培养相融合的研究与探索[J].实验室研究与探索，2011，30（4）：105-107.

[2]荣瑞芬，闫文杰，李京霞，等.实践教学课程考核评价模式探索[J].实验技术与管理，2011，28（3）：232-234.

[3]张纯容，施晓秋.问题与案例驱动的课内实践教学分级模式探索[J].实验室研究与探索，2012，31（1）：145-148.

[4]教育部高等学校计算机科学与技术教学指导委员会.高等学校计算机科学与技术专业人才专业能力构成与培养[M].北京：机械工业出版社，2010：143-147.

[5]董丽薇.数据结构课程教学方法的改进[J].沈阳师范大学学报（自然科学版），2012，30（2）：307-309.

[6]刘城霞，董宛，蔡英.数据结构中基本教学案例的研究[J].计算机教育，2010，（03）：144-146.

[7]韩建民，钟发荣，赵相福，等.基于ACM-ICPC训练模式的数据结构实践教学探讨[J].计算机教育，2013，（10）：103-107.

[8]沈华.数据结构、算法和程序之间关系的探讨[J].计算机教育，2013，（04）：58-61.

[9]沈华.数据结构入门教学中的实例法[J].计算机教育，2013，（24）：64-66.

[10]沈华.数据结构课内实践教学方案[J].实验室研究与探索，2013，32（10）：396-400.

[11]刘光蓉.以计算思维能力培养为导向的C程序设计实验教学[J].实验技术与管理，2013，30（1）：154-156，191.

[12]Korsh J F，Garrett L J. Data structures，algorithms and program style using c[M].Boston，PWS-Kent Publishing Co，US，1986.

[13]沈华，杨晓艳，马驰，等.数据结构及应用：C语言描述[M].北京：机械工业出版社，2011.