menu 小墨迹
more_vert
chevron_right 首页 » WEEK,问题&解决方法,奇异见闻 » Write routines to implement two stacks using only one array. Your stack routines should not declare an overflow unless every slot in the array is used
Write routines to implement two stacks using only one array. Your stack routines should not declare an overflow unless every slot in the array is used
2020-10-01 | WEEK,问题&解决方法,奇异见闻 | 1 条评论 | 43 次阅读 | 174字

代码不长,也不难,可是测试出错,看来看去也看不出哪里有错,于是自己补全了裁判程序运行测试了一下。原来是Push 函数里面switch语句后面没有加 break;导致switch没有跳出。啊这这这。。。。
三天不写手生,但是,签个学期花了好多时间写c语言,我的挂科其实是一念之间,就像一层玻璃纸,我可以挂,可以不挂,截然不同的两个结果,虽然发生了最糟糕那个。默哀。

题目部分:

Write routines to implement two stacks using only one array. Your stack routines should not declare an overflow unless every slot in the array is used.

Format of functions:

Stack CreateStack( int MaxElements );
int IsEmpty( Stack S, int Stacknum );
int IsFull( Stack S );
int Push( ElementType X, Stack S, int Stacknum );
ElementType Top_Pop( Stack S, int Stacknum );

where int Stacknum is the index of a stack which is either 1 or 2; int MaxElements is the size of the stack array; and Stack is defined as the following:

typedef struct StackRecord *Stack;
struct StackRecord  {
    int Capacity;       /* maximum size of the stack array */
    int Top1;           /* top pointer for Stack 1 */
    int Top2;           /* top pointer for Stack 2 */
    ElementType *Array; /* space for the two stacks */
}

Note:## Push is supposed to return 1 if the operation can be done successfully, or 0 if fails. If the stack is empty, Top_Pop must return ERROR which is defined by the judge program.

Sample program of judge:

#include <stdio.h>
#include <stdlib.h>
#define ERROR 1e8
typedef int ElementType;
typedef enum { push, pop, end } Operation;

typedef struct StackRecord *Stack;
struct StackRecord  {
    int Capacity;       /* maximum size of the stack array */
    int Top1;           /* top pointer for Stack 1 */
    int Top2;           /* top pointer for Stack 2 */
    ElementType *Array; /* space for the two stacks */
};

Stack CreateStack( int MaxElements );
int IsEmpty( Stack S, int Stacknum );
int IsFull( Stack S );
int Push( ElementType X, Stack S, int Stacknum );
ElementType Top_Pop( Stack S, int Stacknum );

Operation GetOp();  /* details omitted */
void PrintStack( Stack S, int Stacknum ); /* details omitted */

int main()
{
    int N, Sn, X;
    Stack S;
    int done = 0;

    scanf("%d", &N);
    S = CreateStack(N);
    while ( !done ) {
        switch( GetOp() ) {
        case push: 
            scanf("%d %d", &Sn, &X);
            if (!Push(X, S, Sn)) printf("Stack %d is Full!\n", Sn);
            break;
        case pop:
            scanf("%d", &Sn);
            X = Top_Pop(S, Sn);
            if ( X==ERROR ) printf("Stack %d is Empty!\n", Sn);
            break;
        case end:
            PrintStack(S, 1);
            PrintStack(S, 2);
            done = 1;
            break;
        }
    }
    return 0;
}

/* Your function will be put here */

Sample Input:

5
Push 1 1
Pop 2
Push 2 11
Push 1 2
Push 2 12
Pop 1
Push 2 13
Push 2 14
Push 1 3
Pop 2
End

Sample Output:

Stack 2 is Empty!
Stack 1 is Full!
Pop from Stack 1: 1
Pop from Stack 2: 13 12 11

陈越
单位
浙江大学
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

我的程序:包括实现的裁判程序

#include <stdio.h>
#include <stdlib.h>
#define ERROR 1e8
typedef int ElementType;
typedef enum { push, pop, end } Operation;

