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

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

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

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

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

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

6、序栈和链队列的基本操作基本思路在前面已经实现的整型顺序栈的基础上，进一步实现一个整型链队列的基本操作。 基本框架(1 )在上述程序框架的前面，增加如下包含语句：#i nclude <malloc.h>(2 )在上述程序框架的类型定义部分，增加如下链队列定义：typedef int QueueEleme ntType; typedef struct NodeQueueEleme ntType struct Node Lin kQueueNode;data;*n ext;/*数据域*/*指针域*/typedef struct* front;* rear;Lin kQueueNodeLi

7、n kQueueNode Lin kQueue;(3 )在上述程序框架的函数原型说明部分，增加如下链队列的操作函数原型说明:int InitQueue(LinkQueue * Q);int EmptyQueue(L in kQueueQ);int En terQueue(L in kQueue *Q, QueueEleme ntType x); int DeleteQueue(LinkQueue * Q, QueueElementType *x);(4 )在上述程序框架的函数定义部分，增加上述链队列的操作函数定义。(5 )在上述程序框架的主程序中，增加调用链队列操作函数的有关语句。要点提示主程

8、序的基本过程如下：voidmai n(void) SeqStack my_stack ;Lin kQueuemy_queue;int x;In itStack(&m y_stack );In itQueue(&m y_queue );if(IsEmpty(&m y_stack)打印："栈为空”；提示输入10个正整数；循环10次，执行下面操作：读入整数X；Push(&m y_stack,x);while(!lsEmpty(&m y_stack)Pop(&m y_stack,&x);将x加入队列 my_queue;while(队歹U

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

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

11、标志: 提示输入一辆车的信息（到达 / 离开，牌照号码，当前时刻） 读入这辆车的信息 ; 如果是到达车辆，则调用“车辆到达处理”函数； 否则调用“车辆离开处理”函数。“车辆离开处理”函数的基本过程如下：void leave（ 牌照号码，离开时刻 ） 当“车库”栈不空，并且栈顶车辆不是要离开的车时，重复下面操作： 将“车库”栈的栈顶车辆退出； 让退出的车辆进入“暂时退车道”栈； 如果找到要离开的车辆，则计算并输出停车费用； 将“暂时退车道”栈中的车辆倒回“车库”栈； 如果“便道”队列不空，则队头车辆出队，并进入“车库”栈；注意将“出队车辆”的到达时刻改为“离开车辆”的离开时刻。测试数据假设用 0

12、 表示车辆离开， 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 号位输入数据

13、： 1，E005 ， 30输出结果： E005 当前停放在便道 2 号位输入数据： 0，B002 ， 35输出结果： B002 停放时间为 25 ，停车费用为 125 元2 号位2 号位便道上的 D004 进入车库，入库时刻为 35 ，当前停放在车库 输入数据： 0，D004 ， 40输出结果： D004 停放时间为 5 ，停车费用为 25 元便道上的 E005 进入车库，入库时刻为 40 ，当前停放在车库 输入数据： -1 ，#000 ，0输出结果：当前车库中还有 2 辆车，便道上无车。再见！改进建议 ：1 每次输出结果中，打印整个车库和整个便道的当前停车情况一览表。2 将车库”栈、 “暂时

14、退车道”栈改为对顶栈，共享同一空间。3 根据车辆类型，分别收费。4 便道上的车可以直接开走，此时排在它前面的车要依次开出，并排到队尾。5 停放在便道上的车也收费，但收费标准较低。6 将时间改为时、分表示法。7 到达时刻和离开时刻采用本机系统时间。8 用随机数模拟车辆到达间隔和停车时间。9 用动画演示运行过程。源代码：/ parking.cpp : Defines the entry point for the console application. #include <malloc.h>#include <stdio.h>#include "string.h

15、"#define TRUE 1#define FALSE 0#define Stack_Size 2*车辆信息 *typedef struct Carchar Number10;int time;/* 车牌号 */ /* 到达时刻 */ Car;*车库栈定义*typedef structCar elemStack_Size; int top; SeqStack;*暂退车道栈定义*typedef structCar elem2Stack_Size;int top2; SeqStack2;队列定义 * typedef struct NodeCar data; /* 数据域 */ Link

16、QueueNode;struct Node*next; /* 指针域 */typedef structLinkQueueNode* front;LinkQueueNode* 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(LinkQueue

17、Q);int EnterQueue(LinkQueue *Q, Car x); int DeleteQueue(LinkQueue * Q, Car *x);int CarArrive(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 I

18、sEmpty(SeqStack *s)/* 顺序栈的判栈空函数 */if(s->top =-1)return(TRUE);elsereturn(FALSE);int IsFull(SeqStack *s) /* 顺序栈的判栈满函数 */ if(s->top =Stack_Size) return(TRUE);else return(FALSE);int Push(SeqStack *s, Car *e) /* 顺序栈的进栈函数 */if(s->top=Stack_Size-1)return(FALSE); elses->top +;s->elem s->to

19、p=*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);int InitQueue(LinkQueue * Q)/* 链队列的初始化 */ Q->length=0;Q->front=( LinkQueueNode*)malloc(sizeof( LinkQueueNode); if(Q->front!=NULL) Q->rear=Q-

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

21、of(LinkQueueNode); if(NewNode!=NULL)NewNode->data=*x; NewNode->next=NULL; Q->rear->next=NewNode;Q->rear=NewNode;Q->length+; return(TRUE);else return(FALSE);/ 溢出int DeleteQueue(LinkQueue * Q,Car *x)/* 链队列的出队操作，对头出列，并存放到 x 所指的储存空间中 */LinkQueueNode * p; if(Q->front=Q->rear) retu

22、rn(FALSE);p=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);车辆到达函数 */*s,LinkQueue *Q,char num,int arrivetime)/*int CarArrive(SeqStackCar *come;

23、come=(Car*)malloc(sizeof(Car); strcpy(come->Number,num);/ 到达车辆的车牌号 come->time =arrivetime;/ 到达车辆的时间 if(s->top<Stack_Size-1) /* 若车库未满，直接入车库 */ Push(s,come);/ 车辆入栈 printf("n");printf(" 车辆 %s 停在车库 %d 号位上 n",num,s->top+1);elseEnterQueue(Q, come);/* 若车库已满，就入队列 */ printf

24、("n");printf(" 车辆 %s 停在便道 %d 号位上 n",num,Q->length); /*车辆离开函数 */*s,LinkQueue * Q,char num,int leavetime)return 0;void Carleave(SeqStack SeqStack s2;InitStack(&s2 );Car *Acar;/ 要离开车辆Acar=(Car*)malloc(sizeof(Car);int money,parktime;while(!IsEmpty(s)&&(strcmp(s->ele

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

26、 %dn",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;

27、/将" 出队车辆 " 的到达时刻改为 "离开车辆 "的离开时刻。Push(s,Bcar);/*printf(”便道上的%s进入车库，入库时刻 为%d，当前停放在车库%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");else while(s.top !=-1) *C

28、car=s.elem s.top; s.top-;printf("%s/end while/END ELSE/*%dn",Ccar->Number,Ccar->time);便道停车情况*/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);*主函数*void main(void) char ch;SeqStack my_stack ; LinkQueue my_queue;InitStack(&my_stack