数据结构教案

1、2011 至2012 学年第 一 学期教案课程名称数据结构使用教材数据结构（C语言版）教学时数56课程性质必修 任课班级（人数）信管10-1（53人）信息系（部） 信管教研室任课教师林晓霞山东科技大学泰山科技学院课 时 授 课 计 划2011-2012学年第 二学期第1周授 课 日 期2月 20 日星期1月 日 星期月 日 星期月 日 星期月 日 星期班 级信管10-1基本课题 第1章 绪论 1.1-1.2教学目的与要求：1. 了解数据结构的基本概念2. 理解常用术语教学重点： 数据结构的基本概念和术语教学难点： 数据元素之间的四种结构关系作业及参考书：1、 什么是数据结构？数据结构算法实现及

2、解析/高一凡 编著教具： 多媒体 板书课堂类型： 讲授教学过程：自我介绍开课引入展开举例小结作业一、自我介绍和课程介绍 约8min 课时：64 二、引入 约2min 由问题的提出引入 三、讲课进程设计1.1 什么是数据结构1.1.1、数据结构与其它的关系 约15min数据结构 +算法 =程序程序设计: 为计算机处理问题编制一组指令集 算法: 处理问题的策略数据结构: 问题的数学模型1.1.2、当今计算机应用的特点： 约25minl)所处理的数据量大且具有一定的关系；2)对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。举例说明：1) 学生成绩表 2)井安棋对弈 3)交通管理

3、结论 计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理；我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。1.2 基本概念和术语1.1.1、数据与数据结构 约20min数据：是对客观事物的符号表示。所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据（集合）中的一个“个体”，是数据结构中讨论的基本单位。数据对象：是性质相同的数据元素的集合，是数据的一

4、个子集。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。这种集合称为结构。数据的逻辑结构可归结为以下四类: 种类特征示例集合元素间为松散的关系 线性结构元素间为严格的一对一关系如上面的成绩表中各元素树形结构元素间为严格的一对多关系图状结构（或网状结构）元素间为多对多关系数据结构的形式定义为:数据结构是一个二元组 数据的存储结构 ： 逻辑结构在存储器中的映像数据元素的映象方法：计算机中存储信息的最小单位：位，8位为一字节，两个字节为一字，字节、字或更多的二进制位可称为位串。在逻辑描述中，把位串称为元素或结点。关系的映象方法：顺序映象 链式映象1.2.2、数据类型

5、约5min数据类型 是一个 值的集合和定义在此集合上的 一组操作的总称。1.2.3、抽象数据类型 约20min是指一个数学模型以及定义在此数学模型上的一组操作。关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。抽象数据类型表示法：三元组表示：（D，S，P）其中D是数据对象，S是D上的关系集，P是对D的基本操作集。书中的定义格式：ADT 抽象数据类型名数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>ADT 抽象数据类型名ADT 有两个重要特征:数据抽象 数据封装四、本次课小结

6、： 约3min1. 熟悉各名词2. 术语的含义3. 掌握基本概念五、作业 约2min2、 什么是数据结构？课 时 授 课 计 划2011-2012学年第 二 学期第1周授 课 日 期2月 24日 星期5月 日 星期月 日 星期月 日 星期月 日 星期班 级信管10-1基本课题 抽象数据类型的表示与实现 算法和算法分析教学目的与要求：类C语言的各种句型及算法描述的规范教学重点：类C语言的各种句型及算法描述的规范教学难点：类C语言的各种句型及算法描述的规范作业及参考书：数据结构算法实现及解析/高一凡 编著教具： 多媒体 板书课堂类型： 讲授教学过程：复习引入展开举例小结作业一、复习： 约5min1

7、、数据结构的基本概念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 )初始条件：复数已存在。操作结果：用ImagPar

8、t返回复数Z的虚部值。 Add( z1,z2, &sum )初始条件：z1, z2是复数。操作结果：用sum返回两个复数z1, z2 的和值。 1.3.2对本书所采用的类C语言作简要说明 约18min1. 预定义常量及类型2、数据结构的存储结构typedef3、算法描述为以下的函数形式：4. 在算法描述中可以使用的赋值语句形式有：5. 在算法描述中可以使用的选择结构语句形式有：6. 在算法描述中可以使用的循环结构语句形式有：7. 在描述算法中可以使用的结束语句形式有：8. 在算法描述中可以使用的输入输出语句形式有： 9. 在算法描述中使用的注释格式为：10. 在算法描述中可以使用的扩展

