《数据结构（C语言版）》教案

本文格式为Word版，下载可任意编辑——《数据结构（C语言版）》教案2022至2022学年第一学期教案课程名称数据布局使用教材《数据布局（C语言版）》教学时数56课程性质必修任课班级（人数）信管（53人）信息系（部）信管教研室任课教师山东科技大学泰山科技学院课时授课计划2022-2022学年第二学期第1周授课日期2月20日星期1月日星期月日星期月日星期月日星期班级信管10-1根本课题第1章绪论1.1-1.2教学目的与要求：

1.了解数据布局的根本概念2.理解常用术语教学重点：

数据布局的根本概念和术语教学难点：

数据元素之间的四种布局关系作业及参考书：

1、什么是数据布局？《数据布局算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：自我介绍——开课——引入——开展——举例——小结——作业一、自我介绍和课程介绍约8min课时：64二、引入约2min由问题的提出引入三、讲课进程设计1.1什么是数据布局1.1.1、数据布局与其它的关系约15min数据布局+算法=程序程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据布局:问题的数学模型1.1.2、当今计算机应用的特点：

约25minl)所处理的数据量大且具有确定的关系；

2)对其操作不再是单纯的数值计算，而更多地是需要对其举行组织、管理和检索。

举例说明：

1)学生劳绩表2)井安棋对弈3)交通管理结论计算机的操作对象的关系更加繁杂，操作形式不再是单纯的数值计算，而更多地是对这些具有确定关系的数据举行组织管理；

我们将此称为非数值性处理。要使计算机能够更有效地举行这些非数值性处理，就务必弄领会这些操作对象的特点，在计算机中的表示方式以及各个操作的概括实现手段。

1.2根本概念和术语1.1.1、数据与数据布局约20min数据：是对客观事物的符号表示。

全体能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。

数据元素：是数据（集合）中的一个“个体”，是数据布局中议论的根本单位。

数据对象：是性质一致的数据元素的集合，是数据的一个子集。

数据布局：是相互之间存在一种或多种特定关系的数据元素的集合。这种集合称为布局。

数据的规律布局可归结为以下四类:

种类特征例如集合元素间为松散的关系

线性布局元素间为严格的一对一关系如上面的劳绩表中各元素树形布局元素间为严格的一对多关系图状布局（或网状布局）元素间为多对多关系数据布局的形式定义为:数据布局是一个二元组数据的存储布局：——规律布局在存储器中的映像数据元素的映象方法：计算机中存储信息的最小单位：位，8位为一字节，两个字节为一字，字节、字或更多的二进制位可称为位串。在规律描述中，把位串称为元素或结点。

关系的映象方法：依次映象链式映象1.2.2、数据类型约5min数据类型是一个值的集合和定义在此集合上的一组操作的总称。

1.2.3、抽象数据类型约20min是指一个数学模型以及定义在此数学模型上的一组操作。

关键：使用它的人可以只关切它的规律特征，不需要了解它的存储方式。定义它的人同样不必要关切它如何存储。

抽象数据类型表示法：

三元组表示：（D，S，P）其中D是数据对象，S是D上的关系集，P是对D的根本操作集。

书中的定义格式：

ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义根本操作：根本操作的定义}ADT抽象数据类型名ADT有两个重要特征:数据抽象数据封装四、本次课小结：

约3min1.熟谙各名词2.术语的含义3.掌管根本概念五、作业约2min2、什么是数据布局？课时授课计划2022-2022学年第二学期第1周授课日期2月24日星期5月日星期月日星期月日星期月日星期班级信管10-1根本课题抽象数据类型的表示与实现算法和算法分析教学目的与要求：

类C语言的各种句型及算法描述的模范教学重点：

类C语言的各种句型及算法描述的模范教学难点：

类C语言的各种句型及算法描述的模范作业及参考书：

《数据布局算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：复习——引入——开展——举例——小结——作业一、复习：

约5min1、数据布局的根本概念2、一些根本术语二、引入约2min由程序设计过程遇到的问题引入三、讲课进程设计1.3抽象数据类型的表示与实现1.3.1根本操作：

