停车场管理系统__C语言实现.doc

. .
一．问题描述
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这个时刻离去。
4.简述每一局部的对象、目的和要求：
I.主函数局部：
对象：栈，队列；
目的：创立栈和队列对停车场管理系统进展模拟；
要求：对栈和队列进展初始化。
II．被调函数局部：
对象：栈和队列中的结点〔亦即车辆的信息〕；
目的：将结点存放到栈和队列中，并作出正确的处理；
要求：根据各结点的信息，调用相应的函数或者语句，将结点入栈入队，出栈或者出队。
二． 需求分析
1.程序所能到达的根本可能：
程序以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进展模拟管理。栈以顺序构造实现，队列以链表构造实现。同时另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车。输入数据按到达或离去的时刻有序。当输入数据包括数据项为汽车的“到达〞〔‘A’表示〕信息，汽车标识〔牌照号〕以及到达时刻时，应输出汽车在停车场或者便道上的停车位置；当输入数据包括数据项为汽车的“离去〞〔‘D’表示〕信息，汽车标识〔牌照号〕以及离去时刻时，应输出汽车在停车场停留的时间和应缴纳的费用〔便道上停留的时间不收费〕；当输入数据项为〔‘P’，0，0〕时，应输出停车场的车数；当输入数据项为〔‘W’, 0, 0〕时，应输出候车场车数；当输入数据项为〔‘E’, 0, 0〕，退出程序；假设输入数据项不是以上所述，就输出"ERROR!"。
2.输入输出形式及输入值围：
程序运行后进入循环，显示提示信息：“Please input the state,number and time of the car:〞，提示用户输入车辆信息〔“到达〞或者“离开〞，车牌编号，到达或者离开的时间〕。假设车辆信息为“到达〞，车辆信息开场进栈〔模拟停车场〕，当栈满，会显示栈满信息：“The parking place is full!〞，同时车辆进队列〔模拟停车场旁便道〕，并显示该进入便道车辆的车牌编号，让用户知道该车的具体位置；假设车辆信息为“离开〞，会显示该车进入停车场的时间以及相应的停车费用，假设该车较局部车早进停车场，这局部车需先退出停车场，暂时进入一个新栈为其让道，会显示进入新栈的车辆的车牌编号及其入停车场的时间，当待离开车离开停车场后，这局部车会重新进入停车场，同时便道上的第一辆车进入停车场；假设输入〔‘P’，0，0〕，会显示停车场的车数；假设输入〔‘W’，0，0〕，会显示便道上的车数；假设输入〔‘E’，0，0〕，程序会跳出循环，同时程序完毕；假设输入为其他字母，程序会显示“ERROR！〞报错。假设便道上没有车辆停靠，会显示便道为空的信息：用户每输入一组数据，程序就会根据相应输入给出输出。输入值第一个必须为字母，后两个为数字。
3.测试数据要求：
用户输入字母时，输入大写或小写，都可以被该程序识别，正常运行。但要求用户输入数据时，三个数据项之间必须用逗号相分隔开。
三．概要设计
为了实现上述功能，该程序以栈模拟停车场以及临时停放为给要离去的汽车让路而从停车场退出来的汽车的场地，以队列模拟车场外的便道，因此需要栈和队列这两个抽象数据类型。
1. 栈抽象数据类型定义：
ADT SqStack{
数据对象：D={，
i=1,2,3....,n,n}
数据关系：R={()|D,struct car};
根本操作：
Judge_Output(s,q,r)；//根据r中车辆信息控制车辆是入栈s还是
入队q以及相关操作
A_cars(s,q, a)；//将到达车辆a的信息入栈s或者入队q
D_cars(s,q, d)；//将待离开车辆d出栈s，并将q中相应车辆
入栈并进展相关的操作
}ADT SqStack
2.队列抽象数据类型定义：
ADT LinkQueue{
数据对象：D={Qnode *,Qnode
*,,i=1,2,3....,n,n};
数据关系：R=；
根本操作：
Judge_Output(s,q,r)；//根据r中车辆信息控制车辆是入栈s
还是入队q以及相关操作
A_cars(s,q, a)；//将到达车辆a的信息入栈s或者入队q
D_cars(s,q, d)；//将待离开车辆d出栈s，并将q中相应车
辆入栈并进展相关的操作
}ADT LinkQueue
3.主要算法流程图：
I．Judge_Output算法流程图：

II．A_cars算法流程图：

III．D_cars算法流程图：

4.本程序保护模块：
主函数模块
栈单元模块：实现栈的抽象数据类型
队列单元模块：实现队列的抽象数据类型
调用关系：

