習(xí)題三與上機(jī)答案

1、習(xí)題三3.1設(shè)將整數(shù)a，b，c，d依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入其中，請(qǐng)回答下述問題：(1)若執(zhí)行以下操作序列Push(a), Pop(),Push(b),Push(c), Pop(), Pop( ),Push(d), Pop( ),則出 棧的數(shù)字序列為何(這里Push(i)表示i進(jìn)棧，Pop( )表示出棧)? (2) 能否得到出棧序列adbc和adcb并說明為什么不能得到或者如何得到。 (3)請(qǐng)分析 a，b ，c ，d 的所有排列中，哪些序列是可以通過相應(yīng)的入出棧操作得到的。解：（1）acbd （2）執(zhí)行以下操作序列Push(a), Pop()

2、,Push(b),Push(c), Push(d),Pop(), Pop( ), Pop( )就可以得到adcb 棧的特點(diǎn)是“后進(jìn)先出”，所以不可能得到adbc （3）Push(a), Push(b),Push(c), Push(d),Pop(), Pop( ), Pop( ) ,Pop()可以得到dcba Push(a), Push(b),Push(c), Pop(), Pop( ), Pop( ) , Push(d),Pop()可以得到cbad Push(a), Push(b), Pop(),Pop( ), Push(c), Pop( ) , Push(d), Pop()可以得到bacd

3、Push(a), Push(b), Pop(), Pop( ), Push(c),Push(d), Pop( ) , Pop()可以得到badc Push(a), Pop(),Push(b),Push(c),Push(d), Pop( ), Pop( ) , Pop()可以得到adcb Push(a), Pop(),Push(b),Push(c), Pop( ), Pop( ) , Push(d), Pop()可以得到acbd Push(a), Pop(),Push(b), Pop( ), Push(c), Pop( ) , Push(d), Pop()可以得到abcd Push(a), Po

4、p(),Push(b), Pop( ), Push(c), Push(d), Pop( ) , Pop()可以得到abdc分別借助順序棧和鏈棧，將單鏈表倒置。解：順序表： #include "stdio.h"#define DataType char#define sqstack_maxsize 40typedef struct sqstack DataType datasqstack_maxsize;int top; SqStackTp;int InitStack(SqStackTp *sq) sq->top=0; return(1);int Push(SqStac