约15minAssignComplex(Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。

DestroyComplex(Z)操作结果：复数Z被销毁。

GetReal(Z,realPart)初始条件：复数已存在。

操作结果：用realPart返回复数Z的实部值。

GetImag(Z,ImagPart)初始条件：复数已存在。

操作结果：用ImagPart返回复数Z的虚部值。

Add(z1,z2,sum)初始条件：z1,z2是复数。

操作结果：用sum返回两个复数z1,z2的和值。

1.3.2对本书所采用的类C语言作简要说明约18min1.预定义常量及类型2、数据布局的存储布局typedef3、算法描述为以下的函数形式：

4.在算法描述中可以使用的赋值语句形式有：

5.在算法描述中可以使用的选择布局语句形式有：

6.在算法描述中可以使用的循环布局语句形式有：

7.在描述算法中可以使用的终止语句形式有：

8.在算法描述中可以使用的输入输出语句形式有：

9.在算法描述中使用的解释格式为：

10.在算法描述中可以使用的扩展函数有：

11.规律运算商定1.4算法和算法分析1.4.1、算法约10min算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法务必得志以下五个重要特性：

1．有穷性2．确定性3．可行性4．有输入5．有输出1.4.2、算法设计的原那么约10min设计算法时，通常应考虑达成以下目标：

1．正确性2.可读性3．刚强性4．高效率与低存储量需求1.4.3、算法效率的衡量方法和准那么约20min通常有两种衡量算法效率的方法事后统计法缺点：1．务必执行程序2．其它因素掩盖算法本质事前分析估算法和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度算法=操纵布局+原操作（固有数据类型的操作）一个算法的执行时间大致上等于其全体语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。

在计算时间繁杂度时所采用的记号“O”是数学符号，其严格的数学定义是：若T(n)和f(n)是定义在正整数集合上的两个函数，那么T(n)=O(f(n))表示存在正的常数c和n0，使得当n=n0时都得志0=T(n)=cf(n)程序分析法那么为：

1.执行一条读写或赋值语句用O(1)时间2、依次执行一系列语句所用时间用和准那么3、判断语句的耗时主要是执行语句所用的时间，检验条件还需O(1)4、循环语句的运行时间为屡屡叠代中执行循环体以及检验循环条件的耗时，常用乘法准那么若算法的两个片面的时间繁杂度为T1(n)=o(f(n))和T2(n)=o(g(n))那么大“O”下的：

求和准那么为T1(n)+T2(n)=O(max(f(n),g(n))乘法准那么为T1(n)*T2(n)=O((f(n)*g(n))1.4.4、算法的存储空间需求约10min算法的空间繁杂度定义为:S(n)=O(g(n))表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率一致。

算法的存储量包括:1．输入数据所占空间2．程序本身所占空间3．辅佐变量所占空间四、小结：

约5min1.理解算法五个要素确实切含义。

2.掌管计算语句频度和估算算法时间繁杂度的方法。

五、作业约5min1、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间繁杂度，要求时间繁杂度尽可能的小，规定算法中不能使用求幂函数。留神：此题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0).通常算法的输入和输出可采用以下两种方式之一：

•（1）通过参数表中的参数显式传递；

（2）通过全局变量隐式传递。

•试议论这两种方法的优缺点，并在此题算法中以你认为较好的一种方式实现输入和输出。

课时授课计划2022-2022学年第二学期第2周授课日期2月27日星期月日星期月日星期月日星期月日星期班级信管10-1根本课题线性表的类型定义线性表的依次表示和实现教学目的与要求：

1、掌管线性表的概念和类型定义2、掌管线性表的依次表示和实现方法教学重点：

线性表的类型定义线性表的依次表示和实现方法教学难点：

线性表的类型定义线性表的依次存储的实现方法作业及参考书：

《数据布局算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：复习——引入——开展——举例——小结一、引入约3min由依次的算法引入二、讲课进程设计2．1线性表的类型定义12.1.1线性表的定义约27min线性表是由n（n≥0）个类型一致的数据元素组成的有限序列。

抽象数据类型线性表的定义如下：

ADTList{数据对象D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}根本操作：

布局初始化操作：

InitList(L)操作结果：构造一个空的线性表L。布局销毁操作：

DestroyList(L)初始条件：线性表L已存在。操作结果：销毁线性表L。

引用型操作ListEmpty(L)（线性表判空）ListLength(L)（求线性表的长度）PriorElem(L,cur_e,pre_e)（求数据元素的前驱）NextElem(L,cur_e,next_e)（求数据元素的后继）GetElem(L,i,e)（求线性表中某个数据元素）LocateElem(L,e,compare())（定位函数）ListTraverse(L,visit())（遍历线性表）加工型操作ClearList(L)（线性表置空）PutElem(L,i,e)（变更数据元素的值）ListInsert(L,i,e)（插入数据元素）ListDelete(L,i,e)（删除数据元素）2.1.2举例约10min两个线性表合并LA和LB2.2线性表的依次表示和实现2.2.1依次映象约15min——以x的存储位置和y的存储位置之间某种关系表示规律关系x,y。

最简朴的一种依次映象方法是：

令y的存储位置和x的存储位置相邻。线性表的根本操作在依次表中的实现InitList(L)//布局初始化LocateElem(L,e,compare())//查找ListInsert(L,i,e)//插入元素ListDelete(L,i)//删除元素2.1.1、线性表操作约20minListInsert(L,i,e)的实现：

首先分析插入元素时，线性表的规律布局发生什么变化？线性表操作ListDelete(L,i,e)的实现：

首先分析：

删除元素时，线性表的规律布局发生什么变化？线性表类型的实现2.1.2、线性表依次存储布局的特点：

约20min它是一种简朴、便当的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储依次表示相应的规律依次，这种存储方式属于静态存储形式。

暴露的问题(1)在做插入或删除元素的操作时，会产生大量的数据元素移动；

(2)对于长度变化较大的线性表，要一次性地调配足够的存储空间，但这些空间往往又得不到充分的利用；

(3)线性表的容量难以扩展。

三、小结约5min1.了解线性表的规律布局特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储布局是依次存储布局和链式存储布局。用前者表示的线性表简称为依次表，用后者表示的线性表简称为链表。

2.纯熟掌管这两类存储布局的描述方法，以及线性表的各种根本操作的实现。

课时授课计划2022-2022学年第二学期第2周授课日期3月3日星期月日星期月日星期月日星期月日星期班级信管10-1根本课题线性表的链式表示和实现一元多项式的表示及相加教学目的与要求：

1、掌管线性链表、单链表、静态链表的概念、表示及实现方法。

2、掌管循环链表的概念3、掌管双向链表的表示与实现教学重点：

1、线性链表之单链表的表示及实现方法。

2、双向链表的表示与实现教学难点：

1、线性链表2、双向链表的存储表示作业及参考书：

写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不一致。

《数据布局算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：复习——引入——开展——举例——小结——作业一、复习约5min复习线性表有的概念二、引入约2min由线性表的表示不便当引入三、讲课进程设计2.3线性表的链式表示和实现线性表依次存储布局的特点：

约10min它是一种简朴、便当的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储依次表示相应的规律依次，这种存储方式属于静态存储形式。

暴露的问题(1)在做插入或删除元素的操作时，会产生大量的数据元素移动；

(2)对于长度变化较大的线性表，要一次性地调配足够的存储空间，但这些空间往往又得不到充分的利用；

(3)线性表的容量难以扩展。

2.3.1、单链表约10min用一组地址任意的存储单元存放线性表中的数据元素（这组存储单元可以是连续的也可以是不连续的）。

2.3.2、结点和单链表的C语言描述约10min2.3.3、单链表操作的实现约13min因此生成链表的过程是一个结点“逐个插入”的过程。

操作步骤：

1、建立一个“空表”；

2、输入数据元素an，建立结点并插入；

3、输入数据元素an-1，建立结点并插入；

4、依次类推，直至输入a1为止。

2.3.4、其它形式的链表约5min1.循环链表2.双向链表2.3.5、有序表类型约5min2.4一元多项式的表示2.4.1一元多项式约20min在计算机中，可以用一个线性表来表示:P=(p0,p1,…，pn)抽象数据类型一元多项式的定义如下：

ADTPolynomial{数据对象：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n且ai-1中的指数值＜ai中的指数值}根本操作：

CreatPolyn(P,m)操作结果：输入m项的系数和指数，建立一元多项式P。

DestroyPolyn(P)初始条件：一元多项式P已存在。

操作结果：销毁一元多项式P。

PrintPolyn(P)初始条件：一元多项式P已存在。

操作结果：打印输出一元多项式P。

PolynLength(P)初始条件：一元多项式P已存在。

操作结果：返回一元多项式P中的项数。

AddPolyn(Pa,Pb)初始条件：一元多项式Pa和Pb已存在。

操作结果：完成多项式相加运算，即：

Pa=Pa＋Pb，并销毁一元多项式Pb。

SubtractPolyn(Pa,Pb)……}ADTPolynomial2.4.2一元多项式的实现：

约10mintypedefOrderedLinkListpolynomial;//用带表头结点的有序链表表示多项式四、小结约5min1.能够从时间和空间繁杂度的角度综合对比线性表两种存储布局的不同特点及其适用场合。

五、本章作业：

约5min写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不一致。

此题可以这样考虑，先取开头结点中的值，将它与其后的全体结点值一一对比，察觉一致的就删除掉，然后再取其次结点的值，重复上述过程直到结果一个结点。

课时授课计划2022-2022学年第一学期第3周授课日期9月22日五星期月日星期月日星期月日星期月日星期班级信管10-1根本课题栈栈的应用举例教学目的与要求：

1、栈的数据类型定义2、栈的依次存储与实现3、掌管栈的应用方法，理解栈的重要作用教学重点：

1、栈的依次存储表示与实现方法2、利用栈实现行编辑、利用栈实现表达式求值教学难点：

1、栈的定义2、利用栈实现表达式求值作业及参考书：

1、栈定义的应用2、栈的特点《数据布局算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——开展——举例——小结——作业一、引入约10min1.什么是线性布局？

2.以餐馆中一叠一叠的盘子的使用为例，引出栈的特点。

二、讲课进程设计3.1栈的类型定义3.1.1、栈、栈顶(top)、栈底(bottom)的定义约10min3.1.2栈的类型定义约10min3.2栈的应用举例例一、数制转换约10min十进制数N和其他d进制数的转换是计算机实现计算的根本问题，个简朴算法基于以下原理：

N=(Ndivd)×d+Nmodd(其中：div为整除运算，mod为求余运算)例二、括号匹配的检验约10min检验括号是否匹配的方法可用“期望的急迫程度”这个概念来描述。

三种处境对应到栈的操作即为：

1．和栈顶的左括弧不相匹配；

2．栈中并没有左括弧等在哪里；

3．栈中还有左括弧没有等到和它相匹配的右括弧。

例三、行编辑程序问题约10min在用户输入一行的过程中，允许用户输入出过错，并在察觉有误时可以实时更正。

合理的作法是：设立一个输入缓冲区，用以采纳用户输入的一行字符，然后逐行存入用户数据区,并假设“#”为退格符，“@”为退行符。

例四、迷宫求解约10min假设以栈S记录“当前路径”，那么栈顶中存放的是“当前路径上结果一个通道块”。

“纳入路径”的操作即为“当前位置入栈；

“从当前路径上删除前一通道块”的操作即为“出栈“。

例五、表达式求值约10min任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。

例六、实现递归约10min递归函数的实现一个递归函数的运行过程类似于多个函数的嵌套调用，区别仅在于“调用函数和被调用函数是同一个函数”。为了保证“每一层的递归调用”都是对“本层”的数据举行操作，在执行递归函数的过程中需要一个“递归工作栈”。

三、小结约5min1.掌管栈和队列类型的特点，并能在相应的应用问题中正确选用它们。

2.纯熟掌管栈类型的两种实现方法，特别应留神栈满和栈空的条件以及它们的描述方法。

四、作业约5min1、4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，那么不成能的出栈序是（）(A)a4，a3，a2，a1(B)a3，a2，a4，a1(C)a3，a1，a4，a2(D)a3，a4，a2，a12、栈的特点是（）。

课时授课计划2022-2022学年第一学期第3周授课日期9月27日三星期月日星期月日星期月日星期月日星期班级信管10-1根本课题队列教学目的与要求：

1.纯熟掌管循环队列和链队列的根本操作实现算法。

2.理解递归算法执行过程中栈的状态变化过程。

教学重点：

1．链队的表示与实现教学难点：.1。链队的表示与实现作业及参考书：

1．栈与队列的对比2．读程序段《数据布局算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——开展——举例——小结——作业一、引入约5min在日常生活中，为了维持正常的社会秩序而展现的常见现象是什么？是“排队“。在计算机程序中，模拟排队的数据布局是“队列“。

二、讲课进程设计3.4队列1队列的定义约10min2队列的抽象类型定义约15min3.队列的根本操作：

约20minInitQueue(Q)操作结果：构造一个空队列Q。

DestroyQueue(Q)初始条件：队列Q已存在。

操作结果：队列Q被销毁，不再存在。

QueueEmpty(Q)初始条件:队列Q已存在。

操作结果:若Q为空队列,那么返回TRUE，否那么返回FALSE。

QueueLength(Q)初始条件:队列Q已存在。

操作结果:返回Q的元素个数，即队列的长度。

GetHead(Q,e)初始条件：Q为非空队列。

操作结果：用e返回Q的队头元素。

ClearQueue(Q)初始条件：队列Q已存在。

操作结果：将Q清为空队列。

EnQueue(Q,e)初始条件:队列Q已存在。

操作结果:插入元素e为Q的新的队尾元素。

DeQueue(Q,e)初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返回其值。

QueueTravers(Q,visit())队列类型的实现4.链队列——链式映象约15min5.循环队列——依次映象约20min队列在程序设计中的一个典型应用例子是作业排队问题。

三、小结约5min1.纯熟掌管循环队列和链队列的根本操作实现算法，更加留神队满和队空的描述方法。

2.理解递归算法执行过程中栈的状态变化过程。

四、作业约10min1、线性表、栈和队列都是（）布局,可以在线性表的（）位置插入和删除元素，对于栈只能在（）插入和删除元素，对于队列只能在（）插入元素和（）删除元素。

2、指出下述程序段的功能是什么?

(1)voidDemo1(SeqStack*S){inti;arr[64];n=0;while(StackEmpty(S))arr[n++]=Pop(S);for(i=0,in;i++)Push(S,arr[i]);}//Demo1课时授课计划2022-2022学年第一学期第4周授课日期月日星期月日星期月日星期月日星期月日星期班级信管10-1根本课题测验二栈和队列的总结复习教学目的与要求：

1、深入了解栈和队列的特征，以便在实际问题背景下生动运用它们；

2、稳定这两种布局的构造方法，接触较繁杂问题的递归算法设计。

教学重点：

稳定这两种布局的构造方法，接触较繁杂问题的递归算法设计。

教学难点：

稳定这两种布局的构造方法，接触较繁杂问题的递归算法设计。

作业及参考书：

《数据布局算法实现及解析》/高一凡编著教具：

课堂类型：

教学过程：

停车场管理[问题描述]设停车场内只有一个的停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后依次，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，那么后来的汽车只能在门外的便道上等候，一旦有车开走，那么排在便道上的第一辆车即可开入；

当停车场内某辆车要离开时，在它之后开入的车辆务必先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时务必按它停留的时间长短交纳费用。试为停车场编制按上述要求举行管理的模拟程序。

[测试数据]设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。其中，‘A’表示到达；

‘D’表示离去，‘E’表示输入终止。

[根本要求]以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列举行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据举行操作后的输出数据为：若是车辆到达，那么输出汽车在停车场内或便道上的停车位置；

若是车离去；

那么输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以依次布局实现，队列以链表实现。

[实现提示]需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用依次存储布局实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。

[选作内容]（1）两个栈共享空间，斟酌应开发数组的空间是多少？（2）汽车可有不同种类，那么它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积一致，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。

（3）汽车可以直接从便道上开走，此时派在它前面的汽车要先开走让路，然后再依次排到队尾。

（4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请斟酌如何修改布局以得志这种要求。

课时授课计划2022-2022学年第一学期第4周授课日期10月8日日星期月日星期月日星期月日星期月日星期班级信管10-1根本课题串教学目的与要求：

1、熟谙串七种根本操作的定义，并能利用这些根本操作实现传的其他各种操作的方法。

2、熟谙掌管在串的定长依次存储布局上实现串的各种操作的方法。

3、掌管串的堆存储布局以及在其上实现串的各种操作的根本方法。

教学重点：

1、串七种根本操作的定义2、串的定长依次存储3、串的堆存储布局教学难点：

1、串七种根本操作的定义2、串的堆存储布局作业及参考书：

对串的操作的应用《数据布局算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——开展——举例——小结——作业一、引入约5min计算机上的非数值处理的对象根本上都是字符串数据。

二、讲课进程设计4.1串的抽象数据类型的定义1.定义约10min串、串长、空串、子串、主串、位置、相等、空格串2.串的抽象数据类型的定义约10minStrAssign(T,chars)StrCopy(T,S)DestroyString(S)StrEmpty(S)StrCompare(S,T)StrLength(S)Concat(T,S1,S2)SubString(Sub,S,pos,len)Index(S,T,pos)Replace(S,T,V)StrInsert(S,pos,T)StrDelete(S,pos,len)ClearString(S)4.2串的表示和实现4.2.1、串的定长依次存储表示约15min1.串联接2.求子串4.2.2、串的堆调配存储表示约20min通常，C语言中供给的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()举行串值空间的动态管理，为每一个新产生的串调配一个存储区，称串值共享的存储空间为“堆”。

4.2.3、串的块链存储表示约10min也可用链表来存储串值，由于串的数据元素是一个字符，它只有8位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。

4.4串操作应用举例4.4.1文本编辑约20min可用于文本编辑的程序好多，功能强弱区别很大，但根本操作是一致的：都包括串的查找，插入和删除等根本操作。

对用户来讲，一个文本（文件）可以包括若干页，每页包括若干行，每行包括若干文字。

对文本编辑程序来讲，可把整个文本看成一个长字符串，称文本串，页是文本串的子串，行又是页的子串。为简化程序繁杂程度，可简朴地把文本分成若干行。

三、小结约5min1.熟谙串的七种根本操作的定义，并能利用这些根本操作来实现串的其它各种操作的方法。

2.纯熟掌管在串的定长依次存储布局上实现串的各种操作的方法。

3.了解串的堆存储布局以及在其上实现串操作的根本方法。

4.了解串操作的应用方法和特点。

四、作业约5min假设有如下的串说明：

chars1[30]=“Stocktom,CA“,s2[30]=“March51999”,s3[30],*p;(1)在执行以下语句后，s3的值是什么?strcopy(s3,s1);concat(s3,“,“);concat(s3,s2);(2)调用函数strcompare(s1,s2)的返回值是什么?(3)调用函数strcompare(s1[5],“ton“)的返回值是什么?(4)调用函数strlength(concat(s1,s2))的返回值是什么?课时授课计划2022-2022学年第一学期第5周授课日期10月11日三星期月日星期月日星期月日星期月日星期班级信管10-1根本课题数组教学目的与要求：

1、掌管数组的定义2、掌管数组的依次表示方法教学重点：

1、数组的定义2、数组的依次表示方法教学难点：

数组的依次表示方法作业及参考书：

《数据布局算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——开展——举例——小结一、引入约5min由前几章议论的线性布局中的数据元素都是非布局的原子类型引入数组。

二、讲课进程设计5.1数组的类型定义抽象数据类型定义约5minADTArray{数据对象：

数据关系：

}ADTArray二维数组的定义:约10min数据对象:D={aij|0≤i≤b1-1,0≤j≤b2-1}数据关系:R={ROW,COL}ROW={ai,j,ai+1,j|0≤i≤b1-2,0≤j≤b2-1}COL={ai,j,ai,j+1|0≤i≤b1-1,0≤j≤b2-2}根本操作：

约10minInitArray(A,n,bound1,...,boundn)DestroyArray(A)Value(A,e,index1,...,indexn)Assign(A,e,index1,...,indexn)5.2数组的依次表示和实现类型特点:约10min1)只有引用型操作，没有加工型操作；

