数据结构停车场问题

1、数据结构课程实验指导书一、需求分析1 车辆目前情况，用户通过键盘输入，以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间（离开时间减去停在停车场的时间）和应交纳的费用（在便道上停留的时间不收费）。2.依次输入一系列数据项（3个数据：第一个字符数据A或D表示车辆的到达或离开，第二整形数据表示车辆的车牌号码，第三个整形数据表示汽车到达或离去

2、的时间），要求同一辆汽车到达的时间比离开的时间早。3.测试数据设停车场能容纳3辆车。 请输入车辆目前情况：A ,1，5 1车辆停入停车场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、3车辆停入停车场2号。4车辆停入停车场3号。请输入车辆目前情况：E ,0，0程序结束，感谢使用本程序哦。本程序其他错误处理，没有设置处理。二、概要设计抽象数据类型基本操作对象是汽车类，包含来去信息，车牌号以及到达时间；Class Car/车辆信息Public：int Lincese；/车牌号int ArriveTime；/到达时间；便道先进先出的特性用队列是十分好的，但停车场有一个要求就是先进的要出去时，所有车辆都要让路，所以停车场用栈来模拟，便道使用队列来模拟；ADT StopStack数据对象：D=|class car;数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端

4、为栈顶，a1 端为栈底。基本操作：bool push（const Car& item）；Bool pop（Car&it）；bool topValue（Car&it）；int lengh（）constreturn top;ADT StopQueue数据对象：R=|class car;数据关系： R1 | ai-1, ai R, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾基本操作：bool enquene（constCar&item）；bool dequene（Car&it）；bool frontValue（Car&it）；int length（）；算法的基本思想 （1）用一车类

5、对象做中介，存储输入的要进停车场某一车量情况。 （2）当车进来的时候，首先让其按时间顺序依次入栈。（A为入栈，D为出栈，E为输入结束。） （3）当size=3即栈满时,让其在便道时按时间顺序依次入队； （4）当输入某元素要出栈时，让其上面元素依次压入另一个临时栈，并用通过当时车类的对象减去入栈时时间，算出停车时间，计算出停车费用，。在将临时栈中元素入栈。队列第一个元素入栈。程序的流程程序由三个模块组成：（1） 输入模块：通过键盘输入某一车辆现在状态。（2） 管理模块：首先判断第一个字符为A时，将该车类对象入栈，栈满时，在依次入队，当字符为D时，栈中元素出栈，记录当时出栈时间，得到停留时间，算出

6、停车费用，若队中元素出列，无停车费用。 (3)输出模块：输出车站目前车辆情况。三、详细设计物理数据类型数据类型（物理数据结构）的实现：Class Car/车辆信息Public：int Lincese；/车牌号int ArriveTime；/到达时间；模拟停车场的栈：Class StopStack: public carPrivate:int size;int top;Car* listArray;Public:StopStack(int sz=DefaultListSize)size=sz;top=0;listArray=new Carsz;StopStack()deletelistArray

7、;boolpush（constCar&item）if(top=size)Returnfalse;ElselistArraytop+=item;returnture;boolpop（Car&it）if(top=0)Return false;Else it=listArray-top;return true;booltopValue（Car&it）if(top=0)return false; Elseit=listArraytop-1;return true;int length（）constreturn top;物理实现模拟便道的队列,使用顺序队列。Class StopQuenePrivate:

8、int size;int front;int rear;Car *listArray;Public:StopQuene(Int sz)size=sz+1;rear=0;front=1;listArray=newCarsize;StopQuene()delete listArray;bool enquene（const Car&item） if(rear+2)%size=front) return false;Rear=(rear+1)%size;listArrayrear=it;Returnture;bool dequene（Car&it） if(length()=0)return false

9、;It=listArrayfront;front=(front+1)%size;returntrue;boolfrontValue（Car&it） if(length()=0)returnfalse;It=listArrayfront;returntrue;intlength（）constreturn(rear+size)-front+1)%size;算法的具体步骤 Stopstack depot(3); /定义停车场，最大元素为3 stopquence q(50); while(1) Stopstack temp(2); /定义临时栈Car c;char ch,j;coutch;cinc;i

