数据结构授课教案(理论)

1、1 / 104数据结构与算法 课程（理论）教课程编号：0901409014总学时：6868 周学时： 4 4适用年级专业（学科类）：工商学院 0909 级电气信息类开课时间：2010201020112011 学年第 1 1 学期使用教材：数据结构授课教师姓名：石强第 1 页2 / 104早节、八冃U言课时1教 学 目 的一、 了解本课程在学科中的地位；二、 熟悉本课程所需相关课程及知识；三、 初步了解本课程的学习特点和规律；四、 了解本课程学习要求和成绩评定标准；五、 介绍主要参考书目。教学 重点及 突出 方法一、 了解本课程在学科中的地位，采用举例的方法说明相关课程 间的联系；二、 了解本课

2、程的学习特点和规律，以程序设计基础中得知市为 引子，以书中章节安排为例，让学生对课程的特点有一初步了解；三、 明确提出要求，并列举往年实际学习情况，加深学生印象。教学 难点及突破 方法一、 如何引起学生对本课程的重视？强调课程的基础性和专业性，广泛联系其他课程，指出本课 程的重要性。二、 如何使学生了解本课程的学习特点和规律？结合学生的编程经历和课本中的章节安排进行阐释。相关内容素材课程幻灯片3 / 104黔彩课专用第 1 页4 / 104（教师授课思路、设问及讲解要点）授课思路：自我介绍一说明课程内容和地位一说明相关课程和基础知识一说明课程特点和规律一提出教学要求和成绩评定标准设问： 在说明

3、相关课程和基础知识以及课程特点和规律时， 可让学生 自己先回顾一下所学过的课程及学习时的经历， 以此引出学习本课程时 应注意的问题。讲解要点：一、本课程的地位：数据结构是计算机及相关专业中一门重要的专业基 础课程。二、 学业基础：本课程的先修课程为离散数学和高级语言程序设计。三、 本课程的任务：在基础方面，要求学生掌握常用数据结构的基本概 念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结 构上实现不同的运算，并对算法设计的方式和技巧有所体会。四、 本课程的任务：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实 现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同

4、的 运算，并对算法设计的方式和技巧有所体会。五、 参考资料：配套的习题集（与本教材相配发的）；清华大学出版社的数据结构（第 二、三版），严尉敏、吴伟民主编；其他院校也有类似教材和习题；JAVA和C+语言版的教材（根据个人能力和知识水平选择）。5 / 104教 学后 记基本实现了预期的教学目的，使学生对本课程有了初步的认识和了 解，引起了大多数同学对本课程的重视和兴趣， 也使学生对教学方面的 要求有了明确的认识，有利于今后教学工作的进行，同时也使学生有了 前进的方向和目标。第 3 页6 / 104教师备课专匡第 3 页7 / 104早节第一章绪论（1.1、1.2节）课时1教一、领会数据、数据元素

5、和数据项的概念及其相互间的关系；学二、清楚数据结构的逻辑结构、存储结构的联系与区别，以及在目数据结构上施加的运算及其实现；的三、理解抽象数据类型的概念。一、数据、数据元素、数据项；教学二、逻辑结构和数据结构在概念上的联系与区别；重点及三、存储结构及其三个组成部分；突出 方法四、抽象数据类型和数据抽象。结合计算机文化的基础知识和程序实例来分析说明。教学一、逻辑结构、存储结构的联系与区别；难点二、抽象数据类型与数据抽象。及突破列举C/C+语言中的程序实例进行理解和对比。方法相关面向对象的程序设计内容计算机中的文件管理第 3 页8 / 104素材9 / 104（教师授课思路、设问及讲解要点）教学主要

6、内容及过程：1.1数据结构的概念1.1.1为什么要学习数据结构人们使用计算机的目的（提问方式）一具体问题一抽象出数学模型一设 计或选择一个解此数学模型的算法一编出程序进行解答（在此以数学建模大赛为例）1.1.2有关概念和术语数据（Data）数据元素（Data Element）数据项（Data Item）数据对象（DataObject）或数据元素类（Data Element Class） 数据结构（Data Structure）数据的逻辑结构和数据的物理结构（以文件管理和程序语言中的实例来讲解）1.1.3数据结构课程的内容数据结构课程的发展历程T课程的内容T新的趋势数据类型（Data Type）

