大数据结构上机--停车场管理系统问题

1、实习指导实习题目:停车场管理。实习内容:首先，实现栈和队列的基本操作，在此基础上，实现停车场管理。停车场管理问题描述：设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端） 若车场内已停满 n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第 一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让 路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停 留时间的长短交费（在便道上停留的时间不收费）。试编写程序，模拟上述管理过程。要求以顺序栈模拟停车

2、场，以链队列模拟便道。从终端读入汽车到达或离去的数据，每组数据包括三项： 是“到达”还是“离去”； 汽车牌照号码； “到达”或“离去”的时刻。与每组输入信息相应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。（提示：需另设一个栈，临时停放为让路而从车场退出的车。）实习目的:通过实习，熟悉栈和队列的基本特点，掌握利用栈和队列解决具体问题的方法。实习步骤:1. 实现顺序栈的基本操作基本思路首先实现一个整型顺序栈的初始化、判栈空、进栈、出栈等基本操作，并在主程序中调用这些操作。基本框架#in elude <stdio

3、.h>#defi ne TRUE 1#defi ne FALSE 0#defi ne Stack_Size 50typedef int StackEleme ntType; typedef structStackEleme ntType elemStack_Size;int top; SeqStack;/*以下是函数原形说明。注意函数头后面有分号。*/void InitStack(SeqStack *s);int IsEmpty(SeqStack *s);int Push(SeqStack *s, StackEleme ntType e);int Pop(SeqStack *s, Sta

4、ckEleme ntType *e);/*以下是函数定义。注意函数头后面无分号。*/void In itStack(SeqStack *s)/*顺序栈的初始化函数*/;int lsEmpty(SeqStack *s)/*顺序栈的判栈空函数 */;int Push(SeqStack *s, StackEleme ntType e)/*顺序栈的进栈函数 */;Status Pop(SeqStack *s, StackEleme ntType *e)/*顺序栈的出栈函数 */;void mai n(void);要点提示主程序的基本过程如下：void mai n(void) SeqStack my_s

