一．问题描述
1.实验题目：
设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满 n辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。
要求：根据各结点的信息，调用相应的函数或者语句，将结点入栈入队，出栈或者出队。
二．需求分析
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！”报错。若便道上没有车辆停靠，会显示便道为空的信息：用户每输入一组数据，程序就会根据相应输入给出输出。输入值第一个必须为字母，后两个为数字。
三．概要设计
为了实现上述功能，该程序以栈模拟停车场以及临时停放为给要离去的汽车让路而从停车场退出来的汽车的场地，以队列模拟车场外的便道，因此需要栈和队列这两个抽象数据类型。
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;
}
}