2)数组是多维的布局，而存储空间是一个一维的布局。

有两种依次映象的方式:约10min1)以行序为主序(低下标优先)；

2)以列序为主序(上下标优先)。

5.3矩阵的压缩存储5.3.1特殊矩阵a.对称矩阵约15min定义压缩存储方式b.三角矩阵约15min定义压缩存储方式c.对角矩阵约20min定义压缩存储方式三、小结1、数组的特殊性2、数组的存储3、特殊矩阵的存储课时授课计划2022-2022学年第二学期第5周授课日期3月23日三星期月日星期月日星期月日星期月日星期班级信管10-1根本课题稀疏矩阵广义表教学目的与要求：

1、掌管稀疏矩阵的定义，三元组表示2、掌管广义表的定义，它的链接存储布局教学重点：

1、三元组表示2、广义表的存储布局教学难点：

1、三元组表示法2、定义作业及参考书：

1、画出给出的广义表的两种存储布局2、求广义表的运算3、在对象矩阵中求下标变换公式《数据布局算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——开展——举例——小结——作业一、引入约5min由特殊矩阵引入二、讲课进程设计5.3.2稀疏矩阵1、定义约5min两类稀疏矩阵：1)特殊矩阵2)随机稀疏矩阵2、随机稀疏矩阵的压缩存储方法:1、三元组依次表约20min2、行规律联接的依次表约20min3、十字链表约10min5.4广义表广义表的定义约20min1、广义表：

