2016-08-02
阅读:(674)
评论(0)

些年，一起追过的算法阅读器电子书

栈和线性表类似，也是有两种存储结构，分别为顺序结构和链式结构。大部分情况下，栈使用前者，这和它的使用场景有关，因为通常情况下我们不会对栈进行频繁地，随机地插入，删除操作。下面是我用顺序结构实现的栈，这个栈有个特点就是它的通用性，因为我并没有限制它所存储的数据类型，代码如下:

//void**其为双指针，意味入栈和出栈的将只是对应数据的地址，而不需要对数据本身进行拷贝
typedef struct 
{
    char *base;
    char *top;
    int elementSize; //元素所点字节大小
    int stackSize;  //当前已分配的空间(注意不是元素的实际个数)
}ponyStack;

int InitStack(ponyStack *stack, int elementSize)
{
    stack->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char)*elementSize);
    if (!stack->base)
    {
        return RET_ERROR;
    }

    stack->top = stack->base; //为空
    stack->stackSize = STACK_INIT_SIZE;
    stack->elementSize = elementSize;

    return RET_OK;
}

int ClearStack(ponyStack *stack)
{
    stack->top = stack->base;
    return RET_OK;
}

bool IsEmptyStack(ponyStack stack)
{
    if (stack.top == stack.base)
    {
        return true;
    }
    return false;
}

这里没有贴出全部的代码，更完整的可以从最后的地址那里下载。注意elementSize,这个是栈可以做到通用的核心。不理解的可以再研究一下代码。

看一个栈的使用示例，数制转换。十进制转八进制。例如(1348)十进制= (2504)八进制,它基于如下的原理:

N N/8 N%8

1348 168 4

168 21 0

21 2 5

2 0 2

所以很明显，N不断的除8，每次的余数就是结果的其中一个因子，注意先出来的因子是低位的数，可以考虑用栈来保存每次取余的结果，那么出栈的顺序就是实际的结果顺序。代码很简单：

int decimalToOctonary(int decimalNumber)
{
    double octNumber = 0;
    int nCount = 0;
    int nTemp = 0;
    ponyStack numberStack;
    InitStack(&numberStack, 4);

    while (decimalNumber)
    {
        nTemp = (int)decimalNumber%8;
        Push(&numberStack, &nTemp);
        decimalNumber = decimalNumber/8;
    }

    nCount = CountOfStack(numberStack);//元素个数也就是位数
    while(!IsEmptyStack(numberStack))
    {
        Pop(&numberStack, &nTemp);
        octNumber += (nTemp*pow(10.0, --nCount));
    }

    DestroyStack(&numberStack);

    return (int)octNumber;
}

再来看一个行编辑程序的示例，用户在终端输入字符，完成后保存用户的数据区，因为在输入的过程中可能出错，需要修改，所以不可能每输入一个字符就存入数据区。比较好的做法是先在内存里开一个输入的缓冲区，当用户输入完成一行后，再存入数据区。在行内可以修改。例如，当用户发现刚输入的一个字符是错的之后，可以再输入一个’#’,表示前一个字符是错的，如果发现当前行输入的错误太多，可以输入一个退行符’@’,表示当前行都无效，举个例子:
whli#ilr#e(s#*s)

outcha@putchar(*s=#++)

实际有效的字符是这样的:

while(*s)

putchar(*s++)

可以把内存里这个输入缓冲区定为栈,正常情况下每输入一个字符直接入栈，如果发现字符是’#’,就栈顶pop一次，如果是’@’就清空栈.代码实现如下:

void lineEdit()
{
    char ch = 0;
    char chTemp = 0;
    ponyStack lineStack;
    InitStack(&lineStack, 1);

    ch = getchar();
    while (ch != EOF)
    {

        while (ch != EOF && ch != '\n')
        {
            switch (ch)
            {
            case '#':
                Pop(&lineStack, &chTemp);
                break;
            case '@':
                ClearStack(&lineStack);
                break;
            default:
                Push(&lineStack, &ch);
                break;
            }
            ch = getchar();
        }

        writeToFile(lineStack);//存数据
        ClearStack(&lineStack);//准备接收下一行
        if (ch != EOF)
        {
            ch = getchar();
        }
    }

    DestroyStack(&lineStack);

}

最后一个例子是表达式求值的算法，这个在计算器应用中比较多用到。比如，

求+4*9-16/4

建两个栈，一个存操作数，一个存运算符.为简单起，在运算符栈会预先存一个’#’,表示表达式开始，然后以’#’结束。运算规则是这样的:

输入字符，如果是’#’，则结束，如果是操作数，直接进操作数栈。如果是运算符，则跟栈顶的运算符比较，如果栈顶的优先级低,直接进栈，接收下一字符，如果相等，脱括号，接收下一个字符，如果栈顶的优先级高，pop两个操作数，pop栈内操作符，运算，然后运算的结果进操作数栈。当前运算符继续跟栈顶比较。

要实现这个代码，首先要有一个表格，存储我们操作符之间的优先级关系，如下所示:

static char priority[7][7] = {
    '>','>','<','<','<','>','>',   // +
    '>','>','<','<','<','>','>',   // -
    '>','>','>','>','<','>','>',   // *
    '>','>','>','>','<','>','>',   // /
    '<','<','<','<','<','=',' ',   // (
    '>','>','>','>',' ','>','>',   // )
    '<','<','<','<','<',' ','=',   // #
};// +   -   *   /   (   )   #

然后实现根据上面的思路，实现起来就比较容易了：

int evaluateExpression()
{
    char chCurrent = 0;
    char chOnTop = 0;

    char chTemp = 0;
    int nResult = 0;
    int nTemp = 0;
    int a,b;
    int nOperandFlag = 0;

    ponyStack operatorStack;//运算符栈
    ponyStack operandStack; //操作数栈

    InitStack(&operatorStack, 1);
    chTemp = '#';
    Push(&operatorStack, &chTemp);

    InitStack(&operandStack, 4);

    chCurrent = getchar();
    GetTop(operatorStack, &chOnTop);

    while ((chCurrent != '#')||(chOnTop != '#'))
    {
        if (!isOperator(chCurrent))//是操作数,要考虑多位整型数的情况
        {
            nTemp = nTemp * (int)pow(10.0, nOperandFlag);
            nTemp += (int)(chCurrent - '0');
            chCurrent = getchar();
            nOperandFlag = 1;
        }
        else
        {
            if (nOperandFlag == 1)
            {
                Push(&operandStack, &nTemp);//操作数输入结束，入栈
                nOperandFlag = 0;
                nTemp = 0;
            }

            GetTop(operatorStack, &chOnTop);
            switch (precede(chOnTop, chCurrent))//比较优先级
            {
            case '<':       //栈顶的优先级小
                Push(&operatorStack, &chCurrent);
                chCurrent = getchar();
                GetTop(operatorStack, &chOnTop);
                break;
            case '=':       //脱括号，接收下个字符
                Pop(&operatorStack, &chTemp);
                chCurrent = getchar();
                GetTop(operatorStack, &chOnTop);
                break;
            case '>':       //栈顶的优先级大，出栈运算，结果入栈
                {
                    Pop(&operandStack, &a);
                    Pop(&operandStack, &b);
                    Pop(&operatorStack, &chTemp);
                    nTemp = operate(a, chTemp, b);
                    Push(&operandStack, &nTemp);
                    nTemp = 0;//重置
                    GetTop(operatorStack, &chOnTop);
                }
                break;
            default:
                break;
            }

        }
    }

    GetTop(operandStack, &nResult);

    DestroyStack(&operatorStack);
    DestroyStack(&operandStack);

    return nResult;
}