停车场调度.docxVIP

西安交通大学实验报告课程数据结构与算法 实验名称停车场调度系别 实验日期 年 月 日班号 交报告日期 年 月 日姓名 学号 报告退发 年 月 日 教师审批签字 （订正、重做）题目概述：有一狭长停车场可停放N辆车，只有一个门可供出入，车辆按照到达和早晚从最里面依次向外排。若停车场中的车辆出来，则在它之后进入的车辆都要给它让路，然后在依次进入停车场。以此为背景，模拟停车场调度。一：需求分析数据输入输出形式：本实验中，用数1到N表示每辆车的车牌号，停车场容量、要调度的车辆、停车场的状况通过dos界面输入。程序功能：本程序能够模拟停车场的调度情况。调试数据：停车场容量为20，开出第8车，第1车，第12车，第8车，第22车后的情形。二：概要设计 为实现上述过程，需要栈及队列两种抽象数据类型。 1、抽象数据类型栈的定义ADT { 数据对象：D={a| aLelemtype ,i=1,2,3~n} 数据关系：R={ a,a| a、aD} 约定栈顶与栈底 基本操作： Initsqstack(S, n) 初始条件：栈S已经存在 操作结果：构造一个容量为N的栈 push(S, e) 初始条件：栈S已经存在 操作结果：将元素e压入栈 pop(S, e)初始条件：栈S已经存在 操作结果：出栈并用e返回其值Findsqstack(S, e, *p)初始条件：栈S已经存在 操作结果：查找e是否在栈中，并用p返回e的指针 Printsqstack(S)初始条件：栈S已经存在 操作结果：打印栈中的元素2、抽象数据类型队列的定义ADT Queue{数据对象：D={a| aQelemtype ,i=1,2,3~n} 数据关系：R={ a,a| a、a D} 基本操作：Initlqueque(Q)操作结果：建立链式队列Q的头结点Dellqueque(Q, e)初始条件：队列Q已经存在操作结果：出队并用e返回其值Enlqueque(Q, e)初始条件：队列Q已经存在操作结果：将元素e入队Printlqueque(Q)初始条件：队列Q已经存在 操作结果：打印队列中的元素2、抽象数据类型队列的定义3、程序模块main（）模块实现数据人机对话界面与结果的输入输出栈模块实现栈的基本操作 队列模块实现队列的基本操作调度模块实现栈与队列的数据交换三、详细设计 1、栈的实现 typedef struct Sqstack{Selemtype *top;Selemtype *base;}Sqstack;/*栈节点定义*/void Initsqstack(Sqstack S,int n){S.base=(Selemtype*)malloc(n*sizeof(Selemtype));if(!S.base)exit(-1);S.top=S.base;}/*栈的初始化*/void push(Sqstack S,Selemtype e){*S.top=e;S.top++;}/*入栈*/void pop(Sqstack S,Selemtype e){if(S.top==S.base)exit(-1);--S.top;e=*S.top;}/*出栈*/void Findsqstack(Sqstack S,Selemtype e,Selemtype *p){*S.top=e;p=S.base;while((*p)!=e)p++;if(p==S.top)p=NULL;}/*判断所给元素m是否在栈中，若不在返回空指针p，若在返回m在栈中的位置指针*/void Printsqstack(Sqstack S){ p=S.base;while(p!=S.top){printf(*p);p++;}} 2、队列的实现 ypedef struct Qnode{Qelemtype date;struct Qnode *next;}Qnode;typedef struct{Qnode *front;Qnode *rear;}Lqueque;/*队列节点定义*/void Initlqueque(Lqueque Q){Q.front=(Qnode*)malloc(sizeof(Qnode));if(!Q.front)exit(-1);Q.rear=Q.front;Q.front-next=NULL;}/*初始化队列*/void Dellqueque(Lqueque Q,Qelemtype e){ if(Q.front==Q.rear)exit(-1);p=Q.front-next;e=p-date;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;free(p);}/*出队*/void Enlqueque(Lqueque