《算法与数据结构》课程设计
题目：停车场的收费管理系统
组长：张赛
组员：王佳琪，袁洁莹，张瑜
完成日期：2013年12月25日
一、 设计目的与内容
1. 问题描述
任务：停车场可以同时停放M辆车，停车场的入口和出口可分别有N辆车排队。停车每小时收费5元，每天不超过50元，停车不满半小时不收费，超过半小时按一小时收费。
功能要求：完成停车场进出车的收费管理以及查询每辆车的停车记录（按照车牌号查询）；停车场目前的状况（满或空的车位数）。
规定：输入数据形式和范围：车牌号、停车开始时间
输出形式：有中文提示，停车的时间长短、离开停车场的时间、费用
界面要求：有合理的提示。
存储结构：学生自己根据系统功能要求自己设计，但是要求停车记录要存储在数据文件中。 测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；
2. 基本要求
（1）停车场管理主要实现以下几个功能：
①、停车场车位的划分。
②、车辆进出管理及收费功能。
③、停车场车辆信息查询功能。
④、退出系统。
（2）以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管
理。
（3）栈以顺序结构实现，队列以链表结构实现。
3. 目的：
程序所能达到的功能：
程序主要服务于停车场使用者和停车场管理者。
对于使用停车场的停车者,在其等待期间,系统为使用者提供查询，修改，删除车辆信息的操作。当使用者想要离开停车场，停车场自动计算出停车费用，并自动让正在等待的使用者有序进入停车位。
而管理者可以通过本系统查询过场，在场，等待的车辆信息，也可以统计24小时内的停车收入。
停车场的管理系统利用栈和队列的这些特点来实现模拟停车场和便道。
二、 算法的基本思想
1. 数据结构定义
（1） 队列数据类型定义：
ADT Queue{
数据对象：D={ai|ai∈ElemSet, i=1,2,……,n,n≥0}
数据关系：R1={|ai-1,ai∈D,i=2……,n}
基本操作：
InitQueue(&Q)
操作结果：构造一个空队列Q。
DestroyQueue(&Q)
初始条件：队列Q已存在。
操作结果：队列Q被销毁，不再存在。
ClearQueue(&Q)
初始条件：队列Q已存在。
操作结果：将Q清为空队列。
QueueEmpty(&Q)
初始条件：队列Q已存在。
操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。
QueueLength(Q)
初始条件：队列Q已存在。
操作结果：返回Q的元素个数，即队列的长度。
GetHead(Q, &e)
初始条件：Q为非空队列。
操作结果：用e返回Q的队头元素。
EnQueue(&Q, e)
初始条件：队列Q已存在。
操作结果：插入元素e为Q的新的队尾元素。
DeQueue(&Q, &e)
初始条件：Q为非空队列。
操作结果：删除Q的队头元素，并用e返回其值。
QueueTraverse(Q, visit())
初始条件：Q已存在且非空。
操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
}ADT Queue
（2） 栈数据类型定义
ADT stack{
数据对象：D={ai|ai∈charset, i=1,2,……,n,n≥0}
数据关系：R1={|ai-1,ai∈D,i=2……,n}
基本操作：
initstack(&S, n)
操作结果：构造一个空栈S,该栈可存放n个元素。
push(&S, e)
初始条件：栈S已存在。
操作结果：在栈S的栈顶插入新的栈顶元素e。
pop(&S, &e)
初始条件：栈S已存在。
操作结果：删除S的栈顶元素，并以e返回其值。
DestroyStack(&S)
初始条件：栈S已存在。
操作结果：销毁栈S。
ClearStack(&S)
初始条件：栈S已存在。
操作结果：将S清为空栈。
StackLength(&S)
初始条件：栈S已存在。
操作结果：返回栈S的长度。
StackEmpty(&S)
初始条件：栈S已存在。
操作结果：若S为空栈，则返回TRUE，否则返回FALSE。
GetTop(S, &e)
初始条件：栈S已存在。
操作结果：若栈S不空，则以e返回栈顶元素。
StackTraverse(S, visit())
初始条件：栈S已存在。
操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit()。
}ADT stack
2. 主程序流程
基本框架：
过场、在场与等待车辆信息查找（栈 数组） 在场车辆信息修改（栈）
等待车辆队列删除（队列） 已收取的总停车费用
（1）． 车辆信息类型
typedef struct {
int Htime;
int Mtime;
}Time; //简单模拟时间信息，记录小时和分钟
typedef struct {
char num[20];
Time reachtime;
Time leavetime;
}carinfo;
（2）． 栈类型
typedef struct stack
{ carinfo car[5];
int top;}Stack;
int inistack(Stack *S) //初始化栈
{ S->top=-1;
return 1;
}
void Push(Stack *S,carinfo x) //进栈操作
{ S->top++;
S->car[S->top]=x;
printf("进站成功!\n");
}
void Pop(Stack *S,carinfo x) //出栈操作
{ if(S->top=-1)
printf("空栈，无法出栈!");
x=S->car[S->top];
S->top--;
printf("出栈成功!\n");
}
int IsEmpty(Stack *S) //判断栈空
{ if(S->top==-1)
return 1;
else
return 0;
}
（3）．队列类型（便道）
typedef struct Node{
carinfo data;
struct Node *next;
}QueueNode;
typedef struct {
QueueNode *front;
QueueNode *rear;
}Queue,*linkQueue;
int EnterQ(Queue *Q,carinfo x);
int iniQueue(Queue *Q) //初始化便道
{ Q->front=(QueueNode *)malloc(sizeof(QueueNode)); //
申请节点
if(Q->front!=NULL)
{ Q->rear=Q->front;
Q->front->next=NULL;
return 1;
}
else return 0;
}
int EnterQ(Queue *Q,carinfo x) //进便道
{ QueueNode *newNode;
newNode=(QueueNode *)malloc(sizeof(QueueNode));
if(newNode!=NULL)
{
newNode->data=x;
newNode->next=NULL;
Q->rear->next=newNode;
Q->rear=newNode;
return 1;
}
else return 0;
}
int DeleteQ(Queue *Q,carinfo x) //出便道
{
QueueNode *p;
p=Q->front->next;
if(Q->front==Q->rear) //判断便道是否有车
return 0;
x=p->data;
if(p->next==Q->rear)
{
Q->rear=Q->front;
Q->front->next=NULL;
}
Q->front->next=p->next;
free(p);
return 1;
}
（4）主函数及其他函数的算法
void main()
{ Queue *Q;
Stack *S=NULL;
S=(Stack *)malloc(sizeof(Stack)); //申请栈节点
Q=(linkQueue)malloc(sizeof(Queue)); //申请便道节点
int i;
iniQueue(Q); //初始化调用
inistack(S); //初始化调用
printf("\n****************************欢迎使用停车场管理界面******************************\n");
printf("*******本停车场每小时收费2元,停车不满半小时不收费，超过半小时按一小时收费*******");
printGraph();
while(1)
{
printf("\n请输入操作");
scanf("%d",&i);
switch(i)
{
case 1:Arrive(S,Q);printGraph(); break;
case 2:Departure(S,Q);printGraph();break;
case 3:Print(S);printGraph();break;
case 0:exit(1);break;
case 4:PrintQ(Q);break;
case 5:Search(S);break;
default :printf("重新输入");printGraph();
}
}
}
void Lpush(Stack *S,carinfo x)
{ Push(S,x); //进临时栈
}
void LPop(Stack *S,carinfo x)
{
Pop(S,x);
}
int Arrive(Stack *S,Queue *Q) //车辆到达
{
carinfo x;
int a;
printf("输入车牌号：");
scanf("%s",x.num);
printf("请输入进车场的时间(**:**)：");
scanf("%d:%d",&x.reachtime.Htime,&x.reachtime.Mtime);
if(S->top==Size-1)
{
printf("车场已满，不能进入，进便道\n");
a=EnterQ(Q, x); //递归调用进便道操作
if(a==1){
printf("OK\n");
}
else
printf("No!\n");
}
else
{
Push(S,x);
}
return 1;
}
int Departure(Stack *S,Queue *Q) //车辆离开操作
{ carinfo a;
int parktime,paytime;
char x[20];
Time leavetime;
Stack *p=NULL;
int point1=S->top;
int point2=S->top;
printf("请输入要离去的车牌号：");
scanf("%s",x);
while(point1!=-1&&point2!=-1)
{
if(strcmp(S->car[point1].num,x)==0) //匹配函数，是否输入的信息与车场信息匹配
{
printf("请输入要离开的时间(**:**)：");
scanf("%d:%d",&leavetime.Htime,&leavetime.Mtime);
for(;point1!=S->top;point1++,point2++) //扫描直到结束
S->car[point1]=S->car[point2]; //如果找到了 ，出车
S->top--;
printf("成功出车场\n");
parktime=(leavetime.Htime-S->car[point1].reachtime.Htime)*60+(leavetime.Mtime-S->car[point1].reachtime.Mtime);
if(leavetime.Htime-S->car[point1].reachtime.Htime>=10) paytime=10; else if(leavetime.Mtime-S->car[point1].reachtime.Mtimecar[point1].reachtime.Htime;
else paytime=leavetime.Htime-S->car[point1].reachtime.Htime+1; printf("其在停车场内停留时间为%d分钟，实际按照%d小时计费，所需付费为：%d元。\n",parktime,paytime,paytime*2);
point2=-1;
}
else{
point2=point1;
point1--;
}
}
if(Q->front!=Q->rear) {
a=Q->front->next->data;
printf("从便道进入停车场的车牌号：%s",a.num);
printf("请输入进车场的时间：%d:%d",leavetime.Htime,leavetime.Mtime); scanf("%d:%d",&a.reachtime.Htime,&a.reachtime.Mtime);
Push(S,a);DeleteQ(Q,Q->front->next->data);
}
if(point1==-1) //如果到结束了，还没有找到，则输出信息
{
printf("此车没有在停车场！\n");
return 1;
}
}
void Print1(carinfo x) //简单的输出操作
{
printf("车牌号：%s\n",x.num);
printf("进车场的时间：%d:%d\n",x.reachtime.Htime,x.reachtime.Mtime); printf("\n-----------------\n");
}
void Print(Stack *S)//打印车场信息
{ carinfo x;
int point=S->top; //从栈头开始
if(S->top==-1)
printf("车场没有车辆登记进入!\n");
else
{ while(point!=-1)
{
printf("\n-----------------\n");
printf("车的位置号：%d\n",point);
x=S->car[point]; // 把依次扫描到的信息赋值给x
Print1(x); //调用输出函数
point--; //输出所有的车场信息
}
printf("显示车场信息成功!\n");
}
}
void PrintQ(Queue *Q) //打印便道车辆信息
{
QueueNode *p;
//p=(QueueNode *)malloc(sizeof(Queue)); //申请结点
p=Q->front->next;
if(Q->front!=Q->rear){ /*判断通道上是否有车*/
printf("\n等待车辆的车牌号为: ");
while(p!=NULL){ //判断是否到结尾
printf("%s ",p->data.num);
p=p->next; //如果没找到，继续向下找
}
printf("\n");
}
else
printf("\n\t\t\t便道里没有车。\n");
}
int Search(Stack *S) //按车牌号查找车辆信息
{ char x[20];
Time leavetime;
Stack *p=NULL;
carinfo a;
int point1=S->top;
int point2=S->top;
printf("请输入要查找的车牌号：");
scanf("%s",x);
while(point1!=-1&&point2!=-1)
{
if(strcmp(S->car[point1].num,x)==0) //匹配函数，是否输入的信息与车场信息匹配
{ for(;point1!=S->top;point1++,point2++) //扫描直到结束
S->car[point1]=S->car[point2]; //如果找到了 ，输出信息 printf("该车目前在停车场中。\n");
point2=-1;
}
else{
point2=point1;
point1--;
} }
if(point1==-1) //如果到结束了，还没有找到，则输出信息 {
printf("此车没有在停车场！"); return 1; } }
void printGraph(){ int i;
printf("\n");
for(i=0;i
printf("\n\t\t\t******请选择操作序号******"); printf("\n\n\t\t\t ----车辆到达请选1----"); printf("\n\n\t\t\t ----车辆离开请选2----"); printf("\n\n\t\t\t --查询停车场信息请选3--"); printf("\n\n\t\t\t --查询便道信息请选4--"); printf("\n\n\t\t\t --按车牌号查找请选5--"); printf("\n\n\t\t\t ----退出系统请选0----"); printf("\n\n");
for(i=0;i
3. 各模块之间的调用关系
主函数void main()
初始化调用iniQueue(Q);
inistack(S);
调用到达函数Arrive(S,Q); 调用离开函数Departure(S); 调用打印信息函数printGraph()
三、 测试数据
全部合法数据： 1.主界面
2.到达：
3.离开：
（若便道有车等待） 输出从便道中进入停车场的车牌号、进车场时间（即为从便道中出车的时间）、进站成功！
4.输出车场信息
5输出便车道信息
6、按车牌号查找信息
非法数据 1.主界面：
2.车辆到达：
3.车辆离开
四、 源程序及系统文件使用说明
#include #include #include #define Size 2 #define price 5
typedef struct { int Htime; int Mtime;
}Time; //简单模拟时间信息，记录小时和分钟
typedef struct { char num[20];
Time reachtime;
Time leavetime;
}carinfo; //通过结构来保存来车的车牌号，到达时间，离开时间
typedef struct stack
{
carinfo car[5];
int top;
}Stack;
typedef struct Node{
carinfo data;
struct Node *next;
}QueueNode; //结点的定义
typedef struct {
QueueNode *front;
QueueNode *rear;
}Queue,*linkQueue; //定义队列结点
int EnterQ(Queue *Q,carinfo x);
int inistack(Stack *S) //初始化栈
{
S->top=-1;
return 1;
}
void Push(Stack *S,carinfo x) //进栈操作
{
S->top++;
S->car[S->top]=x;
printf("进站成功!\n");
}
void Pop(Stack *S,carinfo x) //出栈操作
{
if(S->top=-1)
printf("空栈，无法出栈!");
x=S->car[S->top];
S->top--;
printf("出栈成功!\n");
}
int IsEmpty(Stack *S) //判断栈空
{
if(S->top==-1)
return 1;
else
return 0;
}
int iniQueue(Queue *Q) //初始化便道
{
Q->front=(QueueNode *)malloc(sizeof(QueueNode)); //申请节点
if(Q->front!=NULL)
{
Q->rear=Q->front;
Q->front->next=NULL;
return 1;
}
else return 0;
}
int EnterQ(Queue *Q,carinfo x) //进便道
{
QueueNode *newNode;
newNode=(QueueNode *)malloc(sizeof(QueueNode));
if(newNode!=NULL)
{
newNode->data=x;
newNode->next=NULL;
Q->rear->next=newNode;
Q->rear=newNode;
return 1;
}
else return 0;
}
int DeleteQ(Queue *Q,carinfo x) //出便道
{
QueueNode *p;
p=Q->front->next;
if(Q->front==Q->rear) //判断便道是否有车
return 0;
x=p->data;
if(p->next==Q->rear)
{
Q->rear=Q->front;
Q->front->next=NULL;
}
Q->front->next=p->next;
free(p);
return 1;
}
void Lpush(Stack *S,carinfo x)
{ Push(S,x); //进临时栈
}
void LPop(Stack *S,carinfo x)
{
Pop(S,x);
}
int Arrive(Stack *S,Queue *Q) //车辆到达
{
carinfo x;
int a;
printf("输入车牌号：");
scanf("%s",x.num);
printf("请输入进车场的时间(**:**)：");
scanf("%d:%d",&x.reachtime.Htime,&x.reachtime.Mtime);
if(S->top==Size-1)
{
printf("车场已满，不能进入，进便道\n");
a=EnterQ(Q, x); //递归调用进便道操作
if(a==1){
printf("OK\n");
}
else
printf("No!\n");
}
else
{
Push(S,x);
}
return 1;
}
int Departure(Stack *S,Queue *Q) //车辆离开操作
{ carinfo a;
int parktime,paytime;
char x[20];
Time leavetime;
Stack *p=NULL;
int point1=S->top;
int point2=S->top;
printf("请输入要离去的车牌号：");
scanf("%s",x);
while(point1!=-1&&point2!=-1)
{
if(strcmp(S->car[point1].num,x)==0) //匹配函数，是否输入的信息与车场信息匹配 {
printf("请输入要离开的时间(**:**)：");
scanf("%d:%d",&leavetime.Htime,&leavetime.Mtime);
for(;point1!=S->top;point1++,point2++) //扫描直到结束
S->car[point1]=S->car[point2]; //如果找到了 ，出车
S->top--;
printf("成功出车场\n");
parktime=(leavetime.Htime-S->car[point1].reachtime.Htime)*60+(leavetime.Mtime-S->car[point1].reachtime.Mtime);
if(leavetime.Htime-S->car[point1].reachtime.Htime>=10) paytime=10;
else if(leavetime.Mtime-S->car[point1].reachtime.Mtimecar[point1].reachtime.Htime;
else paytime=leavetime.Htime-S->car[point1].reachtime.Htime+1;
printf("其在停车场内停留时间为%d分钟，实际按照%d小时计费，所需付费为：%d元。\n",parktime,paytime,paytime*2);
point2=-1;
}
else{
point2=point1;
point1--;
}
}
if(Q->front!=Q->rear) {
a=Q->front->next->data;
printf("从便道进入停车场的车牌号：%s",a.num);
printf("请输入进车场的时间：%d:%d",leavetime.Htime,leavetime.Mtime);
scanf("%d:%d",&a.reachtime.Htime,&a.reachtime.Mtime);
Push(S,a);DeleteQ(Q,Q->front->next->data);
}
if(point1==-1) //如果到结束了，还没有找到，则输出信息
{
printf("此车没有在停车场！\n");
return 1;
}
}
void Print1(carinfo x) //简单的输出操作
{
printf("车牌号：%s\n",x.num);
printf("进车场的时间：%d:%d\n",x.reachtime.Htime,x.reachtime.Mtime);
printf("\n-----------------\n");
}
void Print(Stack *S)//打印车场信息
{
carinfo x;
int point=S->top; //从栈头开始
if(S->top==-1)
printf("车场没有车辆登记进入!\n");
else
{
while(point!=-1)
{
printf("\n-----------------\n");
printf("车的位置号：%d\n",point);
x=S->car[point]; // 把依次扫描到的信息赋值给x
Print1(x); //调用输出函数
point--; //输出所有的车场信息
}
printf("显示车场信息成功!\n");
}
}
void PrintQ(Queue *Q) //打印便道车辆信息
{
QueueNode *p;
//p=(QueueNode *)malloc(sizeof(Queue)); //申请结点
p=Q->front->next;
if(Q->front!=Q->rear){ /*判断通道上是否有车*/
printf("\n等待车辆的车牌号为: ");
while(p!=NULL){ //判断是否到结尾
printf("%s ",p->data.num);
p=p->next; //如果没找到，继续向下找
}
printf("\n");
}
else
printf("\n\t\t\t便道里没有车。\n");
}
int Search(Stack *S) //按车牌号查找车辆信息
{
char x[20];
Time leavetime;
Stack *p=NULL;
carinfo a;
int point1=S->top;
int point2=S->top;
printf("请输入要查找的车牌号：");
scanf("%s",x);
while(point1!=-1&&point2!=-1)
{
if(strcmp(S->car[point1].num,x)==0) //匹配函数，是否输入的信息与车场信息匹配 {
for(;point1!=S->top;point1++,point2++) //扫描直到结束
S->car[point1]=S->car[point2]; //如果找到了 ，输出信息
printf("该车目前在停车场中。\n");
point2=-1;
}
else{
point2=point1;
point1--;
}
}
if(point1==-1) //如果到结束了，还没有找到，则输出信息
{
printf("此车没有在停车场！");
return 1;
}
}
void printGraph(){
int i;
printf("\n");
for(i=0;i
printf("\n\t\t\t******请选择操作序号******");
printf("\n\n\t\t\t ----车辆到达请选1----");
printf("\n\n\t\t\t ----车辆离开请选2----");
printf("\n\n\t\t\t --查询停车场信息请选3--");
printf("\n\n\t\t\t --查询便道信息请选4--");
printf("\n\n\t\t\t --按车牌号查找请选5--");
printf("\n\n\t\t\t ----退出系统请选0----");
printf("\n\n");
for(i=0;i
}
void main(){
Queue *Q;
Stack *S=NULL;
S=(Stack *)malloc(sizeof(Stack)); //申请栈节点
Q=(linkQueue)malloc(sizeof(Queue)); //申请便道节点
int i;
iniQueue(Q); //初始化调用
inistack(S); //初始化调用
printf("\n****************************欢迎使用停车场管理界面******************************\n");
printf("*******本停车场每小时收费2元,停车不满半小时不收费，超过半小时按一小时收费*******");
printGraph();
while(1)
{
printf("\n请输入操作");
scanf("%d",&i);
switch(i)
{
case 1:Arrive(S,Q);printGraph(); break;
case 2:Departure(S,Q);printGraph();break;
case 3:Print(S);printGraph();break;
case 0:exit(1);break;
case 4:PrintQ(Q);break;
case 5:Search(S);break;
default :printf("重新输入");printGraph();
}
}
}
五、 心得体会
1. 对于本题：
在测试程序的时候，发现了许多编写时没有注意的细节，比如当输入时间>24h时，提示输入错误，重新输入等。由于我们的程序选项较多，我们在制作后期加入了可视化目录界面。更利于操作者使用。通过做这道题，我们都感觉自己对队列与栈了解更多，理解更透彻了，收获很多。
2. 对于数据结构：
在学习数据结构后，感觉对于上学期的C程序有了更好更清楚地理解。数据结构在编程相关知识里是统领、概括的地位。它与之前的C程序以及之后的Java等语言都有关联。这门
课程很具有挑战性，通过学习，提高了我们优化意识，在对待一件事的时候能够用编程的思维尽量精简步骤、程序。
六、 参考文献
1.严蔚敏 数据结构(C语言版） 清华大学出版社，1997
2.徐孝凯 数据结构 清华大学出版社，1999