数据结构实验报告模拟停车场管理(含代码).doc

模拟停车场管理
班级：物联网 姓名:XXX 学号：XXXXXXX 日期：4月9日
一、需求分析
1、程序的功能描述
按照从终端输入的数据序列进行模拟管理。
1）狭道停车用栈来实现,并且用的顺序栈,等车位的便道用队列来实现，并用链 式存储。
2）每一组输入信息包含三个数据项，汽车的“到达"和“离去”的信息，汽车牌 照号码，汽车“到达”或“离去”的时刻。
3)对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出车辆在停车场内或便道上的停车位置;若是车子离去,则输出车辆在停车场内停留的时间和缴纳的费用。(假设在便道等车的时间不收费)
4）选作内容：(1）便道也是要收费的，仅仅比狭道收费便宜点。
（2)狭道上的车可以直接开走。
2、 输入/输出的要求
首先选择操作的模块，根据提示输入车牌和到达时间，程序会告知是否停满或者停车车位。车牌为10个字符以内的字符串,时间的输入中间有冒号把时分隔开。
3、 测试数据
1 苏D543 1:10
1 苏Q123 1:20
1 苏D145 1:30
二、概要设计
1本程序所用的抽象数据类型的定义
typedef struct NODE｛
CarNode *stack[MAX+1]；
int top；
｝SeqStackCar;//狭道的堆栈顺序存储
typedef struct car｛
CarNode ＊data;
struct car ＊next;
}QueueNode；//队列的链式存储
typedef struct Node｛
QueueNode ＊head；
QueueNode ＊rear；
}LinkQueueCar;//便道上等候的队列定义
2、 主模块的流程及各子模块的主要功能
车辆到达：int Arrival(SeqStackCar *Enter，LinkQueueCar ＊W）首先定义一个栈和队列的结构体指针为：＊p ， *t 。然后申请一个车辆信息的内存空间,并把它赋给栈指针。 车辆到达时就输入车牌号，并通过if(Enter—>topr ＊W）
定义一个整型变量room 记录要离开车辆的位置，定义两个栈指针和一个队列指针,
用个if（Enter—>top〉0） 确保栈不空，然后用个while(1) 确保输入的车辆离开位置的合法 性。如果不和法，显示输入有误，要重新输入。通过while（Enter—>top〉room） 判断离开车辆的位置，如果是中间位置，就要再用一个栈前面临时开出来的车,等要开出的车开出后，再把临时栈的车看进 车场内,并要调用PRINT(p，room)； 这个函数计算显示费用。然后还要用 if（（W—>head！=W—〉rear）＆＆Enter—>top如果有车就要显示进车场的车的车牌号，并登记进入时间。
开始
初始化两个栈Enter和Temp及一个队列Wait。

进入主菜单
车到达

车离开

退出

Room前车辆进临时栈

对room计费

便道车信息

车场内信息

判便道是否有车

车场是否为空
列表显示

栈Enter元素出栈

队列中元素进栈
队列Wait中元素出队

元素进栈Enter

便道车进车场

元素进队列Wait

判断栈是否为满

结束
退出列表显示
是
否
否
是
否
是

3、 模块之间的层次关系
主函数中包含着各个函数模块，各模块也在互相调用.比如，离开函数中要计算停车费，故要调取价格函数.价格函数计算要用到离开和进入的时间，又要调用进入和离开函数。
三、详细设计
1、采用C语言定义相关的数据类型
＃define MAX 3 // 停车场最大容量为3辆,便于观察
＃define price 0。05
typedef struct time｛ // 定义时间结构体
int hour；
int min；
}Time；
typedef struct node｛ // 定义车辆信息结构体
char num［10]；
Time reach；
Time leave；
｝CarNode；
2、 写出各模块的伪码算法
void PRINT(CarNode ＊p，int room)｛ // 车辆收费
int A1,A2，B1，B2;
printf(”\n车辆离开的时间："）；
scanf("％d:%d",＆（p—〉leave。hour）,＆（p->leave.min））；
printf（”\n离开车辆的车牌号为:”）；
puts(p—>num）;
printf（”\n其到达停车位时间）;
printf(”\n离开停车位时间为：）；
A1p—>reach。hour；
A2=p—>reach。min;
B1=p->leave.hour；
B2=p-〉leave.min；
printf（”\n应交费用为: ％2.1f元",（（B1—A1)＊60+（B2-A2）)＊price+PRINTE(p，room)）;
free（p）；
｝
int Arrival（SeqStackCar ＊Enter，LinkQueueCar ＊W）//进入便道或者狭道
｛
CarNode *p;
QueueNode ＊t；
p=(CarNode ＊)malloc(sizeofCarNode))；
flushall（）；
printf（”\n请输入车牌号（例：豫B1234）：”）;
gets（p—〉num）；
if(Enter—〉toptop++；
printf("\n车辆在车场第％d位置。”,Enter-〉top);
printf（"\n车辆到达时间:");
scanf(”％d:％d”，＆（p—>reach.hour）,&（p—〉reach。min））；
Enter—〉stack［top]=p；
return（1)；
｝
else
｛
printf（”\n该车须在便道等待!有车位时进入车场”）；
t=（QueueNode ＊）malloc(sizeof(QueueNode））；
进入队列，调整指针；
printf（"请输入进入便道的时间”)；
scanf（"％d：%d”,＆（p-〉reach。hour）,&(p->reach。min)）；
return（1);
｝
｝
void Leave（SeqStackCar *Enter，SeqStackCar *Temp，LinkQueueCar ＊W）
{ //车辆的离开
int room；
CarNode *p,＊t；
QueueNode ＊q；
if（Enter->top〉0） // 判断车场是否为空
｛
while（1)
｛
printf（”\n请输入车在车场的位置/1-—％d/："，Enter—>top）;
scanf（”％d”,＆room)；
if（room〉=1＆＆room<=Enter->top） break；
else printf（”\n 输入有误，请重输： ”）；
｝
while(Enter—〉top〉room） // 把要删除的车辆的前面的车开出来，进临时栈。
｛
Temp-〉top++；
Temp-〉stack［Temp->top]=Enter-〉stack［Enter->top]；
Enter—〉stack［Enter-〉top］=NULL;
Enter—〉top——；
｝
p=Enter—〉stack［Enter-〉top］; //把要删除的车辆节点赋给p。
Enter—〉stack［Enter—>top］=NULL;
Enter—〉top——；
while(Temp-〉top〉=1） // 再把临时栈里德车辆进停车场
{
Enter—〉top++；
Enter->stack［Enter-〉top］=Temp—>stack[Temp—〉top］；
Temp—>stack［Temp—>top]=NULL;
Temp—〉top—-；
}
PRINT(p，room）; // 调用计费函数计费。。
if(（W->head！=W—〉rear）&＆Enter—〉topdata；
Enter—>top++；
scanf(”％d:%d"，＆（t-〉reach。hour),&(t—〉reach。min）);
// t-〉leave .hour =t—〉reach。hour；
//t-〉leave 。min =t—>reach。min;
W—〉head-〉next=q->next；
if(q==W->rear） W—〉rear=W-〉head；
Enter-〉stack[Enter—〉top］=t；
PRINTE(t，room）;
free（q);
}
else printf(”\n便道里没有车.\n”)；
}
else printf（”\n车场里没有车.”);
}
3、画出函数的调用关系图
|———-——---—----——>到达函数—————｜
｜———-————-——-————>离开函数—-——---—〉停车费用
主函数——--—-—---—〉显示车场里的情况
｜-——-———————---——>显示便道里的情况
四、调试分析
1、调试中遇到的问题及对问题的解决方法
因为时间结构体里的小时，分钟都是用的是整型，所以如果出现1：01这个时间的话，会导致显示列表是1:1；这样的话会造成人的误解,同时会导致程序对停车缴纳的费用计算错误。
解决方法1：可以用数组和或者字符串来表示时间，但是问题来了,要是用字符串的话，算停车费有点问题,要废上一段时间的,会提高复杂度.
解决方案2：将输出用右对齐方式，缺位的用0补齐，这样最快捷啦！
2、 算法的时间复杂度和空间复杂度
由于没有进行循环嵌套之类的运算,只有简单的循环语句，所以时间复杂度T（O）=O（n），在数据的存储方面，除了车牌号用的是数组以外，便道用的是顺序栈，这些是提前要申请一定的存储空间的，这样非动态分配的存储空间，在某些时候是会导致空间的浪费，增加其空间复杂度.其余的都是结构体和链式存储的队列属于动态存储。当停车场的规模较小时，空间复杂度较小，随着规模的增加,动态存储的扩充，空间复杂度也随之增加。
五、 使用说明及测试结果（给出程序的使用说明、注意事项及不同情况的测试结果）
时间以24进制计算，停车时间不能跨越24进制。车牌号是10个字符串以内,不可溢出。
第一个应缴费用是在便道中的费用，第二个费用是总费用。
六、源程序（要求程序简洁、清晰、主要语句带注释）代码非本人写，对其进行改进而已
#include〈stdio。h〉
#includetypedef struct node{ // 定义车辆信息结构体
char num［10］；
Time reach；
Time leave;
}CarNode；
typedef struct NODE｛
CarNode ＊stack［MAX+1］；
int top；
｝SeqStackCar;
typedef struct car{
CarNode *data；
struct car ＊next；
｝QueueNode;
typedef struct Node｛
QueueNode *head；
QueueNode ＊rear；
}LinkQueueCar;
void InitStack（SeqStackCar *)；
int InitQueue(LinkQueueCar ＊）；
int Arrival（SeqStackCar ＊，LinkQueueCar *）；
void Leave（SeqStackCar ＊，SeqStackCar *，LinkQueueCar ＊）;
void List（SeqStackCar,LinkQueueCar);
void main（）
{
SeqStackCar Enter，Temp；
LinkQueueCar Wait；
int ch;
system（”color 4A"）；
InitStack（&Enter）；
InitStack(＆Temp）;
InitQueue(＆Wait）；
while(1)
{
printf（"\n §※§※§※§※§※§ 欢迎使用停车场系统。§※§※§※§※§※§\t\n\n");
printf("\n\t＃＃＃＃＃＃＃＃＃＃＃#＃＃＃＃ 1。 车辆到达登记。##＃＃#＃＃##＃＃＃＃#＃#\t\n”）；
printf（"\n\t#＃#＃＃＃＃###＃##＃## 2 车辆离开登记。＃＃＃＃#＃＃#＃＃#＃＃#＃＃\t\n"）；
printf(”\n\t#＃＃＃#＃＃＃＃＃##＃＃＃＃ 3。 车辆列表显示.###＃＃＃#＃＃＃＃＃#＃＃＃\t\n”）；
printf（”\n\t＃#＃＃＃#＃＃##＃#＃＃## 4。 退出系统. ＃###＃＃#＃＃＃##＃#＃#\t\n\n"）;
while(1)
{
printf（” 请选择： "）;
scanf（"%d”，&ch）;
if（ch〉=1＆＆ch〈=4）break；
else printf（”\n 输入有误,请重新选择： 1～4： ”）;
｝
switch（ch）
{
case 1：Arrival（&Enter,＆Wait)； break；
case 2：Leave(&Enter，＆Temp，＆Wait）；break；
case 3：List（Enter，Wait）;break;
case 4:exit(0）；
default: break;
｝
｝
｝
// 自定义函数
void InitStack（SeqStackCar *s)｛ // 栈的初始化
int i;
s—〉top=0;
for（i=0;i<=MAX;i++)
s-〉stack［s-〉top]=NULL；
｝
int InitQueue(LinkQueueCar *Q）｛ // 队列的初始化
Q->head=(QueueNode ＊)malloc(sizeof(QueueNode));
if（Q-〉head！=NULL)
｛
Q—>head->next=NULL;
Q—〉rear=Q—>head；
return(1）；
}
else return(—1)；
}
float PRINTE（CarNode *p,int room）｛ // 车辆收费
int A1，A2，B1，B2;
printf（"\n车辆离开便道的时间：”）;
scanf（"%d：％d”，＆(p—〉leave.hour),&（p—>leave。min)）；
printf（"\n离开车辆的车牌号为："）;
puts(p—>num）；
printf("\n其到达便道时间为： ％d:％d",p->reach.hour,p—〉reach。min）；
printf（”\n离开便道时间为: ％d:％d”,p—>leave。hour，p—〉leave。min);
A1=p—〉reach.hour；
A2=p-〉reach。min；
B1=p—〉leave.hour;
B2=p-〉leave.min；
printf（"\n应交费用为： ％2.1f元"，（（B1—A1）＊60+（B2—A2)）*pricee)；
return（（（B1—A1）*60+（B2—A2)）＊pricee）；
free(p）；
}
void PRINT(CarNode ＊p,int room){ // 车辆收费
int A1，A2,B1，B2；
printf（”\n车辆离开的时间:"）;
scanf（”%d：％d"，＆（p—>leave。hour），&（p—〉leave。min))；
printf(”\n离开车辆的车牌号为:”）；
puts(p—>num);
printf（”\n其到达停车位时间为: ％d:％d",p—〉reach。hour，p—〉reach。min)；
printf（”\n离开停车位时间为: ％d：％d”，p—〉leave。hour，p->leave。min)；
A1=p—>reach.hour；
A2=p-〉reach。min;
B1p—〉leave.hour;
B2=p—>leave.min;
printf（”\n应交费用为： %2.1f元”，（（B1—A1）＊60+（B2—A2））＊price+PRINTE(p，room））;
free(p）；
}
// 车辆的到达登记
int Arrival(SeqStackCar ＊Enter，LinkQueueCar ＊W）{
CarNode ＊p；
QueueNode ＊t;
p=（CarNode *）malloc（sizeof(CarNode））;
flushall(）;
printf(”\n请输入车牌号（例：豫B1234）:”）；
gets(p—〉num）;
if（Enter—〉top〈MAX）
{
Enter—>top++;
printf(”\n车辆在车场第％d位置."，Enter—>top);
printf("\n车辆到达时间：")；
scanf（"％d：%d"，＆（p—>reach。hour)，＆（p—>reach.min）);
Enter->stack[Enter->top］=p;
return（1）；
｝
else
｛
printf("\n该车须在便道等待!有车位时进入车场”);
t=（QueueNode ＊）malloc（sizeof（QueueNode））;
t—>data=p；
t—〉next=NULL;
W->rear-〉next=t;
W-〉rear=t；
printf（"请输入进入便道的时间”）；
scanf(”％d:%d”,＆(p—〉reach。hour)，＆(p-〉reach.min）)；
return（1）；
}
｝
void Leave(SeqStackCar ＊Enter，SeqStackCar ＊Temp,LinkQueueCar *W)
｛ //车辆的离开
int room;
CarNode ＊p，＊t;
QueueNode ＊q；
if（Enter->top〉0） // 判断车场是否为空
｛
while（1）
｛
printf（”\n请输入车在车场的位置/1-—％d/:”，Enter-〉top);
scanf(”％d"，＆room)；
if（room〉=1&&room〈=Enter—>top) break；
else printf（"\n 输入有误，请重输: ”);
｝
while（Enter—〉top〉room） // 把要删除的车辆的前面的车开出来,进临时栈。
｛
Temp—>top++;
Temp—〉stack［Temp—〉top］=Enter—〉stack［Enter—>top];
Enter—>stack［Enter->top］=NULL；
Enter—>top—-；
}
p=Enter->stack［Enter—〉top］; //把要删除的车辆节点赋给p.
Enter—>stack［Enter-〉top］=NULL；
Enter-〉top—-；
while（Temp—>top>=1） // 再把临时栈里德车辆进停车场
{
Enter—>top++;
Enter—〉stack[Enter—〉top]=Temp—〉stack［Temp—〉top］；
Temp—〉stack[Temp-〉top］=NULL；
Temp—>top—-;
｝
PRINT（p,room)； // 调用计费函数计费。。
if（(W—>head!=W—>rear）＆＆Enter—〉topnext;
t=q-〉data；
Enter->top++；
printf（”\n便道的％s号车进入车场第％d位置.”，t—〉num，Enter—〉top)；
printf(”\n请输入%s号车进入车场的时间:”,t->num）；
scanf（"%d：%d",&（t—〉reach。hour),＆（t—〉reach.min））；
// t-〉leave 。hour =t->reach。hour;
//t—〉leave 。min =t-〉reach。min;
W-〉head->next=q—〉next;
if（q==W—>rear) W—>rear=W—>head；
Enter—>stack［Enter—〉top］=t；
PRINTE（t，room）；
free(q)；
｝
else printf（”\n便道里没有车。\n”）；
}
else printf(”\n车场里没有车.”）;
｝
void List1(SeqStackCar *S) //显示车场里的车辆情况
｛
int i；
if（S-〉top>0)
｛
printf（”\n车场：”）；
printf（”\n 位置 到达时间 车牌号\n”）；
for(i=1；i〈=S—〉top；i++)
｛
printf（” ％d "，i)；
printf（" ％d：％d ”,S—>stack[i］—>reach.hour,S—〉stack[i］—〉reach。min）；
puts(S—>stack[i］—〉num)；
}
｝
else printf("\n车场里没有车”）；
｝
void List2（LinkQueueCar ＊W） //显示便道上的车辆情况
｛
QueueNode ＊p;
int i;
p=W—>head—>next;
if(W-〉head!=W—〉rear)
｛
printf（”\n等待车辆的号码为：”);
fori=1； （p!=NULL）; i++)
｛
printf(”\n第 %d 车辆。”,i）;
puts（p-〉data->num）;
p=p—〉next ；
｝
｝
else printf（"\n便道里没有车。”);
printf（"\n”)；
｝
void List（SeqStackCar S，LinkQueueCar W) //显示，遍历
｛
int flag，tag;
flag=1；
while(flag)
{
printf（” 查看车辆列表显示： ”）；
printf（"\n 1。车场列表\n 2。便道列表\n 3。返回主菜单\n”)；
printf(”\n请选择 1~3：”）;
while（1)
｛
scanf（”％d”,＆tag)；
if(tag〉=1 &＆ tag〈=3） break;
else printf（”\n 输入有误，请重新选择 1～3:"）；
｝
switch(tag）
｛
case 1:List1（＆S）;break;
case 2：List2（＆W）;break;
case 3:flag=0; system("cls"）; break;
default: break；
｝
}
}