《数据结构》教案

教学单元（章节）:第一章：绪论1.1数据结构概念教学目的：理解学习数据结构的重要意义掌握数据结构的基本概念知识要点：数据结构、逻辑结构、物理结构、算法4种数据的存储结构、程序与数据结构技能要点：数据结构、4种基本的数据结构、4种数据的存储结构教学方法：讲授+演示教具及教学手段：投影作业布置情况：P11:1、2课后分析与小结：本节课的重点：数据结构有关概念和术语

难点：学习数据结构的意义审批：教研室主任（签字）年抽查：系部主任（签字）年日日教学内容及过程板书或旁注

教师授课教案10.3数组与指针10.3.1指向数组元素的指针定义一个指向数组元素的指针变量10.3.2通过指针引用数组元素数组元素的引用可以用.下标法：a[i].指针法：*(a+i)或*(p+i)10.4字符串与指针4.1字符串的表现形式.用字符数组存放一个字符串.用字符指针指向一个字符串.字符串常量和字符指针的初始化10.8指针运算小结10.8.1有关指针的数据类型的小结10.8.2指针运算小结.指针变量的加减.指针变量赋值.指针变量的比拟教学单元(章节)：c语言第十一章：结构体与共用体1-11.5.1结构体3处理动态链表所需的函数11.10用typedef定义类型教学目的：掌握结构体变量的定义、引用和初始化掌握处理动态链表所需的函数掌握用typedef定义类型知识要点：结构体变量、结构体数组，malloc函数calloc函数、free函数、typedef技能要点：结构体变量的定义、引用和初始化用typedef定义类型教学方法：讲授+演示教具及教学手段：投影作业布置情况：P318；11.1P318；11.5课后分析与小结：本节重点：结构体变量、处理动态链表所需的函数本节难点：结构体变量的引用和初始化、用typedef定义类型审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日板书或旁注板书或旁注板书或旁注教学内容及过程第十一章：结构体与共用体板书或旁注11.1概述结构体类型定义一般形式struct结构体名{类型标识符成员名1：类型标识符成员名2：■*类型标识符成员名n：>；11.2定义结构体类型变量的方法.先定义结构体类型，再用类型标识去定义变量.定义类型的同时定义变量3.直接定义结构体类型变量1.3结构体变量的引用.结构体变量各成员的引用引用形式：结构体变量名.成员名.结构体变量各成员的输入、输出1.4结构体变量的初始化.5结构体数组1.结构体数组的定义2.结构体数组的初始化3.结构体数组stu的存储结构4.结构体数组的引用11.6指针与结构体.指向结构体变量的指针.指向结构体变量的指针与结构体变量的等价关系11.7用指针处理链表处理动态链表所需的函数内存分配函数原型：void*malloc(unsignedsize);内存分配函数原型：void*calloc(unsignedsize);内存释放函数原形：voidfree(void*p);10用typedef定义类型1、使用的一般形式：typedef原类型名新类型名；2.用typedef定义类型的方法(举例)先按定义数组变量形式书写：intn[100]；将变量名换成新类型名：intNUM[100]；③在最前面加上typedef:typedefintNUM[100]；④用新类型名来定义变量：NUMn；3.用typedef定义类型的说明：(1)用typedef可以声明各种类型名，但不能用来定义变量。(2)用typedef只是对已经存在的类型增加一个类型名,而没有创造新的类型。(3)使用typedef有利于程序的通用与移植。教师授课教案教学单元(章节)：第二章：线性表线性表的逻辑结构线性表的顺序存储及操作实现教学目的:理解顺序表的定义、特点及其主要操作掌握插入与删除算法中数据元素的平均移动次数知识要点：线性表的定义、特点、基本操作顺序表的定义、特点和存储顺序表的初始化、插入、删除、查找操作，应用举例技能要点：线性表的逻辑结构及基本操作线性表的顺序存储结构及其基本操作实现教学方法：讲授+演示教具及教学手段：投影作业布置情况：P37；1P38；6课后分析与小结：本节重点：线性表的定义、特点和顺序表的基本操作

本节难点：顺序表的插入和删除算法及其时间复杂度审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日教学内容及过程板书或旁注2.1线性表的逻辑结构线性表的实际例子1.1线性表的定义线性表的基本操作.初始化：Init_List(L).置空：Setnull_List(L).求长度：Length_List(L).取表元:Get_List(L,i).查找:Locate_List(L,x).插入：InsertList(L,x).删除:Delete_List(L,i)2.2线性表的顺序存储结构2.1线性表的顺序存储结构.顺序表的定义和特点.顺序表的存储和类型定义2.2顺序表的基本算法实现.初始化顺序表L.插入.删除.按值查找教师授课教案教学单元(章节):第二章：线性表2.3.1单链表单链表上基本运算的实现教学目的：掌握单链表的定义、特点及存储结构掌握单链表的查找、插入与删除算法理解带首结点的单链表的优点

知识要点：单链表的定义、特点、标识、结点结构和存储结构单链表的建立、求表长、查找、插入和删除算法技能要点：单链表的结点结构和存储结构单链表的查找、插入与删除算法教学方法：讲授+演示教具及教学手段：投影作业布置情况：P38；8课后分析与小结：本节重点：单链表的定义、特点和存储结构基本操作本节难点：单链表的查找、插入和删除算法板书或旁注板书或旁注板书或旁注日日

月月

年年审批：教研室主任（签字）抽查：系部主任（签字）板书或旁注日日

月月

年年教学内容及过程2.3线性表的链式存储结构义和特占储结构而类型定义上的基本运算的实现后入法建立后入法建立导点的单链表;结点的单链表教师授课教案教学单元（章节）:第二章：线性表2.3.3循环链表教学单元（章节）:3.4双向链表教学目的：掌握单链表的定义、特点及存储结构掌握单链表的查找、插入与删除算法理解带首结点的单链表的优点知识要点：循环链表和双向链表的定义、特点、标识、结点结构两个循环链表的连接、双向链表中结点的插入和删除顺序表和链表的比拟技能要点：两个循环链表的连接算法双向链表中结点的插入和删除教学方法：讲授+演示教具及教学手段：投影作业布置情况：P38；7、9课后分析与小结：本节课的重点：循环链表和双向链表的特点和基本操作难点：循环链表连接操作、双向链表的插入和删除

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

教师授课教案板书或旁注第一章：绪论数据结构概念为什么要学习数据结构1.计算机处理问题的分类（1）数值计算问题（2）非数值性问题2.非数值问题求解算法+数据结构二程序数据结构：是指数据的逻辑结构和存储结构算法：是对数据运算的描述有关概念和术语数据数据元素数据项数据结构：集合、线性、树型、图状数据结构：包括物理结构、逻辑结构数据的四种基本存储方法（1）顺序存储方法（2）链接存储方法（3）索引存储方法（4）散列存储方法教学单元（章节）：第一章：绪论1.2算法描述1.3算法分析

第三章：栈和队列3.1栈3.L1栈的定义和基本运算.栈的定义栈：是限制仅在表尾进行插入和删除的线性表。.基本运算(1)初始化栈：构在一个空栈(2)置空栈：将S置成空栈(3)入栈：在栈顶插入一个新元素X(4)出栈：删除(弹出)栈S的顶部元素(5)取栈顶)：取栈S的顶部元素(6)判断空栈Empty_Stack(S)：空栈返回13.1.2栈的存储实现和运算实现1.顺序栈1)顺序栈的定义2)顺序栈基本运算⑴置空栈⑵判空栈⑶入栈⑷出栈3.1.2栈的存储实现和运算实现.链栈1)链栈的定义2)链栈基本运算⑴置空栈⑵判空栈⑶入栈(4)出栈.1.3栈与递归的实现.具有递归特性的问题(1)递归定义的数学函数(2)递归数据结构的处理(3)递归求解方法.递归算法的设计方法与递归过程的实现(1)应用递归算法的前提Hanoi塔问题的递归函数Fibonacci数列的递归算法教师授课教案教学单元(章节)：第三章：栈和队列3.2栈的应用举例3.3队列3.4队列应用举例教学目的：掌握队列的定义、特点和存储结构掌握循环队列和链队列的基本运算理解循环队列的意义和队列的应用知识要点：队列的定义、特点、存储结构、基本运算循环队列产生的原因，循环队列和链队列的主要操作假溢出，循环队列队空与队满的条件技能要点：循环队列队空与队满的条件，循环队列和链队列的入队、出队、判队空操作教学方法：讲授+演示教具及教学手段：投影作业布置情况：P63；2、5、9课后分析与小结：本节课的重点：循环队列和链队列的基本操作

