数据结构教学教案

《数据结构》教学设计

项目一数据结构与算法

教材导读

课程名称《数据结构》课程类型理论课（）/实践课（）

数据结构作为计算机专业的核心课程，其内容不仅是一般程序设计的基

课程定位础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程

序的重要基石。

每当提到计算机专业，总会让人联想到编程,联想到各类技术,然而仅就

代码的编写,并不足以诠释计算机专业的内涵。中国共产党第二十次全

思政理念国代表大会（以下简称党的二十大）报告提出“我们确立和坚持马克思主

义在意识形态领域指导地位的根本制度”。立.足于•我们的学习生活，我

们也应把握事物的核心规律，只有这样，才能谋求自身更长远的发展。

教案设计

项目课题项目一：数据结构与算法

授课时间授课对象

L了解数据结构的基本概念。

知识目标2.掌握数据的逻辑结构和存储结构。

3.掌握算法及算法的特性,理解和掌握算法分析的方法。

能力目标能够熟练进行时间复杂度的算法分析，从而选择有效的算法。

L正确认识计算机中数据的表示与存储方法。

素质目标

2培养学生对抽象概念的理解能力。

掌握数据的逻辑结构和存储结构。

重占

掌握算法及算法的特性，理解和掌握算法分析的方法。

重、难点

能够熟练进行时间复杂度的算法分析，从而选择有效的

难点

算法C

教学方法讲授法

教学用具教材、课件、教案、微课、投影仪、计算机等

教学流程

教学环节教学内容

【教师】数据结构课程主要研究数据在计算机中的表示和对数据的处理

方法，本项目介绍了相关的基本概念及算法分析的理论。大家对数据结

构课程都了解多少呢？请小组讨论一下。

情境导入

【学生】小组讨论并回答问题。

【教师】归纳学生提出的主要想法，发现小组之间了解程度不一，引起

学生好奇心，激发学习新知的兴趣。

1.1数据结构概述

【教师】通过讲解和自由讨论数据结构的概念、数据的逻辑结构、数据

的存储结构，引导学生了解数据结构概述。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】简述数据结构的概念。

【学生】1.数据(Data)是信息的载体,是能够输入计算机中并能被计算

机识别、存储和加工处理的符号集合。

2.数据元素(DataElement)是数据的基本单位，在计算机程序中通常作

为一个整体进行处理。

讲授新知

3.数据项(DataItem)是数据的最小单位,是对数据元素属性的描述，也

称为域或字段。

4.数据对象(DataObjecl)是性质相同的数据元素的集合,是数据的子

集。

5.数据类型(DataType)是一组性质相同的值的集合和定义在该集合上

的一组操作的总称。

6.数据结构(DataStructure)是相互之间存在一定关系的数据元素的集

合。

【教师】简述数据的逻辑结构。

【学生】数据的逻辑结构分为线性结构和非线性结构两种。

常见的基本逻辑结构有集合结构、线性结构、树形结构、图形结构。

【教师】简述数据的存储结构。

【学生】数据的存储结构主要有.顺序存储结构、链式存储结构、索引

存储结构、散列存储结构。

【教师】点评并拓展知识。

1.2算法与算法分析

【教师】通过讲解和自由讨论算法及其特性、算法分析，引导学生了解

算法与算法分析。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】简述算法及其特性。

【学生】1.输入

一个算法有零个或多个输入，这些输入取自某个特定对象的集合。

2输.出

一个算法有一个或多个输此这些输出是与输入有着一定关系的量。

3.有穷性

一个算法总是（对任何合法的输入值）在执行有穷步之后结束，且每一步

都可在有穷时间内完成。

4.确定性

算法中的每条指令都必须有确切的含义,不能有二义性。在任何条件

下，算法只有唯一的一条执行路径,即对于相同的输入，只能得到相同

的输出.

5.可行性

一个算法必须是可行的，即算法中描述的操作，可通过己经实现的基本

运算执行有限次来实现。

【教师】简述算法设计的要求。

【学生】算法设计的要求要满足:正确性、可读性、健壮性、高效率与

低存储量需求。

【教师】简述算法的评价。

【学生】算法的评价主要从时间复杂度和空间复杂度两个方面来考虑。

时间复杂度不是精确的执行次数,而是估算的数量级,着重体现的是随

着问题规模〃的增大，算法执行时间的变化趋势。

【教师】点评并拓展知识。

【教师】询问学生是否有尚未理解的地方

问题解决【学生】提出疑问

【教师】【学生】共同探讨解决

【教师】带领学生复习本项目的知识脉络

整体回顾

【学生】简要复述本项目的知识框架

【教师】请学生完成本项目的［实训习题一］

布置作业

【学生】自行做题与核对答案进行自我检测

教学反思

《数据结构》教学设计

项目二线性表

教材导读

课程名称《数据结构》课程类型理论课()/实践课()

线性表是最常用、最简单的一种数据结构。线性表的数据元素之间存

课程定位

在一对一的对应关系。

党的二十大报告指出：“必须坚持系统观念。万事万物是相互联系、

