資料結構——佇列（銀行叫號系統）

資料結構——佇列（銀行叫號系統）

一、實驗目的

（1）掌握佇列的鏈式存盤結構

（2）掌握佇列的基本操作，并能進行應用實踐

（3）使用C/C++語言和佇列實作”銀行叫號系統“專題

二、實驗任務

設計一個控制臺程式，模擬銀行排隊業務，要求實作功能：

（1）輸出程式界面，提示客戶輸入銀行視窗數量和開放視窗時間

（2）客戶隨機時間進入銀行，程式在事件表中記錄客戶進入時間和離開時間，并將客戶排入視窗佇列，辦理完業務后退出佇列
（3）視窗開放時間結束，客戶停止進入銀行，直到所有客戶退出佇列之后計算出客戶的平均服務時間

三、實驗代碼

1.事件串列
1）定義事件結點

typedef struct Event//定義事件結點
{
	int occurTime;//發生時刻
	int type;//事件型別：0表示顧客到達；1~N表示顧客從N號視窗離開
	struct Event *next;
}Event,*EventList;

2）初始化事件鏈表

int InitList(EventList* pList)//初始化事件鏈表
{
	*pList=(Event*)malloc(sizeof(Event));
	if(*pList==NULL)
	{
		printf("分配記憶體失敗\n");
		exit(-1);
	}
	(*pList)->next=NULL;
	return OK;
}

3）插入元素

int OrderInsert(EventList pList,Event sEvent)//插入元素
{
	Event *pAfter,*pBefore;//臨時變數，用于在鏈表中插入結點
	pAfter=pList;
	pBefore=pList->next;
	while(pAfter!=NULL && sEvent.occurTime>pAfter->occurTime)//比較事件發生的時間
	{
		pBefore=pAfter;
		pAfter=pAfter->next;
	}
	pBefore->next=(Event*)malloc(sizeof(Event));//創建一個新的結點，掛在Before和After兩個結點中間
	pBefore->next->occurTime=sEvent.occurTime;//對新結點賦值
	pBefore->next->type=sEvent.type;
	pBefore->next->next=pAfter;
	return OK;
}

4）判斷鏈表是否為空

int EmptyList(EventList pList)//判斷鏈表是否為空
{
	if(pList->next==NULL)
		return TRUE;
	else
		return FALSE;
}

5）洗掉首結點

int DelFirst(EventList pList,Event *pEvent)//洗掉首結點
{
	Event *pTmp;
	if(EmptyList(pList))
	{
		printf("鏈表為空");
		return ERROR;
	}
	else 
	{
		pTmp=pList->next;//洗掉鏈表首結點
		pList->next=pTmp->next;
		*pEvent=*pTmp;//保存數值
		free(pTmp);//釋放記憶體
		return OK;
	}
}

6）遍歷鏈表

int ListTraverse(EventList pList)//遍歷鏈表
{
	Event *pTmp;
	pTmp=pList;
	while(pTmp->next!=NULL)
	{
		pTmp=pTmp->next;
		if(pTmp->type==0)
			printf("第%d分鐘，下一名客戶即將到來，\n",pTmp->occurTime);
		else
			printf("第%d分鐘，%d號視窗的客戶即將離開，\n",pTmp->occurTime,pTmp->type);
	}
	printf("\n");
	return OK;
}

2.鏈式佇列
1）定義鏈式佇列資料結構

typedef struct QElemType{//定義鏈式佇列資料結構
	int arriveTime;//到達時間
	int duration;//持續時間
	struct QElemType *next;
}QElemType;
typedef struct LinkedQueue{
	QElemType *front;//頭指標
	QElemType *rear;//尾指標
}LinkedQueue;

2）初始化佇列

int InitQueue(LinkedQueue *pQueue)//初始化佇列
{
	pQueue->front=pQueue->rear=(QElemType*)malloc(sizeof(QElemType));//分配記憶體
	if(pQueue->front==NULL)
	{
		printf("分配記憶體失敗\n");
		exit(-1);
	}
	pQueue->front->next=NULL;
	return OK;
}

3）判斷鏈表是否為空

int EmptyQueue(LinkedQueue *pQueue)//判斷鏈表是否為空
{
	if(pQueue->front==pQueue->rear)
		return TRUE;
	else 
		return FALSE;
}

4）首結點出隊

