《数据结构》课程教学设计

摘 要 ：本文针对《数据结构》这门计算机专业的核心课程,深入探讨了课程的定位、教学目标、内容体系等,给出该课程的理论教学设计、实验教学设计及考核方式和标准,并已在瓯江学院理工分院的计算机科学与技术专业三个不同年级的学生中实施,取得了较理想的教学效果.

关 键 词 ：数据结构；教学设计；教学目标；内容体系

中图分类号：TP3-0 文献标志码：A 文章编号：1674-9324（2013）08-0209-04

一、引言

《数据结构》是计算机科学与技术及相关专业的一门非常重要的专业基础核心课程,其主要研究内容是数据之间的逻辑关系和物理实现,即探索有利的数据组织形式及存取方式.有关计算机的各类软件的开发和设计,首先要考虑数据的表示,即使用何种类型的数据结构.因此,如何更好地解决实际问题,仅仅依赖几种计算机程序设计语言是不够的,还必须学习和掌握好数据结构的有关知识.当我们使用计算机来处理一个具体问题时,一般需要经过下列几个步骤：首先要从该具体问题抽象出一个恰当的数学模型,然后设计出解决此类数学模型的算法,再编写相应的程序并进行调试、测试,运行程序并最后得到答案,如图1所示.

早期计算机为解决问题而涉及的运算对象都是一些简单的数据类型,如整型、实型或布尔类型数据,所以一般把着重点放在程序设计的技巧上,而不必重视数据结构.随着计算机的发展,它的应用领域的不断扩大,涉及非数值计算问题的应用所占的比例越来越大,许多问题涉及到的处理对象不再是简单的数据类型,其形式更加多样,结构更为复杂,因此,解决这类问题的关键不再是数学分析和计算方法,而是要设计出合适的数据结构,以便更有效地解决问题.

二、课程说明

1.课程的定位.《数据结构》这门课程,是计算机理论与技术的重要基石,该课程一般是在大学二年级上学期开设,具有承上启下的重要作用,既要对前一年学习的软件技术进行总结提高,又要为后续专业课程提供基础.它贯通始终,是计算机科学与技术人才素质培养框架中的中坚课程,对学生的软件开发能力培养至关重要,也为学生今后的专业生涯打下牢固的基础.所以《数据结构》课程是计算机专业提高软件设计水平的一门关键性课程,它在整个课程体系中具有非常重要的地位.《数据结构》课程在计算机学科中与其他课程的关系如图2所示.

2.课程的教学目标.温州大学瓯江学院作为独立学院,其定位为培养“应用性”本科人才,同时结合本课程的地位,因此,在本课程的教学中体现“基础性”和“应用性”.本课程的定位与目标是：①注重基础性：掌握基本数据结构的特点,了解数据结构与算法的关系；培养学生的算法设计与分析的基本理论知识和技能；培养学生设计及选择有效的算法、设计合适的数据结构的能力；增强学生发现问题、分析问题和解决问题的能力.②突出应用性：本课程强调理论和实践的统一,突出对学生的动手能力的培养.在对学生进行基本数据结构的理论、技术和设计等的知识运用和技能培养的同时,突出对学生进行将实际问题转化为基本数据结构和算法问题的分析能力.鼓励学生学以致用,用学到的知识来解决实际问题.

3.课程内容体系.数据结构课程的内容主要是围绕着数据的逻辑结构、数据的物理结构（数据在计算机中的存储方式）和选用合适的算法来实现对数据的相关操作展开.数据的逻辑结构有：线性结构、树形结构、图结构；数据的物理（存储）结构有：顺序存储结构和链式存储结构.在教学中引入抽象数据类型（ADT）观点介绍数据结构技术,采用算法时空分析来判断算法的好坏.在此基础上介绍数据结构的具体应用.数据结构课程的内容体系如图3所示.

