数据结构-题目2

雨点打透心脏的1/2处 2022-07-28 05:29 146阅读 0赞

/*
    设从键盘输入一个整数序列a1,a2,...,an,试编程实现：当ai>0时，ai进队，当ai<0时，将队首元素出队，当ai=0时，输入结束。
    要求将队列处理成环形队列，进队和出队操作单独编写算法，并在异常情况时（如队满）打印错误信息。
    */
    
    #include <iostream>
    #include <malloc.h>
    #include <cstdio>
    #define MaxSize 100
    using namespace std;
    typedef int ElemType;
    typedef struct
    {
        ElemType data[MaxSize];
        int front,rear;
    }SqQueue;               //定义顺序队类型
    
    bool enQueue(SqQueue *&q,ElemType e)      //进队
    {
        if((q->rear+1)%MaxSize==q->front)    //队满上溢出
            return false;
        q->rear=(q->rear+1)%MaxSize;
        q->data[q->rear]=e;
        return true;
    }
    bool deQueue(SqQueue *&q,ElemType &e)   //出队，并输出
    {
        if(q->front==q->rear)          //队空下溢出
            return false;
        q->front=(q->front+1)%MaxSize;
        e=q->data[q->front];
        return true;
    }
    int main()
    {
        int a;
        ElemType e;
        SqQueue *q;
        q=(SqQueue *)malloc(sizeof(SqQueue));
        q->front=q->rear=0;
        cout<<"请输入：";
        while((cin>>a)&&a!=0)
        {
            if(a>0)
            {
                if(!enQueue(q,a))
                {
                    cout<<"队满，不能入队！"<<endl;
                    break;
                }
    
            }
            else if(a<0)
            {
                if(!deQueue(q,e))
                {
                    cout<<"队空，下溢出！"<<endl;
                    break;
                }
                cout<<"出队元素："<<e<<endl;
            }
            cout<<"请输入：";
        }
        return 0;
    }

运行结果：

![Center][]

/*
    假设以I和O分别表示进栈和出栈操作，栈的初态和终态均为空，写一个程序判断所给操作序列是否合法。
    假设被判定的操作序列已存入一维数组中。
    */
    #include <iostream>
    #include <malloc.h>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    typedef char ElemType;
    typedef struct linknode
    {
        ElemType data;
        struct linknode *next;
    } LiStack;              //定义链栈类型
    
    void InitStack(LiStack *&s)           //初始化链栈s
    {
        s=(LiStack *)malloc(sizeof(LiStack));
        s->next=NULL;
    }
    
    bool StackEmpty(LiStack *s)           //判断链栈s是否为空
    {
        return (s->next==NULL);
    }
    
    void Push(LiStack *&s,ElemType e)      //进栈
    {
        LiStack *p;
        p=(LiStack *)malloc(sizeof(LiStack));
        p->data=e;
        p->next=s->next;
        s->next=p;
    }
    
    bool Pop(LiStack *&s,ElemType &e)   //出栈
    {
        LiStack *p;
        if(s->next==NULL)
            return false;
        p=s->next;
        e=p->data;
        s->next=p->next;
        free(p);
        return true;
    }
    
    int judge(char c[],int n)
    {
        ElemType x;
        LiStack *s;
        InitStack(s);
        for(int i=0; i<n; i++)
        {
            if(c[i]=='I')
                Push(s,c[i]);
            else if(c[i]=='O')
            {
                if(StackEmpty(s))
                    return 0;
                else
                    Pop(s,x);
            }
        }
        return (StackEmpty(s));
    }
    int main()
    {
        ElemType a[10];
        while(1)
        {
            cout<<"输入IO序列:";
            gets(a);
            if(judge(a,strlen(a)))
                cout<<"序列合法！"<<endl;
            else
                cout<<"序列不合法！"<<endl;
            cout<<endl;
        }
        return 0;
    }

运行结果：

![Center 1][]

[Center]: /images/20220727/fd0917ed79c44c04bee48162d2896bd3.png
[Center 1]: /images/20220727/9280777edb644f95bc6689b68d2d448f.png