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

实习指导[实习题目]：泊车场管理。[实习内容]：第一，实现栈和行列的基本操作，在此基础上，实现泊车场管理。泊车场管理问题描绘：设泊车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车出入。在泊车场内，汽车按抵达的先后序次，由北向南挨次摆列（假定大门在最南端）若车场内已停满n辆车，则以后的汽车需在门外的便道上等待，当有车开走时，便道上的第一辆车即可开入。当泊车场内某辆车要走开时，在它以后进入的车辆一定先退出车场为它让路，待该辆车开出大门后，其余车辆再按原序次返回车场。每辆车走开泊车场时，应按其停

。留时间的长短交费（在便道上逗留的时间不收费）。试编写程序，模拟上述管理过程。要求以次序栈模拟泊车场，以链行列模拟便道。从终端读入汽车抵达或离开的数据，每组数据包含三项：①是“抵达”仍是“离开”；②汽车牌照号码；③“抵达”或“离开”的时刻。与每组输入信息相应的输出信息为：假如是抵达的车辆，则输出其在泊车场中或便道上的地点；假如是离开的车辆，则输出其在泊车场中逗留的时间和应交的花费。（提示：需另设一个栈，暂时停放为让路而从车场退出的车。）[实习目的]：经过实习，熟习栈和行列的基本特色，掌握利用栈和行列解决详细问题的方法。[实习步骤]：1．实现次序栈的基本操作基本思路第一实现一个整型次序栈的初始化、判栈空、进栈、出栈等基本操作，并在主程序中调用这些操作。基本框架#include<>#defineTRUE1#defineFALSE0#defineStack_Size50typedefintStackElementType;typedefstruct{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已被初始化为空栈”;提示输入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）在上述程序框架的前面，增添以下包含语句：#include<>2）在上述程序框架的种类定义部分，增添以下链行列定义：typedefintQueueElementType;typedefstructNode{QueueElementTypedata;structNode*next;/*

/*

数据域*/指针域

