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

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

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

3、o.h>#define TRUE 1#define FALSE 0#define Stack_Size 50typedef int StackElementType;typedef struct.StackElementTypeelemStack_Size;int top; SeqStack;/* 以下是函数原形说明。注意函数头后面有分号。*/void InitStack(SeqStack*s);int IsEmpty(SeqStack*s);int Push(SeqStack*s,StackElementTypee);int Pop(SeqStack*s,StackElementTyp

4、e*e);/* 以下是函数定义。注意函数头后面无分号。*/void InitStack(SeqStack*s)/* 顺序栈的初始化函数*/;int IsEmpty(SeqStack*s)/* 顺序栈的判栈空函数*/;int Push(SeqStack*s,StackElementTypee)/* 顺序栈的进栈函数*/;Status Pop(SeqStack *s, StackElementType*e)/* 顺序栈的出栈函数*/;voidmain(void);要点提示主程序的基本过程如下：voidmain(void) SeqStack my_stack ; StackElementType x

5、; StackElementType y; InitStack(&my_stack );if(IsEmpty(&my_stack) 打印：“ my_stack 已被初始化为空栈” ;.提示输入10 个正整数；循环 10 次，执行下面操作：读入整数x;Push(&my_stack,x);while(!IsEmpty(&my_stack)Pop(&my_stack,&y);打印 y;测试数据读入数据： 19，14， 23，01， 68，20， 84，27， 55，11打印结果：读入序列的逆序。2 同时实现顺序栈和链队列的基本操作基本思路在前面已经实现

6、的整型顺序栈的基础上，进一步实现一个整型链队列的基本操作。基本框架（ 1）在上述程序框架的前面，增加如下包含语句：#include <malloc.h>（ 2）在上述程序框架的类型定义部分，增加如下链队列定义：typedef int QueueElementType;typedef struct NodeQueueElementTypedata;/* 数据域 */struct Node*next;/* 指针域 */ LinkQueueNode;typedef structLinkQueueNode* front;LinkQueueNode* rear; LinkQueue;（ 3）

7、在上述程序框架的函数原型说明部分，增加如下链队列的操作函数原型说明：.int InitQueue(LinkQueue * Q);int EmptyQueue(LinkQueueQ);int EnterQueue(LinkQueue *Q, QueueElementType x); int DeleteQueue(LinkQueue * Q, QueueElementType *x);（ 4）在上述程序框架的函数定义部分，增加上述链队列的操作函数定义。（ 5）在上述程序框架的主程序中，增加调用链队列操作函数的有关语句。要点提示主程序的基本过程如下：voidmain(void) SeqStackm

8、y_stack ;LinkQueuemy_queue;intx;InitStack(&my_stack );InitQueue(&my_queue );if(IsEmpty(&my_stack)打印：“栈为空” ;提示输入10 个正整数；循环 10 次，执行下面操作：读入整数x;Push(&my_stack,x);while(!IsEmpty(&my_stack)Pop(&my_stack,&x);将 x 加入队列my_queue;while( 队列 my_queue 非空 )删除 my_queue 的队首元素，并送给x;打印 x;注意指

9、针参数的调用方法。测试数据读入数据： 19，14， 23，01， 68，20， 84，27， 55，11打印结果：读入序列的逆序。.3 实现停车场管理问题基本思路停车场管理问题可以用如下简图说明：车库暂时退车道便道将“车库”和“暂时退车道”定义为两个栈，将“便道”定义为一个队列。在前面程序的基础上，进行如下修改：（ 1）定义一个表示“车辆信息”的结构体类型。（ 2）将栈元素类型和队列元素类型均改为 “车辆信息” 结构体指针类型 （或 “车辆信息”结构体类型），并相应修改有关函数。（ 3）定义一个“车辆到达处理”函数和“车辆离开处理”函数。基本框架（ 1）在上述程序框架的类型定义部分，增加一个表

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

11、是到达车辆，则调用“车辆到达处理”函数；否则调用“车辆离开处理”函数。“车辆离开处理”函数的基本过程如下：void leave( 牌照号码，离开时刻)当“车库”栈不空，并且栈顶车辆不是要离开的车时，重复下面操作：将“车库”栈的栈顶车辆退出；让退出的车辆进入“暂时退车道”栈；如果找到要离开的车辆，则计算并输出停车费用；将“暂时退车道”栈中的车辆倒回“车库”栈；如果“便道”队列不空，则队头车辆出队，并进入“车库”栈；注意将“出队车辆”的到达时刻改为“离开车辆”的离开时刻。测试数据假设用 0 表示车辆离开，1 表示车辆到达，-1 表示程序结束；用字符串表示车辆的牌照号码；用正整数表示时刻，每单位时间

12、的停车费用是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， 35输出结果： B002 停放时间为25

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

14、。6 将时间改为时、分表示法。7 到达时刻和离开时刻采用本机系统时间。8 用随机数模拟车辆到达间隔和停车时间。9 用动画演示运行过程。源代码：/ parking.cpp : Defines the entry point for the console application. #include <malloc.h>#include <stdio.h> #include "string.h" #define TRUE 1 #define FALSE 0 #define Stack_Size 2/*车辆信息 */typedef struct Carch

15、ar Number10;/* 车牌号 */int time;/* 到达时刻 */ Car;/*车库栈定义 */typedef struct.Car elemStack_Size;int top; SeqStack;/*暂退车道栈定义*/typedef structCar elem2Stack_Size;int top2; SeqStack2;/*队列定义 */typedef struct NodeCardata;/* 数据域 */struct Node*next;/* 指针域 */ LinkQueueNode;typedef structLinkQueueNode* front;LinkQue

16、ueNode* rear;int length; LinkQueue;/* 以下是函数原形说明。注意函数头后面有分号。*/void InitStack(SeqStack*s);int IsEmpty(SeqStack*s);int Push(SeqStack*s,Care);int Pop(SeqStack*s,Car*e);int InitQueue(LinkQueue * Q);int EmptyQueue(LinkQueueQ);int EnterQueue(LinkQueue *Q, Car x);int DeleteQueue(LinkQueue * Q, Car *x);int C

17、arArrive(SeqStack*s,LinkQueue*Q,char num,int arrivetime);int CarLeave(SeqStack*s,LinkQueue * Q,SeqStack*s2,char,int leavetime );/*以下是函数定义。注意函数头后面无分号。*/.void InitStack(SeqStack*s)/* 顺序栈的初始化函数*/s->top =-1;int IsEmpty(SeqStack*s)/* 顺序栈的判栈空函数*/if(s->top =-1)return(TRUE);elsereturn(FALSE);int IsFul

18、l(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(SeqStack*s,Car*e)./* 顺序栈的出栈函数*/if(s->top =-1)return(FALSE);else*e=s->el

19、em s->top;s->top-;return(TRUE);intInitQueue(LinkQueue * Q)/* 链队列的初始化*/ Q->length=0;Q->front=( LinkQueueNode*)malloc(sizeof( LinkQueueNode); if(Q->front!=NULL)Q->rear=Q->front;Q->front->next=NULL;return(TRUE);elsereturn(FALSE);/* 溢出 */int EmptyQueue(LinkQueue *Q)/* 链队列的判空*/

20、if(Q->front=Q->rear)return(TRUE);elsereturn(FALSE);int EnterQueue(LinkQueue *Q,Car *x)/* 链队列的入队操作，将数据元素x 插入到队列中*/LinkQueueNode *NewNode;NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode);.if(NewNode!=NULL)NewNode->data=*x;NewNode->next=NULL;Q->rear->next=NewNode;Q->rear=NewNo

21、de;Q->length+;return(TRUE);elsereturn(FALSE);/ 溢出int DeleteQueue(LinkQueue * Q,Car *x)/* 链队列的出队操作，对头出列，并存放到x 所指的储存空间中*/LinkQueueNode * p;if(Q->front=Q->rear)return(FALSE);p=Q->front->next;Q->front->next=p->next;/* 对头元素p 出列 */if(Q->rear=p)/* 如果对中只有一个元素p，则 p 出对后成为空队*/Q->r

22、ear=Q->front;*x=p->data;free(p); /* 释放存储空间 */Q->length-;return(TRUE);/*车辆到达函数*/int CarArrive(SeqStack*s,LinkQueue*Q,char num,int arrivetime)Car *come;come=(Car*)malloc(sizeof(Car);strcpy(come->Number,num);/ 到达车辆的车牌号 come->time =arrivetime;/ 到达车辆的时间 if(s->top<Stack_Size-1) /* 若车库

23、未满，直接入车库 */ Push(s,come);/车辆入栈printf("-n");.printf(" 车辆 %s 停在车库 %d 号位上 n",num,s->top+1);elseEnterQueue(Q, come);/* 若车库已满，就入队列*/printf("-n");printf(" 车辆 %s 停在便道 %d 号位上 n",num,Q->length);return 0;/*车辆离开函数*/void Carleave(SeqStack*s,LinkQueue * Q,char num,in

24、t leavetime)SeqStacks2;InitStack(&s2 );Car *Acar;/ 要离开车辆Acar=(Car*)malloc(sizeof(Car);int money,parktime;while(!IsEmpty(s)&&(strcmp(s->elems->top.Number,num)/ 当 "车库 "栈不空，并且栈顶车辆不是要离开的车时，重复下面操作：/ 将 "车库 "栈的栈顶车辆退出；Pop(s, Acar);/ 让退出的车辆进入 " 暂时退车道 "栈；Push(&a

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

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

27、ar->Number,Bcar->time,s->top+1);/*车库停车情况一览表函数*/void printfstack(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-;printf("%s %dn",Ccar->Number,Ccar->time); /end while/END ELSE/*便道停车情况一览表

28、函数*/int printfQueen(LinkQueueQ) Car *Dcar; Dcar=(Car*)malloc(sizeof(Car);LinkQueueNode * p;.p=Q.front->next;if(Q.front=Q.rear)printf(" 便道无车 n");return(FALSE);while(Q.front!=Q.rear)*Dcar=p->data;if(Q.rear=p)/* 如果对中只有一个元素p，则 p 出对后成为空队*/Q.rear=Q.front;printf("%s%dn",Dcar->Number,Dcar->time);p=p->next;/ free(p); /* 释放存储空间 */return(TRUE);/*主函数*/voidmain(void)char ch;SeqStackmy_stack ;LinkQueuemy_queue;InitStack(&my_stack );InitQueue(&m