《数据结构》教案

页眉内容页眉内容抽查：系部主任（签字）年月日72抽查：系部主任（签字）年月日72页脚内容抽查：系部主任（签字）年月日72抽查：系部主任（签字）年月日72页脚内容教学单元（章节）：第一章：绪论1.1数据结构概念教学目的：理解学习数据结构的重要意义掌握数据结构的基本概念知识要点：数据结构、逻辑结构、物理结构、算法4种数据的存储结构、程序与数据结构技能要点：数据结构、4种基本的数据结构、4种数据的存储结构教学方法：讲授+演示教具及教学手段：投影作业布置情况：Pll；l、2课后分析与小结：本节课的重点：数据结构有关概念和术语难点：学习数据结构的意义审批：教研室主任（签字）年月日页眉内容页眉内容页眉内容页眉内容72页脚内容72页脚内容72页脚内容72页脚内容教学内容及过程板书或旁注第一章：绪论1.1数据结构概念1.1.1为什么要学习数据结构计算机处理问题的分类（1）数值计算问题（2）非数值性问题非数值问题求解算法+数据结构二程序数据结构：是指数据的逻辑结构和存储结构算法：是对数据运算的描述1.1.2有关概念和术语数据数据元素数据项数据结构：集合、线性、树型、图状数据结构：包括物理结构、逻辑结构数据的四种基本存储方法（1）顺序存储方法（2）链接存储方法（3）索引存储方法（4）散列存储方法页眉内容页眉内容页眉内容页眉内容抽查：系部主任（签字）年月日72抽查：系部主任（签字）年月日72页脚内容抽查：系部主任（签字）年月日72抽查：系部主任（签字）年月日72页脚内容教师授课教案教学单元（章节）：第一章：绪论1.2算法描述1.3算法分析教学目的：理解算法的定义、特性、描述方法掌握简单的时间复杂度的估计知识要点：算法的特性、描述方法、算法编制的质量要求、数据结构的基本操作、时间复杂度、空间复杂度、技能要点：描述算法、分析简单算法的时间复杂度教学方法：讲授+演示教具及教学手段：投影作业布置情况：pii；3、4课后分析与小结：本节课的重点：算法的特点和描述，算法分析

难点：算法时间复杂度的估计审批：教研室主任（签字）年月日页眉内容页眉内容页眉内容页眉内容教学内容及过程板书或旁注页脚内容72页眉内容页眉内容页眉内容页眉内容页眉内容页眉内容审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日72页脚内容审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日72页脚内容72页脚内容72页脚内容第一章：绪论1.2算法描述1.2.1算法特性⑴有穷性⑵确定性⑶可行性⑷输入⑸输出好的算法的特点（1）正确⑵可读（3）健壮（4）高效数据结构的基本操作：（1）查找（2）读取（3）插入（4）删除（5）修改1.2.2算法描述算法描述的种类：（1）框图/流程图算法（2）非形式算法（3）伪语言算法（4）高级语言算法1.3算法分析时间复杂度:解决某问题所花费的时间大小，即程序运行从开始到结束所需要的时间，记为T（n）空间复杂度：解决某问题的程序完全运行时所占用的存储空间大小，记为S（n）【例】算法MatrixMultidy的时间复杂度T（n）如（1.1）式所示，当n趋向无穷大时，显然有limTQi）/m3=（2m34-2h+1）/h3=2教师授课教案教学单元（章节）：C语言第七章：数组7.1一维数组的定义和引用7.2二维数组的定义和引用7.3字符数组教学目的：理解一维数组、二维数组、字符数组的定义掌握一维数组、二维数组、字符数组的引用和初始化方法掌握一维数组、二维数组、字符数组的简单应用程序知识要点：一维数组、二维数组、字符数组的定义、引用、初始化一维数组、二维数组、字符数组相关的简单程序技能要点：用数组来处理相关问题的程序教学方法：讲授+演示教具及教学手段：投影作业布置情况：P152；7.1P152；7.3P153；7.11P153；7.15课后分析与小结：本节重点：数组的定义、引用、初始化本节难点：用数组求解简单的问题页眉内容页眉内容页眉内容页眉内容抽查：系部主任（签字）年月日72抽查：系部主任（签字）年月日72页脚内容页脚内容页脚内容72教学内容及过程板书或旁注第七章数组7.1一维数组的定义和引用—维数组的定义—维数组的引用—维数组的初始化—维数组程序举例7.2二维数组的定义和引用7.2.1二维数组的定义7.2.2二维数组的引用7.2.3二维数组的初始化7.2.4二维数组程序举例7.3字符数组7.3.1字符数组的定义7.3.2字符数组的初始化7.3.3字符数组的引用7.3.5字符数组的输入输出教师授课教案教学单元（章节）：C语言第十章：指针10.1地址和指针的概念10.2变量的指针和指针变量教学目的：理解地址和指针的概念掌握指针变量的定义和引用知识要点：地址、指针、指针变量的定义和引用、指针变量作为函数参数技能要点：指针变量的定义和引用指针变量作为函数参数教学方法：讲授+演示教具及教学手段：投影作业布置情况：P278；10.1P278；10.2课后分析与小结：本节重点：指针的含义、指针变量的引用本节难点：指针变量的引用、指针变量作为函数参数审批：教研室主任（签字）年月日

