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

1、目 录1 问题描述12 需求分析13 概要设计131抽象数据类型定义132模块划分34 详细设计541数据类型的定义542主要模块的算法描述65 测试分析116 课程设计总结14参考文献14附录（源程序清单）151 问题描述设停车场是一个可停放n辆汽车的狭长通道，且只有一个门可供出入。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆汽车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆

2、再按原顺序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。2 需求分析（1）根据车辆到达停车场到车辆离开停车场时所停留的时间进行计时收费。（2）当有车辆从停车场离开时，等待的车辆按顺序进入停车场停放。实现停车场的调度功能。（3）用顺序栈来表示停车场，链队表示停车场外的便道。（4）显示停车场信息和便道信息。（5）程序执行的命令为：车辆进入停车场 车辆离开停车场 显示停车场的信息。3 概要设计31抽象数据类型定义（1）栈的抽象数据类型定义AST Stack数据对象：D=ai|aiElemSet,i=1,2,.,n, n0数据关系：R1=|ai-1,aiD，i=2,.,n

3、约定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为新的栈顶元素

4、。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse(S,visit()初始条件：栈S已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失效。ADT Stack（2）队列的抽象数据类型定义ADT Queue数据对象：D=ai|aiElemSet,i=1,2,.,n,n0数据关系：R1=|ai-1,aiD,i=2,.,n约定其中a1端为队列头，an为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q

5、已存在。操作结果：队列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返回其值。QueueTr

6、averse(Q,visit()初始条件：Q已存在且非空。操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。ADT Queue 32模块划分本程序包括六个模块：（1）主程序模块void main()初始化停车站；初始化让路的临时栈；初始化通道；输出主菜单：车辆到达、车辆离开与计费、查看停车场信息；（2）入场模块int arrive(SqStack *In,LinkQueue *W)车辆进入停车场；计算停车费用（3）出场模块void leave(SqStack *In,SqStack *Out,LinkQueue *W)车辆离开停车场；（4

7、）输出模块void info(SqStack S,LinkQueue W) 输出停车场信息； （5）栈模块实现栈的抽象数据类型（6）队列模块实现队列的抽象数据类型4 详细设计41数据类型的定义int MAX; /*定义一个全局变量用来存储车库最大容量*/ float price;/* 定义一个全局变量用来存储每车每小时的费用*/ typedef struct time int hour; int min; Time; /*时间结点*/ typedef struct node char num10; Time reach; Time leave; Car; /*车辆信息结点*/ typedef

8、struct NODE Car *stack100; int top; SqStack; /*停车站*/ typedef struct car Car *data; struct car *next; QNode; typedef struct Node QNode *head; QNode *rear; LinkQueue; /*通道*/ 42主要模块的算法描述本程序主要分为四部分：（1）主函数及程序框架、（2）车辆到达模块、（3）车辆离开模块、（4）显示车辆信息模块，由梁伟明、段庆龙、丁磊和我合作编写，我主要负责leave（车辆离开）函数部分。（1）主函数void main() SqSta

9、ck In,Out; LinkQueue Wait; int ch; InitStack(&In); /*初始化停车站*/ InitStack(&Out); /*初始化让路的临时栈*/ InitQueue(&Wait); /*初始化通道*/ while(1) printf(-欢迎使用停车场管理系统-n);printf(t本系统由5011工作室开发，作者:邓春国、段庆龙、梁伟明、丁磊。nn);printf(请输入停车场的容量:);scanf(%d,&MAX);printf(请输入停车场的收费标准(元/小时):);scanf(%f,&price);printf(您输入的停车场容量为%d位，费用为%

10、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按键无效，请重新按键选择！);/

11、*49-52分别表示“1”-“4”这四个按键的键值*/system(CLS);printf(-欢迎使用停车场管理系统-n);printf(t本系统由CG工作室开发，作者:邓春国、段庆龙、梁伟明、丁磊。nnn);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;

12、/*开始定义一个整型变量room，用来记录要离开的车辆在停车场的位置，定义车辆结点指针p和t和队列结点指针q。*/ if(In-top0) /*有车*/ while(1) printf(n请输入车在停车场的位置(1-%d)：,In-top); scanf(%d,&room); if(room=1&roomtop) break; /*判断停车场内是否有车，如果有车，就输入要离开的车辆在停车场的位置，否则就提示停车场没车。这里用了while循环语句，如果输入的车辆位置超出范围，就要重新输入。*/while(In-toproom) /*车辆离开*/Out-top+;Out-stackOut-top=

13、In-stackIn-top;In-stackIn-top=NULL;In-top-;/*如果栈顶位置In-top大于要离开的车位置room（即要离开的车不在停车场的门口）的话，在要离开的车辆前面的车就要先离开，开到临时停车场，即临时栈中，因此Out所表示的临时栈的栈顶top加1，用来表示临时停车场增加1辆车；接着把该车的信息拷贝到栈Out中，然后删除栈In的栈顶（即这辆车开走）。*/p=In-stackIn-top; In-stackIn-top=NULL;In-top-;while(Out-top=1) In-top+;In-stackIn-top=Out-stackOut-top; Ou

14、t-stackOut-top=NULL; Out-top-; /*直到要离开的车辆前面的车都开到临时停车场之后，该车才离开，离开之后，该车的信息结点In-stackIn-top置空，然后栈顶In-top减1。之后就判断临时停车场是否有车，有车就一辆一辆的开回停车场里面，因此停车场的栈顶In-top 加1，然后就把临时停车场的车结点的信息拷贝到停车场的车结点上，接着删除临时停车场车的结点 (即Out-stackOut-top=NULL;Out-top-;)。*/PRINT(p,room); if(W-head!=W-rear)&In-tophead-next;t=q-data;In-top+;

15、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-stackIn-top=t; free(q);/*判断(W-head!=W-rear)&In-toptop 加1以便增加新的车辆，接着输入队头的车辆信息，即要进去停车场的车的信息，然后便道队列的头结点指向q（即刚进入停车场的车的结点）的后继结点，即原队列中第二辆车的结

16、点，接着判断刚离开的车是否是最后一辆车，如果是，就把队列置空，即队头等于队尾；之后就把结点t（即要进入停车场的车）的信息拷贝到停车场栈顶的车中，最后释放p的空间，即原队头结点。*/ else printf(n停车场里没有车n); /*没车*/printf(请按任意键返回);getch(); leave函数流程图如图4.1所示：结束开始判断停车场是否有车图4.1 leave函数流程图否是是是车临时停车场的车回到停车场便道的车先进入停车场否判断便道否有车否判断前面是否有其他车且停车场未满输入离开车辆的信息车辆离开前面的车先进入临时停车场输出停车场里没有车定义必要的变量5 测试分析测试数据及结果如下

17、：输入停车场的容量4，收费5元/小时，接着查看停车场的信息，如图5.1所示：图5.1 停车场系统初始化示意图接着输入4辆车的信息，然后查看停车场信息，如图5.2所示：图5.2 车辆进入停车场示意图再输入1辆车的信息，然后查看停车场信息，如图5.3(a)和图5.3(b)所示：图5.3(a) 车辆进入便道示意图图5.3(b) 车辆进入便道示意图最后选择车辆离开，输入第2辆车离开，再查看停车场信息，如图5.4(a)和图5.4(b)所示：图5.4(a) 车辆离开示意图图5.4(b) 车辆离开示意图6 课程设计总结通过这次课程设计使我充分的理解了用栈和队列实现模拟停车场的基本原理，知道了栈的顺序存储结构

18、和队列的链式存储结构的定义和算法描述，同时也学会了编写停车场问题的程序。虽然此次的程序不是很完备，没有加入一些更完善的功能，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。在刚开始编程的时候，我感到有点无从下手，但经过对题目的详细分析和思考之后，我就知道具体应该做什么，怎么做了。经过几天和同组同学的一起研究，我们分工完成了这个程序，完成这个程序，我学到了很多东西，这是在课堂上无法做到的。在此我非常要感谢的是我的指导老师成娅辉老师，感谢老师的细心认真的辅导，让我对数据结构这门课程掌握得更好，懂得更多，她教我怎么分析问题，应该要注意些什么，最后还指出我存在的问

19、题。参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，2003附录（源程序清单）#include stdio.h #include stdlib.h #include string.h #include conio.hint MAX; /*定义一个全局变量用来存储车库最大容量*/ float price;/*每车每小时的费用*/ typedef struct

20、time int hour; int min; Time; /*时间结点*/ typedef struct node char num10; Time reach; Time leave; Car; /*车辆信息结点*/ typedef struct NODE Car *stack100; int top; SqStack; /*停车站*/ typedef struct car Car *data; struct car *next; QNode; typedef struct Node QNode *head; QNode *rear; LinkQueue; /*通道*/ void Init

21、Stack(SqStack *); /*初始化栈*/ int InitQueue(LinkQueue *); /*初始化便道*/ int arrive(SqStack *,LinkQueue *); /*车辆到达*/ void leave(SqStack *,SqStack *,LinkQueue *); /*车辆离开*/ void info(SqStack,LinkQueue); /*显示停车场信息*/ void PRINT(Car *p,int room);void InitStack(SqStack *s) /*初始化栈*/ int i; s-top=0; for(i=0;istacks

22、-top=NULL; int InitQueue(LinkQueue *Q) /*初始化便道*/ Q-head=(QNode *)malloc(sizeof(QNode); if(Q-head!=NULL) Q-head-next=NULL; Q-rear=Q-head; return(1); else return(-1); void main() SqStack In,Out; LinkQueue Wait; int ch; InitStack(&In); /*初始化停车站*/ InitStack(&Out); /*初始化让路的临时栈*/ InitQueue(&Wait); /*初始化通道

23、*/ while(1) printf(-欢迎使用停车场管理系统-n);printf(t本系统由5011工作室开发，作者:邓春国、段庆龙、梁伟明、丁磊。nn);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

24、,&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工作室开发，作者:邓春国、段庆龙、梁伟明、丁磊。nnn);printf(您输入的停车

25、场容量为%d位，费用为%2.1f元/小时。n,MAX,price);printf(n(1)车辆到达n(2)车辆离开n(3)停车场信息n(4)退出系统n请选择n); int arrive(SqStack *In,LinkQueue *W) /*车辆到达*/ Car *p; QNode *t; p=(Car *)malloc(sizeof(Car); flushall(); printf(n停车场还有%d停车位(若停车位为0，车可先进入便道等待),MAX-In-top);printf(n请输入车牌号码(例:湘D0734):); gets(p-num); if(In-toptop+;printf(n

26、停车的位置:%d号停车位。,In-top); printf(n请输入车到达的时间(格式“*:*”):); scanf(%d:%d,&(p-reach.hour),&(p-reach.min); In-stackIn-top=p;printf(请按任意键返回);getch(); return(1); else /*停车场已满，车进便道*/ printf(n停车位已满，该车须在便道等待！); t=(QNode *)malloc(sizeof(QNode); t-data=p; t-next=NULL; W-rear-next=t; W-rear=t; printf(请按任意键返回); getch(

27、);return(1); void leave(SqStack *In,SqStack *Out,LinkQueue *W) /*车辆离开*/ int room; Car *p,*t; QNode *q; /*判断车场内是否有车*/ if(In-top0) /*有车*/ while(1) /*输入离开车辆的信息*/ printf(n请输入车在停车场的位置(1-%d)：,In-top); scanf(%d,&room); if(room=1&roomtop) break; while(In-toproom) /*车辆离开*/ Out-top+; Out-stackOut-top=In-stack

28、In-top; In-stackIn-top=NULL; In-top-; p=In-stackIn-top; In-stackIn-top=NULL; In-top-; while(Out-top=1) In-top+; In-stackIn-top=Out-stackOut-top; Out-stackOut-top=NULL; Out-top-; PRINT(p,room); /*判断通道上是否有车及车站是否已满*/ if(W-head!=W-rear)&In-tophead-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-stackIn-top=t; free(q); else printf