四．详细设计
1.相关头文件库的调用说明：
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 14
#define n 2
#define fee 10
2.元素类型、结点类型和结点指针类型：
struct car
{ char bb;
int num;
int time;
};
struct rangweicar
{int num;
int time;
};
typedef struct stackk
{struct rangweicar H[MAXSIZE];
int topp;
}SqStackk;
#define QNODE struct Qnode
QNODE { int data;
QNODE *next;
};
3.栈类型和队列类型：
typedef struct stack
{struct car G[n];
int top;
}SqStack;
typedef struct linkqueue
{QNODE *front,*rear;
int geshu;
}LinkQueue;
//局部根本操作的伪码实现
void Judge_Output(SqStack *s,LinkQueue *q,struct car *r)
{
if((*r).bb=='E'||(*r).bb=='e')
printf("STOP!\n");
else if((*r).bb=='P'||(*r).bb=='p')
printf("The number of parking cars is %d\n",(s->top)+1);
else if((*r).bb=='W'||(*r).bb=='w')
printf("The number of waiting cars is %d\n",q->geshu);
else if((*r).bb=='A'||(*r).bb=='a')
A_cars(s,q,*r);
else if((*r).bb=='D'||(*r).bb=='d')
D_cars(s,q,*r);
else
printf("ERROR!\n");
}
A_cars(SqStack *s,LinkQueue *q,struct car a)
{QNODE *t;
if(s->top!=n-1)
{(s->top)++;
(s->G[s->top]).bb=a.bb;
(s->G[s->top]).num=a.num;
(s->G[s->top]).time=a.time;
}
else
{printf("The parking place is full!\n");
t=(QNODE *)malloc(sizeof(QNODE));
t->data=a.num;
t->next=NULL;
q->rear->next=t;
q->rear=t;
printf("the number of the car in the access road is:%d\n",q->rear->data);
q->geshu++;
}
}
int D_cars(SqStack *s,LinkQueue *q,struct car d)
{int i,j,l;
float x,y;
QNODE *p;
SqStackk *k;
if(d.num==(s->G[s->top]).num)
{x=d.time-(s->G[s->top]).time;
y=fee*x;
printf("The time is %.2f hours,the fee is %.2f yuan\n",x,y);
if(q->geshu==0)
{printf("The queue is empty!\n");
return 0;
}
else
{p=q->front->next;
q->front->next=p->next;
(s->G[s->top]).num=p->data;
(s->G[s->top]).time=d.time;
free(p);
q->geshu--;
if(q->front->next==NULL)
q->rear=q->front;
return 1;
}
}
else
{for(i=0;i<(s->top);i++)
{if((s->G[i]).num!=d.num) continue;
else break;}
if(i>=(s->top))
{printf("ERROR!!\n");
return -1;
}
x=d.time-(s->G[i]).time;
y=fee*x;
printf("The time is %.2f hours,the fee is %.2f yuan\n",x,y);
k=(SqStackk *)malloc(sizeof(SqStackk));
k->topp=-1;
for(j=(s->top);j>i;j--)
{k->topp++; (k->H[k->topp]).num=(s->G[j]).num;
(k->H[k->topp]).time=(s->G[j]).time;
s->top--;
}
for(l=0;l<=(k->topp);l++)
{printf("the information(number and time) in the new stack is:\n");
printf("%d,%d\n",(k->H[l]).num,(k->H[l]).time);}
s->top--;
while(k->topp>=0)
{s->top++;
(s->G[s->top]).bb='A';
(s->G[s->top]).num=(k->H[k->topp]).num;
(s->G[s->top]).time=(k->H[k->topp]).time;
k->topp--;
}
if(q->geshu==0)
{printf("The access road is empty!\n");
return 2;
}
else
{s->top++;
p=q->front->next;
q->front->next=p->next;
(s->G[s->top]).num=p->data;
(s->G[s->top]).time=d.time;
free(p);
q->geshu--;
if(q->front->next==NULL)
q->rear=q->front;
return 3;
}
}
}

4.主函数的伪码：
main()
{SqStack *s;
LinkQueue *q;
QNODE *p;
struct car aa[MAXSIZE];
int i;
s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1;
q=(LinkQueue *)malloc(sizeof(LinkQueue));
p=(QNODE *)malloc(sizeof(QNODE));
p->next=NULL;
q->front=q->rear=p;
q->geshu=0;
printf("******************************************************************************\n");
printf("************************* *************************\n");
printf("************************* 停车场管理系统 *************************\n");
printf("************************* *************************\n");
printf("******************************************************************************\n");
for(i=0;i<MAXSIZE;i++)
{printf("Please input the state,number and time of the car:\n");
scanf("%c,%d,%d",&(aa[i].bb),&(aa[i].num),&(aa[i].time));
getchar();
Judge_Output(s,q,&aa[i]);
if(aa[i].bb=='E'||aa[i].bb=='e') break;
}
}

