数据结构实验二栈、队列

红太狼 2022-08-21 07:56 216阅读 0赞

实验内容：

1．采用链式存储实现栈的初始化、入栈、出栈操作。

2．采用顺序存储实现栈的初始化、入栈、出栈操作。

3．采用链式存储实现队列的初始化、入队、出队操作。

4．采用顺序存储实现循环队列的初始化、入队、出队操作。

5．在主函数中设计一个简单的菜单，分别测试上述算法。

6. 利用栈实现数制转换（将一个十进制数转换成d进制数）。

1.链式栈（相当于一个先入后出 的单链表）

#include <stdio.h>
    #include <stdlib.h> ///链式栈
    
    typedef struct node
    {
        int data;
        struct node *next;
    }Node,*Linklist;
    
    Linklist Createlist()
    {
        Linklist p;
        Linklist h;
        int data1;
        scanf("%d",&data1);
        if(data1 != 0)
        {
            h = (Node *)malloc(sizeof(Node));
            h->data = data1;
            h->next = NULL;
        }
        else if(data1 == 0)
        return NULL;
        scanf("%d",&data1);
        while(data1 != 0)
        {
            p = (Node *)malloc(sizeof(Node));
            p -> data = data1;
            p -> next = h;
            h = p;
            scanf("%d",&data1);
        }
        return h;
    }
    
    void Outputlist(Node *head)
    {
        Linklist p;
        p = head;
        while(p != NULL )
        {
            printf("%d ",p->data);
            p = p->next;
        }
        printf("\n");
    }
    
    void Freelist(Node *head)
    {
        Node *p;
        Node *q = NULL;
        p = head;
        while(p != NULL)
        {
            q = p;
            p = p->next;
            free(q);
        }
    }
    
    int main()
    {
        Node *head;
        head = Createlist();
    
        Outputlist(head);
    
        Freelist(head);
    
        return 0;
    }

2.顺序栈

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h> ///顺序栈
    #define MaxSize 100
    
    using namespace std;
    
    typedef int ElemType;
    
    typedef struct node
    {
        ElemType data[MaxSize];
        int top;
    }SeqStack;
    
    void InitStack(SeqStack &s)
    {
        s.top=-1;
        return;
    }
    
    int StackEmpty(SeqStack s)
    {
        return (s.top==-1);
    }
    
    int push(SeqStack &s, ElemType x)
    {
        if(s.top>=MaxSize)
        {
            cout<<"Over Flow"<<endl;
            return 0;
        }
        else
        {
            s.top++;
            s.data[s.top]=x;
            return 1;
        }
    }
    
    int pop(SeqStack &s,ElemType &x)
    {
        if(s.top==-1)
        {
            cout<<"Stack Empty"<<endl;
            return 0;
        }
        else
        {
            x=s.data[s.top];
            s.top--;
            return 1;
        }
    }
    
    int GetTop(SeqStack s,ElemType &e)
    {
        if(s.top==-1)
        {
            cout<<"Stack Empty"<<endl;
            return 0;
        }
        else
        {
            e=s.data[s.top];
            return 1;
        }
    }
    
    int main()
    {
        SeqStack Sta;
        InitStack(Sta);
        int x;
        cin>>x;
        while(x!=0)
        {
            int flag=push(Sta,x);
            cin>>x;
        }
        while(!StackEmpty(Sta))
        {
            pop(Sta,x);
            cout<<x<<" ";
        }
        cout<<endl;
        /*int k=StackEmpty(Sta);
        cout<<k<<endl;
        int flag=push(Sta,3);
        cout<<"flag="<<flag<<endl;
        k=StackEmpty(Sta);
        cout<<k<<endl;
        int x;
        flag=GetTop(Sta,x);
        cout<<"flag="<<flag<<endl;
        cout<<"e="<<x<<endl;
        flag=pop(Sta,x);
        cout<<"flag="<<flag<<endl;
        k=StackEmpty(Sta);
        cout<<k<<endl;*/
        return 0;
    }

3.链队列