int DelQueue(LinkedQueue *pQueue,QElemType *pQElem)//首結點出隊
{
	QElemType *pTmp;//臨時結點指標
	if(EmptyQueue(pQueue))
	{
		printf("佇列為空，不能繼續出佇列\n");
		return ERROR;
	}
	else 
	{//指向首結點后一個元素，并復制給pQElem
		pTmp=pQueue->front->next;
		*pQElem=*pTmp;
		pQueue->front->next=pTmp->next;//洗掉這個結點
		if(pQueue->rear==pTmp)
			pQueue->rear=pQueue->front;
		free(pTmp);
		return OK;
	}
}

5）結點入隊

int EnQueue(LinkedQueue *pQueue,QElemType sQElem)//結點入隊
{
	QElemType *pTmp;//臨時結點指標
	pTmp=(QElemType*)malloc(sizeof(QElemType));
	if(pTmp==NULL)
	{
		printf("記憶體分配失敗\n");
		exit(-1);
	}
	else 
	{//尾結點指向新入隊的元素
		*pTmp=sQElem;
		pTmp->next=NULL;
		pQueue->rear->next=pTmp;
		pQueue->rear=pTmp;
	}
	return OK;
}

6）獲取佇列長度

int QueueLength(LinkedQueue *pQueue)//獲取佇列長度
{
	QElemType *pTmp;//臨時結點指標
	int count=0;//遍歷鏈表，統計結點數
	pTmp=pQueue->front->next;//佇列第一個結點
	while(pTmp!=NULL)
	{
		count++;
		pTmp=pTmp->next;
	}
	return count;
}

7）獲取佇列首結點

int GetHead(LinkedQueue *pQueue,QElemType *pQElem)//獲取佇列首結點
{
	if(EmptyQueue(pQueue))
	{
		printf("佇列為空");
		return ERROR;
	}
	*pQElem=*(pQueue->front->next);
	return OK;
}

8）遍歷佇列

int QueueTraverse(LinkedQueue *pQueue)//遍歷佇列
{
	QElemType *pTmp;//臨時結點指標
	if(EmptyQueue(pQueue))
	{
		printf("佇列為空\n");
		return ERROR;
	}
	pTmp=pQueue->front->next;//佇列第一個結點
	while(pTmp!=NULL)
	{
		printf(">[到達時刻：第%d分鐘，服務時長：%d分鐘]\n",pTmp->arriveTime,pTmp->duration);
		pTmp=pTmp->next;
	}
	printf("\n");
	return OK;
}

3.主要業務功能
1）定義全域變數

#define MAXSIZE 20//銀行服務視窗最大數量
int gWindowsNum;//銀行服務視窗數
int gCustomerNum;//客戶總人數
int gTotalTime;//總服務時間
int gCloseTime;//銀行關閉時間
EventList gEventList;//事件串列
Event gEvent;//事件
LinkedQueue gQueue[MAXSIZE];//佇列陣列
QElemType gCustomer;//佇列結點

2）初始化資料

void Initialize( )//初始化資料
{
	int i;
	gTotalTime=0;
	gCustomerNum=0;
	InitList(&gEventList);//初始化事件串列
	printf("請輸入銀行服務視窗個數(1~20):");//服務視窗個數
	scanf("%d",&gWindowsNum);
	while (gWindowsNum<1 || gWindowsNum>MAXSIZE)
	{
		printf("請輸入1到%d之間的整數：",MAXSIZE);
		scanf("%d",&gWindowsNum);
	}
	printf("\n請輸入服務關閉時間（超過這個時間就不在接納新顧客）（單位：分鐘）：");//服務關閉時間
	scanf("%d",&gCloseTime);
	while(gCloseTime<1)
	{
		printf("請輸入大于零的整數:");
		scanf("%d",&gCloseTime);
	}
	for(i=0;i<gWindowsNum;i++)//為每個視窗建立一個空佇列
	{
		InitQueue(&gQueue[i]);
	}
}

3）處理客戶到達事件

int ShortestQueue( );

