北京师范大学《数据结构》课程教学大纲一、课程基本信息
中文名称： 数据结构
英文名称：Data Structure
课程类别（公共任选课、学科基础课、专业方向课）：学科基础课
学分： 4学时：  48+32
建议开设学期：2  开课单位建议：信息科学与技术学院
主讲教师：
（姓名） 沈复兴（性别）
男
（职称）      （学科方向）
教授          计算机软件
郑新                  女                      副教授        计算机应用
肖永康                男                      讲师          计算机应用
二、课程目标：
本课程的主要目标是使学生深入了解数据结构的思想和数据结构的实现方法，特别是数据结构在实际工作中的应用和技术。本课程追求理论联系实际，实践教学与相应的教学内容相呼应。在形式上，灵活多样地采取了实践、拓展性学习、报告会等多种形式，目的在于加深学生对所学内容的理解，发展学生从事发展算法与程序设计研究和实践的能力，努力做到学以致用，同时激发学生的学习兴趣和主动参与精神，更好地掌握和运用所学习的知识。
三、课程内容与主要学习材料（含教材及参考书目）
课程内容：
第一章 绪论
1. 教学内容:
♦数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物理结构、算法等。
♦抽象数据类型。
♦描述算法的程序语言（C++）。
♦算法时间复杂度和空间复杂度的分析。
2. 教学目的及要求
♦掌握数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系等数据结构的基本概念；
♦了解数据类型、抽象数据类型、数据抽象和信息隐蔽原则以及面向对象这种数据抽象实现方法
♦了解算法的定义、算法的特性、算法的时间代价、算法的空间代价
♦掌握用C++语言描述算法的方法，能够使用C++语言编写程序
3.  教学重点
数据结构的概念；算法分析；C++语言。
4.  学时分配
本章共教授4学时.
第二章数组
1.  教学内容
♦线性表的基本概念
大学编程课是学什么的♦顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查、插入和删除；
使用顺序表的事例；顺序表复杂度分析
♦特殊矩阵的压缩存储：特殊矩阵定义、稀疏矩阵类定义、矩阵转置与快速转置、矩阵乘法与输出
♦字符串：字符串类型定义；字符串操作的实现；字符串的模式匹配
2.  教学目的及要求
♦了解线性表的逻辑结构特性，以及线性表的两种存储实现方式
♦熟练掌握顺序表的定义与实现，包括搜索、插入、删除算法的实现及其平均比较次数的计算，掌握应用顺序表作为集合的简单操作
♦了解稀疏矩阵的定义及其数组实现
♦掌握字符串的定义及实现
3.  教学重点
线性表的基本概念、顺序表的实现及应用
4.  教学难点
矩阵的快速转置及模式匹配改进
5.  教学时间分配
本章共教授4学时.
第三章链表
1．教学内容
♦单链表：单链表的结构；单链表的类定义；单链表中的查、插入与删除；带表头结点的单链表；单链表的游标类及静态链表
♦循环链表：循环链表的类定义及操作；用循环链表解约瑟夫问题；
♦多项式及其相加：多项式的链表表示类定义；多项式的加法
♦双向链表：双向链表的类定义及操作
♦稀疏矩阵：稀疏矩阵的正交链表表示法及建立和删除操作
2．教学目的及要求
♦了解链表与数组一样，是一种实现级结构。有动态链表和静态链表之分
♦了解链表有单链表、循环单链表、双向链表之分
♦了解单链表的结构、特点
♦熟练掌握单链表的类定义、构造函数、单链表的查、插入与删除算法
♦掌握带表头结点的单链表的优点和类定义及相应操作的实现
♦了解游标类的定义与实现
♦掌握循环链表的特点，循环链表的类定义，以及用循环链表解决问题的方法 ♦掌握双向链表的特点，双向链表的类定义及相关操作的实现，用双向链表解决问题的方法。
♦了解稀疏矩阵正交链表表示方法
3.  教学重点
单链表、循环链表以及双向链表的类定义、实现及应用
4.  教学难点
实现链表删除与插入操作时指针的变化以及特殊情况处理；稀疏矩阵正交
链表表示方法
5． 教学时间分配
本章共教授4学时.
第四章 栈与队列
１．教学内容
♦栈：栈的类型定义及特点；栈的顺序存储表示；栈的链接存储表示
♦栈的应用：回文验证、数制转换及表达式求值（后缀表达式求值；中缀表达式求值）
♦队列 ：队列数据类型定义及特点；队列的顺序存储表示；队列的链接存储表示；队列的应用举例
♦优先级队列：优先级队列的定义；优先级队列的存储表示
２． 教学目的及要求
♦熟练掌握栈的定义和特性，栈的顺序表示、链表表示以及相应操作的实现；特别注意在不同表示方式下栈空和栈满的条件
♦了解栈的不同应用，掌握后缀与中缀表达式计算方法和算法思路
♦熟练掌握队列的定义、特性，队列的顺序表示、链表表示以及相应操作的实现。
特别是循环队列中队头与队尾指针的变化情况
♦了解优先级队列的定义、特性，优先级队列的插入与删除算法
3．教学重点与难点
栈与队列的操作实现及表达式求值的方法
4.  教学时间分配
本章共教授4学时.
第五章递归
1.  教学内容：
♦栈与递归：递归定义与递归函数，递归问题求解与递归栈
♦递归与回溯：用回溯方法求解递归的两个典型应用——迷宫问题和八皇后问题 ♦广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广义表的访问算法；广义表的递归算法
2.  教学目的及要求:
♦掌握递归的概念
♦掌握递归过程的机制与利用递归工作栈实现递归的方法
♦了解迷宫问题和八皇后问题的递归求解思路及回溯方法
♦掌握利用递归解决问题的分治法和回溯法
♦掌握广义表的定义及其实现方法
♦掌握广义表的递归算法
3.教学重点
递归解决问题的思想及广义表的定义和操作
4.教学难点
递归到非递归的转换
5.  教学时间分配
本章共教授4学时.
第六章树和森林
1． 教学内容
♦树和二叉树：树的定义；树的术语；二叉树的定义；二叉树的性质；二叉树的顺序表示；二叉链表表示
♦二叉树遍历及应用：中序遍历；前序遍历；后序遍历；层次遍历
♦线索二叉树：线索；中序线索化二叉树
♦二叉搜索树：二叉搜索树的定义；二叉搜索树上的搜索；二叉搜索树的插入；
二叉搜索树的删除
♦二叉树的计数：卡特兰数的推导
♦堆：堆的定义；堆的建立；堆的插入与删除；堆的调整算法
♦树与森林：树的存储表示；森林与二叉树的转换；遍历树；遍历森林
♦霍夫曼树：路径长度；霍夫曼树；霍夫曼编码
2． 教学目的及要求
♦了解树的基本概念。包括树的定义、树的术语
♦掌握二叉树的概念、性质及二叉树的表示
♦熟练掌握二叉树的遍历方法及应用
♦了解线索二叉树的特性及寻某结点的前驱和后继的方法
♦熟练掌握二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法
♦掌握二叉树的计数方法，了解其推导
♦掌握树与二叉树的转换，树的遍历算法
♦掌握森林与二叉树的转换，森林的遍历算法
♦熟练掌握堆的定义，堆的建立、堆的插入与删除、堆的向上和向下调整等算法以及用来实现优先级队列的方法
♦掌握霍夫曼树的实现方法、构造霍夫曼编码的方法及带权路径长度的计算 3． 教学重点
二叉树的表示、存储实现以及操作；堆
4．教学难点
二叉树的计数及堆的调整
5． 教学时间分配
共讲授9课时
第七章：集合
1． 教学内容
♦集合：集合基本概念；集合的实现方式；用位向量实现整形集合；用顺序表实现集合
♦并查集：并查集的定义；并查集的实现
2． 教学的要求
♦掌握集合的基本概念及其表示方法，包括位数组及顺序表的表示及其相关操作的实现算法
♦掌握利用并查集实现集合的方法
3． 教学重点
集合的概念与实现
4． 教学时间分配
本章共教授2学时.
第八章图
1.  教学内容
♦图的基本概念：图的基本概念；图的抽象数据类型
♦图的存储表示：邻接矩阵；邻接表；邻接多重表
♦图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；关节点与重连通分量
♦最小生成树：kruskul算法；prim算法
♦单源最短路径问题：dijkstra算法
♦活动网络：AOV网络与拓扑排序；AOE网络与关键路径
2.  教学目的及要求
♦理解图的基本概念和图的抽象数据类型
♦掌握图的3种存储表示：邻接矩阵、邻接表和邻接多重表。对于前两种，要求掌握典型操作，如构造、求根、第一个邻接顶点、下一个邻接顶点等操作的实现算法
♦熟练掌握图的两种遍历算法与求解连通性问题的方法。包括深度优先搜索和广度优先搜索算法、求连通分量的方法(不要求算法)
♦理解求解关节点及构造重连通图的方法(不要求算法)
♦掌握构造最小生成树的Prim算法和Kruskal算法，要求理解算法
♦理解如何用Dijkstra方法求解单源最短路径问题(不要求算法)
♦熟练掌握活动网络的拓扑排序算法
♦掌握求解关键路径的方法
3． 教学重点
图的存储；图的遍历；构造图的最小生成树的方法；活动网络拓扑排序算
法
4．教学难点
求图的连通分量；构造最小生成树算法；求解单源最短路径问题
5.  教学时间分配
共占用5学时。
第九章排序
1.  教学内容
♦插入排序：直接插入排序；折半插入排序；链表插入排序；希尔排序
♦交换排序：起泡排序；快速排序
♦选择排序：直接选择排序；锦标赛排序；堆排序
♦归并排序：归并；迭代的归并排序算法；递归的链表归并排序
♦基数排序：多关键码排序；链式基数排序
2.  教学目的及要求
♦掌握排序的基本概念和性能分析方法
♦掌握插入排序、交换排序、选择排序、归并排序等内排序的方法及其性能分析方法
♦了解基数排序方法及其性能分析方法
3． 教学重点
排序算法及性能分析
4．教学难点
快速排序
5.  教学时间分配
共占用6学时。
第十章搜索
1.  教学内容
♦静态搜索结构：顺序搜索；基于有序顺序表的顺序搜索和折半搜索；静态树表的搜索；索引顺序表
♦动态搜索结构：AVL树（AVL树定义；平衡化旋转；AVL树的插入和删除；AVL 树高度）；B树（B树的定义；B树的插入；B树的删除；B+树）；键树的查 ♦散列：散列表；散列函数；处理溢出的方法；散列表分析
2.  教学目的及要求
♦熟练掌握静态搜索表的顺序搜索和折半搜索算法及其性能分析方法
♦掌握线性索引、静态索引树表的搜索和构造方法
♦掌握AVL树的平衡化旋转、构造、插入、删除时的调整方法及其性能分析
♦掌握B树、B+树的搜索和构造方法
♦掌握散列法，包括散列函数的构造、解决冲突的方法
3． 教学重点
基于有序顺序表的顺序搜索和折半搜索、AVL树、B树、散列表等一系列索引方法及性能分析
4．教学难点
动态搜索方法
5.  教学时间分配
共占用6学时。
教材：
♦优秀原版教材《Data Structures&Algorithm Analysis in C++》，MARK ALLEN WEISS，清华大学出版社；该书已由沈复兴和陈硕完成全书翻译即将出版。
学习材料：
1).教育部高教司推荐优秀信息科学技术国内经典教材《数据结构（用面向对象方法与

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。