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

数据结构课程设计停车场管理系统 专 业：信息管理与信息系统 班 级：10信本指导教师： 完成日期：2012年1月1日目 录 1、 课程设计目标.1 1 问题描述.1 2 问题分析.1二、概要设计.11 抽象数据类型定义.12 模块划分.4三、详细设计.6 1 数据类型的定义.62 主要模块的算法描述.84、 测试分析.14 1 主界面.142 具体操作.15五、课程设计总结.17六、源程序清单.18 *参考文献.30 *设计人员名单.3132一、课程设计目标1 问题描述设停车场是一个可停放n辆汽车的狭长通道，且只有一个门可供出入。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆汽车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原顺序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。2 问题分析（1）根据车辆到达停车场到车辆离开停车场时所停留的时间进行计时收费。（2）当有车辆从停车场离开时，等待的车辆按顺序进入停车场停放。实现停车场的调度功能。（3）用顺序栈来表示停车场，链队表示停车场外的便道。（4）显示停车场信息和便道信息。（5）程序执行的命令为：车辆进入停车场 车辆离开停车场 显示停车场的信息。二、概要设计1 抽象数据类型定义（1）栈的抽象数据类型定义AST Stack数据对象：D=ai|aiElemSet,i=1,2,.,n, n0数据关系：R1=<ai-1,ai>|ai-1,aiD，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|aiElemSet,i=1,2,.,n,n0数据关系：R1=<ai-1,ai>|ai-1,aiD,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 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）队列模块实现队列的抽象数据类型开始输入车辆的号码及到达时间停车场是否已满进入停车场进入便道等候离开停车场停车场是否已满输出离开时间计算价格停车场里没有车辆判断变道是否为空车辆进入停车场便道里没有车辆结束三、详细设计1 数据类型的定义 MAX 全局变量 定义一个全局变量用来存储车库最大容量Price 全局变量 定义一个全局变量用来存储每车每小时的费用 typedef struct time 定义两个整型的变量，用来存放时间的小时和分钟。Time; /*时间结点*/ typedef struct node 定义一个字符型数组存放车牌号，在定义两个Time型的时间用来存放进入停车场时间和出停车场的时间。Car; /*车辆信息结点*/ typedef struct NODE 定义一个数组成为栈的主体，里面存放指向车辆信息Car的指针，在定义一个整型变量存放栈顶。SqStack; /*停车站*/ typedef struct car 便道中车辆信息的定义，其中包括Car型和next指针。QNode; typedef struct Node 便道，只有head指针和rear指针，指向QNode型变量，一个代表头，一个代表尾。LinkQueue; /*通道*/ 2 主要模块的算法描述本程序主要分为四部分：（1）主函数及程序框架（2）车辆到达模块（3）车辆离开模块（4）显示车辆部分。（1） 主函数 算法分析void main() 初始化停车站 In 初始化让路的临时栈 Out 初始化通道 Wait 进入无限循环 输出程序界面 1、车辆到达 2、车辆离开 3、停车场信息 4、退出系统 确定停车场的容量MAX与停车场收费标准price 进入第二个无限循环 让用户选择一个功能 一个功能使用完毕后清屏再次输入主界面函数流程图如图所示：（2） 车辆到达模块算法分析int arrive(SqStack *In,LinkQueue *W)车辆进入停车场判断停车场是否已满若满则进入通道等候不满则进入停车场读入车辆信息，车牌号和进入时间开始判断停车场是否已满是否进入停车场进入便道读入车辆信息：车牌号读入车辆信息：车牌号、进入时间结束 函数流程图如图所示（3） 车辆离开模块算法分析void leave(SqStack *In,SqStack *Out,LinkQueue *W) /*车辆离开*/开始定义一个整型变量room，用来记录要离开的车辆在停车场的位置，定义车辆结点指针p和t和队列结点指针q。 if(In->top>0) /*有车*/ 判断停车场内是否有车，如果有车，就输入要离开的车辆在停车场的位置，否则就提示停车场没车。这里用了while循环语句，如果输入的车辆位置超出范围，就要重新输入。While(In->top>room) /*车辆离开*/如果栈顶位置In->top大于要离开的车位置room（即要离开的车不在停车场的门口）的话，在要离开的车辆前面的车就要先离开，开到临时停车场，即临时栈中，因此Out所表示的临时栈的栈顶top加1，用来表示临时停车场增加1辆车；接着把该车的信息拷贝到栈Out中，然后删除栈In的栈顶（即这辆车开走）。直到要离开的车辆前面的车都开到临时停车场之后，该车才离开，离开之后，该车的信息结点In->stackIn->top置空，然后栈顶In->top减1。之后就判断临时停车场是否有车，有车就一辆一辆的开回停车场里面，因此停车场的栈顶In->top 加1，然后就把临时停车场的车结点的信息拷贝到停车场的车结点上，接着删除临时停车场车的结点 (Out->stackOut->top=NULL;Out->top-;)。判断(W->head!=W->rear)&&In->top<MAX（即通道上是否有车及停车场是否已满），如果便道有车且停车场未满，通道的车便可进入停车场，此时指针q指向便道的头，即队头，然后停车场的栈顶In->top 加1以便增加新的车辆，接着输入队头的车辆信息，即要进去停车场的车的信息，然后便道队列的头结点指向q（即刚进入停车场的车的结点）的后继结点，即原队列中第二辆车的结点，接着判断刚离开的车是否是最后一辆车，如果是，就把队列置空，即队头等于队尾；之后就把结点t（即要进入停车场的车）的信息拷贝到停车场栈顶的车中，最后释放p的空间，即原队头结点。 leave函数流程图如图所示：判断前面是否有其他车且停车场未满开始结束判断停车场是否有车否是是是车临时停车场的车回到停车场便道的车先进入停车场否判断便道否有车否输入离开车辆的信息车辆离开前面的车先进入临时停车场输出停车场里没有车定义必要的变量（4）显示车辆信息算法分析void info(SqStack S,LinkQueue W) 输出停车场信息； 其中，包含了两个函数Info1（）输出停车场有关信息Info2（）输出通道有关信息void PRINT()输出 出停车站时的信息计算金钱Info21函数流程图如图所示Info1开始开始是否输出结束通道无车计算便道内车的数量判断停车场否有车结束输出读取车辆信息计算停车场内车的数量PRINT开始输入车离开的时间结束输出计算车离开应支付的费用四、测试分析1 主界面2 具体操作2.1进站时间与车牌号2.2 车站已满，请进入临时车道2.3 出站与收费2.4 车辆离开，变道的车进入停车场2.5 结束五、课程设计总结通过这次课程设计使我充分的理解了用栈和队列实现模拟停车场的基本原理，知道了栈的顺序存储结构和队列的链式存储结构的定义和算法描述，同时也学会了编写停车场问题的程序。虽然此次的程序不是很完备，没有加入一些更完善的功能，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。在刚开始编程的时候，我感到有点无从下手，但经过对题目的详细分析和思考之后，我就知道具体应该做什么，怎么做了。经过几天和同组同学的一起研究，我们分工完成了这个程序，完成这个程序，我学到了很多东西，这是在课堂上无法做到的。在此我非常要感谢的是我的指导老师安强强老师，感谢老师的细心认真的辅导，让我对数据结构这门课程掌握得更好，懂得更多，他教我怎么分析问题，应该要注意些什么，最后还指出我存在的问题。6、 源程序清单#include "stdio.h" #include "stdlib.h" #include "string.h" #include "conio.h"int MAX; /*定义一个全局变量用来存储车库最大容量*/ float price;/*每车每小时的费用*/ typedef struct 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 InitStack(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;i<=MAX;i+) s->stacks->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); /*初始化通道*/ while(1) printf("-欢迎使用停车场管理系统-n");printf("t本系统由524开发，作者:张翔磊、王玺、张建强、蔺永杰、范亮。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,&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本系统由524开发，作者:张翔磊、王玺、张建强、蔺永杰、范亮。nnn");printf("您输入的停车场容量为%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请输入车牌号码(例:陕A1234):"); gets(p->num); if(In->top<MAX) /*停车场未满，车进车场*/ In->top+;printf("n停车的位置:%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();return(1); void leave(SqStack *In,SqStack *Out,LinkQueue *W) /*车辆离开*/ int room; Car *p,*t; QNode *q; /*判断车场内是否有车*/ if(In->top>0) /*有车*/ while(1) /*输入离开车辆的信息*/ printf("n请输入车在停车场的位置(1-%d)：",In->top); scanf("%d",&room); if(room>=1&&room<=In->top) break; while(In->top>room) /*车辆离开*/ Out->top+; Out->stackOut->top=In->stackIn->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->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->stackIn->top=t; free(q); else printf("n停车场里没有车n"); /*没车*/printf("请按任意键返回");getch();void info1(SqStack *S) /*列表输出车场信息*/ int i; if(S->top>0) /*判断停车场内是否有车*/ printf("n车场:"); printf("n 位置 到达时间 车牌号n"); for(i=1;i<=S->top;i+) printf(" %dt",i); printf("%d:%d ",S->stacki->reach.hour,S->stacki->reach.min); puts(S->stacki->num); else printf("n停车场里没有车"); void info2(LinkQueue *W) /*显示便道信息*/ QNode *p; p=W->head->next; if(W->head!=W->rear) /*判断通道上是否有车*/ printf("n便道中车辆的号码为:n"); while(p!=NULL) puts(p->data->num); p=p->next; else printf("n便道里没有车n");printf("请按任意键返回");getch(); void info(SqStack S,LinkQueue W) info1(&S); /*显示停车场信息*/ info2(&W); /*显示停便道信息*/ void PRINT(Car *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("车离开的时间是: %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)+(B2-A2)/60.0)*price); free(p); 参考文献1 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20022 耿国华 数据结构（C语言版）M北京：高等教育出版社，2005设计者名单课程名称停车场管理系统院系信息工程学院专业班级信息管理与信息系统姓名学号任务范亮1014212136课题设计分析张建强1014212153函数设计分析王玺1014212164程序模块设计张翔磊1014212110编写程序代码蔺永杰1014212154程序的调试与测试成绩评定：指导教师评语：界面设计功能实现操作演示答辩效果设计报导创新总分 指导教师：成绩评定： 注：界面设计10%，功能实现35%，操作演示20%，答辩效果20%，设计报告10%，创新5%。