计算机考研：数据结构常用算法精析(3)

考研网

数据结构是计算机考研408计算机学科专业基础综合的重要组成部分，考生需要认真复习，尤其是对于数据结构中一些常用的算法问题，考生一定要弄懂弄会，理解的去掌握。新东方在线小编下面一一为大家分析一下，帮助考生更好地去掌握。
        第三章
    例如：Exp=a*b+(c-d/e)*f
    若 Exp=a*b+(c-d/e)*f 　则它的
    前缀式为： +*ab*-c/def
    中缀式为： a*b+c-d/e*f
    后缀式为： ab*cde/-fx+
    综合比较它们之间的关系可得下列结论：
    1.三式中的 “操作数之间的相对次序相同”;
    (二叉树的三种访问次序中，叶子的相对访问次序是相同的)
    2.三式中的 “运算符之间的的相对次序不同”;
    3.中缀式丢失了括弧信息，致使运算的次序不确定;
    (而前缀和后缀运算只需要一个存储操作数的栈，而中缀求值需要两个栈，符号栈和操
    作数栈)
    4.前缀式的运算规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;
    5.后缀式的运算规则为：
    ·运算符在式中出现的顺序恰为表达式的运算顺序;
    ·每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;
    6.中缀求值的运算规则：
    如果是操作数直接入栈。
    如果是运算符。这与当前栈顶比较。个如果比当前栈顶高，则入栈，如果低则说明当前栈顶是最高的必须把他先运算完了。用编译原理的话就是说当前栈顶已经是最左素短语了)
    其实中缀表达式直接求值和把中缀表达式转化成后缀表达式在求值的过程惊人的相似，只不过是直接求值是求出来，而转化成后缀是输出来。
    中缀表达式直接求值算法：
                    

kysix

    OPNDType EvalueExpression()
    { //OPTR 和OPND分别为运算符栈和操作数栈
    InitStack(OPTR);Push(OPTR,’#’);
    InitStack(OPND);c=getchar();
    While(c!=’#’|| GetTop(OPTR)!=’#’)
    {
    If(!IN(c,OP) ) //如果是操作数，直接入操作数栈
    { push(OPND,c);
    c=getchar();
    }
    Else //如果是运算符，则与当前的栈顶比较
    {
    Switch(Precede(GetTop(OPTR),c))
    {
    Case ‘’: //比当前栈顶低，则要把栈顶先运算完(先规约)
    pop(OPTR,theta); //把栈顶运算符弹出
    Pop(OPND,b); //取出操作数，并且是前操作数
    Pop(OPND,a); //在下面(栈的先进后出)
    Push(OPND,Operate(a,theta,b)); //运算的结果入栈
    //(他是其他运算符的操作数)
    Break;
    }//Switch
    }//else
    }//whild
    Return GetTop(OPND);//操作数栈中最后剩下的就是整个表达式的结果了。
    }
                    

kyfour

    中缀表达式转化成后缀表达式算法
    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在栈中
                    

kytwo

    而Pi是最先出栈的那么在Pi为栈顶的时候，Pj和Pk一定都同时被压入栈中，那么就与1矛盾了，1要求Pj要在Pk入栈前出栈，而此时Pk
Pj都在栈中所以假设不成立。
    用两个栈来模拟一个队列
    栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列
    时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1
    退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队
    列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空，才算是队列空。
    第3章节有关数据结构算法，上文中为大家作了分析，希望考生对于这些算法能够熟记于心，方便考试的应用和日后的实际操作，预祝大家都能够取得好成绩，加油!