第3章-堆栈和队列.

1本章主要内容:堆栈堆栈的应用队列队列的应用23.1栈(Stack)•只允许在一端插入和删除的线性表•允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)•特点后进先出(LIFO)退栈进栈3–栈的存储结构•顺序栈–实现：一维数组s[M]top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组长度为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空4栈的基本操作1、初始化Initiate(s)2、进栈push(s,x)3、退栈pop(s)4、取栈顶元素gettop(s)5、判栈是否非空Notempty(s)6、置空栈SETNULL(s)5栈的顺序存储结构顺序栈的定义typedefintelemtype;#definemaxsize64typedefstruct{elemtypedata[maxsize];inttop;}seqstack;6栈的基本运算初始化initiate(seqstack*s){s-top＝0;}判栈空intnotEMPTY(seqstack*s){if(s-top0)return1;elsereturn0;}7进栈seqstack*PUSH(seqstack*s,datatypex){if(s-top==maxsize){printf(“overflow\n”);returnNULL;}else{s-data[s-top]＝x;s-top++;}returns;}8退栈datatypePOP(seqstack*s){if(s-top=0){printf(“underflow\n”);returnNULL;}else{s-top--;return(s-data[s-top]);}}9取栈顶datatypeTOP(seqstack*s){if(s-top=0){printf(“underflow\n”);returnNULL;}elsereturn(s-data[s-top-1]);}10栈的链接表示—链式栈•链式栈无栈满问题，空间可扩充•插入与删除仅在栈顶处执行•链式栈的栈顶在链头•适合于多栈操作11栈的链接存储结构链栈的结点定义typedefintelemtype;structslnodetype{elemtypedata;structslnodetype*next;};12链栈的进栈算法slnodetype*PUSHLSTACK(slnodetype*top,elemtypex){slnodetype*p;p＝malloc(sizeof(slnodetype));p-data＝x;p-next＝top;returnp;}^…...栈底hhxp13链栈的出栈算法slnodetype*POPLSTACK(slnodetype*top,datatype*datap){slnodetype*p;if(top-next==NULL){printf(“underflow\n”);returnNULL;}else{p＝top;*datap＝p-data;top=top-next;free(p);returntop;}}top^…...栈底top14例递归的执行情况分析递归过程及其实现递归：函数直接或间接的调用自身实现：建立递归工作栈voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i=w;++i)printf(“%3d,”,w);printf(“/n”);}}运行结果：1，2，2，3，3，3，3.2栈的应用当w=315递归调用执行情况如下：主程序(1)print(w)w=3;3print(2);（1）w=3top(2)输出：3,3,3w2print(1);（2）w=2（1）w=3top(3)输出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)输出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)输出：2,2(2)2(1)3top(4)输出：1(3)1(2)2(1)3top(2)输出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0结束(1)16表达式求值中缀表达式a*b+ca+b*ca+(b*c+d)/e中缀表达式：操作数栈和运算符栈例计算2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符-12(1)对每种运算符赋予一个优先数，如：运算符：*/+-优先数：2211语句结束符“；”的优先数为0(2)可以使用两个工作栈：数栈(NS)；运算符栈(OS)。(3)编译程序自左向右扫描至语句结束符，处理的原则是：凡遇到操作数，一律进数栈；当遇到运算符时，则将该运算符的优先数与运算符栈中的栈顶元素的优先数相比较。若该运算符的优先数大，则进栈；反之，则取出栈顶的运算符，并在数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入数栈，然后继续比较该运算符与栈顶元素的优先数。17队列(Queue)•定义–队列是只允许在一端删除，在另一端插入的顺序表–允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。•特性–先进先出(FIFO,FirstInFirstOut)18队列的进队和出队进队时队尾指针先进一rear=rear+1，再将新元素按rear指示位置加入。出队时队头指针先进一front=front+1，再将下标为front的元素取出。队满时再进队将溢出出错；队空时再出队将队空处理。19顺序队列的指针说明typedefstruc{datatypedata[maxsize];intfront,rear;}sequeue;20队列的基本操作1、置空队列2、判定队列是否为空3、取队列头元素4、将新元素插入队尾5、队列头元素出队21顺序队列置队空SETNULL(sequeue*sq){sq-front＝maxsize-1;sq-rear＝maxsize-1;}22顺序队列判队空intEMPTY(sequeue*sq){if(sq-rear==sq-front)return(TRUE);elsereturn(FALSE);}23顺序队列取队头元素datatypeFRONT(sequeue*sq){if(EMPTY(sq)){printf(“queueisempty\n”);returnNULL;}elsereturn(sq-front+1)%maxsize;}24顺序队列入队intENQUEUE(sequeue*sq,datatypex){if(sq-front==(sq-rear+1)%maxsize){printf(“sequeueisfull\n”;returnNULL);}else{sq-rear＝(sq-rear+1)%maxsize;sq-data[sq-rear]＝x;return(TRUE);}}25顺序队列出队datetypeDEQUEUE(sequeue*sq){if(EMPTY(sq)){printf(“queueisempty\n”);returnNULL;}else{sq-front＝(sq-front+1)%maxsize;return(sq-data[sq-front]);}}26•顺序队列存在问题设数组维数为M，则：–当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出–当front-1,rear=M-1时，再有元素入队发生溢出——假溢出•解决方案1.队首固定，每次出队剩余元素向下移动——浪费时间2.循环队列»基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;0M-11frontrear实现：利用“模”运算入队：rear=(rear+1)%M;sq[rear]=x;出队：front=(front+1)%M;x=sq[front];队满、队空判定条件27•存储队列的数组被当作首尾相接的表处理。•队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。•队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;•队列初始化：front=rear=0;循环队列(CircularQueue)28012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front==rear队满：(rear+1)%M==front29循环队列的进队和出队30队列的链接表示—链式队列•队头在链头，队尾在链尾。•链式队列在进队时无队满问题，但有队空问题。31链队列结点类型定义typedefstruct{linklist*front,*rear;}linkqueue;32链队列置队空SETNULL(linkqueue*q){q-front＝malloc(sizeof(linklist));q-front-next＝NULL;q-rear＝q-front;}33链队列判队空intEMPTY(linkqueue*q){ifq-front==q-rear)return(TRUE);elsereturn(FALSE);}34链队列取队头结点datatypeFRONT(linkqueue*q){if(EMPTY(q)){printf(“queueisempty\n”);returnNULL;}elsereturn(q-front-next-data);}35链队列入队ENQUEUE(linkqueue*q,datatypex){q-rear-next＝malloc(sizeof(linklist));q-rear＝q-rear-next;q-rear-data＝x;q-rear-next＝NULL;}36链队列出队datatypeDEQUEUE(linkqueue*q){linklist*s;if(EMPTY(q)){printf(“queueisempty\n”);returnNULL;}else{s＝q-front;q-front＝q-front-next;free(s);return(q-front-data);}}3701110111101010100100111101110011100110000110011012345678123456队列的应用举例－－求迷宫的最短路径38xy00+11+1+12+103+1-140-15-1-16-107-1+1需要解决的问题1：如何从某一坐标点出发搜索其四周的邻点39需要解决的问题2：如何存储搜索路径需要解决的问题3：如何防止重复到达某坐标点步xypre1110222133324313…………40需要解决的问题4：如何输出搜索路径1…121314151617181920x1…525656656…y1…663175488…pre0…8910101112141616…41#definer64#definem210#definen210intm＝m2-2,n＝n2-2;typedefstruct{intx,y;intpre;}sqtype;sqtypesq[r];structmoved{intx,y;}move[8];intmaze[m2][n2];42intSHORTPATH(intmaze[][]){inti,j,v,front,rear,x,y;sq[1].x