5、tack ;StackEleme ntType x;StackEleme ntType y;In itStack(&m y_stack );if(IsEmpty(&my_stack)打印：“ my_stack 已被初始化为空栈”提示输入10个正整数；循环10次，执行下面操作：读入整数X；Push(&m y_stack, x);while(!lsEmpty(&m y_stack)Pop(&m y_stack, &y);打印y;测试数据读入数据：19，14，23，01，68, 20，84, 27, 55, 11打印结果：读入序列的逆序。2. 同时实现

6、顺序栈和链队列的基本操作基本思路在前面已经实现的整型顺序栈的基础上，进一步实现一个整型链队列的基本操作。 基本框架(1 )在上述程序框架的前面，增加如下包含语句：#i nclude <malloc.h>(2) 在上述程序框架的类型定义部分，增加如下链队列定义：typedef int QueueEleme ntType;typedef struct NodeQueueElementType data; /* 数据域 */struct Node*next; /*指针域 */ Lin kQueueNode;typedef structLin kQueueNode * front;Lin

7、kQueueNode * rear; Lin kQueue;(3 )在上述程序框架的函数原型说明部分，增加如下链队列的操作函数原型说明: int InitQueue(LinkQueue * Q);int EmptyQueue(L in kQueue Q);int En terQueue(L in kQueue *Q, QueueEleme ntType x); int DeleteQueue(LinkQueue * Q, QueueElementType *x);(4) 在上述程序框架的函数定义部分，增加上述链队列的操作函数定义。(5) 在上述程序框架的主程序中，增加调用链队列操作函数的有关语

8、句。要点提示主程序的基本过程如下：void mai n(void) SeqStack my_stack ;Lin kQueue my_queue;int x;In itStack(&m y_stack );In itQueue(&m y_queue );if(IsEmpty(&m y_stack)打印："栈为空”；提示输入10个正整数；循环10次，执行下面操作：读入整数X；Push(&m y_stack, x);while(!lsEmpty(&m y_stack)Pop(&m y_stack, &x);将x加入队列my_queu

9、e;while(队歹U my_queue 非空)删除my_queue的队首元素，并送给 x;打印x;注意指针参数的调用方法。测试数据读入数据：19, 14, 23, 01, 68, 20, 84, 27, 55, 11打印结果：读入序列的逆序。3. 实现停车场管理问题基本思路停车场管理问题可以用如下简图说明:暂时退车道便道1F将“车库”和“暂时退车道”定义为两个栈，将“便道”定义为一个队列。在前面程序的基础上，进行如下修改：（1 ）定义一个表示“车辆信息”的结构体类型。（2） 将栈元素类型和队列元素类型均改为“车辆信息”结构体指针类型（或“车辆信息” 结构体类型），并相应修改有关函数。（3）定

10、义一个“车辆到达处理”函数和“车辆离开处理”函数。基本框架（1）在上述程序框架的类型定义部分，增加一个表示“车辆信息”的结构体类型定义， 设置两个数据域：牌照号码、到达时刻。牌照号码用字符串表示，到达时刻可先用正整数表 示（参后面测试数据）。（2 ）在上述程序框架的函数原型说明部分，增加“车辆到达处理”函数和“车辆离开处 理”函数的原型说明。（3）在上述程序框架的函数定义部分，增加“车辆到达处理”函数和“车辆离开处理” 函数的函数定义。（4）为了简化参数传递， 可以先将有关的栈和队列定义为全局变量，调通后再改为用参 数传递。要点提示主程序的基本过程如下：void mai n（void）重复如下

11、过程，直到读入结束标志: 提示输入一辆车的信息（到达 /离开，牌照号码，当前时刻） 读入这辆车的信息；如果是到达车辆，则调用“车辆到达处理”函数； 否则调用“车辆离开处理”函数。“车辆离开处理”函数的基本过程如下：void leave（ 牌照号码，离开时刻）当“车库”栈不空，并且栈顶车辆不是要离开的车时，重复下面操作: 将“车库”栈的栈顶车辆退出； 让退出的车辆进入“暂时退车道”栈；如果找到要离开的车辆，则计算并输出停车费用； 将“暂时退车道”栈中的车辆倒回“车库”栈；如果“便道”队列不空，则队头车辆出队，并进入“车库”栈；注意将“出队车辆”的到达时刻改为“离开车辆”的离开时刻。测试数据假设用

12、0表示车辆离开，1表示车辆到达，-1表示程序结束；用字符串表示车辆的牌照 号码；用正整数表示时刻，每单位时间的停车费用是5元；停车场大小 n=2。则运行结果如下：输入数据：1，A001, 5输出结果：A001当前停放在车库1号位输入数据：1，B002, 10输出结果：B002当前停放在车库2号位输入数据：0，A001，15输出结果：A001停放时间为10,停车费用为50元输入数据：1，C003, 20输出结果：C003当前停放在车库2号位输入数据：1，D004，25输出结果：D004当前停放在便道1号位输入数据：1，E005，30输出结果：E005当前停放在便道2号位输入数据:0, B002,

13、 35输出结果:B002停放时间为25,停车费用为125元便道上的D004进入车库，入库时刻为 35,当前停放在车库 2号位输入数据:0, D004, 40输出结果:D004停放时间为5,停车费用为25元便道上的E005进入车库，入库时刻为40,当前停放在车库 2号位输入数据:-1 , #000, 0输出结果:当前车库中还有 2辆车，便道上无车。再见！改进建议:1. 每次输出结果中，打印整个车库和整个便道的当前停车情况一览表。2. 将车库”栈、"暂时退车道”栈改为对顶栈，共享同一空间。3. 根据车辆类型，分别收费。4. 便道上的车可以直接开走，此时排在它前面的车要依次开出，并排到队尾

14、。5. 停放在便道上的车也收费，但收费标准较低。6. 将时间改为时、分表示法。7. 到达时刻和离开时刻采用本机系统时间。& 用随机数模拟车辆到达间隔和停车时间。9.用动画演示运行过程。源代码：/ park in g.cpp : Defines the entry point for the con sole applicatio n.#i nclude <malloc.h>#i nclude <stdio.h>#include "string.h"#defi ne TRUE 1#defi ne FALSE 0#defi ne Stack_Si

15、ze 2/*车辆信士自 */typedef struct Carrchar Number10;/*车牌号*/int time;/*到达时刻*/ Car;/*车库栈定义 */typedef structCar elemStack_Size; int top; SeqStack;/*暂退车道栈定义*typedef structCar elem2Stack_Size;int top2;列定义 * SeqStack2;未*typedef struct Node指针域*/Car data; /* 数据域 */ struct Node*n ext; /* Lin kQueueNode;typedef st

16、ructLin kQueueNode * front;Lin kQueueNode * rear;int len gth; Lin kQueue;/*以下是函数原形说明。注意函数头后面有分号。*/void InitStack(SeqStack *s);int lsEmpty(SeqStack *s);int Push(SeqStack *s, Car e);int Pop(SeqStack *s, Car *e);int Ini tQueue(L in kQueue * Q);int EmptyQueue(L in kQueue Q);int En terQueue(L in kQueue *

17、Q, Car x);int DeleteQueue(Li nkQueue * Q, Car *x);int CarArrive(SeqStack *s,L in kQueue *Q,char nu m,i nt arrivetime);int CarLeave(SeqStack *s,L in kQueue * Q,SeqStack *s2,char,i nt leavetime );/*以下是函数定义。注意函数头后面无分号。*/void InitStack(SeqStack *s)/*顺序栈的初始化函数*/s->top =-1;int lsEmpty(SeqStack *s)/*顺序栈

18、的判栈空函数 */if(s->top =-1) return(TRUE);elsereturn(FALSE);int lsFull(SeqStack *s)/*顺序栈的判栈满函数*/if(s->top =Stack_Size)return(TRUE);elsereturn(FALSE);int Push(SeqStack *s, Car *e)/*顺序栈的进栈函数*/if(s->top=Stack_Size-1)return(FALSE); elses->top +;s->elem s->top=*e;return(TRUE);int Pop(SeqStac

19、k *s, Car *e)/*顺序栈的出栈函数*/if(s->top =-1)return(FALSE);else*e=s->elem s->top;s->top-;return(TRUE);int Ini tQueue(L in kQueue * Q)/*链队列的初始化*/ Q->le ngth=O;Q->front=( Lin kQueueNode*)malloc(sizeof( Lin kQueueNode);if(Q->fro nt!=NULL)Q->rear=Q->fr ont;Q->fro nt-> next=NUL

20、L; return(TRUE);elsereturn(FALSE);/*溢出 */int EmptyQueue(L in kQueue *Q)/*链队列的判空*/if(Q->fr on t=Q->rear)return(TRUE);elsereturn(FALSE);int En terQueue(L in kQueue *Q,Car *x)/*链队列的入队操作，将数据元素x插入到队列中*/Lin kQueueNode *NewNode;NewNode=(Li nkQueueNode *)malloc(sizeof(Li nkQueueNode);if(NewNode!=NULL)

21、NewNode->data=*x;NewNode-> next=NULL;Q->rear- >n ext=NewNode;Q->rear=NewNode;Q->le ngth+;return(TRUE);elsereturn(FALSE);/ 溢出int DeleteQueue(Li nkQueue * Q,Car *x)/*链队列的出队操作，对头出列，并存放到x所指的储存空间中*/Lin kQueueNode * p;if(Q->fr on t=Q->rear)return(FALSE);p=Q->fr ont->n ext;Q-&

22、gt;front->next=p->next;/*对头元素 p 出列 */if(Q->rear=p) /*如果对中只有一个元素p，贝U p出对后成为空队*/Q->rear=Q->fr ont;*x=p->data;free(p); /*释放存储空间*/Q->le ngth-;return(TRUE);/*车辆到达函数*/int CarArrive(SeqStack *s,L in kQueue *Q,char nu m,i nt arrivetime) Car *come;come=(Car*)malloc(sizeof(Car);strcpy(com

23、e->Number, num);/到达车辆的车牌号come->time =arrivetime;/至 U达车辆的时间if(s->top<Stack_Size-1) /*若车库未满，直接入车库*/Push(s,come);/车辆入栈n");printf(”printf(”车辆 s停在车库 d号位上 n",num,s->top+1);elseEn terQueue(Q, come);/*若车库已满，就入队列 */printf("n");printf(" 车辆 %s停在便道 d号位上 n",num,Q->

24、length); return 0;/*车辆离*/* void Carleave(SeqStack *s,L in kQueue * Q,char nu m,i nt leavetime) SeqStack s2;In itStack(&s2 );Car *Acar;要离开车辆Acar=(Car*)malloc(sizeof(Car);int mon ey,parktime;while(!lsEmpty(s )&&(strcmp(s->elems->top.Number, num)/当"车库"栈不空，并且栈顶车辆不是要离开的车时，重复下面

25、操作：/将"车库"栈的栈顶车辆退出；Pop(s, Acar);/让退出的车辆进入"暂时退车道”栈；Push(&s2,Acar);/如果找到要离开的车辆，则计算并输出停车费用；Pop(s, Acar);parktime=leavetime-Acar->time;mon ey=5*parktime;printf("n");printf("%s的停车时间为 %d 停车费用为 %dn",num,parktime,money);/将"暂时退车道”栈中的车辆倒回”车库”栈；while(!IsEmpty(&

26、s2)Pop(&s2, Acar);Push(s, Acar);/如果”便道”队列不空，则队头车辆出队，并进入 "车库”栈；if(!EmptyQueue(Q)Car *Bcar;出便道进车库的车Bcar=(Car*)malloc(sizeof(Car);DeleteQueue(Q,Bcar);Bcar->time=leavetime; 将”出队车辆”的到达时刻改为”离开车辆”的离开时刻。Push(s,Bcar);printf("便道上的%s进入车库，入库时刻为d,当前停放在车库%d号位n ",Bcar->Number,Bcar->time

27、,s->top+1);/*车 库 停 车 情况一览*/* void prin tfstack(SeqStack s)Car *Ccar;Ccar=(Car*)malloc(sizeof(Car);if(s.top =-1)printf("车库无车 n”);elsewhile(s.top !=-1)*Ccar=s.elem s.top;s.top-; prin tf("%s%dn",Ccar->Number,Ccar->time);/end while/END ELSE便道停 车 情况一览未*/* int prin tfQuee n(Lin kQu

28、eue Q) Car *Dcar;Dcar=(Car*)malloc(sizeof(Car);Lin kQueueNode * p;p=Q.fr ont->n ext;if(Q.fr on t=Q.rear)printf("便道无车 n");return(FALSE);while(Q.fro nt!=Q.rear)*Dcar=p->data;if(Q.rear=p) /*如果对中只有一个元素p,贝U p出对后成为空队*/Q.rear=Q.fro nt;prin tf("%s%dn",Dcar->Number,Dcar->time);p=p->n ext;/ free(p); /* 释放存储空间*/return(TRUE);/*/void mai n(void)char ch;SeqStack my_stack ; Lin kQueue my_queue; I