数据结构“数据结构”教学中提高学生编程能力

摘 要： 数据结构课程主要研究数据的逻辑结构和数据的存储结构，以及对数据进行操作的有关算法。该课程以程序设计为基础，对学生进行较复杂程序设计的训练，对学生编程能力的培养至关重要。文章着重从如何注重教学方法、引导学生学习的常用算法、如何进行大量程序设计实践等方面来提高学生编程能力进行了讨论。教学实践证明这些教学方法能很好地提高学生的编程能力。
关键词： 编程能力； 教学方法； 算法； 程序设计； 实践
1006-8228（2013）08-61-02
0 引言
数据结构是计算机专业及计算机相关专业的一门实践性较强的软件基础课，它内容繁多，涉及面广，主要研究如何把具有一定逻辑关系的数据在计算机中存储，它是对数据进行操作的有关算法研究的一门学科，它以程序设计为基础，对学生进行较复杂程序设计的训练，课程以提高学生的编程能力培养为主要目标。本文对数据结构的教学方法和实践环节进行探讨。

1 注重教学方法，提高学生的认识能力

在数据结构课程教学中为了提高学生的编程能力，应注重课堂的教学方法，使学生能更好地掌握课程内容，理解前人设计的算法，为此我们研究了数据结构的教学方法。现代教学论中，人们把教学方法归为两大类：一类是程序式教学法，其特点是课堂以教师为中心，有计划有步骤地教给学生教学大纲上规定的知识；另一类是发现式教学法，这种教学法的基本目的不再局限于把前人整理好的知识传授给学生，而是引导、鼓励学生尽可能参与探索知识的过程，其侧重点在于使学生领悟和掌握形成知识的过程和获取知识的方法。
在教学过程中，我们将这两种方法相结合，在讲解数据结构理论基础知识时主要采用程序式教学法，始终抓住什么是“数据结构”这根主线，按照数据结构的逻辑结构、存储结构、运算和运算的实现这四步逐层展开讨论，做到教学思路清晰、逻辑性强，引导学生理解程序的运行原理和过程，并且对于不同层次的学生具体采用不同的方法。在讲解数据结构算法的实现时，我们发现有些班的学生对编程普遍怀有恐惧感，针对这种情况教师与学生一起按常人的逻辑思维方式考虑解决问题的方法，归纳出解决问题的方法和步骤，按方法和步骤与学生一起一步一步地写出程序，然后回过去重读一遍程序，并将不够理想的地方加以改进，使学生知道原来教师考虑问题的思路和自己的思路基本是一样的，这样引导学生编程的过程可使学生获益匪浅，再经过大量地由浅入深地训练后，学生消除了恐惧感，增强了信心，对编程逐渐也产生了兴趣。
数据结构中的内容很丰富，为使学生更好地掌握，我们将教学重点放在使用广泛的数据结构上，精讲最基本的概念与方法，并在这基础上例举一些综合的算法例子，通常借助于发现式教学法的思想进行教学，提供背景材料，讲透算法思想，提出问题，鼓励学生思考、分析，举一反三，让学生自己设计出多种算法。例如，在讲解数据结构中的递归算法时，由于递归算法是数据结构中最难掌握的内容之一，学生一般不能很快接受，因此讲解递归算法的方法很重要。我们先从学生较易接受的数学函数计算入手，进而引入非数值的递归算法，为了使学生了解嵌套调用、层层返回等概念，画出递归运行的状态图和栈的变化图，告诉学生嵌套调用和返回的含义，概括出“递归进入一层，则进栈，递归退出一层，则退栈”的方法，使学生一目了然。在掌握了基本递归算法及运行过程后，进一步例举稍难的递归算法，使学生从多个方面加深对递归算法的理解，这对数据结构后续内容中的树、图、查找和排序算法设计的学习是很有帮助的。

2 注重常用的、经典算法的学习，以激起探索研究的愿望