5.函数调用关系：

五．测试分析：
1. 出现问题及解决方法：
该程序是四个程序调试中最顺利的一个，只在一个地上出了问题，就是输入字符时由于回车键也是字符，回车键总会被读入，导致经常输出“ERROR！〞。后来找到原因后在scanf函数后紧接着加了一个getchar〔〕；语句后就恢复了正常。
2.法优缺点分析：
优点：用栈和队列来模拟停车场让整个问题显得简单，易于实现；
缺点：栈和队列这两个数学模型用在停车场管理上还是有失妥当的，现实中停车场出口入口不可能为同一处，不可能当一辆车要离开，在它后面进来的车必须为它让路，因此无法用栈的“后进先出〞原那么来模拟；而且没有考虑便道上的车在等待过程中可以中途开走等情况，而这些都无法用队列的“先进先出〞原那么来模拟。
3.主要算法的时间和空间复杂度分析：
〔1〕由于算法Judge_Output函数根据判断条件，每次只选择一个程序段执行，所以其时间复杂度是O(1)；
〔2〕由于算法A_cars函数根据判断条件，将数据入栈或入队列，所以其时间复杂度也是O(1)；
〔3〕由于算法D_cars函数在出栈数据不在最顶端时需将n个数据先出该栈，再入新栈，再回旧栈的操作，故其时间复杂度是O(n)；
〔4〕所有算法的空间复杂度都是O(1)。
六． 使用说明
程序运行后用户根据提示一次输入车辆的状态信息，车牌编号，时间，程序会根据车辆的状态信息调用相应的函数，并输出用户想得到的信息。
七． 调试结果
输入数据：〔‘A’，1，5〕，〔‘A’，2，10〕，〔‘D’，1，15〕，〔‘A’，3， 20〕，〔‘A’，4，25〕，〔‘A’，5，30〕，〔‘D’，2，35〕，〔‘D’，4，40〕，〔‘P’，0，0〕，〔‘W’，0，0〕，〔‘F’，0，0〕，〔‘E’，0，0〕。
输出数据：1号车停放时间为10小时，收费100元；2号车停放时间为25小时，收费250元；4号车停放5小时，收费50元；此时停车场有两辆车，便道上无车。假设停车场已满，那么会显示停车场已满的信息；假设便道上无车等待停车，会显示便道上无车的信息；假设中途有车离开，需其后的车让道，会显示进入临时停车场的车辆的信息；假设输入〔‘F’，0，0〕，输出“ERROR！〞；假设输入〔‘E’，0，0〕，程序完毕。
运行结果截屏：

