数据结构——C语言描述课后答案

5. 试写一个算法,判断依次读入的一个以@为结束符的字母序列,是否为形如?序列1 & 序列2?模式的字符序列。其中序列1和序列2 中都不含字符?&?,且序列2 是序列1的逆序列。例如,?a+b&b+a?是属该模式的字符序列,而?1+3&3-1?则不是。 [提示]:

(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;

联系客服:779662525#qq.com(#替换为@)