搜索
数据结构课程实验指导书－1－一、需求分析1．车辆目前情况，用户通过键盘输入，以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间（离开时间减去停在停车场的时间）和应交纳的费用（在便道上停留的时间不收费）。2.依次输入一系列数据项（3个数据：第一个字符数据A或D表示车辆的到达或离开，第二整形数据表示车辆的车牌号码，第三个整形数据表示汽车到达或离去的时间），要求同一辆汽车到达的时间比离开的时间早。3.测试数据设停车场能容纳3辆车。请输入车辆目前情况：A,1，51车辆停入停车场1号。请输入车辆目前情况：A,2，61车辆停入停车场1号2车辆停入停车场2号。请输入车辆目前情况：A,3，5输入时间错误哦！请输入车辆目前情况：A,3，61车辆停入停车场1号2车辆停入停车场2号。3车辆停入停车场3号。请输入车辆目前情况：A,4，61车辆停入停车场1号。2车辆停入停车场2号。3车辆停入停车场3号。4车辆在便道1号。停车场已满。4车辆已放在便道。请输入车辆目前情况：D,1，71车辆已离开。时间5，收费10块。2车辆停入停车场1号。3车辆停入停车场2号。4车辆停入停车场3号。请输入车辆目前情况：E,0，0程序结束，感谢使用本程序哦。本程序其他错误处理，没有设置处理。二、概要设计抽象数据类型基本操作对象是汽车类，包含来去信息，车牌号以及到达时间；ClassCar//车辆信息{Public：数据结构课程实验指导书－2－intLincese；//车牌号intArriveTime；//到达时间}；便道先进先出的特性用队列是十分好的，但停车场有一个要求就是先进的要出去时，所有车辆都要让路，所以停车场用栈来模拟，便道使用队列来模拟；ADTStopStack数据对象：D={ia|ia∈classcar};数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：boolpush（constCar&item）；Boolpop（Car&it）；booltopValue（Car&it）；intlengh（）const{returntop;}ADTStopQueue数据对象：R={ia|ia∈classcar};数据关系：R1＝{ai-1,ai|ai-1,ai∈R,i=2,...,n}约定其中a1端为队列头，an端为队列尾基本操作：boolenquene（constCar&item）；booldequene（Car&it）；boolfrontValue（Car&it）；intlength（）；算法的基本思想（1）用一车类对象做中介，存储输入的要进停车场某一车量情况。（2）当车进来的时候，首先让其按时间顺序依次入栈。（A为入栈，D为出栈，E为输入结束。）（3）当size=3即栈满时,让其在便道时按时间顺序依次入队；（4）当输入某元素要出栈时，让其上面元素依次压入另一个临时栈，并用通过当时车类的对象减去入栈时时间，算出停车时间，计算出停车费用，。在将临时栈中元素入栈。队列第一个元素入栈。程序的流程程序由三个模块组成：（1）输入模块：通过键盘输入某一车辆现在状态。（2）管理模块：首先判断第一个字符为A时，将该车类对象入栈，栈满时，在依次入队，当字符为D时，栈中元素出栈，记录当时出栈时间，得到停留时间，算出停车费用，若队中元素出列，无停车费用。(3)输出模块：输出车站目前车辆情况。三、详细设计物理数据类型数据类型（物理数据结构）的实现：数据结构课程实验指导书－3－ClassCar//车辆信息{Public：intLincese；//车牌号intArriveTime；//到达时间}；模拟停车场的栈：ClassStopStack:publiccar{{Private:intsize;inttop;Car*listArray;Public:StopStack(intsz=DefaultListSize){size=sz;top=0;listArray=newCar[sz];}~StopStack(){delete[]listArray;}boolpush（constCar&item）{if(top==size)Returnfalse;Else{listArray[top++]=item;returnture;}}boolpop（Car&it）{if(top==0)Returnfalse;Else{it==listArray[--top];returntrue;}}}booltopValue（Car&it）{if(top==0)returnfalse;Else{it=listArray[top-1];returntrue;}intlength（）const{returntop;}};物理实现模拟便道的队列,使用顺序队列。ClassStopQuene{Private:intsize;intfront;intrear;Car*listArray;Public:StopQuene(Intsz){size=sz+1;rear=0;front=1;listArray=newCar[size];}~StopQuene(){delete[]listArray;}boolenquene（constCar&item）{if((rear+2)%size==front)returnfalse;数据结构课程实验指导书－4－Rear=(rear+1)%size;listArray[rear]=it;Returnture;}booldequene（Car&it）{if(length()==0)returnfalse;It=listArray[front];front=(front+1)%size;returntrue;}boolfrontValue（Car&it）{if(length()==0)returnfalse;It=listArray[front];returntrue;}intlength（）const{return((rear+size)-front+1)%size;}};算法的具体步骤Stopstackdepot(3);//定义停车场，最大元素为3stopquenceq(50);while(1){Stopstacktemp(2);//定义临时栈Carc;charch,j;cout请输入车辆目前情况:;cinch;cinc;if(ch=='E')break;elseif(ch=='A'){if(length()!=3)depot.push(c);//元素（车辆）入栈elseq.dequene(c);//元素入列{......}//输出车站停车情况}elseif(ch=='D'){while(top.lincese!=c.lincese){cark;k=depot.pop();//栈中元素出栈temp.push(k);//进入临时栈}数据结构课程实验指导书－5－{}//输出费用while(temp.length()){cark;k=temp.pop();depot.push(k);}if(q.length!=0){cark;k=q.dequene();//元素出栈k.arrive=ch.arrive;depot.push(k);}}}算法的时空分析算法的执行，入栈，出栈，入队列，出队列。入栈时间复杂度O（1），出栈O（N），输入N次，时间复杂度最坏为O（N^2）,最好为O（N），出入队同理。输入和输出的格式输入请输入车辆到达或离开情况情况：等待输入输出：车辆在停车场号四、调试分析代码太长了、五、测试结果数据结构课程实验指导书－6－六、用户使用说明（可选）七、实验心得（可选）异常处理太难了。七、附录（可选）#includeiostreamusingnamespacestd;classcar{public:intlisence;intarrive;};templateclassElemclassstopstack{private:intsize;inttop;Elem*listArray;public:stopstack(intsz=0){size=sz;top=0;数据结构课程实验指导书－7－listArray=newElem[sz];}~stopstack(){delete[]listArray;}voidclear(){top=0;}boolpush(constElem&item){if(top==size)returnfalse;else{listArray[top++]=item;returntrue;}}boolpop(Elem&it){if(top==0)returnfalse;else{it=listArray[--top];returntrue;}}booltopValue(Elem&it)const{if(top==0)returnfalse;else{it=listArray[top-1];returntrue;}}intlength()const{returntop;}};templatetypenameElemclassstopqueue//队列的类{private:数据结构课程实验指导书－8－Elem*Array;intfence,maxsize;public:stopqueue(intsz){maxsize=sz;fence=0;Array=newElem[sz];}//队列的构建~stopqueue(){deleteArray;}//队列的销毁voidclear(){fence=0;Array=newElem[axsize];}//队列的清空boolenqueue(constElem&it){if(fence(maxsize)){Array[fence]=it;fence++;returntrue;}elsereturnfalse;}//入队booldequeue(Elem&it){if(fence0){it=Array[0];for(inti=1;ifence;i++)Array[i-1]=Array[i];fence--;returntrue;}elsereturnfalse;}//出队boolbackvalue(Elem&it){数据结构课程实验指导书－9－if(fence0)it=Array[fence-1];returntrue;}intlength()const{returnfence;}};voidmain(){stopstackcardepot(2),temp(2);stopqueuecarq(2),te(2);inta=0;while(1){cout请输入车辆到达或者离开:(A：到达D:离开E:输入结束)'\n';carc;charch;cinchc.lisencec.arrive;if(ch=='E')break;elseif(ch=='A'){if(depot.length()2){carl;depot.topValue(l);if(c.arrivel.arrive){intnum=a=depot.length();while(num--){depot.pop(l);temp.push(l);if(c.lisence==l.lisence){cout车牌重复。请重新输入.'\n';break;}}while(a--){数据结构课程实验指导书－10－temp.pop(l);depot.push(l);}if(num==-1){depot.push(c);coutc.lisence停在停车场depot.length()位置。'\n