教学内容及过程板书或旁注C语言第十早：指针10.1地址和指针的概念1.地址的概念2.指针的概念10.2变量的指针和指针变量10.2.1定义个指针变量1•定义扌日针变里的般形式：基类型*指针变量名2.定义指针变量的注意事项10.2.2指针变量的引用&——取址运算符。*指针运算符，10.2.3指针变量作为函数参数使个指针变量指向另个变量通过指针变量访问整型变量页眉内容页眉内容页眉内容页眉内容审批：教研室主任（签字）年月日审批：教研室主任（签字）年月日页脚内容72审批：教研室主任（签字）年月日审批：教研室主任（签字）年月日页脚内容72教师授课教案教学单元（章节）：C语言第十章：指针10.3.1指向数组元素的指针10.3.2通过指针引用数组元素10.4.1字符串的表现形式10.8指针运算小结教学目的：掌握通过指针引用数组元素理解字符串的表现形式掌握指针的相关运算知识要点：数组与指针、字符串与指针、指针运算技能要点：通过指针引用数组元素、字符串的表现形式指针的各种运算教学方法：讲授+演示教具及教学手段：投影作业布置情况：P279；10.6P279；10.9课后分析与小结：本节重点：指针运算、通过指针引用数组元素和字符串本节难点：通过指针引用数组元素、字符串抽查：系部主任（签字）年月日抽查：系部主任（签字）年月日页眉内容页眉内容页眉内容页眉内容抽查：系部主任（签字）年月日72抽查：系部主任（签字）年月日72页脚内容页脚内容页脚内容72教学内容及过程板书或旁注10.3数组与指针10.3.1指向数组元素的指针定义个指向数组元素的指针变量10.3.2通过指针引用数组元素数组兀素的引用可以用下标法：a[i]指针法：*(a+i)或*(p+i)10.4字符串与指针10.4.1字符串的表现形式用字符数组存放一个字符串用字符指针指向个字符串字符串常量和字符指针的初始化10.8指针运算小结10.8.1有关指针的数据类型的小结10.8.2指针运算小结指针变量的加减指针变量赋值3•指针变量的比较教师授课教案教学单元（章节）：C语言第十一章：结构体与共用体11.1-11.5.1结构体11.7.3处理动态链表所需的函数11.10用typedef定义类型教学目的：掌握结构体变量的定义、引用和初始化掌握处理动态链表所需的函数掌握用typedef定义类型知识要点：结构体变量、结构体数组，malloc函数calloc函数、free函数、typedef技能要点：结构体变量的定义、引用和初始化用typedef定义类型教学方法：讲授+演示教具及教学手段：投影作业布置情况：P318；11.1P318；11.5课后分析与小结：本节重点：结构体变量、处理动态链表所需的函数本节难点：结构体变量的引用和初始化、用typedef定义类型审批：教研室主任（签字）年月日

板书或旁注教学内容及过程板书或旁注第十一章：结构体与共用体11.1概述结的体癸翌定文一般黑式struct结杓体名{类型标识符成员名类型抨识符成员宓2：■}类型葆识特咸房畧恥11.2定义结构体类型变量的方法先定义结构体类型，再用类型标识去定义变量定义类型的同时定义变量3.直接定义结构体类型变量11.3结构体变量的引用结构体变量各成员的引用引用形式：结构体变量名•成员名结构体变量各成员的输入、输出11.4结构体变量的初始化11.5结构体数组结构体数组的定义2.结构体数组的初始化结构体数组stu的存储结构4.结构体数组的引用11.6指针与结构体指向结构体变量的指针指向结构体变量的指针与结构体变量的等价关系11・7用指针处理链表处理动态链表所需的函数内存分配函数原型：void*malloc(unsignedsize);内存分配函数原型：void*calloc(unsignedsize);内存释放函数原形：voidfree(void*p);11.10用typedef定义类型使用的一般形式：typedef原类型名新类型名；用typedef定义类型的方法(举例)先按定义数组变量形式书写：intn[100]；将变量名换成新类型名：intNUM[100]；在最前面加上typedef:typedefintNUM[100]；用新类型名来定义变量：NUMn；用typedef定义类型的说明：用typedef可以声明各种类型名，但不能用来定义变量。用typedef只是对已经存在的类型增加一个类型名，而没有创造新的类型。使用typedef有利于程序的通用与移植。页眉内容页眉内容页眉内容页眉内容页眉内容页眉内容页脚内容页脚内容72页脚内容页脚内容72抽查：系部主任（签字）年月日72抽查：系部主任（签字）年月日72页脚内容教师授课教案教学单元（章节）：第二章：线性表2.1线性表的逻辑结构2.2线性表的顺序存储及操作实现教学目的：理解顺序表的定义、特点及其主要操作掌握插入与删除算法中数据元素的平均移动次数知识要点：线性表的定义、特点、基本操作顺序表的定义、特点和存储顺序表的初始化、插入、删除、查找操作，应用举例技能要点：线性表的逻辑结构及基本操作线性表的顺序存储结构及其基本操作实现教学方法：讲授+演示教具及教学手段：投影作业布置情况：P37；lP38；6课后分析与小结：本节重点：线性表的定义、特点和顺序表的基本操作

