數(shù)據(jù)結(jié)構(gòu)教程習(xí)題答案 李蓉蓉 安楊等編著第三版 第三章答案.doc

3.3/*題目：假設(shè)表達(dá)式中允許包含三種括號(hào)，圓括號(hào)，方括號(hào)和大括號(hào)，編寫(xiě)一個(gè)算法判斷表達(dá)式中的括號(hào)是不是匹配實(shí)踐:狼影時(shí)間：2012.9.19*/# include # include # define size 256/定義節(jié)點(diǎn)typedef structchar exsize;int top;STACK;/函數(shù)聲明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(輸入表達(dá)式n);scanf(%s, exp);if(is_match(exp)printf(此表達(dá)式匹配n);elseprintf(此表達(dá)式不匹配n);/棧的初始化STACK *init_stack(void)STACK *stack = (STACK *)malloc(sizeof(STACK);if(NULL = stack)printf(內(nèi)存分配失敗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;/*輸入表達(dá)式(1+2+3*5234)此表達(dá)式匹配Press any key to continue*/3.4/*題目;設(shè)從鍵盤(pán)輸入一整數(shù)序列，編寫(xiě)程序，當(dāng)ai大于零時(shí)，ai進(jìn)隊(duì)，當(dāng)ai小于零時(shí)，將對(duì)首元素出隊(duì)當(dāng)ai等于零時(shí)，將表示輸入結(jié)束，要求用環(huán)形隊(duì)列，進(jìn)隊(duì)與出隊(duì)單獨(dú)編寫(xiě)算法，并在異常情況下 打印出錯(cuò)實(shí)踐：狼影時(shí)間;2012.9.20*/# include # include # define size 100typedef struct int nodesize;int front;int rear;QUEUE;/函數(shù)聲明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(輸入數(shù)字的個(gè)數(shù)n);scanf(%d, &n);printf(請(qǐng)輸入數(shù)據(jù)n);for(i = 0; in; i+)scanf(%d, &arryi);i = 0;while(i0)if(!en_queue(queue, arryi)printf(進(jìn)隊(duì)出錯(cuò)n);break;if(arryifront = queue-rear = -1;return queue;/進(jìn)隊(duì)的操作 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; /進(jìn)行出隊(duì)操作 bool out_queue(QUEUE *queue) if(queue-rear = queue-front)return false;elsequeue-front = (queue-front+1)%size;return true; /打印隊(duì)列void print_queue(QUEUE *queue)if(queue-front = queue-rear)printf(隊(duì)列為空n);return;elsewhile(queue-front != queue-rear)queue-front = (queue-front+1)%size;printf(%d , queue-nodequeue-front);/*輸入數(shù)字的個(gè)數(shù)5請(qǐng)輸入數(shù)據(jù)1 2 3 -1 4隊(duì)列內(nèi)容是2 3 4Press any key to continue*/3.5/*題目：編寫(xiě)一個(gè)算法，將一個(gè)環(huán)形隊(duì)列（容量為n，元素下標(biāo)從1到n）的元素倒置（具體的圖請(qǐng)參考課本p88）設(shè)計(jì);狼影時(shí)間：2012.9.20*/# include # include /* 解此題的思路是 將隊(duì)列中的數(shù)據(jù)先轉(zhuǎn)到棧中，然后再把棧中的數(shù)據(jù)轉(zhuǎn)到另一個(gè)隊(duì)列中，實(shí)現(xiàn)倒置 對(duì)照書(shū)中給的圖來(lái)初始化兩個(gè)隊(duì)列 圖參考課本88頁(yè) 也有其他簡(jiǎn)單的方法，如果你想到告訴我一聲啊，共同學(xué)習(xí)嗎！*/typedef structchar c20;int top;STACK;typedef structchar ch20; int rear;int front;QUEUE;/函數(shù)聲明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);/初始化 隊(duì)列QUEUE *init_queue1(void)QUEUE *queue = (QUEUE *)malloc(sizeof(QUEUE);if(NULL = queue)printf(內(nèi)存分配錯(cuò)誤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èi)存分配錯(cuò)誤n);exit(-1);stack-top = -1;return stack;/隊(duì)列的初始化QUEUE *init_queue2(void)QUEUE *queue = (QUEUE *)malloc(sizeof(QUEUE);if(NULL = queue)printf(內(nèi)存分配錯(cuò)誤n);exit(-1);queue-front = 10;queue-rear = 0;return queue;/創(chuàng)建隊(duì)列void creat_queue(QUEUE *queue)char c;for(c = a; crear = (queue-rear)%10+1;queue-chqueue-rear = c;/數(shù)的轉(zhuǎn)置void traverse(QUEUE *queue1, QUEUE *queue2, STACK *stack)queue1-front = (queue1-front)%10+1;/將隊(duì)列中的數(shù)出隊(duì)放到棧中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);/將元素出棧，放到隊(duì)列中queue2-rear = (queue2-rear)%10+1;while(stack-top != -1)queue2-chqueue2-rear = stack-cstack-top;stack-top-;queue2-rear = (queue2-rear)%10+1;/打印隊(duì)列中的內(nèi)容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個(gè)10以內(nèi)的數(shù)每輸入i（0=i=9)就把它插入到第i號(hào)隊(duì)列，最后把10個(gè)隊(duì)中非空隊(duì)列，按隊(duì)列號(hào)從小到大 的順序串接成一條鏈，并輸出該鏈的所有元素設(shè)計(jì)：狼影時(shí)間：2012.9.20*/# include # include /在這里用鏈表的形式來(lái)創(chuàng)建隊(duì)列typedef struct node int data;struct node *pNext;NODE;typedef structNODE *front;NODE *rear;QUEUE;/函數(shù)的聲明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個(gè)隊(duì)列for(j = 0; j10; j+)queuej = init_queue();/輸入輸入數(shù)的個(gè)數(shù)printf(請(qǐng)輸入數(shù)的個(gè)數(shù)nn);scanf(%d, &n);printf(請(qǐng)輸入i值(0=i=9)n);for(j = 0; jn; j+)doscanf(%d, &i);if(i=10)printf(你輸入第%d個(gè)數(shù)據(jù)錯(cuò)誤, 請(qǐng)重新輸入n, j+1);while(i=10); /當(dāng)i值滿足條件時(shí)，循環(huán)結(jié)束/將i值放入相應(yīng)的隊(duì)列中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;/將隊(duì)列中的內(nèi)容放入鏈表for(i = 0; ifront = (NODE *)malloc(sizeof(NODE);if(NULL = queue-front)printf(內(nèi)存分配錯(cuò)誤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èi)存分配錯(cuò)誤n);exit(-1);pHead-pNext = NULL;return pHead;/進(jìn)隊(duì)列的操作void en_queue(QUEUE *queue, int i)NODE *pNew;pNew = (NODE *)malloc(sizeof(NODE);if(NULL = pNew)printf(內(nèi)存分配錯(cuò)誤n);exit(-