Loading...
墨滴

公子宇

2021/12/12  阅读:33  主题:自定义主题1

停车场管理

停车场管理问题

一、问题描述

(1) 实验题目

设停车场是一个可停放 n 辆汽车的狭长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端)。若停车场内已经停满n辆车,那么后来的车只能在门外的便道上等候。一旦有车开走,则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。

(2) 基本要求

以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项:汽车的“到达”(‘A’表示)或“离去”(‘D’表示)信息、汽车标识(牌照号)以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为:若是车辆到达,则输出汽车在停车场内或者便道上的停车位置;若是车辆离去,则输出汽车在停车场停留的时间和应缴纳的费用(便道上停留的时间不收费)。栈以顺序结构实现,队列以链表结构实现。

(3) 测试数据

n=2,输入数据为:(‘A’,1,5),(‘A’,2,10),(‘D’,1,15),(‘A’,3, 20),(‘A’,4,25),(‘A’,5,30),(‘D’,2,35),(‘D’,4,40),(‘E’,0,0)。每一组输入数据包括三个数据项:汽车 “到达”或“离去”信息、汽车牌照号码及到达或离去的时刻,其中,‘A’表示到达;‘D’表示离去,‘E’表示输入结束。其中:(‘A’,1,5)表示1号牌照车在5这个时刻到达,而(‘D’,1,15)表示1号牌照车在15这个时刻离去。

二、需求分析

(1) 程序所能达到的基本可能

  1. 本程序用来求出车辆到达停车场时的位置,以及出站时应缴纳的费用
  2. 程序运行后显示提示信息,引导用户输入命令
  3. 用户输入完毕后,自动输出位置或是费用

(2) 输入和输出的形式

  1. 输入数据:程序接受5个命令,分别是:到达(‘A’,车牌号,时间);离去(‘D’,车牌号,时间);停车场(‘P’, 0, 0)显示停车场的车数;候车场(‘W’, 0, 0)显示候车场的车数;退出(‘E’, 0, 0)退出程序。
  2. 输出数据:对于车辆到达,要输出汽车在停车场内或者便道上的停车位置;对于车辆离去,则输出汽车在停车场应缴纳的费用(便道上不收费)。

三、概要设计

(1) 定义头文件need.h

  1. 创建data类型

  2. 创建栈类型以及相关模块

    SqStack* SqStack_new();
    int SqStack_isEmpty(SqStack *s);
    int SqStack_push(SqStack *s, ElemType x);
    int SqStack_pop(SqStack *s, ElemType *x);
  3. 创建队列类型以及相关模块

    LinkQueue* LQueue_new();
    void LQueue_in(LinkQueue *q, ElemType x);
    int LQueue_isEmpty(LinkQueue *q);
    int LQueue_out(LinkQueue *q, ElemType *x);
    int LQueue_length(LinkQueue *q);

(2) 头文件引用和全局变量声明

#include "need.h"

SqStack *parking;
LinkQueue *waiting;

(3) 模块定义

int calCosts(int t1, int t2);
void printCommand()// 打印提示
void getInput(data* com)// 获取输入
void Arrival(data* com);
data depCar(SqStack *p, int number);
void Departure(data* com);
void numParking(data* com);
void numWaiting(data* com);

(4) 主程序调用关系

  1. 变量声明
  2. 初始化停车场、候车场
  3. 循环运行
    1. 打印提示、获取输入
    2. 判断输入:a, b, c, d, e
    3. 如果是a,调用void Arrival(data* com);
    4. 如果是d,调用void Departure(data* com);
    5. 如果是p,调用void numParking(data* com);
    6. 如果是w,调用void numWaiting(data* com);
    7. 如果是e,退出程序

四、详细设计

(1) 定义必要的数据类型

typedef struct _
{

    char status;
    int number;
    int time;
}data;

#define MAXSIZE 2
#define ElemType data
// 创建栈类型
typedef struct stack
{

    ElemType cap[MAXSIZE];
    int top;
}SqStack;
// 创建队列类型
typedef struct node
{

    ElemType info;
    struct node *next;
}QNode;
typedef struct linkqueue
{

    QNode *head, *tail;
}LinkQueue;

(2) 编写栈、队列的模块

SqStack* SqStack_new()// 初始化一个栈
int SqStack_isEmpty(SqStack *s)// 对栈进行判空
int SqStack_push(SqStack *s, ElemType x)// 将x压入栈中
int SqStack_pop(SqStack *s, ElemType *x)// 从栈顶弹出一个数据,赋给x

LinkQueue* LQueue_new()// 初始化一个队列
void LQueue_in(LinkQueue *q, ElemType x)// x进入队列
int LQueue_isEmpty(LinkQueue *q)// 判断队列是否为空
int LQueue_out(LinkQueue *q, ElemType *x)// 出列一个数据,赋给x
int LQueue_length(LinkQueue *q)// 返回队列的长度

