《数据结构教（学）案C语言版》由会员分享，可在线阅读，更多相关《数据结构教（学）案C语言版（26页珍藏版）》请在金锄头文库上搜索。
1、WORD课程教案课程名称： 数据结构 授课教师：学习对象：任课时间：一、学生情况分析数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以与解决实际问题的能力。二、课程教学目标数据结构是计算机学科中一门核心专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以与对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以与有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。三、课程教学容第一章 绪论教学容
2、：1） 什么是数据结构2） 抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言3） 数据结构的抽象层次4） 算法定义5）性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；教学要求： 了解：数据结构基本概念与数据结构的抽象层次 了解：抽象数据类型概念 了解：算法的定义与算法特性 掌握：算法的性能分析与度量方法第二章 线性表教学容：1） 线性表的定义和特点2） 线性表的顺序存储与查找、插入和删除操作3） 线性表的链式存储与查找、插入和删除操作4） 使用线性表的实例教学要求：了解：线性表的定义和特点熟练掌握
3、：线性表的顺序存储结构的查找、插入和删除等基本操作熟练掌握：单链表、循环链表与双向链表的定义与实现掌握：熟练掌握单链表的应用方法第三章 栈和队列教学容：1） 栈：栈的抽象数据类型；栈的顺序存储表示；栈的链式存储表示2） 队列：队列的抽象数据类型；队列的顺序存储表示；队列的链式存储表示3） 队列的应用举例教学要求：熟练掌握：栈的定义与实现熟练掌握：队列的定义与实现掌握：能运用栈和队列解决简单实际问题第四章 串教学:容：1) 字符串的抽象数据类型2) 字符串操作的实现3) 字符串的模式匹配教学要求：熟练掌握：字符串的定义方式熟练掌握：字符串的各种操作的实现了解：字符串的模式匹配算法第五章 数组和广
4、义表教学:容：1) 数组的定义和初始化2) 作为抽象数据类型的数组的顺序存储方式教学要求：了解：作为抽象数据类型的数组的定义熟练掌握：顺序表的数组定义方式与实现第六章 树和二叉树教学容：1) 树和森林的概念：树的定义；树的术语；树的抽象数据类型；森林的概念2) 二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型3) 二叉树的表示：数组表示；链表存储表示4) 二叉树的遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例；二叉树的中序非递归算法5) 线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化6) 树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历7) 二叉树的
5、计数8) 霍夫曼树：路径长度；霍夫曼树；霍夫曼树编码教学要求：了解：树和森林的概念掌握：二叉树的概念、性质与二叉树的表示熟练掌握：二叉树的遍历方法掌握：线索化二叉树的特性与寻找某结点的前驱和后继的方法掌握：树和森林的实现与遍历方法掌握：二叉树的计数方法与从二叉树遍历结果得到二叉树的方法掌握：霍夫曼树的实现方法与霍夫曼编码的概念第七章 图教学容：1）图的基本概念：图的基本概念；图的抽象数据类型2）图的存储表示：邻接矩阵；邻接表；邻接多重表3）图的遍历与连通性；深度优先搜索；广度优先搜索；连通分量4）最小生成树：克鲁斯卡尔算法；普里姆算法教学要求：掌握：图的基本概念和图的存储表示熟练掌握：图的两种
6、遍历方法与求解连通性问题的方法掌握：构造最小生成树的Prim和Kruskal方法第九章 查找教学容：1) 静态查找表：顺序表的查找；有序表的查找；索引顺序表的查找2) 二叉排序树：二叉排序树上的搜索、插入和删除教学要求：熟练掌握：静态搜索表的顺序搜索和折半搜索方法熟练掌握：二叉搜索树的表示、搜索、插入、删除算法与其性能分析方法第十章 部排序 教学容：1) 概述2) 插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序3) 选择排序：直接选择排序；堆排序教学要求：掌握：排序的基本概念和性能分析方法掌握：插入排序、选择排序、等排序的方法与性能分析方法单元名称：第一讲：绪论 一、教学目标 1
7、.了解数据结构课程的体系结构2.掌握本章介绍的各种基本概念和术语3.了解数据结构的二元组表示4.掌握逻辑结构与物理结构之间的映像关系。二、重点与难点重点：数据结构的基本概念；逻辑结构与物理结构之间的映像关系。难点：逻辑结构与物理结构之间的映像关系。三、教学容与教学过程介绍本学期课程的容与安排本课程是计算机专业的重要专业课之一，主要介绍常用的数据结构以与相关算法。本课程主要讲授线性表、栈和队列、串、数组、树和二叉树、图、查找、排序等容。成绩考核方式为：期末成绩+平时成绩，其中期末成绩占70%，平时成绩占30%，平时成绩为：作业成绩+出勤率+上机成绩。讲授新课1.1 什么是数据结构 讲解：（数据结
8、构课程的研究背景）从计算机最初以数值计算为主到大量非数值计算出现引出数据结构。讲解：（数据结构课程的研究对象）例1-1图书馆的书目检索系统自动化问题。1-2计算机和人机对奕问题1-3多叉路口交通灯的管理问题总结：从以上三个例子可以看出，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树和图等之类的数据结构，这些都是数据结构课程的研究对象。因此，简单地说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以与它们之间的关系和操作等等的学科。介绍数据结构课程的发展以与与其他课程之间的关系。1.2基本概念和术语基本概念：数据、数据元素、数据项、数据对象、数据结构、结构（1）
9、常见基本结构（逻辑结构）：集合、线性结构、树形结构、图状结构或网状结构数据结构的形式定义： 数据结构一般用一个二元组来表示：Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上的关系的有限集表示一种数据结构，它由数据元素集合K和在K上定义的一种二元关系的集合R所组成。其中：是数据元素的有限集合，n为中数据元素的个数。是K上关系的有限集合，m为K上关系的个数，通常情况下m的取值为1。K上任何一个二元关系Rj是序偶的集合。对于Rj中的任一序偶（x，yK），称x为第一个元素（或y的前驱），y为第二个元素（或x的后继）。数据结构中的数据元素和数据元素之间的关系还可以用图形直观地
10、表示出来。图形中的每个结点对应一个数据元素，两结点之间带箭头的连线对应二元关系中的一个序偶，其中序偶的第一个元素称为弧尾，第二个元素称为弧头。举例讲解：例数据结构line=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=，,，。例数据结构tree=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=，。例数据结构graph=K，R，其中K=01，02，03，04，05，R=r，r=，。介绍常见数据结构（集合、线性结构、树型结构、图型结构）具体表示方式(2) 逻辑结构上述数据结构的定义是对操作对象的一种数学描述，是从操作
11、对象抽象出来的数学模型。结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。根据这种逻辑关系通常将数据结构划分为线性结构和非线性结构，其中非线性结构又分为树型结构和图型结构。(3) 物理结构数据结构在计算机中的表示（存储映象）称为数据的物理结构或存储结构，它涉与到数据元素与其相互关系在计算机部的表示形式。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。根据数据元素相互之间的关系在计算机中的表示形式将数据的物理结构划分为顺序结构和链式结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像的特点是借助指示元素存储
12、地址的指针表示数据元素之间的逻辑关系。注意：数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据的逻辑结构，而算法的实现依赖于采用的存储结构。（4）数据结构一般包括三方面容： 数据的逻辑结构、数据的存储结构、数据的运算 （举例讲解）小结：总结本讲的主要容四、作业布置见习题集单元名称：第二讲：线性表的类型定义，线性表的顺序存储一、教学目标 掌握线性表的顺序表示和实现二、重点与难点线性表的顺序表示和实现。三、教学过程的具体安排讲授新课2.1线性表的类型定义 线性表的定义：一个线性表是n 个数据元素的有限序列。其中每个数据元素的具体含义，在不同的情况下各不一样，但是同一线
13、性表中的元素必定具有一样特性，即属于同一数据对象。例如：26个英文字母表；学生健康情况登记表（图2.1）等。 例如线性表（a1,ai-1,ai,ai+1,an），称ai-1是ai的直接前驱元素， ai+1是 ai的直接后继。引导学生自己总结线性结构的特点。线性表的长度：线性表中元素的个数（n0），n=0为空表。 线性表中数据元素的位序（如数据元素ai在线性表中的位序为i）。抽象数据类型线性表的定义：讲解定义中的数据对象，数据关系以与基本操作（教材P19），重点讲解常用的基本操作含义。通过示例2-1，2-2讲解更复杂的基本操作，并分析时间复杂度。2.2 线性表的顺序表示和实现（1）线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。（2）顺序储存的地址关系：假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(a i+1)=LOC(ai)+l 线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l，其中LOC(a1)为线性表的基地址。（3）顺序表与其特点, 顺序储存结构是一种随机存取的存储结构。（4）线性表的动态分配顺序存储结构。 #define LI