难点：栈的应用、循环队列审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日教学内容及过程板书或旁注第三章：栈和队列3.2栈的应用举例.数制转换.表达式求值3.3队列.3.1队列的定义和基本运算.队列的定义和特点.队列结构的基本操作Init_Queue(Q)将Q置为一个空队列In_Queue(Q,x)插入元素x为队Q的新队尾元素Out_Queue(Q,x)删除Q的队头元素，并返回日值Front.Queue(Q,x)返回Q的队头元素EmptyQueue(Q)判队空3.3.2队列的存储和运算实现.顺序队列：定义、特点和存储结构.循环队列：定义、存储结构和基本操作.链队列

1)定义、特点和存储结构2)基本操作4队列应用举例教师授课教案教学单元(章节)：第四章：串和数组1串

教学目的：掌握串的定义、特点、相关术语和基本运算了解串的存储结构及其基本运算实现知识要点：串的定义、特点、相关术语和基本运算串的顺序存储结构和堆分配存储结构技能要点：串的基本运算定长串连接、求子串和串比拟操作教学方法：讲授+演示教具及教学手段：投影作业布置情况：P78；2、3课后分析与小结：本节重点：串的定义、存储结构和基本运算本节难点：串连接、求子串和串比拟算法审批：教研室主任（签字）年月日抽查：系部主任（签字）年月日教学内容及过程板书或旁注第四章：串和数组4.1串4.1.1串的基本概念.串的定义.术语1.2串的基本运算(1)求串长(2)串赋值(3)串连接(4)求子串(5)串比拟(6)串定位⑺插入(8)删除(9)串替换1.2串的存储结构.串的定长顺序存储结构.堆分配存储结构.定长顺序串基本运算的实现(1)串连接(2)子串(3)串比拟教师授课教案教学单元(章节)：第四章：串和数组4.2数组

