的应用.docx
《的应用.docx》由会员分享，可在线阅读，更多相关《的应用.docx（8页珍藏版）》请在冰点文库上搜索。
的应用
1数制转换
用计算机实现计算时常常要将十进制数N转换成其他r进制数。
因为
N=（NDIVr）*r+NMODr（其中DIV是整除运算，MOD是取余运算）
所以可以用除以r取余的规则将Ｎ转换成r进制数。
例如（1537）10=（3001）8，其转换过
程如下。
N NDIV8 NMOD8
1537 192 1 低位
192 24 0
24 3 0
3 0 3 高位
例1 编写算法将一个非负十进制数N转换成八进制数，并打印输出。
注意到上例中的转换过程是先求出个位，再求出第二位，直至最高位。
而打印时恰好相
反,需要先打印最高位,最后才打印个位。
所以可设一栈，将运算的中间结果入栈，然后将栈
中所有数据出栈即可。
算法19实现了数制转换。
voidconversion（intn,intr）{//将十进制非负整数n转换成r（1 Stacks;inte;
StackInit（s,16）; //int类型的数占16比特,初始化s为空栈
while（n）{ //当n为非0时,
Push（s,n%r）;n=n/r;} //将余数（n除以r的余数）入栈,令n为（n除以r的）商
if（StackEmpty（s））cout<<0; //若原n的值为0,则只需输出0
else{ //不然,则表明原n>0,
while（!
StackEmpty（s））{ //将栈中各余数以逆序方式输出
Pop（s,e）;cout< }
}//conversion
算法19 数制转换算法
如果r>10，则应先构造一张对照表指明数值x用何符号表示。
例如，十六进制数A表
示十进制数中的10。
在conversion函数中定义对照表:
charconvtab[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}；
并将conversion函数中的
cout<即可将r的范围扩展到12后缀表达式求值
一个算术表达式有三种表示方法：
前缀（波兰）表示、中缀表示和后缀（逆波兰）表示。
我们习惯使用中缀表达式：
即算术表达式中的双目运算符出现在两个操作数中间，如a+b
表示a和b相加。
如果将运算符写在操作数之前,则称这种表达式为前缀表达式,如+ab也表
示a和b相加。
后缀表达式则是将运算符写在操作数之后,如ab+等价于中缀表达式a+b。
在
中缀表达中,由于运算符有优先级，有时为保持运算次序的正确性，就必须添加括号。
在前
缀和后缀表达式中，不需要引入括号，所有的计算按运算符出现的顺序，严格地从左到右进
行（无需考虑运算符的优先规则）。
例2 写出与中缀表达式P＝（a+b）*（c-d/e）-f*（g+h）等价的前缀表达式和后缀表达式，
然后指出它们的运算次序。
所谓等价的含义是指表达式的计算顺序和结果完全相同。
P的前缀表示为
q=-*+ab-c/de*f+gh
前缀表达式的计算规则是从左到右，如遇到一个二目运算符@就要在其后寻找两个操作
数。
如已有两个操作数x和y，则计算x@y，并将结果视作一个操作数T。
如@后无两个操
作数，则继续往右计算，直到计算出两个操作数x和y。
由此知q的运算次序如图3（a）所示。
P的后缀表示为
w=ab+cde/?
?
fgh+*-
后缀表达式的计算规则是从左到右，如果遇到的是二目运算符@，则将它前面的两个操
作数x和y进行@运算,即x@y。
其结果被视为一个操作数。
如遇到的是操作数,则继续往右,
直到出现一个运算符。
由此，w的计算次序如图3（b）所示。
中缀表达式P的计算次序如图3（c）所示。
由此可知P和其前缀表示q及后缀表示w是
等价的。
显然，计算一个后缀表达式要比计算一个等价的中缀表达式简单得多，因为不需要处理
括号，也不需要处理优先级。
而且比计算前缀表达式更容易实现，所以编译程序常常把中缀
表达式先转换成等价的后缀表达式，然后再对它求值。
例3 编写算法求后缀表达式的值。
为叙述方便，假定表达式是合法表达式，且每个操作数是一位非负整数，运算符限定为
双目运算符+、-、*和/。
表达式从键盘输入并以'#'结束。
算法21描述了简单表达式求值算法。
算法中设置一个栈s，初始时s为空栈，从左到
右扫描表达式，每遇到一个操作数就将其入栈保存，每遇到一个运算符就从栈中取出栈顶的
两个操作数进行计算，并将结果推入栈中，如此继续扫描,直到遇到边界符'#'，此时栈中只
有一个数，就是表达式的值。
intevaluate（）{//从键盘输入一个简单的合法的后缀表达式（以'#'结束）,求出它的值
Stacks;charch;intx,y;
StackInit（s,MAXSIZE）;//假设MAXSIZE是已定义的常量,例如,MAXSIZE=100
cin>>ch; //从键盘输入数据
while（ch!
='#'）{ //当表达式尚未结束时,
if（（ch>='0'）&&（ch<='9'））{ //如果输入的是操作数
x=ch-'0';Push（s,x）; //则将数字字符转换成整数,并入栈
}
else{ //不然,ch是一运算符
Pop（s,y）; //从栈中取出第二操作数
Pop（s,x）; //从栈中取出第一操作数
switch（ch）{ //根据运算符进行不同的运算,并将结果推入栈
case'+':
Push（s,x+y）;break;
case'-':
Push（s,x-y）;break;
case'*':
Push（s,x*y）;break;
case'/':
Push（s,x/y）;break;
default:
exit（ERROR）; //若出现非法运算符,则出错
}//switch
}//else
cin>>ch; //扫描下一个字符
}//while
Pop（s,x）; returnx; //取出在栈中的最终结果并返回表达式的值
}//evaluate
算法20 后缀表达式求值算法
/*========================================*/
/* 应用栈来走迷宫 */
/*========================================*/
#include
structstack_node /*栈的结构宣告 */
{
intx; /*路径座标x */
inty; /*路径座标y */
structstack_node*next; /*指向下一节点 */
};
typedefstructstack_nodestack_list;/*串列新型态 */
typedefstack_list*link; /*串列指标新型态 */
linkpath=NULL; /*路径栈指标 */
/*----------------------------------------*/
/* 栈资料的存入 */
/*----------------------------------------*/
linkpush（linkstack,intx,inty）
{
linknew_node; /*新节黠指标 */
/*配置节点记忆体*/
new_node=（link）malloc（sizeof（stack_list））;
if（!
new_node）
{
printf（"记忆体配置失败!
\n"）;
returnNULL; /*存入失败 */
}
new_node->x=x; /*存入路径座标x */
new_node->y=y; /*存入路径座标y */
new_node->next=stack; /*新节点指向原开始 */
stack=new_node; /*新节点成为栈开始*/
returnstack;
}
/*----------------------------------------*/
/* 栈资料的取出 */
/*----------------------------------------*/
linkpop（linkstack,int*x,int*y）
{
linktop; /*指向栈顶端 */
if（stack!
=NULL）
{
top=stack; /*指向栈顶端 */
stack=stack->next; /*栈指标指向下节点*/
*x=stack->x; /*取出路径座标x */
*y=stack->y; /*取出路径座标y */
free（top）; /*释回节点记忆体 */
returnstack; /*传回栈指标 */
}
else
*x=-1;
}
/*----------------------------------------*/
/* 主程式:
用回溯的方法在数组迷宫找出口. */
/* 数字0:
表示是可走的路 */
/* 数字1:
表示是墙壁,不可走的路 */
/* 数字2:
标示是走过的路 */
/* 数字3:
标表示是回溯的路 */
/*----------------------------------------*/
voidmain（）
{
intmaze[7][10]={ /*迷宫的数组 */
1,1,1,1,1,1,1,1,1,1,
1,0,1,0,1,0,0,0,0,1,
1,0,1,0,1,0,1,1,0,1,
1,0,1,0,1,1,1,0,0,1,
1,0,1,0,0,0,0,0,1,1,
1,0,0,0,1,1,1,0,0,1,
1,1,1,1,1,1,1,1,1,1};
inti,j;
intx=5; /*迷宫的入口座标 */
inty=8;
while（x!
=1||y!
=1） /*是否是迷宫出口 */
{
maze[x][y]=2; /*标示走过的路 */
if（maze[x-1][y]<=0） /*往上方走 */
{
x=x-1; /*座标x减一 */
path=push（path,x,y）; /*存入路径 */
}
else
if（maze[x+1][y]<=0）/*往下方走 */
{
x=x+1; /*座标x加一 */
path=push（path,x,y）; /*存入路径 */
}
else
if（maze[x][y-1]<=0） /*往左方走 */
{
y=y-1; /*座标y减一 */
path=push（path,x,y）; /*存入路径 */
}
else
if（maze[x][y+1]<=0） /*往右方走 */
{
y=y+1; /*座标y加一 */
path=push（path,x,y）;/*存入路径 */
}
else /*没有路可走:
回溯 */
{
maze[x][y]=3;/*表示回溯的路 */
path=pop（path,&x,&y）;/*退回一步 */
}
}
maze[x][y]=2; /*标示最后一点 */
printf（"迷宫的路径如下图所示:
\n"）;
for（i=1;i<6;i++） /*印出迷宫的图形 */
{
for（j=1;j<9;j++）
printf（"%d",maze[i][j]）;/*印出各座标 */
printf（"\n"）; /*换行 */
}
}
（End）
第1页 第2页 第3页 第4页 第5页 第6页 第7页 第8页 第9页
升级会员 