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

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

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

3、RUE 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,StackElementType*e);/*以下是函数定

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

5、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 同时实现顺序栈和链队列的基本操作基本思路在前面已经实现的整型顺序栈的基础上，进一步实现一个整型链队列的基本操作。基本框架（ 1 ）

6、在上述程序框架的前面，增加如下包含语句：#include （ 2 ）在上述程序框架的类型定义部分，增加如下链队列定义： typedef int QueueElementType;typedef struct NodeQueueElementTypedata;/* 数据域 */struct Node*next;/* 指针域 */ LinkQueueNode;typedef structLinkQueueNode* front;LinkQueueNode* rear; LinkQueue;（ 3 ）在上述程序框架的函数原型说明部分，增加如下链队列的操作函数原型说明：精选资料-int InitQue

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

8、(&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;注意指针参数的调用方法。测试数据读入数据： 19 ，14 ，23 ，01 ，68 ，20 ，84 ，27 ，55 ，11打印结果：读入序列的逆序。精

9、选资料-3 实现停车场管理问题基本思路停车场管理问题可以用如下简图说明：车库暂时退车道便道将“车库”和“暂时退车道”定义为两个栈，将“便道”定义为一个队列。在前面程序的基础上，进行如下修改：（ 1 ）定义一个表示“车辆信息”的结构体类型。（ 2 ）将栈元素类型和队列元素类型均改为 “车辆信息” 结构体指针类型 （或 “车辆信息”结构体类型），并相应修改有关函数。（ 3 ）定义一个“车辆到达处理”函数和“车辆离开处理”函数。基本框架（ 1 ）在上述程序框架的类型定义部分，增加一个表示“车辆信息”的结构体类型定义，设置两个数据域：牌照号码、到达时刻。牌照号码用字符串表示，到达时刻可先用正整数表示（

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

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

12、001 当前停放在车库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 ，停车费用为 125元便道上的D004进入车库，入库时刻为35 ，当前停放在车库2 号

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

14、。8 用随机数模拟车辆到达间隔和停车时间。9 用动画演示运行过程。源代码：/ parking.cpp : Defines the entry point for the console application. #include #include #include string.h #define TRUE 1 #define FALSE 0 #define Stack_Size 2/*车辆信息 */typedef struct Carchar Number10;/* 车牌号 */int time;/* 到达时刻 */ Car;/*车库栈定义 */typedef struct精选资料-Car

15、elemStack_Size;int top; SeqStack;/*暂退车道栈定义*/typedef structCar elem2Stack_Size;int top2; SeqStack2;/*队列定义 */typedef struct NodeCardata;/* 数据域 */struct Node*next;/* 指针域 */ LinkQueueNode;typedef structLinkQueueNode* front;LinkQueueNode* rear;int length; LinkQueue;/*以下是函数原形说明。注意函数头后面有分号。*/void InitStack

16、(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 CarArrive(SeqStack*s,LinkQueue*Q,char num,int arrivetime);int CarLeave(SeqSt

17、ack*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 IsFull(SeqStack*s)/*顺序栈的判栈满函数*/if(s-top =Stack_Size)return(TRUE);elsereturn(FALSE);int

18、 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-elem s-top;s-top-;return(TRUE);intInitQueue(LinkQueue * Q)/* 链队列的初始化*/ Q-length=0;Q-front=( LinkQueueNode*)mal

19、loc(sizeof( LinkQueueNode);if(Q-front!=NULL)Q-rear=Q-front;Q-front-next=NULL;return(TRUE);elsereturn(FALSE);/* 溢出 */int EmptyQueue(LinkQueue *Q)/* 链队列的判空 */if(Q-front=Q-rear)return(TRUE);elsereturn(FALSE);int EnterQueue(LinkQueue *Q,Car *x)/* 链队列的入队操作，将数据元素x 插入到队列中*/LinkQueueNode *NewNode;NewNode=(L

20、inkQueueNode *)malloc(sizeof(LinkQueueNode);if(NewNode!=NULL)精选资料-NewNode-data=*x;NewNode-next=NULL;Q-rear-next=NewNode;Q-rear=NewNode;Q-length+;return(TRUE);elsereturn(FALSE);/溢出int DeleteQueue(LinkQueue * Q,Car *x)/* 链队列的出队操作，对头出列，并存放到x 所指的储存空间中*/LinkQueueNode * p;if(Q-front=Q-rear)return(FALSE);p

21、=Q-front-next;Q-front-next=p-next;/* 对头元素p 出列 */if(Q-rear=p)/* 如果对中只有一个元素p ，则 p 出对后成为空队*/Q-rear=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);/到达车辆的车牌号

22、come-time =arrivetime;/到达车辆的时间if(s-toptop+1);精选资料-elseEnterQueue(Q, come);/*若车库已满，就入队列*/printf(-n);printf(车辆 %s 停在便道 %d 号位上 n,num,Q-length);return 0;/*车辆离开函数*/void Carleave(SeqStack*s,LinkQueue * Q,char num,int leavetime) SeqStacks2;InitStack(&s2 );Car *Acar;/要离开车辆Acar=(Car*)malloc(sizeof(Car);int m

23、oney,parktime;while(!IsEmpty(s)&(strcmp(s-elems-top.Number,num)/ 当 车库 栈不空，并且栈顶车辆不是要离开的车时，重复下面操作：/ 将 车库 栈的栈顶车辆退出；Pop(s, Acar);/ 让退出的车辆进入 暂时退车道 栈；Push(&s2,Acar);/ 如果找到要离开的车辆，则计算并输出停车费用；Pop(s, Acar);parktime=leavetime-Acar-time;money=5*parktime;printf(-n);printf(%s的停车时间为 %d ，停车费用为 %dn,num,parktime,mone

24、y);/ 将 暂时退车道 栈中的车辆倒回 车库 栈；while(!IsEmpty(&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 ，当前 停放 在车

25、库 %d 号 位 n,Bcar-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/*便道停车情况一览表函数*/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=