7、原子类型结构类型1.2.2抽象数据类型 抽象数据类型（Abstruct Data Type,简称ADT）1.2.3抽象数据类型分类原子类型、固定聚合类型、可变聚合类型1.2.4定义格式（可用实际程序举例说明）教学过程1.2抽象数据类型1.2.1数据类型10 / 104教学 后记通过学生比较熟知的相关基础知识和实际社会生活的常识的举例， 激发了学生学习数据结构的兴趣， 对本课程的基本概念和相关术语有了 基本了解， 课程内容重点突出，安排合理，取得了预期效果。11 / 104早节第一章绪论（1.3节）课时1教 学 目 的一、 算法的概念及特点；二、 掌握进行简单算法分析的方法。教学 重点及 突出

8、方法一、 算法与程序；二、 评价算法优劣的标准及方法。 以实际程序为例来分析讲解。教学 难点及突破 方法一、 区别算法与程序；二、 算法的时间复杂度分析；三、 算法的空间复杂度分析。以实际程序为例来分析讲解，介绍一些ACM比赛的网站，并实际使用在线测试功能来加深学生的理解。相关内容素材算法设计思想与实现第 6 页12 / 104教 学过 程（教师授课思路、设问及讲解要点）教学主要内容及过程：1.3算法和算法分析1.3.1算法特性 算法（Algorithm） 算法特性算法要求（注意和程序进行对比来理解）1.3.2算法描述自然语言程序流程图N-S图程序设计语言伪码语言（举例讲解）1.3.3算法性能

9、分析与度量 程序性能时间复杂度定义及方法（用ACM大赛的相关网站来说明测试问题） 空间复杂度定义及影响因素（举例讲解，并进行随堂练习）第 7 页13 / 104教学 后记通过实际举例加深了学生对计算机的时间和空间概念的认识，对算法使用的伪码语言还是理解不够， 主要是这方面的例子还不够完善， 需 今后改进之。引起了部分学生对ACM的兴趣，有利于今后学生自主的 进行算法程序试验，从而提高学习效率和教学效果。课后习题：第5、7、8题教师备课专戌第 6 页14 / 104早节第二章 线性表（2.1、2.2节）课时2教 学 目 的一、 理解线性表的定义及其运算；二、 理解顺序表的定义、组织形式、结构特征

10、和类型说明；三、 掌握在顺序表上实现的插入、删除和按值查找的算法。教学 重点及 突出 方法一、 线性表的定义及逻辑上的特点；二、 顺序表上插入、删除和定位运算的实现。从逻辑结构入手，由概念到实际的物理结构设计，最后设计实现 算法，并辅助以动态演示程序说明算法过程，分析算法性冃匕。教学 难点及突破 方法一、 线性表与线性结构的联系与区别；二、 顺序表上插入、删除和定位运算的实现。从逻辑结构入手，由概念到实际的物理结构设计，最后设计实现 算法，并辅助以动态演示程序说明算法过程，分析算法性匕匕。15 / 104教（教师授课思路、设问及讲解要点）相关内容素材动态演示程序（VB所做的演示课件）第 10

11、页秋肺备躁专匡16 / 104教学主要内容及过程：2.1线性表的逻辑结构2.1.1线性表的定义2.1.2线性表的基本操作过线性表初始化、求线性表的长度、取表元、按值查找、插入操作、删除操作程（从逻辑结构的特点和定义出发来分析讲解）2.2线性表的顺序存储及运算实现2.2.1线性表的顺序存储2.2.2顺序表上基本运算的实现 线性表初始化/求线性表的长度/取表元/按值查找/插入操作/删除操作 （从物理结构的特点出发来分析讲解，结合演示程序来直观和真切的认识问题解决的方法和过程）2.2.3顺序表应用举例（提出解决问题的基本方法和步骤，禾I用图形的直观性和现实性来提高解决问题的速度和效率）第 11 页1