相互依存的。只有用普遍联系的、全面系统的、发展变化的观点观察事

思政理念物,才能把握事物发展规律。”通过对线性表的学习，有助于我们在日常生

活中遇到符合线性关系的数据元素时,能够厘清脉络，更有效地解决问题，

这也为我们把握事物的发展规律提供了可行的思路与措施。

教案设计

项目课题项目二：线性表

授课时间授课对象

1.理解线性表的逻辑结构特征。

2.掌握顺序表的含义、特点、基本操作和相关算法分析。

知识目标

二掌握链表的含义、特点、基本操作和相关算法分析。

4.理解循环链表和双向链表的逻辑结构特征及基本操作。

1.能够运用顺序表、链表的相关算法解决实际问题。

能力目标

2.能够恰当地选择线性表作为数据的逻辑结构和存储结构。

，提升团队协作和进行算法效率分析的能力.

素质目标

2.培养分析问题、解决问题的能力。

掌握顺序表的含义、特点、基本操作和相关算法分析。

重点

重、难点掌握链表的含义、特点、基本操作和相关算法分析。

难点•熟练运用问卷设计方法、技巧等对问卷进行调查。

教学方法讲授法

教学用具教材、课件、教案、微课、投影仪、计算机等

教学流程

教学环节教学内容

【教师】本项目介绍了线性表的相关内容。大家对线性表都了解多少呢？

请小组讨论一下。

情境导入【学生】小组讨论并回答问题。

【教师】归纳学生提出的主要想法，发现小组之间了解程度不一，引起学

生好奇心，激发学习新知的兴趣。

2.1线性表的定义及基本操作

【教师】通过讲解和自由讨论线性表的定义、线性表的基本操作，引导学

生理解线性表的定义及基本操作。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】简述线性表的定义

【学生】线性表(LinearList)是由〃个性质相同的数据元素构成的有限

序列。其中,表中数据元素的个数〃定义为线性表的长度，当〃=0时，

称为空表,此时表中没有任何数据元素。

【教师】简述线性表的基本操作。

【学生】(l)InitList(&L)o初始化线性表Lo

讲授新知

(2)ListEmpty(L)o判断线性表L是否为空表，如果L为空表，则返回

true(l);否则返回false(0)«>

(3)ListLength(L)o求线性表L的长度。

(4)LocateNode(L,x),,查找线性表!.中值为x的结点的位置。

(5)GetNode(L,i)o取线性表L中的第i个结点，要求

1WiWListLength(L)。

(6)InsertList(&L,x,i)o在线性表L中的第i个结点之前插入值为x

的新结点。

(7)DeleteList(&L,i)«删除线性表L中的第i个结点。

【教师】点评并拓展知识。

2.2线性表的顺序存储结构

【教师】通过讲解和自由讨论顺序表的定义、顺序表的基本操作，引导学

生了解线性表的顺序存储结构。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】简述顺序表的定义。

【学生】顺序表（SequentialList）是线性表的顺序存储表示的简称,指

的是用一组地址连续的存储单元依次存储线性表中的元素・，即以存储位置

的相邻表示相继的两个元素之间的前驱和后继关系（逻辑关系），并以表

中第一个元素的存储位置作为顺序表的起始地址，称为顺序表的基地址。

【教师】简述线性表的存储。

【学生】线性表的存储有两种方式：顺序存储（顺序表）与链式存储（链表）。

顺序表的存储空间是静态分配的，而链表的存储空间是动态分配的八选择

顺序表还是链表,要根据实际问题的需求决定。

【教师】简述顺序表的操作。

【学生】顺序表具有按元素序号随机访问的特点，即对指定位置（下标）元

素进行读取与修改,所需的时间复杂度是。（1）。对于长度为〃的顺序

表，按序查找某一特定值的元素、删除第，•个元素或在第i个元素之前插

入一元素，所需的平均时间复杂度是05）。

现存在两个有序（升序或降序）顺序表（la与1b）,其长度分别是m与〃，

合并为一个有序顺序表1c,则所需的时间及杂度是如果la与

1b合并后仍然存放在la中，则算法的时间复杂度是O（〃?X〃）。

【教师】点评并拓展知识。

2.3线性表的链式存储结构

【教师】通过讲解和自由讨论链表的定义、单链表的基本操作、循环链表

概述、双向链表概述，引导学生了解线性表的链式存储结构。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】简述链表的定义。

【学生】1.结点（Node）的组成

线性表中的数据元素及元素之间的逻辑关系可由结点来表示。结点由两

部分组成：一部分用来存储数据元素信息的数据域；另一部分用来存储元

素直接后继存储位置的指针域。

2.单链表（LingleLinkedList）

用链式存储结构表示的线性表称为链表，即用•组任意（可以连续也可以

不连续）的存储单元来存放线性表的结点。

3.开始结点、尾结点、头结点和头指针

在链表中存储第一个数据元素（al）的结点称为开始结点；存储最后一个

数据元素（an）的结点称为尾结点，由于尾结点没有直接后继，所以尾结

