停车场(注释)数据结构.doc

2.3 栈与队列的应用 typedef struct {char license_plate; /*汽车牌照号码，定义为一个字符指针类型*/ float time; /*汽车进入停车场的时刻*/ char state; /*汽车当前状态，字符p表示停放在停车位上，字符q表示停放在便道上*/ }Car； ② 由于车位是一个狭长的通道，不允许两辆车同时出入停车位，当有车到来时要进入停车位的时候也要顺次停放，当某辆车要离开时，比它后到的车要先暂时离开停车位，而且越后到的车就越先离开停车位，显然这与栈的“后进先出”特点相吻合，因此用栈来描述停车场是合适的。由于停车位只能停放有限辆车，而且为了便于停车厂的管理，为每个车位要分配一个固定的编号，不妨设为1、2、3、4、5、…（可利用数组的下标），分别表示停车位的1车位、2车位、3车位、4车位、5车位、…。 综上所述，使用一个顺序栈表示停车场比较方便，具体定义如下： #define MAX_PARK 5 typedef struct {Car Pack[MAX_PARK]; /*各汽车信息的存储空间*/ int top; /*用来指示栈顶位置的指针*/ }ParkStack; ③ 当停车场的停车位上都已经停满了汽车，又有新的汽车到来时要把它停放在便道上，车辆要按照进入便道的先后顺序顺次存放在便道上；当有车从停车场上离开后，便道上等候的第一辆汽车就立即进入停车场中空出的某个车位。由于问题描述中限制了便道上的汽车不能从便道上开走，即便道上的汽车只有在停车位上停放过之后才能离开停车厂，这样越早进入便道的汽车就越早进入停车位，而且每次进入停车位的汽车都是处于便道“最前面”的汽车，显然，这和队列“先进先出”的特点相吻合。 综上所述，使用链队列来模拟便道比较合适，类型定义如下： typedef struct qnode {Car data; /*各汽车信息的存储空间*/ struct qnode *next; }Qnode; typedef struct {Qnode *front, *rear; /*用来指示队头和队尾位置的指针*/ }RoadQueue; ④ 当某辆车要离开停车场的时候，比它后进停车场的车要为它让路，而且当它开走之后让路的车还要按照原来的停放次序再次进入停车位的某个车位上，为了完成这项功能，需要再定义一个辅助栈，停车位中让路的车依次“压入”辅助栈，待提出开走请求的车开走后再从辅助栈的栈顶依次“弹出”到停车位中。对辅助栈也可采用顺序栈，与停车场栈类似： typedef struct {CAR BUFFER[MAX_PARK]; /*各汽车信息的存储空间*/ int top; /*用来指示栈顶位置的静态指针*/ }BUFFER; 3．基本功能分析 ① 主控功能：介绍程序的基本功能，并给出程序功能所对应的键盘操作的提示，如车到来或离去的表示方法，停车场或者便道的状态的查询方法提示等。 ② 汽车到来：首先要查询当前停车场的状态，当停车场非满时，将其驶入停车场（入栈），开始计费；当停车场满时，让其进入便道等候（入队）。 ③ 汽车离开停车场：当某辆车要离开停车场的时候，比它后进停车场的车要为它让路，（即将这些车依次“压入”辅助栈），开走请求离开的车，再将辅助栈中的车依次出栈，“压入”停车场；同时根据离开的车在停车场停留的时间进行收费；最后查询是否有车在便道等候，若有，将便道上的第一辆车驶入停车场（先出队，再入栈），开始交费。 ④ 状态查询：用来在屏幕上显示停车位和便道上各位置的状态。 四．测试数据 1．当停车场容量为2时，（‘A’、“F001”、5），(‘A’、“A002”、10)，(‘D’、“F001”、15)，(‘A’、“F003”、20)，（‘A’、“C004”、25），（‘A’、“B005”、30），(‘D’、“A002”、35)，(‘D’、“C004”、40)，(‘E’、0、0)。 其中：‘A’表示到达（Arrival）;‘D’表示离去（Departure）;‘E’表示输入结束（End）。 2．当停车场容量为5时，连续有7辆车到来，牌照号分别为F001、F002、F003、F004、、F005、F006、F007，前5辆车应该进入停车位1－5车位，第6、7辆车应停入便道的1、2位置上。牌照号为F003的汽车从停车厂开走，应显示F005、F004的让路动作和F006从便道到停车位上的动作。（到达和离开时间请自行设定） 3．随时检查停车位和便道的状态，不应该出现停车位有空位而便道上还有车的情况。 4．程序容错性的测试，当按键输入错误的时候是否有错误