(3) 打印提示模块和获取输入模块

void printCommand()// 打印提示
void getInput(data* com)// 获取输入

(4) Arrival模块

void Arrival(data* com);

调用int SqStack_push(SqStack *s, ElemType x);

  • 如果返回1,则表明压入成功,打印该车的位置,即parking->top + 1
  • 如果返回0,则表明栈已满,推入队列之中,调用int LQueue_length(LinkQueue *q);,返回在队列中的位置

(5) Departure模块

void Departure(data* com);

  1. 调用data depCar(SqStack *p, int number);,从栈中返回指定的一辆车
  2. 调用int calCosts(int t1, int t2);,打印所需支付的费用
  3. 调用int LQueue_out(LinkQueue *q, ElemType *x);,出列一辆车
  4. 如果有车出列,将新的时间赋给该车,这是该车进入停车场的时间
  5. 调用int SqStack_push(SqStack *s, ElemType x);,将该车压入栈中;

(6) numParking模块

void numParking(data* com);

打印parking->top + 1

(7) numWaiting模块

void numWaiting(data* com);

调用int LQueue_length(LinkQueue *q);,返回队列的长度

五、调试分析

(1) 算法编写思路

程序根据5个不同的命令,除最后一个退出命令外,其余皆定义了一个函数。将问题划分成了几个互不相关的模块。这些模块共同需要的底层函数,如栈和队列的进出、判空等放在另一个头文件里。这种做法,即缩减了主模块所在文件的大小,也有利于各个模块的维护。

(2) 算法的时空分析

  • 打印提示函数void printCommand();、获取输入函数void getInput(data* com);Arrival模块、numParking模块、numWaiting模块运算次数为1,时间复杂度为O(1)。
  • Departure模块因为调用了data depCar(SqStack *p, int number);,来从栈中返回指定的车。data depCar(SqStack *p, int number);模块使用了2个循环结构,时间复杂度为O(n)。

六、使用说明

程序运行之后用户按提示输入命令即可

七、调试结果

连续多组测试样例

Commands supported:
 - (A)Arrival             - by entering A(or a),CarNumber,time
 - (D)Departure           - by entering D(or d),CarNumber,time
 - (P)number of car in the Parking   - by entering P(or p),0,0
 - (W)number of car in the Waiting   - by entering W(or w),0,0
 - (E)Exit program                   - by entering E(or e),0,0
Your command: a,1,5
 - Position of car: 1 in the Parking
--------------------------------------------------------------

每一次循环都会打印提示,以下省略

······a,2,10
 - Position of car: 2 in the Parking
······d,1,15
 - The cost of this car: 150
······a,3,20
 - Position of car: 2 in the Parking
······a,4,25
 - Position of car: 1 in the Waiting
······a,5,30
 - Position of car: 2 in the Waiting
······d,2,35
 - The cost of this car: 375
······d,4,40
 - The cost of this car: 75
······e,0,0

八、遇到的问题和解决方法

在编写代码时,我的问题主要出现在获取输入函数void getInput(data* com);Departure模块,总结如下:

(1) 获取字符输入异常

  • 描述

    一开始我使用scanf("%c,%d,%d", &com->status, &com->number, &com->time);来获取输入,但我总是在连续输入两三次之后就会自动跳过一次输入。我意识到这是因为字符输入时缓存空间的问题,但在网上找了一圈,也没找到什么好办法。只好采取了一个另一种思路。

  • 解决办法

    使用scanf("%s", temp);获取一整个字符串,之后采用如下办法:

    com->status = temp[0]; // 字符串的第一个字符赋给status
    com->number = temp[2]-'0'// 字符串的第三个字符赋给number
    // 判断是否为两位数,将值赋给time
    if(temp[5] != 0) com->time = (temp[4]-'0')*10 + temp[5] - '0';
    else com->time = temp[4] - '0';

(2) 车辆离开停车场时

  • 描述

    最初在编写Departure模块时,在车辆离开停车场这一块的部分,我仅仅只是使用了一个栈的弹出模块,之后发现,这只是弹出了最后一个进入停车场的车。

  • 解决办法

    编写一个data depCar(SqStack *p, int number);模块,通过车牌号number来确定停车场里要离开的车,然后以返回值的形式返回。

九、实验收获与感想

  1. 在这次实验中,我充分吸取了Josephus问题的教训,在编写代码时将问题分成了多个模块,每个模块均是相互独立。
  2. 这次实验中,我使用了大量的与栈、队列有关的函数,让我对栈和队列有了更加深入的了解。

十、附录

源程序文件清单:

  • ParkingManagement.c
  • need.h

公子宇

2021/12/12  阅读:33  主题:自定义主题1

作者介绍

公子宇