void CustomerArrived()//處理客戶到達事件
{
	QElemType sQElem;
	Event sEvent;
	int index;//排隊人數最少的視窗編號
	int arrivetime;//客戶到達時間
	int duration;//業務辦理時間
	printf("當前時刻：第%d分鐘\n", gEvent.occurTime);//顧客到達的時間，在上一位顧客之后1~5分鐘
	arrivetime = gEvent.occurTime+ rand() % 5 + 1;
	duration = rand() % 21 + 10;//辦理業務時間為10~30分鐘
	if (arrivetime < gCloseTime)//服務尚未關閉
	{
		gCustomerNum++;//新顧客到達事件
		sEvent.occurTime = arrivetime;
		sEvent.type = 0;
		OrderInsert(gEventList, sEvent);//顧客進入人數最少的視窗排隊
		sQElem.arriveTime = gEvent.occurTime;//入隊時刻
		sQElem.duration = duration;//辦理業務時間
		index = ShortestQueue();
		EnQueue(&gQueue[index], sQElem);//入列
        //如果恰好排在了隊首，預定離開事件
		if (QueueLength(&gQueue[index]) == 1)
		{
			//記錄顧客從第index+1號號視窗離開（因為索引從0開始）
			sEvent.occurTime =gEvent.occurTime + duration;
			sEvent.type = index + 1;
			OrderInsert(gEventList, sEvent);
		}
	}
	else//銀行排隊服務關閉，不再接受新客戶
		printf("\n排隊服務以關閉，不再接受新客戶！\n");
}

4）處理顧客離開事件

void CustomerLeaved( )//處理顧客離開事件
{
	Event sEvent;
	int index=gEvent.type-1;//佇列編號為視窗編號-1
	DelQueue(&gQueue[index],&gCustomer);//洗掉隊首結點
	printf("\n顧客離開時間：第%d分鐘，",gEvent.occurTime);
	gTotalTime+=gCustomer.duration;//記錄服務時間
	//如果佇列不為空，則預定下一位顧客從第index+1號視窗離開
	if(!EmptyQueue(&gQueue[index]))
	{
		GetHead(&gQueue[index],&gCustomer);//獲得下一位顧客
		//記錄離開事件
		sEvent.occurTime=gEvent.occurTime+gCustomer.duration;
		sEvent.type=index+1;
		OrderInsert(gEventList,sEvent);
	}
}

5）獲取最短佇列的編號

int ShortestQueue( )//獲取最短佇列的編號
{
	int i=0;
	int min=9999;//最短佇列的長度
	int index=-1;//最短佇列的編號
	int length=0;
	//遍歷各個視窗，比較哪個視窗排隊的人最少
	for(i=0;i<gWindowsNum;i++)
	{
		length=QueueLength(&gQueue[i]);
		if(min>length)
		{
			min=length;
			index=i;
		}
	}
	return index;
}

6）顯示當前視窗佇列

void PrintQueue( )//顯示當前視窗佇列
{
	int i;
	printf("\n視窗排隊狀態：\n");
	for(i=0;i<gWindowsNum;i++)
	{
		printf("%d號視窗：\n",i+1);
		QueueTraverse(&gQueue[i]);
	}
	printf("\n");
}

7）顯示當前時間表

void PrintEventList( )//顯示當前時間表
{
	printf("\n事件表狀態：\n");
	ListTraverse(gEventList);
}

8）銀行排隊模擬

void BankSimulation( )//銀行排隊模擬
{
	//亂數發生器，用于模擬隨機客戶排隊事件
	//根據當前系統時間初始化隨機種子
	srand( (unsigned)time(NULL));
	//準備開業
	Initialize( );
	//第一個顧客到來
	gEvent.occurTime=0;
	gEvent.type=0;
	OrderInsert(gEventList,gEvent);
	//處理排隊串列
	while(!EmptyList(gEventList))
	{
		DelFirst(gEventList,&gEvent);
		//處理顧客事件
		if(gEvent.type==0)
			CustomerArrived( );
		else
			CustomerLeaved( );
		//顯示當前事件串列，以及排隊情況
		PrintEventList( );
		PrintQueue( );
		//暫停一會，便于觀察輸出內容
		system("PAUSE");
		printf("\n");
	}
	//平均服務時間
	printf("\n");
	printf("客戶平均服務時間：%f分鐘\n",(float)gTotalTime/gCustomerNum);
	system("PAUSE");
}

4.主函式入口

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<time.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
int main( )//主函式入口
{
	BankSimulation( );
	return 0;
}

5.程式運行截圖


**~~本 蒟蒻 發布的第一篇文章，貼代碼不易，復制后別忘了 點贊哦 （@W@）！,蟹蟹啦！*