12、7 / 104教学 后记由于使用了动态演示程序，使学生更简便直观的了解了线性表的顺 序存储实现的特点和实现过程，加快了教学进度，加深了知识的理解，取得了很好的教学效果，今后应多使用和设计辅助教学程序。课后习题：第1、2、3、4、5题河北夭学18 / 104早节第二章 线性表（2.3，2.4节）课时2教 学 目 的一、 理解链表的定义、组织形式、结构特征和类型说明；二、 掌握在链表上实现的插入、删除和按值查找的算法；三、 了解循环链表、双（循环）链表的结构特点和在其上施加的插 入、删除等操作。教学 重点及 突出 方法一、 单链表的结构特点及类型说明；二、 头指针和头结点的作用及区别；三、 定位、

13、删除、插入运算在单链表上的实现；四、 循环链表、双链表的结构特点，循环链表、双链表上删除与 插入运算的实现。从逻辑结构入手，由概念到实际的物理结构设计，最后设计实现 算法，并辅助以动态演示程序说明算法过程，分析算法性冃匕。教学 难点及突破 方法一、 头结点在链表中的作用及指针操作；二、 删除、插入运算中的指针操作顺序；三、 双链表上指针的操作顺序。从逻辑结构入手，由概念到实际的物理结构设计，最后设计实现 算法，并辅助以动态演示程序说明算法过程，分析算法性匕匕。相关内容素材动态演示程序（VB所做的演示课件）第13页贏聊备澀軟庄第 15 页19 / 104（教师授课思路、设问及讲解要点）教学主要内

14、容及过程：2.3线性表的链式存储和运算实现2.3.1单链表2.3.2单链表上基本运算的实现建立单链表求表长查找操作插入操作删除操作（从物理结构的特点出发来分析讲解，结合演示程序来直观和真切的认 识问题解决的方法和过程）2.3.3循环链表插入操作删除操作2.3.4双向链表插入操作删除操作2.3.5静态链表插入操作删除操作（结合演示程序来直观和真切的认识问题解决的方法和过程）2.3.6单链表应用举例（提出解决问题的基本方法和步骤，禾I用图形的直观性和现实性来提高 解决问题的速度和效率）2.4顺序表和链表的比较（结合前两节的基本算法实现和应用举例来说明各自特点）第 14 页20 / 104由于使用了

15、动态演示程序，使学生更简便直观的了解了线性表的链 式存储实现的特点和实现过程，加快了教学进度，加深了知识的理解， 取得了很好的教学效果。在解决应用题时，利用图示进行分析，比较好 的说明了算发设计的过程和分析方法，有助于学生自学能力的提高。课后习题：第& 7、8 9、10题 补充习题：1、 设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B C。其中B的结点是A中值小于0的结点，C的结点是A中值大于0的结点(A表中的元素类型为整型，要求B C利用A的结点空间)。2、 以ha,hb为头指针的单链表分别表示有序表A和B,本算法判别A是否包含在B内，若是返回1,否则反0。Int i

16、nclusion(linklistha, hb)pa=ha-n ext;pb=hb-n ext;if(pa=null)_ ;while()if(pa-data=pb-data)_ ;else_;return 0;H r-教学后记第 15 页21 / 104早节第三章 栈和队列（3.1节）课时2教 学 目 的一、 理解栈的定义、特征及在其上所定义的基本运算；二、 掌握在两种存储结构上对栈所施加的基本运算的实现。教学 重点及 突出 方法一、 栈的定义及逻辑特点，栈的基本运算；二、 栈的顺序存储结构及运算实现；三、 栈的链式存储结构及运算实现。从逻辑结构入手，由概念到实际的物理结构设计，最后设计实现

17、 算法，并辅助以动态演示程序说明算法过程，分析算法性冃匕。教学 难点及突破 方法一、 顺序栈的溢出判断条件；二、 双向栈的基本操作控制。结合图示，从栈的基本形态出发理解和运用。相关内容素材动态演示程序（VB所做的演示课件）濒师备课专隹22 / 104（教师授课思路、设问及讲解要点）教学主要内容及过程: 第二草栈和队列3.1栈3.1.1栈的定义及基本运算（从逻辑结构的特点和定义出发来分析讲解）3.1.2栈的存储实现和运算实现1顺序栈2.链栈3.双向栈（从物理结构的特点出发来分析讲解，结合演示程序来直观和真切的认 识问题解决的方法和过程）第 17 页栈初始化、空栈、入栈、 出栈、取栈顶元素置空栈、

