Question

求数据结构最小生成树的实验报告，包含流程图，

Answer 1

数据结构（实验报告）

姓名： 高 申 雷

学号： 0613042024

日期： 2008年3月25日

一、实验题目： 停 车 场 管 理
二、问题描述：
设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆次序。编制一程序模拟该停车场的管理。
三、需求分析：
停车场采用栈式结构，停车场外的便道采用队列结构（即便道就是等候队列）。停车场的管理流程如下：
①当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进栈（车辆进入停车场）；如果停车场已满，则车辆进入等候队列（车辆进入便道等候）。
②当车辆要求出栈时，该车到栈顶的那些车辆先弹出栈（在它之后进入的车辆必须先退出车场为它让路），再让该车出栈，其他车辆再按原次序进栈（进入车场）。当车辆出栈完毕后，检查等候队列（便道）中是否有车，有车则从队列头取出一辆车压入栈中。
四、概要设计：
1、用栈模拟停车场，用队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。
2、每一组输入数据包括三个数据项：汽车到达或离去的信息，汽车牌照号码以及到达或离去的时刻。
3、每次输入完进行输出操作：若是车辆到达，输出汽车在停车场内或便道上的停车位置；若是车辆离去，输出停留时间和应缴纳的费用（在便道上停留的时间不收费）。
4、其中栈以顺序结构实现，队列以链表结构实现。
五、详细设计：
1、定义栈（停车场） struct stack
初始化栈void initstack(stack* s)
元素进栈int instack(stack* s,cinfo x)
元素出栈cinfo outstack(stack* s)
2、定义队列（车场外的便道）struct queue
初始化队列void initqueue(queue* q)
元素进队列void inqueue(queue* q,int num1)
元素出队列int outqueue(queue* q)
3、处理车辆到达的情况void carrival(stack* s,queue* q,cinfo x)
处理车辆离开void carleave(stack* s1,stack* s2,queue* q,cinfo x)
4、主程序void main()
注：详细设计中的具体代码见模块代码中。
六、模块代码：
#include"iostream.h"
int N;
const int M=5;//M为单元时间的收费值
struct cinfo//定义栈中元素的类型
{ int cnum; int atime;
};
struct stack//定义栈
{ cinfo cstack[3000];//这里随便定义一个数字表示数组的长度,因为后
int top; //面会根据用户输入的N值作为停车场能够停车的
int size; //数量.
};
struct node//定义队列节点的类型
{ node* next; int nnum;
};
struct queue//定义队列
{ node *front,*rear;
};
void initstack(stack* s)//初始化栈
{ s->top=-1;
}
int instack(stack* s,cinfo x)//元素进栈
{ //int 元素进栈n;
if(s->top==N-1)
{ cout<<"Stack is full!"<<endl; return 0;
} else
{ s->cstack[++s->top]=x;
return 1;
}
}
cinfo outstack(stack* s)//元素出栈
{ cinfo y;
if(s->top<0)
{ y.cnum=NULL;
y.atime=NULL;
return y;
} else
{ s->top--;
return s->cstack[s->top+1];
}
}
void initqueue(queue* q)//初始化队列
{ q->front=new node;
q->rear=q->front;
q->front->next=NULL;
q->front->nnum=0;
}
void inqueue(queue* q,int num1)//元素进队列
{ node* p;
p=new node;
p->nnum=num1;
p->next=NULL;
q->rear->next=p;
q->rear=p;
q->front->nnum++;
}
int outqueue(queue* q)//元素出队列
{ node* p;
int n;
if(q->front==q->rear) return 0;
else {
p=q->front->next;
q->front->next=p->next;
if(p->next==NULL)
q->rear=q->front;
n=p->nnum;
delete p;
q->front->nnum--;
return n;
}
}
void carrival(stack* s,queue* q,cinfo x)//处理车辆到达的情况
{ int f;
f=instack(s,x);
if(f==0) {
inqueue(q,x.cnum);
cout<<"The Number"<<x.cnum<<" "<<"car park into the pos"<<q->front->nnum<<" "<<"of the road."<<endl;
} else
{ cout<<"The Number"<<x.cnum<<" "<<"car park into the pos"<<s->top+1<<" "<<"of the room."<<endl;
}
}
void carleave(stack* s1,stack* s2,queue* q,cinfo x)//处理车辆离开
{ node* p;
cinfo y;
int a,n=0;
while((s1->top>-1)&&(n==0))
{ y=outstack(s1);
if(y.cnum!=x.cnum) {
a=instack(s2,y);
} else
n=1;
}
if(y.cnum==x.cnum)
{ cout<<"The number"<<x.cnum<<" "<<"car want to leave,the charge is"<<" "<<(x.atime-y.atime)*M<<" "<<"yuan!"<<endl;
while(s2->top>-1)
{ y=outstack(s2);
n=instack(s1,y);
}
a=outqueue(q);
if(a!=0)
{ y.cnum=a; y.atime=x.atime;
n=instack(s1,y);
cout<<"The Number"<<y.cnum<<" "<<"car park into the pos"<<s1->top+1<<" "<<"of the room."<<endl;
}
} else
{ while(s2->top>-1)
{ y=outstack(s2);
n=instack(s1,y);
}
p=q->front;
n=0;
while(p->next!=NULL&&n==0)
{ if(p->next->nnum!=x.cnum)
p=p->next;
else {
p->next=p->next->next;
q->front->nnum--;
if(p->next=NULL)
q->rear=q->front;
cout<<"The number"<<x.cnum<<" "<<"want to leave from the road."<<endl;
n=1;
}
}
if(n==0)
{ cout<<"You have entered a wrong number!"<<endl;
}
}
}
void main()//主程序
{ //int maxsize;
cout<<"Start，Written by ZIGZ"<<endl<<endl<<endl;
cout<<"Please enter a number as the maxsize of the roomStack:"<<endl;
cin>>N;//这里N将作为栈能存放元素的数量
while(N<=0)
{ cout<<"Oh!You have enter a wrong number,'N' should above 0.Please enter another number again:"<<endl;
cin>>N;
} //stack *max;
//max->size=maxsize;
char ch1;
stack* s1,*s2;
queue* q;
cinfo x;
int flag;
s1=new stack;
s2=new stack;
q=new queue;
initstack(s1);
initstack(s2);
initqueue(q);
flag=1;
for(;;) {cout<<"Please enter the infomation: 'A'/'D'; car number; car arrival time."<<endl;
cin>>ch1>>x.cnum>>x.atime;
switch(ch1)
{ case'A':
case'a':carrival(s1,q,x);
break;
case'D':
case'd':carleave(s1,s2,q,x);
break;
case'E':
case'e':flag=0;cout<<"Ok,the system will be shut down!Written by ZIGZ!"<<endl;
break;
default:cout<<"You have enter a wrong!!"<<endl;
}
if(flag==0)
break;
}
}
七、运行结果：

八、经验小结：
通过《停车场管理》的实验学习使我基本上理解并学会了用栈的先进后出和队列的先进先出的原理去解决实际问题的思想和方法。但是在编程方面还是很欠缺，还要加强学习。