10、f(ch=E) break;else if(ch=A) if(length()!=3) depot.push(c); /元素（车辆）入栈 else q.dequene(c); /元素入列 . /输出车站停车情况 else if(ch=D) while(top.lincese!=c.lincese)car k;k=depot.pop(); /栈中元素出栈temp.push(k); /进入临时栈 /输出费用 while(temp.length() car k; k=temp.pop(); depot.push(k); if(q.length!=0) car k;k=q.dequene(); /元素

11、出栈k.arrive=ch.arrive;depot.push(k); 算法的时空分析 算法的执行，入栈，出栈，入队列，出队列。入栈时间复杂度O （1），出栈O（N），输入N次，时间复杂度最坏为O（N2）,最好为 O（N），出入队同理。 输入和输出的格式输入 请输入车辆到达或离开情况情况：等待输入输出：车辆在停车场 号四、调试分析代码太长了、五、测试结果六、用户使用说明（可选）七、实验心得（可选）异常处理太难了。7、 附录（可选）#include using namespace std; class car public:int lisence; int arrive;template cla

12、ss stopstackprivate: int size; int top; Elem *listArray;public:stopstack(int sz=0) size=sz; top=0; listArray = new Elemsz; stopstack() delete listArray; void clear() top = 0; bool push(const Elem& item) if (top = size) return false; else listArraytop+ = item; return true; bool pop(Elem& it) if (top

13、= 0) return false; else it = listArray-top; return true; bool topValue(Elem& it) const if (top=0)return false; else it = listArraytop-1; return true; int length() const return top; ;template class stopqueue/队列的类private:Elem* Array;int fence,maxsize;public:stopqueue(int sz)maxsize=sz;fence=0;Array=ne

14、w Elemsz; /队列的构建stopqueue()delete Array; /队列的销毁void clear()fence=0;Array=new Elemaxsize; /队列的清空bool enqueue(const Elem& it)if(fence0)it=Array0;for(int i=1;i0)it=Arrayfence-1;return true; int length() const return fence; ;void main() stopstack depot(2),temp(2); stopqueue q(2),te(2); int a=0; while(1)

15、 cout请输入车辆到达或者离开:(A：到达 D:离开 E:输入结束)chc.lisencec.arrive; if(ch=E) break; else if(ch=A) if(depot.length()l.arrive) int num=a=depot.length(); while(num-) depot.pop(l); temp.push(l); if(c.lisence=l.lisence) cout车牌重复。请重新输入.n; break; while(a-) temp.pop(l); depot.push(l); if(num=-1) depot.push(c); coutc.li

16、sence停在停车场depot.length()位置。n; else cout时间应比上一时间晚!请重新输入:n; continue; else car l; q.backvalue(l); if(q.length()=2) cout停车场已满!l.arrive) int num=a=depot.length(); while(num-) depot.pop(l); temp.push(l); if(c.lisence=l.lisence) cout停车场已有该车。请重新输入.n; break; while(a-) car l; temp.pop(l); depot.push(l); int

17、n=a=q.length(); while(n-) car h; q.dequeue(h); te.enqueue(h); if(h.lisence=c.lisence) cout便道已有该停车。请重新输入.n; break; while(a-) car h; te.dequeue(h); q.enqueue(h); if(num=-1)&(n=-1) q.enqueue(c); coutc.lisence停在便道q.length()位置n; else cout时间应比上一时间晚!请重新输入:f.arrive) while(1) car k; depot.pop(k); if(c.lisenc

18、e!=k.lisence) temp.push(k); a+; else coutk.lisence已出停车场.需收取(c.arrive-k.arrive)元.n; while(a-) car k; temp.pop(k); depot.push(k); else cout时间应比上一时间晚!请重新输入:0) q.backvalue(f);if(c.arrivef.arrive) q.dequeue(d); d.arrive=c.arrive; depot.push(d); coutd.lisence停在停车场2位置n; else cout时间应比上一时间晚!请重新输入:n; continue

19、; #include using namespace std; class car public:int lisence; int arrive;template class stopstackprivate: int size; int top; Elem *listArray;public:stopstack(int sz=0) size=sz; top=0; listArray = new Elemsz; stopstack() delete listArray; void clear() top = 0; bool push(const Elem& item) if (top = si

