数据结构停车场管理实验报告

停车场管理实验报告学院：计算机工程学院班级：计算1414 姓名：李连活一．实验目的和要求熟练栈和队列的结构特性，掌握在实际问题背景下的应用二．实验主要内容以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“达到”或“离去”信息、汽车牌照号码以及达到或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆达到、则输出汽车在停车场内或便道上停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。三．实验仪器和环境PC机Windows8.1Visualc++c语言四．实验原理1.概要设计（1）抽象数据类型定义ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,…n;n>0}数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,…n}基本操作:InitStack(&S)操作结果：构造一个空栈S。Push(&S,e)初始条件：栈S已存在。操作结果：插入e为新的栈顶元素Pop(&S,&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素,并且用e返回。}ADTStackADTQueue{数据对象:D={ai|ai∈ElemSet,i=1,2,…n;n>0}数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,…n}其中:a1为队头,an为队尾基本操作:InitQueue(&Q);操作结果：构造一个空队列QEnQueue(&Q,&e);初始条件：对列Q已存在。操作结果：插入元素e为Q的新队尾元素。DeQueue(&Q,&e);初始条件：对列Q已存在。操作结果：删除Q的队头元素,并用e返回。}ADTQueue（2）本程序包含七个模块：<1>主程序模块，其中主函数为Voidmain(){初始化；构造空栈；输入已知数据；插入数据入栈；分析{入栈；出栈；入队；出队；}输出数据；}<2>构造栈模块-----构造一个空栈；栈插入模块-----插入新的数据元素；栈删除模块-----删除指定的数据元素；构造队列模块-----构造一个空队列；队列插入模块-----插入新的数据元素；队列删除模块-----删除指定的数据元素；（3）各模块之间的调用关系如下：主函数模块主函数模块构造栈模块栈插入模块栈删除模块构造队列模块队列插入模块队列删除模块分析2．详细设计<1>类型定义#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineMONEY3typedefintStatus;typedefstructElemType{ chara[3]; intnum; inttime;}ElemType;typedefstructSqStack{ElemType*base;//在栈构造之前和销毁之后,base的值为NULLElemType*top;//栈顶指针intstacksize;//当前已经分配的存储空间,以元素为单位}SqStack;//栈的表示typedefstructQNode{ ElemTypedata; structQNode*next;}QNode,*QueuePtr;//队列的表示typedefstructLinkQueue{ QueuePtrfront;//队头指针 QueuePtrrear;//队尾指针}LinkQueue;<2>栈和队列的基本操作StatusInitStack(SqStack&S)//构造一个空栈StatusPush(SqStack&S,ElemTypee)//插入元素e为新的栈顶元素StatusPop(SqStack&S,ElemType&e)//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORStatusInitQueue(LinkQueue&Q)//构造一个空队列QStatusEnQueue(LinkQueue&Q,ElemTypee)//插入元素e为Q的新队列StatusDeQueue(LinkQueue&Q,ElemType&e)//若队列不空,则删除Q的对头元素,用e返回其值,并返回Ok;否则返回ERROR;<3>部分操作的算法StatusInitStack(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; returnOK;}StatusPush(SqStack&S,ElemTypee){//插入元素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; returnOK;}StatusPop(SqStack&S,ElemType&e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(S.top==S.base)returnOK; e=*--S.top; returnOK;}//----------------队列StatusInitQueue(LinkQueue&Q){//构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW);//存储分配失败 Q.front->next=NULL; returnOK;}StatusEnQueue(LinkQueue&Q,ElemTypee){//插入元素e为Q的新队列 p=(QueuePtr)malloc(sizeof(QNode));//存储分配失败 if(!p)exit(OVERFLOW); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; returnOK;}StatusDeQueue(LinkQueue&Q,ElemType&e){//若队列不空,则删除Q的对头元素,用e返回其值,并返回Ok;否则返回ERROR; if(Q.front==Q.rear)returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); returnOK;}五．源程序Stop1.h:#include<stdio.h>#include<process.h>#include<malloc.h>#include<string.h>//------------------------函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineTNFEASIBLE-1#defineOVERFLOW-2//Status是函数的类型，其值是函数结果状态代码typedefintStatus;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineMONEY3Stop2.h:#include"stop1.h"typedefstructElemType{ chara[3]; intnum; inttime;}ElemType;typedefstructSqStack{ ElemType*base; ElemType*top; intstacksize;}SqStack;//栈的表示typedefstructQNode{ ElemTypedata; structQNode*next;}QNode,*QueuePtr;//队列的表示typedefstructLinkQueue{ QueuePtrfront;//队头指针 QueuePtrrear;//队尾指针 }LinkQueue;StatusInitStack(SqStack&S);//构造空栈StatusPush(SqStack&S,ElemTypee);//进栈StatusPop(SqStack&S,ElemType&e);//出栈StatusInitQueue(LinkQueue&Q);//构造一个空队列StatusEnQueue(LinkQueue&Q,ElemTypee);//入队StatusDeQueue(LinkQueue&Q,ElemType&e);//出队Stop.cpp:#include"stop2.h"StatusInitStack(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;returnOK;}StatusPush(SqStack&S,ElemTypee){//插入元素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; returnOK;}StatusPop(SqStack&S,ElemType&e){//出栈if(S.top==S.base)returnOK;e=*--S.top;returnOK;}/***********************************************************************队列*/StatusInitQueue(LinkQueue&Q){//构造一个空队列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); Q.front->next=NULL; returnOK;}StatusEnQueue(LinkQueue&Q,ElemTypee){//插入元素e为Q的新队列structQNode*p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; returnOK;}StatusDeQueue(LinkQueue&Q,ElemType&e){ structQNode*p; if(Q.front=Q.rear)returnERROR; p=Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); returnOK;} Stop_main.cpp:#include"stop2.h"main(){ inti,t,f,m,n,s1_num,Q_num; structSqStacks1,s2; structLinkQueueQ; structElemTypee,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_num<n){Push(s1,e1);s1_num++; printf("此车停在停车场第%d辆\n",s1_num);} else{EnQueue(Q,e1);Q_num++; printf("此车停在便道距离门口第%d辆\n",Q_num);} } elseif(strcmp(e1.a,"D")==0){//当有车辆离开的时候f=s1_num; for(i=0;i<f;i++){ Pop(s1,e);s1_num--; if(e1.num==e.num){ t=e1.time-e.time;m=