习题三和上机答案.doc

习题三3.1设将整数a，b，c，d依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若执行以下操作序列Push(a), Pop(),Push(b),Push(c), Pop(), Pop( ),Push(d), Pop( ),则出 栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?(2) 能否得到出栈序列adbc和adcb并说明为什么不能得到或者如何得到。(3)请分析 a，b ，c ，d 的所有排列中，哪些序列是可以通过相应的入出栈操作得到的。解：（1）acbd （2）执行以下操作序列Push(a), Pop(),Push(b),Push(c), Push(d),Pop(), Pop( ), Pop( )就可以得到adcb 栈的特点是“后进先出”，所以不可能得到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 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), Pop(),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(SqStackTp *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(SqStackTp *sq)if (sq-top=0)return(1);else return(0);/*主函数*/void main() SqStackTp sq;DataType ch;InitStack(&sq);for (ch=A;chdata=x;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;chdata);printf(n);while(!EmptyStack(ls) Pop(&ls,&ch);printf(%c,ch); printf(n); 有两个栈A，B这两个栈中分别存储这一个升序数列，现要求编写算法把这两个栈中的数合成一个升序队列解：link merge(link a,link b) link h,s,m,n,t; h=(cnode *)malloc(sizeof(cnode); h-next=NULL; s=h; m=a; n=b; while(m-next&n-next) if(m-next-datanext-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; 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-next=s-next; s-next=t; s=t; free(m); free(n); return h;4 设两个栈共享一个数组空间，其类型定义见节，试写出两个栈公用的读栈顶元算法elemtp top_dustack(dustacktp ds,p;int i)；进栈操作算法void push_dustack(dustacktp ds,p;int i , elemtp x)；及出栈算法 elemtp pop_ dustack(dustacktp ds,p;int i )。其中i的取值是1或2，用以指示栈号。解：读栈顶元函数 elemtp top_sqstack(s:sqstacktp) if( s.top=0) return(null); elsereturn(s.elems.top); 进栈操作 void push_sqstack(sqstacktp s，elemtp x) 若栈s未满，将元素x压入栈中；否则，栈的状态不变并给出出错信息 if(s.top=maxsize) printf(“Overflow”); else s.top+; 栈顶指针加1 s.elems.top=x x进栈 出栈函数 elemtp pop_sqstack(sqstacktp s) 若栈s不空，则删去栈顶元素并返回元素值，否则返回空元素NULL if(s.top=0) return(null); else s.top-; 栈顶指针减1 teturn(s.elems.top+1); 返回原栈顶元素值 5假设以数组sequ(0.m-1)存放循环队列元素，同时设变量rear和quelen分别指示循环队列中队尾元素和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。解：队满的条件 (sq.rear+1) MOD maxsize=sq.front 入队列操作 void en_cqueue(cqueuetp cq,elemtp x) 若循环队列cq未满，插入x为新的队尾元素；否则队列状态不变并给出错误信息 if (cq.rear+1) MOD maxsize=cq.front) printf(“Overflow”); else cq.rear=(cq.rear+1) MOD maxsize; cq.elemcq.rear=x 出队列函数 elemtp dl_cqueue(VAR cq:cqueuetp) 若循环队列cq不空，则删去队头元素并返回元素值；否则返回空元素NULL if( cq.front=cq.rear) return(NULL); else cq.front=(cq.front+1) MOD maxsize; return(cq.elemcq.front); 6 假设以带头结点的环形链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的初始化队列、入队列、出队列的算法。解：初始化： void init_lqueue( lqueuetp lq) 设置一个空的链队列lq new(lq.front); lq.front-next:=NIL; lq.rear=lq.front; 入队列操作： PROC en_lqueue(VAR lq:lqueuetp;x:elemtp); 在链队列lq中，插入x为新的队尾元素 BEGIN new(s); s.data:=x; s.next:=NIL; lq.rear.next:=s; lq.rear:=sENDP; en_lqueue出队列操作： elemtp dl_lqueue(lqueuetp lq) 若链队列lq不空，则删去队头元素并返回元素值；否则返回空元素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; 当链队列中仅有一个结点时，出队时还需修改尾指针 x=p-data; dispose(p); return(x) 第三章上机内容1、设单链表中存放n 个字符,设计一个算法,使用栈判断该字符串是否中心对称,如abccba即为中心对称字符串. （根据题目填空完善程序）提示：先用create()函数从用户输入的字符串创建相应的单链表，然后调用bj()函数判断是否为中心对称字符串。在 bj（）函数中先将字符串进栈，然后将栈中的字符逐个与单链表中字符进行比较。# include # include # define MaxLen 100typedef struct node char data；struct node *next；cnode；cnode *create (char s)int I=0；cnode *h, *p, *r；while (sI!=0)p=(cnode *)malloc(sizeof(cnode)；p-data=sI；p-next=NULL；if (I= =0)h=p；r=p ； /*r始终指向最后一个结点*/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=p-next；elsebreak；if (p= =NULL)return 1 ；elsereturn 0 ；void main()char strmaxlen；cnode *h；printf（“输入一个字符串：”）；scanf（“%c”,str）；h=create( str )；if (judge(h)= = 1)printf( “ str是中心对称字符串n”）；elseprintf（“str不是中心对称字符串n”）；输入一个字符串：abccba输出： str是中心对称字符串 2、设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个算法判断其中的括号是否匹配。提示：本题使用一个运算符栈st，当遇到的（、或时进栈，当遇到、）时判断栈顶是否为相应的括号，若是退栈继续执行；否则算法结束。解：#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 suanshi: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=)|*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) list *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(c) case ):CHECK() break; case :CHECK() break; case :CHECK() break; return 1;3、设计一个程序，演示用算符优先法对算术表达式求值的过程。基本要求：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例3_1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。测试数据：3*（7-2）解：#include 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,40,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(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&cnext-infor,c,d) case -1: