数据结构详细教案――栈和队列

第0页数据结构教案第三章栈和队列数据结构教案第3章栈和队列第1页1目录3.1栈的基本概念.........................................................................................................................23.1.1栈的抽象数据类型定义..............................................................................................23.1.2顺序栈..........................................................................................................................23.1.3链栈..............................................................................................................................43.2栈的应用.................................................................................................................................43.2.1数制转换：将十进制数N转换成其他d进制数......................................................43.2.2括号匹配的检验..........................................................................................................43.2.3行输入处理程序..........................................................................................................43.2.4迷宫求解......................................................................................................................53.2.5表达式求值..................................................................................................................53.3栈与递归的实现.....................................................................................................................63.4队列的基本概念.....................................................................................................................63.4.1队列的抽象数据类型定义..........................................................................................63.4.2链队列..........................................................................................................................73.4.3循环队列......................................................................................................................83.5队列与栈的应用.....................................................................................................................83.5.1离散事件模拟..............................................................................................................8数据结构教案第3章栈和队列第2页2第3章栈和队列3.1栈的基本概念3.1.1栈的抽象数据类型定义1、栈的逻辑特征1）限定在表尾进行插入或删除操作的线性表；2）栈顶——表尾端；栈底——表头端3）后进先出的线性表2、抽象数据类型的定义ADTStack{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R={R1},R1={ai-1,ai|ai-1,ai∈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()失败，则操作失败}ADTStack思考：栈的取元素、插入、删除操作与线性表的相应操作有何区别，为什么？3.1.2顺序栈数据结构教案第3章栈和队列第3页31、增量式顺序栈的定义#defineSTACK_INIT_SIZE100/*存储空间的初始分配量*/#defineSTACKINCREMENT10/*存储空间的分配增量*/typedefstruct{ElemType*base;/*栈底指针*/ElemType*top;/*栈顶指针(栈顶元素的下一个位置)*/intstacksize;/*当前分配的存储容量*/}SqStack;1）和顺序表一样采用增量式的空间分配；2）操作和栈顶相关：插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置；删除操作（出栈）：删除栈顶元素；取元素操作：取栈顶元素的值。各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在O(1)时间内能获取操作位置，故可设置专门的栈顶指针top。3）约定：top指向栈顶元素的下一个位置（便于表示空栈）。4）栈顶的初始化：S.top=S.base(在上述3)约定下的空栈形式)，5）栈空：S.base==S.top，栈满：S.top-S.base=S.stacksize6）入栈：*S.top++=e，出栈：e=*--S.top注意：4),5),6)步受3)制约。约定不同，相应的判定和处理也不一样。如假设top就指向栈顶元素，此时4),5),6)如何？2、取栈顶元素GetTop_Sq1)算法设计参数：顺序栈S、取得的栈顶元素&e分析：由于top指向栈顶元素的下一个位置，因此实际的栈顶元素的位置应是top-1；栈非空时，此操作有效。算法1StatusGetTop_Sq(SqStackS,ElemType&e){/*判断栈是否为空*/if(S.base==S.top)returnERROR;e=*(S.top-1);returnOK;}3、入栈操作Push_Sq1)算法设计参数：顺序栈&S、插入元素e分析：插入位置为栈顶元素的下一个，无须判断位置的合法性；上溢即栈满的条件需要判断，由于是增量式分配，故栈满时需要重新申请空间;算法2StatusPush_Sq(SqStack&S,ElemTypee){/*判断栈是否为满*/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;数据结构教案第3章栈和队列第4页4S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}2)算法分析——时间T(n)=O(1)4、出栈操作Pop_Sq1)算法设计参数：顺序栈&S、删除的栈顶元素&e分析：在栈非空时，删除栈顶元素算法3StatusPop_Sq(SqStack&S,ElemType&e){/*判断栈是否为空*/if(S.base==S.top)returnERROR;e=*(--S.top);/*注意与GetTop()的区别*/returnOK;}2)算法分析——时间T(n)=O(1)3.1.3链栈与链表类似，只是链表的头指针即为栈顶指针。因其操作均在栈顶进行，故可以不引入头结点。思考：在链栈下的入栈、出栈以及取栈顶元素的操作的算法如何写？3.2栈的应用3.2.1数制转换：将十进制数N转换成其他d进制数算法思想：N=(Ndivd)×d+Nmodd1）将N%d的结果保存，2）N=N/d，3）若N==0结束，否则继续1）。保存的余数从先到后依次表示转换后的d进制数的低位到高位，而输出是由高位到低位的，因此必须定义先进后出的线性表——栈来保存；当全部的余数求出后，通过逐个出栈输出d进制数。3.2.2括号匹配的检验算法思想：从左至右扫描表达式，遇左括号入栈，遇右括号与栈顶元素比较：若左右括号匹配，则继续扫描；否则说明不匹配，结束。在上述操作中，若栈为空，或扫描结束后栈不为空，均说明不匹配。3.2.3行输入处理程序处理规则：遇‘#’退一格；遇‘@’退一行算法思想：引入栈，保存终端输入的一行字符（逐行处理）；遇‘#’退一格——出栈一次遇‘@’退一行——清栈步骤：1）初始化栈S2）读入字符ch数据结构教案第3章栈和队列第5页53）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、问题描述·只包含+,-,*,