20、ze) return false; else listArraytop+ = item; return true; bool pop(Elem& it) if (top = 0) return false; else it = listArray-top; return true; bool topValue(Elem& it) const if (top=0)return false; else it = listArraytop-1; return true; int length() const return top; ;template class stopqueue/队列的类priv

21、ate:Elem* Array;int fence,maxsize;public:stopqueue(int sz)maxsize=sz;fence=0;Array=new Elemsz; /队列的构建stopqueue()delete Array; /队列的销毁void clear()fence=0;Array=new Elemaxsize; /队列的清空bool enqueue(const Elem& it)if(fence0)it=Array0;for(int i=1;i0)it=Arrayfence-1;return true; int length() const return fe

22、nce; ;void main() stopstack depot(2),temp(2); stopqueue q(2),te(2); int a=0; while(1) cout请输入车辆到达或者离开:(A：到达 D:离开 E:输入结束)chc.lisencec.arrive; if(ch=E) break; else if(ch=A) if(depot.length()l.arrive) int num=a=depot.length(); while(num-) depot.pop(l); temp.push(l); if(c.lisence=l.lisence) cout车牌重复。请重新

23、输入.n; break; while(a-) temp.pop(l); depot.push(l); if(num=-1) depot.push(c); coutc.lisence停在停车场depot.length()位置。n; else cout时间应比上一时间晚!请重新输入:n; continue; else car l; q.backvalue(l); if(q.length()=2) cout停车场已满!l.arrive) int num=a=depot.length(); while(num-) depot.pop(l); temp.push(l); if(c.lisence=l.l

24、isence) cout停车场已有该车。请重新输入.n; break; while(a-) car l; temp.pop(l); depot.push(l); int n=a=q.length(); while(n-) car h; q.dequeue(h); te.enqueue(h); if(h.lisence=c.lisence) cout便道已有该停车。请重新输入.n; break; while(a-) car h; te.dequeue(h); q.enqueue(h); if(num=-1)&(n=-1) q.enqueue(c); coutc.lisence停在便道q.leng

25、th()位置n; else cout时间应比上一时间晚!请重新输入:f.arrive) while(1) car k; depot.pop(k); if(c.lisence!=k.lisence) temp.push(k); a+; else coutk.lisence已出停车场.需收取(c.arrive-k.arrive)元.n; while(a-) car k; temp.pop(k); depot.push(k); else cout时间应比上一时间晚!请重新输入:0) q.backvalue(f);if(c.arrivef.arrive) q.dequeue(d); d.arrive=

26、c.arrive; depot.push(d); coutd.lisence停在停车场2位置n; else cout时间应比上一时间晚!请重新输入:n; continue; #include using namespace std; class car public:int lisence; int arrive;template class stopstackprivate: int size; int top; Elem *listArray;public:stopstack(int sz=0) size=sz; top=0; listArray = new Elemsz; stopsta

27、ck() delete listArray; void clear() top = 0; bool push(const Elem& item) if (top = size) return false; else listArraytop+ = item; return true; bool pop(Elem& it) if (top = 0) return false; else it = listArray-top; return true; bool topValue(Elem& it) const if (top=0)return false; else it = listArray

28、top-1; return true; int length() const return top; ;template class stopqueue/队列的类private:Elem* Array;int fence,maxsize;public:stopqueue(int sz)maxsize=sz;fence=0;Array=new Elemsz; /队列的构建stopqueue()delete Array; /队列的销毁void clear()fence=0;Array=new Elemaxsize; /队列的清空bool enqueue(const Elem& it)if(fenc

29、e0)it=Array0;for(int i=1;i0)it=Arrayfence-1;return true; int length() const return fence; ;void main() stopstack depot(2),temp(2); stopqueue q(2),te(2); int a=0; while(1) cout请输入车辆到达或者离开:(A：到达 D:离开 E:输入结束)chc.lisencec.arrive; if(ch=E) break; else if(ch=A) if(depot.length()l.arrive) int num=a=depot.length(); while(num-) depot.pop(l); temp.push(l); if(c.lisence=l.lisence) cout车牌重复。请重新输入.n; break;