kk.cpp

用c语言描述的数据结构编写的银行业务模拟程序

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define COUNTER         8  /* 银行共有 8 个营业窗口 */
#define ARRIVAL   COUNTER  /* 客户到达事件 */

typedef struct {
	size_t OccurTime, NType; /* 事件发生时刻；事件类型 */
} Event; /* 链表数据元素类型 */

typedef struct Enode {
	Event event;
	struct Enode *next;
} Enode, *EventList;

typedef struct {
	size_t ArrTime, Duration;  /* 到达时刻；办理时间 */
} QElem;  /* 队列数据元素类型 */

typedef struct Qnode {
	QElem Cust;  /* 客户记录 */
	struct Qnode *next;
} Qnode, *Qptr;

typedef struct {
	Qptr front, rear; /* 队头指针，队尾指针 */
} LinkQueue;

int bank_open( void );     /* 初始化操作 */
int CustArr( void );  /* 处理客户到达事件 */
int CustDepart( void );    /* 处理客户离开事件 */
void DelFirst( void );  /* 删除事件表第一个节点，并把值赋给en */
int DeQueue( LinkQueue * );  /* 出队 */
void DestroyAll( void );  /* 销毁链表和队列 */
void DestroyList( EventList ); /* 销毁链表 */
void DestroyQueue( LinkQueue * ); /* 销毁队列 */
int EnQueue( LinkQueue *, QElem );  /* 进队 */
EventList InitList( void ); /* 创建链表 */
int InitQueue( LinkQueue * ); /* 建立空队列 */
size_t Minimun( void );  /* 求长度最短队列 */
int OrderInsert( EventList, Event ); /* 插入事件表 */
size_t QueueLength( LinkQueue );  /* 计算队列长度 */

#define CLOSETIME     480  /* 每天工作 8 小时（ 60 * 8 = 480 ） */
#define MAX_TIME       30  /* 事务处理时间不超过 30 分钟 */
#define INTERVAL        5  /* 每 5 分钟至少来一位客人 */

EventList ev;          /* 事件表 */
Event en;              /* 事件 */
LinkQueue q[COUNTER];  /* 客户队列 */
QElem customer;        /* 客户记录 */
size_t TotalTime, CustNum;  /* 累计客户逗留时间，客户数 */

/* Begin of bank_open 05-9-17 00:40 */
int bank_open( void )  /* 初始化操作 */
{
    size_t i;

    srand( time(NULL) );          /* 生成随机数种子 */
    
    CustNum = TotalTime = 0;      /* 初始化累计时间和客户数 */
    if ( !( ev = InitList() ) ) {  /* 初始化事件链表 */
        return 0;  /* 创建失败，返回 0 */
    }
    en.OccurTime = 0;
    en.NType = ARRIVAL;  /* 设定第一个客户到达事件 */
    
    if ( !OrderInsert(ev, en) ) {  /* 插入事件表 */
        DestroyList( ev );
        return 0;  /* 插入失败，返回0 */
    }
    for ( i = 0; i < COUNTER; ++i ) {  /* 置空队列 */
        if ( !InitQueue(&q[i]) ) {
            DestroyList( ev );
            for ( i = 0; q[i].front; ++i ) {
                DestroyQueue( &q[i] );
            }
            return 0;  /* 创建队列失败，返回 0 */
        }
    }
    
    return 1;
} /* End of bank_open */

/* Begin of CustArr 05-9-17 08:20 */
int CustArr( void ) /* 处理客户到达事件 */ 
{
    int durtime, intertime;
    QElem e;
    size_t i;

    ++CustNum;
    /* 生成随机数 */
    durtime = rand() / (RAND_MAX / MAX_TIME + 1) + 1; /* 事务处理时间不超过 MAX_TIME 分钟 */
    intertime = rand() / (RAND_MAX / INTERVAL); /* INTERVAL 分钟内有一位客人到达银行，0 表示客户同时到达 */
    e.ArrTime = en.OccurTime;
    e.Duration = durtime;
    en.OccurTime += intertime;          /* 下一客户到达时间 */
    if ( en.OccurTime < CLOSETIME ) {   /* 银行尚未关门，插入事件表 */
        if ( !OrderInsert(ev, en) ) {   /* 插入失败 */
            DestroyAll();
            return 0;
        }
    }

    i = Minimun();  /* 求长度最短队列 */
    if ( !EnQueue(&q[i], e) ) {
        DestroyAll();
        return 0;
    }

    /* 如果此时 i 号窗口只有一位顾客，则马上把他的离开事件插入事件表 */
    if ( QueueLength(q[i]) == 1 ) {
        en.NType = i;
        en.OccurTime = e.ArrTime + durtime;
        if ( !OrderInsert(ev, en) ) {
             DestroyAll();
             return 0;
        }
    }

    return 1;
} /* End of CustArr */

/* Begin of CustDepart 05-9-17 09:00 */
int CustDepart( void ) /* 处理客户离开事件 */
{
    Qptr tmp;
    size_t i = en.NType;

    if ( !DeQueue( &q[i] ) ) {  /* 删除排头客户 */
        DestroyAll();
        return 0;
    }
    
    TotalTime = TotalTime + en.OccurTime - customer.ArrTime; /* 累计逗留时间 */
    if ( q[i].front != q[i].rear ) {
        tmp = q[i].front->next;
        customer = tmp->Cust;
        en.OccurTime += customer.Duration;
        if ( !OrderInsert(ev, en) ) {
            DestroyAll();
            return 0;
        }
    }

    return 1;
}  /* End of CustDepart */

