《数据结构》第三四章习题C语言版.doc

《《数据结构》第三四章习题C语言版.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.6证明：ipj，pk还在栈中，则pk1){printf(j);digui(j-1);}}3.11简述队列和栈两种数据类型的相同点和差异点•相同点:都是操作受限的线性表•差异:1.队列只能在头部删除、尾部插入而栈

2、只能在称为栈顶的一端插入、删除。2.队列是先进先出表，栈是后进先出表。3.15typedefintElemType;typedefstruct{inttop[2];ElemTypev[m0]；}DuStack;Inistack(DuStack&tws){tws.top[0]=0;tws.top[1]=m0-1;v=(ElemType*)malloc(m0*sizeof(ElemType));}voidpush(DuStack*tws,inti,ElemTypex){if(tws->top[0]+1=tws->top[1]){printf(“overflow”);return;}swit

3、ch(i){case0:tws->v[tws->top[0]]=x;tws->top[0]++;break;case1:tws->v[tws->top[1]]=x;tws->top[1]--;break;}}ElemTypepop(Dustack*tws,inti){switch(i){case0:if(tws->top[0]==0){printf(“underflow”);return;}tws->top[0]--；x=tws->v[tws->top[0]];break;case1:if(tws->top[1]==m0-1){printf(“underflow”);return;}t

4、ws->top[1]++;x=tws->v[tws->top[1]];break;}return(x);}3.17StatusMatching（）{//设读入的字符序列以@结尾,本算法判该字符串是否以&为中心对称InitStack(s1);InitStack(s2);scanf(&ch);while(ch!='@')//读入以@为结尾的字符序列{Push(s1,ch);scanf(&ch);//@不是栈中字符序列的一部分}x=GetTop(s1);//取s1栈顶元素,注意GetTop与pop区别WHILE(x!='&')//将字符串'&'后的一串放入栈S2{push(s2,x);Pop

5、(s1,x)//'&'弹出栈S1,但不进入S2}eq=true;//判s1,s2中对应字符相等否while(!StackEmpty(s1)&&!StackEmpty(s2)&&eq){pop(s1,x1);pop(s2,x2);if(x1!=x2)//有不配字符eq=false;}IF(StackEmpty(s1)&&StackEmpty(s2)&&eq)returnTRUE;//匹配elsereturnFALSE;//不匹配}3.29typedefstruct{elemtypeelems[m];intrear,front//取值在0到m-1之间inttag;　　//０为空，１为非空}

6、cyclicqueue//设头、尾指针和标志域的循环队列StatusInitQueue(cyclicqueue&cq);　　//初始化{cq.tag:=0;cq.rear=cq.front=0;returnOK;} Status  EnQueue(cyclicqueue&cq,elemtypex){　　　　//cq是由头尾指针和标志域的循环队列，本算法是入队操作，若队列不满，　　　　　//则将x插入到队尾If((cq.tag=1)&&(cq.front=cq.rear))return(false);//队满else{cq.rear=(cq.rear+1)%m;cq.elems(cq.r

7、ear)=x;if(cq.tag=0)cq.tag=1;//由空变不空标记}} StatusDelQueue(cyclicqueue&cq,elemtype&x){　　　　　//cq是由头尾指针和标志域的循环队列，本算法是出队操作，若队列非空　　　　　//则将队头元素出队If(cq.tag=0)return(FALSE)//队空不能删除else{cq.front=(cq.front+1)%m;IF（cq.front=cq.rear）cq.tag