18、判栈空、入栈、 出栈置空栈、判栈空、入栈、 出栈第 18 页23 / 104教学 后记本章节偏重于基本知识的讲解，着重在理解，因此从栈的逻辑结构 出发到具体的存储实现一一顺序和链式结构，最后介绍一改进方案一一 双向栈，充分体现算法设计的过程，再结合动态演示程序，效果良好。课后习题：第 2、3、4、8、9、10 题第 19 页24 / 104早节第三章 栈和队列（3.2节）课时2教 学 目的通过数制转换问题、迷宫的求解、中缀表达式求值、汉诺塔问题 等实际应用理解栈的特点和实际运用方法。教学 重点及突出 方法一、 数制转换冋题；二、 迷宫的求解；三、 中缀表达式求值；四、汉诺塔问题。从实际问题样例

19、出发，分析出解决问题的相关数据结构。教学 难点及突破 方法一、 迷宫结构的设计、栈的结构设计；二、 中缀表达式分析栈的设计；三、 汉诺塔中占的设计和使用（递归）。从实际问题的特点分析，结合动态演示程序进行讲解。相关内容素材动态演示程序（VB所做的演示课件）25 / 104教 学过 程（教师授课思路、设问及讲解要点）教学主要内容及过程：例3.1简单应用：数制转换冋题例3.2利用栈实现迷宫的求解。例3.3中缀表达式求值中缀表达式转换成后缀表达式后缀表达式求值（结合演示程序来直观和真切的认识问题解决的方法和过程）教肺答潭专用26 / 104第 20 页27 / 104由于栈的“后进先出”特点，在很多