本节难点：顺序表的插入和删除算法及其时间复杂度审批：教研室主任（签字）年月日

教学内容及过程板书或旁注2.1线性表的逻辑结构2.1.0线性表的实际例子2.1.1线性表的定义2.1.2线性表的基本操作初始化：Init_List(L)置空：SetnullList(L)求长度：Length_List(L)取表兀：Get_List(L,i)查找：Locate_List(L,x)插入：Insert_List(L,x)删除：Delete_List(L,i)2.2线性表的顺序存储结构2.2.1线性表的顺序存储结构1•顺序表的定义和特点2•顺序表的存储和类型定义2.2.2顺序表的基本算法实现初始化顺序表L插入删除按值查找页眉内容页眉内容页眉内容页眉内容审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日72页脚内容审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日72页脚内容教师授课教案教学单元（章节）：第二章：线性表2.3.1单链表2.3.2单链表上基本运算的实现教学目的：掌握单链表的定义、特点及存储结构掌握单链表的查找、插入与删除算法理解带首结点的单链表的优点知识要点：单链表的定义、特点、标识、结点结构和存储结构单链表的建立、求表长、查找、插入和删除算法技能要点：单链表的结点结构和存储结构单链表的查找、插入与删除算法教学方法：讲授+演示教具及教学手段：投影作业布置情况：P38；8课后分析与小结：本节重点：单链表的定义、特点和存储结构基本操作本节难点：单链表的查找、插入和删除算法页眉内容页眉内容页眉内容页眉内容抽查：系部主任（签字）年月日72抽查：系部主任（签字）年月日72页脚内容72页脚内容72页脚内容教学内容及过程板书或旁注2.3线性表的链式存储结构2.3.1单链表单链表的定义和特点单链表的存储结构和类型定义2.3.2单链表上的基本运算的实现建立单链表（1）头部插入法建立（2）尾部插入法建立求表长（1）带头结点的单链表（2）不带头结点的单链表查找操作（1）按序号查找（2）按值查找插入操作（1）后插节点（2）前插节点（3）插入运算删除操作（1）删除节点（2）删除运算教师授课教案教学单元（章节）：第二章：线性表2.3.3循环链表2.3.4双向链表教学目的：掌握单链表的定义、特点及存储结构掌握单链表的查找、插入与删除算法理解带首结点的单链表的优点知识要点：循环链表和双向链表的定义、特点、标识、结点结构两个循环链表的连接、双向链表中结点的插入和删除顺序表和链表的比较技能要点：两个循环链表的连接算法双向链表中结点的插入和删除教学方法：讲授+演示教具及教学手段：投影作业布置情况：P38；7、9课后分析与小结：本节课的重点：循环链表和双向链表的特点和基本操作难点：循环链表连接操作、双向链表的插入和删除审批：教研室主任（签字）年月日

教学内容及过程板书或旁注2.3.3循环链表循环链表的定义循环链表示意图带头结点的单循环链表仅设尾指针的单循环链表循环链表的特点循环链表的说明2.3.4双向循环链表双向链表的概念双链表示意图双链表的类型定义双向链表的操作1•双向链表中结点的前插2•双向链表中结点的删除五•顺序表和链表的比较教师授课教案教学单元（章节）：第三章：栈和队列3.1栈教学目的：掌握栈的定义、特点和存储结构掌握顺序栈和链栈的基本运算理解栈与递归的关系知识要点：栈的定义、特点、基本运算，顺序栈和链栈的主要操作上溢、下溢，栈空与栈满的条件，栈与递归问题技能要点：顺序栈和链栈的置空、判栈空、入栈、出栈操作教学方法：讲授+演示教具及教学手段：投影作业布置情况：P63；l、3、4课后分析与小结：本节课的重点：顺序栈和链栈的基本操作

难点：栈与递归问题审批：教研室主任（签字）年月日页眉内容页眉内容页眉内容页眉内容抽查：系部主任（签字）年月日72抽查：系部主任（签字）年月日72页脚内容页脚内容页脚内容72教学内容及过程板书或旁注第三章：栈和队列3.1栈3.1.1栈的定义和基本运算1•栈的定义栈：是限制仅在表尾进行插入和删除的线性表。2.基本运算初始化栈：构在一个空栈置空栈：将S置成空栈入栈：在栈顶插入一个新兀素X出栈：删除(弹出)栈S的顶部元素取栈顶)：取栈S的顶部元素判断空栈Empty_Stack(S):空栈返回13.1.2栈的存储实现和运算实现1•顺序栈顺序栈的定义顺序栈基本运算⑴置空栈⑵判空栈⑶入栈⑷出栈3.1.2栈的存储实现和运算实现2.链栈链栈的定义链栈基本运算⑴置空栈⑵判空栈⑶入栈⑷出栈3.1.3栈与递归的实现1•具有递归特性的问题递归定义的数学函数递归数据结构的处理递归求解方法2.递归算法的设计方法与递归过程的实现应用递归算法的前提Hanoi塔问题的递归函数Fibonacci数列的递归算法教师授课教案教学单元（章节）：第三章：栈和队列3.2栈的应用举例3.3队列3.4队列应用举例

