C语言使用栈和队列实现停车场管理

我就是我 2021-12-23 06:47 340阅读 0赞

## **C语言利用栈和队列实现停车场管理** ##

这次做的是C语言利用栈实现停车场管理–**纯手打非转载**  
停车场管理  
\[问题描述\]  
设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。  
\[基本要求\]  
（1） 要求以顺序栈模拟停车场，以链队列模拟便道。  
（2） 从终端读入汽车到达或离去的数据，每组数据包括三项：  
①是“到达”还是“离去”；  
②汽车牌照号码；  
③“到达”或“离去”的时刻。  
与每组输入信息相应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。

**算法思想：**  
1.车辆停入停车场的流程：  
首先判断停车场的车位是否停满。两种情况：(1)停满时此时后来的车辆只能停在走道上  
(2)未停满时后来的车辆继续入栈。  
2.车辆出站的思想。两种情况：(1)车辆在栈顶时，此时直接出栈而用不到辅助栈(2)车辆不在车顶时排在前面的车辆必须让位，此时它才能出栈，算法思想是首先根据输入的车牌号进行在栈中搜索，返还一个角标，根据角标来，找到出栈的车辆，这时前面的车辆入辅助栈，当循环的目标车辆时，这时不需要入辅助栈，直接出栈即可！  
**总体结构思路如下**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70]  
这时车位停满的情况，若非栈顶出栈则需要把他前面的车让位进辅助栈，当目标车出栈的再回来。

**停车流程图如下：**

![停车流程图如下][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70 1]  
**车辆离开流程图如下**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70 2]

**源代码：**

