![数据结构报告-停车场问题_第1页](http://file4.renrendoc.com/view/d88abcb40ba47ceeaf338c24a57b9bcd/d88abcb40ba47ceeaf338c24a57b9bcd1.gif)
![数据结构报告-停车场问题_第2页](http://file4.renrendoc.com/view/d88abcb40ba47ceeaf338c24a57b9bcd/d88abcb40ba47ceeaf338c24a57b9bcd2.gif)
![数据结构报告-停车场问题_第3页](http://file4.renrendoc.com/view/d88abcb40ba47ceeaf338c24a57b9bcd/d88abcb40ba47ceeaf338c24a57b9bcd3.gif)
![数据结构报告-停车场问题_第4页](http://file4.renrendoc.com/view/d88abcb40ba47ceeaf338c24a57b9bcd/d88abcb40ba47ceeaf338c24a57b9bcd4.gif)
![数据结构报告-停车场问题_第5页](http://file4.renrendoc.com/view/d88abcb40ba47ceeaf338c24a57b9bcd/d88abcb40ba47ceeaf338c24a57b9bcd5.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据结构报告-停车场问题⒈问题描述:停车场管理问题[问题描述]设有一个可以停放n辆汽车的狭长停车场,它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车,则后来的车辆只能在停车场大门外的便道上等待,一旦停车场内有车开走,则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走,在它之后进入停车场的车都必须先退出停车场为它让路,待其开出停车场后,这些车辆再依原来的次序进场。每辆车在离开停车场时,都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去,允许其离去,不收停车费,并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。[实现要求]要求程序输出每辆车到达后的停车位置(停车场或便道上),以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。[实现提示]汽车的模拟输入信息格式可以是:(到达/离去,汽车牌照号码,到达/离去的时刻)。例如,(‘A’,,1,5)表示1号牌照车在5这个时刻到达,而(‘D’,,5,20)表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为(‘E’,0,0)时结束。本题可用栈和队列来实现。⒉设计:⑴数据结构设计和核心算法设计描述;停车场管理系统是充分利用数据结构中栈和队列的思想实现的,栈是一种只能在叫做栈的一段进行进栈或者出栈操作的线性数据结构。栈的主要特点是”后进先出”,即后进栈的元素先处理。停车场的容量即为栈的存储空间,停车场的车辆的停靠是无秩序的,因此采用链式存储的方式更适合,也方便车辆的调度。队列是限定仅能在表的一端进行插入,在表的另一端进行删除的线性表。队列中可以插入的一端称为队尾,可以删除的一端称为队首。把一个元素插入队列中的操作为进队,队列中删除一个元素的操作为出队。队列存取操作符合:先进先出。停车场的车辆到达停车和车辆的离开的管理方式就是采用队列的“先进先出”的移动的思想。停车场的入口就是队列的队首,停车场的出口就是队列的队尾。⑵主控及功能模块层次结构;数据结构报告-停车场问题全文共12页,当前为第1页。2.1设定栈的抽象数据类型定义为:
ADTstack{
数据对象:D={ai|ai∈charset,i=1,2,……,n,n≥0}
数据关系:R1={|ai-1,ai∈D,i=2……,n}
基本操作:
initstack(&S,n)
操作结果:构造一个空栈S,该栈可存放n个元素。
push(&S,e)
初始条件:栈S已存在。
操作结果:在栈S的栈顶插入新的栈顶元素e。
pop(&S,&e)
初始条件:栈S已存在。
操作结果:删除S的栈顶元素,并以e返回其值。
DestroyStack(&S)
初始条件:栈S已存在。
操作结果:销毁栈S。
ClearStack(&S)
初始条件:栈S已存在。
操作结果:将S清为空栈。
StackLength(&S)
初始条件:栈S已存在。
操作结果:返回栈S的长度。
StackEmpty(&S)
初始条件:栈S已存在。
操作结果:若S为空栈,则返回TRUE,否则返回FALSE。
GetTop(S,&e)
初始条件:栈S已存在。
操作结果:若栈S不空,则以e返回栈顶元素。
StackTraverse(S,visit())
初始条件:栈S已存在。
操作结果:从栈底到栈顶依次对S中的每个元素调用函数visit()。
}ADTstack
2.2设定队列的抽象数据类型定义为:
ADTQueue{
数据对象:D={ai|ai∈ElemSet,i=1,2,……,n,n≥0}
数据关系:R1={|ai-1,ai∈D,i=2……,n}
基本操作:
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返回Q的队头元素。
EnQueue(&Q,e)
数据结构报告-停车场问题全文共12页,当前为第2页。初始条件:队列Q已存在。
操作结果:插入元素e为Q的新的队尾元素。
DeQueue(&Q,&e)
初始条件:Q为非空队列。
操作结果:删除Q的队头元素,并用e返回其值。
QueueTraverse(Q,visit())
初始条件:Q已存在且非空。
操作结果:从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败,则操作失败。
数据结构报告-停车场问题全文共12页,当前为第1页。数据结构报告-停车场问题全文共12页,当前为第2页。2.3详细设计车辆信息类型
typedefstructnode{
intpassport;//存储车辆牌照信息
inttime;//存储进场时间信息
}node;
2.栈类型(停车场)
typedefstructstack{//定义停车场栈类型 node*base; node*top; intstacksize;}stack;voidinitstack(stack&S,intn){//构造空栈 S.base=(node*)malloc(n*sizeof(node)); S.top=S.base; S.stacksize=n;}
voidpush(stack&S,nodee){//入栈函数 if((S.top-S.base)>=S.stacksize){EnQueue(Q,e);}//如果栈满则调用入队函数 else{ S.top->passport=e.passport; S.top->time=e.time; S.top++; }}voidwait(stack&S){ if((S.top-S.base)==(S.stacksize-1)&&count!=0){ nodetemp; DeQueue(Q,temp); temp.time=times; push(S,temp); }}数据结构报告-停车场问题全文共12页,当前为第3页。数据结构报告-停车场问题全文共12页,当前为第3页。 if(S.top==S.base)returnERROR;//如果栈空则返回ERROR --S.top; e.passport=S.top->passport; e.time=S.top->time; returnOK;}3.队列类型(便道)
typedefstructQnode{//定义便道队列类型 nodeQdata; structQnode*next;}Qnode;typedefstruct{ Qnode*front; Qnode*rear;}LinkQueue;voidEnQueue(LinkQueue&Q,nodee){//入队函数 Qnode*q; q=(Qnode*)malloc(sizeof(Qnode)); q->Qdata.passport=e.passport; q->Qdata.time=e.time; q->next=NULL; if(count==0){Q.front=q;count++;}//若创建节点前队空,头指针指向节点 Q.rear->next=q; Q.rear=q;}voidDeQueue(LinkQueue&Q,node&e){//出队函数 if(Q.rear==NULL){} else{ e.passport=Q.front->Qdata.passport; e.time=Q.front->Qdata.time; Q.front=Q.front->next; if(Q.front==NULL){Q.rear=Q.front;count=0;} }}4.全局变量及编译预处理语句
#defineERROR0
#defineOK1
#defineNULL0
intcount=0;//队列是否为空的标志inttimes;stacks,temp;//初始化栈数据结构报告-停车场问题全文共12页,当前为第4页。数据结构报告-停车场问题全文共12页,当前为第4页。5.主函数及其他函数的算法
voidmain(){ intn,exit; floatmoney; charinfo; intpass; Q.front=NULL; Q.rear=(Qnode*)malloc(sizeof(Qnode)); Q.rear->next=Q.rear; printf("停车场容量:"); scanf("%d",&n); initstack(s,n); initstack(temp,n); printf("停车场费率(元/小时):"); scanf("%f",&money); while(exit!=OK){ printf("\n请选择车辆状态\n1到达2离去3结束:");getchar(); scanf("%c",&info); printf("请输入车辆牌照:"); scanf("%d",&pass); if(info=='1'||info=='3')printf("请输入进场时间:"); if(info=='2')printf("请输入离场时间:"); scanf("%d",×); if(info=='3'){exit=OK;} elseif(info=='1'){ inti,j; nodea; a.passport=pass; a.time=times; push(s,a); for(i=1;i<=n;i++){ if(s.base[i-1].passport==a.passport){ printf("停车位置(停车场内):%d\n",i); } } Qnode*tp; tp=Q.front; if(tp==NULL){} else{ j=1; while(tp!=Q.rear){ tp=tp->next;数据结构报告-停车场问题全文共12页,当前为第5页。 数据结构报告-停车场问题全文共12页,当前为第5页。 } printf("停车位置(便道):%d\n",j); } } elseif(info=='2'){ noded; inttp,counter=0; do{ counter++; tp=pop(s,d); while(tp!=ERROR){ if(d.passport==pass){ floatm; m=-(times-d.time)*money; printf("停留时间:%d需交费:%f\n",-(times-d.time)*(-1),m*(-1)); while(temp.base!=temp.top){ pop(temp,d); push(s,d); } wait(s); d.passport=9999; tp=ERROR; } else{ push(temp,d); d.passport=0; tp=ERROR; } } }while(d.passport==0||counter>n); } elseif(info!='1'&&info!='2'&&info!='3'){} }}数据结构报告数据结构报告-停车场问题全文共12页,当前为第6页。⑶主要功能模块的输入、处理(算法框架描述)和输出;⑷功能模块之间的调用与被调用关系等。(1)输入车辆数据:1为到达,2为离去,3为结束程序。(2)接着输入车辆的牌照信息
(3)若为到达的车辆,输入进场信息,若为离去的车辆,输入离场信息。(4)若车辆到达,可得到车辆的停放位置信息,若车辆离去,可得到车辆的停放时间(在便道上的停放时间除外),以及应该交纳的费用。(5)本程序不断循环要求输入车辆信息,直到输入的车辆数据为E时,程序结束。⒊测试:测试范例,测试结果,测试结果的分析与讨论,测试过程中遇到的主要问题及所采用的解决措施。测试数据:设n=2
输入数据:2输出:
停车场容量:2
停车场费率:6
A,1,5停车位置(停车场内):1
A,2,10停车位置(停车场内):2
D,1,15停留时间:10需交费:60.00
A,3,20停车位置(停车场内):2
A,4,25停车位置(便道):1
A,5,30停车位置(便道):2
D,2,35停留时间:25需交费:150.00
D,4,40停留时间:5需交费:30.00
E,0,0数据结构报告数据结构报告-停车场问题全文共12页,当前为第7页。运行结果(1)进入停车场离开停车场等待停车数据结构报告-停车场问题全文共12页,当前为第8页。数据结构报告-停车场问题全文共12页,当前为第8页。程序源代码#include<stdio.h>#include<stdlib.h>#defineERROR0#defineOK1#defineNULL0typedefstructnode{//定义车辆信息数据结构 intpassport;//存储车辆牌照信息 inttime;//存储进场时间信息}node;typedefstructstack{//定义停车场栈类型 node*base; node*top; intstacksize;}stack;typedefstructQnode{//定义便道队列类型 nodeQdata; structQnode*next;}Qnode;typedefstruct{ Qnode*front; Qnode*rear;}LinkQueue;intcount=0;//队列是否为空的标志inttimes;stacks,temp;//初始化栈LinkQueueQ;//初始化队列voidinitstack(stack&S,intn){//构造空栈 S.base=(node*)malloc(n*sizeof(node)); S.top=S.base; S.stacksize=n;}voidEnQueue(LinkQueue&Q,nodee);//入队函数voidDeQueue(LinkQueue&Q,node&e);//出队函数voidpush(stack&S,nodee){//入栈函数 if((S.top-S.base)>=S.stacksize){EnQueue(Q,e);}//如果栈满则调用入队函数 else{ S.top->passport=e.passport;数据结构报告-停车场问题全文共12页,当前为第9页。 数据结构报告-停车场问题全文共12页,当前为第9页。 S.top++; }}intpop(stack&S,node&e){//出栈函数 if(S.top==S.base)returnERROR;//如果栈空则返回ERROR --S.top; e.passport=S.top->passport; e.time=S.top->time; returnOK;}voidwait(stack&S){ if((S.top-S.base)==(S.stacksize-1)&&count!=0){ nodetemp; DeQueue(Q,temp); temp.time=times; push(S,temp); }}voidEnQueue(LinkQueue&Q,nodee){//入队函数 Qnode*q; q=(Qnode*)malloc(sizeof(Qnode)); q->Qdata.passport=e.passport; q->Qdata.time=e.time; q->next=NULL; if(count==0){Q.front=q;count++;}//若创建节点前队空,头指针指向节点 Q.rear->next=q; Q.rear=q;}voidDeQueue(LinkQueue&Q,node&e){//出队函数 if(Q.rear==NULL){} else{ e.passport=Q.front->Qdata.passport; e.time=Q.front->Qdata.time; Q.front=Q.front->next; if(Q.front==NULL){Q.rear=Q.front;count=0;} }}voidmain(){ intn,exit; floatmoney; charinfo; intpass; Q.front=NULL;数据结构报告-停车场问题全文共12页,当前为第10页。 数据结构报告-停车场问题全文共12页,当前为第10页。 Q.rear->next=Q.rear; printf("停车场容量:"); scanf("%d",&n); initstack(s,n); initstack(temp,n); printf("停车场费率(元/小时):"); scanf("%f",&money); while(exit!=OK){ printf("\n请选择车辆状态\n1到达2离去3结束:"); scanf("%c",&info); printf("请输入车辆牌照:"); scanf("%d",&pass); if(info=='1'||info=='3')printf("请输入进场时间:"); if(info=='2')printf("请输入离场时间:"); scanf("%d",×); if(info=='3'){exit=OK;} elseif(info=='1'){ inti,j; nodea; a.passport=pass; a.time=times; push(s,a); for(i=1;i<=n;i++){ if(s.base[i-1].passport==a.passport){ printf("停车位置(停车场内):%d\n",i); } } Qnode*tp; tp=Q.front; if(tp==NULL){} else{ j=1; while(tp!=Q.rear){ tp=tp->next; j++; } printf("停车位置(便道):%d\n",j); } } elseif(
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 六年级体育上册 第二十九课 跳短绳教案
- 2023六年级数学上册 1 分数乘法第7课时 整数乘法运算律推广到分数教案 新人教版
- 专题5.9 相交线与平行线章末拔尖卷(人教版)(解析版)
- 农业大数据分析应用
- 中山市申明亭学校教师招聘笔试真题2023
- 2023年北京门头沟事业编招聘考试真题
- 2023年百色市德保县中医医院招聘护理人员考试真题
- 邯郸馆陶县招聘教师笔试真题2023
- 结构力学优化算法:遗传算法(GA):结构优化中的约束处理方法
- 结构力学优化算法:禁忌搜索(TS):禁忌搜索算法的初始解生成
- 六年级上册美术说课稿- 第4课《线与造型》人教新课标
- 苏少版六年级上册综合实践活动成长手册第11课《假日生活晒晒晒-我的义工经历》教案
- 任务一-认识普通车床课件
- 120中心应急预案制度
- 计算机网络技术行业与人才需求分析
- 2023年甘肃省2023年度重点人才项目申报书(2023年模版)
- 反诈骗打击“双卡”犯罪“断卡”行动进行时课件
- 北师大版八年级上册数学全册课件
- DLT52101-电力建设施工质量验收及评价规程全套验评表格
- 二年级上册数学评价方案
- 《白鹭》一等奖创新教学设计(共2个课时)
评论
0/150
提交评论