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

1、.数据结构设计：停车场管理姓名：韦邦权专业： 2013 级计算机科学与技术学号： 13224624班级： 13052316完成日期： 2013.12.19精选文档.1 问题描述设停车场是一个可停放 n 辆汽车的狭长通道， 且只有一个门可供出入。 汽车在停车场内按车辆到达时间的先后顺序， 依次由北向南排列 （门在最南端， 最先到达的第一辆车停放在车场的最北端） ，若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道上等候， 一旦有车开走， 则排在便道上的第一辆汽车即可开入； 当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路， 待该辆车开出大门外，其他车辆再按原顺序进入车场，

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

3、,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)初始条件：栈

4、 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=

5、<ai-1,ai>|ai-1,ai D,i=2,.,n约定其中 a1端为队列头， an 为队列尾。基本操作：精选文档.InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列操作结果：队列QQ已存在。被销毁，不再存在。ClearQueue(&Q)初始条件：队列 Q 已存在。操作结果：将 Q 清为空队列。QueueEmpty(Q)初始条件：队列 Q 已存在。操作结果：若 Q 为空队列，则返回TRUE，否则 FALSE。QueueLength(Q)初始条件：队列操作结果：返回QQ已存在。的元素个数，即队列的长度。Get

6、Head(Q,&e)初始条件： Q 为非空队列。操作结果：用 e 返回的队头元素。EnQueue(&Q,e)初始条件：队列 Q 已存在。操作结果：插入元素e 为 Q 的新的队尾元素。DeQueue(&Q,&e)初始条件： Q 为非空队列。操作结果：删除Q 的队头元素，并用e 返回其值。QueueTraverse(Q,visit()初始条件： Q 已存在且非空。操作结果：从队头到队尾，依次对Q 的每个数据元素调用函数visit()。一旦visit() 失败，则操作失败。ADT Queue32 模块划分本程序包括六个模块：（ 1）主程序模块精选文档.void mai

7、n()初始化停车站；初始化让路的临时栈；初始化通道；输出主菜单：车辆到达、车辆离开与计费、查看停车场信息；（ 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 详细设计41 数据类型的定义int MAX; /* 定义一个全局变

8、量用来存储车库最大容量*/float price;/* 定义一个全局变量用来存储每车每小时的费用*/typedef struct timeint hour;int min;Time; /* 时间结点 */typedef struct nodechar num10;Time reach;Time leave;Car; /* 车辆信息结点 */typedef struct NODECar *stack100;int top;SqStack; /*停车站 */typedef struct carCar *data;struct car *next;QNode;typedef struct Node精

9、选文档.QNode *head;QNode *rear;LinkQueue; /* 通道 */42 主要模块的算法描述本程序主要分为四部分： （ 1）主函数及程序框架、 （ 2）车辆到达模块、（3）车辆离开模块、（4）显示车辆信息模块，（ 1）主函数void main()SqStack In,Out; LinkQueue Wait;int ch;InitStack(&In); /* 初始化停车站 */InitStack(&Out); /* 初始化让路的临时栈 */InitQueue(&Wait); /* 初始化通道 */while(1)printf("- 欢迎

10、使用停车场管理系统 -n");printf("t 本系统由 5011工作室开发，作者 :邓春国、段庆龙、梁伟明、丁磊。 nn");printf(" 请输入停车场的容量 :");scanf("%d",&MAX);printf(" 请输入停车场的收费标准 (元/ 小时 ):");scanf("%f",&price);printf(" 您输入的停车场容量为 %d位，费用为 %2.1f元 / 小时。n",MAX,price);printf("n (

11、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:pri

12、ntf("n 按键无效，请重新按键选择！");/*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)退出系统

13、n 请选择 n");（ 2）车辆离开模块1 算法分析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",

14、&room);if(room>=1&&room<=In->top) break;/* 判断停车场内是否有车，如果有车，就输入要离开的车辆在停车场的位置，否则就提示停车场没车。这里用了while 循环语句，如果输入的车辆位置超出范围，就要重新输入。 */while(In->top>room) /* 车辆离开 */Out->top+;Out->stackOut->top=In->stackIn->top;In->stackIn->top=NULL;In->top-;/* 如果栈顶位置 In->

15、;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->t

16、op;Out->stackOut->top=NULL; Out->top-;精选文档./* 直到要离开的车辆前面的车都开到临时停车场之后，该车才离开， 离开之后，该车的信息结点 In->stackIn->top 置空，然后栈顶 In->top 减 1。之后就判断临时停车场是否有车，有车就一辆一辆的开回停车场里面， 因此停车场的栈顶In->top 加1，然后就把临时停车场的车结点的信息拷贝到停车场的车结点上，接着删除临时停车场车的结点(即 Out->stackOut->top=NULL;Out->top-;)。*/PRINT(p,roo

17、m);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->he

18、ad->next=q->next; if(q=W->rear) W->rear=W->head;In->stackIn->top=t;free(q);/* 判断 (W->head!=W->rear)&&In->top<MAX （即通道上是否有车及停车场是否已满），如果便道有车且停车场未满，通道的车便可进入停车场，此时指针q 指向便道的头，即队头，然后停车场的栈顶In->top 加 1 以便增加新的车辆，接着输入队头的车辆信息，即要进去停车场的车的信息，然后便道队列的头结点指向q（即刚进入停车场的车的结点）

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

20、车是便道的车先进入停车场结束图 4.1leave否输出停车场里没有车否否函数流程图精选文档.5 测试分析测试数据及结果如下：输入 2 辆车的信息，如图5.2 所示：再输入 2 辆车的信息，如图精选文档.最后选择车辆离开，输入第2 辆车离开，如图6 课程设计总结通过这次课程设计使我充分的理解了用栈和队列实现模拟停车场的基本原理，知道了栈的顺序存储结构和队列的链式存储结构的定义和算法描述，同时也学会了编写停车场问题的程序。 虽然此次的程序不是很完备，没有加入一些更完善的功能，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。在刚开始编程的时候， 我感到有点无从下

21、手， 但经过对题目的详细分析和思考之后，我就知道具体应该做什么，怎么做了。经过几天和同学的一起研究，我完成这个程序，我学到了很多东西，这是在课堂上无法做到的。源程序#include<stdio.h>#include <stdlib.h>#include<iostream.h>#include<string.h>精选文档.#include<math.h>#define size 1/ 停车场位置数/ 模拟停车场的堆栈的性质；typedef struct zanlindint number;/ 汽车车号int ar_time;/ 汽车到达

22、时间zanInode;typedef structzanInode*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 压入

23、 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 duilieint number;/ 汽车车号int ar_time;/ 汽车到达时间struct duilie *next;*queueptr;typedef structqueueptr fro

24、nt;/ 便道的队列的对头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， a

25、r_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<<" 停车场的通道为空! !&q

26、uot;<<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

27、.stacksize_curren<2)zanInode e;e.number=number;e.ar_time=time_a;push(st,e);cout<< "该车已进入停车场在: "<<st.stacksize_curren<<"号车道 "<<endl<<endl;elseenqueue(q,number,time_a);cout<<" 停车场已满，该车先停在便道的第"<<q.length<<"个位置上 "

28、<<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)/ 找到

29、要开出的车，并弹出停车场栈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_t

30、ime=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<<"="<