栈和队列及其应用-理发室问题.doc

栈和队列及其应用 目的： （1）了解栈和队列的特性，以便在实际问题背景下灵活运用应用； （2）巩固对这两种结构的构造方法的理解 。 一、问题描述： 1、题目内容：使用队列模拟理发馆的排队现象，通过仿真手法评估其营业状况。 设某理发馆设有N把理发椅，可同时为N位顾客进行理发。当顾客进门时，若有空闲理发椅，则立即入座理发，否则依次排队候理，一旦有顾客理完发离去时，排在队头的顾客便开始理发。假若理发馆每天连续营业T小时（只要有顾客等待，理发椅就不空），求一天内顾客在理发馆内的平均逗留时间（包括理发所需时间和排队等候的时间）与顾客排队等候理发的人数的平均值（排队长度的平均值）。 2、基本要求 （1）当给定理发椅数及营业时间后，由随机数确定顾客理发时间及进门间隔时间，求出一天内顾客在理发馆平均逗留时间、平均队长及关门后收尾工作的时间。 （2）由用户读入的数据仅为理发椅数及营业时间。营业的时间以分钟计，理发椅数及关门时间均为整型，且均大于等于1。 3、测试数据 理发椅数目N及关门时间由用户读入，第一个顾客进门的时刻为0，之后每个顾客的进门时刻在前一个顾客进门时设定。即在进门事件发生时随即产生两个随机数（DU，IN），DU为进门顾客理发所需的服务时间（简称理发时间）；IN为下一个顾客到达的时间间隔（简称间隔时间）。 二、实现提示： R为由随机数发生器的随机数，顾客理发时间和顾客之间的间隔时间不妨假设与R有关，可以由下式确定： DU=15+R%50 IN=2+R%10 确定的方法与实际越吻合，模拟的结果越接近现实的情况。 #includeiostream.h #includestdlib.h #includetime.h #define XX 12 //本程序关键，XX控制随机数R的范围 typedef int ElemType; struct Queue { ElemType *queue; int front,rear,len; int maxsize; }; void Init(Queue Q,int i) { Q.maxsize=i; Q.queue=new ElemType[Q.maxsize]; Q.front=Q.rear=0; Q.len=0; } void str(Queue Q,ElemType x) { if((Q.rear+1)%Q.maxsize==Q.front) { int k=sizeof(ElemType); Q.queue=(ElemType*)malloc(2*Q.maxsize*k); if(Q.rear!=Q.maxsize-1) { for(int i=0;iQ.rear;i++) { Q.queue[i+Q.maxsize]=Q.queue[i]; } Q.rear+=Q.maxsize; } Q.maxsize*=2; } Q.queue[Q.rear]=x; Q.rear=(Q.rear+1)%Q.maxsize; Q.len++; } void delet(Queue Q) { Q.front=(Q.front+1)%Q.maxsize; Q.len--; } void main() { Queue Qchair; //定义一个队列与空椅的相关联； Queue Qwait; //定义一个队列与排队人数，是否轮在理发相关联； Init(Qchair,10);Init(Qwait,10);//初始化两个队列，并赋值长度为10 int n,t; cout请输入数据：endl; cout理发椅：;cinn; cout营业时间：;cint; srand((int)time(0)); int h[1000]; //理发所需时间 int g[1000]; //到来时间 int x[1000][2]; //开始理发时间和开始理发时队的长度 int i=1; g[1]=0; //第一个顾客到来时间为0； int R; while(g[i]60*t) //当最后一个顾客到来时间超过营业时间，结束操作 { R=rand()%XX+1; //得到随机数R h[i]=15+R%50; //根据随机数计算得到第i个顾客理发所需时间，并存放h数组中； g[i+1]=g[i]+2+R%10; //得到第i+1个顾客到来所需时间，得到第i+1个顾客实际到来时间，存放g数组中； i++; } int a(1),b(1),c(1); for(i=0;i6