《数据结构》课程教学大纲.pdf

课程教学大纲

课程代号:07021021
学时数:56+S16
适用专业：计算机科学与技术专业
一、本课程的性质、目的和任务
1。本课程的性质
数据结构是高等院校计算机各专业的核心课程之一,也是重要的专业基础课,主要介绍
和研究各种基本的数据结构及其应用.
2。本课程的目的
通过本课程的学习，使学生获得有关数据的各种逻辑结构、在存储器上的存储结构以
及相关运算的算法：并能够根据实际问题的需要选择和设计出相应运算的算法。为《操作
系统》、《数据库概论》等后续课程的学习及为应用软件特别是非数值应用软件的开发打
下良好的基础和时间基础。
3.本课程的任务
本课程的主要任务是培养学生:
(1)熟练掌握各种数据结构的特点、存储表示，操作算法及在计算机科学中基本应用。
（2)初步掌握算法的时间分析和空间分析的技巧。
(3)培养、训练学生选用合格的数据结构和使用类C语言编写质量高、风格好的应用
程序及初步评价算法程序的能力.
二、教学基本内容和要求
1。绪论
（1）教学目的与要求
熟悉数据结构的一些基本概念；
了解抽象数据类型的定义、表示和实现方法；
掌握C++语言的语句及算法描述的书写规则;
掌握计算语句频度和估算算法时间复杂度的方法。
(2）主要内容
数据、数据元素、数据对象、数据类型、数据结构等概念；抽象数据类型的定义、表
示和实现方法；描述算法的C++语言；算法设计的基本要求以及从时间和空间角度分析算
法的方法。
(3)重点、难点
重点：算法的时间和空间复杂性的评价；
难点:算法效率的度量。
2.线性表
(1）教学目的与要求
掌握线性表的定义和顺序存储结构；
掌握线性表的链式存储结构；
掌握线性表的插入、删除、归并等基本运算；
了解静态链表和一元多项式的有关知识。
(2）主要内容
线性表的顺序存储结构、线性表的链式存储结构；在线性表的两类存储结构（顺序的
和链式的)上实现基本操作;静态链表的存储结构和运算；一元多项式的抽象数据类型定义、
表示及加法的实现。
(3)重点、难点
重点：线性表的链式存储结构；
难点：静态链表的存储结构和运算。
3.集合、稀疏矩阵和广义表
（1）教学目的与要求
了解集合的定义和抽象数据类型;
了解集合的顺序存储结构和操作实现;
了解集合的链式存储结构和操作实现；
掌握稀疏矩阵的定义和存储结构；
掌握广义表的定义、存储结构和运算;
（2）主要内容
集合定义;集合的抽象数据类型；集合的顺序存储结构和操作实现；集合的链式存储结
构和操作实现；稀疏矩阵的定义；稀疏矩阵的存储结构；稀疏矩阵的运算；广义表的定义；
广义表的存储结构；广义表的运算。
(3）重点、难点
重点：稀疏矩阵的定义和存储结构；广义表的定义和存储结构；
难点：广义表的运算.
4.栈和队列
(1)教学目的与要求
掌握栈的定义、两种存储结构的表示方法及基本操作的实现;
掌握算术表达式的计算；
掌握队列的定义,链队列、循环队列的基本操作的实现算法;
了解栈在递归与非递归算法中的应用.
（2）主要内容
栈的表示和实现：进、出栈及双栈操作；算术表达式的计算；栈和递归过程；队列的
定义,链队列、循环队列及基本操作的实现；栈和队列在程序设计中的应用。
（3)重点、难点
重点：进、出栈操作；入、出队列操作；
难点:循环队列的实现，栈和递归过程。
5。树
（1)教学目的与要求
掌握树和二叉树的定义、性质、存储结构；
掌握二叉树的遍历和运算;
熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。
(2)主要内容
树的结构定义和基本操作;二叉树的定义、性质和存储结构；遍历二叉树的各种算法描
述；树和森林的定义、存储结构、与二叉树的转换、遍历。
(3)重点、难点
重点：二叉树的性质，二叉树的遍历；
难点：二叉树的运算。
6.特殊二叉树
（1)教学目的与要求
掌握二叉搜索树的定义、构造方法和查找方法；
掌握堆的定义;
掌握最优二叉树（哈夫曼树）的特性以及建立最优二叉树和哈夫曼编码的方法；
了解二叉树的线索化和利用线索进行遍历；
了解平衡二叉树的定义和调整。
（2)主要内容
二叉搜索树的定义、抽象数据类型和运算;堆的定义、抽象数据类型、存储结构和运算;
哈夫曼树;二叉树的线索化，利用线索进行遍历;平衡二叉树的定义和调整。
(3）重点、难点
重点：建立哈夫曼树和哈夫曼编码的方法；
难点:二叉树的线索化；平衡二叉树的调整.
7.图
（1)教学目的与要求
掌握图的定义和基本术语;
掌握图的各种存储结构及其构造算法，主要指邻接矩阵、邻接表和逆邻接表、边集数
组；
掌握图两种搜索路径的遍历：深度优先和广度优先搜索遍历。
（2)主要内容
图的定义和术语、图的存储结构，图的两种遍历策略：深度优先和广度优先搜索遍历，
非连通图的遍历。
(3)重点、难点
重点：图的邻接矩