数据结构严蔚敏习题册 答案

{

if(abs(p^2-A)<=e) return p;

else return sqrt_recurve(A,(p+A/p)/2,e); }//Sqrt_recurve

float Sqrt_nonrecursive(float A,float p,float e)//求平方根的非递归算法 {

while(abs(p^2-A)>=e) p=(p+A/p)/2; return p;

}//Sqrt_nonrecursive 3.27

这一题的所有算法以及栈的变化过程请参见《数据结构(pascal版)》,作者不再详细写出. 3.28

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 3.29

Status EnCyQueue(CyQueue &Q,int x)//带tag域的循环队列入队算法 {

if(Q.front==Q.rear&&Q.tag==1) //tag域的值为0表示\空\表示\满\ return OVERFLOW; Q.base[Q.rear]=x;

Q.rear=(Q.rear+1)%MAXSIZE;

if(Q.front==Q.rear) Q.tag=1; //队列满 }//EnCyQueue

Status DeCyQueue(CyQueue &Q,int &x)//带tag域的循环队列出队算法 {

if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE; Q.front=(Q.front+1)%MAXSIZE; x=Q.base[Q.front];

if(Q.front==Q.rear) Q.tag=1; //队列空 return OK; }//DeCyQueue

分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.

3.30

Status EnCyQueue(CyQueue &Q,int x)//带length域的循环队列入队算法 {

if(Q.length==MAXSIZE) return OVERFLOW; Q.rear=(Q.rear+1)%MAXSIZE; Q.base[Q.rear]=x; Q.length++; return OK; }//EnCyQueue

Status DeCyQueue(CyQueue &Q,int &x)//带length域的循环队列出队算法 {

if(Q.length==0) return INFEASIBLE;

head=(Q.rear-Q.length+1)%MAXSIZE; //详见书后注释 x=Q.base[head]; Q.length--; }//DeCyQueue 3.31

int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0 {

InitStack(S);InitQueue(Q); while((c=getchar())!='@') {

Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构 }

while(!StackEmpty(S)) {

Pop(S,a);DeQueue(Q,b)); if(a!=b) return ERROR; }

return OK;

}//Palindrome_Test 3.32

void GetFib_CyQueue(int k,int n)//求k阶斐波那契序列的前n+1项 {

InitCyQueue(Q); //其MAXSIZE设置为k for(i=0;i

for(i=0;i

m=i%k;sum=0;

for(j=0;j

Q.base[m]=sum; //求第i项的值存入队列中并取代已无用的第一项 printf(\ }

}//GetFib_CyQueue 3.33

Status EnDQueue(DQueue &Q,int x)//输出受限的双端队列的入队操作 {

if((Q.rear+1)%MAXSIZE==Q.front) return OVERFLOW; //队列满 avr=(Q.base[Q.rear-1]+Q.base[Q.front])/2;

if(x>=avr) //根据x的值决定插入在队头还是队尾 {

Q.base[Q.rear]=x;

Q.rear=(Q.rear+1)%MAXSIZE; } //插入在队尾

else {

Q.front=(Q.front-1)%MAXSIZE; Q.base[Q.front]=x; } //插入在队头 return OK; }//EnDQueue

Status DeDQueue(DQueue &Q,int &x)//输出受限的双端队列的出队操作 {

if(Q.front==Q.rear) return INFEASIBLE; //队列空 x=Q.base[Q.front];

Q.front=(Q.front+1)%MAXSIZE; return OK; }//DeDQueue 3.34

void Train_Rearrange(char *train)//这里用字符串train表示火车,'P'表示硬座,'H'表示硬卧,'S'表示软卧,最终按PSH的顺序排列 {

r=train;

InitDQueue(Q); while(*r) {

if(*r=='P') {

printf(\

printf(\实际上等于不入队列,直接输出P车厢 }

else if(*r=='S') {

printf(\

EnDQueue(Q,*r,0); //0表示把S车厢从头端入队列 } else {

printf(\

EnDQueue(Q,*r,1); //1表示把H车厢从尾端入队列 } }//while

while(!DQueueEmpty(Q)) {

printf(\ DeDQueue(Q);

}//while //从头端出队列的车厢必然是先S后H的顺序 }//Train_Rearrange 第四章 串

4.10

void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r {

StrAssign(r,''); //初始化r为空串 for(i=Strlen(s);i;i--) {

StrAssign(c,SubString(s,i,1));

StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中 }

}//String_Reverse

4.11

void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r {

StrAssign(r,'');

for(i=1;i<=Strlen(s);i++) {

StrAssign(c,SubString(s,i,1));

for(j=1;j

for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中

if(k>Strlen(t)) StrAssign(r,Concat(r,c)); } }//for

}//String_Subtract 4.12

int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数 {

for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围

if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串 { //分别把T的前面和后面部分保存为head和tail StrAssign(head,SubString(S,1,i-1));

StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1)); StrAssign(S,Concat(head,V));

StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串 i+=Strlen(V); //当前指针跳到插入串以后 n++; }//if return n; }//Replace

分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果? 4.13

int Delete_SubString(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数 {

for(n=0,i=1;i<=Strlen(s)-Strlen(t)+1;i++) if(!StrCompare(SubString(s,i,Strlen(t)),t)) {

StrAssign(head,SubString(S,1,i-1));

StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1)); StrAssign(S,Concat(head,tail)); //把head,tail连接为新串 n++; }//if return n,

}//Delete_SubString 4.14

Status NiBoLan_to_BoLan(Stringtype str,Stringtype &new)//把前缀表达式str转换为后缀式new {

Initstack(s); //s的元素为Stringtype类型