20、实际问题中都利用栈做一个辅 助的数据结构来进行求解，本章节用实际应用问题进一步说明了栈结构 的这一特点，使学生加深了印象，取得了较好的效果。补充习题：1、写出和下列递归过程等价的非递归过程：void test(i nt sum)int a;read(a);if(a=0) sum=1;elsetest(sum);sum=sum*a;write(sum);2、已知ackerman函数定义如下：ackm( m,n)= n+1 if m=0ackm(m-1,1) if m!=0 & n=0 ackm(m-1,ackm(m, n-1) ifm!=0 & n!=0写出非递归算法。第 21

21、页第 22 页28 / 104早节第三章栈和队列（3.3、3.4节）课时2教 学 目 的一、 理解队列的定义、特征及在其上所定义的基本运算；二、 掌握在两种存储结构上对队列所施加的基本运算的实现。教学 重点及 突出 方法一、 队列的定义及逻辑特点，队列的基本运算；二、 队列的顺序存储结构及其上的运算实现；三、 队列的链式存储结构及运算实现。从逻辑结构入手，由概念到实际的物理结构设计，最后设计实现 算法，并辅助以动态演示程序说明算法过程，分析算法性冃匕。教学 难点及突破 方法一、 循环队列的队空、队满判断条件；二、 循环队列上的插入、删除操作。结合幻灯片中的图示进行分析，然后提出解决方法，最后提

22、出实 现的算法，并分析算法性能。相关内容素材动态演示程序（VB所做的演示课件）濒师备课专隹29 / 104（教师授课思路、设问及讲解要点）教学主要内容及过程:3.3队列331队列的定义及基本运算（从逻辑结构的特点和定义出发来分析讲解）3.3.2队列的存储实现及运算实现1顺序队置空队入队出队 判队空2链队创建一个带头结点的空队 入队判队空 出队3.双向队（从物理结构的特点出发来分析讲解，结合演示程序来直观和真切的认 识问题解决的方法和过程）3.4队列应用举例 设计一个算法找一条从迷宫入口到出口的最短路径。第 23 页30 / 104教师备課专匡教学 后记总结：本章节偏重于基本知识的讲解，着重在理

23、解，因此从队列的逻辑结 构出发到具体的存储实现一一顺序和链式结构，最后介绍改进方案一一 双向队，充分体现算法设计的过程，再结合动态演示程序，效果良好。课后习题：第& 7题第 24 页31 / 104早节第四章 串（4.1、4.2节）课时2教 学 目 的一、 了解串的定义；二、 理解和领会串的存储方式；三、 掌握常用的串运算；四、初步了解串的模式匹配。教学 重点及 突出 方法一、 串的基本概念、基本运算；二、 串的两种存储方式；三、 串的模式匹配算法BF算法。从逻辑结构入手，由概念到实际的物理结构设计，最后设计实现 算法，并辅助以动态演示程序说明算法过程，分析算法性冃匕。教学 难点及突破

24、 方法一、 串的基本运算的综合应用；二、 串的模式匹配算法（BF）。举实例来说明基本运算的结合使用，通过动态演示程序说明BF算法的原理和过程，并以此来分析该算法性能。相关内容素材动态演示程序（VB所做的演示课件）第 25 页32 / 104(教师授课思路、设问及讲解要点)教学主要内容及过程:第四章串4.1串及其基本运算4.1.1串的基本概念串、子串与主串、子串的位置、串相等(从逻辑结构的特点和定义出发来分析讲解)4.1.2串的基本运算求串长StrLength(s)串赋值StrAssign(s1,s2)连接操作StrConeat (s1,s2,s)或StrConeat (s1,s2)求子串Sub

25、Str (s,i,len)串比较StrCmp(s1,s2)子串定位StrIndex(s,t)串插入StrInsert(s,i,t)串删除StrDelete(s,i,len)串替换StrRep(s,t,r)4.2串的定长顺序存储及基本运算4.2.1串的定长顺序存储类似顺序表特殊字符作为串的终结符定长串存储空间4.2.2定长顺序串的基本运算(从物理结构的特点出发来分析讲解)4.2.3模式匹配1、简单的模式匹配(BF)(用具体实例，再结合演示程序来直观和真切的认识问题解决的方法和 过程)第 26 页教学过程第 27 页33 / 104教学 后记总结：本章节偏重于基本知识的讲解，着重在理解，因此从串的

26、逻辑结构 出发到具体的存储实现一一顺序和链式结构，最后介绍一模式匹配方法 BF算法，充分体现算法设计的过程，再结合动态演示程序，效果 良好，大多数学生理解并掌握了串的基本运算。课后习题：第3、4题第 28 页34 / 104早节第四章串（4.2、4.3节）课时2教一、深入了解并掌握串的模式匹配的方法；学二、了解串的堆存储结构。目的一、串的模式匹配算法一一KMP及其改进算法；教学 重点二、串的堆存储结构及其基本运算。及 突出使用动态演示程序辅助讲解模式匹配算法，结合C语言的串操作方法库函数说明堆的结构。教学一、串的模式匹配算法一一KMP算法；难点二、串的模式匹配算法一一KMP改进算法。及 突破结

27、合前面BF算法的缺点来对比的提出新的更高效的解决方法，方法同时使用动态演示举例来辅助说明问题。相关动态演示程序（VB所做的演示课件）内容素材栽师各课专托35 / 104（教师授课思路、设问及讲解要点）教学主要内容及过程:423模式匹配2、KMP算法（根据前面的BF算法分析结果提出改进，由此引出KMP算法，从论 证原理出发总结算法过程，并最终生成算法，注意使用演示程序辅助教教学）3、改进的KMP算法、（根据前面的KMP算法分析结果提出改进，由此引出改进的KMP算学法，最终生成算法，注意使用演示程序辅助教学）4.3串的堆存储结构过4.3.1串名的存储映象带串长度的索引表末尾指针的索引表程带特征位的

28、索引表（结合幻灯的图示，并举例讲解）4.3.2堆存储结构4.3.3基于堆结构的基本运算（绘图示范算法过程）第 29 页36 / 104第 30 页37 / 104教学 后记总结：本早节着重于算法介绍和应用，理解难度较大，通过结合模式匹配 可能遇到的实际情况进行分析，使学生理解难度降低，知识掌握程度较 好，但理论证明部分还需改进和加强，以提高学生自学能力。补充习题：1、模式串t= abcaabbcabcaabdab求next和nextval。2、主串s= abcaabbcaaabababaabca，模式为t= baba，求:next和nextval:用KMP算法对目标s进行匹配。第 29 页38

29、 / 104早节第五章数组和广义表（5.1、5.2、5.3节）课时2教一、理解多维数组的结构特点和在内存中的两种顺序存储方式；学二、理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算；目三、初步了解稀疏矩阵的定义。的教学一、多维数组的逻辑结构；重点二、多维组的两种顺序存储方式，计算给定元素在存储区中的地及址；突出 方法三、对称矩阵、三角矩阵的压缩存储方式。依据计算机内存空间特性说明数组的存放方式，并总结出公式。教学 难点对称矩阵、三角矩阵的压缩存储方式。引用线性代数中矩阵的例子来分析得出各转换公式。及 突破 方法相关动态演示程序（VB所做的演示课件）内容素材第 30 页39 / 104教 学过

30、程（教师授课思路、设问及讲解要点）教学主要内容及过程：第五章数组和广义表5.1多维数组5.1.1数组的逻辑结构5.1.2数组的内存映象（结合幻灯中的图示理解并举例说明）5.2特殊矩阵的压缩存储5.2.1对称矩阵5.2.2三角矩阵5.2.3带状矩阵（注意找出推导公式的过程，主要由学生自主完成）5.3稀疏矩阵5.3.1稀疏矩阵的三兀组表存储（结合幻灯中的图示并以实例讲解）（教师授课思路、设问及讲解要点）第 32 页藪打备课专庄40 / 10441 / 104教学 后记总结：本章节偏重于基本知识的讲解，着重在理解，从数组的逻辑结构出 发到具体的存储实现一一两种顺序结构，然后介绍改进方案一一压缩存 储

31、方式，充分体现算法设计的过程，效果良好。课后习题：第1、3题第 33 页42 / 104早节第五章 数组和广义表（5.3节）课时2教 学 目 的领会稀疏矩阵的两种存储方式和简单运算。教学 重点及 突出 方法一、稀疏矩阵以二兀组表表示时转置、相乘、相加的算法； 一、稀疏矩阵以十子链表表示时转置、相乘、相加的算法。 结合实际例子分析执行过程，根据不同存储的特点来讲解。教学 难点及突破 方法稀疏矩阵转置、相乘、相加的算法实现。结合实际例子分析执行过程，根据不同存储的特点来讲解，并辅 助以动态演示。相关内容素材动态演示程序（VB所做的演示课件）第 34 页“北大学43 / 104（教师授课思路、设问及

32、讲解要点）教学主要内容及过程:5.3稀疏矩阵5.3.1稀疏矩阵的三元组表存储1.稀疏矩阵的转置教（转置算法的改进过程需结合2章中讲解的顺序表的使用特点）2.稀疏矩阵的乘积学3.稀疏矩阵的相加（从物理结构的特点出发来分析讲解，结合演示程序来直观和真切的认过识问题解决的方法和过程）5.3.2稀疏矩阵的十字链表存储程1.稀疏矩阵的转置2.稀疏矩阵的乘积3.稀疏矩阵的相加（从物理结构的特点出发来分析讲解，结合演示程序来直观和真切的认识问题解决的方法和过程）第 35 页月北大学44 / 104总结：本章节着重于算法介绍和应用，理解难度较大，通过结合矩阵的不 同存储结构可能遇到的实际情况进行分析， 使学生

33、理解难度降低，知识 掌握程度较好，但算法的改进部分还需提高和加强， 以提高学生自学能 力。课后习题：第4、9题补充习题：将一个A1.1OO,1.1OO的三对角矩阵，按行优先存入一维数组B1.298中，A中元素A66，65在B数组中的位置k为多少？第 36 页45 / 104早节第五章数组和广义表（5.4节）课时2教 学 目 的了解广义表的定义和基本运算。教学 重点及 突出 方法一、 广义表的定义和基本运算；二、 广义表运算的存储和实现。从逻辑结构入手，由概念到实际的物理结构设计，最后设计实现算法，并辅助以动态演示程序说明算法过程，分析算法性冃匕。教学 难点及突破 方法广义表运算的存储和实现。从

34、逻辑结构入手，由概念到实际的物理结构设计，最后设计实现算法，并辅助以动态演示程序说明算法过程，分析算法性匕匕。相关内容素材动态演示程序（VB所做的演示课件）第 37 页“北大学46 / 104月北大学 “北大学47 / 104教 学过 程（教师授课思路、设问及讲解要点）教学主要内容及过程：5.4广义表5.4.1广义表的定义和基本运算1广义表的定义（从逻辑结构的特点和定义出发来分析讲解）2广义表的性质3.广义表基本运算542广义表的存储.头尾表示法2孩子兄弟表示法5.5.3广义表基本操作的实现（从物理结构的特点出发来分析讲解，）月北大学48 / 104教 学后 记总结：本章节偏重于基本知识的讲解

35、，着重在理解，从广义表的逻辑结构 出发到具体的存储实现一一头尾表示法和孩子兄弟法，然后介绍算法设 计的过程，再结合动态演示程序，效果良好，大多数学生理解并掌握了 串的基本运算。课后习题：第5、13题 补充习题： 已知广义表L=(x,y,z),a,(u,t,w)， 从L表中取出原子项t的运算是()。A.head(tail(tail(L)B.tail(head(head(tail(L)C.head(tail(head(tail(L)D.head(tail(head(tail(tail(L)月北大学49 / 104月北大学50 / 104早节第六章 二叉树（6.1、6.2节）课时2教 学 目 的一、

36、 深刻理解二叉树的定义、性质及其存储方法；二、 熟练掌握二叉树的二叉链表存储方式、 结点结构和类型定义。教学 重点及 突出 方法一、 二叉树的定义、逻辑特点及性质，二叉树上定义的基本运算；二、 二叉树的链式存储结构及其类型说明，二叉树的顺序存储结 构及其类型说明；二、二叉树链式存储结构的组织方式；从逻辑结构入手，由抽象概念到实际的物理结构的设计。教学 难点及突破 方法一、 二叉树的主要性质；二、 二叉树的递归定义；二、二叉树链式存储结构的组织方式。利用图形进行性质证明，从逻辑结构入手，由抽象概念到实际的 物理结构的设计相关内容素材课程幻灯片黔师备课专压“北大学51 / 104（教师授课思路、设

37、问及讲解要点）教学主要内容及过程: 第六章二叉树6.1定义与性质6.1.1二叉树的基本概念1.二叉树2.二叉树的相关概念（从逻辑结构的特点和定义出发来分析讲解）6.1.2二叉树的主要性质（结合图形演示性质的证明过程，部分证明需由学生首先自己给出）6.2基本操作与存储实现6.2.1二叉树的存储1.顺序存储结构2.链式存储结构（1）二叉链表存储（2）三叉链表存储（从物理结构的特点出发来分析讲解）6.2.2二叉树的基本操作及实现1.二叉树的基本操作月北大学52 / 104教 学后 记总结：本章节偏重于基本知识的讲解，着重在理解，因此从二叉树的概念 出发，先介绍性质，然后从其逻辑结构到具体的存储实现一

38、一顺序和链 式结构，再分析各自特点，课堂气氛活跃，效果良好。课后习题第1、2、3、5、6题补充习题：一棵有124个叶子结点的完全二叉树，最多有几个结点？月北大学53 / 104月北大学54 / 104早节第六章 二叉树（6.2、6.3节）课时2教 学 目 的一、 熟悉并掌握额二叉树的基本运算；二、 理解并掌握二叉树的三种遍历算法（递归和非递归）。教学 重点及 突出 方法一、 二叉树的基本运算；二、 二叉树的三种遍历方法及其算法；结合动态演示程序理解算法运行过程，理解算法设计特点。教学 难点及突破 方法一、 三种遍历的主要区别；二、 递归和非递归的特点与联系。结合幻灯片中的图示进行分析， 然后提出解决方法，最后提出实现的算法， 并分析算法性能。相关内