📄 xtjd3.htm
字号:
EnQueue(Qx,x);EnQueue(Qy,y+1);
//修改下邻点的颜色<br>
}<br>
}//while<br>
}//Repaint_Color<br>
分析:本算法采用了类似于图的广度优先遍历的思想,用两个队列保存相邻同色点的横坐标和纵坐标.递归形式的算法该怎么写呢?
<p>3.21
<p>void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new<br>
{<br>
p=str;q=new; //为方便起见,设str的两端都加上了优先级最低的特殊符号<br>
InitStack(s); //s为运算符栈<br>
while(*p)<br>
{<br>
if(*p是字母)) *q++=*p; //直接输出<br>
else<br>
{<br>
c=gettop(s);<br>
if(*p优先级比c高) push(s,*p);<br>
else<br>
{<br>
while(gettop(s)优先级不比*p低)<br>
{<br>
pop(s,c);*(q++)=c;<br>
}//while<br>
push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则<br>
}//else<br>
}//else<br>
p++;<br>
}//while<br>
}//NiBoLan //参见编译原理教材
<p>3.22
<p>int GetValue_NiBoLan(char *str)//对逆波兰式求值<br>
{<br>
p=str;InitStack(s); //s为操作数栈<br>
while(*p)<br>
{<br>
if(*p是数) push(s,*p);<br>
else<br>
{<br>
pop(s,a);pop(s,b);<br>
r=compute(b,*p,a); //假设compute为执行双目运算的过程<br>
push(s,r);<br>
}//else<br>
p++;<br>
}//while<br>
pop(s,r);return r;<br>
}//GetValue_NiBoLan
<p>3.23
<p>Status NiBoLan_to_BoLan(char *str,stringtype &new)//把逆波兰表达式str转换为波兰式new<br>
{<br>
p=str;Initstack(s); //s的元素为stringtype类型<br>
while(*p)<br>
{<br>
if(*p为字母) push(s,*p);<br>
else<br>
{<br>
if(StackEmpty(s)) return ERROR;<br>
pop(s,a);<br>
if(StackEmpty(s)) return ERROR;<br>
pop(s,b);<br>
c=link(link(*p,b),a);<br>
push(s,c);<br>
}//else<br>
p++;<br>
}//while<br>
pop(s,new);<br>
if(!StackEmpty(s)) return ERROR;<br>
return OK;<br>
}//NiBoLan_to_BoLan<br>
分析:基本思想见书后注释.本题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b).
<p>3.24
<p>Status g(int m,int n,int &s)//求递归函数g的值s<br>
{<br>
if(m==0&&n>=0) s=0;<br>
else if(m>0&&n>=0) s=n+g(m-1,2*n);<br>
else return ERROR;<br>
return OK;<br>
}//g
<p>3.25
<p>Status F_recurve(int n,int &s)//递归算法<br>
{<br>
if(n<0) return ERROR;<br>
if(n==0) s=n+1;<br>
else<br>
{<br>
F_recurve(n/2,r);<br>
s=n*r;<br>
}<br>
return OK;<br>
}//F_recurve
<p>Status F_notrecurve(int n,int s)//非递归算法<br>
{<br>
if(n<0) return ERROR;<br>
if(n==0) s=n+1;<br>
else<br>
{<br>
InitStack(s); //s的元素类型为struct {int a;int b;}<br>
while(n!=0)<br>
{<br>
a=n;b=n/2;<br>
push(s,{a,b});<br>
n=b;<br>
}//while<br>
s=1;<br>
while(!StackEmpty(s))<br>
{<br>
pop(s,t);<br>
s*=t.a;<br>
}//while<br>
}<br>
return OK;<br>
}//F_notrecurve
<p>3.26
<p>float sqrt_recurve(float A,float p,float e)//求平方根的递归算法<br>
{<br>
if(abs(p^2-A)<=e) return p;<br>
else return sqrt_recurve(A,(p+A/p)/2,e);<br>
}//sqrt_recurve
<p>float sqrt_notrecurve(float A,float p,float e)//求平方根的非递归算法<br>
{<br>
while(abs(p^2-A)>=e)<br>
p=(p+A/p)/2;<br>
return p;<br>
}//sqrt_notrecurve
<p>3.27
<p>这一题的所有算法以及栈的变化过程请参见《数据结构(pascal版)》,作者不再详细写出.
<p>3.28
<p>void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q<br>
{<br>
Q=(CiLNode*)malloc(sizeof(CiLNode));<br>
Q->next=Q;<br>
}//InitCiQueue
<p>void EnCiQueue(CiQueue &Q,int x)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素<br>
{<br>
p=(CiLNode*)malloc(sizeof(CiLNode));<br>
p->data=x;<br>
p->next=Q->next; //直接把p加在Q的后面<br>
Q->next=p;<br>
Q=p; //修改尾指针<br>
}
<p>Status DeCiQueue(CiQueue &Q,int x)//从循环链表表示的队列Q头部删除元素x<br>
{<br>
if(Q==Q->next) return INFEASIBLE; //队列已空<br>
p=Q->next->next;<br>
x=p->data;<br>
Q->next->next=p->next;<br>
free(p);<br>
return OK;<br>
}//DeCiQueue
<p>3.29
<p>Status EnCyQueue(CyQueue &Q,int x)//带tag域的循环队列入队算法<br>
{<br>
if(Q.front==Q.rear&&Q.tag==1) //tag域的值为0表示"空",1表示"满"<br>
return OVERFLOW;<br>
Q.base[Q.rear]=x;<br>
Q.rear=(Q.rear+1)%MAXSIZE;<br>
if(Q.front==Q.rear) Q.tag=1; //队列满<br>
}//EnCyQueue
<p>Status DeCyQueue(CyQueue &Q,int &x)//带tag域的循环队列出队算法<br>
{<br>
if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE;<br>
Q.front=(Q.front+1)%MAXSIZE;<br>
x=Q.base[Q.front];<br>
if(Q.front==Q.rear) Q.tag=1; //队列空<br>
return OK;<br>
}//DeCyQueue<br>
分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.
<p>3.30
<p>Status EnCyQueue(CyQueue &Q,int x)//带length域的循环队列入队算法<br>
{<br>
if(Q.length==MAXSIZE) return OVERFLOW;<br>
Q.rear=(Q.rear+1)%MAXSIZE;<br>
Q.base[Q.rear]=x;<br>
Q.length++;<br>
return OK;<br>
}//EnCyQueue
<p>Status DeCyQueue(CyQueue &Q,int &x)//带length域的循环队列出队算法<br>
{<br>
if(Q.length==0) return INFEASIBLE;<br>
head=(Q.rear-Q.length+1)%MAXSIZE; //详见书后注释<br>
x=Q.base[head];<br>
Q.length--;<br>
}//DeCyQueue
<p>3.31
<p>int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0<br>
{<br>
InitStack(S);InitQueue(Q);<br>
while((c=getchar()!='@')<br>
{<br>
Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构<br>
}<br>
while(!StackEmpty(S))<br>
{<br>
Pop(S,a);DeQueue(Q,b));<br>
if(a!=b) return ERROR;<br>
}<br>
return OK;<br>
}//Palindrome_Test
<p>3.32
<p>void GetFib_CyQueue(int k,int n)//求k阶斐波那契序列的前n+1项<br>
{<br>
InitCyQueue(Q); //其MAXSIZE设置为k<br>
for(i=0;i<k-1;i++) Q.base[i]=0;<br>
Q.base[k-1]=1; //给前k项赋初值<br>
for(i=0;i<k;i++) printf("%d",Q.base[i]);<br>
for(i=k;i<=n;i++)<br>
{<br>
m=i%k;sum=0;<br>
for(j=0;j<k;j++) sum+=Q.base[(m+j)%k];<br>
Q.base[m]=sum; //求第i项的值存入队列中并取代已无用的第一项<br>
printf("%d",sum);<br>
}<br>
}//GetFib_CyQueue
<p>3.33
<p>Status EnDQueue(DQueue &Q,int x)//输出受限的双端队列的入队操作<br>
{<br>
if((Q.rear+1)%MAXSIZE==Q.front) return OVERFLOW; //队列满<br>
avr=(Q.base[Q.rear-1]+Q.base[Q.front])/2;<br>
if(x>=avr) //根据x的值决定插入在队头还是队尾<br>
{<br>
Q.base[Q.rear]=x;<br>
Q.rear=(Q.rear+1)%MAXSIZE;<br>
} //插入在队尾<br>
else<br>
{<br>
Q.front=(Q.front-1)%MAXSIZE;<br>
Q.base[Q.front]=x;<br>
} //插入在队头<br>
return OK;<br>
}//EnDQueue
<p>Status DeDQueue(DQueue &Q,int &x)//输出受限的双端队列的出队操作<br>
{<br>
if(Q.front==Q.rear) return INFEASIBLE; //队列空<br>
x=Q.base[Q.front];<br>
Q.front=(Q.front+1)%MAXSIZE;<br>
return OK;<br>
}//DeDQueue
<p>3.34
<p>void Train_rearrange(char *train)//这里用字符串train表示火车,'P'表示硬座,'H'表示硬卧,'S'表示软卧,最终按PSH的顺序排列<br>
{<br>
r=train;<br>
InitDQueue(Q);<br>
while(*r)<br>
{<br>
if(*r=='P')<br>
{<br>
printf("E");<br>
printf("D"); //实际上等于不入队列,直接输出P车厢<br>
}<br>
else if(*r=='S')<br>
{<br>
printf("E");<br>
EnDQueue(Q,*r,0); //0表示把S车厢从头端入队列<br>
}<br>
else<br>
{<br>
printf("A");<br>
EnDQueue(Q,*r,1); //1表示把H车厢从尾端入队列<br>
}<br>
}//while<br>
while(!DQueueEmpty(Q))<br>
{<br>
printf("D");<br>
DeDQueue(Q);<br>
}//while //从头端出队列的车厢必然是先S后H的顺序<br>
}//Train_rearrange</p>
<P align=left
style="LINE-HEIGHT: 150%; MARGIN-BOTTOM: 0px; MARGIN-TOP: 0px"> </P>
<HR>
<P align=left><B><SPAN
style="COLOR: blue; FONT-FAMILY: 宋体; FONT-SIZE: 24pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">数据结构辅导站</SPAN><SPAN
lang=EN-US
style="COLOR: blue; FONT-FAMILY: Times New Roman; FONT-SIZE: 24pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-spacerun: yes; mso-fareast-font-family: 宋体">
</SPAN></B><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:12.0pt;font-family:宋体;
mso-bidi-font-family:"Times New Roman";mso-font-kerning:1.0pt;mso-ansi-language:
EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"><a href="index.htm">返回主页</a></span></P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -