数据结构.doc-西北师范大学数学与统计学院.doc

西北师范大学信息与计算科学专业 专业必修课程教学大纲 数据结构 一、说明 (一)课程性质 《数据结构》是计算机科学中一门综合性的专业基础课，也是信息与计算科学专业的专业必修课。 (二)教学目的 通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。具体达到以下基本要求： 1. 了解数据结构及其分类、数据结构与算法的密切关系。 2. 熟练掌握各种基本数据结构的概念、特点、存贮方式、算法及分析评估。 3. 掌握设计算法的步骤和算法分析方法。 4. 掌握数据结构在排序等常用算法中的应用。 5. 熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。 （三）教学内容 1. 引论 数据、数据???素、数据结构、数据类型、抽象数据类型的概念；算法、算法描述与算法分析。 2. 线性表 线性表的逻辑结构定义、基本操作和在两种存储结构中基本操作的实现；链表；用线性表表示一元多项式及实现稀疏多项式的相加等运算。 3. 栈和队列 栈和队列的结构特性、基本操作及在两种存储结构上基本操作的实现；栈和队列的应用、递归算法的设计。 4. 串 串的逻辑结构定义、串的基本运算及其实现;串的匹配算法。 5. 数组和广义表 数组的逻辑结构定义和存储方法；特殊矩阵和稀疏矩阵的压缩存储方法；广义表的逻辑结构和存储结构以及广义表运算的递归算法。 6. 树和二叉树 树的基本概念；二叉树的定义、性质、存储表示；二叉树的遍历；线索二叉树；森林和二叉树的相互转换；树的应用；哈夫曼树及哈夫曼编码。 7. 图 图的基本概念、存储表示（邻接矩阵、邻接表、十字链表，邻接多重表）；图的遍历、图的连通性问题；关键路径；最短路径。 8. 内部排序 插入排序、快速排序（交换排序）、选择排序、归并排序；排序的基本思想和算法分析。 (四)教学时数 总学时108，课程讲授学时72，实验学时36 (五)教学方式 讲授与上机实践相结合 二、本文 理论部分 第1章 概论 教学要点： 数据、数据元素、数据结构、数据类型、抽象数据类型的概念；算法、算法描述与算法分析。 教学时数： 3学时 教学内容： 数据结构的概念及内容 （1学时） 数据结构的基本概念；数据结构的内容；数据的逻辑结构和物理结构。 算法及其性能分析（2学时） 抽象数据类型的表示和实现；算法的特点；算法性能分析。 考核要求： 理解数据、数据元素、数据项、数据结构等概念； 区分数据的逻辑结构与物理结构； 了解评价算法优劣的标准及方法，并能分析算法的时间复杂度。 第2章 线性表 教学要点： 线性表的逻辑结构定义、基本操作和在两种存储结构中基本操作的实现；链表；用线性表表示一元多项式及实现稀疏多项式的相加等运算。 教学时数： 8学时 教学内容： 2.1 线性表的定义及抽象操作（1学时） 线性表的概念及逻辑特点；线性表的常用操作。 2.2 线性表的顺序存贮结构及算法。（2学时） 顺序表的存储类型定义；顺序表的初始化及插入、删除算法。 2.3 线性表的链式存贮结构及算法。（5学时） 单链表的存储结构及插入、删除算法；双链表的常用算法；循环链表的算法设计；链表的应用举例。 考核要求： 理解线性表的逻辑结构及其特点； 区分头结点和头指针； 掌握顺序表的存储方式及常用算法； 掌握单链表的存储方式及常用算法； 理解双链表、循环链表的存储方式及常用算法 能综合利用线性表解决诸如有序表的合并、多项式求和等实际问题。 第3章 栈和队列 教学要点： 栈和队列的结构特性、基本操作及在两种存储结构上基本操作的实现；栈和队列的应 用。 教学时数： 12学时 教学内容： 3.1 栈的定义与存储（3学时） 栈的定义与特点；栈的顺序存储结构及其算法实现；栈的链式存储结构及其算法实现。 3.2 栈的应用举例（3学时） 栈在编译系统中的应用；括号匹配问题；表达式的转换与求值。 3.3 递归（4学时） 递归的概念；递归算法的实现；递归算法的非递归模拟。 3.4 队列的定义与存储（2学时） 队列的定义与特点；队列的顺序存储结构及其算法实现；队列的链式存储结构及其算法实现。 考核要求： 了解栈与队列的特点； 掌握栈的顺序存储与链式存储的插入与删除算法； 掌握队列的顺序存储与链式存储的插入与删除算法； 能综合运用栈来实现表达式转换及求值等操作，理解栈的独特作用。 理解递归的概念及递归算法的特点，分析递归算法的执行过程