02-线性结构4 Pop Sequence

2018-06-18 03:51:57来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

  这道题是2013年PAT春季考试真题,考察队堆栈的基本概念的掌握。在保证输入正确后,关键在于对"Pop"序列的判断,我用isPopOrder()函数进行了判断,代码如下:

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 1001

typedef struct SNode *Stack;
struct SNode{
    int Data[MaxSize];
    int MaxCap;  //Maximum capacity of this stack
    int Top;
};

Stack CreateStack(int M)
{
    Stack PtrS;
    PtrS = (Stack)malloc(sizeof(struct SNode));
    PtrS->Top = -1;
    PtrS->MaxCap = M;
    return PtrS;
}

/*堆栈基本操作此处略去*/

int isPopOrder(int *CheckOrder, int M, int N, int K)
{
    int i, ci = 0;
    Stack S;
    S = CreateStack(M);
    for(i = 1; i < N + 1; i++){
        Push(i, S);  //Push in the order of 1, 2, ..., N
        while(CheckOrder[ci] == GetTop(S)){
            Pop(S);
            ci++;
        }
    }
    if(GetTop(S) == -1)  //堆栈为空
        return 1;
    else
        return 0;
}

int main(int argc, char const *argv[])
{
    int M, N, K;  //M is the maximum capacity of the stack; Push N numbers; K sequences to be checked
    int i, j;
    int CheckOrder[MaxSize], res[MaxSize];
    scanf("%d %d %d", &M, &N, &K);
    for(i = 0; i < K; i++){
        for(j = 0; j < N; j++){
            scanf("%d", &CheckOrder[j]);
        }
        res[i] = isPopOrder(CheckOrder, M, N, K);
    }
    for(i = 0; i < K; i++){
        if(res[i])
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

  isPopOrder()中,每步循环按顺序放一个数进入堆栈,每放一次就对要检查的CheckOrder[ci]这一数字进行判断,若它和此时栈顶元素相同,则使当前栈顶元素出栈,并继续判断是否仍和栈顶元素相同并使出栈,直到不同或空栈为止;不同就进入下一循环继续顺序入栈。最后看堆栈中是否还存在元素,如果还有的话说明要判断的序列不符合要求。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:分享一个很通用c语言的Makefile

下一篇:Mac电脑C语言开发的入门帖