课程教案
课程名称：数据结构
授课教师：
学习对象：
任课时间：
一、学生情况分析
数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。
二、课程教学目标
《数据结构》是计算机学科中一门核心专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。
三、课程教学内容
第一章绪论
教学内容：
1）什么是数据结构
2）抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言
3）数据结构的抽象层次
4）算法定义
5）性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复
杂度度量；时间复杂度度量；时间复杂度的渐进表示法；
教学要求：
二叉树中序遍历非递归算法了解：数据结构基本概念及数据结构的抽象层次
了解：抽象数据类型概念
了解：算法的定义及算法特性
掌握：算法的性能分析与度量方法
第二章线性表
教学内容：
1）线性表的定义和特点
2）线性表的顺序存储及查、插入和删除操作
3）线性表的链式存储及查、插入和删除操作
4）使用线性表的实例
教学要求：
了解：线性表的定义和特点
熟练掌握：线性表的顺序存储结构的查、插入和删除等基本操作
熟练掌握：单链表、循环链表及双向链表的定义及实现
掌握：熟练掌握单链表的应用方法
第三章栈和队列
教学内容：
1）栈：栈的抽象数据类型；栈的顺序存储表示；栈的链式存储表示
2）队列：队列的抽象数据类型；队列的顺序存储表示；队列的链式存储表示
3）队列的应用举例
教学要求：
熟练掌握：栈的定义及实现
熟练掌握：队列的定义及实现
掌握：能运用栈和队列解决简单实际问题
教学：内容：
1)字符串的抽象数据类型
2)字符串操作的实现
3)字符串的模式匹配
教学要求：
熟练掌握：字符串的定义方式
熟练掌握：字符串的各种操作的实现
了解：字符串的模式匹配算法
第五章数组和广义表
教学：内容：
1)数组的定义和初始化
2)作为抽象数据类型的数组的顺序存储方式
教学要求：
了解：作为抽象数据类型的数组的定义
熟练掌握：顺序表的数组定义方式及实现
第六章树和二叉树
教学内容：
1)树和森林的概念：树的定义；树的术语；树的抽象数据类型；森林的概念
2)二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型
3)二叉树的表示：数组表示；链表存储表示
4)二叉树的遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例；二
叉树的中序非递归算法
5)线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化
6)树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历
7)二叉树的计数
8)霍夫曼树：路径长度；霍夫曼树；霍夫曼树编码
教学要求：
了解：树和森林的概念
掌握：二叉树的概念、性质及二叉树的表示
熟练掌握：二叉树的遍历方法
掌握：线索化二叉树的特性及寻某结点的前驱和后继的方法
掌握：树和森林的实现及遍历方法
掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法
掌握：霍夫曼树的实现方法及霍夫曼编码的概念
第七章图
教学内容：
1）图的基本概念：图的基本概念；图的抽象数据类型
2）图的存储表示：邻接矩阵；邻接表；邻接多重表
3）图的遍历与连通性；深度优先搜索；广度优先搜索；连通分量
4）最小生成树：克鲁斯卡尔算法；普里姆算法
教学要求：
掌握：图的基本概念和图的存储表示
熟练掌握：图的两种遍历方法与求解连通性问题的方法
掌握：构造最小生成树的Prim和Kruskal方法
教学内容：
1)静态查表：顺序表的查；有序表的查；索引顺序表的查
2)二叉排序树：二叉排序树上的搜索、插入和删除
教学要求：
熟练掌握：静态搜索表的顺序搜索和折半搜索方法
熟练掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法第十章内部排序
教学内容：
1)概述
2)插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序
3)选择排序：直接选择排序；堆排序
教学要求：
掌握：排序的基本概念和性能分析方法
掌握：插入排序、选择排序、等内排序的方法及性能分析方法
单元名称：第一讲：绪论
一、教学目标
1.了解《数据结构》课程的体系结构
2.掌握本章介绍的各种基本概念和术语
3.了解数据结构的二元组表示
4.掌握逻辑结构与物理结构之间的映像关系。
二、重点与难点
重点：数据结构的基本概念；逻辑结构与物理结构之间的映像关系。
难点：逻辑结构与物理结构之间的映像关系。
三、教学内容与教学过程
介绍本学期课程的内容及安排
本课程是计算机专业的重要专业课之一，主要介绍常用的数据结构以及相关算法。本课程主要讲授线性表、栈和队列、串、数组、树和二叉树、图、查、排序等内容。
成绩考核方式为：期末成绩+平时成绩，其中期末成绩占70%，平时成绩占
30%，平时成绩为：作业成绩+出勤率+上机成绩。
讲授新课
1.1什么是数据结构
讲解：（数据结构课程的研究背景）
从计算机最初以数值计算为主到大量非数值计算出现引出数据结构。
讲解：（数据结构课程的研究对象）
例1-1图书馆的书目检索系统自动化问题。
1-2计算机和人机对奕问题
1-3多叉路口交通灯的管理问题
总结：
从以上三个例子可以看出，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树和图等之类的数据结构，这些都是数据结构课程的研究对象。因此，简单地说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。
介绍数据结构课程的发展以及与其他课程之间的关系。
1.2基本概念和术语
基本概念：数据、数据元素、数据项、数据对象、数据结构、结构
（1）常见基本结构（逻辑结构）：集合、线性结构、树形结构、图状结构或网状结构数据结构的形式定义：
数据结构一般用一个二元组来表示：
Data_Structure=(D,S)
其中：D是数据元素的有限集，S是D上的关系的有限集
DS表示一种数据结构，它由数据元素集合K和在K上定义的一种二元关系的集合R所
组成。其中：
=n
i
K
≤
K
n
,
0|
{≥
}0
≤
i是数据元素的有限集合，n为DS中数据元素的个数。
m
j
=m
R
R
0|
}0
,
{≥
≤
≤
j是K上关系的有限集合，m为K上关系的个数，通常情况下m 的取值为1。
K上任何一个二元关系Rj是序偶的集合。对于Rj中的任一序偶<x，y>（x，y∈K），称x
为第一个元素（或y的前驱），y为第二个元素（或x的后继）。
数据结构中的数据元素和数据元素之间的关系还可以用图形直观地表示出来。图形中的每个结点对应一个数据元素，两结点之间带箭头的连线对应二元关系中的一个序偶，其中序偶的第一个元素称为弧尾，第二个元素称为弧头。

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