#include <iostream>///链队列
    #include <stdio.h>
    #include <stdlib.h>
    #define OVERFLOW -2
    #define OK 1
    #define ERROR 0
    
    using namespace std;
    
    typedef int QElemType;
    
    typedef struct QNode
    {
        QElemType data;
        struct QNode *next;
    }QNode,*QueuePtr;
    typedef struct
    {
        QueuePtr front;
        QueuePtr rear;
    }LinkQueue;
    
    
    int InitQueue(LinkQueue &Q)
    {
        Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
        if(!Q.front) exit(OVERFLOW);
        Q.front->next=NULL;
        return OK;
    }
    
    int DestroyQueue(LinkQueue &Q)
    {
        while(!Q.front)
        {
            Q.rear=Q.front->next;
            free(Q.front);
            Q.front=Q.rear;
        }
        return OK;
    }
    
    int EnQueue(LinkQueue &Q,QElemType e)
    {
        QueuePtr p;
        p=(QueuePtr)malloc(sizeof(QNode));
        if(!p) exit(OVERFLOW);
        p->data=e;
        p->next=NULL;
        Q.rear->next=p;
        Q.rear=p;
        return OK;
    }
    
    int DeQueue(LinkQueue &Q,QElemType &e)
    {
        QueuePtr p;
        if(Q.front==Q.rear) return ERROR;
        p=Q.front->next;
        e=p->data;
        Q.front->next=p->next;
        if(Q.rear==p) Q.rear=Q.front;
        free(p);
        return OK;
    }
    
    int Empty(LinkQueue Q)
    {
        if(Q.rear==Q.front)
        {
            return 1;
        }
        else return 0;
    }
    
    int main()
    {
        LinkQueue QQ;
        int flag=InitQueue(QQ);
        if(flag==1)
        {
            int x;
            cin>>x;
            while(x!=0)
            {
                flag=EnQueue(QQ,x);
                if(flag==0)
                    break;
                cin>>x;
            }
            while(!Empty(QQ))
            {
                flag=DeQueue(QQ,x);
                cout<<x<<" ";
            }
            cout<<endl;
        }
        else
            cout<<"Queue Error!"<<endl;
        return 0;
    }

4.循环队列

#include <iostream>
    #include <cstdio>///循环队列
    #include <cstdlib>
    
    #define Maxsize 100
    #define OK 1
    #define OVERFLOW -2
    
    using namespace std;
    
    typedef int ElemType;
    
    typedef struct
    {
        ElemType *base;
        int front;
        int rear;
    } SeqQueue;
    
    int InitQueue(SeqQueue &Q)
    {
        Q.base=(ElemType *)malloc(Maxsize*sizeof(ElemType));
        if(!Q.base)
            exit(OVERFLOW);
        Q.front = Q.rear =0;
        return OK;
    }
    
    int EnQueue(SeqQueue &Q,ElemType e)
    {
        if((Q.rear+1)%Maxsize==Q.front)
        {
            cout<<"Queue Full"<<endl;
            return 0;
        }
        Q.rear = (Q.rear+1)%Maxsize;
        Q.base[Q.rear]=e;
        return 1;
    }
    
    int DeleQueue(SeqQueue &Q,ElemType &e)
    {
        if(Q.front==Q.rear)
        {
            cout<<"Queue Empty"<<endl;
            return 0;
        }
        Q.front=(Q.front+1)%Maxsize;
        e=Q.base[Q.front];
        return 1;
    }
    
    int Empty(SeqQueue Q)
    {
        if(Q.rear==Q.front)
            return 1;
        else return 0;
    }
    
    int main()
    {
        SeqQueue QQ;
        int flag;
        int n;
        flag=InitQueue(QQ);
        if(flag)
        {
            cin>>n;
            while(n!=0)
            {
                flag=EnQueue(QQ,n);
                if(flag==0)
                {
                    break;
                }
                cin>>n;
            }
            while(!Empty(QQ))
            {
                flag=DeleQueue(QQ,n);
                cout<<n<<" ";
            }
            cout<<endl;
        }
        else
        {
            cout<<"Queue Error!"<<endl;
        }
        return 0;
    }

6. 利用顺序栈实现

#include <iostream>
    #define Maxsize 100
    
    using namespace std;
    
    typedef int ElemType;
    
    typedef struct ///利用顺序栈实现
    {
        ElemType data[Maxsize];
        int top;
    } SeqStack;
    
    void InitStack(SeqStack &s)
    {
        s.top=-1;
    }
    
    int StackEmpty(SeqStack s)
    {
        return (s.top==-1);
    }
    
    int PushStack(SeqStack &s,ElemType x)
    {
        if(s.top>=Maxsize)
        {
            cout<<"Over Flow"<<endl;
            return 0;
        }
        else
        {
            s.top++;
            s.data[s.top]=x;
            return 1;
        }
    }
    
    int PopStack(SeqStack &s,ElemType &x)
    {
        if(s.top==-1)
        {
            cout<<"Stack Empty!"<<endl;
            return 0;
        }
        else
        {
            x=s.data[s.top];
            s.top--;
            return 1;
        }
    }
    
    void Display(SeqStack s)
    {
        for(int i=0; i<=s.top; i++)
        {
            cout<<s.data[i]<<" ";
        }
        cout<<endl;
    }
    
    void conversion(int d)
    {
        SeqStack s;
        int N,e;
        InitStack(s);
        cout<<"输入一个十进制数: "<<endl;
        cin>>N;
        while(N)
        {
            PushStack(s,N%d);
            N=N/d;
        }
        while(!StackEmpty(s))
        {
            PopStack(s,e);
            cout<<e;
        }
        cout<<endl;
    }
    
    int main()
    {
        int d;
        cout<<"输入想要转化成的进制数: "<<endl;
        cin>>d;
        conversion(d);
        return 0;
    }