9、函数有：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计算机执

10、行指令的速度算法 = 控制结构 + 原操作 （固有数据类型的操作）一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。 在计算时间复杂度时所采用的记号“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、循环语句

11、的运行时间为多次叠代中执行循环体以及检验循环条件的耗时，常用乘法准则若算法的两个部分的时间复杂度为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. 理解算法五个要素的

12、确切含义。2. 掌握计算语句频度和估算算法时间复杂度的方法。五、作业 约5min1、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,n),x和n，输出为Pn(x0).通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。课 时 授 课 计 划2011-2012学年第 二学期

13、第2周授 课 日 期2月 27 日 星期月 日 星期月 日 星期月 日 星期月 日 星期班 级信管10-1基本课题 线性表的类型定义 线性表的顺序表示和实现教学目的与要求：1、掌握线性表的概念和类型定义2、掌握线性表的顺序表示和实现方法教学重点：线性表的类型定义线性表的顺序表示和实现方法教学难点：线性表的类型定义线性表的顺序存储的实现方法作业及参考书：数据结构算法实现及解析/高一凡 编著教具： 多媒体 板书课堂类型： 讲授教学过程：复习引入展开举例小结一、引入 约3min由顺序的算法引入二、讲课进程设计21线性表的类型定义12.1.1线性表的定义 约27min 线性表是由n（n0）个类型相同的

14、数据元素组成的有限序列。抽象数据类型线性表的定义如下：ADT List 数据对象D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长; 称 n=0 时的线性表为空表。数据关系R1 <ai-1 ,ai >|ai-1 ,aiD, i=2,.,n 基本操作：结构初始化操作：InitList( &L )操作结果：构造一个空的线性表L。结构销毁操作：DestroyList( &L )初始条件：线性表 L 已存在。操作结果：销毁线性表 L。引用型操作ListEmpty( L )（线性表判空）ListLength( L )（求线性表的长度）Pr

15、iorElem( 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 )（插入数据元素）ListDelet

16、e(&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、线性表

17、操作 约20minListInsert(&L, i, e)的实现：首先分析插入元素时，线性表的逻辑结构发生什么变化？线性表操作 ListDelete(&L, i, &e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？线性表类型的实现2.1.2、线性表顺序存储结构的特点： 约20min 它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。 暴露的问题 (1)在做插入或删除元素的操作时，会产生大量的数据元素移动； (2)对于长度变化较大的线性表，要一次性地分

18、配足够的存储空间，但这些空间常常又得不到充分的利用； (3)线性表的容量难以扩充。三、小结 约5min1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。课 时 授 课 计 划2011-2012学年第 二 学期第2周授 课 日 期3月 3 日 星期月 日 星期月 日 星期月 日 星期月 日 星期班 级信管10-1基本课题 线性表的链式表示和实现 一元多项式的表示及相加教学目的与要求：1、

19、掌握线性链表、单链表、静态链表的概念、表示及实现方法。2、掌握循环链表的概念3、掌握双向链表的表示与实现教学重点：1、线性链表之单链表的表示及实现方法。2、双向链表的表示与实现教学难点：1、线性链表2、双向链表的存储表示作业及参考书：写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。 数据结构算法实现及解析/高一凡 编著教具： 多媒体 板书课堂类型： 讲授教学过程：复习引入展开举例小结作业一、复习 约5min复习线性表有的概念二、引入 约2min由线性表的表示不方便引入三、讲课进程设计2.3 线性表的链式表示和实现 线性表顺序存储结构的特点： 约10min 它是一种简单、方

20、便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。 暴露的问题 (1)在做插入或删除元素的操作时，会产生大量的数据元素移动； (2)对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用； (3)线性表的容量难以扩充。2.3.1、单链表 约10min用一组地址任意的存储单元存放线性表中的数据元素（这组存储单元可以是连续的也可以是不连续的）。2.3.2、结点和单链表的 C 语言描述 约10min2.3.3、单链表操作的实现 约13min因此生成链表的过程是一个结点“逐个插入

21、”的过程。操作步骤：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)抽象数据类型一元多项式的定义如下：ADT Polynomial 数据对象：D ai| aiTermSet,i=1,2,.,m, m0 TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数 数据关系：R1

22、<ai-1 ,ai >|ai-1 ,aiD, 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,

23、&Pb ) 初始条件：一元多项式 Pa 和 Pb 已存在。操作结果：完成多项式相加运算，即： Pa = PaPb，并销毁一元多项式 Pb。 SubtractPolyn ( &Pa, &Pb ) ADT Polynomial2.4.2一元多项式的实现： 约10mintypedef OrderedLinkList polynomial; / 用带表头结点的有序链表表示多项式四、小结约5min1.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。五、本章作业： 约5min写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。 本题可

