数据结构教案C语言版讲解.doc

课程教案 课程名称： 数据结构 授课教师：学习对象：任课时间： 一、学生情况分析 数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。 二、课程教学目标 《数据结构》是计算机学科中一门核心专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。 三、课程教学内容 第一章 绪论 教学内容： 什么是数据结构 抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言 数据结构的抽象层次 算法定义 5）性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法； 教学要求： 了解：数据结构基本概念及数据结构的抽象层次 了解：抽象数据类型概念 了解：算法的定义及算法特性 掌握：算法的性能分析与度量方法 第二章 线性表 教学内容： 线性表的定义和特点 线性表的顺序存储及查找、插入和删除操作 线性表的链式存储及查找、插入和删除操作 使用线性表的实例 教学要求： 了解：线性表的定义和特点 熟练掌握：线性表的顺序存储结构的查找、插入和删除等基本操作 熟练掌握：单链表、循环链表及双向链表的定义及实现 掌握：熟练掌握单链表的应用方法 栈和队列 教学内容： 栈：栈的抽象数据类型；栈的顺序存储表示；栈的链式存储表示 队列：队列的抽象数据类型；队列的顺序存储表示；队列的链式存储表示 队列的应用举例 教学要求： 熟练掌握：栈的定义及实现 熟练掌握：队列的定义及实现 掌握：能运用栈和队列解决简单实际问题 串 教学:内容： 字符串的抽象数据???型 字符串操作的实现 字符串的模式匹配 教学要求： 熟练掌握：字符串的定义方式 熟练掌握：字符串的各种操作的实现 了解：字符串的模式匹配算法 数组和广义表 教学:内容： 数组的定义和初始化 作为抽象数据类型的数组的顺序存储方式 教学要求： 了解：作为抽象数据类型的数组的定义 熟练掌握：顺序表的数组定义方式及实现 树和二叉树 教学内容： 树和森林的概念：树的定义；树的术语；树的抽象数据类型；森林的概念 二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型 二叉树的表示：数组表示；链表存储表示 二叉树的遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例；二叉树的中序非递归算法 线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化 树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历 二叉树的计数 霍夫曼树：路径长度；霍夫曼树；霍夫曼树编码 教学要求： 了解：树和森林的概念 掌握：二叉树的概念、性质及二叉树的表示 熟练掌握：二叉树的遍历方法 掌握：线索化二叉树的特性及寻找某结点的前驱和后继的方法 掌握：树和森林的实现及遍历方法 掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法 掌握：霍夫曼树的实现方法及霍夫曼编码的概念 图 教学内容： 1）图的基本概念：图的基本概念；图的抽象数据类型 2）图的存储表示：邻接矩阵；邻接表；邻接多重表 3）图的遍历与连通性；深度优先搜索；广度优先搜索；连通分量 4）最小生成树：克鲁斯卡尔算法；普里姆算法 教学要求： 掌握：图的基本概念和图的存储表示 熟练掌握：图的两种遍历方法与求解连通性问题的方法 掌握：构造最小生成树的Prim和Kruskal方法 第九章 查找 教学内容： 静态查找表：顺序表的查找；有序表的查找；索引顺序表的查找 二叉排序树：二叉排序树上的搜索、插入和删除 教学要求： 熟练掌握：静态搜索表的顺序搜索和折半搜索方法 熟练掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法 内部排序 教学内容： 概述 插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序 选择排序：直接选择排序；堆排序 教学要求： 掌握：排序的基本概念和性能分析方法 掌握：插入排序、选择排序、等内排序的方法及性能分析方法 单元名称：第 一 讲：绪论 一、教学目标 1.了解《数据结构》课程的体系结构 2.掌握本章介绍的各种基本概念和术语 3.了解数据结构的二元组表示 4.掌握逻辑结构与物理结构之间的映像关系。 二、重点与难点 重点：数据结构的基本概念；逻辑结构与物理结构之间的映像关系。 难点：逻辑结构与物理结构之间的映像关系。 三、教学内容与教学过程 介绍