数据结构停车场管理实验报告C++.doc

数据结构课 程 设 计题目 停车场管理器设计 专业：计算机科学与技术班级：1401姓名：彭旭学号：143230135实验主要内容以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“达到”或“离去”信息、汽车牌照号码以及达到或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆达到、则输出汽车在停车场内或便道上停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。环境 Windows 10 Visual c+ c语言实验原理1.概要设计（1）抽象数据类型定义ADT Stack 数据对象:D=ai|ai ElemSet, i=1,2,n;n0 数据关系:R1=|ai-1,ai D,i=2,n 基本操作: InitStack(&S) 操作结果：构造一个空栈S。 Push(&S,e)初始条件：栈S已存在。操作结果：插入e为新的栈顶元素 Pop(&S,&e) 初始条件：栈S已存在。操作结果：删除S的栈顶元素,并且用e返回。 ADT Stack ADT Queue 数据对象:D=ai|ai ElemSet, i=1,2,n; n0 数据关系:R1=|ai-1,ai D, i=2,n其中:a1为队头, an为队尾 基本操作: InitQueue(&Q); 操作结果：构造一个空队列Q EnQueue(&Q,&e);初始条件：对列Q已存在。操作结果：插入元素e为Q的新队尾元素。 DeQueue(&Q,&e); 初始条件：对列Q已存在。操作结果：删除Q的队头元素, 并用e返回。ADT Queue （2）本程序包含七个模块：主程序模块，其中主函数为 Void main() 初始化； 构造空栈； 输入已知数据； 插入数据入栈； 分析 入栈；出栈；入队；出队；输出数据； 构造栈模块-构造一个空栈； 栈插入模块-插入新的数据元素； 栈删除模块-删除指定的数据元素；构造队列模块-构造一个空队列； 队列插入模块-插入新的数据元素； 队列删除模块-删除指定的数据元素；（3）各模块之间的调用关系图解：主函数模块构造栈模块栈插入模块栈删除模块构造队列模块队列插入模块队列删除模块分析2详细设计类型定义#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define MONEY 3typedef int Status;typedef struct ElemTypechar a3;int num;int time;ElemType;typedef struct SqStack ElemType *base;/在栈构造之前和销毁之后,base的值为NULL ElemType *top;/栈顶指针 int stacksize;/当前已经分配的存储空间,以元素为单位SqStack;/栈的表示typedef struct QNodeElemType data; struct QNode *next;QNode,*QueuePtr;/队列的表示typedef struct LinkQueue QueuePtr front;/队头指针QueuePtr rear;/队尾指针LinkQueue;栈和队列的基本操作Status InitStack(SqStack &S)/构造一个空栈Status Push(SqStack &S,ElemType e)/插入元素e为新的栈顶元素Status Pop(SqStack &S,ElemType &e)/若栈不空，则删除S的栈顶元素，用e 返回其值，并返回OK；否则返回ERRORStatus InitQueue(LinkQueue &Q)/构造一个空队列QStatus EnQueue(LinkQueue &Q,ElemType e)/插入元素e为Q的新队列Status DeQueue(LinkQueue &Q,ElemType &e)/若队列不空,则删除Q的对头元素,用e返回其值,并返回Ok;否则返回ERROR;部分操作的算法Status InitStack(SqStack &S)/构造一个空栈 S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType); if(!S.base) exit (OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;Status Push(SqStack &S,ElemType e)/插入元素e为新的栈顶元素if(S.top-S.base=S.stacksize)/栈满，追加存储空间S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base) exit(OVERFLOW);/存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACK_INIT_SIZE;*S.top+=e;return OK;Status Pop(SqStack &S,ElemType &e)/若栈不空，则删除S的栈顶元素，用e 返回其值，并返回OK；否则返回ERRORif(S.top=S.base) return OK;e=*-S.top;return OK;/-队列Status InitQueue(LinkQueue &Q)/构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit (OVERFLOW);/存储分配失败Q.front-next=NULL;return OK;Status EnQueue(LinkQueue &Q,ElemType e)/插入元素e为Q的新队列p=(QueuePtr)malloc(sizeof(QNode);/存储分配失败if(!p) exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;Status DeQueue(LinkQueue &Q,ElemType &e)/若队列不空,则删除Q的对头元素,用e返回其值,并返回Ok;否则返回ERROR;if(Q.front=Q.rear) return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK;源程序Stop1.h:#include #include #include #include /-函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define TNFEASIBLE -1#define OVERFLOW -2/Status 是函数的类型，其值是函数结果状态代码typedef int Status;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define MONEY 3Stop2.h:#includestop1.htypedef struct ElemTypechar a3;int num;int time;ElemType;typedef struct SqStackElemType *base;ElemType *top;int stacksize;SqStack;/栈的表示typedef struct QNodeElemType data;struct QNode *next;QNode,*QueuePtr;/队列的表示 typedef struct LinkQueue QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue; Status InitStack(SqStack &S);/构造空栈 Status Push(SqStack &S,ElemType e);/进栈 Status Pop(SqStack &S,ElemType &e);/出栈 Status InitQueue(LinkQueue &Q);/构造一个空队列 Status EnQueue(LinkQueue &Q,ElemType e);/入队 Status DeQueue(LinkQueue &Q,ElemType &e);/出队Stop.cpp: #includestop2.hStatus InitStack(SqStack &S)/构造空栈 S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;Status Push(SqStack &S,ElemType e)/插入元素e为新的栈顶元素 if(S.top-S.base=S.stacksize)/栈满，追加存储空间S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACK_INIT_SIZE; *S.top+=e;return OK;Status Pop(SqStack &S,ElemType &e)/出栈 if (S.top=S.base) return OK; e=*-S.top; return OK;/*队列*/Status InitQueue(LinkQueue &Q)/构造一个空队列 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(OVERFLOW);Q.front-next=NULL;return OK; Status EnQueue(LinkQueue &Q,ElemType e)/插入元素e为Q的新队列 struct QNode *p;p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK; Status DeQueue(LinkQueue &Q,ElemType &e)struct QNode *p;if(Q.front=Q.rear) return ERROR;p=Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK;Stop_main.cpp: #includestop2.h main()int i,t,f,m,n,s1_num,Q_num;struct SqStack s1,s2;struct LinkQueue Q;struct ElemType e,e1;s1_num=0;Q_num=0;t=0;m=0;InitStack(s1);InitStack(s2);InitQueue(Q);printf(停车场的容量是:);scanf(%d,&n);printf(输入车辆信息（E为退出，A为进入标志，D为离开标志，车牌号 时间空格隔开）：n);scanf(%s,e1.a);scanf(%d%d,&e1.num,&e1.time);while(strcmp(e1.a,E)!=0)if(strcmp(e1.a,A)=0) /当有车辆进来的时候 if(s1_numn) Push(s1,e1);s1_num+; printf(此车停在停车场第%d辆n,s1_num); else EnQueue(Q,e1);Q_num+; printf(此车停在便道距离门口第%d辆n,Q_num);else if(strcmp(e1.a,D)=0) /当有车辆离开的时候 f=s1_num;for(i=0;if;i+)Pop(s1,e);s1_num-;if(e1.num=e.num)t=e1.time-e.time;m=MONEY*t