数据结构教学大纲.docx
《数据结构教学大纲.docx》由会员分享，可在线阅读，更多相关《数据结构教学大纲.docx（14页珍藏版）》请在冰点文库上搜索。
数据结构教学大纲
《数据结构》课程教学大纲
一课程说明
1.课程基本情况
课程名称：
数据结构
英文名称：
DataStructure
课程编号：
2413213
开课专业：
计算机科学与技术
开课学期：
第3学期
学分/周学时：
5/5
课程类型：
专业基础必修课
2．课程性质（本课程在该专业的地位作用）
数据结构是一门研究非数值数据的数据的逻辑结构、数据的存储结构、数据的运算的学科，是计算机学科与技术专业的一门综合性较强的专业基础必修课程。
数据结构不仅是一般程序设计的基础，也是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。
3．本课程的教学目的和任务
使学生较熟练地掌握数据结构的基本概念、特性、存储结构及相关算法，熟悉它们在计算机科学中最基本的应用，能运用高级程序设计语言编写结构清晰、可读性好的算法及初步评价算法的能力，为后续课程的学习，以及计算机软件的研制和开发打下一定的理论基础及实践基础。
4．本课程与相关课程的关系、教材体系特点及具体要求
本课程先修课程为《离散数学》、《C程序设计》，后续课程为《操作系统》、《数据库》等。
讲授《数据结构》课程的教材在国内/外已形成了比较完整的体系，且有许多优秀者。
本课程教材的选择需包含线性表、栈和队列、串、数组（广义表）、树、图基本数据结构及其应用以及排序和查找的原理与方法，且有适当的拓展。
5.教学时数及课时分配
（1）理论学时分配
知识模块
主要内容
学时
分配
模块1：
数据结构的概念
数据结构的概念，抽象数据类型，算法和算法分析。
4
模块2：
线性表
线性表的定义与运算；线性表的顺序存储；线性表的链式存储。
8
模块3：
栈和队列。
栈的定义与运算；栈的顺序存储；栈的链式存储；队列的定义与运算；队列的顺序存储；队列的链式存储。
8
模块4：
串
串的定义与运算；串的顺序存储；串的链式存储。
6
模块5：
数组和广义表
数组的定义与运算；数组的顺序存储；数组的压缩存储；广义表、广义表存储结构。
8
模块6：
树
树的定义与基本术语；二叉树；线索二叉树；树、森林、二叉树的关系；哈夫曼树及其应用。
10
模块7：
图
图的定义与运算；图的存储结构；图的遍历；生成树；最短路径；拓扑排序；关键路径。
10
模块8：
查找
查找的基本概念；线性表的查找；树表的查找；哈希表的查找。
8
模块9：
排序
排序的基本概念；内部排序（插入、冒泡、快速、选择、归并、基数）；外部排序方法简介。
8
半期考试
2
课时合计
（2）实验学时分配
序号
实验名称
实验类型
实验
要求
每组
人数
学时
分配
1
整数的排序
验证
必做
1
2
2
单链表的建立
设计、综合性
必做
1
2
3
栈的建立
设计、综合性
必做
1
2
4
求顺序串的子串
设计、综合性
必做
1
2
5
稀疏矩阵的转置
设计、综合性
必做
1
2
6
用链式存储结构建立二叉排序树
设计、综合性
必做
1
4
7
图的深度优先搜索
设计、综合性
必做
1
4
8
折半查找
设计、综合性
选做
1
0
9
希尔排序
设计、综合性
选做
1
0
学时合计
二教材及主要参考书
教师可根据上述教学内容要求和实际情况选择合适教材，推荐使用教材：
[1]陈明.数据结构（C语言描述第2版）.北京:
高教出版社,2011-11
参考教材推荐:
[1]严蔚敏.数据结构及应用算法教程（修订版）.北京:
清华出版社,2011-05
[2]P.J.Deitel,H.M.Deitel.Chowtoprogram6thedition.NewJersey:
PearsonEducation,Inc,2010
三教学方法和教学手段说明
本课程教学难点在于数据存储结构、数据操作的描述都比较抽象，数据操作的实现难度比较大，为此，建议采用以下教学方法和手段：
1、教学方法
（1）课堂讨论式教学方法：
在教学过程中,对于给定问题引导学生讨论、思考可以用哪些数据结构组织数据？
何种数据结构组织较优？
同时讨论数据操作的算法如何设计？
这样可以培养学生的抽象思维、分析和解决问题的能力。
（2）启发式教学方法：
在教学过程中，积极启发学生如何对现有算法进行分析、设计和改进，这样可以培养学生创造能力及活学活用所学知识的能力。
（3）实践教学方法：
在教学过程中，引导学生进行大量的实践训练。
这样可以培养学生驾驭所学知识和把所学知识转化为实际应用的能力。
2、教学手段
充分运用多媒体课件、网络课件、板书、幻灯片等多样化的教学手段。
在教学过程中，使用多媒体课件进行辅助，突破学生难于理解的数据结构及比较复杂的算法，把抽象的数据结构在计算机中的存储直观的表示出来，把难以理解的算法思路及处理过程通过动画演示出来，变抽象为具体，化枯燥乏味为生动形象。
这样可以激发学生的学习兴趣，改善教学效果。
四成绩考核办法
1考核方式：
平时考核、期中考试、期末考试。
2综合成绩计算：
执行学校的规定。
五教学内容
模块1：
数据结构的概念（理论4学时，实验2学时）
一、教学目的
理解数据结构的基本概念、抽象数据类型的定义和表示方法、数据结构的逻辑结构和存储结构。
理解算法定义及其特性，掌握算法分析的基本方法。
二、教学重点
数据结构的基本概念、抽象数据类型的定义和表示方法、数据结构的逻辑结构和存储结构、算法定义及其特性、算法分析的基本方法。
三、教学难点
抽象数据类型的定义和表示方法、算法分析的基本方法。
四、讲授要求
重点讲授数据结构的抽象数据类型的定义和表示方法、数据结构的逻辑结构和存储结构以及二者的关系与区别。
五、讲授要点
数据结构及相关基本概念、抽象数据类型、算法概念及算法分析基本方法。
六、实验及实践要求
1、实验1名称：
整数的排序
2、实验类型：
验证性
3、学时分配：
2学时
4、每组人数：
1人
5、实验目的：
了解数据结构、算法、算法渐近时间复杂度的概念
6、实验内容及要求：
建立一个整型一维数组a[10]，并完成操作：
（1）用循环语句从键盘上为数组a赋值10个整数。
（2）对数据a进行升序排序。
（3）根据所写程序计算所采用算法的渐近时间复杂度。
模块2：
线性表（理论8学时，实验2学时）
一、教学目的
理解线性表的定义、基本运算、抽象数据类型、各种存储结构，掌握线性表基本运算在各种存储结构上的实现。
二、教学重点
线性表的定义、基本运算、抽象数据类型、线性表的各种链式存储结构，线性表的各种存储结构上的基本运算的实现。
三、教学难点
线性表的各种链式存储结构，线性表的各种存储结构上的基本运算的实现。
四、讲授要求
重点讲授线性表的各种存储结构及其上基本运算的实现。
五、讲授要点
线性表的定义、基本运算、抽象数据类型、各种链式存储结构，线性表的各种存储结构上的基本运算的实现。
六、实验及实践要求
1、实验2名称：
单链表的建立
2、实验类型：
设计性、综合性
3、学时分配：
2学时
4、每组人数：
1人
5、实验目的：
了解单链表的结构特点、描述方法及有关概念，掌握单链表建立的基本操作算法
6、实验内容及要求：
建立一个包括头结点和4个结点（6，5，4，8）的单链表，要求具有建立头结点、插入结点、删除结点、输出整个单链表的功能。
模块3：
栈和队列（理论8学时，实验2学时）
一、教学目的
理解栈和队列的定义、基本运算、抽象数据类型、各种存储结构，掌握栈和队列基本运算在各种存储结构上的实现。
二、教学重点
栈和队列的定义、基本运算、抽象数据类型、栈和队列的各种链式存储结构，栈和队列的各种存储结构上的基本运算的实现。
三、教学难点
栈和队列的各种链式存储结构，栈和队列的各种存储结构上的基本运算的实现。
四、讲授要求
重点讲授栈和队列的各种存储结构及其上基本运算的实现。
五、讲授要点
栈和队列的定义、基本运算、抽象数据类型、栈和队列的各种链式存储结构，栈和队列的各种存储结构上的基本运算的实现。
六、实验及实践要求
1、实验3名称：
栈的建立及入栈、出栈
2、实验类型：
设计性、综合性
3、学时分配：
2学时
4、每组人数：
1人
5、实验目的：
了解栈的结构特点及有关的概念，掌握链栈建立及入栈、出栈的基本操作算法
6、实验内容及要求：
建立一个栈，要求具有初始化栈、入栈、出栈的功能。
模块4：
串（理论6学时，实验2学时）
一、教学目的
理解串的定义、基本运算、抽象数据类型、各种存储结构，掌握串基本运算在各种存储结构上的实现。
二、教学重点
串的定义、基本运算、抽象数据类型、各种链式存储结构，串的各种存储结构上的基本运算的实现。
三、教学难点
串的各种存储结构，串的各种存储结构上的基本运算的实现。
四、讲授要求
重点讲授串的各种存储结构及其上基本运算的实现。
五、讲授要点
串的各种链式存储结构，串的各种存储结构上的基本运算的实现。
六、实验及实践要求
1、实验4名称：
求顺序串的子串
2、实验类型：
设计性、综合性
3、学时分配：
2学时
4、每组人数：
1人
5、实验目的：
了解串的有关概念及串和线性表的关系，掌握串的存储结构及串的基本运算
6、实验内容及要求：
在顺序存储结构下，求主串S中从第i个字符起，长度为k的子串。
当参数i和k满足约束条件时，使用函数返回所求子串；当不满足条件时，函数返回空值。
模块5：
数组和广义表（理论8学时，实验2学时）
一、教学目的
理解数组的定义、基本运算、抽象数据类型、各种存储结构，掌握数组基本运算在各种存储结构上的实现。
理解广义表概念，掌握广义表存储结构。
二、教学重点
数组的基本运算、抽象数据类型、各种链式存储结构，数组的各种存储结构上的基本运算的实现。
三、教学难点
数组的各种存储结构，数组的各种存储结构上的基本运算的实现。
四、讲授要求
重点讲授数组的各种存储结构及其上基本运算的实现。
五、讲授要点
数组的各种链式存储结构，数组的各种存储结构上的基本运算的实现。
六、实验及实践要求
1、实验5名称：
稀疏矩阵的转置
2、实验类型：
设计性、综合性
3、学时分配：
2学时
4、每组人数：
1人
5、实验目的：
熟悉数组的有关概念，掌握稀疏矩阵的三元组存储结构的转置方法。
6、实验内容及要求：
用三元组a[10][3]存储稀疏矩阵，然后将其转置并存储到b[3][10]，要求实现不带回溯的转置。
模块6：
树（理论10学时，实验4学时）
一、教学目的
理解树的定义、基本运算、抽象数据类型、各种存储结构，掌握树基本运算在各种存储结构上的实现。
二、教学重点
树的定义、基本运算、抽象数据类型、各种链式存储结构，树的各种存储结构上的基本运算的实现。
三、教学难点
树的各种存储结构，树的各种存储结构上的基本运算的实现。
四、讲授要求
重点讲授树的各种存储结构及其上基本运算的实现。
五、讲授要点
树的各种链式存储结构，树的各种存储结构上的基本运算的实现。
六、实验及实践要求
1、实验6名称：
用链式存储结构建立二叉排序树
2、实验类型：
设计性、综合性
3、学时分配：
4学时
4、每组人数：
1人
5、实验目的：
通过二叉排序树的建立来了解二叉树的定义及有关概念，熟悉二叉树的存储结构及性质。
6、实验内容及要求：
用链式存储结构建立一个二叉排序树，要求：
（1）使用bt指针指向根结点
（2）使用p指针指向当前已找到的结点
（3）使用q指针不断向下寻找新的结点
模块7：
图（理论10学时，实验4学时）
一、教学目的
理解图的定义、基本运算、抽象数据类型、各种存储结构，掌握图基本运算在各种存储结构上的实现。
二、教学重点
图的定义、基本运算、抽象数据类型、各种链式存储结构，图的各种存储结构上的基本运算的实现。
三、教学难点
图的各种存储结构，图的各种存储结构上的基本运算的实现。
四、讲授要求
重点讲授图的各种存储结构及其上基本运算的实现。
五、讲授要点
图的各种链式存储结构，图的各种存储结构上的基本运算的实现。
六、实验及实践要求
1、实验7名称：
图的深度优先搜索
2、实验类型：
设计性、综合性
3、学时分配：
4学时
4、每组人数：
1人
5、实验目的：
熟悉图的存储结构及邻接矩阵和邻接矩阵表等有关概念，掌握图的深度优先搜索方法。
6、实验内容及要求：
建立一个包含8个结点（数据域为整型数据）的图，要求图采用邻接矩阵作为存储结构。
模块8：
查找（理论8学时，实验0学时）
一、教学目的
理解查找及相关基本概念，掌握顺序查找、折半查找、分块查找方法。
了解树表查找及相关基本概念，了解二叉查找树、平衡二叉树、B-树的算法思想及方法。
理解和掌握哈希表、哈希函数、处理冲突的概念和方法。
二、教学重点
查找及相关基本概念，顺序查找、折半查找、分块查找方法。
树表查找及相关基本概念，二叉查找树、平衡二叉树、B-树的算法思想及方法。
哈希表、哈希函数、处理冲突的概念和方法。
三、教学难点
二叉查找树、平衡二叉树、B-树。
四、讲授要求
重点讲授顺序查找、折半查找、分块查找。
五、讲授要点
顺序查找、折半查找、分块查找。
六、实验及实践要求
1、实验8名称：
折半查找
2、实验类型：
设计性、综合性
3、学时分配：
鼓励学生在课外完成，但不作成绩计算
4、每组人数：
1人
5、实验目的：
了解折半查找的条件，熟悉并掌握折半查找的过程及方法。
6、实验内容及要求
由教师根据教学情况给出实验内容及要求。
模块9：
排序（理论8学时，实验0学时）
一、教学目的
理解排序及相关基本概念，掌握插入、交换、选择、归并、分配5类内部排序的基本思想、排序过程和实现方法。
了解外部排序的思想、方法。
二、教学重点
插入、交换、选择、归并、分配5类内部排序的基本思想、排序过程和实现方法。
三、教学难点
插入、交换、选择、归并、分配5类内部排序的实现方法。
四、讲授要求
重点讲授插入、交换、选择、归并、分配5类内部排序的实现方法。
五、讲授要点
插入、交换、选择、归并、分配5类内部排序的实现方法。
六、实验及实践要求
1、实验9名称：
希尔排序
2、实验类型：
设计性、综合性
3、学时分配：
鼓励学生在课外完成，但不作成绩计算
4、每组人数：
1人
5、实验目的：
熟悉希尔排序的基本思想，掌握希尔排序的排序过程及其实现方法。
6、实验内容及要求
由教师根据教学情况给出实验内容及要求。
升级会员 