教学目的：掌握队列的定义、特点和存储结构

掌握循环队列和链队列的基本运算

理解循环队列的意义和队列的应用知识要点：队列的定义、特点、存储结构、基本运算循环队列产生的原因，循环队列和链队列的主要操作假溢出，循环队列队空与队满的条件技能要点：循环队列队空与队满的条件，循环队列和链队列的入队、出队、判队空操作教学方法：讲授+演示教具及教学手段：投影作业布置情况：P63；2、5、9课后分析与小结：本节课的重点：循环队列和链队列的基本操作

难点：栈的应用、循环队列审批：教研室主任（签字）年月日

教学内容及过程板书或旁注第三章：栈和队列3.2栈的应用举例数制转换表达式求值3.3队列3.3.1队列的定义和基本运算队列的定义和特点队列结构的基本操作Init_Queue(Q)将Q置为一个空队列In_Queue(Q,x)插入兀素x为队Q的新队尾兀素Out_Queue(Q,x)删除Q的队头元素，并返回其值Front_Queue(Q,x)返回Q的队头兀素Empty_Queue(Q)判队空3.3.2队列的存储和运算实现1.顺序队列：定义、特点和存储结构2•循环队列：定义、存储结构和基本操作3.链队列定义、特点和存储结构基本操作3.4队列应用举例教师授课教案教学单元（章节）：第四章：串和数组4.1串教学目的：掌握串的定义、特点、相关术语和基本运算了解串的存储结构及其基本运算实现知识要点：串的定义、特点、相关术语和基本运算串的顺序存储结构和堆分配存储结构技能要点：串的基本运算定长串连接、求子串和串比较操作教学方法：讲授+演示教具及教学手段：投影作业布置情况：P78；2、3课后分析与小结：本节重点：串的定义、存储结构和基本运算本节难点：串连接、求子串和串比较算法审批：教研室主任（签字）年月日教学内容及过程板书或旁注第四章：串和数组4.1串4.1.1串的基本概念串的定义术语4.1.2串的基本运算求串长串赋值串连接求子串串比较串定位插入⑻删除(9)串替换4.1.2串的存储结构串的定长顺序存储结构堆分配存储结构定长顺序串基本运算的实现串连接子串串比较教师授课教案教学单元（章节）：第四章：串和数组4.2数组教学目的：了解数组的逻辑存储结构和内存映像了解稀疏矩阵的定义及其数组实现知识要点：数组与线性表、数组的逻辑存储结构和内存映像

稀疏矩阵的定义、压缩存储方法、转置技能要点：数组的内存映像、数组元素地址的计算稀疏矩阵的存储、转置教学方法：讲授+演示教具及教学手段：投影作业布置情况：P78；5、6课后分析与小结：本节重点：数组的逻辑结构和物理结构、稀疏矩阵本节难点：稀疏矩阵的压缩方法审批：教研室主任（签字）年月日

教学内容及过程板书或旁注第四章：串和数组4.2数组4.2.1数组的逻辑结构1维数组2维数组4.2.2数组的内存映像存储方式以行为主以列为主数组物理地址的计算1维数组物理地址计算函数表达式2维数组物理地址计算函数表达式4.2.3稀疏矩阵定义特殊矩阵稀疏矩阵的压缩存储教师授课教案教学单元（章节）：第五章：树和二叉树5.1树的概念和基本操作5.2.1二叉树的基本概念5.2.2二叉树的主要性质教学目的：掌握树的定义、特点和相关术语理解树的基本操作掌握二叉树的定义、相关概念和主要性质知识要点：树的定义、特点、相关术语和基本操作二叉树、完全二叉树、满二叉树的定义完全二叉树、满二叉树的性质技能要点：树的相关术语、树的遍历二叉树、完全二叉树、满二叉树二叉树的结点个数、完全二叉树的深度教学方法：讲授+演示教具及教学手段：投影作业布置情况：P107；1、2、8、9课后分析与小结：本节重点：树和二叉树的相关概念、二叉树的性质本节难点：二叉树的主要性质审批：教研室主任（签字）年月日

