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

217实习指导[实习题目]：停车场管理。[实习内容]：首先，实现栈和队列的基本操作，在此基础上，实现停车场管理。停车场管理问题描述：设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。试编写程序，模拟上述管理过程。要求以顺序栈模拟停车场，以链队列模拟便道。从终端读入汽车到达或离去的数据，每组数据包括三项：①是“到达”还是“离去”；②汽车牌照号码；③“到达”或“离去”的时刻。与每组输入信息相应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。（提示：需另设一个栈，临时停放为让路而从车场退出的车。）[实习目的]：通过实习，熟悉栈和队列的基本特点，掌握利用栈和队列解决具体问题的方法。[实习步骤]：1．实现顺序栈的基本操作基本思路首先实现一个整型顺序栈的初始化、判栈空、进栈、出栈等基本操作，并在主程序中调用这些操作。基本框架#includestdio.h#defineTRUE1#defineFALSE0#defineStack_Size50typedefintStackElementType;typedefstruct218{StackElementTypeelem[Stack_Size];inttop;}SeqStack;/*以下是函数原形说明。注意函数头后面有分号。*/voidInitStack(SeqStack*s);intIsEmpty(SeqStack*s);intPush(SeqStack*s,StackElementTypee);intPop(SeqStack*s,StackElementType*e);/*以下是函数定义。注意函数头后面无分号。*/voidInitStack(SeqStack*s)/*顺序栈的初始化函数*/{……;}intIsEmpty(SeqStack*s)/*顺序栈的判栈空函数*/{……;}intPush(SeqStack*s,StackElementTypee)/*顺序栈的进栈函数*/{……;}StatusPop(SeqStack*s,StackElementType*e)/*顺序栈的出栈函数*/{……;}voidmain(void){……;}要点提示主程序的基本过程如下：voidmain(void){SeqStackmy_stack;StackElementTypex;StackElementTypey;InitStack(&my_stack);if(IsEmpty(&my_stack))打印：“my_stack已被初始化为空栈”;219提示输入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）在上述程序框架的前面，增加如下包含语句：#includemalloc.h（2）在上述程序框架的类型定义部分，增加如下链队列定义：typedefintQueueElementType;typedefstructNode{QueueElementTypedata;/*数据域*/structNode*next;/*指针域*/}LinkQueueNode;typedefstruct{LinkQueueNode*front;LinkQueueNode*rear;}LinkQueue;（3）在上述程序框架的函数原型说明部分，增加如下链队列的操作函数原型说明：220intInitQueue(LinkQueue*Q);intEmptyQueue(LinkQueueQ);intEnterQueue(LinkQueue*Q,QueueElementTypex);intDeleteQueue(LinkQueue*Q,QueueElementType*x);（4）在上述程序框架的函数定义部分，增加上述链队列的操作函数定义。（5）在上述程序框架的主程序中，增加调用链队列操作函数的有关语句。要点提示主程序的基本过程如下：voidmain(void){SeqStackmy_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;}}注意指针参数的调用方法。测试数据读入数据：19，14，23，01，68，20，84，27，55，11打印结果：读入序列的逆序。2213．实现停车场管理问题基本思路停车场管理问题可以用如下简图说明：将“车库”和“暂时退车道”定义为两个栈，将“便道”定义为一个队列。在前面程序的基础上，进行如下修改：（1）定义一个表示“车辆信息”的结构体类型。（2）将栈元素类型和队列元素类型均改为“车辆信息”结构体指针类型（或“车辆信息”结构体类型），并相应修改有关函数。（3）定义一个“车辆到达处理”函数和“车辆离开处理”函数。基本框架（1）在上述程序框架的类型定义部分，增加一个表示“车辆信息”的结构体类型定义，设置两个数据域：牌照号码、到达时刻。牌照号码用字符串表示，到达时刻可先用正整数表示（参后面测试数据）。（2）在上述程序框架的函数原型说明部分，增加“车辆到达处理”函数和“车辆离开处理”函数的原型说明。（3）在上述程序框架的函数定义部分，增加“车辆到达处理”函数和“车辆离开处理”函数的函数定义。（4）为了简化参数传递，可以先将有关的栈和队列定义为全局变量，调通后再改为用参数传递。要点提示主程序的基本过程如下：voidmain(void){重复如下过程，直到读入结束标志：车库便道暂时退车道222{提示输入一辆车的信息（到达/离开，牌照号码，当前时刻）；读入这辆车的信息;如果是到达车辆，则调用“车辆到达处理”函数；否则调用“车辆离开处理”函数。}}“车辆离开处理”函数的基本过程如下：voidleave(牌照号码，离开时刻){当“车库”栈不空，并且栈顶车辆不是要离开的车时，重复下面操作：{将“车库”栈的栈顶车辆退出；让退出的车辆进入“暂时退车道”栈；}如果找到要离开的车辆，则计算并输出停车费用；将“暂时退车道”栈中的车辆倒回“车库”栈；如果“便道”队列不空，则队头车辆出队，并进入“车库”栈；}注意将“出队车辆”的到达时刻改为“离开车辆”的离开时刻。测试数据假设用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号位223输入数据：0，B002，35输出结果：B002停放时间为25，停车费用为125元便道上的D004进入车库，入库时刻为35，当前停放在车库2号位输入数据：0，D004，40输出结果：D004停放时间为5，停车费用为25元便道上的E005进入车库，入库时刻为40，当前停放在车库2号位输入数据：-1，#000，0输出结果：当前车库中还有2辆车，便道上无车。再见！[改进建议]：1．每次输出结果中，打印整个车库和整个便道的当前停车情况一览表。2．将车库”栈、“暂时退车道”栈改为对顶栈，共享同一空间。3．根据车辆类型，分别收费。4．便道上的车可以直接开走，此时排在它前面的车要依次开出，并排到队尾。5．停放在便道上的车也收费，但收费标准较低。6．将时间改为时、分表示法。7．到达时刻和离开时刻采用本机系统时间。8．用随机数模拟车辆到达间隔和停车时间。9．用动画演示运行过程。源代码：//parking.cpp:Definestheentrypointfortheconsoleapplication.#includemalloc.h#includestdio.h#includestring.h#defineTRUE1#defineFALSE0#defineStack_Size2/**************车辆信息******************/typedefstructCar{charNumber[10];/*车牌号*/inttime;/*到达时刻*/}Car;/******************车库栈定义**********************/typedefstruct224{Carelem[Stack_Size];inttop;}SeqStack;/******************暂退车道栈定义**********************/typedefstruct{Carelem2[Stack_Size];inttop2;}SeqStack2;/*****************队列定义******************/typedefstructNode{Cardata;/*数据域*/structNode*next;/*指针域*/}LinkQueueNode;typedefstruct{LinkQueueNode*front;LinkQueueNode*rear;intlength;}LinkQueue;/*以下是函数原形说明。注意函数头后面有分号。*/voidInitStack(SeqStack*s);intIsEmpty(SeqStack*s);intPush(SeqStack*s,Care);intPop(SeqStack*s,Car*e);intInitQueue(LinkQueue*Q);intEmptyQueue(LinkQueueQ);intEnterQueue(LinkQueue*Q,Carx);intDeleteQueue(LinkQueue*Q,Car*x);intCarArrive(SeqStack*s,LinkQueue*Q,charnum[],intarrivetime);intCarLeave(SeqStack*s,LinkQueue*Q,SeqStack*s2,char[],intleavetime);/**********以下是函数定义。注意函数头后面无分号。********/225voidInitStack(SeqStack*s)/*顺序栈的初始化函数*/{s-top=-1;}intIsEmpty(SeqStack*s)/*顺序栈的判栈空函数*/{if(s-top==-1)return(TRUE);elsereturn(FALSE);}intIsFu