教学目的：了解数组的逻辑存储结构和内存映像了解稀疏矩阵的定义及其数组实现知识要点：数组与线性表、数组的逻辑存储结构和内存映像

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

月月

年年教学目的：理解算法的定义、特性、描述方法掌握简单的时间复杂度的估计审批：教研室主任（签字）抽查：系部主任（签字）日日

月月

年年知识要点：算法的特性、描述方法、算法编制的质量要求、数据结构的基本操作、时间复杂度、空间复杂度、技能要点：描述算法、分析简单算法的时间复杂度教学方法：讲授+演示教具及教学手段：投影作业布置情况：PH;3、4课后分析与小结：本节课的重点：算法的特点和描述，算法分析

难点：算法时间复杂度的估计审批：教研室主任（签字）年，抽查：系部主任（签字）年，日日教学内容及过程板书或旁注

教师授课教案第一章：绪论1.2算法描述1算法特性(1)有穷性⑵确定性⑶可行性⑷输入⑸输出好的算法的特点(1)正确⑵可读(3)健壮(4)高效数据结构的基本操作：(1)查找(2)读取(3)插入(4)删除(5)修改算法描述算法描述的种类：(1)框图/流程图算法(2)非形式算法(3)伪语言算法(4)高级语言算法1.3算法分析时间复杂度:解决某问题所花费的时间大小，即程序运行从开始到结束所需要的时间，记为T(n)空间复杂度:解决某问题的程序完全运行时所占用的存储空间大小，记为S(n)【例】算法MatrixMultidy的时间复杂度T(n)如(1.1)式所小,当n趋向无穷大时，显然有JjjjqT(ri)/媪=Jjjjq(2媪+3后+2月+1)/媳=2M->0O*8教学单元(章节)：C语言第七章：数组一维数组的定义和引用二维数组的定义和引用3字符数组

教学目的：理解一维数组、二维数组、字符数组的定义掌握一维数组、二维数组、字符数组的引用和初始化方法掌握一维数组、二维数组、字符数组的简单应用程序知识要点：一维数组、二维数组、字符数组的定义、引用、初始化一维数组、二维数组、字符数组相关的简单程序技能要点：用数组来处理相关问题的程序教学方法：讲授+演示教具及教学手段：投影作业布置情况：P152；7.1P152；7.3P153；7.11P153；7.15课后分析与小结：本节重点：数组的定义、引用、初始化本节难点：用数组求解简单的问题审批：教研室主任（签字）抽查：系部主任（签字）审批：教研室主任（签字）抽查：系部主任（签字）审批：教研室主任（签字）抽查：系部主任（签字）日日

月月

年年审批：教研室主任（签字）抽查：系部主任（签字）日日

月月

年年板书或旁注教学内容及过程板书或旁注第七章数组7.1一维数组的定义和引用7.1.1一维数组的定义7.1.2—维数组的引用1.3一维数组的初始化4一维数组程序举例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变量的指针和指针变量教学目的：理解地址和指针