教学内容及过程板书或旁注第五章：树和二叉树5.1树的概念和基本操作5.1.1树的定义和相关木语1•树的定义2.相关术语5.1.2树的基本操作Initiate(t)初始化一棵空树t。Root(x)求结点x所在树的根结点。Parent(t,x)求树t中结点x的双亲结点。Child(t,x,i)求树t中结点x的第i个孩子结点。RightSibling(t,x)求树t中结点x的第一个右边兄弟结点。Insert(t,x,i,s)把以s为根结点的树插入到树t中作为结点x的第i棵子树。Delete(t,x,i)在树t中删除结点x的第i棵子树。Traverse(t)是树的遍历操作，访问每个结点。5.2二叉树5.2.1二叉树的基本概念1•二叉树2.二叉树的相关概念：满二叉树、完全二叉树5.2.2二叉树的主要性质性质1：层数与节点的关系性质2：深度与节点的关系性质3：非空二叉树的度为2的结点与叶子节点的关系性质4：完全二叉树的深度与节点的关系性质5：完全二叉树的相关性质页眉内容页眉内容页眉内容页眉内容审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日72页脚内容审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日72页脚内容教师授课教案教学单元（章节）：第五章：树和二叉树5.2.3二叉树的基本操作与存储实现5.2.4二叉树的遍历教学目的：掌握一叉树的2种存储结构理解二叉树的基本操作掌握二叉树的遍历方法知识要点：二叉树的顺序存储、二叉链表存储、三叉链表存储二叉树的基本操作先序遍历、中序遍历、后序遍历、层次遍历技能要点：二叉树的顺序存储、二叉树链式存储的存储结构先序遍历、中序遍历、后序遍历、层次遍历二叉树的过程教学方法：讲授+演示教具及教学手段：投影作业布置情况：P107；3、4、5、6课后分析与小结：本节重点：二叉树的存储结构和遍历方法本节难点：先序、中序、后序遍历二叉树页眉内容页眉内容页眉内容页眉内容页脚内容页脚内容72页脚内容页脚内容72教学内容及过程板书或旁注第五章：树和二叉树5.2.3二叉树的基本操作与存储实现二叉树的顺序存储结构二叉树的链式存储结构二叉链表存储三叉链表存储二叉树的基本操作Initiate(bt)Create(x,lbt,rbt)InsertL(bt,x，parent)DeleteL(bt,parent)InsertR(bt,x，parent)DeleteR(bt,parent)serch(bt,x)Traverse(bt)5.2.4二叉树的遍历先序遍历中序遍历后序遍历层次遍历页眉内容页眉内容页眉内容页眉内容审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日72页脚内容审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日72页脚内容教师授课教案教学单元（章节）：第五章：树和二叉树5.3树和森林教学目的：理解树的3种存储结构掌握树、森林与二叉树的转换方法掌握树和森林的遍历方法知识要点：树的双亲表示法、孩子链表表示法、孩子兄弟表示法树和森林转换为二叉树、二叉树转换为树和森林树的先根遍历、后根遍历，森林的先序遍历、后序遍历技能要点：二叉树的顺序存储结构、二叉树链式存储的存储结构树、森林与二叉树的转换过方法、树和森林的遍历教学方法：讲授+演示教具及教学手段：投影作业布置情况：P108；7、15、16课后分析与小结：本节重点：树、森林与二叉树的转换、树和森林的遍历本节难点：树的存储树、森林与二叉树的转换页眉内容页眉内容页眉内容页眉内容页脚内容页脚内容72页脚内容页脚内容72教学内容及过程板书或旁注第五章：树和二叉树5.3树和森林5.3.1树的存储双亲表示法孩子链表示法孩子兄弟表示法5.3.2树、森林与二叉树的转换树转换为二叉树森林转换为二叉树二叉树转换为树和森林5.3.3树和森林的遍历树的遍历1）先根遍历2）后根遍历森林的遍历（1）先序遍历（2）后序遍历页眉内容页眉内容页眉内容页眉内容抽查：系部主任（签字）年月日72抽查：系部主任（签字）年月日72页脚内容页脚内容页脚内容72教师授课教案教学单元（章节）：第五章：树和二叉树5.4最优二叉树——哈夫曼树教学目的：理解哈夫曼树的相关定义掌握最优二叉树的构建方法掌握哈夫曼编码的定义和实现过程知识要点：哈夫曼树、带权路径长度、哈夫曼编码、等长编码、不等长编码技能要点：构造哈夫曼树设计哈夫曼编码教学方法：讲授+演示教具及教学手段：投影作业布置情况：P109；20、21课后分析与小结：本节重点：最优二叉树和哈夫曼编码的构造方法本节难点：带权路径、哈夫曼编码审批：教研室主任（签字）年月日教学内容及过程板书或旁注第五章：树和二叉树5.4最优二叉树哈夫曼树5.4.1哈夫曼树的基本概念1•哈夫曼树的概念2•权值3.带权路径长度5.4.2哈夫曼树的构造算法1•哈夫曼树的构造步骤5.4.3哈夫曼编码等长编码不等长编码3•哈夫曼编码的概念4•哈夫曼编码的构造过程5.4.4哈夫曼编码的算法实现1•哈夫曼编码的算法思路2•哈夫曼编码的算法实现教师授课教案教学单元（章节）：第六章：图6.1图的基本概念6.2图的存储表示教学目的：掌握图的定义和相关术语理解图的基本操作掌握图的两种存储结构知识要点：图、无向图、有向图、完全图、度、入度、出度、权和网路径、回路、子图、连通图、强连通图、生成树图的基本操作、邻接矩阵、邻接表技能要点：图的相关术语、图的邻接矩阵的表示图的邻接表的表示教学方法：讲授+演示教具及教学手段：投影作业布置情况：P138；l、2、4课后分析与小结：本节重点：图的相关术语和存储表示本节难点：邻接矩阵、邻接表审批：教研室主任（签字）年月日

