数据结构实验课：实验四、队列的实现及应用

一、实验目的 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 文件输入数据