表头：非空广义表的第一个元素α1表尾：其余元素（α2，…，αn）组成的表。

2、广义表的抽象数据类型定义3、广义表的操作：

5.5广义表的的存储布局由于广义表中的数据元素可以具有不同的布局．因此，采用链式存储布局表示广义表。每个数据元素可用一个结点表示。

1、广义表的头尾链表存储表示约10mintypedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{AtomTypeatom;struct{structGLNode*hp,*tp;}ptr};}*GList;三、小结约5min1.了解数组的两种存储表示方法，并掌管数组在以行为主的存储布局中的地址计算方法。2.掌管对特殊矩阵举行压缩存储时的下标变换公式。3.了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时举行矩阵运算采用的处理方法。4、掌管广义表的布局特点及其存储表示方法，读者可根据自己的习惯纯熟掌管任意一种布局的链表，学会对非空广义表举行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两片面或者分解为n个子表。

四、课后作业及习题约5min1、画出下面广义表的两种存储布局图示：

((((a),b)),(((),d),(e,f)))2、求以下广义表运算的结果：

（1）

GetHEAD[((a,b),(c,d))];（2）

GetTAIL[((a,b),(c,d))];（3）

GetTAIL[HEAD[((a,b),(c,d))]];（4）

GetHEAD[TAIL[HEAD[((a,b),(c,d))]]];（5）

