//數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）中棧的習(xí)題
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#define ERROR 0
#define OK 1
typedef struct{
int OccurTime;
int NType;
}Event;
typedef struct{
int ArrivalTime;
int Duration;
}QElemType;
struct LNODE
{
Event data;
struct LNODE *next;
};
typedef struct LNODE LNode;
typedef struct LNODE *LinkList;
typedef struct LNODE *EvenList;
typedef struct QNode{
QElemType elem;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{ QueuePtr front;
QueuePtr rear;
}LinkQueue;
EvenList ev;
Event en;
LinkQueue q[5];
QElemType customer;
int TotalTime,CustomerNum,CloseTime;
int InitList(EvenList *L)
{
*L=(LNode *)malloc(sizeof(LNode));
if(!(*L)) exit(ERROR);
(*L)->next=NULL;
return OK;
}
int DelFirst(EvenList *L,Event *e)
{ LNode *pc,*q;
pc=*L;q=pc->next;
pc->next=q->next;*e=q->data;return OK;}
int ListEmpty(LNode L)
{LNode *p;
int j=0;
p=L.next;
while(p)
{j++;break;}
if(j==0) return 1;
else return 0;
}
int compare(Event a,Event b)
{ if(a.OccurTime>b.OccurTime) return 1;
else if(a.OccurTime==b.OccurTime) return 0;
else return -1;
}
int OrderInsert(EvenList *L,Event e,int (* cmp)(Event ,Event ))
{ LNode *p,*pc;/*把事件插入鏈表*/
p=(LNode *)malloc(sizeof(LNode));/*分配空間*/
if(!p) { printf("not"); return(0);}
if(ListEmpty(**L))
{ p->data=e;p->next=(*L)->next;(*L)->next=p;}
else {
switch(cmp(((*L)->next)->data,e))
{case -1:pc=(*L)->next;
while(pc->next!=NULL)
{
if((pc->next)->data.OccurTime<=e.OccurTime)
pc=pc->next;
else break;
}
p->data=e;p->next=pc->next;/*把它接在比它大的前*/
pc->next=p;break;
case 0:pc=(*L)->next;/*相等時(shí)，接在相等的后面*/
p->data=e;p->next=pc->next;
pc->next=p;break;
case 1:p->data=e;p->next=(*L)->next;
(*L)->next=p;break;/*小于時(shí)，接在最前面*/
}}
return 1;
}
void DestroyList(EvenList *L)/*銷毀表*/
{LNode *p;
while(*L)
{p=(*L)->next;free(*L);*L=p;}
}
int InitQueue(LinkQueue *Q)/*初始化隊(duì)列*/
{ Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q->front) exit(0);
(Q->front)->next=NULL;
return OK;
}
int DestroyQueue(LinkQueue *Q)/*銷毀隊(duì)列*/
{ while(Q->front)
{ Q->rear=Q->front->next;
free(Q->front);
Q->front=Q->rear;
}
return OK;
}
int EnQueue(LinkQueue *Q,QElemType e)/*插在隊(duì)最后*/
{QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(0);
p->elem=e;p->next=NULL;
(Q->rear)->next=p;
Q->rear=p;/*重新設(shè)置隊(duì)尾*/
return OK;
}
int QueueEmpty(LinkQueue Q)
{ if(Q.front==Q.rear) return OK;
else return 0;}
int DelQueue(LinkQueue *Q,QElemType *e)/*刪除隊(duì)的第一個(gè)元素*/
{QueuePtr p;
if(QueueEmpty(*Q)) return ERROR;
p=(Q->front)->next;
*e=p->elem;
(Q->front)->next=p->next;
if(Q->rear==p) Q->rear=Q->front;
free(p);
return OK;
}
void GetHead(LinkQueue Q,QElemType *a)
{QNode *p;
if(Q.front==Q.rear) exit(0);
p=(Q.front)->next;
*a=p->elem;
}
int QueueLength(LinkQueue Q)/*隊(duì)的長(zhǎng)度*/
{ int i=0;
QNode *pc;
if(Q.front==Q.rear) return 0;
pc=Q.front;
while(pc->next)
{i++;pc=pc->next;}
return i;
}
int Mininum(LinkQueue *Q)/*求長(zhǎng)度最短的隊(duì)*/
{ int a[4],e,j,i;
for(i=1;i<=4;i++)
a[i-1]=QueueLength(Q[i]);
e=a[0];j=1;
for(i=1;i<=3;i++)
if(e>a[i]) {e=a[i];j=i+1;}
return j;
}
void OpenForDay()/*初始化操作*/
{ int i;
TotalTime=0;CustomerNum=0;/*初始化累計(jì)時(shí)間和客戶數(shù)*/
InitList(&ev);
en.OccurTime=0;en.NType=0;/*設(shè)定第一個(gè)客戶到達(dá)事件*/
OrderInsert(&ev,en,compare);/*把它插入事件表*/
for(i=1;i<=4;i++) InitQueue(&q[i]);/*置空隊(duì)列*/
}
void Random(int *a,int *b)/*生成隨機(jī)數(shù)，a為每個(gè)客戶辦理時(shí)間在30分鐘內(nèi)，
b 為兩相隔客戶到達(dá)的間隔時(shí)間不超過(guò)5分鐘*/
{ *a=0+rand()%30;*b=0+rand()%5;}
void CustomerArrived()/*處理客戶到達(dá)事件*/
{int durtime,intertime,t,i,b;
++CustomerNum;/*記錄客戶數(shù)*/
Random(&durtime,&intertime);
b=en.OccurTime;
t=en.OccurTime+intertime;/*下一客戶到達(dá)時(shí)刻*/
if(t<CloseTime)
{en.OccurTime=t;en.NType=0;
OrderInsert(&ev,en,compare);
}
i=Mininum(q);/*求隊(duì)列最短*/
customer.ArrivalTime=b;customer.Duration=durtime;/*為要插入隊(duì)的客戶設(shè)置到達(dá)時(shí)間和辦理所需時(shí)間*/
EnQueue(&q[i],customer);
if(QueueLength(q[i])==1)
{en.OccurTime=b+durtime;en.NType=i;
OrderInsert(&ev,en,compare);/*設(shè)定第i 個(gè)離開(kāi)事件并插入事件表*/
}
}
void CustomerDeparture()/*處理客戶離開(kāi)事件*/
{int i;
i=en.NType;DelQueue(&q[i],&customer);/*刪除第i隊(duì)列的排頭客戶*/
TotalTime+=en.OccurTime-customer.ArrivalTime;/*累計(jì)客戶逗留時(shí)間*/
if(!QueueEmpty(q[i]))/*設(shè)定第i隊(duì)列的一個(gè)將要離開(kāi)事件并插入事件表*/
{ GetHead(q[i],&customer);/*得到它的資料*/
en.OccurTime+=customer.Duration;en.NType=i;
OrderInsert(&ev,en,compare);
}
}
void Bank_Simulation()
{
OpenForDay();/*初始化*/
while(!ListEmpty(*ev))/*非空時(shí)，刪掉表里的第一個(gè)*/
{ DelFirst(&ev,&en);
if(en.NType==0)
CustomerArrived();/*是客戶還沒(méi)辦理的，就處理到達(dá)事件*/
else CustomerDeparture();/*否則處理離開(kāi)事件*/
}
printf("The Average Time is %.2f\n",(float)TotalTime/CustomerNum);
}
void main()
{scanf("%d",&CloseTime);/*輸入關(guān)門時(shí)間*/
Bank_Simulation();
getch();
}