5. 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如?序列1 & 序列2?模式的字符序列。其中序列1和序列2 中都不含字符?&?，且序列2 是序列1的逆序列。例如，?a+b&b+a?是属该模式的字符序列，而?１+３&３－１?则不是。 [提示]：
（1） 边读边入栈，直到&
（2） 边读边出栈边比较，直到……
int IsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0 {
InitStack(s);
while((e=getchar())!='&') push(s,e);
while((e=getchar())!='@') {
if(StackEmpty(s)) return 0; pop(s,c);
if(e!=c) return 0; }
if(!StackEmpty(s)) return 0; return 1; }//IsReverse
6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。
void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new {
p=str;q=new; //为方便起见,设str的两端都加上了优先级最低的特殊符号 InitStack(s); //s为运算符栈 while(*p) {
if(*p是字母)) *q++=*p; //直接输出 else {
c=gettop(s);
if(*p优先级比c高) push(s,*p); else {
while(gettop(s)优先级不比*p低) {
pop(s,c);*(q++)=c; }//while
push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则 }//else
}//else p++; }//while
}//NiBoLan //参见编译原理教材
7. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。 void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q {
Q=(CiLNode*)malloc(sizeof(CiLNode)); Q->next=Q; }//InitCiQueue
void EnCiQueue(CiQueue &Q,int x)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素 {
p=(CiLNode*)malloc(sizeof(CiLNode)); p->data=x;
p->next=Q->next; //直接把p加在Q的后面 Q->next=p;
Q=p; //修改尾指针 }
Status DeCiQueue(CiQueue &Q,int x)//从循环链表表示的队列Q头部删除元素x {
if(Q==Q->next) return INFEASIBLE; //队列已空 p=Q->next->next; x=p->data;
Q->next->next=p->next; free(p); return OK; }//DeCiQueue
8. 要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 [提示]：
初始状态：front==0, rear==0, tag==0 队空条件：front==rear, tag==0 队满条件：front==rear, tag==1
其它状态：front !=rear, tag==0（或1、2）
入队操作： …
…（入队）
if (front==rear) tag=1；（或直接tag=1）
出队操作：
…
…（出队） tag=0；
[问题]：如何明确区分队空、队满、非空非满三种情况？
9. 简述以下算法的功能（其中栈和队列的元素类型均为int）： （1）void proc_1(Stack S) { int i, n, A[255]; n=0;
while(!EmptyStack(S))
{n++; Pop(&S, &A[n]);} for(i=1; i<=n; i++) Push(&S, A[i]); }
将栈S逆序。
（2）void proc_2(Stack S, int e) { Stack T; int d; InitStack(&T);
while(!EmptyStack(S)) { Pop(&S, &d);
if (d!=e) Push( &T, d); }
while(!EmptyStack(T)) { Pop(&T, &d); Push( &S, d); } }
删除栈S中所有等于e的元素。 （3）void proc_3(Queue *Q) { Stack S; int d; InitStack(&S);
while(!EmptyQueue(*Q)) {
DeleteQueue(Q, &d); Push( &S, d); }
while(!EmptyStack(S)) { Pop(&S, &d); EnterQueue(Q，d) } }
将队列Q逆序。 第四章 串
1. 设s=?I AM A STUDENT?, t=?GOOD?, q=?WORKER?。给出下列操作的结果： StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,?A?,4); StrReplace(s,?STUDENT?,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); [参考答案]
StrLength(s)=14;
SubString(sub1,s,1,7) sub1=?I AM A ?; SubString(sub2,s,7,1) sub2=? ?; StrIndex(s,4,?A?)=6;
StrReplace(s,?STUDENT?,q); s=?I AM A WORKER?;
StrCat(StrCat(sub1,t),StrCat(sub2,q)) sub1=?I AM A GOOD WORKER?。
2. 编写算法，实现串的基本操作StrReplace(S,T,V)。 StrCat(S,T)； SubString(Sub,S,pos,len)。
int String_Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数 {
for(n=0,i=1;i<=S[0]-T[0]+1;i++) {
for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++);
if(k>T[0]) //找到了与T匹配的子串:分三种情况处理 {
if(T[0]==V[0])
for(l=1;l<=T[0];l++) //新子串长度与原子串相同时:直接替换 S[i+l-1]=V[l];
else if(T[0] for(l=S[0];l>=i+T[0];l--) S[l+V[0]-T[0]]=S[l]; for(l=1;l<=V[0];l++) S[i+l-1]=V[l]; } else //新子串长度小于原子串时:先将后部左移 { for(l=i+V[0];l<=S[0]+V[0]-T[0];l++) S[l]=S[l-V[0]+T[0]]; for(l=1;l<=V[0];l++) S[i+l-1]=V[l]; } S[0]=S[0]-T[0]+V[0]; i+=V[0];n++; }//if }//for return n;