习题三和上机答案.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
Pusha), 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 40
　typedef struct sqstack
　{ DataType data[sqstack_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->data[sq->top]=x; return(1);}
　}

　int Pop(SqStackTp *sq,DataType *x)
　{
　　if (sq->top==0){ printf("下溢"); return(0);}
　　else { *x=sq->data[sq->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';ch<='A'+12;ch++)
　　{ Push(&sq,ch); printf("%c",ch);}
　　printf("\n");
　　while(!EmptyStack(&sq))
　　{ Pop(&sq,&ch);printf("%c",ch); } 
　　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; 
　　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';ch<='A'+12;ch++)
　　{ Push(&ls,ch); printf("%c",ls->data);}
　　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);
else
return(s.elem[s.top]);
}

进栈操作
void push_sqstack(sqstacktp s，elemtp x){
若栈s未满，将元素x压入栈中；否则，栈的状态不变并给出出错信息
if(s.top==maxsize)
printf(“Overflow”);
else{
s.top++; 栈顶指针加1
s.elem[s.top]=x x进栈
}
}

出栈函数
elemtp pop_sqstack(sqstacktp s){
若栈s不空，则删去栈顶元素并返回元素值，否则返回空元素NULL
if(s.top==0)
return(null);
else{
s.top--; 栈顶指针减1
teturn(s.elem[s.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.elem[cq.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.elem[cq.front]);
}
}

⒊6 假设以带头结点的环形链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的初始化队列、入队列、出队列的算法。
解：
初始化：
void initlqueue( 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:=s
ENDP; 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 100
typedef struct node
{
char data；
struct node *next；
}cnode；
cnode *create (char s[])
{
int I=0；
cnode *h, *p, *r；
while (s[I]!=’\0’)
{
p=(cnode *)malloc(sizeof(cnode))；
p->data=s[I]；p->next=NULL；
if (I= =0)
{
h=p；
r=p ； /*r始终指向最后一个结点*/
}
else
{
r->next=p；r=p；
}
I++；
}
return h；
}

int judge(cnode *h)
{
char st[MaxLen]；
int top=0；
cnode *p=h；
while (p!=NULL)
{
st[top]=p->data；
top++；
p=p->next；
}
p=h；
while (p!=NULL)
{
top--；
if (p->data= =st[top])
p=p->next；
else
break；
}
if (p= =NULL)
return 1 ；
else
return 0 ；
}

void main()
{
char str[maxlen]；
cnode *h；
printf（“输入一个字符串：”）；
scanf（“%c”,str）；
h=create( str )；
if (judge(h)= = 1)
printf( “ str是中心对称字符串\n”）；
else
printf（“str不是中心对称字符串\n”）；
}
输入一个字符串：abccba
输出： str是中心对称字符串

2、设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个算法判断其中的括号是否匹配。
提示：本题使用一个运算符栈st，当遇到的‘（’、‘[’、或‘{’时进栈，当遇到‘}’、‘]’、‘）’时判断栈顶是否为相应的括号，若是退栈继续执行；否则算法结束。
解：
#include "stdio.h"
#include "string.h"
#define NULL 0
typedef struct list
{ char str;
struct list *next;
} list;

void push(char,list *);
int pop(char,list *);
void deal(char *str);

main (void)
{ char str[20];
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 0

typedef struct list{
int infor;
struct list *next;
}list;

int operand(int d[][8],char *s);
list *creat(void);
list *creat(void);
void push(list *,int);
int pop(list *);
int operate(int,int,int);
int check(int,int,int d[][8]);

main(void)
{ int d[8][8]={-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 a[20],*s=a;
printf("\nInput the expression\n");
gets(s);
while(*s!='\0') s++;
*s='#';
printf("The result is %d.\n",operand(d,a));
getch();
return 0;
}

int operand(int d[8][8],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(check(tr->next->infor,c,d))
{ case -1: push(tr,c); c=*s++; break;
case 0 : pop(tr);c=*s++; break;
case 1 : theta=pop(tr);
b=pop(nd);
a=pop(nd);
push(nd,operate(a,b,theta));
break;
}
}
return nd->next->infor;
}

list *creat(void)
{ list *p;
p=(list *) malloc (sizeof(list));
if(!p) exit(-2);
p->next=NULL;
return p;
}
void push(list *L,int c)
{ list *p;
p=(list *) malloc (sizeof(list));
if(!p) exit(-2);
p->infor=c;
p->next=L->next;L->next=p;
}
int pop(list *L)
{ list *p;
int c;
p=L->next;
c=p->infor;
L->next=p->next;
free(p);
return c;
}
int operate(int a,int b,int theta)
{ int result;
switch(theta)
{ case '+': result=a+b;break;
case '-': result=a-b;break;
case '*': result=a*b;break;
case '/': result=a/b;break;
}
return result;
}
int check(int top,int c,int d[8][8])
{ int i,j;
for(i=1;i<8;i++)
{ if(top==d[i][0])
for(j=1;j<8;j++)
if(c==d[0][j])
if(d[i][j]!=-2) return d[i][j];
else { printf("Error!"); getchar(); exit(0); }
}
}