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

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 exp256;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 = 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(pop_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-exstack-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;/函数声明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; in; i+)scanf(%d, &arryi);i = 0;while(i0)if(!en_queue(queue, arryi)printf(进队出错n);break;if(arryifront = 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 = (queue-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/*题目：编写一个算法，将一个环形队列（容量为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 *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 = 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;return queue;/栈的初始化STACK *init_stack(void)STACK *stack = (STACK *)malloc(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; 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-rear)%10+1;/打印队列中的内容void print_queue(QUEUE *queue)queue-front = (queue-front)%10+1;while(queue-front != queue-rear)printf(%c , queue-chqueue-front);queue-front = (queue-front)%10+1;printf(n);3.6/*题目:输入n个10以内的数每输入i（0=i=9)就把它插入到第i号队列，最后把10个队中非空队列，按队列号从小到大 的顺序串接成一条链，并输出该链的所有元素设计：狼影时间：2012.9.20*/# include # include /在这里用链表的形式来创建队列typedef struct node int data;struct node *pNext;NODE;typedef structNODE *front;NODE *rear;QUEUE;/函数的声明NODE *init_link(void);QUEUE *init_queue(void);void en_queue(QUEUE *queue, int i);void print_link(NODE *pHead);void en_queue(QUEUE *queue, int i);bool is_empty(QUEUE *queue);void put_link(QUEUE *queue, NODE *pHead);main()int n, i, j;QUEUE *queue10;NODE *pHead;/初始化化链表pHead = init_link();/初始化10个队列for(j = 0; j10; j+)queuej = init_queue();/输入输入数的个数printf(请输入数的个数nn);scanf(%d, &n);printf(请输入i值(0=i=9)n);for(j = 0; jn; j+)doscanf(%d, &i);if(i=10)printf(你输入第%d个数据错误, 请重新输入n, j+1);while(i=10); /当i值满足条件时，循环结束/将i值放入相应的队列中switch(i)case 0: en_queue(queue0, i);break;case 1: en_queue(queue1, i);break;case 2: en_queue(queue2, i);break;case 3: en_queue(queue3, i);break;case 4: en_queue(queue4, i);break;case 5: en_queue(queue5, i);break;case 6: en_queue(queue6, i);break;case 7: en_queue(queue7, i);break;case 8: en_queue(queue8, i);break;case 9: en_queue(queue9, i);break;default:break;/将队列中的内容放入链表for(i = 0; ifront = (NODE *)malloc(sizeof(NODE);if(NULL = queue-front)printf(内存分配错误n);exit(-1);queue-front-pNext = NULL;queue-rear = queue-front;return queue;/链表的初始化NODE *init_link(void)NODE *pHead = (NODE *)malloc(sizeof(NODE);if(NULL = pHead)printf(内存分配错误n);exit(-1);pHead-pNext = NULL;return pHead;/进队列的操作void en_queue(QUEUE *queue, int i)NODE *pNew;pNew = (NODE *)malloc(sizeof(NODE);if(NULL = pNew)printf(内存分配错误n);exit(-