GetTAIL[HEAD[TAIL[((a,b),(c,d))]]];3、设有三对角矩阵An×n,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]=aij，求：（1）

用i,j表示k的下标变换公式；

（2）

用k表示i,j的下标变换公式。

课时授课计划2022-2022学年第一学期第6周授课日期10月20日五星期月日星期月日星期月日星期月日星期班级信管10-1根本课题树的定义和根本术语二叉树教学目的与要求：

1、掌管树、二叉树的根本概念和术语，二叉树的性质2、掌管二叉树的两种存储布局教学重点：

1、二叉树的性质和定义2、链式存储布局教学难点：

1、二叉树的性质2、链式存储二叉树的根本操作作业及参考书：

1、一棵度为2的树与二叉树的识别2、3个结点的树与3个结点的二叉树《数据布局算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——开展——举例——小结——作业一、引入约5min由前几章的线性布局带来的问题引出非线性布局。

二、讲课进程设计第6章树和二叉树6.1树的定义和根本术语1、树的定义约10min树是包含n个结点的有限集合(n0)Tree=(D,R)其中，D是具有一致性质的数据元素的集合，若D中只有一个元素，那么R为空集，否那么R是D上某个二元关系H的集合，H是如下描述的二元关系：

（1）在D中存在唯一一个称为根的元素r0,它在关系H下无前驱；