我们把数据结构课程的内容划分为基础部分、数据结构与算法部分和应用部分.基础部分的内容有数据结构与算法的基本概念,抽象数据类型（Abstract Data Type,简称ADT）的表示,算法时空分析（算法复杂度）等.数据结构与算法部分是课程的核心内容.介绍各种基本数据结构的特点、ADT、各种存储实现方法、相关的操作的实现.应用部分主要介绍排序、查找（或检索）、索引和散列等经典算法.

三、理论教学设计

1.教学方法与手段.由于独立学院的学生本身基础不够扎实,加上《数据结构》课程理论性强,内容抽象,学生在学习该课程的开始阶段,容易产生畏惧和茫然的情绪.为了提高教学质量,我们在对教学方法和教学手段等方面进行了有益的探索和尝试.要处理好多媒体教学模式与传统教学模式之间的关系.多媒体教学模式以其形象性、生动性和信息量大等特点已成为主要的课堂教学手段,但也存在一些不足,一方面影响教师的即兴发挥,而这恰是传统黑板教学的长处；另一方面,由于多媒体教学具有信息量大、呈现快速、表现直观、操作简便的特点,教学活动很容易出现“课件喧宾夺主”的不良倾向.笔者认为,在讲述如算法思想、编写程序时,采用传统的教学模式更能清晰地表达.因此,在教学中要综合使用多媒体教学模式与传统教学模式两种教学手段,以达到良好的教学效果.

2.把握课程的重点和难点.①课程的重点.基础部分：数据结构的有关概念术语、算法特性、算法描述和算法分析；数据结构与算法部分：线性表、栈、队列、串、树、二叉树、图等数据结构的逻辑结构、存储结构、相应基本操作的实现,这些基本数据结构的应用：一元多项式的运算、递归算法的设计和实现、哈夫曼算法的实现和哈夫曼编码的设计、最小生成树和最短路径的求法及实现；应用部分：顺序查找算法的设计,二分查找算法的设计,二叉查找树的创建、查找、插入和删除的算法的设计,散列表的建立和查找算法的设计；直接插入排序算法、冒泡排序算法、简单选择排序算法、快速排序算法、堆排序算法和归并排序算法的实现,这些排序算法的性能比较.②课程的难点.基础部分：抽象数据类型（Abstract Data Type,简称ADT）概念的理解和描述,算法时间复杂度和空间复杂度的估算方法；数据结构与算法部分：栈在递归函数中的应用,模式匹配KMP算法.图的遍历方法、Dijstra、Floyd、Prim、Kruskal等典型的图应用算法；应用部分：排序算法的复杂性分析,排序方法在各类实际问题中的应用.散列表的建立和查找算法的设计. 四、实验教学设计

1.实验类型.根据独立学院应用型人才培养目标,注重培养实践动手能力,结合教育部的“面向21世纪教学内容和改革计划,保留少量必开的经典验证型实验,增开综合型、设计型实验”的精神,为了保证实验课的正常运行,完成实验教学目标,针对独立学院学生普遍编程能力比较弱,C程序设计语言基础较差的情况,我们打算增开一些巩固C语言的课程预备型实验,保留了必要的经典的验证型实验内容,增加设计型实验,加强综合型实验,使得实验类型不再单一,实验内容更显层次化,做到既要有基本实验的训练,又有独立思考、综合运用知识、创新等能力和素质的培养.预备型实验：主要加强学生C语言的薄弱环节,如结构体、指针、数组、函数调用等,掌握C语言的这些知识点是完成数据结构实验的有力保证.验证型实验：主要是为了理解和巩固数据结构的基本知识点,用来验证典型数据结构的逻辑定义及在具体存储结构下的相关操作实现.综合型实验：实验内容涉及本课程的综合知识或本课程相关课程知识,主要是为了培养学生的综合分析能力、实验动手能力、数据处理能力及查找参考资料的能力.