点指针域的值为NULL,NULL在表示链表的示意图中经常用“A”来代替；

在开始结点之前附加的一个结点称为头结点；指向链表中第一个结点（头

结点或开始结点）的指针称为头指针。

【教师】简述链表的操作八

【学生】链表不具有随机访问的特点，对r长度为〃的链表，查找指定位置

（第几个）的元素所需的时间复杂度是。（〃）;查找某一特定值的元素所需的

时间复杂度是。（〃）;删除第/个元素或在第i个元素之前插入一个元素

所需的时间复杂度是。（〃）。

现有两个有序（升序或降序）链表（ha与hb）,其长度分别是m与〃，如果将

它们合并为一个有序链表ha,则所需的时间复杂度是。（加+〃）。

【教师】简述循环链表。

【学生】将单链表中最后一个结点的指针指向锌表中的第一个结点，使整

个链表构成一个环形，这种链表称为单循环链表，简称循环链表。

【教师】简述双向链表。

【学生】在单链表的每个结点里再增加一个指向其直接前驱结点的指针域

prior,这样形成的链表中有两条方向不同的链，囚此称为双向链表，

【教师】点评并拓展知识。

2.4顺序表与链表的比较

【教师】简述顺序表与链表的比较。

【学生】1.基于时间的考虑

顺序表可实现元素的随机存取，对表中任意结点都可以在0（1）时间内直

接存取；而链表中的结点则需要从头指针起，按顺序扫描结点才能存取。

2.基于空间的考虑

顺序表的存储空间是静态分配的，在程序执行之前，必须明确规定它的存

储规模，即对MaxSize要有合适的设定。因此，当线性表的长度变化较

大而难以估计其存储规模时，不宜采用顺序表。链表无须事先估计存储

规模，但链表的存储密度较低。

3.基于语言的考虑

各种高级语言都提供数组，但不一定提供指针，由于链表是基于指针的，

所以链表的使用有时会受到裔级语言的限制。

【教师】点评并拓展知识。

2.5案例实现一一通信录管理

【教师】通过讲解和自由讨论案例分析、案例1一一基于顺序表的通信录

管理、案例2一—基于链表的通信录管理，引导学生了解案例实现一一通

信录管理。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】询问学生是否有尚未理解的地方

问题解决【学生】提出疑问

【教师】【学生】共同探讨解次

【教师】带领学生复习本项目的知识脉络

整体回顾

【学生】简要复述本项目的知识框架

【教师】请学生完成本项目的［实训习题二］

布置作业

【学生】自行做题与核对答案进行自我检测

教学反思

《数据结构》教学设计

项目三栈和队列

教材导读

课程名称《数据结构》课程类型理论课（）/实践课（）

栈和队列是操作受限的线性表,它们的逻辑结构与线性表相同，只是操作

课程定位

规则比普通的线性表有更多的限制。

党的二十大报告提出“推动全党坚定理想信念、严密组织体系、严明纪律

规矩”。作为新时代的新青年，我们应当严格要求自己，“没有规矩不成

思政理念方圆”。只有明确信念,遵守秩序，并主动作为秩序的维护者,我们才能充

分地发挥自身优势，合理地提出诉求，进而实现自己的理想,为社会发展贡

献自己的力量。

教案设计

项目课题项目三：枝和队列

授课时间授课对象

1.理解栈和队列的逻辑结构特征及两者与线性表的异同。

知识目标2.掌握实现顺序栈、链栈基本操作的算法。

3.掌握实现循环队列、链队列基本操作的算法。

工能够运用栈和队列的相关理论设计算法,解次实际问题。

能力目标2.具备恰当地选择栈和队列作为数据的逻辑结构和存储结构的能力,

，引导学生遵守公共秩序。

素质目标

2.培养学生的民族认同感、文化自信心和家国情怀。

掌握实现顺序栈、链栈基本操作的算法。

重、难点重点

掌握实现循环队列、链队列基木操作的算法。

难点能够运用栈和队列的相关理论设计算法，解决实际问题。

教学方法讲授法

教学用具教材、课件、教案、微课、投影仪、计算机等

教学流程

教学环节教学内容

【教师】本项目介绍了栈和队列的相美内容。大家对栈和队列都了解多少

呢？请小组讨论一下。

情境导入【学生】小组讨论并回答问题。

【教师】归纳学生提出的主要想法，发现小组之间了解程度不一，引起学

生好奇心，激发学习新知的兴趣。

3.1栈

【教师】通过讲解和自由讨论栈的定义及基本操作、顺序栈、链栈、顺序

栈和链栈的比较、栈的应用，引导学生理解栈。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】谁来简述栈的定义？

【学生】栈(Stack)是只允许在一端完成插入和删除操作的线性表，句栈

中插入元素称为进(入)栈，从栈中删除元素称为退(出)栈。

【教师】回答得非常好，那有谁知道栈的基本操作呢？

【学生】(1)置栈空InitStack(S).构造一个空栈So

讲授新知

(2)判栈空SUckEmpty(S)o若S为空栈，则返回1；否则返回0。