typedef struct StackRecord *Stack;
struct StackRecord  {
    int Capacity;       /* maximum size of the stack array */
    int Top1;           /* top pointer for Stack 1 */
    int Top2;           /* top pointer for Stack 2 */
    ElementType *Array; /* space for the two stacks */
};

Stack CreateStack( int MaxElements );
int IsEmpty( Stack S, int Stacknum );
int IsFull( Stack S );
int Push( ElementType X, Stack S, int Stacknum );
ElementType Top_Pop( Stack S, int Stacknum );

//Operation GetOp();  /* details omitted */
void PrintStack( Stack S, int Stacknum ); /* details omitted */

int main()
{
    int N, Sn, X;
    Stack S;
    int done = 0;

    scanf("%d", &N);
    S = CreateStack(N);
    while ( !done ) {
        switch( GetOp() ) {
        case push:
            scanf("%d %d", &Sn, &X);
            if (!Push(X, S, Sn)) printf("Stack %d is Full!\n", Sn);
            break;
        case pop:
            scanf("%d", &Sn);
            X = Top_Pop(S, Sn);
            if ( X==ERROR ) printf("Stack %d is Empty!\n", Sn);
            break;
        case end:
            PrintStack(S, 1);
            PrintStack(S, 2);
            done = 1;
            break;
        }
    }
    system("pause");
    return 0;
}

int GetOp(){
    char s[20];
    scanf("%s",s);
    if (0 == strcmp(s,"Push")){
        return push;
    }else if (0 == strcmp(s,"Pop")){
        return pop;
    }else if (0 == strcmp(s,"End")){
        return end;
    }
}

void PrintStack( Stack S, int Stacknum ){
    printf("\nNO.%d:",Stacknum);
    while (!IsEmpty(S,Stacknum)){
        printf("%d ",Top_Pop(S,Stacknum));
    }
}

/* Your function will be put here */
Stack CreateStack( int MaxElements ){
    Stack retVal = (Stack)malloc(sizeof(Stack));
    retVal->Capacity = MaxElements;
    retVal->Array = (ElementType)malloc(sizeof(ElementType) * MaxElements);
    retVal->Top1 = -1;
    retVal->Top2 = MaxElements;
    return retVal;
}
int IsEmpty( Stack S, int Stacknum ){
    switch (Stacknum){
        case 1:
            return S->Top1 <= -1;
        case 2:
            return S->Top2 >= S->Capacity;
    }
}

int IsFull( Stack S ){
    return (S->Top1 + 1) >= S->Top2;
}

int Push( ElementType X, Stack S, int Stacknum ){
    if (IsFull(S)){
        return 0;
    }
    switch(Stacknum){
        case 1:
            S->Array[++(S->Top1)] = X;
            break;
        case 2:
            S->Array[--(S->Top2)] = X;
            break;
    }
    return 1;
}

ElementType Top_Pop( Stack S, int Stacknum ){
    if (IsEmpty(S,Stacknum)){
        return ERROR;
    }
    switch(Stacknum){
        case 1:
            return S->Array[S->Top1--];
        case 2:
            return S->Array[S->Top2++];
    }
}
None

添加新评论
icon_mrgreen.gificon_neutral.gificon_twisted.gificon_arrow.gificon_eek.gificon_smile.gificon_confused.gificon_cool.gificon_evil.gificon_biggrin.gificon_idea.gificon_redface.gificon_razz.gificon_rolleyes.gificon_wink.gificon_cry.gificon_surprised.gificon_lol.gificon_mad.gificon_sad.gificon_exclaim.gificon_question.gif2016ka.gif2016bb.gif2016qiao.gif2016ll.gif2016shuai.gif2016zj.gif2016zk.gif

    iuio博主
    October 1st, 2020 at 01:23 pm

    垂死病中惊坐起,暗风吹雨入寒窗。