24、以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。课 时 授 课 计 划2011-2012学年第 一 学期第3周授 课 日 期9月22日 五星期月 日 星期月 日 星期月 日 星期月 日 星期班 级信管10-1基本课题栈栈的应用举例教学目的与要求：1、 栈的数据类型定义2、 栈的顺序存储与实现3、 掌握栈的应用方法，理解栈的重要作用教学重点：1、栈的顺序存储表示与实现方法2、利用栈实现行编辑、利用栈实现表达式求值教学难点：1、栈的定义2、利用栈实现表达式求值作业及参考书：1、栈定义的应用2、栈的特点数据结构算

25、法实现及解析/高一凡 编著教具： 多媒体 板书课堂类型： 讲授教学过程：引入展开举例小结作业一、引入约10min 1. 什么是线性结构？  2. 以餐馆中一叠一叠的盘子的使用为例，引出栈的特点。二、讲课进程设计3.1 栈的类型定义 3.1.1、栈、栈顶(top)、栈底(bottom)的定义约10min3.1.2栈的类型定义约10min3.2 栈的应用举例例一、 数制转换 约10min十进制数N和其他d进制数的转换是计算机实现计算的基本问题，个简单算法基于下列原理： N = (N div d)×d + N mod d (其中：div为整除运算，mod为求余运算)例二、 括号匹

26、配的检验 约10min 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。三种情况对应到栈的操作即为： 1和栈顶的左括弧不相匹配； 2栈中并没有左括弧等在哪里；3栈中还有左括弧没有等到和它相匹配的右括弧。例三、 行编辑程序问题 约10min 在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。合理的作法是：设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区,并假设“#”为退格符，“”为退行符。例四、 迷宫求解 约10min假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。 “纳入路径”的操作即为“当前位置入栈； “从当前

27、路径上删除前一通道块”的操作即为"出栈"。例五、表达式求值 约10min任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。例六、 实现递归 约10min递归函数的实现 一个递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于“调用函数和被调用函数是同一个函数”。为了保证“每一层的递归调用”都是对“本层”的数据进行操作，在执行递归函数的过程中需要一个“递归工作栈”。三、小结约5min1. 掌握栈和队列类型的特点，并能在相 应的应用问题中正确选用它们。2. 熟练掌握栈类型的两种实现方法，特 别应注意栈满和栈空的条件以及

28、它们的描述方法。四、作业 约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、栈的特点是（）。课 时 授 课 计 划2011-2012学年第 一 学期第3周授 课 日 期9月27日 三星期月 日 星期月 日 星期月 日 星期月 日 星期班 级信管10-1基本课题队列教学目的与要求：1. 熟练掌握循环队列和链队列的基本操作实现算法。2. 理解递归算法执行过程中栈的状态变化过程。教学重点：1链队的表示与实现教学难点：.1。链队

29、的表示与实现作业及参考书：1栈与队列的比较2读程序段数据结构算法实现及解析/高一凡 编著教具： 多媒体 板书课堂类型： 讲授教学过程：引入展开举例小结作业一、引入约5min 在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？ 是"排队"。在计算机程序中，模拟排队的数据结构是"队列"。二、讲课进程设计3.4 队列1队列的定义约10min2队列的抽象类型定义 约15min3.队列的基本操作： 约20minInitQueue(&Q) 操作结果：构造一个空队列Q。DestroyQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列