（2）除结点r0外,K中每个结点对于关系H来说，都有且只有一个前驱。

（3）结点r0外的任何结点rR，都存在一个结点序列r0,r1,…,rs,ri-1,riH(1=i=s),这样一个结点序列称为根到结点r的路径。

树的例子：家族，机构等2、树的抽象数据类型的定义约5minADTTree数据对象D：

数据关系R：

根本操作P：

InitTree(T);DestroyTree(T);CreateTree(T,definition);ClearTree(T);……3、树的术语约10min结点：数据元素和指向子树的分枝；

终端结点（叶子），分枝结点子女：结点的子树的根称为结点的子女，该结点称为子女的双亲；

层次：根为第一层，根的子女为其次层，以此类推深度：树中结点的最大层次称为树的深度（或高度）度：结点的分枝数目树的度：树中结点的最大度兄弟：同一双亲的子女互称兄弟，其父母为兄弟的结点互称堂兄祖先：结点的祖先是从根到该结点所经分支上的全体结点子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。

有序树：结点的子树从左到右有依次，否那么，称为无序树森林树的不相交集合，除去根结点后的子树集合就是森林RF={root,ri|i=1,2,…,m,m0}6.2二叉树6.2.1二叉树的类型定义约15min二叉树是另一种树型布局，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。(树的度最大为2)二叉树的主要根本操作：

