7-27

发表于 更新于 阅读次数：

堆栈

堆栈在递归中的应用

并非所有高级程序设计语言都提供了递归功能。
一个递归过程可以通过设置堆栈结构转化为非递归过程。
递归分为：直接递归（调用自己）和间接递归（通过调用别的函数来调用自己）
递归不节省时间和空间，但是能让程序紧凑、结构清晰、便于阅读

对于程序：

1
2
3
4
5
6
int F(int m,int n){
    if(m*n==0)
        return (m+n-1);
    else 
        return F(m-1,F(m,n-1));
}

非递归算法为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define M 100
int F(int m,int n){
    int stack[m],top=-1;
    do{
        if (m*n!=0){
            stack[++top]=m-1;
            n--;
        }
        else{
            n=m+n+1;
            if(top>=0)
                m=stack[top];
            top--;
        }
    }while(top>=-1);
    return (n)
}

计算表达式

中缀表达式：运算符出现在两个运算对象之间（除了单目运算符）
例如：

1
A+(B-C/D)*E

后缀表达式：运算符出现在运算对象之后
后缀表达式中没有括号也不存在优先级的差别
例如：

1
ABCD/-E*+

计算后缀表达式

处理后缀表达式过程中，需要设置一个堆栈，用来保存已经读到的运算对象。当读到的一个字符为运算对象（数字、字母）就将其压入堆栈；当读到的一个字符为运算符，就从堆栈中取出相应的运算对象，进行计算，并把结果作为新的运算对象压入堆栈

中缀表达式转换后缀表达式

使用两个栈，一个栈临时储存运算符，另一个记录最终表达式结果，根据运算符优先级关系进行处理

迷宫问题

思路：从迷宫的入口出发，沿着某一个方向向前试探，若能够行得通则继续往前走；否则沿原路返回，换一个方向继续试探。为了保证能够原路返回，需要设置一个对战结构保存中入口到当前位置的路径。
迷宫用一个二维数组maze[m+1] [n+1]表示（多出来的+1表示迷宫的外围），数组的元素值为0时表示可以进入，1表示道路堵塞，2表示已经进入过。
老鼠移动的方向设置一个数组move[][]={{1,0},{1,1},...}
为了记录当前位置以及在该位置上选择的方向，可以设置一个堆栈进行回溯。

队列

在表的一端进行插入，在另一端进行删除。插入的一端称为队尾，删除的一端称为队头。没有元素的队列称为空队。插入称为进队，删除称为出队。按照先进先出的原则。
队列和堆栈一样是动态结构。
采用顺序存储结构的队列简称顺序队列。

队列构造

设置两个变量front、rear来指出队头和队尾的位置。

初始化队列：front=-1;rear=-1;
测试队列是否为空：front==rear;
取当前队头元素：item=queue[front+1];
进队：

1
2
3
4
5
6
if(reat==Max-1) //队列满
    return 0;
else{   //队列未满
    queue[++rear]=item;
    return 1;
}

出队：

1
2
3
4
5
6
if(栈空)  
    return 0;
else{
    item=queue[++front]; //将队头指针向队尾方向移动一个位置   
    return 1;
}

循环队列

插入：

1
2
3
4
5
if((rear+1)%Max==front)
    return 0;
else{
    queue[++rear%M]=item;
}

删除：

1
2
3
4
5
6
7
if(front==rear)
    return 0;
else{
    front=(front+1)%Max;
    item=queue[front];
    return 1;
}

队列的链式存储结构

使用过程中频繁进行插入和删除的数据结构适合采用链式存储结构。
把线性链表的第一个链结点的指针定义为头指针front，链表最后的链结点rear作为队尾指针，并且只能在链头进行删除，在链尾进行插入。