八． 附录
源程序文件清单：
#include<stdio.h> /*调用的头文件库声明*/
#include<stdlib.h>
#define MAXSIZE 14
#define n 2
#define fee 10
struct car /*用该构造体来存放车的状态，编号和时间信息 */
{ char bb;
int num;
int time;
};
typedef struct stack /*用该栈来模拟停车场*/
{struct car G[n];
int top;
}SqStack;
struct rangweicar /*用该构造体来存放临时让出的车辆的编号以及时间信息*/
{int num;
int time;
};
typedef struct stack /*用该栈来模拟临时让出的车辆的停靠场地*/
{struct rangweicar H[MAXSIZE];
int topp;
}SqStackk;
#define QNODE struct Qnode
QNODE { int data; /*链队结点的类型*/
QNODE *next;
};
typedef struct linkqueue /*用该链队来模拟便道*/
{QNODE *front,*rear;
int geshu;
}LinkQueue;
void Judge_Output(SqStack *s,LinkQueue *q,struct car *r) /*该算法通过传递来的车辆信息调
{ 用相关函数实现操作*/
if((*r).bb=='E'||(*r).bb=='e') /*假设车辆状态为‘E’，终止程序*/
printf("STOP!\n");
else if((*r).bb=='P'||(*r).bb=='p') /*假设车辆状态为‘P’，输出停车场车辆数*/
printf("The number of parking cars is %d\n",(s->top)+1);
else if((*r).bb=='W'||(*r).bb=='w') /*假设车辆状态为‘W’，输出便道车辆数*/
printf("The number of waiting cars is %d\n",q->geshu);
else if((*r).bb=='A'||(*r).bb=='a') /*假设车辆状态为‘A’，调用A_cars函数*/
A_cars(s,q,*r);
else if((*r).bb=='D'||(*r).bb=='d') /*假设车辆状态为‘D’，调用D_cars函数*/
D_cars(s,q,*r);
else
printf("ERROR!\n"); /*假设车辆状态为其他字母，报错*/
}
A_cars(SqStack *s,LinkQueue *q,struct car a) /*该算法实现对车辆状态为到达的车辆的操
{QNODE *t; 作*/
if(s->top!=n-1) /*假设停车场还没有满，那么车进停车场，并存入车辆的状态，车牌编
{(s->top)++; 号和到达时间信息*/
(s->G[s->top]).bb=a.bb;
(s->G[s->top]).num=a.num;
(s->G[s->top]).time=a.time;
}
else
{printf("The parking place is full!\n"); /*假设停车场已满，车进便道，并显示该车的车牌编
t=(QNODE *)malloc(sizeof(QNODE)); 号，同时记录便道车辆数目*/
t->data=a.num;
t->next=NULL;
q->rear->next=t;
q->rear=t;
printf("the number of the car in the access road is:%d\n",q->rear->data);
q->geshu++;
}
}
int D_cars(SqStack *s,LinkQueue *q,struct car d) /*该算法实现车辆状态为离开的车
{int i,j,l; 辆的操作*/
float x,y;
QNODE *p;
SqStackk *k;
if(d.num==(s->G[s->top]).num) /*假设待离开车为最后进停车场的车的情况*/
{x=d.time-(s->G[s->top]).time;
y=fee*x; /*直接计算停车时间，费用并离去*/
printf("The time is %.2f hours,the fee is %.2f yuan\n",x,y);
if(q->geshu==0) /*假设便道上无车，函数返回*/
{printf("The queue is empty!\n");
return 0;
}
Else /*假设便道上有车，第一辆车进停车场*/
{p=q->front->next;
q->front->next=p->next;
(s->G[s->top]).num=p->data; /*并存入其车牌编号及进停车场的时间*/
(s->G[s->top]).time=d.time;
free(p);
q->geshu--;
if(q->front->next==NULL)
q->rear=q->front; /*假设此时便道上无车，返回1*/
return 1;
}
}
Else /*待离开的车不是最后进停车场的那辆车的情况*/
{for(i=0;i<(s->top);i++) /*先找到待离开车在停车场中的位置*/
{if((s->G[i]).num!=d.num) continue;
else break;}
if(i>=(s->top))
{printf("ERROR!\n");
return -1;
}
x=d.time-(s->G[i]).time; /*计算待离开车的停车时间并计算费用*/
y=fee*x;
printf("The time is %.2f hours,the fee is %.2f yuan\n",x,y);
k=(SqStackk *)malloc(sizeof(SqStackk)); /*设立一个新栈临时停放为该车离开而让
k->topp=-1; 路的车辆*/
for(j=(s->top);j>i;j--)
{k->topp++; (k->H[k->topp]).num=(s->G[j]).num;
(k->H[k->topp]).time=(s->G[j]).time;
s->top--;
}
for(l=0;l<=(k->topp);l++)
{printf("the information(number and time) in the new stack is:\n");
printf("%d,%d\n",(k->H[l]).num,(k->H[l]).time);} /*显示在新栈中的车辆信息*/
s->top--;
while(k->topp>=0) /*将新栈中的车重新开入停车场中*/
{s->top++;
(s->G[s->top]).bb='A';
(s->G[s->top]).num=(k->H[k->topp]).num;
(s->G[s->top]).time=(k->H[k->topp]).time;
k->topp--;
}
if(q->geshu==0) /*假设便道上无车，那么返回2，无车开入停车场中*/
{printf("The access road is empty!\n");
return 2;
}
Else /*假设便道上有车，那么第一辆车开入停车场中*/
{s->top++;
p=q->front->next;
q->front->next=p->next;
(s->G[s->top]).num=p->data;
(s->G[s->top]).time=d.time;
free(p);
q->geshu--;
if(q->front->next==NULL)
q->rear=q->front;
return 3;
}
}
}
main()
{SqStack *s;
LinkQueue *q;
QNODE *p;
struct car aa[MAXSIZE];
int i;
s=(SqStack *)malloc(sizeof(SqStack)); /*对停车场初始化*/
s->top=-1;
q=(LinkQueue *)malloc(sizeof(LinkQueue));
p=(QNODE *)malloc(sizeof(QNODE)); /*对便道初始化*/
p->next=NULL;
q->front=q->rear=p;
q->geshu=0;
printf("******************************************************************************\n");
printf("************************* *************************\n");
printf("************************* 停车场管理系统 *************************\n");
printf("************************* *************************\n");
printf("******************************************************************************\n");
for(i=0;i<MAXSIZE;i++) /*输入车辆信息*/
{printf("Please input the state,number and time of the car:\n");
scanf("%c,%d,%d",&(aa[i].bb),&(aa[i].num),&(aa[i].time));
getchar();
Judge_Output(s,q,&aa[i]);
if(aa[i].bb=='E') break;
}
}
. .word.zl.