开发者社区> 流楚丶格念> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

数据结构——栈PTA习题

简介: 数据结构——栈PTA习题
+关注继续查看

单选题


image

image.png


函数题


6-1 在一个数组中实现两个堆栈 (29分)


本题要求在一个数组中实现两个堆栈。


函数接口定义:


Stack CreateStack( int MaxSize );
bool Push( Stack S, ElementType X, int Tag );
ElementType Pop( Stack S, int Tag );


其中Tag是堆栈编号,取1或2;MaxSize堆栈数组的规模;Stack结构定义如下:


typedef int Position;
struct SNode {
    ElementType *Data;
    Position Top1, Top2;
    int MaxSize;
};
typedef struct SNode *Stack;


注意:如果堆栈已满,Push函数必须输出“Stack Full”并且返回false;如果某堆栈是空的,则Pop函数必须输出“Stack Tag Empty”(其中Tag是该堆栈的编号),并且返回ERROR。


输入样例:


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


输出样例:


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


代码


#include <stdio.h>
#include <stdlib.h>

#define ERROR 1e8
typedef int ElementType;
typedef enum { push, pop, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
struct SNode {
    ElementType *Data;
    Position Top1, Top2;
    int MaxSize;
};
typedef struct SNode *Stack;

Stack CreateStack( int MaxSize );
bool Push( Stack S, ElementType X, int Tag );
ElementType Pop( Stack S, int Tag );

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

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

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

/* 你的代码将被嵌在这里 */

Stack CreateStack(int MaxSize)
{
    struct SNode *S = NULL;
    S = (struct SNode*)malloc(sizeof(struct SNode));

    S->Data =(int *)malloc(MaxSize * sizeof(int));
    S->Top1 = -1;       
    S->Top2 = MaxSize;  // 两个栈是   首尾

    S->MaxSize = MaxSize;
    return S;

}
bool Push(Stack S, ElementType X, int Tag)
{
    // 判断是否满了   这俩栈如果相对差1就是满了
    if (S->Top2 - S->Top1 == 1)
    {
        printf("Stack Full\n");
        return false;
    }
    else
    {
        // 栈编号
        if (Tag == 1)
        {
            S->Data[++(S->Top1)] = X;
        }
        else if (Tag == 2)
        {
            S->Data[--(S->Top2)] = X;
        }
        return true;
    }
}
ElementType Pop(Stack S, int Tag)
{
    if (Tag == 1)
    {
        if (S->Top1 == -1)
        {
            printf("Stack %d Empty\n", Tag);
            return ERROR;
        }
        else 
            return S->Data[(S->Top1)--];
    }
    else if (Tag == 2)
    {
        if (S->Top2 == S->MaxSize)
        {
            printf("Stack %d Empty\n", Tag);
            return ERROR;
        }
        else
        {
            return S->Data[(S->Top2)++];
        }
    }

}


6-2 另类堆栈 (21分)


在栈的顺序存储实现中,另有一种方法是将Top定义为栈顶的上一个位置。请编写程序实现这种定义下堆栈的入栈、出栈操作。如何判断堆栈为空或者满?


函数接口定义:


bool Push( Stack S, ElementType X );
ElementType Pop( Stack S );


其中Stack结构定义如下:


typedef int Position;
typedef struct SNode *PtrToSNode;
struct SNode {
    ElementType *Data;  /* 存储元素的数组 */
    Position Top;       /* 栈顶指针       */
    int MaxSize;        /* 堆栈最大容量   */
};
typedef PtrToSNode Stack;


注意:如果堆栈已满,Push函数必须输出“Stack Full”并且返回false;如果队列是空的,则Pop函数必须输出“Stack Empty”,并且返回ERROR。


输入样例:


4
Pop
Push 5
Push 4
Push 3
Pop
Pop
Push 2
Push 1
Push 0
Push 10
End


输出样例:


Stack Empty
3 is out
4 is out
Stack Full
0 1 2 5


代码



#include <stdio.h>
#include <stdlib.h>

#define ERROR -1
typedef int ElementType;
typedef enum { push, pop, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct SNode *PtrToSNode;
struct SNode {
    ElementType *Data;  /* 存储元素的数组 */
    Position Top;       /* 栈顶指针       */
    int MaxSize;        /* 堆栈最大容量   */
};
typedef PtrToSNode Stack;

Stack CreateStack( int MaxSize )
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S->Top = 0;
    S->MaxSize = MaxSize;
    return S;
}

bool Push( Stack S, ElementType X );
ElementType Pop( Stack S );

Operation GetOp();          /* 裁判实现,细节不表 */
void PrintStack( Stack S ); /* 裁判实现,细节不表 */

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

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

/* 你的代码将被嵌在这里 */
bool Push(Stack S, ElementType X)
{
    if (S->Top==S->MaxSize)
    {
        printf("Stack Full\n");
        return false;
    }
    else
    {
        S->Data[(S->Top)++] = X;
        return true;
    }
}

ElementType Pop(Stack S)
{
    if (S->Top == 0)
    {
        printf("Stack Empty\n");
        return ERROR;
    }
    else 
        return S->Data[--(S->Top)];
}


编程题


7-1 符号配对 (30分)


请编写程序检查C语言源程序中下列符号是否配对:/* 与 */、( 与 )、[ 与 ]、{ 与 }。


输入格式:


输入为一个C语言源程序。当读到某一行中只有一个句点.和一个回车的时候,标志着输入结束。程序中需要检查配对的符号不超过100个。


输出格式:


首先,如果所有符号配对正确,则在第一行中输出YES,否则输出NO。然后在第二行中指出第一个不配对的符号:如果缺少左符号,则输出?-右符号;如果缺少右符号,则输出左符号-?。


输入样例1:


void test()
{
    int i, A[10];
    for (i=0; i<10; i++) /*/
        A[i] = i;
}
.


输出样例1:


NO
/*-?


输入样例2:


void test()
{
    int i, A[10];
    for (i=0; i<10; i++) /**/
        A[i] = i;
}]
.


