数据结构与算法课程教学实施方案
时间:2022-03-03 08:05:15 浏览次数:次
摘要:介绍了《高等学校计算机科学与技术专业核心课程教学实施方案》中“数据结构与算法”课程的设计理念。该课程方案以问题求解为导向,贯穿数据结构理论、抽象和设计的三个形态,强调围绕抽象数据类型(ADT)的有效表述,建立数据结构的逻辑结构、存储结构和运算的有机联系,并配备扎实的实践训练。分层次培养创新的科学型人才、综合的工程型人才、技术的应用型人才。
关键词:数据结构;算法;计算机科学与技术;核心课程;问题求解;实践教学;课程建设
作为计算机学科一个重要的分支,数据结构与算法的研究涉及构筑计算机求解问题过程的两大基石:刻画实际问题中信息及其关系的数据结构,描述问题解决方案的算法。
人们利用计算机的目的是解决实际的应用问题。在明确所要解决问题的基础上,经过对问题的深入分析和抽象,为其建立一个逻辑模型并分析基本的运算,然后确定恰当的数据结构表示该模型,在此基础上设计合适数据存储及相关算法,最后完成具体的程序来模拟和解决实际问题。
计算机求解问题的核心是算法设计,而算法设计又高度依赖于数据结构,数据结构的选择则取决于问题本身的需求。可以说“数据结构与算法”是计算机专业课程的核心。
在“高等学校计算机科学与技术专业核心课程教学实施方案”研究项目的支持下,本课程项目小组跟踪研究美国IEEE/ACM CC2001—2005课程体系(ComputingCurricula)和我国教育部CCC2006学科规范,分析当前IT技术发展需求,结合各位作者在高校长期开设的“数据结构与算法”教学成果,编写了“数据结构与算法”教学实施方案。本文详细介绍该实施方案的基本定位、理论知识体系、实践应用方案等内容。
一、课程的基本定位
1 课程的定位
作为一门重要的专业核心必修课程,“数据结构与算法”课程既是对以往课程的深入和扩展,也为深入地学习其他专业课程打下基础。课程中排序问题算法以及基本的树、图等数据结构,是计算机科学的基本功。B+树、散列(Hash)等高级数据结构,也是数据库、操作系统、编译原理、计算机网络等重要专业课程的基础。本课程在计算机学科中与其他课程的关系如图l所示。
2 知识体系
数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作,涉及数据的逻辑结构、数据的存储结构和数据的运算。算法是程序的逻辑抽象,是解决某类客观问题的处理步骤。数据结构与算法呈相互依赖的关系,只有恰当地确立了问题的模型结构,才能选择和设计合
适的解决方法。数据结构与算法的知识体系如图2所示。
常见逻辑关系有:线性结构、树形结构、图结构和文件结构。常见的存储方法有:顺序方法、链接方法、索引方法、散列方法。建立在数据结构之上的有效运算是问题求解的核心。排序、检索是最经典的运算,为了加快检索速度往往需要预先建立索引。
整个数据结构与算法的知识结构可以划归为基础篇、数据结构篇和运算篇三大体系。
基础篇的核心内容是数据结构与算法的基本概念,对后续内容起到导引作用。内容包括数据结构与算法定义、抽象数据类型(Abstract Data Tvde,简称ADT)、算法复杂度等问题求解过程中需要考虑的因素。
数据结构篇是数据结构与算法课程的核心内容。介绍各种基本数据结构的特点、ADT、各种存储实现方法、相关的经典算法及其效率。以数据结构的逻辑结构为主线,按照线性结构(线性表、字符串、栈和队列)、树、图等深入展开,揭示出不同数据结构的区别和内在联系,并穿插介绍回溯、搜索、分治、贪心、动态规划等经典算法在各类数据结构中的应用。
运算篇主要介绍排序、检索、索引等经典算法。排序是广泛应用的运算,其时间效率要求很高,对排序算法进行深入讨论和研究,有助于了解算法设计的多样性。检索是面向用户的最终应用,一个系统的好坏往往体现在检索的效率和效果上,搜索引擎就是典型的应用。为了提高检索效率往往需要进行适当的排序和索引;为了较好地展示相关检索的结果,往往需要对检索结果排序后再呈现给用户。
高级数据结构篇介绍多维数组、广义表、字符树、高级二叉搜索树等。Patricia树、后缀树是目前热点研究的字符树,伸展树、红黑树是比平衡二叉树(AVL)更为实用的二叉搜索树(BST)。向学生介绍这些学科前沿的数据结构,加强课程的深度和广度,有助于拓宽学生的知识面,提高解决实际问题的能力。
二、课程的分层次教学基本定位和设计思路
在大学计算机专业教育背景下,分层次教学的定位是培养科学型、工程型、应用型三类人才。本教学实施方案,以学生为本,因材施教,进行多元化、个性化的分层次培养,让每种类型的学生都得到最大的收获。
1 科学型人才的理论教学
科学型人才的理论教学应该重视基础理论和核心技术以及创新意识和创新能力的培养。注重数据结构与算法设计和问题求解的知识体系,帮助学生建立数据结构与算法的思维方法,理解抽象的概念、复杂的算法。从问题求解的角度,培养学生选择合适的数据模型,设计合适的算法,运用数据结构与算法基本理论来分析和解决问题。
从理论、抽象和设计的三个层次展开数据结构与算法教学。对每种数据结构都从其数学特性入手,先介绍其抽象数据类型,即逻辑结构和基本运算;再讨论其不同的存储方法,与学生一起讨论研究不同存储实现下可能的算法实现;然后结合算法分析来讨论各种存储方法和算法的利弊,摒弃那些不适宜的方法。注重数据结构基本概念和抽象数据类型表述,尤其是ADT的信息封装和信息隐蔽,使得学生可以在不同的设计阶段采用不同的抽象数据类型作为设计的基础,在适当的抽象层次上考虑程序的结构和算法。对各种经典算法的设计方法进行深入介绍,例如系统地介绍回溯、搜索、分治、贪心、动态规划等方法,扩展介绍第k短路径、唯一支撑树、动态散列表等。
结合计算机科学技术的现代前沿研究课题,设计研究启发式教学案例,提供精选的理论和技术扩展阅读文献。引导学生从广度和深度上把握课程的知识体系,建立数据结构与算法的思维方法。通过扎实的经典基础理论训练,帮助学生灵活地运用问题抽象、数据抽象、算法抽象来分析问题,应用数据结构与算法来设计和实现相应的程序,完成创新能力和实践能力的训练。
2 工程型人才的理论教学
工程型人才的理论教学应重视培养基本的理论分析能力和综合设计实现能力。掌握“数据结构”中的概念技术,合理组织数据,高效处理数据的典型算法,培养学生面对实际问题时选择恰当数据结构和相应算法的能力,通过创新的变通、组合,提出合理的总体解决方案并付诸实现,提高学生上机协作解决较大规模实际问题的能力,为进一步的应用开发打下良好的基础。
构建概念表述、数据模型、设计算法三个层面的课