(3)判栈满StackFull(S)o若S为满栈，则返回1；否则返回0。

(4)入栈Push(S,x)。若S非满枝，则将元素x插入栈顶。

(5)出栈Pop(S,x)。若S非空栈，则将栈顶元素存放到x中并返回，

变更栈的状态。

(6)取栈顶元素GotTop(S,x)。若S非空栈，则将栈顶元素存放到x中，

栈的状态不变。

【教师】简述顺序栈的定义。

【学生】栈的顺序存储结构即为顺序栈。

【教师】简述链栈的定义。

【学生】栈的链式存储结构称为链栈(LinkedStack),其插入和删除操作

只允许在表头位置上进行，链表的头指针就是栈顶指针。

【教师】简述顺序栈和链栈的比较。

【学生】1.时间性能

因为栈的所有操作都在栈顶进行，所以顺序栈和链栈基本操作的算法都只

需要常数阶的时间。

2.空间性能

顺序栈初始化时需要设定一个固定的长度，当数据元素过多时可能出现上

溢现象，数据元素较少时乂存在空间浪费现象。链栈只有在内存空间不

足时才会出现栈满的问题，但因为每个元素结点都需要指针域，从而产牛.

了结构性开销。

因此.栈的使用过程中如果元素个数变化较大,则宜选用链栈：反之则选

用顺序栈。

【教师】简述栈的应用。

【学生】栈的典型应用之一是子程序的调用和返回，一个程序可以由多个

子程序(C语言为函数)构成，其中的一个子程序可以调用另一个子程序，

这种调用者和被调用者之间的联系(衔接)就是通过栈实现的。例

如，mair()函数调用了funl(),funl()又调用了fun2(),main函数调用

fun1()时,要将调用指令的下一条指令的地址等信息压入枝(保存断

点)，furl()在调用fun2()时，又要将funl。中调用指令的下一条指令的

地址等信息压入栈,fun2()运行结束,执行出栈操作，获得funl()的断点

地址(恢复断点)，funl()继续运行,funl()运行结束后，继续出栈,获得

mainO函数的断点地址,main()函数继续运行直到结束。

【教师】点评并拓展知识。

3.2队列

【教师】通过讲解和自由讨论队列的定义及基本操作、顺序队列、循环队

歹人链队列、循环队列和链队列的比较、队列的应用，引导学生理解队列。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】简述队列的定义。

【学生】队列(Queue)是只允许在一端进行插入，而在另一端进行删除的

操作受限的线性表。

【教师】简述队列的基本操作。

【学生】(1)置队空：InitQueue(&Q)。构造一个空队列Q。

(2)判队空:QueueEmpty(Q)o若队列Q为空，则返回1；否则返回0。

(3)判队满：QueueFull(Q)o若队列Q为满，则返回1；否则返回0。

(4)入队:EnQueue(&Q,x)。若队列Q非满,则将元素x插入Q的队

尾。

(5)出队：DelQueue(&Q,&x).若队列Q非空，则将Q的队头元素赋

值给X中并返回，改变队列的状态。

(6)取队头元素：GetHead(Q,&x)。若队列Q非空，则将Q的队头元

素赋值给x中并返回.不改变队列的状态c

【教师】简述顺序队列的定义。

【学生】要从许多标志中选择反映总体性质特征的标志，必须遵循这三个

基本原则：根据研究的目的和任务选拦分组标志、选择能反映现象本质的

标志作为分组标志、根据现象所处的历史条件和经济条件选择分组标志。

【教师】简述统计分组标志的种类。

【学生】队列的顺序存储结构称为顺序队列。

【教师】简述循环队列的定义。

【学生】循环队列可以理解为向量空间的元素位置首尾相接的顺序队列，

在循环队列中，可以通过数学运算中的取余运算实现队列的首尾相连。

【教师】简述链队列的定义。

【学生】队列的链式存储结构称为链队列。

【教师】简述循环队列和链队列的比较。

【学生】关于循环队列和链队列之间的差别，可以从其时间性能和空间性

能两个角度进行分析。

1.时间性能

受限于队列的操作，插入操作只能在队尾进行，删除操作只能在队头进行，

因此循环队列和链队列基本操作的算法时间复杂度都为0(1)。

2.空间性能

循环队列虽然可以避免普通顺序队列的“假溢出”现象，但作为顺序存储

结构依然存在事先确定队列空间的问题。所以，循环队列存在存储元素

个数的限制和空间浪费的问题。链队列在内存拥有空闲空间时没有队列

满的问题，但因结构问题，存储密度小于1,故产生了结构性开销。

因此，当队列使用过程中元素个数变化较大时.，更适合选用链队列；反之，

则应选用循环队列。

【教师】简述队列的应用。

【学生】队列的典型应用之一，是设备缓存区的设置，如磁盘缓存区可以对

应3条缓冲队列，分别是输入缓冲队列、输出缓冲队列及空闲缓冲队列。

当用户程序有数据输出时.，操作系统先使空闲缓冲队列的队首元素出队，

将数据写入该结点后，该结点进入输出缓冲队列，当输出缓冲队列的长度