查找类Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());插入类InitBiTree(T);Assign(T,e,value);CreateBiTree(T,definition);InsertChild(T,p,LR,c);删除类ClearBiTree(T);DestroyBiTree(T);DeleteChild(T,p,LR);6.2.2二叉树的性质约20min性质1：

在二叉树的第i层上至多有2i-1个结点。

(i≥1)性质2：深度为k的二叉树上至多含2k-1个结点（k≥1）。

性质3：对任何一棵二叉树，若它含有n0个叶子结点（0度结点）、n2个度为2的结点，那么必存在关系式：n0=n2+1。

两类特殊的二叉树：

满二叉树：指的是深度为k且含有2k-1个结点的二叉树。

完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。（编号的规矩为，由上到下，从左到右。）性质4：具有n个结点的完全二叉树的深度为ëlog2nû+1。

性质5：若对含n个结点的完全二叉树从上到下且从左至右举行1至n的编号，那么对完全二叉树中任意一个编号为i的结点：（1）如i=1，那么序号为i的结点是根结点，无双亲结点；

如i1，那么序号为i的结点的双亲结点序号为。（2）如2×in，那么序号为i的结点无左孩子；

如2×i≤n，那么序号为i的结点的左孩子结点的序号为2×i。（3）如2×i＋1n，那么序号为i的结点无右孩子；

