实验四、队列的实现及应用
一、实验目的
1.掌握队列的存储表示和实现。
2.掌握队列的基本操作实现。
3.掌握队列在解决实际问题中的应用。
二、实验要求
利用队列模拟服务台前的排队现象问题。
问题描述：某银行有一个客户办理业务站，在单位时间内随机地有客户到达，设每位客户的业务办理时间是某个范围的随机值。设只有一个窗口，一位业务人员，要求程序模拟统计在设定时间内，业务人员的总空闲时间和客户的平均等待时间。假定模拟数据已按客户到达的先后顺序依次存于某个正文数据文件中，对应每位客户有两个数据：到达时间和需要办理业务的时间，文本文件内容如：10 20 23 10 45 5 55 10 58 15 65 10。
三、解题参考思路
与栈相对应，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。允许插入的一端称队尾，允许删除的一端称队头。插入与删除分别称为入队与出队。队列示意图如下图所示：
【数据描述】
typedef struct{ int arrive; int treat;//客户的信息结构 }QNODE； typedef struct node{ QNODE data; Struct node *next;//队列中的元素信息 }LNODE,*QueuePtr; typedef struct{ //链队列类型 QueuePtr front ; //队头指针 QueuePtr rear ; //队尾指针 } LinkQueue;
队列的基本操作如队列的初始化、判空、入队和出队等操作实现参考教材。
【算法描述】
{ 设置统计初值：业务员等待时间，客户总的待时间，客户总人数等
设置当前时钟clock时间为0；//用变量clock来模拟当前时间.
打开数据文件，准备读；
读入第一位客户信息于暂存变量中；//文件读操作have= fscanf(fp,"%d %d",&temp.arrive,&temp.treat);
do{//约定每轮循环，处理完一位客户
if(等待队列为空，并且还有客户)
{ //等待队列为空时
累计业务员总等待时间；
时钟推进到暂存变量中的客户的到达时间；//clock=temp.arrive
暂存变量中的客户信息进队；
读取下一位客户信息于暂存变量；
}
从等待队列出队一位客户；
累计客户人数；
将该客户的等待时间累计到客户的总等待时间；//=当前时间-客户到达时间
设定当前客户的业务办理结束时间；//=当前时间+客户办理业务所需时间
while(下一位客户的到达时间在当前客户处理结束之前，并且还有客户)
{
暂存变量中的客户信息进队；
读取下一位客户信息于暂存变量；
}
时钟推进到当前客户办理结束时间；
}while(还有未处理的客户)；//等待队列不为空或者还有客户（have==2）
计算统计结果，并输出；
附：文件操作：
char Fname[120];//读取文件的文件名 FILE*fp; if((fp=fopen(Fname,“r”))==NULL) { printf(“文件打开出错”); return 0; } have= fscanf(fp,"%d %d",&temp.arrive,&temp.treat);//have返回值等于从文件中一次读操作读出数据的个数，这里等于2.
四、实验任务
认真阅读与理解实验内容的具体要求，参考教材相关章节，结合实验内容的要求，编写实验程序并上机调试与测试，完成实验报告的撰写。
需要自己新建 text.txt 文件输入数据
#include <stdio.h> #include<stdlib.h> typedef struct{ int arrive; int treat;//客户的信息结构 }QNODE; typedef struct node{ QNODE data; struct node *next;//队列中的元素信息 }LNODE,*LNODEPtr; LNODE *front,*rear;// 队头指针和队尾指针 //======================================== //入队 void EnQueue(QNODE e) { LNODEPtr s=(LNODEPtr)malloc(sizeof(LNODE)); if(!s) // 存储分配失败 exit(0); s->data=e; s->next=NULL; rear->next=s; // 把拥有元素e的新结点s赋值给原队尾结点的后继 rear=s; // 把当前的s设置为队尾结点，rear指向s } //========================================= //出队 int DeQueue(QNODE *e) { LNODEPtr p; if(front==rear) return 0; *e=front->next->data; // 将欲删除的队头结点的值赋值给e p=front->next; // 将欲删除的队头结点暂存给p front->next=front->next->next; if(rear==p) // 若队头就是队尾，则删除后将rear指向头结点 rear=front; free(p); return 1; } //========================================== int main() { int waitsum1=0,waitsum2=0;//一为业务员等待时间。二为客户等待时间 int clock=0; int nubk=0;//用于积累客户人数 int have=0;//have用于判断是否有未处理的客户 非0为存在 0为不存在 QNODE temp,e; //建造空队列 front=rear=(LNODEPtr)malloc(sizeof(LNODE)); front->next=NULL;//防止指针乱指 FILE *fp=fopen("C:\\test.txt","r");//创建一个TXT文件并打入‘10 20 23 10 45 5 55 10 58 15 65 10’。 /*"要打开的文件路径以及文件命名","r" */ if(fp==NULL){ printf("文件打开失败"); return 0; } have= fscanf(fp,"%d %d",&temp.arrive,&temp.treat); do{ if( have==2 && front==rear )//等待队列为空并且还有客户 { waitsum1+=(temp.arrive-clock);//累计业务员总等待时间 clock=temp.arrive;// 时钟推进到暂存变量中的客户的到达时间 //入队 EnQueue(temp); have= fscanf(fp,"%d %d",&temp.arrive,&temp.treat); } nubk++;//积累客户人数+1 //出队 DeQueue(&e); waitsum2+=(clock-e.arrive); clock+=e.treat;//时间推进到客户结束时间 while(temp.arrive<=clock && have==2) //在上一个客户结束结束之前，若有到达的客户就入队 { //入队 EnQueue(temp); have= fscanf(fp,"%d %d",&temp.arrive,&temp.treat); } }while(have==2||front!=rear);//还有未处理的客户 printf("业务员等待时间为%d\n客户平均等待时间为%f",waitsum1,(float)waitsum2/(float)nubk); return 0; }
