习题课(栈队列串数组).ppt

《习题课(栈队列串数组).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题3.15constintStackSize=500;typedefstruct{SElemtype*base;inttop0,top1;     }TwoStack;//双向栈类型StatusInitStack(TwoStack&tws){tws.base=newSElemtype[StackSize];    tws.top0=-1;  tws.top1=StackSize;  returnOK;}Statuspush(TwoStack&tws,inti,SElemtypex)//x入栈,i=0表示低端栈,i

2、=1表示高端栈{  if(tws.top0+1==tws.top1)returnOVERFLOW;//栈满if(i==0)tws.base[++tws.top0]=x;  elseif(i==1)tws.base[--tws.top1]=x;  elsereturnERROR;  returnOK;}Statuspop(TwoStack&tws,inti,SElemtype&x)//x出栈,i=0表示低端栈,i=1表示高端栈{if(i==0){  if(tws.top0==-1)returnOVERFLOW;    x

3、=tws.base[tws.top0--];}elseif(i==1)  { if(tws.top1==StackSize)returnOVERFLOW;x=tws.base[tws.top1++]; }  elsereturnERROR;returnOK;}习题3.18StatusEx3_18(char*str)//判别表达式中的小括号是否匹配{count=0;for(p=str;p;p++){  if(*p==‘(’)count++;    elseif(*p==‘)’)count--;    if(count

4、<0)returnERROR;//避免…)..(…假匹配}  if(count)returnERROR;//注意括号不匹配的两种情况returnOK;}习题3.19StatusEx3_19(SqListstr)//判别表达式中三种括号是否匹配{InitStack(S);for(i=0;i

5、

6、str.elem[i]=='['

7、

8、str.elem[i]==‘{’)Push(S,str.elem[i]);    elseif(str.elem[i]==‘)

9、’

10、

11、str.elem[i]==‘]’

12、

13、str.elem[i]==‘}’)    {if(StackEmpty(S))returnERROR;      Pop(S,c);if(str.elem[i]==‘)’&&c!=‘(’)returnERROR;if(str.elem[i]==‘]’&&c!=‘[’)returnERROR;if(str.elem[i]==‘}’&&c!=‘{’)returnERROR;}//elseif}//forif(!StackEmpty(S))returnERROR;  returnOK;

14、}习题3.28voidInitCiQueue(CiQueue&Q)//初始化循环链表表示的队列Q{  Q=newCiLNode; Q->next=Q;}voidEnCiQueue(CiQueue&Q,QElemTypee)//把元素e插入循环链表表示的队列Q,Q指向队尾元素,//Q->next->next指向队头元素{p=newCiLNode;  p->data=e;  p->next=Q->next;//直接把p加在Q的后面Q->next=p;  Q=p;  //修改尾指针}StatusDeCiQueue(CiQueu

15、e&Q,QElemType&e)//从循环链表表示的队列Q头部删除元素e{if(Q==Q->next)returnERROR;//队列已空r=Q->next;p=r->next; e=p->data; r->next=p->next; if(p==Q)Q=r;deletep; returnOK;}//DeCiQueue习题3.29StatusEnCyQueue(CyQueue&Q,QElemTypee)//带tag域的循环队列入队算法,tag值为0表示“空”,1表示“满”{if(Q.front==Q.rear&&Q.t

16、ag==1)returnOVERFLOW; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE; if(Q.front==Q.rear)Q.tag=1;//队列满}//EnCyQueueStatusDeCyQueue(CyQueue&