《数据结构教程习题答案 李蓉蓉 安杨等编著第三版 第三章答案》由会员分享，可在线阅读，更多相关《数据结构教程习题答案 李蓉蓉 安杨等编著第三版 第三章答案（15页珍藏版）》请在金锄头文库上搜索。
1、3.3/*题目：假设表达式中允许包含三种括号，圆括号，方括号和大括号，编写一个算法判断表达式中的括号是不是匹配实践:狼影时间：2012.9.19*/# include # include # define size 256/定义节点typedef structchar exsize;int top;STACK;/函数声明STACK *init_stack(void);bool is_match(char *exp);bool pop_stack(STACK *stack, char *ch);void push_stack(STACK *stack, char e);main()char ex
2、p256;printf(输入表达式n);scanf(%s, exp);if(is_match(exp)printf(此表达式匹配n);elseprintf(此表达式不匹配n);/栈的初始化STACK *init_stack(void)STACK *stack = (STACK *)malloc(sizeof(STACK);if(NULL = stack)printf(内存分配失败n);exit(-1);stack-top = -1;return stack;/判断是不是匹配bool is_match(char *exp)int i = 0;char ch;STACK *stack;stack
3、= init_stack();while(expi != 0)if(=expi | =expi | =expi)push_stack(stack, expi);else if()=expi | =expi | =expi)/线面是匹配的三种情况，switch(expi)case ):if(pop_stack(stack, &ch)if(ch != ()return false;elsereturn false;break;case :if(pop_stack(stack, &ch)if(ch != )return false;elsereturn false;break;case :if(po
4、p_stack(stack, &ch)if(ch != )return false;elsereturn false;break;default:break;i+;if(-1 = stack-top)return true;elsereturn false;/入栈的操作void push_stack(STACK *stack, char e)stack-top+;stack-exstack-top = e;/出栈的操作bool pop_stack(STACK *stack, char *ch)if(-1 = stack-top)return false;else*ch = stack-exst
5、ack-top;stack-top-;return true;/*输入表达式(1+2+3*5234)此表达式匹配Press any key to continue*/3.4/*题目;设从键盘输入一整数序列，编写程序，当 ai 大于零时，ai 进队，当 ai 小于零时，将对首元素出队当 ai 等于零时，将表示输入结束，要求用环形队列，进队与出队单独编写算法，并在异常情况下 打印出错实践：狼影时间;2012.9.20*/# include # include # define size 100typedef struct int nodesize;int front;int rear;QUEUE;
6、/函数声明QUEUE *init_queue(void);bool en_queue(QUEUE *queue, int e);bool out_queue(QUEUE *queue);void print_queue(QUEUE *queue);main()QUEUE *queue;int arrysize;int n;int i;queue = init_queue();printf(输入数字的个数n);scanf(%d, &n);printf(请输入数据n);for(i = 0; i0)if(!en_queue(queue, arryi)printf(进队出错n);break;if(ar
7、ryifront = queue-rear = -1;return queue;/进队的操作bool en_queue(QUEUE *queue, int e)if(queue-front = (queue-rear+1)%size)return false;elsequeue-rear = (queue-rear+1)%size;queue-nodequeue-rear = e;return true;/进行出队操作bool out_queue(QUEUE *queue)if(queue-rear = queue-front)return false;elsequeue-front = (q
8、ueue-front+1)%size;return true;/打印队列void print_queue(QUEUE *queue)if(queue-front = queue-rear)printf(队列为空n);return;elsewhile(queue-front != queue-rear)queue-front = (queue-front+1)%size;printf(%d , queue-nodequeue-front);/*输入数字的个数5请输入数据1 2 3 -1 4队列内容是2 3 4Press any key to continue*/3.5/*题目：编写一个算法，将一
9、个环形队列（容量为 n，元素下标从 1 到 n）的元素倒置（具体的图请参考课本 p88）设计;狼影时间：2012.9.20*/# include # include /*解此题的思路是 将队列中的数据先转到栈中，然后再把栈中的数据转到另一个队列中，实现倒置对照书中给的图来初始化两个队列图参考课本 88 页也有其他简单的方法，如果你想到告诉我一声啊， ，共同学习吗！*/typedef structchar c20;int top;STACK;typedef structchar ch20; int rear;int front;QUEUE;/函数声明void creat_queue(QUEUE
10、*queue);QUEUE *init_queue1(void);void traverse(QUEUE *queue1, QUEUE *queue2, STACK *stack);STACK *init_stack(void);QUEUE *init_queue2(void);void creat_queue(QUEUE *queue);void print_queue(QUEUE *queue);main()QUEUE *queue1, *queue2;STACK *stack;stack = init_stack();queue1 = init_queue1();queue2 = ini
11、t_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;return queue;/栈的初始化STACK *init_stack(void)STACK *stack = (STACK *)mal
12、loc(sizeof(STACK);if(NULL = stack)printf(内存分配错误n);exit(-1);stack-top = -1;return stack;/队列的初始化QUEUE *init_queue2(void)QUEUE *queue = (QUEUE *)malloc(sizeof(QUEUE);if(NULL = queue)printf(内存分配错误n);exit(-1);queue-front = 10;queue-rear = 0;return queue;/创建队列void creat_queue(QUEUE *queue)char c;for(c = a
13、; crear = (queue-rear)%10+1;queue-chqueue-rear = c;/数的转置void traverse(QUEUE *queue1, QUEUE *queue2, STACK *stack)queue1-front = (queue1-front)%10+1;/将队列中的数出队放到栈中while(queue1-front != queue1-rear)stack-top+;stack-cstack-top = queue1-chqueue1-front;queue1-front = (queue1-front)%10+1;stack-top+;stack-cstack-top = queue1-chqueue1-front;free(queue1);/将元素出栈，放到队列中queue2-rear = (queue2-rear)%10+1;while(stack-top != -1)queue2-chqueue2-rear = stack-cstack-top;stack-top-;queue2-rear = (queue2-re