在数据结构课程教学过程中我们强调基本的编程方法和常用的算法的介绍，并指导学生积累常用算法，积累经典的好算法，例如查找算法、排序算法、遍历算法和图操作算法等，这样使学生在解决复杂问题之前掌握可使用的基本方法，可借鉴好算法的思想来拓展自己的思路。
数据结构中有很多经典的好算法，它们是著名的计算机科学家的成果。我们不仅要学习算法的设计思想，还要学习算法设计的思维方式，以提高学生的逻辑思维能力。以最小生成树两种方法为例，①普里姆（Prim）算法以图中的点为主，通过点朝最小边权伸张出去的方式来求解，其时间复杂度为O（n2）（n为图的顶点个数），它与图中的边数无关，因此适用于求边稠密的图的最小生成树，但在如何判断加入一条边而不形成回路的问题上就遇到了困难；②克鲁斯卡尔（Kruskal）求最小生成树算法以边为主，容易判断加入新顶点是否产生回路的问题，其时间复杂度为O（eloge）（e为图中边的个数），因此适合求边稀疏的图的最小生成树。求解同一个问题时，不同的算法具备不同的特点，适应不同的范围，这样分析讨论，可使学生思路畅通，激发起探研的愿望。再例，数据结构中的排序算法可分类讨论，由个别到一般，由具体到抽象形成算法的设计，并进行算法的初步分析，其中有些算法的分析并未得到完整的答案，例如，希尔排序的分析就是一个复杂的问题，因为它的时间复杂度是所取“增量”序列的函数，只是得出一些局部的结论。虽然我们不一定要引导学生去专门钻研这些难题，但是，提出并分析这些问题至少可以提高学生的学习兴趣，形成研究问题的情景，对数据结构中的许多问题留下思考和探索的空间，从中启发出今后需要深入研究的问题，这样有利于对学生能力的培养。

3 加强实验环节，以提高学生的编程能力

数据结构是一门理论和实践性都很强的课程，学习它的主要目的是提高学生的编程能力，而学会编程、提高编程的能力并不是轻而易举的，要通过长时间的实践锻炼，要学生自己多动手去体验，有些问题只有通过实践后才能明白，也只有实践才能把教师和书本上的知识变成自己的。因此我们在教学过程中针对每个环节都布置一定数量的上机实践题目，有基础题、有综合题，还有结合实际的综合应用题。例如基础题有顺序表、链表的创建、查找、插入、删除；栈、队列的操作；二叉树的遍历；图的存储实现；查找；排序等。综合题有一种结构上的综合操作题如两个链表

摘自：学术论文格式模板www.udooo.com

的合并操作就是查找、插入和删除基本操作的综合，还有多种结构上的综合操作题，如图的遍历搜索演示实验，它可综合考查学生对字符串、链表、栈、队列、图的遍历和递归算法等的理解和综合应用能力，这种实验题知识点覆盖了数据结构的绝大部分内容，具有较强的综合性。我们举几个结合实际应用的例题。 例1：用二叉排序树与单链表相结合来实现学生成绩管理。
用二叉排

源于：论文的标准格式www.udooo.com

序树存放成绩，用链表存放学生信息，相同成绩的学生连在一个链表中并由二叉排序树相应结点指向，具体链表结点形式：
二叉树结点形式：
程序具有前序、中序、后序遍历浏览所有信息功能、有各信息查询功能、有统计成绩功能、有链表结点插入和树结点插入功能，有链表结点删除和树结点删除等功能，对编程基础好的学生还要求将二叉排序树改为平衡树来完成。
例2：用栈解决算术表达式求值演示。根据算符优先关系，实现算术四则混合运算表达式的求值，演示在求值中运算符栈、操作数栈、输入字符和主要操作的变化过程。
例3：用栈队列进行停车场管理。以栈模拟停车场，以队列模拟车场外的通道，从输入的数据序列进行模拟管理。
例4：用图进行上海导游咨询。以图中顶点表示上海各主要景点，存放景点名称、代号、简介等，以边表示路径，存放路径长度等相关信息，程序具有为游客提供各景点相关信息的查询，有查询任意两个景点之间的最短路径等功能。
为了达到预期实验效果，在做每个实验时，要求学生上机运行所编程序，教师认真检查程序运行结果及程序的测试数据，必要时查看学生所编写的程序，了解他们的编程思想；将编程风格好、解决方案好的程序作为例子给学生讲解，鼓励他们多观察、分析、比较、积累，遇到问题时多想几种解决方案；通过分析这些程序，培养学生良好的编程习惯，让他们明白编程风格的好坏在很大程度上影响程序的质量。良好的编程风格可以使程序结构清晰合理，且使程序代码便于维护。我们经过这样大量的上机实践，使学生的编程能力、上机调试能力得到很大的提高。

4 结束语

本文探讨了提高学生编程能力的具体教学措施，这些措施需要结合教学方法灵活地加以运用。我们积累了大量的教学实验用例，帮助学生开阔视野，增强学习的动力，进而提高学生学习的自觉性，使他们的学习过程走向良性循环的轨道。我们经过几年的数据结构教学实践，学生的编程能力普遍提高，证明了上述教学方法是有效的。
参考文献：
严蔚敏，吴伟民.数据结构（C语言版）[M].清华大学出版社，2011.
许自龙.关于《数据结构》的教学实践和体会[J].信息技术教学与研究，2012.4.
[3] 吕国英.算法设计与分析（第二版）[M].清华大学出版社，2011.
[4] 严蔚敏，吴伟民.数据结构题集[M].清华大学出版社，2011.
[5] 严蔚敏，陈文博.数据结构及应用算法教程[M].清华大学出版社，2009.