输出样例2:


NO
?-]


输入样例3:


void test()
{
    int i
    double A[10];
    for (i=0; i<10; i++) /**/
        A[i] = 0.1*i;
}
.


输出样例3:


YES


代码


#include<stdio.h>
#include<stdlib.h>
typedef struct
{
    int *data;
    int top;
}stack,*Stack;

void initstack(Stack S)
{
    S->data=(int*)malloc(100*sizeof(int));
    S->top=-1;
}

int panduan(char a)
{
    switch(a)
    {
        case '(':
            return 1;
        case  '[':
            return 2;
        case '{':
            return 3;
        case ')':
            return -1;
        case ']':
            return -2;
        case '}':
            return -3;
        case '/':
            return 4;
        case '*':
            return 5;
        case '.':
            return 10;
        case '\n':
            return 11;
        default:
            return 0;
    }
}

char* chu(int number)
{
    char *a; 
    switch(number)
    {
        case 1:
              a="(";
            return a;
        case -1:
            a=")";
            return a;
        case 2:
            a="[";
            return a;
        case -2:
            a="]";
            return a;
        case 3:
            a="{";
            return a;
        case -3:
            a="}";
            return a;
        case 6:
            a="/*";
            return a;
        case -6:
            a="*/";
            return a;
        default :
            return 0;
    }
}

int main()
{
    Stack S;
    int state=0;
    S=(Stack)malloc(sizeof(stack));
    initstack(S);
    char a;
    int flag=0;
    int number;
    int lastnumber;
    int last=0;
    while(1)
    {
        flag++;
        scanf("%c",&a);
        number=panduan(a);
        if(number==10)
        {
            flag=9;
            continue;
        }
        if(number==11&&flag==10)
        {
            number=lastnumber;
            break;  
        }
        if(number==11)
        continue;
        if(number==4&&last!=5)
        {
            last=4;
            continue;
        }
        else if(number==5&&last==4)
        {
            number=6;
            last=0;
        }
        else if(number==5&&last!=4)
        {
            last=5;
            continue;
        }
        else if(number==4&&last==5) 
        {
            number=-6;
            last=0;
        }
        if(number!=0&&number>0)
        {
            S->data[++S->top]=number;
        }
        else if(number!=0&&number<0)
        {
            if((S->data[S->top]+number)==0&&S->top>=0)
            S->top--;
            else if(S->top==-1)
            {
                printf("NO\n?-%s",chu(number));
                state=1;
                break;
            }
            else
            {
                state=1;
                printf("NO\n%s-?",chu(S->data[S->top]));
                break;
            }
        }
        lastnumber=number;
    }
    if(S->top==-1&&state!=1)
    printf("YES");
    else if(S->top!=-1&&state!=1)
    printf("NO\n%s-?",chu(S->data[0])); 

}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
RAC 数据库的启动与关闭
        RAC数据库与单实例的差异主要表现在多个实例通过集群件来统一管理共享的资源。因此原有的单实例的管理方式,如数据库、监听器等的关闭启动等可以使用原有的方式进行,也可以通过集群管理工具,命令行来集中管理,这也是推荐的管理方式。
1190 0
Java数据结构与算法(八)-二叉树
一、为什么要使用树 有序数组插入、删除数据慢。 链表查找数据慢 树可以解决这两个问题 二、相关术语 树的结点:包含一个数据元素及若干指向子树的分支; 孩子结点:结点的子树的根称为该结点的孩子; 双亲结点:B 结点是A 结点的孩子,则A结点是B 结...
728 0
数据结构——栈
1 栈具有后进先出(LIFO)的操作特点,是操作受限的线性表。栈的存储有顺序栈和链栈两种。 2 在顺序存储方式下,采用一维数组(即向量)来模拟连续的存储空间。通常将0下表作为栈底,栈的第一个元素(即栈底元素)存放在0下表位置。顺序栈的实现: //SqStack.h #ifndef _SQSTACK_ #define _SQSTACK_ template&lt;class T&gt; c
923 0
数据结构——栈
1、什么是栈 2、顺序栈的实现和基本操作 3、共享栈的实现和基本操作 4、链式栈的实现和基本操作 5、栈的简单应用
119 0
数据结构-二叉树
数据结构-二叉树
32 0
数据结构 —— 二叉树
数据结构 —— 二叉树
9 0
+关注
流楚丶格念
csdn平台优质创作者,51cto TOP博主,360图书馆科技博主,燕山大学目前大三在读,日拱一卒,功不唐捐,加油!!!
1010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载