30、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为非空队列。 操作结果

31、：删除Q的队头元素，并用e返回其值。QueueTravers(Q, visit()队列类型的实现4.链队列链式映象 约15min5.循环队列顺序映象 约20 min队列在程序设计中的一个典型应用例子是作业排队问题。三、小结约5min1. 熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。2. 理解递归算法执行过程中栈的状态变化过程。四、作业 约10min1、线性表、栈和队列都是（）结构,可以在线性表的（）位置插入和删除元素，对于栈只能在（）插入和删除元素，对于队列只能在（）插入元素和（）删除元素。2、 指出下述程序段的功能是什么? (1) void Demo1

32、(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0, i< n; i+) Push(S, arri); /Demo1课 时 授 课 计 划2011-2012学年第 一 学期第4周授 课 日 期月 日 星期月 日 星期月 日 星期月 日 星期月 日 星期班 级信管10-1基本课题 实验二栈和队列的总结复习教学目的与要求：1、 深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们；2、 巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。教学重点：巩固这两种结构的构造方法，接触较复杂

33、问题的递归算法设计。教学难点：巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。作业及参考书：数据结构算法实现及解析/高一凡 编著教具： 课堂类型： 教学过程： 停车场管理问题描述设停车场内只有一个的停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放

34、在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。测试数据设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表示输入结束。基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道

35、上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。实现提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。选作内容（1） 两个栈共享空间，思考应开辟数组的空间是多少？（2） 汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3） 汽车可以直接从便道上开走，此时派在它前面

36、的汽车要先开走让路，然后再依次排到队尾。（4） 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。课 时 授 课 计 划2011-2012学年第 一 学期第4周授 课 日 期10月8日 日星期月 日 星期月 日 星期月 日 星期月 日 星期班 级信管10-1基本课题串教学目的与要求：1、熟悉串七种基本操作的定义，并能利用这些基本操作实现传的其他各种操作的方法。2、熟悉掌握在串的定长顺序存储结构上实现串的各种操作的方法。3、掌握串的堆存储结构以及在其上实现串的各种操作的基本方法。教学重点：1、串七种基本操作的定义2、串的定长顺序存储3、串的堆存储结构教学难

37、点：1、串七种基本操作的定义2、串的堆存储结构作业及参考书：对串的操作的应用数据结构算法实现及解析/高一凡 编著教具： 多媒体 板书课堂类型： 讲授教学过程：引入展开举例小结作业一、引入约5min计算机上的非数值处理的对象基本上都是字符串数据。二、讲课进程设计4.1串的抽象数据类型的定义1.定义 约10min串、串长、空串、子串、主串、位置、相等、空格串2.串的抽象数据类型的定义约10minStrAssign (&T, chars) StrCopy (&T, S) DestroyString (&S) StrEmpty(S) StrCompare(S,T) StrLen

38、gth(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、串的定长顺序存储表示 约15min 1.串联接2.求子串4.2.2、串的堆分配存储表示约20min通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( )和free( )进行串值空间的动态管理，为每一个

39、新产生的串分配一个存储区，称串值共享的存储空间为“堆”。4.2.3、串的块链存储表示 约10min也可用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。4.4串操作应用举例4.4.1文本编辑 约20min可用于文本编辑的程序很多，功能强弱差别很大，但基本操作是一致的：都包括串的查找，插入和删除等基本操作。对用户来讲，一个文本（文件）可以包括若干页，每页包括若干行，每行包括若干文字。对文本编辑程序来讲，可把整个文本看成一个长字符串，称文本串，页是文本串的子串，行又是页的子串。为简化程序复杂程度，可简单地把文本分

40、成若干行。三、小结约5min1. 熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。2. 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。3. 了解串的堆存储结构以及在其上实现串操作的基本方法。4. 了解串操作的应用方法和特点。四、作业约5min假设有如下的串说明：char s130="Stocktom,CA", s230=“March 5 1999”, s330, *p; (1)在执行下列语句后，s3的值是什么?strcopy(s3,s1); concat(s3,","); concat(s3,s2);(2)调用函数strcompare(s1,s