《《数据结构（C语言版）》教案.docx》由会员分享，可在线阅读，更多相关《《数据结构（C语言版）》教案.docx（97页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构（C语言版）教案2011 至2012 学年第 一 学期 教案 课程名称数据结构运用教材数据结构（C语言版） 教学时数56课程性质必修 任课班级（人数）信管（53人） 信息系（部） 信管教研室 任课老师 山东科技高校泰山科技学院 课 时 授 课 计 划 2011-2012学年第 二学期第1周 授 课 日 期 2月 20 日 星期1 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 基本课题 第1章 绪论 1.1-1.2 教学目的与要求： 1. 了解数据结构的基本概念 2. 理解常用术语 教学重点： 数据结构的基本概念和术语 教学难点： 数据元素之间的四种结构关
2、系 作业及参考书： 1、 什么是数据结构？ 数据结构算法实现及解析/高一凡 编著 教具： 多媒体 板书 课堂类型： 讲授 教学过程：自我介绍开课引入绽开举例小结作业 一、自我介绍和课程介绍 约8min 课时：64 二、引入 约2min 由问题的提出引入 三、讲课进程设计 1.1 什么是数据结构 1.1.1、数据结构与其它的关系 约15min 数据结构 +算法 =程序 程序设计: 为计算机处理问题编制一组指令集 算法: 处理问题的策略 数据结构: 问题的数学模型 1.1.2、当今计算机应用的特点： 约25min l) 所处理的数据量大且具有肯定的关系； 2) 对其操作不再是单纯的数值计算，而更多
3、地是须要对其进行组织、管理和检索。举例说明： 1) 学生成果表 2)井安棋对弈 3)交通管理 结论 计算机的操作对象的关系更加困难，操作形式不再是单纯的数值计算，而更多地是对这些具有肯定关系的数据进行组织管理；我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必需弄清晰这些操作对象的特点，在计算机中的表示方式以及各个操作的详细实现手段。1.2 基本概念和术语 1.1.1、数据与数据结构 约20min 数据：是对客观事物的符号表示。全部能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据（集
4、合）中的一个“个体”，是数据结构中探讨的基本单位。数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。这种集合称为结构。数据的逻辑结构可归结为以下四类: 种类 特征 示例 集合 元素间为松散的关系 线性结构 元素间为严格的一对一关系 如上面的成果表中各元素 树形结构 元素间为严格的一对多关系 图状结构（或网状结构） 元素间为多对多关系 数据结构的形式定义为:数据结构是一个二元组 数据的存储结构 ： 逻辑结构在存储器中的映像 数据元素的映象方法：计算机中存储信息的最小单位：位，8位为一字节，两个字节为一字，字节、字或更多的二进制位可
5、称为位串。在逻辑描述中，把位串称为元素或结点。关系的映象方法：依次映象 链式映象 1.2.2、数据类型 约5min 数据类型 是一个 值的集合和定义在此集合上的 一组操作的总称。1.2.3、抽象数据类型 约20min 是指一个数学模型以及定义在此数学模型上的一组操作。关键：运用它的人可以只关切它的逻辑特征，不须要了解它的存储方式。定义它的人同样不必要关切它如何存储。抽象数据类型表示法： 三元组表示：（D，S，P） 其中D是数据对象，S是D上的关系集，P是对D的基本操作集。书中的定义格式： ADT 抽象数据类型名 数据对象：<数据对象的定义> 数据关系：<数据关系的定义>
6、 基本操作：<基本操作的定义> ADT 抽象数据类型名 ADT 有两个重要特征: 数据抽象 数据封装 四、本次课小结： 约3min 1. 熟识各名词 2. 术语的含义 3. 驾驭基本概念 五、作业 约2min 2、 什么是数据结构？ 课 时 授 课 计 划 2011-2012学年第 二 学期第1周 授 课 日 期 2月 24日 星期5 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 基本课题 抽象数据类型的表示与实现 算法和算法分析 教学目的与要求： 类C语言的各种句型及算法描述的规范 教学重点： 类C语言的各种句型及算法描述的规范 教学难点： 类C语
7、言的各种句型及算法描述的规范 作业及参考书： 数据结构算法实现及解析/高一凡 编著 教具： 多媒体 板书 课堂类型： 讲授 教学过程：复习引入绽开举例小结作业 一、复习： 约5min 1、数据结构的基本概念 2、一些基本术语 二、引入 约2min 由程序设计过程遇到的问题引入 三、讲课进程设计 1.3抽象数据类型的表示与实现 1.3.1基本操作： 约15min AssignComplex( Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。DestroyComplex( Z) 操作结果：复数Z被销毁。 GetReal( Z, realPart
8、) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。GetImag( Z, ImagPart ) 初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1, z2 的和值。 1.3.2对本书所采纳的类C语言作简要说明 约18min 1. 预定义常量及类型 2、数据结构的存储结构typedef 3、算法描述为以下的函数形式： 4. 在算法描述中可以运用的赋值语句形式有： 5. 在算法描述中可以运用的选择结构语句形式有： 6. 在算法描述中可以运用的循环结构
9、语句形式有： 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 通常有两种衡
10、量算法效率的方法 事后统计法 缺点：1必需执行程序 2其它因素掩盖算法本质 事前分析估算法 和算法执行时间相关的因素：1算法选用的策略2问题的规模3编写程序的语言4编译程序产生的机器代码的质量5计算机执行指令的速度 算法 = 限制结构 + 原操作 （固有数据类型的操作） 一个算法的执行时间大致上等于其全部语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。 在计算时间困难度时所采纳的记号“O”是数学符号，其严格的数学定义是：若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n)表示存在正的常数c和n0，使得当n>=n0时都满意0=&
11、lt;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
12、) = O(g(n) 表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同。 算法的存储量包括: 1输入数据所占空间2程序本身所占空间3协助变量所占空间 四、小结： 约5min 1. 理解算法五个要素的准确含义。2. 驾驭计算语句频度和估算算法时间困难度的方法。五、作业 约5min 1、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间困难度，要求时间困难度尽可能的小，规定算法中不能运用求幂函数。留意：本题中的输入ai(i=0,1,n),x和n，输出为Pn(x0).通常算法
13、的输入和输出可采纳下列两种方式之一： （1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。 试探讨这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 课 时 授 课 计 划 2011-2012学年第 二学期第2周 授 课 日 期 2月 27 日 星期 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 基本课题 线性表的类型定义 线性表的依次表示和实现 教学目的与要求： 1、驾驭线性表的概念和类型定义 2、驾驭线性表的依次表示和实现方法 教学重点： 线性表的类型定义 线性表的依次表示和实现方法 教学难点： 线性表的类型定义 线性表的依次
14、存储的实现方法 作业及参考书： 数据结构算法实现及解析/高一凡 编著 教具： 多媒体 板书 课堂类型： 讲授 教学过程：复习引入绽开举例小结 一、引入 约3min 由依次的算法引入 二、讲课进程设计 21线性表的类型定义 12.1.1线性表的定义 约27min 线性表是由n（n0）个类型相同的数据元素组成的有限序列。 抽象数据类型线性表的定义如下： ADT List 数据对象 D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长; 称 n=0 时的线性表为空表。 数据关系 R1 <ai-1 ,ai >|ai-1 ,aiD, i=2,.,n 基本操
15、作： 结构初始化操作： 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( ) )（定位函数） ListT
16、raverse(L, visit( )（遍历线性表） 加工型操作 ClearList( L )（线性表置空） PutElem( L, i, e )（变更数据元素的值） ListInsert( L, i, e )（插入数据元素） ListDelete(L, i, e) （删除数据元素） 2.1.2举例 约10min 两个线性表合并LA和LB 2.2 线性表的依次表示和实现 2.2.1依次映象 约15min 以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系<x,y>。最简洁的一种依次映象方法是： 令y的存储位置和x的存储位置相邻。线性表的基本操作在依次表中的实现 InitL
17、ist(L) / 结构初始化 LocateElem(L, e, compare() / 查找 ListInsert(L, i, e) / 插入元素 ListDelete(L, i) / 删除元素 2.1.1、线性表操作 约20min ListInsert(L, i, e)的实现： 首先分析 插入元素时，线性表的逻辑结构发生什么改变？ 线性表操作 ListDelete(L, i, e)的实现： 首先分析： 删除元素时，线性表的逻辑结构发生什么改变？线性表类型的实现 2.1.2、线性表依次存储结构的特点： 约20min 它是一种简洁、便利的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中
18、，从而利用数据元素的存储依次表示相应的逻辑依次，这种存储方式属于静态存储形式。暴露的问题 (1)在做插入或删除元素的操作时，会产生大量的数据元素移动； (2)对于长度改变较大的线性表，要一次性地安排足够的存储空间，但这些空间经常又得不到充分的利用； (3)线性表的容量难以扩充。三、小结 约5min 1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是依次存储结构和链式存储结构。用前者表示的线性表简称为依次表，用后者表示的线性表简称为链表。2.娴熟驾驭这两类存储结构的描述方法，以及线性表的各种基本操作的实现。 课 时 授 课 计 划 2011-2
19、012学年第 二 学期第2周 授 课 日 期 3月 3 日 星期 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 基本课题 线性表的链式表示和实现 一元多项式的表示及相加 教学目的与要求： 1、驾驭线性链表、单链表、静态链表的概念、表示及实现方法。 2、驾驭循环链表的概念 3、驾驭双向链表的表示与实现 教学重点： 1、线性链表之单链表的表示及实现方法。2、双向链表的表示与实现 教学难点： 1、线性链表 2、双向链表的存储表示 作业及参考书： 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。 数据结构算法实现及解析/高一凡 编著 教具： 多媒体
20、 板书 课堂类型： 讲授 教学过程：复习引入绽开举例小结作业 一、复习 约5min 复习线性表有的概念 二、引入 约2min 由线性表的表示不便利引入 三、讲课进程设计 2.3 线性表的链式表示和实现 线性表依次存储结构的特点： 约10min 它是一种简洁、便利的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储依次表示相应的逻辑依次，这种存储方式属于静态存储形式。 暴露的问题 (1)在做插入或删除元素的操作时，会产生大量的数据元素移动； (2)对于长度改变较大的线性表，要一次性地安排足够的存储空间，但这些空间经常又得不到充分的利用； (3)线性表的容量难以扩充
21、。 2.3.1、单链表 约10min 用一组地址随意的存储单元存放线性表中的数据元素（这组存储单元可以是连续的也可以是不连续的）。2.3.2、结点和单链表的 C 语言描述 约10min 2.3.3、单链表操作的实现 约13min 因此生成链表的过程是一个结点“逐个插入”的过程。操作步骤： 1、建立一个“空表”； 2、输入数据元素an，建立结点并插入； 3、输入数据元素an-1，建立结点并插入； 4、依次类推，直至输入a1为止。2.3.4、其它形式的链表 约5min 1. 循环链表2. 双向链表 2.3.5、有序表类型 约5min 2.4一元多项式的表示 2.4.1一元多项式 约20min 在计
22、算机中，可以用一个线性表来表示: P = (p0, p1, ，pn) 抽象数据类型一元多项式的定义如下： ADT Polynomial 数据对象：D ai| aiTermSet,i=1,2,.,m, m0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 数据关系：R1 <ai-1 ,ai >|ai-1 ,aiD, i=2,.,n 且ai-1中的指数值ai中的指数值 基本操作： CreatPolyn ( P, m ) 操作结果：输入 m 项的系数和指数， 建立一元多项式 P。DestroyPolyn ( P ) 初始条件：一元多项式 P 已存在。操作结果：销毁一
23、元多项式 P。PrintPolyn ( P ) 初始条件：一元多项式 P 已存在。操作结果：打印输出一元多项式 P。PolynLength( P ) 初始条件：一元多项式 P 已存在。操作结果：返回一元多项式 P 中的项数。AddPolyn ( Pa, Pb ) 初始条件：一元多项式 Pa 和 Pb 已存在。操作结果：完成多项式相加运算，即： Pa = PaPb，并销毁一元多项式 Pb。 SubtractPolyn ( Pa, Pb ) ADT Polynomial 2.4.2一元多项式的实现： 约10min typedef OrderedLinkList polynomial; / 用带表头
24、结点的有序链表表示多项式 四、小结约5min 1.能够从时间和空间困难度的角度综合比较线 性表两种存储结构的不同特点及其适用场合。 五、本章作业： 约5min 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。 本题可以这样考虑，先取起先结点中的值，将它与其后的全部结点值一一比较，发觉相同的就删除掉，然后再取其次结点的值，重复上述过程直到最终一个结点。 课 时 授 课 计 划 2011-2012学年第 一 学期第3周 授 课 日 期 9月22日 五 星期 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 基本课题栈栈的应用举例 教学目的与要求：
25、1、 栈的数据类型定义 2、 栈的依次存储与实现 3、 驾驭栈的应用方法，理解栈的重要作用 教学重点： 1、栈的依次存储表示与实现方法 2、利用栈实现行编辑、利用栈实现表达式求值 教学难点： 1、栈的定义 2、利用栈实现表达式求值 作业及参考书： 1、栈定义的应用 2、栈的特点 数据结构算法实现及解析/高一凡 编著 教具： 多媒体 板书 课堂类型： 讲授 教学过程：引入绽开举例小结作业 一、引入约10min 1. 什么是线性结构？ 2. 以餐馆中一叠一叠的盘子的运用为例，引出栈的特点。 二、讲课进程设计 3.1 栈的类型定义 3.1.1、栈、栈顶(top)、栈底(bottom)的定义约10mi
26、n 3.1.2栈的类型定义约10min 3.2 栈的应用举例 例一、 数制转换 约10min 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，个简洁算法基于下列原理： N = (N div d)d + N mod d (其中：div为整除运算，mod为求余运算) 例二、 括号匹配的检验 约10min 检验括号是否匹配的方法可用“期盼的急迫程度”这个概念来描述。三种状况对应到栈的操作即为： 1和栈顶的左括弧不相匹配； 2栈中并没有左括弧等在哪里；3栈中还有左括弧没有等到和它相匹配的右括弧。例三、 行编辑程序问题 约10min 在用户输入一行的过程中，允许用户输入出差错，并在发觉有误时可
27、以刚好更正。合理的作法是：设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区,并假设“#”为退格符，“”为退行符。例四、 迷宫求解 约10min 假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最终一个通道块”。“纳入路径”的操作即为“当前位置入栈； “从当前路径上删除前一通道块”的操作即为“出栈“。例五、表达式求值 约10min 任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。例六、 实现递归 约10min 递归函数的实现 一个递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于“调用函数和被调用函数是
28、同一个函数”。为了保证“每一层的递归调用”都是对“本层”的数据进行操作，在执行递归函数的过程中须要一个“递归工作栈”。 三、小结约5min 1. 驾驭栈和队列类型的特点，并能在相 应的应用问题中正确选用它们。 2. 娴熟驾驭栈类型的两种实现方法，特 别应留意栈满和栈空的条件以及它们的描述方法。四、作业 约5min 1、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，a1 2、栈的特点是（）。 课 时 授 课 计 划 2011-2012学年第
29、 一 学期第3周 授 课 日 期 9月27日 三 星期 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 基本课题队列 教学目的与要求： 1. 娴熟驾驭循环队列和链队列的基本操作实现算法。 2. 理解递归算法执行过程中栈的状态改变过程。 教学重点： 1链队的表示与实现 教学难点：.1。链队的表示与实现 作业及参考书： 1栈与队列的比较 2读程序段 数据结构算法实现及解析/高一凡 编著 教具： 多媒体 板书 课堂类型： 讲授 教学过程：引入绽开举例小结作业 一、引入约5min 在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？ 是“排队“。在计算机程序中，模
30、拟排队的数据结构是“队列“。 二、讲课进程设计 3.4 队列 1队列的定义约10min 2队列的抽象类型定义 约15min 3.队列的基本操作： 约20min InitQueue(Q) 操作结果：构造一个空队列Q。DestroyQueue(Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁，不再存在。 QueueEmpty(Q) 初始条件:队列Q已存在。操作结果:若Q为空队列,则返回TRUE，否则返回FALSE。QueueLength(Q) 初始条件:队列Q已存在。操作结果:返回Q的元素个数，即队列 的长度。GetHead(Q, e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元
31、素。 ClearQueue(Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。 EnQueue(Q, e) 初始条件:队列Q已存在。操作结果:插入元素e为Q的新的队尾元素。DeQueue(Q, e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。 QueueTravers(Q, visit() 队列类型的实现 4.链队列链式映象 约15min 5.循环队列依次映象 约20 min 队列在程序设计中的一个典型应用例子是作业排队问题。三、小结约5min 1. 娴熟驾驭循环队列和链队列的基本操作实现算法，特殊留意队满和队空的描述方法。2. 理解递归算法执行过程中栈的状
32、态改变过程。四、作业 约10min 1、线性表、栈和队列都是（）结构,可以在线性表的（）位置插入和删除元素，对于栈只能在（）插入和删除元素，对于队列只能在（）插入元素和（）删除元素。2、 指出下述程序段的功能是什么? (1) void Demo1(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周 授 课 日 期 月 日 星期 月 日 星期 月 日 星期
33、 月 日 星期 月 日 星期 班 级 信管10-1 基本课题 试验二栈和队列的总结复习 教学目的与要求： 1、 深化了解栈和队列的特征，以便在实际问题背景下敏捷运用它们； 2、 巩固这两种结构的构造方法，接触较困难问题的递归算法设计。 教学重点： 巩固这两种结构的构造方法，接触较困难问题的递归算法设计。 教学难点： 巩固这两种结构的构造方法，接触较困难问题的递归算法设计。 作业及参考书： 数据结构算法实现及解析/高一凡 编著 教具： 课堂类型： 教学过程： 停车场管理 问题描述 设停车场内只有一个的停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后依次，依次
34、由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满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）。其中
35、，A表示到达；D表示离去，E表示输入结束。基本要求 以栈模拟停车场，以队列模拟车场外的便道，根据从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以依次结构实现，队列以链表实现。实现提示 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用依次存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两
36、个数据项：汽车的牌照号码和进入停车场的时刻。选作内容 （1） 两个栈共享空间，思索应开拓数组的空间是多少？ （2） 汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3） 汽车可以干脆从便道上开走，此时派在它前面的汽车要先开走让路，然后再依次排到队尾。（4） 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思索如何修改结构以满意这种要求。 课 时 授 课 计 划 2011-2012学年第 一 学期第4周 授 课 日 期 10月8日 日 星期 月 日 星期 月 日 星期 月 日 星期 月 日 星期