达到某一值时，再将全部结点中的数据写到磁盘中，这些结点重新进入空

闲缓冲队列,输出缓冲队列的设置能够有效减少磁盘的写操作次数。与磁

盘的输出类似,磁盘输入时,操作的是空闲缓冲队列与输入缓冲队列。

【教师】点评并拓展知识。

3.3案例实现一一汉诺塔问题和键盘缓冲区

【教师】通过讲解和自由讨论案例1一一汉诺塔问题、案例2一一键盘缓

冲区，引导学生理解案例。

【学生】阅读教材，带着疑问去学习、理解并记忆。

【教师】询问学生是否有尚未理解的地方

问题解决【学生】提出疑问

【教师】【学生】共同探讨解决

【教师】带领学生复习本项目的知识脉络

整体回顾

【学生】简要复述本项目的知识框架

【教师】请学生完成本项目的［实训习题三］

布置作业

【学生】自行做题与核对答案进行自我检测

教学反思

《数据结构》教学设计

项目四串和数组

教材导读

课程名称《数据结构》课程类型理论课（）/实践课（）

基于串自身的特性,其本质是•种特殊的线性表,数据结构中常常把一个

课程定位串作为一个整体来处理,而数组作为高级语言中已经实现的数据类型，可

视作线性表的扩展。

党的二十大报告指出：“坚持和发展马克思主义，必须同中华优秀传统文化

相结合。只有植根本国、本民族历史文化沃土，马克思主义真理之树才能

思政理念根深叶茂。”这要求我们客观地、正确地看待局部与整体，明确•般与特

殊之间的规律。当面对困难时,我们需要积极应对,寻找解决方案，保持乐

观的心态。这样,我们才能奋发向上,更坦然地迎接各项挑战。

教案设计

项目课题项目四：弟和数组

授课时间授课对象

1.熟悉串的定义及基本操作,并能借助其实现串的其他各种操作。

2.熟练掌握在串的定长顺序存储结构上实现串各种操作的方法。

知识目标3.理解串的堆存储结构及在该结构上实现串操作的基本方法。

不理解串的链式存储结构。

5•.理解串的朴素模式匹配算法。

工.能应用串的各种基本操作和模式匹配算法解决实际问题。

能力目标

2.能理解数组中各个元素的相对存放位置，并解决实际问题。

工.培养学生的团队合作精神和沟通交流能力。

素质目标

2.培养弘毅致远、坚韧不拔的学习意志。

熟练掌握在串的定长顺序存储结构上实现串各种

操作的方法。

理解串的堆存储结构及在该结构上实现串操作的

重占

基本方法。

重、难点理解串的链式存储结构。

理解串的朴素模式匹配算法

能应用串的各种基本操作和模式匹配算法解决实际问

难点

题。

教学方法讲授法

教学用具教材、课件、教案、微课、投影仪、计算机等

教学流程

教学环节教学内容

【教师】本项目介绍了串和数组的相关内容。大家对串和数组都了解多少

呢?请小组讨论一下。

情境导入【学生】小组讨论并回答问题。

【教师】归纳学生提出的主要想法，发现小组之间了解程度不一，引起学

生好奇心，激发学习新知的兴趣。

3.1串

【教师】通过讲解和自由讨论串的逻辑结构、串的存储结构、串的模式匹

配，引导学生理解串。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】谁来简述串的定义？

【学生】串(Siring)是字符串的简称。它是一种在数据元素的组成上具有

讲授新知•定约束条件的线性表，即要求组成线性表的所有数据元素都是字符。所

以也可以这样定义串：串是由零个或多个字符组成的有限序列。

【教师】回答得非常好，那有谁知道串的基本操作呢？

【学生】J)StrAssign(&sl,s2)。将串si赋值为s2。

(2)StrLcngth(s)o返回串的长度。

(3)StrConcat(sl,s2,&s)或StrConcat(&sbs2).用s返回由串s2和

串si连接而成的新串。

(4)SubStr(s,pos,len)o返回串s中从第pos个字符开始长度为len的

子串。

(5)StrCompare(sl,s2)。比较串si和串s2的大小。若sl>s2,则返回

正整数;若si=s2,则返回0；若sl<s2,则返回负整数。

(6)StrIndex(s,t,pos)。返回串t在串s的第pos个字符之后首次出现

的位置，若t不是s的子串，则返回0o

(7)StrInsert(&s,pos,t)。在串s的第pos个字符之前插入串t。

(8)StrDelete(&s,pos>len)«删除串s中第pos个字符开始长度为len的

子串。

(9)StrReplace(&s,t,r)o用串r替换串s中出现的所有与串t相等的

不重叠子串。

(lO)StrEqual(s,t)o判断串s与串t是否相等。

【教师】简述串的存储结构。

【学生】申有三种存储表示，即定长顺序存储结构、堆分配存储结构和链式

存储结构。串的顺序存储结构类似于线性表的顺序存储结构，是用一组地

址连续的存储单元存储串值的字符序列;堆分配存储结构用一组空间足够

