您好,欢迎访问三七文档
当前位置:首页 > 财经/贸易 > 资产评估/会计 > 数据结构详细教案――栈和队列
第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、问题描述·只包含+,-,*,
本文标题:数据结构详细教案――栈和队列
链接地址:https://www.777doc.com/doc-4296262 .html