2.实验方法.对于验证型实验,学生在做实验的任务基本上,只是将课本的算法修改为在某种编程语言环境下可以运行的程序而已.但对于设计型和综合型实验,尤其是综合型实验,它是多个知识点的综合训练,包括问题分析、总体结构设计、程序设计等基本技能,需要用更科学的实验方法系统地完成.所以,为完成《数据结构》实验,我们引入软件工程的方法来指导实验,以实现实验方法的规范化.需求分析：说明实验的主要任务,如输入的形式和输入值的范围、输出的形式、程序功能和测试数据等.概要设计：说明本实验中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次调用关系.详细设计：实现概要设计中定义的所有数据类型,对每个操作用程序设计语言编写代码；画出函数之间的调用关系图.调试分析：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；算法的时间复杂度与空间复杂度的分析；算法的改进设想.

3.实验过程.数据结构课程实验同其他课程不同,在上实验课之前需要做大量的准备工作,整个实验从开始到结束不可能在有限的实验计划课时中全部完成,因此对整个实验过程的控制和管理显得非常重要,要求对每一次实验课都进行精心地策划,我们主要从课前预习阶段、实验操作阶段和实验总结阶段等三个阶段进行改革,以实现实验过程的规范化.课前预习阶段：以往的实验教学环节,往往是学生到了课堂上才知道实验的内容,学生往往措手不及,这不利于实验教学的正常开展.现在我们采用把每个实验内容提前放在网上,要求学生课前充分预习,详细了解实验目的和原理、实验要用到的数据结构和算法,在实验之前必须提交实验预习报告.通过课前预习,保证学生在实验中思路清晰,能及时发现问题,易于取得实验的成功.实验操作阶段：学生上机实验的过程是实验成败的关键,我们一方面培养学生在实验过程中养成做实验记录的良好习惯,另一方面引导学生在实验过程中积极思考,当出现异常情况时,教师要指导学生分析其产生问题的根源,寻求解决问题的方法.学生在每次实验结束后,要将实验记录交给教师检查签字.实验总结阶段：这一阶段要求学生完成高质量的实验报告,实验报告中除了包括数据结构定义、算法思路、异常情况分析、测试数据及运行结果等必备的内容外,更重要的还要包括实验设计实施的成败得失、经验教训和心得体会.整理和填写实验报告的过程,即是学生对自身存在的问题进行修正和完善的过程,通过分析整理实验报告,学生可以更深刻地认识到自己在实验中存在的问题,加强其设计思维的训练,也能不断地积累解决实际问题的动手能力.

五、课程考核

1.《数据结构》课程的考核学生成绩以100分制评定,其中,平时成绩（包括书面作业、课堂测试、期中测试）,占总成绩的15%；考勤和学习态度,占总成绩的5%；上机实习（加实习报告）,占学期总成绩的20%；期末考试,占总成绩的60%.

2.“数据结构综合实验”的考核学生成绩以优、良、中、及格和不及格五个等级评定,其中,学生编写的实际软件和运行结果,占总成绩的30%；设计报告,占总成绩50%；教师提问,占总成绩10%；考勤和学习态度,占总成绩10%.关于综合实验成绩的考核,由于过去过分依赖实验报告的优劣,导致学生不注重实验过程,片面追求实验报告的篇幅和整洁程度,严重制约了对学生综合素质的培养.因此,必须注重综合能力的考评,考虑平时的表现、实验过程的考核、严禁抄袭.

《数据结构》是计算机科学与技术专业的专业基础主干课程,该课程整体的教学设计是以独立学院人才培养目标为依据,结合学生的整体情况和课程在整个学科体系中的地位作出的,已在本院2008级、2009级、2010级计算机科学与技术专业三届的学生中实施过.从实施过程中得到的反馈信息有：学生认为理论课掌握得比较好,但要自己动手编程解决具体问题还是比较难,实验的完成情况不理想；该课程对前导课程（主要是C语言程序设计和离散数学）的依赖性很强,学生编程能力低下和数学基础的薄弱对该课程的教与学都有比较严重的影响.因此,借着该课程院级精品课程建设的契机,对该课程教学设计还要做较深入的探索,比如对各种实验类型的比例设置,实验难度的控制,如何与前导课程的融合,做好课程群建设等,以不断提高课程的教学质量.