大、地址连续的存储单元存放串值字符序列，但其存储空间在程序运行过程

中才可以分配;串的链式存储结构类似于线性表的链式存储结构,把可利用

存储空间分成一系列大小相同的结点,每个结点有两个域:data域用来存放

字符,next域用来存放指向下一结点的指针。

【教师】简述串的模式匹配。

【学生】串的模式匹配又称子串的定位操作，是在主串s中定位子串t

的操作。首先，判断主串s中是否存在子串t,如果存在，则模式匹配

成功，并输出子串t在主串s中首次出现的位置；如果不存在，则模式

匹配失败。串定位操作Strindex(s,t,pos)的功能就是模式匹配(在

串匹配中，一般将主串称为目标串，子串称为模式串。

串的朴素模式匹配算法原理简单,但是当FI标串中存在多个和模式串“部

分匹配”的子串时，算法的效率降低。

【教师】点评并拓展知识。

4.2数组

【教师】通过讲解和自由讨论数组的定义、数组的存储结构与寻址、矩阵

的存储压缩，引导学生理解数组。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】简述数组的定义。

【学生】数组是高级程序设计语言已经实现的数据结构，由同一类型的元

素组成，依据下标顺序连续存储。对于一个数组，若已知其维数、元素类

型、存放顺序(高下标优先或低卜标优先)，只需知道其起始地址，就可以计

算出其中任一元素的内存地址。

【教师】简述数组的性质。

【学生】数组具有如下性质：

(1)定义数组就是指明数组中包含元素的个数，即指明数组的长度。换句

话说，数组具有固定长度。

(2)数组中的元素具有相同的数据类型。

(幻数组中的每个元素都和唯一的一组下标值相关联，即可以通过•组下

标值唯一确定数组中的一个元素。

(4)数组是一种随机存储结构，即可随机存取数组中的任意元素，时间复

杂度为0(1)。

【教师】简述数组的存储结构与寻址。

【学生】从理论上讲，数组可以使用两种存储结构，即顺序存储结构和链

式存储结构。然而，由于数组结构没有插入和删除元素的操作，所以便

用顺序存储结构较为适宜。数组一般不使用链式存储结构。数组是线性

表的推广。数组作为一种数据结构,其特点是数组中的元素本身可以是具

有某种结构的数据，但必须属于同一类数据类型。一般的数组结构使用顺

序存储结构,对多维数组分配时，要将其元素映象存储在一维存储器中，-

般用“先行后列”和“先列后行”两种存储方式进行顺序存放。

【教师】简述矩阵的存储压缩“

【学生】矩阵通常用二维数组来表示，但有某些特殊矩阵，如三角矩阵、对

称矩阵、对角矩阵和稀疏矩阵等，此类矩阵阶数很高但相同值或零元素很

多,为了节省存储空间,可以对这类矩阵进行压缩存储。

【教师】点评并拓展知识。

4.3案例实现一一单词检索计数和稀疏矩阵的运算

【教师】通过讲解和自由讨论案例1——单词检索计数、案例2——稀谛

矩阵的运算，引导学生理解案例。

【学生】阅读教材，带着疑问去学习、理解并记忆。

【教师】询问学生是否有尚未理解的地方

问题解决【学生】提出疑问

【教师】【学生】共同探讨解决

【教师】带领学生复习本项目的知识脉络

整体回顾

【学生】简要复述本项目的知识框架

【教师】请学生完成本项目的［实训习题四］

布置作业

【学生】自行做题与核对答案进行自我检测

教学反思

《数据结构》教学设计

项目五树和二叉树

教材导读

课程名称《数据结构》课程类型理论课()/实践课()

树结构在客观世界中是大量存在的，如家族谱、单位下行机构的设置,以及

书的目录等，其在计算机领域中也有着广泛的应川，如磁盘中文件的目录

结构等,可以说,它类似于自然界中的树。通过对树结构的学习，有助于我

课程定位

们从整体出发,追根溯源，了解事物的内在逻辑,用更为科学、理性的方式

观察不同事物之间的关系,进而全方位、辩证地分析问题，以便做出更明智

的决策。

教案设计

项目课题项目五：树和二叉树

授课时间授课对象

1.理解树的逻辑结构和基本术语。

2理解二叉树的递归定义,掌握二叉树的性质.

二掌握二叉树的遍历，能确定遍历所得到的结点访问序列。

知识目标4.掌握二叉树的存储方法和基本操作的算法。

5•.掌握树、森林与二叉树之间的转换方法。

6.能根据给定的叶结点及其权值构造出相应的最优二叉树。

7.能根据最优二叉树构造对应的哈夫曼编码。

工具有用树来描述实际问题、应用二又树解决实际问题的能力。

能力目标

2.具有恰当选择二叉树作为数据的逻辑结构和存储结构的能力。

1.培养严谋的逻辑思维能力。

素质目标

2.加强学生创新意识和工匠精神的培养。

重、难点重点.掌握二叉树的遍历，能确定遍历所得到的结点访问序

列。

掌握二叉树的存储方法和基本操作的算法。

掌握树、森林与二叉树之间的转换方法。

能根据给定的叶结点及其权值构造出相应的最优二叉

树。

能根据最优二叉树构造对应的哈夫曼编码。

难点

具有用树来描述实际问题、应用二叉树解决实际问题的

能力。

教学方法讲授法

教学用具教材、课件、教案、微课、投影仪、计算机等

教学流程

教学环节教学内容

【教师】本项目介绍了树和二叉树的相关内容。大家对树和二叉树都了解

多少呢？请小组讨论一下。

情境导入【学生】小组讨论并回答问题。

【教师】归纳学生提出的主要想法，发现小组之间了解程度不一，引起学

生好奇心，激发学习新知的兴趣。

5.1树的概述

【教师】通过讲解和自由讨论树的相关概念及基本操作、树结构的逻辑特

征、树的存储结构，引导学生理解树。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】谁来简述树的概念？

【学生】树(Tree)是n(n>0)个结点的有限集合T,T为空时称为空树，

否则它满足以下两个条件。

讲授新知(1)有且仅有一个特定的根(Root)结点。

(2)其余的结点可分为m(m妾0)个互不相交的有限子集T1、T2、…、其，

其中每个子集本身又是一棵树，并称其为根结点的子树(SubTree)。

【教师】回答得非常好，那有谁知道树的基本操作呢？

【学生】(DlnitTreeOo初始化一棵空树，返回空指针。

(2)CreateTree()o创建一棵树，返回指向根结点的指针。

(3)DestroyTree(T)«销毁树T。

(4)EmptyTree(T)o判断所给出的树T是否为空。若树为空，则返回

true；否则返回false。

(5)GetFoot(T)o求树T的根结点。若树非空，则返回指向根结点的指

针；否则返回空。

(6)TreeDepth(T)o求树T的深度。

(7)Parent(T,x)o求树T中结点x的双亲结点。若树非空且结点x存

在且X不是根结点，则返回指向X的双亲结点的指针；否则返回空。

(8)LeftChiId(T,x)0求树T中结点x的最左边孩子结点。若树非空

且结点X存在且结点X有孩子结点，则返回指向X的最左边孩子结点

的指针；否则返回空。

(9)RigktSibling(T,x)。求树T中结点x的右兄弟结点。若树非空

且结点X存在且结点X有右兄弟结点，则返回指向X的右兄弟结点的指

针；否则返回空。

(10)InsertChiId(T,p,i,q)。将子树q插入树T中，作为p所指

结点的第i棵子树。P为指针，lWi<n+l(n为p所指向的结点的度)。

(H)DeleteChild(T,p,i)。删除树T中p所指结点的第i棵子树，

P为指针，lWiWn(n为p所指向的结点的度)。

(12)Fir.dNode(T,x)。在树T中查找数据元素x,若找到，则返回指向

该元素的指针；否则返回空。

(13)PreOrder(T)o当树T非空时，前序遍历树。

(14)PostOrder(T)o当树T非空时，后序遍历树。

(15)LevelTravel(T)。当树T非空时，层次遍历树。

【教师】简述树的特点。

【学生】树的特点是:除根结点和叶子结点外,其他的结点都只有一个直接

前驱和一个或多个直接后继。根结点只有直接后继结点，而叶子结点则只

有前驱结点。

【教师】简述树的存储结构。

【学生】1.双亲表示法

2.孩子链表表示法

3.双亲孩子表示法

4.孩子兄弟表示法

【教师】点评并拓展知识。

5.2二叉树

【教师】通过讲解和自由讨论二叉树的定义、二叉树的基本性质、二叉树

的基本操作、二叉树的存储结构、二叉树遍历、二又树遍历的应用，引导

学生理解二又树。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】简述二叉树的定义。

【学生】1.二叉树的递归定义

二叉树(BinaryTree)是n(n20)个结点的有限集，或者是空集(n=0),

或者由一个根结点及两棵互不相交的、分别称为这个根结点的左子树和右

子树的二叉树组成。

2.二叉树的基本形态

二叉树可以是空集，可以有空的左子树或空的右子树，或者左、右子树皆

为空。

【教师】简述二叉树的特殊形态。

【学生】二叉树有两种特殊形态：满二叉树和完全二叉树。

【教师】简述二叉树的基本性质。

【学生】性质1非空二叉树上第层上至多有2i-1个结点。

性质2深度为h的二叉树至多有2h-l个结点(hNl)。

性质3对任何一棵非空二叉树，如果其度为0的结点数为n0,度为2

的结点数为n2,则n0=n2+l。

性质4具有n(n>0)个结点的完全二叉树的深度为[log2n]+l或为

[log2(n+l)b

性质5对一棵有n个结点的完全二叉树，从1开始按层序(按从上到

下、从左到右的顺序)编号，则编号为i(lWiWn)的结点有：

(1)如果i=1,则结点i是二叉树的根结点，无双亲结点；如果i>l,

则结点i的双亲结点的编号是。

(2)如果2i>n,则结点i无左孩子(结点i为叶子结点)；否则其左孩子

结点的编号是2i。

(3)如果2i+l>n,则结点i无右孩子；否则其右孩子结点的编号是2i+lo

【教师】简述二叉树的存储结构。

【学生】1.顺序存储结构

二叉树的顺序存储结构就是用一组地址连续的存储单元依次存放二叉树

的结点，并且能用结点的存储位置反映结点之间的逻辑关系(双亲和孩子

的关系)。

2.二叉链表

二叉树的二叉链表存储结构是指用链表的形式来存储二叉树，链表中的每

个结点包含两个指针域和一个数据域，故称为二叉链表。

3.三又链表

三叉链表在二叉链表的基础上增加了指向双亲结点的指针域parent,以

便快捷地访问该结点的双亲结点，解决了二叉链表对双亲结点操作不方便

的问题。

【教师】简述二叉树遍历。

【学生】二叉树的遍历方式分为前序、中序、后序和层序遍历。

【教师】点评并拓展知识。

5.3树、森林与二叉树

【教师】通过讲解和自由讨论树与二叉树的转换、森林与二叉树的转换、

树与森林的遍历，引导学生理解树、森林与二叉树。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】简述树与二叉树的转换。

【学生】1.树转换为二叉树

(1)加线：在所有相邻兄弟结点之间加一连线。

(2)去线：对每个结点，保留其与第一个孩子的连线，删去该结点与其他

孩子的连线。

(3)旋转：以树的根结点为轴心，将整棵树顺时针旋转45。，使之结构层

次分明。

2.二叉树转换为树

(1)加线：若某结点是其双亲结点的左孩子，则在该结点的右孩子、右孩

子的右孩子等与该结点的双亲结点之间分别加一条线。

(2)去线：删去原二叉树中所有的双亲结点与右孩子结点之间的连线，

(3)整理：整理所得到的树，使之结构层次分明。

【教师】简述森林与二叉树的转换。

【学生】1.森林转换为二叉树

林是若干棵树的集合。若把每棵树的根结点看作兄弟结点，则可用与树

转换为二叉树相似的方法将森林转换为二叉树。森林转换为二叉树的步

骤为：

(1)将森林中的每棵树转换为相应的二叉树。

(2)以森林中第一棵树转换成的二叉树作为森林转换后的二叉树的根结点

和左子树。

(3)从第二棵二叉树开始，依次把后一棵二叉树作为前一棵二叉树的右子

树。所有转换后的二叉树连在一起所得到的二叉树就是由森林转换后的

二叉树。

2.二又树转换为森林

转换为森林的二叉树必须是一棵有右子树的二叉树。二叉树转换为森林

的步骤为：

(1)加线：若某结点是其双亲结点的左孩子，则在该结点的右孩子、右孩

子的右孩子等与该结点的双亲结点之间分别加一条线。

(2)去线：删去原二叉树中所有的双亲结点与右孩子结点之间的连线，

(3)整理：整理所得到的树，使之结构层次分明，形成森林。

【教师】简述树与森林的遍历。

【学生】照访问根结点的次序不同，树的遍历分为前序遍历和后序遍历。

森林的遍历也有两种：前序遍历和后序遍历。前序遍历森林即前序遍历

森林中的每一棵树，后序遍历森林即后序遍历森林中的每一棵树。

【教师】点评并拓展知识。

5.4哈夫曼树及其应用

【教师】通过讲解和自由讨论哈夫曼树、哈夫曼编码，引导学生理解哈夫

曼树及其应用。

【学生】阅读教材，认真听讲解，自由讨论，理解并记忆。

【教师】简述哈夫曼树的基本概念。

【学生】(1)路径和路径长度

从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路

径上的分支数目称作路径长度。

(2)树的路径长度

树的路径长度是指从树的根结点到每一结点的路径长度之和。

(3)树结点的权

为树中的结点赋予一个有着某种意义的实数，称此实数为该结点的权。

(4)结点的带权路径长度

结点的带权路径长度是指从树的根结点到该结点之间的路径长度与该结

点的权的乘积。

(5)树的带权路径长度

树的带权路径长度是指树中所有叶子结点的带权路径长度之和。

(6)哈夫曼树

给定一组带有权值的叶子结点，可以构造出许多带权路径长度不同的二又

树，其中带权路径长度最小的二叉树称作哈夫曼树。

【教师】简述哈夫曼编码。

【学生】哈夫曼编码就是一种不等长的前缀编码。以要编码的字符为叶

子结点，以字符出现的频率为叶子结点的权值，构造一棵哈夫曼树。在

哈夫曼树中，约定左结点表示字符“0”，右结点表示字符“1”，从根结

点到叶子结点所经过的所有结点所对应的0和1组成的序列即为该叶

子结点的编码，这就是哈夫曼编码。

【教师】点评并拓展知识。

5.5案例实现一一人事管理系统

【教师】通过练习人事管理系统的案例，引导学生更加深刻地了解本项目。

【学生】阅读教材，带着疑问去学习、理解并记忆。

【教师】询问学生在本次任务中学到了什么方法。