数据结构教程习题答案 李蓉蓉 安杨等编著第三版 第三章答案

3.3/********************************************题目：假设表达式中允许包含三种括号，圆括号，方括号和大括号，编写一个算法判断表达式中的括号是不是匹配实践:狼影时间：2012.9.19************************************************/#includestdio.h#includestdlib.h#definesize256//定义节点typedefstruct{charex[size];inttop;}STACK;//函数声明STACK*init_stack(void);boolis_match(char*exp);boolpop_stack(STACK*stack,char*ch);voidpush_stack(STACK*stack,chare);main(){charexp[256];printf(输入表达式\n);scanf(%s,exp);if(is_match(exp)){printf(此表达式匹配\n);}else{printf(此表达式不匹配\n);}}//栈的初始化STACK*init_stack(void){STACK*stack=(STACK*)malloc(sizeof(STACK));if(NULL==stack){printf(内存分配失败\n);exit(-1);}stack-top=-1;returnstack;}//判断是不是匹配boolis_match(char*exp){inti=0;charch;STACK*stack;stack=init_stack();while(exp[i]!='\0'){if('('==exp[i]||'['==exp[i]||'{'==exp[i]){push_stack(stack,exp[i]);}elseif(')'==exp[i]||']'==exp[i]||'}'==exp[i]){//线面是匹配的三种情况，switch(exp[i]){case')':if(pop_stack(stack,&ch)){if(ch!='(')returnfalse;}elsereturnfalse;break;case']':if(pop_stack(stack,&ch)){if(ch!='[')returnfalse;}elsereturnfalse;break;case'}':if(pop_stack(stack,&ch)){if(ch!='{')returnfalse;}elsereturnfalse;break;default:break;}}i++;}if(-1==stack-top)returntrue;elsereturnfalse;}//入栈的操作voidpush_stack(STACK*stack,chare){stack-top++;stack-ex[stack-top]=e;}//出栈的操作boolpop_stack(STACK*stack,char*ch){if(-1==stack-top)returnfalse;else{*ch=stack-ex[stack-top];stack-top--;}returntrue;}/***********************************************输入表达式(((1+2+3*5{{{[[[234]]]}}})))此表达式匹配Pressanykeytocontinue**********************************************/3.4/*************************************************题目;设从键盘输入一整数序列，编写程序，当ai大于零时，ai进队，当ai小于零时，将对首元素出队当ai等于零时，将表示输入结束，要求用环形队列，进队与出队单独编写算法，并在异常情况下打印出错实践：狼影时间;2012.9.20***************************************************************/#includestdio.h#includestdlib.h#definesize100typedefstruct{intnode[size];intfront;intrear;}QUEUE;//函数声明QUEUE*init_queue(void);boolen_queue(QUEUE*queue,inte);boolout_queue(QUEUE*queue);voidprint_queue(QUEUE*queue);main(){QUEUE*queue;intarry[size];intn;inti;queue=init_queue();printf(输入数字的个数\n);scanf(%d,&n);printf(请输入数据\n);for(i=0;in;i++){scanf(%d,&arry[i]);}i=0;while(in){if(arry[i]0){if(!en_queue(queue,arry[i])){printf(进队出错\n);break;}}if(arry[i]0)if(!out_queue(queue)){printf(出队错误\n);break;}if(arry[i]==0){break;}i++;}printf(队列内容是\n);print_queue(queue);printf(\n);}//初始化队列QUEUE*init_queue(void){QUEUE*queue=(QUEUE*)malloc(sizeof(QUEUE));if(NULL==queue){printf(内存分配错误\n);exit(-1);}queue-front=queue-rear=-1;returnqueue;}//进队的操作boolen_queue(QUEUE*queue,inte){if(queue-front==(queue-rear+1)%size)returnfalse;else{queue-rear=(queue-rear+1)%size;queue-node[queue-rear]=e;}returntrue;}//进行出队操作boolout_queue(QUEUE*queue){if(queue-rear==queue-front)returnfalse;elsequeue-front=(queue-front+1)%size;returntrue;}//打印队列voidprint_queue(QUEUE*queue){if(queue-front==queue-rear){printf(队列为空\n);return;}else{while(queue-front!=queue-rear){queue-front=(queue-front+1)%size;printf(%d,queue-node[queue-front]);}}}/***************************输入数字的个数5请输入数据123-14队列内容是234Pressanykeytocontinue****************************/3.5/****************************************************题目：编写一个算法，将一个环形队列（容量为n，元素下标从1到n）的元素倒置（具体的图请参考课本p88）设计;狼影时间：2012.9.20********************************************/#includestdio.h#includestdlib.h/******************************************解此题的思路是将队列中的数据先转到栈中，然后再把栈中的数据转到另一个队列中，实现倒置对照书中给的图来初始化两个队列图参考课本88页也有其他简单的方法，如果你想到告诉我一声啊，，共同学习吗！************************************************/typedefstruct{charc[20];inttop;}STACK;typedefstruct{charch[20];intrear;intfront;}QUEUE;//函数声明voidcreat_queue(QUEUE*queue);QUEUE*init_queue1(void);voidtraverse(QUEUE*queue1,QUEUE*queue2,STACK*stack);STACK*init_stack(void);QUEUE*init_queue2(void);voidcreat_queue(QUEUE*queue);voidprint_queue(QUEUE*queue);main(){QUEUE*queue1,*queue2;STACK*stack;stack=init_stack();queue1=init_queue1();queue2=init_queue2();creat_queue(queue1);traverse(queue1,queue2,stack);print_queue(queue2);}//初始化队列QUEUE*init_queue1(void){QUEUE*queue=(QUEUE*)malloc(sizeof(QUEUE));if(NULL==queue){printf(内存分配错误\n);exit(-1);}queue-front=8;queue-rear=8;returnqueue;}//栈的初始化STACK*init_stack(void){STACK*stack=(STACK*)malloc(sizeof(STACK));if(NULL==stack){printf(内存分配错误\n);exit(-1);}stack-top=-1;returnstack;}//队列的初始化QUEUE*init_queue2(void){QUEUE*queue=(QUEUE*)malloc(sizeof(QUEUE));if(NULL==queue){printf(内存分配错误\n);exit(-1);}queue-front=10;queue-rear=0;returnqueue;}//创建队列voidcreat_queue(QUEUE*queue){charc;for(c='a';c='f';c++){queue-rear=(queue-rear)%10+1;queue-ch[queue-rear]=c;}}//数的转置voidtraverse(QUEUE*queue1,QUEUE*queue2,STACK*stack){queue1-front=(queue1-front)%10+1;//将队列中的数出队放到栈中while(queue1-front!=queue1-rear){stack-top++;stack-c[stack-top]=queue1-ch[queue1-front];queue1-front=(queue1-front)%10+1;}stack-top++;stack-c[stack-top]=queue1-ch[queue1-front];free(queue1);//将元素出栈，放到队列中queue2-rear=(queue2-rear)%10+1;while(stack-top!=-1){queue2-ch[queue2-rear]=stack-c[stack-top];stack-top--;queue2-rear=(que