|
发表于 2017-8-6 15:43:12
|
显示全部楼层
中缀表达式转化成后缀表达式算法
void trans-post(char E[n] ,char B[n]) //中、后缀表达式转换//
{ //E[n]是中缀表达式、B[n]是后缀表达式存储的空间
int i=0,j=0; char x; stype S;
Clearstack(S); Push(S,‘#’);//‘#’入栈//
do {
x=E[i++] ; //扫描当前表达式分量//
if (x=‘#’) //到了中缀表达式最后了
while(!Emptystack(S)) //全部退栈,#和#是优先级最低的,
B[j++]==pop(S); //所以当前栈的所有运算都要规约
//输出栈顶运算符,并退栈直到遇见栈底的开始放进去的那个#//
else if (isdigit(x))
B[j++]=x; //操作数直接输出//
else if (x=‘)’) //遇到)那么就一定要找到(
{
while (Getstop(S)!=‘(’)
B[j++]=pop(S); //输出栈顶,并退栈//
pop(S); //退掉‘(’//
}
else //x为运算符//
{
while (precede(Getstop(S), x)) //栈顶( q1)与x比较//
B[j++]=pop(S); // q1 >=x时,输出栈顶符并退栈//
Push(S,x); // q1 双端队列:
两端都可以插入和删除,但实际应用中通常是输出受限的双端对列和输入受限的双端队列
输入受限的双端队列指的是:一端可以输入输出另一端只能输出不能输入
输出受限的双端队列指的是:一端可以输入输出另一端只能输入不能输出
求从迷宫入口到出口的一条最短路径
要用到队列,因为队列可以用在广度优先中,队列中的元素表示离中心点依次越来越远。
所以第一次找到出口肯定是半径最短的。
链式栈:
a0
^
a1
top ……
An
链式队列:
front
rear
q
头
a0
an-1
^
N个结点的不同二叉树有: 等于不同的进出栈总数
有n个数顺序(依次)进栈,出栈序列有Cn种,Cn=[1/(n+1)]*(2n)!/[(n!)*(n!)]。=
尾递归和单向递归的消除不需要借用栈
单向递归和尾递归可直接用迭代实现其非递归过程
其他情形必须借助栈实现非递归过程。
证明:若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着i
i
若Pi>Pj 说明大的数先于小的数出栈,那么在Pi出栈前Pj一定在栈中
证明:1)j
2)iPk 说明Pi出栈前,Pk在栈中
3)iPj 说明Pi出栈前Pj在栈中
|
|