教学内容及过程板书或旁注第六章：图6.1图的基本概念6.1.1图的定义和术语定义相关术语1）有向图、无向图、完全图2）顶点、边、弧、弧头、弧尾3）度、入度、出度4）权和网5）路径和路径长度、回路、简单路径、简单回路6）子图、连通图、强连通图7）连通的、连通分量、强连通分量8）生成树、生成森林6.1.2图的基本操作（I）Creatgraph（G）（2）DestroyGraph（G）（3）GetVex（G,v）（4）PutVex（G,v，value）（5）Insertvex（G，v）（6）Deletevex（G,v）（7）InsertArc（G，v，u）（8）DeleteArc（G，v，u）（9）DFSTraverse（G，v）（10）BFSTtaverse（G，v）（II）Locatevex（g，v）（12）FiirstAdjvex（g，v）（13）nextAdjvex（g，v，w）6.2图的存储表示6.2.1邻接矩阵邻接矩阵存储结构的定义表示方法6.2.2邻接表邻接表存储结构的定义表示方法教师授课教案教学单元（章节）：第六章：图6.3图的遍历6.4.1最小生成树教学目的：掌握图的两种遍历方法理解最小生成树的的相关概念掌握用Prim算法构造最小生成树的过程知识要点：深度优先搜索、广度优先搜索最小生成树、Prim算法思路技能要点：深度优先搜索遍历、广度优先搜索遍历用Prim算法构造最小生成树教学方法：讲授+演示教具及教学手段：投影作业布置情况：P138；3、5课后分析与小结：本节重点：图的两种遍历、最小生成树本节难点：用Prim算法构造最小生成树审批：教研室主任（签字）年月日页眉内容页眉内容页眉内容页眉内容抽查：系部主任（签字）年月日72抽查：系部主任（签字）年月日72页脚内容页脚内容页脚内容72教学内容及过程板书或旁注第六章：图6.3图的遍历6.3.1深度优先搜索深度优先搜索的定义深度优先搜索的算法实现6.3.2广度优先搜索广度优先搜索的定义广度优先搜索的算法实现6.4图的应用6.4.1最小生成树1.最小生成树的基本概念2.构造最小生成树的Prim算法Prim算法的基本思想Prim算法的基本步骤Prim算法的C语言描述教师授课教案教学单元（章节）：第六章：图最短路径拓扑排序教学目的：理解最短路径问题和拓扑排序的意义了解用Dijkstra算法求单源最短路径了解拓扑排序的方法知识要点：最短路径问题、Dijkstra算法的基本思想、有向无环图、AOV网、拓扑排序的步骤技能要点：用Dijkstra算法求单兀最短路径拓扑排序算法教学方法：讲授+演示教具及教学手段：投影作业布置情况：P139；6课后分析与小结：本节重点：最短路径问题和拓扑排序本节难点：Dijkstra算法、拓扑排序算法审批：教研室主任（签字）年月日

教学内容及过程板书或旁注第六章：图6.4图的应用6.4.2最短路径1.最短路径问题2.单源最短路径3.Dijkstra算法的思想4.Dijkstra算法的C语言实现6.4.3拓扑排序1.有向无环图2.AVO网3.拓扑排序4.拓扑排序的基本步骤5.拓扑排序的算法思想教师授课教案教学单元（章节）：第七章查找7.1基本概念和术语7.2静态查找表教学目的：了解查找的概念和静态查找表结构理解顺序查找和折半查找及其性能分析方法知识要点：关键码、查找表、平均查找长度顺序查找、有序表的折半查找、分块查找技能要点：顺序查找、有序表的折半查找和分块查找算法的基本思想教学方法：讲授+演示教具及教学手段：投影作业布置情况：P167：1、3课后分析与小结：本节重点：顺序查找、折半查找和分块查找算法本节难点：折半查找算法的基本思想审批：教研室主任（签字）年月日页眉内容页眉内容页眉内容页眉内容页脚内容页脚内容72页脚内容页脚内容72教学内容及过程板书或旁注第七章查找7.1基本概念和术语1.关键码2.查找表3•查找4.平均查找长度7.2静态查找表7.2.1静态查找表结构7.2.2顺序查找1）基本思想2）算法实现3）性能分析7.2.3有序表的折半查找1）基本思路2）算法实现3）性能分析7.2.4分块查找1）基本思路2）性能分析页眉内容页眉内容页眉内容页眉内容抽查：系部主任（签字）年月日72抽查：系部主任（签字）年月日72页脚内容页脚内容页脚内容72教师授课教案教学单元（章节）：第七章查找7.4哈希表教学目的：理解哈希方法理解冲突处理方法知识要点：哈希表和哈希方法、常用的哈希函数冲突处理方法、哈希表的查找和性能分析技能要点：哈希函数的比较、解决地址冲突的处理方法教学方法：讲授+演示教具及教学手段：投影作业布置情况：P167：6课后分析与小结：本节重点：常用的哈希函数、冲突处理方法本节难点：冲突处理方法、哈希表的查找和性能分析审批：教研室主任（签字）年月日

教学内容及过程板书或旁注第七章查找7.4哈希表7.4.1哈希表和哈希方法7.4.2常用的哈希函数直接定址法除留余数法数字分析法平方取中法折叠法7.4.3冲突处理方法开放定址法（1）线性探测法（2）二次探测法（3）双哈希函数探测法拉链法3•建立公共溢出区7.4.4哈希表的查找及其分析1•哈希表的查找算法2•哈希表的性能分析教师授课教案教学单元（章节）：第八章排序8.1基本概念8.2简单排序方法教学目的：理解排序的基本概念掌握插入排序、简单选择排序的方法知识要点：排序的基本概念和性能分析直接插入排序、冒泡排序、简单选择排序技能要点：直接插入排序、冒泡排序和简单选择排序的性能分析教学方法：讲授+演示教具及教学手段：投影作业布置情况：P186：1课后分析与小结：本节重点：冒泡排序算法、直接插入排序算法

本节难点：冒泡排序算法、简单选择排序算法审批：教研室主任（签字）年月日

教学内容及过程板书或旁注第八章排序8.1基本概念排序内排序3•外排序8.2简单排序方法8.2.1直接插入排序直接插入排序方法的思路直接插入排序算法实现直接插入排序效率分析8.2.2冒泡排序冒泡排序方法的思路冒泡排序算法实现冒泡排序效率分析8.2.3简单选择排序简单选择排序方法的思路简单选择排序算法实现简单选择排序效率分析教师授课教案教学单元（章节）：第八章排序8.3快速排序8.5归并排序8.7排序方法的比较和讨论教学目的：理解快速排序和归并排序的方法及性能分析

了解主要排序方法各自的特点知识要点：快速排序、两路归并的迭代算法两路归并的递归算法、主要排序方法各自的特点技能要点：快速排序、两路归并的迭代算法两路归并的递归算法、排序方法的比较教学方法：讲授+演示教具及教学手段：投影作业布置情况：P186：l、2课后分析与小结：本节重点：两路归并算法、快速排序算法

本节难点：两路归并算法、快速排序算法审批：教研室主任（签字）年月日页眉内容页眉内容页眉内容页眉内容页脚内容页脚内容72页脚内容页脚内容72教学内容及过程板书或旁注第八章排序8.3快速排序1•快速排序的基本思路2•快速排序算法实现3•快速排序的过程示意4•快速排序效率分析8.5归并排序归并排序的基本思路归并排序算法实现1）两路归并的迭代算法2）两路归并的递归算法归并排序的过程示意归并排序效率分析8.7排序方法的比较和讨论从从算法的时间复杂度、空间复杂度和算法所需的辅助空间三个方面来比较从排序方法的稳定性角度对各种排序方法加以比较。页眉内容页眉内容页眉内容页眉内容抽查：系部主任（签字）年月日抽查：系部主任（签字）年月日页脚内容72页脚内容页脚内容72教师授课教案教学单元（章节）：实验1对线性表进行顺序存储的操作的实现教学目的：1.掌握线性表的抽象数据类型。2.掌握线性表的顺序存储及相关算法。知识要点：用C语言采用顺存存储结构定义线性表对线性表顺序存储的各种操作的实现技能要点：用C实现线性表顺序存储的基本操作：插入、删除、查找等教学方法：讲授+演示+实验教具及教学手段：PC机、TurboC2.0作业布置情况：上机实验课后分析与小结：本节重难点：用C实现线性表顺序存储的基本操作审批：教研室主任（签字）年月日

教学内容及过程板书或旁注实验内容：用C语言实现线性表顺序存储结构的创建、插入、删除、查找、合并等算法。1•顺序线性表的定义建立顺序线性表求线性表长度查找数据元素数据元素插入数据元素删除排序，从小到大教师授课教案教学单元（章节）：实验2对线性表进行链式存储的操作的实现教学目的：1.掌握线性表的抽象数据类型。2.掌握线性表的链式存储及相关算法。知识要点：用C语言采用链式存储结构定义线性表对线性表链式存储的各种操作的实现技能要点：用C实现线性表链式存储的基本操作：插入、删除、查找等教学方法：讲授+演示+实验教具及教学手段：PC机、TurboC2.0作业布置情况：上机实验课后分析与小结：本节重难点：用C实现线性表链式存储的基本操作审批：教研室主任（签字）年月日

