数据结构实验-停车场

HUNANUNIVERSITY实验报告题目：停车场管理 学生姓名李湃学生学号 专业班级 指导老师 需求分析1、设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。2、输入要求：每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。3、输出要求：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。4、测试数据：设n=2，输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。其中：‘A’表示车辆到达；‘D’表示车辆离去；‘E’表示输入结束。概要设计抽象数据类型该问题中数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。第一个数据项由题目要求，用英文大写字符表示，故用英文字符来存储；第二第三项为正整数，可用整数来存储。停车场只用一个大门可供汽车进出，为先进先出型，所以可以用栈来模拟，记为1栈。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。这个过程车的进出规则为先走后回，可用栈来保存让路车辆信息，记为2栈。车场外便道上的车辆满足先进后出，可以用队列来模拟。堆栈的基本操作包括初始化，进栈出栈等。队列的基本操作包括初始化、入队出队等。ADTStack{数据对象：D={a[i]|a[i]∈｛（字符，整数，整数）｝,i=1,2,……,n,n>=0}数据关系：R1={<a[i-1],a[i]>|a[i-1],a[i]∈D,i=2,……,n}约定a[n]端为栈顶，a[1]端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈StackLength(S)初始条件：栈S已经存在操作结果：返回S中元素个数Push(&S,e)初始条件：栈S已经存在操作结果：将元素e插入成为新的栈顶元素Pop(&S,&e)初始条件：栈S已经存在且非空操作结果：删除S的栈顶元素，用e返回其值}ADTStackADTQueue{数据对象：D={a[i]|a[i]∈｛（字符，整数，整数）｝,i=1,2,……,n,n>=0}数据关系：R1={<a[i-1],a[i]>|a[i-1],a[i]∈D,i=2,……,n}约定a[n]端为队列尾，a[1]端为队列头。基本操作：InitQueue(&Q)操作结果：构造一个空队列QueueLength(Q)初始条件：队列Q已经存在操作结果：返回Q中元素个数EnQueue（&Q，e）初始条件：队列Q已经存在操作结果：将元素e插入成为新的队尾元素DeQueue(&Q,&e)初始条件：队列Q已经存在且非空操作结果：删除Q的队首元素，用e返回其值}ADTStack算法基本思想接收输入信息。若为入场(A)，先判断1栈中元素个数是否已经达到规定最大值n（停车场容量），如果没有，将该信息入1栈，否则将该信息入队。输出该入场车辆位置。若为出场(D)，将1栈顶元素出栈，判断该信息所属车辆是否为出场车辆。若否，将该信息入2栈，并重新将1栈顶元素出栈，重新判断。若是，输出时间差（用时间差表示应缴纳费用）。然后循环将2栈中栈顶元素出栈并进入1栈直到2栈为空。再将队首元素出队入1栈。继续接收信息并继续判断，做出相应操作，直到接收到的信息为（‘E’，0，0）时退出程序。程序的流程程序由三个模块组成：输入模块：完成车辆信息的储存。操作模块：通过判断决定相应操作。输出模块：将车辆位置信息或入场出场时间差输出到屏幕。三、详细设计物理数据类型由于栈和队列中储存元素的类型一致，所以用相同的存储结构比较方便。这里用顺序存储结构，因为1栈为满的概率很大。每个信息元素包含三个数据项，分别为字符类型和两个整数类型，可分别用C语言中char型和int型保存。元素结构体定义：Typedefstruct{charstate;intNo;inttime;}Elemtype;栈的顺序存储设计：#defineSTACK_INIT_SIZE10#defineSTACKINCERMENT5typedefstruct{Elemtype*base;Elemtype*top;intstacksize;}SqStack;//栈的基本操作StatusInitStack(SqStack&S){//构造一个空栈SS.base=(Elemtype*)malloc(STACK_INIT_SIZE*sizeof(Elemtype));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusPop(SqStack&S,Elemtype&e){//若栈不空，则删除S的栈顶元素，用e返回其值，//并返回OK;否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//PopStatusPush(SqStack&S,Elemtypee){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){//栈满，追加存储空间S.base=(Elemtype*)realloc(S.base,(S.stacksize+STACKINCERMENT)*sizeof(Elemtype));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCERMENT;}*S.top++=e;returnOK;}//PushintStackLength(SqStack&S){//返回栈的长度returnstacksize;}队列的顺序存储设计：#defineMAXQSIZE10typedefstruct{Elemtype*base;intfront;intrear;}SqQueue;//基本操作StatusInitQueue(SqQueue&Q){//构造一个空队列QQ.base=(Elemtype*)malloc(MAXqSIZE*sizeof(Elemtype));if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;}intQueueLength(SqQueueQ){//返回Q的元素个数，即队列的长度return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}StatusEnQueue(SqQueue&Q,Elemtypee){//插入元素e为Q的新的队尾元素if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//队列满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}StatusDeQueue(SqQueue&Q,Elemtype&e){//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；//否则返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}输入输出格式：输入：请输入停车场大小：//提示请输入汽车入场出场信息：//提示伪代码：printf("请输入停车场大小:\n");scanf("%d",&n);getchar();if(n<1)returnERROR;printf("请输入汽车入场出场信息：\n");输出：//位置*车停在停车场第*个位置//或*车停在便道第*个位置//收费*车在停车场停留时间为：**伪代码：printf("%d车停在停车场第%d个位置\n",e.No,StackLength(S1));}printf("%d车停在便道第%d个位置\n",e.No,QueueLength(Q));}printf("%d车在停车场停留时间为：%d\n",e.No,e.time-c.time);停车场问题具体实现步骤：while((e.state=getchar())!='E'){scanf("%d%d",&e.No,&e.time);getchar();switch(e.state){case'A':if(StackLength(S1)<n){Push(S1,e);printf("%d车停在停车场第%d个位置\n",e.No,StackLength(S1));}else{EnQueue(Q,e);printf("%d车停在便道第%d个位置\n",e.No,QueueLength(Q));}break;case'D':while(1){Pop(S1,c);if(e.No==c.No)break;if(StackLength(S1)==0)return(ERROR);Push(S2,c);}if(e.time<c.time)return(ERROR);printf("%d车在停车场停留时间为：%d\n",e.No,e.time-c.time);while(StackLength(S2)!=0){Pop(S2,c);Push(S1,c);}if(QueueLength(Q)!=0){