5、kTp *sq,DataType x)if(sq->top=sqstack_maxsize-1) printf("棧滿"); return(0);else sq->top+; sq->datasq->top=x; return(1);int Pop(SqStackTp *sq,DataType *x)if (sq->top=0) printf("下溢"); return(0);else *x=sq->datasq->top; sq->top-; return(1);int EmptyStack(SqStac

6、kTp *sq)if (sq->top=0)return(1);else return(0);/*主函數(shù)*/void main() SqStackTp sq;DataType ch;InitStack(&sq);for (ch='A'ch<='A'+12;ch+) Push(&sq,ch); printf("%c",ch);printf("n");while(!EmptyStack(&sq) Pop(&sq,&ch);printf("%c",ch);

7、 printf("n");鏈表：#include "stdio.h"#define datatype char#define size sizeof(struct node)typedef struct node datatype data;struct node *next;*LStackTp;void InitStack(LStackTp *ls)*ls=NULL;void Push(LStackTp *ls,datatype x) LStackTp p;p=(LStackTp)malloc(size); p->data=x

8、; p->next=*ls;*ls=p;int Pop(LStackTp *ls,datatype *x) LStackTp p;if(*ls)!=NULL) p=*ls;*x=p->data;*ls=(*ls)->next;free(p);return(1); else return(0);int EmptyStack(LStackTp ls) if(ls=NULL) return(1);else return(0);void main() LStackTp ls;datatype ch;InitStack(ls);for (ch='A'

9、ch<='A'+12;ch+) Push(&ls,ch); printf("%c",ls->data);printf("n");while(!EmptyStack(ls) Pop(&ls,&ch);printf("%c",ch); printf("n"); 有兩個(gè)棧A，B這兩個(gè)棧中分別存儲(chǔ)這一個(gè)升序數(shù)列，現(xiàn)要求編寫算法把這兩個(gè)棧中的數(shù)合成一個(gè)升序隊(duì)列解：link merge(link a,link b) link h,s,m,n,t; h=(cnode *)mal

10、loc(sizeof(cnode); h->next=NULL; s=h; m=a; n=b; while(m->next&&n->next) if(m->next->data<n->next->data) t=m->next; m->next=t->next; t->next=s->next; s->next=t; s=t; else if(m->next->data=n->next->data) t=m->next; m->next=t->next;

11、 n=n->next; t->next=s->next; s->next=t; s=t; else t=n->next; n->next=t->next; t->next=s->next; s->next=t; s=t; while(m->next) t=m->next; m->next=t->next; t->next=s->next; s->next=t; s=t; while(n->next) t=n->next; n->next=t->next; t->n

12、ext=s->next; s->next=t; s=t; free(m); free(n); return h;4 設(shè)兩個(gè)棧共享一個(gè)數(shù)組空間，其類型定義見節(jié)，試寫出兩個(gè)棧公用的讀棧頂元算法elemtp top_dustack(dustacktp ds,p;int i)；進(jìn)棧操作算法void push_dustack(dustacktp ds,p;int i , elemtp x)；及出棧算法 elemtp pop_ dustack(dustacktp ds,p;int i )。其中i的取值是1或2，用以指示棧號(hào)。解：讀棧頂元函數(shù) elemtp top_sqstack(s:sqsta

13、cktp) if( s.top=0) return(null); elsereturn(s.elems.top); 進(jìn)棧操作 void push_sqstack(sqstacktp s，elemtp x) 若棧s未滿，將元素x壓入棧中；否則，棧的狀態(tài)不變并給出出錯(cuò)信息 if(s.top=maxsize) printf(“Overflow”); else s.top+; 棧頂指針加1 s.elems.top=x x進(jìn)棧 出棧函數(shù) elemtp pop_sqstack(sqstacktp s) 若棧s不空，則刪去棧頂元素并返回元素值，否則返回空元素NULL if(s.top=0) return(n

14、ull); else s.top-; 棧頂指針減1 teturn(s.elems.top+1); 返回原棧頂元素值 5假設(shè)以數(shù)組sequ(0.m-1)存放循環(huán)隊(duì)列元素，同時(shí)設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)尾元素和內(nèi)含元素的個(gè)數(shù)。試給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)的入隊(duì)列和出隊(duì)列的算法（在出隊(duì)列的算法中要返回隊(duì)頭元素）。解：隊(duì)滿的條件 (sq.rear+1) MOD maxsize=sq.front 入隊(duì)列操作 void en_cqueue(cqueuetp cq,elemtp x) 若循環(huán)隊(duì)列cq未滿，插入x為新的隊(duì)尾元素；否則隊(duì)列狀態(tài)不變并給出錯(cuò)誤信息 if (cq.re

15、ar+1) MOD maxsize=cq.front) printf(“Overflow”); else cq.rear=(cq.rear+1) MOD maxsize; cq.elemcq.rear=x 出隊(duì)列函數(shù) elemtp dl_cqueue(VAR cq:cqueuetp) 若循環(huán)隊(duì)列cq不空，則刪去隊(duì)頭元素并返回元素值；否則返回空元素NULL if( cq.front=cq.rear) return(NULL); else cq.front=(cq.front+1) MOD maxsize; return(cq.elemcq.front); 6 假設(shè)以帶頭結(jié)點(diǎn)的環(huán)形鏈表表示隊(duì)列，并

16、且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注意不設(shè)頭指針），試編寫相應(yīng)的初始化隊(duì)列、入隊(duì)列、出隊(duì)列的算法。解：初始化： void init_lqueue( lqueuetp lq) 設(shè)置一個(gè)空的鏈隊(duì)列l(wèi)q new(lq.front); lq.front->next:=NIL; lq.rear=lq.front; 入隊(duì)列操作： PROC en_lqueue(VAR lq:lqueuetp;x:elemtp); 在鏈隊(duì)列l(wèi)q中，插入x為新的隊(duì)尾元素 BEGIN new(s); s.data:=x; s.next:=NIL; lq.rear.next:=s; lq.rear:=sENDP; en_lqu

17、eue出隊(duì)列操作： elemtp dl_lqueue(lqueuetp lq) 若鏈隊(duì)列l(wèi)q不空，則刪去隊(duì)頭元素并返回元素值；否則返回空元素NULL if(lq.front=lq.rear) return(null); else p=lq.front->next; lq.front->next=p->next; IF (p->next=NIL)lq.rear=lq.front; 當(dāng)鏈隊(duì)列中僅有一個(gè)結(jié)點(diǎn)時(shí)，出隊(duì)時(shí)還需修改尾指針 x=p->data; dispose(p); return(x) 第三章上機(jī)內(nèi)容1、設(shè)單鏈表中存放n 個(gè)字符,設(shè)計(jì)一個(gè)算法,使用棧判斷該字符

18、串是否中心對(duì)稱,如abccba即為中心對(duì)稱字符串. （根據(jù)題目填空完善程序）提示：先用create()函數(shù)從用戶輸入的字符串創(chuàng)建相應(yīng)的單鏈表，然后調(diào)用bj()函數(shù)判斷是否為中心對(duì)稱字符串。在 bj（）函數(shù)中先將字符串進(jìn)棧，然后將棧中的字符逐個(gè)與單鏈表中字符進(jìn)行比較。# include <stdio.h># include <malloc.h># define MaxLen 100typedef struct node char data；struct node *next；cnode；cnode *create (char s)int I=0；cnode *h, *p,

19、 *r；while (sI!=0)p=(cnode *)malloc(sizeof(cnode)；p->data=sI；p->next=NULL；if (I= =0)h=p；r=p ； /*r始終指向最后一個(gè)結(jié)點(diǎn)*/elser->next=p；r=p；I+；return h；int judge(cnode *h)char stMaxLen；int top=0；cnode *p=h；while (p!=NULL)sttop=p->data；top+；p=p->next；p=h；while (p!=NULL)top-；if (p->data= =sttop)p=

20、p->next；elsebreak；if (p= =NULL)return 1 ；elsereturn 0 ；void main()char strmaxlen；cnode *h；printf（“輸入一個(gè)字符串：”）；scanf（“%c”,str）；h=create( str )；if (judge(h)= = 1)printf( “ str是中心對(duì)稱字符串n”）；elseprintf（“str不是中心對(duì)稱字符串n”）；輸入一個(gè)字符串：abccba輸出： str是中心對(duì)稱字符串 2、設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括號(hào)、方括號(hào)和花括號(hào)三種類型的括號(hào)，編寫一個(gè)算法判斷其中的括號(hào)是否匹配。提示：本題

21、使用一個(gè)運(yùn)算符棧st，當(dāng)遇到的（、或時(shí)進(jìn)棧，當(dāng)遇到、）時(shí)判斷棧頂是否為相應(yīng)的括號(hào)，若是退棧繼續(xù)執(zhí)行；否則算法結(jié)束。解：#include "stdio.h"#include "string.h"#define NULL 0typedef struct list char str; struct list *next; list;void push(char,list *);int pop(char,list *);void deal(char *str);main (void) char str20; printf("nInput a suans

22、hi:n"); gets(str); deal(str); printf("Right!"); getch(); return 0;void deal(char *str) list *L; L=(list *) malloc (sizeof(list); if(!L) printf("Error!"); exit(-2); L->next=NULL; while(*str) if(*str='('|*str=''|*str='') push(*str,L); else if(*str=&#

23、39;)'|*str=''|*str='') if(pop(*str,L) puts("Error!Check it."); puts("Press Enter to exit."); getchar();exit(-2); str+; if(L->next) puts("Error!Check it."); puts("Press any key to exit."); getchar();exit(-2); void push(char c,list *L) lis

24、t *p; p=(list *) malloc (sizeof(list); if(!p) printf("Error!"); exit(-2); p->str=c; p->next=L->next; L->next=p;#define CHECK(s) if(L->next->str=s) p=L->next; L->next=p->next; free(p); return 0;int pop(char c,list *L) list *p; if(L->next=NULL) return 1; switch(

25、c) case ')':CHECK('(') break; case '':CHECK('') break; case '':CHECK('') break; return 1;3、設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過程?；疽螅阂宰址蛄械男问綇慕K端輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用教科書表3.1給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教科書的例3_1演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過程。測(cè)試數(shù)據(jù)：3*（7-2）解：#inclu

26、de "stdio.h"#include "string.h"#define NULL 0typedef struct listintinfor;struct list *next;list;intoperand(int d8,char *s);list*creat(void);list*creat(void);void push(list *,int);int pop(list *);intoperate(int,int,int);int check(int,int,int d8);main(void) int d88=-2,43,45,42,47,4

27、0,41,35, 43,1 ,1 ,-1,-1,-1,1 , 1, 45,1 ,1 ,-1,-1,-1,1 , 1, 42,1 ,1 , 1, 1,-1,1 , 1, 47,1 ,1 , 1, 1,-1,1 , 1, 40,-1,-1,-1,-1,-1,0 ,-2, 41, 1, 1, 1, 1,-2,1 , 1, 35,-1,-1,-1,-1,-1,-2, 0 ;char a20,*s=a;printf("nInput the expressionn");gets(s);while(*s!='0') s+;*s='#'printf(&quo

28、t;The result is %d.n",operand(d,a);getch();return 0;int operand(int d88,char *s) list *tr,*nd;int c,a,b,theta;tr=creat();nd=creat();push(tr,'#');c=*s+;while(c!='#'|tr->next->infor!='#')if(c>='0'&&c<='9') c=c-'0' push(nd,c); c=*s+; else switch(ch