数据结构课程设计《停车场管理系统》.doc

数据结构
设计:停车场管理
姓名:韦邦权
专业：2013级计算机科学与技术
学号：13224624
班级：13052316
完成日期：2013。12。19
1 问题描述
设停车场是一个可停放n辆汽车的狭长通道,且只有一个门可供出入。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列（门在最南端，最先到达的第一辆车停放在车场的最北端）,若车场内已停满n辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆汽车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原顺序进入车场,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。
2 需求分析
（1）根据车辆到达停车场到车辆离开停车场时所停留的时间进行计时收费。
(2）当有车辆从停车场离开时，等待的车辆按顺序进入停车场停放。实现停车场的调度功能。
（3）用顺序栈来表示停车场，链队表示停车场外的便道.
（4）显示停车场信息和便道信息。
（5）程序执行的命令为：车辆进入停车场 车辆离开停车场 显示停车场的信息。
3 概要设计
3．1抽象数据类型定义
(1）栈的抽象数据类型定义
AST Stack｛
数据对象：D={ai｜ai∈ElemSet，i=1,2，.。.,n， n≥0｝
数据关系：R1=｛〈ai—1,ai>｜ai-1，ai∈D，i=2,.。。，n｝
约定an端为栈顶，a1端为栈底。
基本操作:
 InitStack(＆S）
 操作结果：构造一个空栈S.
DestroyStack（&S)
初始条件:栈S已存在。
操作结果：栈S被销毁。
ClearStack(&S)
初始条件:栈S已存在。
操作结果：将栈S清为空栈。
StackEmpty(S）
初始条件：栈S已存在。
操作结果:若栈S为空栈,则返回TRUE，否则FALSE。
StackLength（s)
初始条件：栈S已存在。
操作结果:返回S的元素个数，既栈的长度。
GetTop（S，＆e）
初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
Push（＆S，e)
初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop（＆S,＆e)
初始条件:栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
StackTraverse（S，visit(））
初始条件：栈S已存在且非空。
 操作结果:从栈底到栈顶依次对S的每个数据元素调用函数visit（）。一旦visit（）失败,则操作失效.
｝ADT Stack
（2）队列的抽象数据类型定义
ADT Queue｛
数据对象：D=｛ai｜ai∈ElemSet，i=1,2，.。。,n，n≥0}
数据关系：R1=｛<ai-1，ai〉｜ai—1，ai∈D，i=2,。..，n｝
约定其中a1端为队列头，an为队列尾.
基本操作:
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返回的队头元素。
EnQueue（&Q,e）
初始条件：队列Q已存在。
操作结果:插入元素e为Q的新的队尾元素。
DeQueue（&Q，＆e）
初始条件：Q为非空队列。
操作结果:删除Q的队头元素，并用e返回其值。
QueueTraverse（Q，visit（））
初始条件:Q已存在且非空。
操作结果:从队头到队尾，依次对Q的每个数据元素调用函数visit(）.一旦visit（） 失败,则操作失败.
｝ADT Queue
3．2模块划分
本程序包括六个模块:
(1）主程序模块
void main（）
｛
初始化停车站；
初始化让路的临时栈;
初始化通道；
输出主菜单：车辆到达、车辆离开与计费、查看停车场信息;
｝
（2)入场模块
int arrive（SqStack *In,LinkQueue ＊W）
｛
车辆进入停车场；
计算停车费用
}
（3)出场模块
void leave（SqStack ＊In，SqStack ＊Out，LinkQueue *W）
｛
车辆离开停车场；
｝
（4）输出模块
void info（SqStack S,LinkQueue W)
{
输出停车场信息;
}
（5）栈模块——实现栈的抽象数据类型
（6）队列模块-—实现队列的抽象数据类型
4 详细设计
4．1数据类型的定义
int MAX; /*定义一个全局变量用来存储车库最大容量＊/
float price；/* 定义一个全局变量用来存储每车每小时的费用＊/
typedef struct time
｛
int hour;
int min；
｝Time； /*时间结点＊/
typedef struct node
｛
char num[10］;
Time reach；
Time leave；
}Car; /*车辆信息结点＊/
typedef struct NODE
{
Car *stack［100］；
int top；
}SqStack； /＊停车站＊/
typedef struct car
{
Car *data；
struct car ＊next；
｝QNode；
typedef struct Node
｛
QNode ＊head；
QNode ＊rear；
｝LinkQueue； /*通道*/
4．2主要模块的算法描述
本程序主要分为四部分：(1)主函数及程序框架、(2)车辆到达模块、（3)车辆离开模块、（4）显示车辆信息模块，
（1）主函数
void main（）
{
SqStack In，Out; LinkQueue Wait;
int ch;
InitStack（＆In); /*初始化停车站＊/
InitStack（&Out）； /*初始化让路的临时栈*/
InitQueue（&Wait)； /＊初始化通道＊/
while(1)
{
printf("——---—————————-———--欢迎使用停车场管理系统-—-—--—---———-——————\n")；
printf(”\t本系统由5011工作室开发，作者：邓春国、段庆龙、梁伟明、丁磊.\n\n"）;
printf（"请输入停车场的容量：”);
scanf（”％d”，＆MAX)；
printf（”请输入停车场的收费标准(元/小时）：”）；
scanf（"％f"，＆price）;
printf（"您输入的停车场容量为%d位，费用为％2。1f元/小时.\n”，MAX,price)；
printf(”\n（1）车辆到达\n（2）车辆离开\n（3)停车场信息\n(4)退出系统\n请选择\n”)；
while（1）
｛
ch=getch（）；
switch(ch)
｛
case 49:arrive(＆In,&Wait);break; /＊车辆到达*/
case 50：leave(&In，＆Out，&Wait）；break; /*车辆离开＊/
case 51：info（In，Wait）;break； /＊输出车站信息*/
case 52：｛printf（"谢谢使用!”）;exit（0）；} /＊退出主程序＊/
default：printf("\n按键无效，请重新按键选择！”)；
}/＊49—52分别表示“1"—“4"这四个按键的键值*/
system(”CLS”）；
printf（"-———--—--—-——-—--—--欢迎使用停车场管理系统———--—-—-———————---—\n”）；
printf（"\t本系统由CG工作室开发，作者:邓春国、段庆龙、梁伟明、丁磊。\n\n\n”)；
printf(”您输入的停车场容量为%d位，费用为％2。1f元/小时。\n"，MAX，price）；
printf（"\n（1）车辆到达\n（2）车辆离开\n（3）停车场信息\n(4)退出系统\n请选择\n"）;
}
｝
｝
（2）车辆离开模块
算法分析
void leave(SqStack ＊In，SqStack ＊Out,LinkQueue ＊W） /*车辆离开＊/
{
int room；
Car ＊p，*t；QNode ＊q;
/＊开始定义一个整型变量room,用来记录要离开的车辆在停车场的位置,定义车辆结点指针p和t和队列结点指针q.＊/
if（In-〉top>0) /＊有车*/
｛
while（1)
{
printf（”\n请输入车在停车场的位置(1-％d)：",In—>top）；
scanf（”％d"，&room)；
if(room>=1&&room〈=In->top） break；
｝
/＊判断停车场内是否有车，如果有车，就输入要离开的车辆在停车场的位置，否则就提示停车场没车。这里用了while循环语句，如果输入的车辆位置超出范围,就要重新输入.＊/
while(In—>top>room） /＊车辆离开＊/
｛
Out—〉top++；
Out-〉stack［Out->top]=In->stack［In—〉top］；
In—>stack[In->top］=NULL；In—〉top--;
｝
/*如果栈顶位置In—〉top大于要离开的车位置room(即要离开的车不在停车场的门口）的话，在要离开的车辆前面的车就要先离开，开到临时停车场，即临时栈中，因此Out所表示的临时栈的栈顶top加1，用来表示临时停车场增加1辆车；接着把该车的信息拷贝到栈Out中，然后删除栈In的栈顶(即这辆车开走).*/
p=In-〉stack［In—〉top]；
In-〉stack[In->top]=NULL；In—>top--;
while(Out-〉top>=1)
｛
In->top++;In—>stack［In-〉top］=Out-〉stack[Out—〉top］；
Out—>stack［Out—〉top］=NULL; Out—〉top——;
｝
/*直到要离开的车辆前面的车都开到临时停车场之后，该车才离开,离开之后，该车的信息结点In-〉stack［In—〉top］置空，然后栈顶In—〉top减1.之后就判断临时停车场是否有车,有车就一辆一辆的开回停车场里面,因此停车场的栈顶In—〉top 加1，然后就把临时停车场的车结点的信息拷贝到停车场的车结点上，接着删除临时停车场车的结点 (即Out—〉stack［Out—>top]=NULL；Out—〉top-—;）。＊/
PRINT（p，room);
if（（W—〉head!=W-〉rear）＆＆In->top〈MAX）
{
q=W—〉head—>next；t=q—>data;In—〉top++；
printf（”\n便道的％s号车进入车场第％d号停车位."，t—〉num，In—〉top);
printf（"\n请输入现在的时间（格式“*＊：*＊”）："）;
scanf（”％d：%d"，&（t—〉reach。hour)，＆（t—>reach.min）)；
W—>head-〉next=q-〉next；
if（q==W—〉rear） W—〉rear=W-〉head；
In->stack[In-〉top］=t;
free（q）;
}
/*判断（W—〉head！=W—>rear)&＆In—〉top〈MAX（即通道上是否有车及停车场是否已满）,如果便道有车且停车场未满，通道的车便可进入停车场，此时指针q指向便道的头，即队头，然后停车场的栈顶In—〉top 加1以便增加新的车辆，接着输入队头的车辆信息，即要进去停车场的车的信息，然后便道队列的头结点指向q（即刚进入停车场的车的结点）的后继结点，即原队列中第二辆车的结点，接着判断刚离开的车是否是最后一辆车，如果是，就把队列置空，即队头等于队尾;之后就把结点t(即要进入停车场的车）的信息拷贝到停车场栈顶的车中，最后释放p的空间，即原队头结点。＊/
}
else printf(”\n停车场里没有车\n”）； /*没车＊/
printf（”请按任意键返回”)；
getch(）；
}
leave函数流程图如图4。1所示：
结束

开始

判断停车场是否有车
图4.1 leave函数流程图
否
是
是
是
车临时停车场的车回到停车场
便道的车先进入停车场
否
判断便道否有车
否
判断前面是否有其他车且停车场未满
输入离开车辆的信息
车辆离开
前面的车先进入临时停车场
输出停车场里没有车
定义必要的变量
5 测试分析
测试数据及结果如下:
输入2辆车的信息，如图5.2所示:
再输入2辆车的信息,如图
最后选择车辆离开，输入第2辆车离开,如图
6 课程设计总结
通过这次课程设计使我充分的理解了用栈和队列实现模拟停车场的基本原理,知道了栈的顺序存储结构和队列的链式存储结构的定义和算法描述，同时也学会了编写停车场问题的程序。虽然此次的程序不是很完备，没有加入一些更完善的功能，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。在刚开始编程的时候，我感到有点无从下手，但经过对题目的详细分析和思考之后,我就知道具体应该做什么,怎么做了.经过几天和同学的一起研究,我完成这个程序，我学到了很多东西，这是在课堂上无法做到的。
源程序
＃include〈stdio。h〉
＃include 〈stdlib。h>
＃include<iostream。h〉
#include<string。h>
＃include<math。h〉
＃define size 1 //停车场位置数
//模拟停车场的堆栈的性质;
typedef struct zanlind{
int number; //汽车车号
int ar_time； //汽车到达时间
｝zanInode;
typedef struct{
zanInode ＊base； //停车场的堆栈底
zanInode ＊top； //停车场的堆栈顶
int stacksize_curren；
}stackhead;
//堆栈的基本操作；
void initstack(stackhead ＆L) //构造一个空栈
｛
L.base=（zanInode＊)malloc(size＊sizeof（zanlind))；
if（！L。base) exit(0）；
L.top=L。base；
L.stacksize_curren=0;
｝
void push（stackhead &L，zanInode e） //把元素e压入s栈
｛
*L.top++=e;
L。stacksize_curren++；
｝
void pop(stackhead &L,zanInode &e） //把元素e弹出s栈
｛
if(L.top==L。base)
｛
cout<〈”停车场为空 ！!”；
return;
｝
e=＊—-L。top；
L。stacksize_curren-—；
}
//模拟便道的队列的性质；
typedef struct duilie｛
int number； //汽车车号
int ar_time； //汽车到达时间
struct duilie *next；
｝*queueptr;
typedef struct｛
queueptr front； //便道的队列的对头
queueptr rear； //便道的队列的队尾
int length;
}linkqueue；
//队列的基本操作；
void initqueue（linkqueue ＆q） //构造一个空队列
｛
q。front=q.rear=(queueptr）malloc（sizeof（duilie））;
if（！q。front｜｜！q。rear)
exit（0);
q。front->next=NULL;
q。length=0；
｝
void enqueue（linkqueue ＆q，int number，int ar_time） //把元素的插入队列（属性为number，ar_time)
{
queueptr p；
p=（queueptr）malloc(sizeof（duilie）)；
if（！p) exit（0)；
p—〉number=number；
p—〉ar_time=ar_time;
p—>next=NULL；
q。rear-〉next=p；
q。rear=p；
q.length++；
}
void popqueue（linkqueue &q，queueptr &w) //把元素的插入队列（属性为number,ar_time）
{
queueptr p；
if（q.front==q。rear）
｛
cout〈〈”停车场的通道为空 ！ !"<〈endl;
return；
}
p=q.front—〉next;
w=p；
q。front—>next=p—〉next；
q。length——；
if(q.rear==p） q。front=q。rear；
｝
void jinru（stackhead ＆st,linkqueue ＆q) //对进入停车场的汽车的处理；
｛
int number,time_a;
cout<〈”车牌为：”；
cin>〉number;
cout〈<"进场的时刻:"；
cin>〉time_a；
if（st。stacksize_curren〈2)
｛
zanInode e；
e。number=number;
e.ar_time=time_a；
push(st，e）;
cout〈〈 ” 该车已进入停车场在: "〈<st。stacksize_curren〈〈” 号车道"<〈endl<<endl;
}
else
｛
enqueue（q,number,time_a）；
cout<<”停车场已满,该车先停在便道的第”〈〈q。length〈〈”个位置上”<<endl;
}
}
void likai(stackhead &st，stackhead &sl,linkqueue ＆q） //对离开的汽车的处理；
{ //st堆栈为停车场，sl堆栈为倒车场
int number，time_d，flag=1，money,arrivaltime； //q为便道队列
cout〈〈"车牌为:”;
cin>〉number；
cout<〈”出场的时刻:”；
cin>>time_d；
zanInode e,q_to_s;
queueptr w;
while（flag） //找到要开出的车,并弹出停车场栈
{
pop（st，e)；
push（sl，e）；
if（e。number==number）
｛
flag=0;
money=（time_d—e.ar_time）＊2；
arrivaltime=e。ar_time;
｝
}
pop(sl，e）; //把临时堆栈的第一辆车（要离开的)去掉；
while（sl.stacksize_curren) //把倒车场的车倒回停车场
{
pop(sl，e）；
push(st，e)；
}
if（st.stacksize_curren<2＆&q.length！=0） //停车场有空位，便道上的车开进入停车场
｛
popqueue(q，w）;
q_to_s。ar_time=time_d；
q_to_s。number=w—>number；
push（st，q_to_s)；
cout<<”车牌为”〈<q_to_s.number〈〈”的车已从通道进入停车场,所在的停车位为:”〈<st。stacksize_curren〈〈endl<〈endl；
｝
cout〈<"\n 收 据”〈<endl；
cout<〈” ====================== 车牌号： "〈〈number〈〈endl；
cout〈〈”==================================================="<<endl；
cout〈〈”｜进车场时刻 | 出车场时刻 | 停留时间 ｜ 应付(元）｜”〈〈endl;
cout<〈”====================================================”〈〈endl；
cout<〈”| ”〈<arrivaltime〈〈” ｜ ”〈〈time_d〈〈” ｜ ”<<time_d-arrivaltime〈〈” ｜ ”<<money〈〈” ｜"<<endl；
cout<<”-—-—————-—-—————--—-—-—-——-—-————————-————----—-—————”<〈endl〈〈endl；
｝
void main（）
{
int m=100；
char flag； //进入或离开的标识；
stackhead sting，slinshi； //停车场和临时倒车场堆栈的定义;
linkqueue line； //队列的定义；
initstack（sting）； //构造停车场堆栈sting
initstack(slinshi）; //构造倒车场堆栈slinshi
initqueue(line）； //构造便道队列line
while(m)
{
cout<〈"\n ＊＊ 停车场管理程序 ＊*”〈〈endl；
cout<〈”==================================================="〈<endl;
cout〈<”** **"<〈endl；
cout〈<”＊＊ A ——- 汽车 进 车场 D ——— 汽车 出 车场 ＊*"〈〈endl；
cout〈〈”*＊ ＊*”〈<endl;
cout<<”*＊ E -—— 退出 程序 ＊＊"〈〈endl;
cout〈〈”===================================================”〈〈endl；
cout〈<" 请选择 :(A，D,E): ”；
cin〉〉flag;
switch（flag)
｛
case ’A': jinru（sting，line);break； //汽车进车场
case 'D’： likai（sting，slinshi，line）；break； //汽车出车场
case ’E’: exit（0）；
｝
m—-;
｝
｝
15