*/}LinkQueueNode;typedefstruct{LinkQueueNode*front;LinkQueueNode*rear;}LinkQueue;3）在上述程序框架的函数原型说明部分，增添以下链行列的操作函数原型说明：intInitQueue(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打印结果：读入序列的逆序。3．实现泊车场管理问题基本思路泊车场管理问题能够用以下简图说明：车库暂时退车道便道将“车库”和“暂时退车道”定义为两个栈，将“便道”定义为一个行列。在前面程序的基础上，进行以下改正：1）定义一个表示“车辆信息”的构造体种类。2）将栈元素种类和行列元素种类均改为“车辆信息”构造体指针种类（或“车辆信息”构造体种类），并相应改正相关函数。3）定义一个“车辆抵达办理”函数和“车辆走开办理”函数。基本框架1）在上述程序框架的种类定义部分，增添一个表示“车辆信息”的构造体种类定义，设置两个数据域：牌照号码、抵达时刻。牌照号码用字符串表示，抵达时刻可先用正整数表示（参后边测试数据）。2）在上述程序框架的函数原型说明部分，增添“车辆抵达办理”函数和“车辆走开办理”函数的原型说明。3）在上述程序框架的函数定义部分，增添“车辆抵达办理”函数和“车辆走开办理”函数的函数定义。4）为了简化参数传达，能够先将相关的栈和行列定义为全局变量，调通后再改为用参数传达。重点提示主程序的基本过程以下：voidmain(void){重复以下过程，直到读入结束标记：{提示输入一辆车的信息（抵达/走开，牌照号码，目前时刻）；读入这辆车的信息;假如是抵达车辆，则调用“车辆抵达办理”函数；不然调用“车辆走开办理”函数。}}“车辆走开办理”函数的基本过程以下：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号位输入数据：0，B002，35输出结果：B002停放时间为25，泊车花费为125元便道上的D004进入车库，入库时刻为35，目前停放在车库2号位输入数据：0，D004，40输出结果：D004停放时间为5，泊车花费为25元便道上的E005进入车库，入库时刻为40，目前停放在车库输入数据：-1，#000，0输出结果：目前车库中还有2辆车，便道上无车。再会！

2号位[改良建议]：1．每次输出结果中，打印整个车库和整个便道的目前泊车状况一览表。2．将车库”栈、“暂时退车道”栈改为对顶栈，共享同一空间。3．依据车辆种类，分别收费。4．便道上的车能够直接开走，此时排在它前面的车要挨次开出，并排到队尾。5．停放在便道上的车也收费，但收费标准较低。6．将时间改为时、分表示法。7．抵达时刻和走开时刻采纳本机系统时间。8．用随机数模拟车辆抵达间隔和泊车时间。9．用动画演示运转过程。源代码：#include<>#include<>#include""#defineTRUE1#defineFALSE0#defineStack_Size2/**************车辆信息******************/typedefstructCar{charNumber[10];inttime;/*

/*

车牌号*/抵达时刻*/}Car;/******************车库栈定义**********************/typedefstruct{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);/**********以下是函数定义。注意函数头后边无分号。********/voidInitStack(SeqStack*s)/*次序栈的初始化函数*/{s->top=-1;}intIsEmpty(SeqStack*s)/*次序栈的判栈空函数*/{if(s->top==-1)return(TRUE);elsereturn(FALSE);}intIsFull(SeqStack*s)/*次序栈的判栈满函数*/{if(s->top==Stack_Size)return(TRUE);elsereturn(FALSE);}intPush(SeqStack*s,Car*e)/*次序栈的进栈函数*/{if(s->top==Stack_Size-1)return(FALSE);else{s->top++;s->elem[s->top]=*e;return(TRUE);}}intPop(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*)malloc(sizeof(LinkQueueNode));if(Q->front!=NULL){Q->rear=Q->front;Q->front->next=NULL;return(TRUE);}elsereturn(FALSE);/*溢出*/}intEmptyQueue(LinkQueue*Q)/*链行列的判空*/{if(Q->front==Q->rear)return(TRUE);elsereturn(FALSE);}intEnterQueue(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=NewNode;Q->length++;return(TRUE);}elsereturn(FALSE);umber,num)))当"车库"栈不空，而且栈顶车辆不是要走开的车时，重复下边操作：{将"车库"栈的栈顶车辆退出；Pop(s,Acar);让退出的车辆进入"暂时退车道"栈；Push(&s2,Acar);}假如找到要走开的车辆，则计算并输出泊车花费；Pop(s,Acar);parktime=leavetime-Acar->time;money=5*parktime;printf("-------------------------------------\n");printf("%s的泊车时间为%d，泊车花费为%d\n",num,parktime,money);将"暂时退车道"栈中的车辆倒回"车库"栈；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，目前停放在车库%d号位\n",Bcar->Number,Bcar->time,s->top+1);}}/***********************车库泊车状况一览表函数*******************************************/voidprintfstack(SeqStacks){Car*Ccar;Ccar=(Car*)malloc(sizeof(Car));if==-1)printf("车库无车\n");else{while!=-1){*Ccar=[];;printf("%s%d\n",Ccar->Number,Ccar->time);}//endwhile}//ENDELSE}/***********************便道泊车状况一览表函数*******************************************/intprintfQueen(LinkQueueQ){Car*Dcar;Dcar=(Car*)malloc(sizeof(Car));LinkQueueNode*p;p=>next;if=={printf("便道无车\n");return(FALSE);}while!={*Dcar=p->data;if==p)/*假如对中只有一个元素p，则p出对后成为空队*/=;printf("%s%d\n",Dcar->Number,Dcar->time);p=p->next;free(p);/*开释储存空间*/}return(TRUE);}/***************************

主

函

数**************************************************/voidmain(void){charch;SeqStackmy_stack;LinkQueuemy_queue;InitStack(&my_stack);InitQueue(&my_queue);while(1){intt;printf("*************************************\n");printf("

WELCO