摘要：数据结构是高等院校计算机专业的一门重要的专业课。就目前普遍采用的面向过程的教学方式的弊端，提出了进行对象化的教学方式。结合我院实践，提出了一系列的教学步骤，并对此作了分析和探讨。
　　关键词：数据结构；面向对象；模板类
　　
　　Discussion and practice on data structure by object-oriented teaching method
　　Xu Chong, Xu Jian
　　Hangzhou dianzi university, Hangzhou, 310018, China
　　Abstract: Data structure is an important course for computer science major in university. In this paper, the abuse of a commonly used process-oriented teaching method has been analyzed; the author proposes the object-oriented teaching methods. Based on the experience of our college,it puts forward a series of teaching procedures then have been analyzed and discussed.
　　Key words: data structure; object oriented; template class
　　
　　数据结构是计算机软件技术的基础,以数据为中心讲述问题如何在计算机程序中得以实现,这门课程的理解和掌握,对学生进行数据分析、组织及处理能力以及编程能力有着非常深远的影响。课程教学目标不仅要培养学生缜密的逻辑思维和数据抽象能力,更要培养学生在软件设计领域科学的思维方式,将算法理论和编程实践完美结合,能够在工程实际中灵活加以应用。因此不断改进数据结构的教学方法,提高数据结构课程的教学质量是培养高素质软件人才的迫切要求。
　　众所周知,面向对象程序设计思想是目前的主流,它首先着眼于应用问题所涉及的对象、对象的属性、操作等,据此建立类的继承层次结构,实现所应完成的功能。在存储结构的访问上,只有通过类的成员函数才能完成,提高了数据的安全性。并且这种程序可靠性,可复用性均比面向过程的程序更为优越。在数据结构课程中,可体现为主要工作是处理数据,对于基本的数据结构(线性表、栈、队列、树、图),可以将其数据元素的类型定义和基本操作封装在类中,对这些类作概括抽象,建立实例,能帮助学生加深对数据结构整体认识,并锻炼学生的编程能力,培养好的编程习惯,从根本上解决学生不会分析问题,走出不会编程实现的困境。
　　本文中使用的面向对象语言为C++,以《二叉树和图》这一章节中的内容为例,探讨了使用面向对象的教学方式,在我校经实践取得了不错的效果。
　　
　　1目前主流的数据结构教学方法存在的弊端
　　
　　目前国内高校计算机专业的数据结构课程教学大多采用面向过程的思想,当描述一种数据结构时,通常使用抽象数据类型(ADT)。而解决一个具体问题时,首先从系统要实现的功能着手,自顶向下,逐步分解来实现相应的程序模块。采用这种思想,该课程侧重点在于具体算法设计实现上,学生往往会注重算法而忽略数据结构的定义,考虑问题的着眼点放在局部而非整体。另一方面每一个算法是由一个具体问题研究而出,导致程序的可复用性很差,不是当前的程序设计方法主流。
　　经查阅资料发现,目前国内高校采用面向对象的思想进行数据结构教学还不多见,所使用的语言描述工具常是伪代码指令,学生往往很困惑,无法调动学习积极性。
　　通过上面的分析,可以看出我们正面临着一个问题：如何修正数据结构课程的教学指导思想来适应快速发展的软件开发技术,引入面向对象的描述方法来展开教学已迫在眉睫。
　　2进行面向对象数据结构教学的步骤
　　
　　2.1 做好面向对象程序设计的教学前期工作
　　面向对象程序设计,有2个最为重要的思想即封装和继承。作为数据结构的先修课程,在教学过程要重点把握好这两点。
　　2.1.1 认识封装,学会用对象来构造程序
　　在培养学生编程思维时,要能够首先考虑用什么对象来解决问题,学会用对象来构造程序。
　　2.1.2 使用继承,实现代码重用
　　使用继承的方法很好地实现了软件的可重用性,让学生从实例中领悟一般与特殊的关系,在进行开发程序时,就可以从类库中选择类,进行继承功能。
　　2.2 用模板类的方式实现每种基本数据结构
　　数据结构课程的主要教学内容是数据的逻辑结构、存储结构和数据的操作。4大基本数据结构分别是集合、线性结构、树形结构和图形结构。在数据结构中,更侧重于算法的实现,因此对各种数据类型通过使用模板,可以只设计一个类来处理多种类型的数据,而不必为每一种类型分别创建类,指定一组基于相同代码但是处理不同类型或类的函数就可以完成。下面以二叉树为例构建模板类：
　　//二叉树结点结构
　　template
　　struct BTNode
　　{
　　ElemType data; //结点数据域
　　BTNode *lchild; //结点左孩子
　　BTNode *rchild; //结点右孩子
　　};
　　//二叉链表类
　　template
　　class BinaryTree
　　{
　　public:
　　BinaryTree():m_root(NULL){} // 构造函数
　　~BinaryTree()//析构函数
　　//按以先序次序输入结点值的方式建立二叉树的接口函数
　　void Create1(ElemType ch[],const ElemType &endChar);
　　//以二叉树的先序和中序次序建立二叉树的接口函数
　　void Create2(ElemType ch1[],ElemType ch2[],int );
　　void PreorderTraverse (void (*visit)(const ElemType &));//先序递归遍历二叉树的接口函数
　　void InorderTraverse (void (*visit)(const ElemType &)); //中序递归遍历二叉树的接口函数
　　void PostorderTraverse (void (*visit)(const ElemType &));//后序递归遍历二叉树的接口函数
　　……
　　private:
　　BTNode *m_root;//二叉树根结点指针
　　BTNode* _Copy( BTNode* ); //复制二叉树
　　//按先序次序输入结点值的方式建立二叉树
　　void _Create1(BTNode* &,ElemType ch[],const ElemType &,int &);
　　//已知二叉树的先序遍历次序及中序遍历次序,建立二叉树
　　void _Create2(BTNode * &,ElemType ch1[],ElemType ch2[],int ,int ,int &);
　　void _Destroy(BTNode* &);//销毁二叉树
　　//先序递归遍历二叉树
　　void _PreorderTraverse(BTNode* ,void (*visit)(const ElemType &e));
　　//中序递归遍历二叉树
　　void _InorderTraverse(BTNode* ,void (*visit)(const ElemType &e));
　　//后序递归遍历二叉树
　　void _PostorderTraverse(BTNode* ,void (*visit)(const ElemType &e));
　　……
　　};
　　在这个模板类中,首先定义了二叉树结点BTNode,是一个结构体,包含数据域、左孩子指针和右孩子指针。再定义了一个二叉链表类BinaryTree,公有函数中包含了该类的构造函数和析构函数,除此还有二叉树先序中序和后序遍历等。另预留了2个create函数作为接口,作为学生在学完后的课程设计作业。若要添加操作,只需在类中增加相应函数即可实现。私有函数是封装的,通过调用类中的公有函数来访问它。
　　2.3 用案例加深面向对象的理解
　　在教学过程中,讲解各种数据结构及其算法往往使学生觉得枯燥无味,很多学生学完了数据结构后经常会发问：学习这种数据结构有何用途？或者在现实生活中哪里可以应用到？引入案例更能吸引学生,提高他们的学习兴趣,因此案例是重要的教学资源。教师在讲授每一种数据结构时,首先设计与现实生活紧密相连的实际问题,让学生试着先用面向过程的方式去解决,再由教师用面向对象的方式去解决,从程序编码的数量,到重用代码的便利等多方面进行比较,加深对面向对象的理解。如在《图》这一章中,设计一个实例为教学计划编制问题,若用面向过程的方式来完成,必须要构造图,建立邻接表作为存储结构,利用基本数据结构栈的出栈入栈等操作,最后用拓扑的方式完成。程序所用函数调用如图1所示：
　　而用面向对象的方式,因为已经将图的存储结构和基本操作封装在一个头文件中,使用这种数据结构时,只需要将相应的头文件包含在程序中,随用随调。这样可以帮助学生将所学知识形成一个完整框架,让学生懂得设计程序不仅要懂得算法,还要让程序设计得模块化,结构化。这正是面向对象思想的精髓。
　　2.4 改革课程设计让学生从看懂到会做
　　课程设计是培养学生动手实践能力的具体体现。配套相应的课程设计让学生自行完成,能加深学生对数据结构的理解,使用面向对象的思想让学生真正学会编程,学会分析问题,解决问题。我院主要从如下2点进行了课程设计的教学改革：
　　2.4.1 梯度命题,循序渐进
　　课程设计以往是教师根据实验指导书布置课题后由学生完成,部分学生感到难度很大,无从下手。现阶段我们将课程设计改为验证型、验证设计型、设计应用型多种层次,进行梯度命题,分层教学,使得不同层次的学生各有收获。针对各种基本数据结构,教师首先用模板类实现,学生在课程设计时先用实例验证程序,在此基础上,设计出预留的一些函数接口,实现该类的部分功能。最后再针对某一具体问题,由学生开发出完整的程序。这是一个由易入难的循序渐进的过程,学生通过验证型实验更加牢固掌握基本数据结构,再由验证设计型和设计应用型实验学会如何应用数据结构,如何在计算机中实现存储,实现各种需求的功能。
　　如二叉树部分,教师设定的验证型实验为：给定一棵二叉树,验证其先序中序和后序遍历结果。在掌握了二叉树遍历的基础上,设计出模板类中预留的两个接口函数create1和create2。最后,安排设计型实验为创建表达式树；分别用3种遍历方式遍历该树,比较它与实际的波兰式、中缀式和逆波兰式之间的区别；完成给定表达式树的表达式求值运算。这样有梯度地安排课程设计,一方面强化了基本概念,另一方面引导学生完成更复杂的设计。对基础薄弱的同学来说,验证型实验难度不大,基本都能完成,大大增强了自信；对优秀学生来说,挑战设计型实验更能提高自身的能力。
　　2.4.2 精编课题,联系实际
　　教师在每一章精编几道综合实用课题,从功能定义、系统分析、数据抽象、类的定义、代码实现等方面进行指导,弥补学生在学习理论知识时不能联系实际的情况。我校课程设计的题目有：学生成绩管理系统(线性表)、地图四染色问题(栈)、舞伴问题(队列)、线索二叉树问题、报文编码问题(哈夫曼树)、校园导航问题(图的最短路径)、教学计划编制(拓扑排序)、文本文件单词的检索(查找)、排序综合问题等,并要求学生利用类模板完成上述程序。课程设计的成绩由几个方面综合决定,包括课题的难易度、完成情况、代码编写质量等,最后由学生提交设计报告进行总结和讨论。设计报告要学生再“多想一点”,即其他可能存在的求解方法,该设计的优缺点,如何提高时间空间性能等问题。通过总结,学生对问题有了更加深入全面的理解。
　　
　　3结束语
　　
　　数据结构作为计算机专业的重要基础课程之一,对学生软件开发的过程和习惯的培养是至关重要的。在教学过程中应该把面向对象的思想融入进去,用类和模板的形式描述数据结构,让学生适应快速发展的软件开发技术。从4个方面讨论了如何进行面向对象化的数据结构教学,在我院经过实践,通过2个学期的教学,从效果上来看,比前几届学生的动手能力、学习积极性上均有了明显提高,绝大部分的同学都能顺利完成课程设计并获得较好成绩。
　　
　　参考文献
　　
　　[1] 李睿,林亚平.做中学—面向对象程序设计与数据结构课程一体化研究[J].计算机教育,2008,16：151～152
　　[2] 冯莉.用OOP探讨数据结构的教学思想和方法[J].襄樊学院学报,2008,29(8)：74～77
　　[3] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京：清华大学出版社,2002