/* Begin of DelFirst 05-9-17 00:45 */
void DelFirst( void )  /* 删除事件表第一个节点，并把值赋给en */
{
    EventList tmp = ev->next;

    ev->next = tmp->next;
    en = tmp->event;

    free(tmp);
} /* End of DelFirst */

/* Begin of DeQueue 05-9-17 08:35 */
int DeQueue(LinkQueue *Q)  /* 出队 */
{
    Qptr tmp;

    if ( Q->front == Q->rear ) {
        return 0;  /* 如果队列已空，返回 0 */
    }

    tmp = Q->front->next;
    customer = tmp->Cust;
    Q->front->next = tmp->next;
    if ( Q->rear == tmp ) {  /* 如果队尾元素被删除，则队尾指针要指向头结点 */
        Q->rear = Q->front;
    }
    free(tmp);
    
    return 1;
}  /* End of DeQueue */

/* Begin of DestroyAll 05-9-17 01:15 */
void DestroyAll( void )  /* 销毁链表和队列 */
{
     size_t i;
     
     DestroyList( ev );
     for ( i = 0; i < COUNTER; ++i ) {
         DestroyQueue( &q[i] );
     }
} /* End of DestroyAll */

/* Begin of DestroyList 05-9-16 23:00 */
void DestroyList( EventList L ) /* 销毁链表 */
{
    EventList T = L;

    for ( L = L->next; L; T = L, L = L->next ) {
        free( T );
    }
    free( T );
} /* End of DestroyList */

/* Begin of DestroyQueue 05-9-17 00:30 */
void DestroyQueue(LinkQueue *Q) /* 销毁队列 */
{
    while ( Q->front ) {
        Q->rear = Q->front->next;
        free( Q->front );
        Q->front = Q->rear;
    }
} /* End of DestroyQueue */

/* Begin of EnQueue 05-9-17 01:20 */
int EnQueue(LinkQueue *Q, QElem e)  /* 进队 */
{
    Qptr tmp = (Qptr)malloc( sizeof Qnode );
    
    if ( !tmp ) {
        return 0; /* 进队失败，返回 0 */
    }
    
    tmp->Cust = e;
    tmp->next = NULL;
    Q->rear->next = tmp;
    Q->rear = tmp;

    return 1;
} /* End of EnQueue */

/* Begin of InitList 05-9-16 22:30 */
EventList InitList( void )  /* 创建链表 */
{
    EventList h;

    if ( !( h =(EventList)malloc(sizeof Enode) ) ) {  /* 创建失败，返回 NULL */
        return NULL;
    }
    h->next = NULL;
    
    return h;
} /* End of InitList */

/* Begin of InitQueue 05-9-16 22:00 */
int InitQueue(LinkQueue *Q)  /* 建立空队列 */
{
    Q->rear = Q->front =(Qptr)malloc( sizeof Q->front );
    if ( !Q->front ) {  /* 创建失败，返回 0 */
        return 0;
    }
    Q->front->next = NULL;
    
    return 1;
} /* End of InitQueue */

/* Begin of Minimun 05-9-17 01:05 */
size_t Minimun( void )  /* 求长度最短队列 */
{
    size_t h = 0, i, j, k;

    j = QueueLength(q[0]);
    for ( i = 1; i < COUNTER; ++i ) {
        k = QueueLength(q[i]);
        if ( j > k ) {
            j = k;
            h = i;
    	}
    }
    
    return h;
} /* End of Minimun */

/* Begin of OrderInsert 05-9-16 23:15 */
int OrderInsert(EventList ev, Event a)  /* 插入事件表 */
{
    EventList tmp, h = ev, e = ev->next;

    if ( !( tmp = InitList() ) ) {  /* 分配空间失败，返回 0 */
        return 0;
    }
    /* 插入 */
    tmp->event = a;
    while ( e && (a.OccurTime > e->event.OccurTime) ) {
        h = e;
        e = e->next;
    }
    h->next = tmp;
    tmp->next = e;

    return 1;
} /* End of OrderInsert */

/* Begin of QueueLength 05-9-17 01:00 */
size_t QueueLength(LinkQueue Q) /* 计算队列长度 */
{
    size_t i;

    for ( i = 0; Q.front->next; ++i ) {
        Q.front = Q.front->next;
    }

    return i;
} /* End of QueueLength */
extern EventList ev;   /* 事件表 */
extern Event en;       /* 事件 */
extern size_t TotalTime, CustNum;  /* 累计客户逗留时间，客户数 */

int main( void )
{
    if ( !bank_open() ) {
        return EXIT_FAILURE;  /* 初始化失败，退出 */
    }
    while ( ev->next ) {
        DelFirst();  /* 删除事件表第一个节点，并把值赋给en */
        if ( en.NType == ARRIVAL ) {
            if ( !CustArr() ) {
                return EXIT_FAILURE;
            }
        } else if ( !CustDepart() ) {
            return EXIT_FAILURE;
        }
    }
    printf( "Average Stay Time：%.2f minutes\n", (float)TotalTime / CustNum );
    
    puts( "Press ENTER to quit..." );
    getchar();
    DestroyAll();
    
    return EXIT_SUCCESS;
}