教学内容及过程板书或旁注实验内容：用C语言实现线性表链式存储结构的创建、插入、删除、查找、排序等算法。单链表的定义头输入法建立单链表插入结点删除结点查找兀素排序查找单链表结点逆置教师授课教案教学单元（章节）：实验3栈及栈的应用实验教学目的：1.掌握栈的抽象数据类型。掌握实现栈的各种操作的算法。理解栈与递归的关系。知识要点：栈的每种操作在顺栈和链栈上的实现算法用C描述中缀换后缀算法技能要点：栈的每种操作在顺栈和链栈上的实现算法用c描述中缀换后缀算法教学方法：讲授+演示+实验教具及教学手段：PC机、TurboC2.0作业布置情况：上机实验课后分析与小结:本节重难点：栈的每种操作在顺栈和链栈上的实现算法审批：教研室主任（签字）年月日教学内容及过程板书或旁注实验内容：用C语言实现顺序栈和链栈存储结构的主要算法。用C描述中缀换后缀算法C语言实现顺序栈的定义、创建、置空、判栈空算法C语言实现顺序栈的出栈、入栈、查找算法C语言实现链栈的定义、创建、置空、判栈空算法C语言实现链栈的出栈、入栈、查找算法C语言实现中缀表达式转化成后缀表达式并求值教师授课教案教学单元（章节）：实验4队列及队列应用实验教学目的：1.掌握队列的抽象数据类型。2.掌握队列的各种操作的实现算法。知识要点：1.用C描述队列的各种操作在顺队和链队上的实现算法。2.用C描述进队，出队的算法。技能要点：1.用C描述队列的各种操作在顺队和链队上的实现算法。2.用C描述进队，出队的算法。教学万法：讲授+演示+实验教具及教学手段：PC机、TurboC2.0作业布置情况：上机实验课后分析与小结：本节重难点：用C描述队列的各种操作在顺队和链队上的实现审批：教研室主任（签字）年月日页眉内容页眉内容页眉内容页眉内容抽查：系部主任（签字）年月日抽查：系部主任（签字）年月日页脚内容72页脚内容页脚内容72教学内容及过程板书或旁注实验内容：用C语言描述队列的各种操作在顺队和链队上的实现算法。用C描述进队，出队的算法。C语言实现顺序队列的定义、创建、置空、判空算法C语言实现顺序队列的出队、入队、查找算法C语言实现链队列的定义、创建、置空、判空算法C语言实现链队列的出队、入队、查找算法教师授课教案教学单元（章节）：实验5串的操作实验教学目的：1.串的抽象数据类型。2.掌握串的各种操作的实现算法。知识要点：用C描述串类型并实现相关串操作算法。技能要点：用C描述串类型并实现相关串操作算法。教学方法：讲授+演示+实验教具及教学手段：PC机、TurboC2.0作业布置情况：上机实验课后分析与小结：本节重难点：用C描述串类型并实现相关串操作审批：教研室主任（签字）年月日教学内容及过程板书或旁注实验内容：用C语言描述串类型并实现相关串操作（1）c语言实现串定义（2）C语言实现串字符定位（3）C语言实现求子串（4）C语言实现串连接（5）C语言实现串字符删除页眉内容页眉内容页眉内容页眉内容抽查：系部主任（签字）年月日抽查：系部主任（签字）年月日页脚内容72页脚内容页脚内容72教师授课教案教学单元（章节）：实验6二叉树的基本操作教学目的：1.掌握树的操作实现算法。2•掌握二叉树的建立，遍历等算法。知识要点：1.用C描述二叉树的运算算法。2.用C描述二叉树的基本操作算法，并对二叉树进行遍历。技能要点：1.用C描述一叉树的运算算法。2.用C描述二叉树的基本操作算法，并对二叉树进行遍历。教学方法：讲授+演示+实验教具及教学手段：PC机、TurboC2.0作业布置情况：上机实验课后分析与小结:本节重难点：用C描述二叉树的基本操作、遍历算法审批：教研室主任（签字）年月日

教学内容及过程板书或旁注实验内容：用C语言描述二叉树的建立，遍历等算法。用C语言实现建立二叉树用C语言实现先序遍厉二叉树用C语言实现中序遍厉二叉树用C语言实现后序遍厉二叉树用C语言实现层次遍厉二叉树

教师授课教案教学单元（章节）：实验7二叉树的应用教学目的：掌握哈夫曼树的构造算法。知识要点：用C描述哈夫曼树的构造算法技能要点：用C描述哈夫曼树的构造算法教学方法：讲授+演示+实验教具及教学手段：PC机、TurboC2.0作业布置情况：上机实验课后分析与小结:本节重难点：用C描述哈夫曼树的构造算法审批:教研室主任（签字）年月日

教学内容及过程板书或旁注实验内容：用C语言描述哈夫曼树的构造算法建立哈夫曼树显示哈夫曼树编码解码页眉内容页