下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 数据结构 第3章 栈和队列

数据结构 第3章 栈和队列.ppt

数据结构 第3章 栈和队列

逃课是个艺术
2012-05-03 0人阅读 举报 0 0 暂无简介

简介:本文档为《数据结构 第3章 栈和队列ppt》,可适用于高等教育领域

第三章栈和队列第三章栈和队列第三章栈和队列第三章栈和队列栈抽象数据类型栈的定义栈的表示和实现栈的应用举例** 栈与递归的实现 队列** 离散事件模拟栈和队列是重要的线性结构实质上是操作受限的线性表。 栈的定义  栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端(表尾)进行。  进行插入和删除的一端是浮动端通常被称为栈顶(TOP)并用一个“栈顶指针”指示而另一端是固定端通常被称为栈底(bottom)。  当表中没有元素时称为空栈。我们经常将栈用下图的形式描述我们经常将栈用下图的形式描述S=(aaa…an)则a称为栈底元素 an为栈顶元素。栈的修改是按后进先出的原则进行的。因此栈称为后进先出表(LIFO)。后进先出(LastInFirstOut)简称为LIFO线性表。后进先出(LastInFirstOut)简称为LIFO线性表。举例:家里吃饭的碗。举例:在建筑工地上使用的砖块ADTStack{数据对象:D={ai|ai∈ElemSet,i=,,,n,n≥}数据关系:R={<ai,ai>|ai,ai∈D,i=,,n}约定an端为栈顶a端为栈底。基本操作:}ADTStack下面我们先给出栈结构的基本操作:()初始化栈InitStack(S)()入栈Push(&S,e)()出栈Pop(S,e)()获取栈顶元素内容GetTop(S,&e)()判断栈是否为空StackEmpty(S) ()清空栈 ClearStack(S)()返回栈的长度 StackLength(S)栈的表示和实现-顺序栈栈的表示和实现-顺序栈   由于栈是运算受限的线性表因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈是用一组连续的存储单元依次存放栈中的每个数据元素。  用起始端作为栈底用指针base标记它是固定的。  栈顶位置是随着进栈和退栈操作而变化的故需用一个指针top来标记。顺序栈的定义顺序栈的定义  栈的空间能够扩充。设两个常量: STACK_INIT_SIZE(初始分配量) STACKINCREMENT(分配增量)typedefstruct{SElemType*baseSElemType*topintstacksize顺序栈的存储容量}SqStacktop初值指向栈底每插入一个元素(入栈)增始终指向栈顶元素的下一个位置,每删除一个元素减(出栈)。base==  栈不存在栈空:top==base栈満:topbase>=stacksize元素个数??基本操作的实现基本操作的实现 StatusInitStack(SqStackS){Sbase=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType))if(!Sbase)exit(OVERFLOW)Stop=SbaseSstacksize=STACK_INIT_SIZEreturnOK}InitStack()初始化typedefstruct{SElemType*baseSElemType*topintstacksize}SqStack()取栈顶元素()取栈顶元素StatusGetTop(SqStackS,SElemTypee){if(Stop==Sbase)returnERRORe=*(Stop)returnok}()出栈StatusPop(SqStackS,SElemTypee){if(Stop==Sbase)returnERRORe=*Stop returnOK}Stope=*Stop入栈入栈StatusPush(SqStackS,SElemTypee){if(StopSbase>=Sstacksize){Sbase=(SElemType*)realloc(Sbase,(STACK_INIT_SIZESTACKINCREMENT)*sizeof(SElemType))if(!Sbase)exit(OVERFLOW)Stop=SbaseSstacksizeSstacksize=STACKINCREMENT}*Stop=ereturnok}*Stop=eStop栈顶指针链栈∧aan注意:链栈中指针的方向an栈底元素链栈适用于多个栈共享一个空间。栈的应用举例例一、数制转换例二、括号匹配的检验例三、行编辑程序例四、迷宫求解例五、表达式求值例六、实现递归队列例、数制转换问题例、数制转换问题算法基于原理:N=(Ndivd)×dNmodd例如:()=()其运算过程如下:NNdivNmod     voidconversion(){InitStack(S)scanf("d",N)while(N){Push(S,N)N=N}while(!StackEmpty(S)){Pop(S,e)printf("d",e)}}conversion例、括号匹配的检验例、括号匹配的检验假设在表达式中:([]())或[([][])]等为正确的格式[(])或([())或(()) 均为不正确的格式检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如:考虑下列括号序列:()算法的设计思想:算法的设计思想:)凡出现左括弧则进栈)凡出现右括弧首先检查栈是否空若栈空则表明该“右括弧”多余否则和栈顶元素比较若相匹配则“左括弧出栈”否则表明不匹配)表达式检验结束时若栈空则表明表达式中匹配正确否则表明“左括弧”有余例、行编辑程序问题例、行编辑程序问题“每接受一个字符即存入存储器”并不恰当!在用户输入一行的过程中允许用户输入出差错并在发现有误时可以及时更正。合理的作法是:   设立一个输入缓冲区用以接受用户输入的一行字符然后逐行存入用户数据区并假设“#”为退格符“”为退行符。可设这个输入缓冲区为一个栈结构。假设从终端接受了这样两行字符:whli##ilr#e(s#*s)outchaputchar(*s=#)则实际有效的是下列两行:while(*s)putchar(*s)while(ch!=EOFch!='n'){switch(ch){case'#':Pop(S,c)breakcase'':ClearStack(S)break重置S为空栈default:Push(S,ch)break}ch=getchar()从终端接收下一个字符}ClearStack(S)重置S为空栈if(ch!=EOF)ch=getchar() }while(ch!=EOF){EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区例、迷宫问题例、迷宫问题通常用的是“穷举求解”的方法基本思想:若当前位置“可通”则纳入路径继续前进若当前位置“不可通”则后退换方向继续探索若四周“均无通路”则将当前位置从路径中删除出去。设定当前位置的初值为入口位置do{若当前位置可通 则{将当前位置插入栈顶若该位置是出口位置则算法结束否则切换当前位置的东邻方块为新的当前位置  }否则{ ………}}while(栈不空)若栈不空且栈顶位置尚有其他方向未被探索 则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通 则{删去栈顶位置从路径中删去该通道块若栈不空则重新测试新的栈顶位置直至找到一个可通的相邻块或出栈至栈空  }若栈空则表明迷宫没有通路。$$$$$$$$例、表达式求值例、表达式求值例、实现递归例、实现递归   当在一个函数的运行期间调用另一个函数时在运行该被调用函数之前需先完成三项任务:将所有的实在参数、返回地址等信息传递给被调用函数保存为被调用函数的局部变量分配存储区将控制转移到被调用函数的入口。保存被调函数的计算结果释放被调函数的数据区依照被调函数保存的返回地址将控制转移到调用函数。  从被调用函数返回调用函数之前应该完成下列三项任务:多个函数嵌套调用的规则是:此时的内存管理实行“栈式管理”后调用先返回!例如:voidmain(){voida(){voidb(){………a()b()……}main}a}bMain的数据区函数a的数据区函数b的数据区递归工作栈:递归过程执行过程中占用的数据区。递归工作记录:每一层的递归参数合成一个记录。当前活动记录:栈顶记录指示当前层的执行情况。当前环境指针:递归工作栈的栈顶指针。  递归函数执行的过程可视为同一函数进行嵌套调用。例如:Hanoivoidhanoi(intn,charx,chary,charz){将塔座x上按直径由小到大且至上而下编号为至n的n个圆盘按规则搬到塔座z上y可用作辅助塔座。if(n==)move(x,,z)将编号为1的圆盘从x移到zelse{hanoi(n,x,z,y)将x上编号为1至n的圆盘移到y,z作辅助塔move(x,n,z)将编号为n的圆盘从x移到zhanoi(n,y,x,z)将y上编号为1至n的圆盘移到z,x作辅助塔}}abc返址nxyzacbabcvoidhanoi(intn,charx,chary,charz){if(n==)move(x,,z)else{hanoi(n,x,z,y)move(x,n,z)hanoi(n,y,x,z)}}cabbcavoidmain(){hanoi(,a,b,c)}bacabc 队列 队列队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入而在另一端进行删除。允许删除的一端称为队头(front)允许插入的一端称为队尾(rear)。线性表栈队列Insert(L,i,x)Insert(S,n,x)Insert(Q,n,x)≤i≤nDelete(L,i)Delete(S,n)Delete(Q,)≤i≤n队列亦称作先进先出(FirstInFirstOut)的线性表。(P图)例如:排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。队列亦称作先进先出(FirstInFirstOut)的线性表。(P图)例如:排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。队列的抽象数据类型定义队列的抽象数据类型定义ADTQueue{数据对象:D={ai|ai∈ElemSet,i=,,,n,n≥}数据关系:R={<ai,ai>|ai,ai∈D,i=,,n}约定其中a端为队列头an端为队列尾 基本操作:         …………}ADTQueue队列的基本操作:队列的基本操作:InitQueue(Q)DestroyQueue(Q)QueueEmpty(Q)QueueLength(Q)ClearQueue(Q)GetHead(Q,e)EnQueue(Q,e)DeQueue(Q,e)用e返回队头元素在队尾插入元素删除队头元素队列类型的实现队列类型的实现链队列链式映象循环队列顺序映象链队列链队列它是限制仅在表头删除和表尾插入的单链表。一个链队列由一个头指针唯一确定。显然仅有单链表的头指针不便于在表尾做插入操作为此再增加一个尾指针指向链表的最后一个结点。我们将这两个指针封装在一起。typedefstructQNode{结点类型QElemTypedatastructQNode*next}QNode,*QueuePtrtypedefstruct{链队列类型QueuePtrfront队头指针QueuePtrrear队尾指针}LinkQueue空队列:基本操作的算法描述基本操作的算法描述StatusInitQueue(LinkQueueQ){构造一个空队列QQfront=Qrear=(QueuePtr)malloc(sizeof(Qnode))if(!Qfront)exit(OVERFLOW)存储分配失败Qfront>next=returnOK}初始化入队插入元素(在队尾)入队插入元素(在队尾)StatusEnQueue(LinkQueueQ,QElemTypee){插入元素e为Q的新的队尾元素p=(QueuePtr)malloc(sizeof(Qnode))if(!p)exit(OVERFLOW)存储分配失败p>data=ep>next=Qrear>next=pQrear=preturnOK}出队删除(队头)元素出队删除(队头)元素StatusDeQueue(LinkQueueQ,QElemTypee){若队列不空则删除Q的队头元素用e返回其值并返回OK否则返回ERRORif(Qfront==Qrear)returnERRORp=Qfront>nexte=p>dataQfront>next=p>nextfree(p)returnOK}if(Qrear==p)Qrear=Qfront销毁队列销毁队列StatusDestroyQueue(LinkQueueQ){while(Qfront){Qrear=Qfront>nextfree(Qfront)从队头释放结点。Qfront=Qrear}returnOK}循环队列顺序映象循环队列顺序映象 队列的顺序存储结构称为顺序队列顺序队列实际上是运算受限的顺序表。顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的因而要设两个指针(fornt,rear)和分别指示队头和队尾元素在队列中的位置约定它们的初始值在队列初始化时均应置为0。入队时将新元素插入所指的位置然后将rear加1。出队时删去所指的元素然后将front加1并返回被删元素。队列的插入和删除示意图队列的插入和删除示意图rearfrontfrontfrontrearrearrearfront=rear=front=rear=front=rear=front=rear=front=rear=aaaaa(a)(b)(c)(e)(f)初始状态a入队a,a,a出队假溢出frontarearfronta,a入队front=rear=(d)aa,a,a进队aa克服上述假上溢现象的方法:克服上述假上溢现象的方法: 是将向量空间想象为一个首尾相接的圆环并称这种向量为循环向量存储在其中的队列称为循环队列(CircularQueue)(图)在循环队列中进行出队、入队操作时头尾指针仍要加朝前移动。只不过当头尾指针指向向量上界(MaxSize)时其加操作的结果是指向向量的下界。循环队列示意图循环队列示意图rearfrontfrontfrontfrontrearrearrear(a)(b)(c)(d)aaaaaaaafrontrear(e)aaaaaa队満、队空的判断出现的问题?   --队満、队空的判断出现的问题?   --队満、队空的判断只凭等式Qfront==Qrear无法判断队空还是满。解决方法:   ()增设标志位  ()少用一个元素空间。约定以“队列头指针在队列尾指针的下一位置上”作为判满的标志。队空:  Qfront==Qrear队满: (Qrear)MAXQSIZE==Qfront队列的顺序存储结构队列的顺序存储结构#defineMAXQSIZE最大队列长度typedefstruct{QElemType*base动态分配存储空间intfront头指针指向队头元素intrear尾指针,指向队列尾元素的下一个位置}SqQueue基本操作算法描述基本操作算法描述StatusInitQueue(SqQueueQ){构造一个最大存储空间为maxsize的空循环队列QQbase=(QElemType*)malloc(MAXQSIZE*SIZEOF(QElemType))if(!Qbase)exit(OVERFLOW)Qfront=Qrear=初值returnOK}插入元素:插入元素:StatusEnQueue(SqQueueQ,ElemTypee){插入元素e为Q的新的队尾元素if((Qrear)MAXQSIZE==Qfront)returnERROR队列满QbaseQrear=eQrear=(Qrear)MAXQSIZEreturnOK}删除元素:删除元素:StatusDeQueue(SqQueueQ,QElemTypee){若队列不空则删除Q的队头元素用e返回其值并返回OK否则返回ERRORif(Qfront==Qrear)returnERRORe=QbaseQfrontQfront=(Qfront)MAXQSIZEreturnOK}求长度(P)

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/53

数据结构 第3章 栈和队列

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利