#include <stdio.h>
    #include <stdlib.h>
    #include<conio.h>
    #include <malloc.h>
    #define stackSize 3
    typedef int ElementType;
    //定义车辆信息的结构体
    typedef struct{ 
       int BNo;
       int type;
       int arrivetime;
       int pushtime;
       int departuretime;
    }BusInf;
    //栈定义
    typedef struct{ 
        BusInf elem[stackSize];
        int top;
    }SeqStack;
    //初始化栈
    void InitStack(SeqStack *s)
    { 
        s->top=-1;
    }
    //判断栈空--为1表示空--位0表示非空
    int IsEmpty(SeqStack *s)
    { 
        if(s->top==-1)
        { 
            return 1;
        }
        else{ 
            return 0;
        }
    }
    //判断栈满--0未满--1栈满
    int IsFull(SeqStack *s)
    { 
        if(s->top==stackSize-1)
        { 
           return 1;
        }
        else
            return 0;
    }
    //进站--1表示入栈--0表示栈满
    int push(SeqStack *s,BusInf bus)
    { 
        if(IsFull(s)==1)
        { 
            return 0;
        }
        else
        { 
            s->top++;
            s->elem[s->top]=bus;
          return 1;
        }
    }
    //出栈--1表示出栈，0表示栈空--用指针带出出栈的值
    int pop(SeqStack *s,BusInf *bus)
    { 
        if(IsEmpty(s)==1)
        { 
            return 0;
        }
        else
        { 
            *bus = s->elem[s->top];
            s->top--;
            return 1;
        }
    }
    //队列
    typedef struct Node{ 
        BusInf Bus;
        struct Node * next;
    }LinkQueueNode;
    typedef struct{ 
        LinkQueueNode *front;//头指针
        LinkQueueNode *rear;//队尾指针
    }LinkQueue;
    //初始化队列--将Q初始化为一个空的链队列
    int InitQueue(LinkQueue *Q)
    { 
        Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
        if(Q->front!=NULL)
        { 
            Q->rear=Q->front;
            Q->front->next=NULL;
            Q->rear->next=NULL;
            return 1;
        }
        else return 0;
    }
    //入队操作
    int EnterQueue(LinkQueue *Q,BusInf bus)
    { 
        //新建一个节点，插入队尾
        LinkQueueNode *NewNode = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
        if(NewNode!=NULL)
        { 
            NewNode->Bus=bus;
            NewNode->next=NULL;
            Q->rear->next=NewNode;
            //将最后一个插入的节点设为尾结点
            Q->rear=NewNode;
            return 1;
        }
        else{ 
            return 0;
        }
    }
    //出队操作
    int DeleteQueue(LinkQueue *Q,BusInf *bus){ 
        LinkQueueNode *p;
        if(Q->front==Q->rear){ 
          return 0;
        }
        else{ 
            p = Q->front->next;
            Q->front->next=p->next;//将对头更新
            *bus = p->Bus;
            //判断如果这个时候是否队列为空，是的话收尾指针相等
            if(Q->rear==p){ 
                Q->front=Q->rear;
            }
            //释放节点P
            free(p);
            return 1;
        }
    }
    //查找栈中有无车牌信息--temp代表出栈的位置....-1代表无车牌
    int searchBusNo(SeqStack *s,BusInf bus)
    { 
    
        SeqStack *p=NULL;
        p=s;
        int temp = p->top;
        while(temp>=0)
        { 
            if(p->elem[temp].BNo==bus.BNo)
                return temp;
            temp--;
        }
        return -2;
    }
    void showBus(SeqStack *s){ 
        printf("已停靠车辆：\n");
        //int temp = (s->top)+1;
         printf(" 车牌号 到达时间 停车时间\n");
         for(int temp=0;temp<=s->top;temp++)
         { 
           printf(" %4d%14d%15d\n",s->elem[temp].BNo,s->elem[temp].arrivetime,s->elem[temp].pushtime);
         }
    }
    //显示队列里的车
    void showQBus(LinkQueue *l){ 
        LinkQueueNode *p=l->front->next;
        printf("等待车辆：\n");
        printf(" 车牌号 到达时间\n");
        while(p!=NULL)
        { 
            printf(" %4d%14d\n",p->Bus.BNo,p->Bus.arrivetime);
            p=p->next;
        }
    }
    int selectCar(){ 
        int flag=0;
        printf("1.轿车 2.客车 3.卡车 ");
        printf("\n请选择车辆种类：\n");
        scanf("%d",&flag);
        if(flag!=1 && flag!=2 &&flag!=3)
        { 
            printf("输入错误重新输入：");
            scanf("%d",&flag);
        }
        return flag;
    }
    //输入车辆信息并且入栈或入队
    void inputCarData(SeqStack *s,LinkQueue *l){ 
        BusInf bus;
        printf("请输入车牌号:");
        scanf("%d",&bus.BNo);
        //判断车牌号是否重复
        if(searchBusNo(s,bus)!=-2){ 
            printf("车牌号重复！\n");
            printf("请重新输入车牌信息:");
            scanf("%d",&bus.BNo);
        }
        printf("请输入到达时间：\n");
        scanf("%d",&bus.arrivetime);
        if(bus.arrivetime<0 || bus.arrivetime>24)
        { 
            printf("时间输入不合法（0-24）重新输入：\n");
            scanf("%d",&bus.arrivetime);
        }
        bus.pushtime=bus.arrivetime;
        bus.type= selectCar();
        //车辆进栈--先判断栈是否满
        if(IsFull(s)==1){ 
            showBus(s);
            //栈满的情况，下面来的进队列中
            EnterQueue(l,bus);
            showQBus(l);
        }
        //栈没满的情况
        else{ 
         push(s,bus);
        //显示进栈车辆信息
        showBus(s);
        }
    }
    
    //离开停车位
    void leaveStack(SeqStack *s,SeqStack *se,LinkQueue *Q)
    { 
        if(IsEmpty(s)==1)
           { 
               printf("此时没有车辆停靠！");
                return;
           }
        int pay[]={ 2,3,4};
        int temp=0;
        int leavetime=0;
        BusInf bus;
        printf("请输入离开的车号");
        scanf("%d",&temp);
        bus.BNo=temp;
        int m = searchBusNo(s,bus);
        while(m==-2)
        { 
            printf("输入错误重新输入");
            scanf("%d",&temp);
            bus.BNo=temp;
            m=searchBusNo(s,bus);
        }
        printf("请输入出栈时间:");
        scanf("%d",&leavetime);
        while(leavetime<=s->elem[m].arrivetime)
        { 
            printf("离开时间必须大于停车时间！重新输入：");
            scanf("%d",&leavetime);
        }
            //显示出栈的车辆
        printf("******离去车辆信息******\n");
        printf(" 车牌号 价格 离开时间\n");
        s->elem[m].departuretime=leavetime;
        printf("%4d%13d%13d",s->elem[m].BNo,(leavetime-s->elem[m].arrivetime)*pay[s->elem[m].type-1],s->elem[m].departuretime);
        printf("\n************\n");
        //这时m接收的就是出栈的位置--2中情况在栈顶和不在栈顶--让位时进入辅助栈se
        //离开的车在栈顶时
        if(m==s->top)
        { 
            BusInf *b;
            b=(BusInf*)malloc(sizeof(BusInf));
            pop(s,b);
        }
        //不在栈顶
        else
        { 
         for(int i=s->top;i>=m;i--){ 
            BusInf *b=(BusInf*)malloc(sizeof(BusInf));
            //先入栈再出战
            if(i==m)
            { 
                pop(s,b);
            }
            else{ 
                push(se,s->elem[i]);
                pop(s,b);
            }
        }
            for(int j=se->top;j>=0;j--)
            { 
                BusInf *b=(BusInf*)malloc(sizeof(BusInf));
                pop(se,b);
                push(s,*b);
            }
        }
        //判断队列是否有等待车辆--有的话对头入栈
        if(Q->rear!=Q->front){ 
            BusInf *b = (BusInf*)malloc(sizeof(BusInf));
            DeleteQueue(Q,b);
            b->pushtime=leavetime;
            push(s,*b);
            showBus(s);
            showQBus(Q);
        }
        else
        showBus(s);
    }
    //菜单选择
    int menu()
    { 
        char n;
        printf("\n ************* 停车场管理系统 **************\n");
        printf(" *%15c1---停车%19c\n",' ','*');
        printf(" *%15c2---离开%19c\n",' ','*');
        printf(" *%15c3---结束程序%15c\n",' ','*');
        printf(" *******************************************\n");
        printf("菜单选择：1,2,3: ");
        do{ 
    	     n=getch();
    	     }while(n<'1' || n>'3');
         printf("\n");
         return(n-48);
    }
    int main()
    { 
        //车辆栈
        SeqStack *s =(SeqStack*)malloc(sizeof(SeqStack));
        InitStack(s);
        //车辆在路边停靠的队列
        LinkQueue *l=(LinkQueue *)malloc(sizeof(LinkQueue));
        InitQueue(l);
        //辅助栈存储让位的信息
        SeqStack *se = (SeqStack*)malloc(sizeof(SeqStack));
        InitStack(se);
        while(1)
        { 
            switch(menu()){ 
                case 1:inputCarData(s,l);
                break;
                case 2:leaveStack(s,se,l);
                break;
                case 3:return 0;
            }
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70]: /images/20211223/a90c6b887e0a480791516d79a065d770.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70 1]: /images/20211223/d5f4cc8b021f40ab90bbb691ea058344.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ2NzI1MQ_size_16_color_FFFFFF_t_70 2]: /images/20211223/d3af0430764b495b841d34ab36d1f2c2.png