如2×i＋1≤n，那么序号为i的结点的右孩子结点的序号为2×i＋16.2.3二叉树的存储布局约25min1、二叉树的依次存储表示2、二叉树的链式存储表示1).二叉链表2)．三叉链表3)．双亲链表4)．线索链表三、小结约5min1、树、二叉树的定义2、二叉树的性质3、存储布局四、作业约5min1.一棵度为2的树与一棵二叉树有何识别？2.试分别画出具有3个结点的二叉树和3个结点的二叉树的全体不同形态。

课时授课计划2022-2022学年第一学期第7周授课日期10月25日三星期月日星期月日星期月日星期月日星期班级信管10-1根本课题遍历二叉树和线索二叉树教学目的与要求：

1.遍历二叉树是二叉树各种操作的根基。掌管各种遍历策略的递归算法，生动运用遍历算法实现二叉树的其它操作。

2.理解二叉树线索化的实质.纯熟掌管二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。

教学重点：

1.遍历二叉树是二叉树各种操作的根基。

2．各种遍历策略的递归算法，运用遍历算法实现二叉树的其它操作。

教学难点：

各种遍历策略的递归算法，运用遍历算法实现二叉树的其它操作。

二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。

作业及参考书：

写出所给二叉树的前、中、后序的序列《数据布局算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——开展——举例——小结——作业一、引入约3min由二叉树的布局引出对每个结点的遍历。

二、讲课进程设计6.3遍历二叉树和线索二叉树6.3.1二叉树的遍历一、问题的提出约7min顺着某一条探寻路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。（将树线性化）对“二叉树”而言，可以有三条探寻路径：

Ø1．先上后下的按层次遍历；

Ø2．先左（子树）后右（子树）的遍历；

Ø3．先右（子树）后左（子树）的遍历。

二、先左后右的遍历算法约10min先（根）序的遍历算法若二叉树为空树，那么空操作；

否那么（1）访问根结点；

（2）先序遍历左子树；

（3）先序遍历右子树。

中（根）序的遍历算法若二叉树为空树，那么空操作；

否那么（1）中序遍历左子树；

（2）访问根结点；

（3）中序遍历右子树。

后（根）序的遍历算法若二叉树为空树，那么空操作；

否那么（1）后序遍历左子树；

（2）后序遍历右子树；

（3）访问根结点。

三、算法的递归描述约10min总结：无论先序、中序、后序遍历二叉树，遍历时的探寻路线是一致的：从根结点启程，逆时针延二叉树外缘移动对每个结点均途径三次。

先序遍历：第一次经过结点时访问。

中序遍历：其次次经过结点时访问。

后序遍历：第三次经过结点时访问。

四、中序遍历算法的非递归描述约10min五、遍历算法的应用举例约30min1、统计二叉树中叶子结点的个数(先序遍历)先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中添加一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，那么计数器增1。

2、求二叉树的深度(后序遍历)算法根本思想:首先分析二叉树的深度和它的左、右子树深度之间的关系。

3、复制二叉树(后序遍历)其根本操作为：生成一个结点。

4、建立二叉树的存储布局p不同的定义方法相应有不同的存储布局的建立算法按给定的表达式建相应二叉树由先缀表示式建树由原表达式建树我们已经知道二叉树布局和它的某个遍历序列不存在一一对应的关系，但若已知一个二叉树的前序序列和中序序列，却确定可以惟一确定一个二叉树的布局。

6.3.2线索二叉树约20min•何谓线索二叉树？•遍历二叉树的结果是，求得结点的一个线性序列。

•如何保存这种在遍历过程中得到的信息？•最简朴的方法是在每个结点上增加二个指针域：fwd和bkwd用来指示此结点在遍历中的前驱和后继结点。

•线索链表的遍历算法•由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。

•如何建立线索链表？结索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。为了记录遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前访问的结点，那么pre指向它的前驱。由此在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。

三、小结约7min1、遍历的总结2、线索化的总结四、作业1、对所给出的二叉树写出前、中、后序的遍历序列。

课时授课计划2022-2022学年第一学期第7周授课日期11月1日三星期月日星期月日星期月日星期月日星期班级信管10-1根本课题树和森林教学目的与要求：

1．熟谙树的各种存储布局及其特点，掌管树、森林与二叉树的转换方法。

2．学会编写实现树的各种操作的算法。

教学重点：

1、树、森林与二叉树的转换方法2．学会编写实现树的各种操作的算法。

教学难点：

1、树、森林与二叉树的转换方法2．学会编写实现树的各种操作的算法。

作业及参考书：

树和森林的转换《数据布局算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——开展——举例——小结——作业一、引入约5m