下载文档原格式
xxxx学院教案首页xxxx学院教案附页第一学时（栈的定义、常用操作与顺序存储的实现）一、情景导入（1）引出栈的概念由线性表引出栈：栈是线性表的一种，只是在操作上，与线性表有所差别。
如果没有道具，借用课本，粉笔盒或学生自主进行展示。
（2）进入主题，讲解栈的特点与线性表进行类比，栈与基础线性表的差别，在于它的操作受限、取数的方式不如线性表自由。
可以结合图3-1中的图示，引导学生回想存取碗时的具体操作，帮助学生领悟栈的特点。
图3-1 一摞碗二、知识讲解（1）栈的特点结合图3-2中栈的结构图，对栈的操作原则——后进先出，进行讲解。
图3-2 栈的结构图（2）栈的常用操作栈的常用操作如下：•创建栈（初始化栈）•判断栈是否为空•进栈•出栈•获取栈顶元素•获取栈的长度•销毁栈在对栈的原则进行讲解之后，对栈中常用操作进行总结。
（3）栈的顺序存储实现栈是线性表的一种，顺序存储的栈是一种顺序表。
在知识点（2）提到的操作中，进栈和出栈是可以展示出栈特点的特色操作，可以结合图示，对这两种操作的实现进行详细说明；此外，简单叙述栈中其余功能的实现方法。
在讲解完顺序栈中的各种操作之后，结合书中例3-1给出的代码，带领学生掌握栈的实现方法。
第二学时（栈的链式存储实现）一、知识回顾（1）对上节课留的作业进行答疑。
（2）回顾总结上节课的内容，引出本节课主题。
上个学时讲解了栈的定义、栈的特点与栈的顺序实现，本学时来探讨栈的链式存储实现。
二、知识讲解（1）链栈的数据结构定义链栈是一种链表，与顺序栈相同，链栈在操作时也受到限制，遵循“后进先出”的原则。
结合链表的数据结构定义，引导学生完成链栈的数据结构定义。
（2）链栈的实现链栈的存储方式与链表相同，操作原则与顺序栈相同。
从这两点出发进行分析，引导学生找到链栈实现的思路，然后给学生留出一定时间，由学生自主分析巩固链栈操作的实现方法，之后结合学生自主实现链栈时遇到的问题，对链栈进行讲解。
（用栈实现四则运算）三、情境引入通过计算机的算术运算功能，引出本学时的主题：计算机的基本功能大多都是基于对数据的操作，给出一个运算式，计算机能迅速计算出结果，若运算时有误，如运算式“1+3*（2+5”，右边少了一个“）”，编绎器会立刻检查出错误并报告，那么计算机是如何做到的呢？藉由以上问题，引出逆波兰表达式。
数据结构教案第三章栈和队列目录3.1栈的基本概念 (2)3.1.1 栈的抽象数据类型定义 (2)3.1.2 顺序栈 (2)3.1.3 链栈 (4)3.2栈的应用 (4)3.2.1 数制转换：将十进制数N转换成其他d进制数 (4)3.2.2 括号匹配的检验 (4)3.2.3 行输入处理程序 (4)3.2.4 迷宫求解 (5)3.2.5 表达式求值 (5)3.3栈与递归的实现 (6)3.4队列的基本概念 (6)3.4.1 队列的抽象数据类型定义 (6)3.4.2 链队列 (7)3.4.3 循环队列 (8)3.5队列与栈的应用 (8)3.5.1 离散事件模拟 (8)第3章栈和队列3.1 栈的基本概念3.1.1 栈的抽象数据类型定义1、栈的逻辑特征1）限定在表尾进行插入或删除操作的线性表；2）栈顶——表尾端；栈底——表头端3）后进先出的线性表2、抽象数据类型的定义ADT Stack{数据对象：D={a i |a i∈ElemSet, i=1,2,…,n, n≥0}数据关系：R={R1},R1={<a i-1,a i>|a i-1,a i∈D, i=2,3,…,n }基本操作：InitStack( &S )操作结果：构造一个空的栈SDestroyStack( &S )初始条件：栈S已存在操作结果：销毁栈SClearStack( &S )初始条件：栈S已存在操作结果：将栈S重置为空栈StackEmpty( S )初始条件：栈S已存在操作结果：若S为空栈，则返回TRUE，否则返回FALSEStackLength( S )初始条件：栈S已存在操作结果：返回栈S中数据元素的个数GetTop( S, &e )初始条件：栈S已存在且非空操作结果：用e返回S中栈顶元素Push( &S, e )初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop( &S, &e )初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值StackTraverse( S, visit( ) )初始条件：栈S已存在且非空操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit( )。
栈和队列教案(总13页) --本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--教案课程名称：数据结构（C语言版）授课班级：技校二年级学生授课学时：1学时授课章节：第三章栈和队列课型：理论课任课教师：***图2 栈的示意图从图2中可以看出第一个进栈的a1为栈底元素，最后一个进栈的an为栈顶元素，进栈和出栈也是同一个方向。
这也是最基本的栈的示意图。
需要同学们熟知。
其实，要解决这个出站问题就离不开我们今天将要学习的进栈、出栈技术，这节课我们将从如下三个方面来掌握它：栈的定义、栈的表示和实现、栈的应用与练习。
其中栈的表示与实现是本节的重点。
一、抽象数据类型栈的定义（6分钟）点。
二、介绍栈的定义类型（8分钟）ADT Stack{数据对象：D＝{ a i | a i ∈ElemSet, i=1,2,...,n, n≥0 }数据关系：R1＝{ <a i-1, a i >| a i-1, a i∈D, i=2,...,n }约定a n端为栈顶，a1 端为栈底。
基本操作：InitStack(&S)操作结果：构造一个空栈 S。
DestroyStack(&S)初始条件：栈 S 已存在。
操作结果：栈 S 被销毁。
StackEmpty(S)初始条件：栈 S 已存在。
操作结果：若栈 S 为空栈，则返回TRUE，否则 FALE。
GetTop(S, &e)初始条件：栈 S 已存在且非空。
操作结果：用 e 返回 S 的栈顶元素。
StackLength(S)初始条件：栈 S 已存在。
分钟）操作结果：返回 S 的元素个数，即栈的长度。
ClearStack(&S)初始条件：栈 S 已存在。
操作结果：将 S 清为空栈。
Push(&S, e)初始条件：栈 S 已存在。
操作结果：插入元素 e 为新的栈顶元素。
Pop(&S, &e)初始条件：栈 S 已存在且非空。
第3章栈和队列本章教学提要教学重点：栈的定义及其基本运算栈的顺序存储结构队列的定义及基本运算队列的顺序存储结构教学难点：栈的链式存储结构队列的链式存储结构——链队列本章教学内容本章将介绍两种特殊的线性表——栈和队列。
从逻辑结构上看，栈和队列仍是线性表，其特殊性主要是其基本运算有着严格的规定。
由于栈和队列在程序设计中应用广泛，因此对它们单独进行讨论。
3．1 栈栈是规定仅在表尾进行插入和删除运算的线性表，采用的是后进先出的访问方法。
表头叫做栈底，表尾叫做栈顶。
栈的基本运算：1．inistack(s)：初始化操作，设定一个空栈s。
2．push(s,x)：在栈s的顶部插入元素x，简称为入栈。
3．pop(s,*x)：删除并返回栈s的栈顶数据元素，简称为出栈，其中x是返回的栈顶数据元素。
相当于线性表中删除一个数据元素，该运算与push (s,x)为互逆运算。
4．top(s,*x)：取出栈s的栈顶元素x，但不删除栈顶元素。
5．setnull(s)：置s为一个空栈。
6．empty(s)：判定s是否为空栈，若是则返回值为真，否则返回值为假。
3．2 队列队列是一种访问次序是先进先出的线性表队列的基本运算如下：1．addqueue(q,x)：在队列q的队尾插入元素x，称为入队列。
2．delqueue(q,*x)：删除并返回队列q的队头元素，x为返回的队头元素，称为出队列。
3．frontque(q,*x)：取得队列q的队头元素，x为返回的队头元素。
4．setnull(q)：置q为一个空队列。
5．empty(q)：判断q是否为空队列，当q为空时，返回“true”，否则“false”。
队列也是一种操作受限的线性表，它具有线性表的两种存储结构——顺序存储结构和链式存储结构。
数据结构教案第三章栈和队列目录3.1栈的基本概念 (2)3.1.1 栈的抽象数据类型定义 (2)3.1.2 顺序栈 (2)3.1.3 链栈 (4)3.2栈的应用 (4)3.2.1 数制转换：将十进制数N转换成其他d进制数 (4)3.2.2 括号匹配的检验 (4)3.2.3 行输入处理程序 (4)3.2.4 迷宫求解 (5)3.2.5 表达式求值 (5)3.3栈与递归的实现 (6)3.4队列的基本概念 (6)3.4.1 队列的抽象数据类型定义 (6)3.4.2 链队列 (7)3.4.3 循环队列 (8)3.5队列与栈的应用 (8)3.5.1 离散事件模拟 (8)第3章栈和队列3.1 栈的基本概念3.1.1 栈的抽象数据类型定义1、栈的逻辑特征1）限定在表尾进行插入或删除操作的线性表；2）栈顶——表尾端；栈底——表头端3）后进先出的线性表2、抽象数据类型的定义ADT Stack{数据对象：D={a i |a i∈ElemSet, i=1,2,…,n, n≥0}数据关系：R={R1},R1={<a i-1,a i>|a i-1,a i∈D, i=2,3,…,n }基本操作：InitStack( &S )操作结果：构造一个空的栈SDestroyStack( &S )初始条件：栈S已存在操作结果：销毁栈SClearStack( &S )初始条件：栈S已存在操作结果：将栈S重置为空栈StackEmpty( S )初始条件：栈S已存在操作结果：若S为空栈，则返回TRUE，否则返回FALSEStackLength( S )初始条件：栈S已存在操作结果：返回栈S中数据元素的个数GetTop( S, &e )初始条件：栈S已存在且非空操作结果：用e返回S中栈顶元素Push( &S, e )初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop( &S, &e )初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值StackTraverse( S, visit( ) )初始条件：栈S已存在且非空操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit( )。
一旦visit( )失败，则操作失败}ADT Stack思考：栈的取元素、插入、删除操作与线性表的相应操作有何区别，为什么？3.1.2 顺序栈1、增量式顺序栈的定义#define STACK_INIT_SIZE 100 /* 存储空间的初始分配量 */#define STACKINCREMENT 10 /* 存储空间的分配增量*/typedef struct{ElemType *base; /* 栈底指针*/ElemType *top; /* 栈顶指针(栈顶元素的下一个位置) */int stacksize; /* 当前分配的存储容量*/ }SqStack;1）和顺序表一样采用增量式的空间分配；2）操作和栈顶相关：插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置；删除操作（出栈）：删除栈顶元素；取元素操作：取栈顶元素的值。
各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在O(1)时间内能获取操作位置，故可设置专门的栈顶指针top。
3）约定：top指向栈顶元素的下一个位置（便于表示空栈）。
4）栈顶的初始化：S.top = S.base(在上述3)约定下的空栈形式)，5）栈空：S.base == S.top，栈满：S.top - S.base >= S.stacksiz e6）入栈：*S.top ++ = e，出栈：e = *--S.top注意：4), 5), 6)步受3)制约。
约定不同，相应的判定和处理也不一样。
如假设top就指向栈顶元素，此时4),5),6)如何？2、取栈顶元素GetTop_Sq1)算法设计参数：顺序栈S、取得的栈顶元素&e分析：由于top指向栈顶元素的下一个位置，因此实际的栈顶元素的位置应是top -1；栈非空时，此操作有效。
算法1Status GetTop_Sq(SqStack S, ElemType &e){/* 判断栈是否为空*/if ( S.base == S.top) return ERROR;e = *( S.top -1);return OK;}3、入栈操作Push_Sq1)算法设计参数：顺序栈&S、插入元素e分析：插入位置为栈顶元素的下一个，无须判断位置的合法性；上溢即栈满的条件需要判断，由于是增量式分配，故栈满时需要重新申请空间;算法2Status Push_Sq( SqStack &S, ElemType e ){/* 判断栈是否为满*/if ( S.top – S.base >= S.stacksize ){/* 栈满，追加空间*/S.base = ( ElemType * ) realloc( S.base,( S.stacksize + STACKINCREMENT ) * sizeof(ElemType) );if ( S.base == NULL ) exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;}2)算法分析——时间T(n) = O(1)4、出栈操作Pop_Sq1)算法设计参数：顺序栈&S、删除的栈顶元素&e分析：在栈非空时，删除栈顶元素算法3Status Pop_Sq( SqStack &S, ElemType &e){/* 判断栈是否为空*/if (S.base == S.top) return ERROR;e = *( --S.top); /* 注意与GetTop( )的区别*/return OK;}2)算法分析——时间T(n) = O(1)3.1.3 链栈与链表类似，只是链表的头指针即为栈顶指针。
因其操作均在栈顶进行，故可以不引入头结点。
思考：在链栈下的入栈、出栈以及取栈顶元素的操作的算法如何写？3.2 栈的应用3.2.1 数制转换：将十进制数N转换成其他d进制数算法思想：N = ( N div d )×d + N mod d1）将N%d的结果保存，2）N=N/d，3）若N==0结束，否则继续1）。
保存的余数从先到后依次表示转换后的d 进制数的低位到高位，而输出是由高位到低位的，因此必须定义先进后出的线性表——栈来保存；当全部的余数求出后，通过逐个出栈输出d进制数。
3.2.2 括号匹配的检验算法思想：从左至右扫描表达式，遇左括号入栈，遇右括号与栈顶元素比较：若左右括号匹配，则继续扫描；否则说明不匹配，结束。
在上述操作中，若栈为空，或扫描结束后栈不为空，均说明不匹配。
3.2.3 行输入处理程序处理规则：遇‘#’退一格；遇‘@’退一行算法思想：引入栈，保存终端输入的一行字符（逐行处理）；遇‘#’退一格——出栈一次遇‘@’退一行——清栈步骤：1）初始化栈S2）读入字符ch3）ch!=EOF3.1) ch!=EOF && ch!=’\n’3.1.1）ch为‘#’：Pop(S, c), 转3.1.4)3.1.2）ch为‘@’：ClearStack (S) , 转3.1.4)3.1.3）ch为其他：Push (S, ch) , 转3.1.4)3.1.4）再读入字符ch，继续3.1)3.2) 处理完一行，清空栈3.3) 如ch!=EOF，读入字符ch，继续3)3.2.4 迷宫求解问题：找从“入口”到“出口”的路径（所经过的通道方块）分析：1）方块的表示——坐标，当前的状态（障碍、未走的通路、已走的通路）；2）已走的路径：A.路径中各方块的位置及在路径中的序号;B.从各方块出发已探索的方向，注意不能重复（可约定按东、南、西、北的方向顺次探索）；C.从当前方块无路可走时，将已走路径回退一个方块，继续探索其他未走的方向栈——存储已走的通道块3.2.5 表达式求值1、问题描述·只包含+, -, *, / 四个双目运算符，且算符本身不具有二义性；·三个运算规则→运算符优先关系（考虑算符本身的优先级和结合性）；·只有'('==')'，'#'=='#'；·假设输入的是一个合法的表达式。
2、算法思想引入OPTR和OPND两个栈初始：OPTR有一个元素'#'，OPND为空读入一字符cc=='#'：return(GetTop(OPND))c非运算符：Push(OPND,c)c运算符：t=GetTop(OPTR)，比较t和c的优先关系t<c：Push(OPTR,c)t==c：Pop(OPTR, x)t>c：Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a);x=Operate(a, theta, b); Push(OPND, x);继续读入字符处理。
3.3 栈与递归的实现1、递归定义直接或间接地调用自身的函数，称为递归函数。
如右图所示，递归表现为：在该函数的所有可能执行路径中，存在一条由于调用自身或其它函数所导致的环路路径；为确保函数最终在有限的时间内执行完毕，必须在环路中存在一个出口，即当某种条件成立时，不必执行环路，而直接执行一条通向结束的非环路线。
2、递归应用1) 递归应用类型·递归定义的数学问题·具有递归特性的数据结构，其操作可以递归地表示·其它一些问题2) 递归应用的特点对于一个问题，当问题规模很大时，往往难于直接求解，此时：·将大问题分解成若干小问题·考虑如何利用这些小问题的解构成大问题的解·避免陷入考虑如何求解小问题这种分解、合成的方法就是递归求解中的递归方法；另外，递归应用要注意避免陷入死循环，递归必须有出口，即要确立递归的结束条件，给出此时的直接求解方法。
3) 递归应用举例Hanoi 塔问题3、递归的实现1) 系统的处理(1) 调用前现场保护，被调用函数的局部变量的空间分配，控制转移至被调用的函数入口。
(2) 调用后保存计算结果，释放被调函数的数据区，控制转移回调用处。
2) 实现——栈“后调用先返回”。
系统利用递归工作栈记录各层调用的现场信息。
3.4 队列的基本概念3.4.1 队列的抽象数据类型定义1、队列的逻辑特征1) 先进先出的线性表2) 队头：允许删除的一端；队尾：允许插入的一端3) 应用举例：操作系统的作业排队2、队列的抽象数据类型定义 ADT QueueADT Queue {数据对象：D={a i |a i ∈ElemSet, i=1,2,…,n, n ≥0}开始 结束形成了环数据关系：R={R1},R1={<a i-1,a i>|a i-1,a i∈D, i=2,3,…,n }基本操作：InitQueue(&Q)操作结果：构造一个空队列QDestroyQueue(&Q)初始条件：队列Q已存在操作结果：销毁队列QClearQueue(&Q)初始条件：队列Q已存在操作结果：将队列Q重置为空队列QueueEmpty(Q)初始条件：队列Q已存在操作结果：若Q为空队列，则返回TRUE，否则返回FALSEQueueLength(Q)初始条件：队列Q已存在操作结果：返回队列Q中数据元素的个数GetHead(Q,&e)初始条件：队列Q已存在且非空操作结果：用e返回Q中队头元素EnQueue(&Q, e)初始条件：队列Q已存在操作结果：插入元素e为Q的新的队尾元素DeQueue(&Q, &e)初始条件：队列Q已存在且非空操作结果：删除Q的队头元素，并用e返回其值QueueTraverse(Q, visit())初始条件：队列Q已存在且非空操作结果：从队头到队尾依次对Q的每个数据元素调用函数visit()。
