数据结构与算法——看病排队候诊问题.doc

看病排队候诊问题

1. 问题描述
医院各科室的医生有限，因此病人到医院看病时必须排队候诊，而病人病情有轻重之分，不能简单地根据先来先服务的原则进行治疗，所以医院根据病人的病情规定了不同的优先级别。医生在诊断治疗时，总是优先选择级别高的病人进行诊治，如果遇到两个级别相同的病人，则选择先来的病人进行诊治。

2. 设计要求
用队列模拟上述看病排队候诊问题，建立两个队列分别对应两个不同的优先级别，按照从终端读入输入数据的方式进行模拟管理。输入1，表示有新的病人加入队列候诊，根据病情指定其优先级别；输入2，表示医生根据优先级别为病人进行诊治；输入3，表示退出系统。

3. 数据结构
解决看病排队候诊问题的数据结构，可以采用链式队列来实现。

4. 分析与实现
根据设计要求，定义两个队列q1和q2，q1对应优先级别低的队列，q2对应优先级别高的队列。当有新的病人要加入队列候诊是，根据用户从键盘终端输入的优先级别，将该病人加入相应的队列中，并同时生成一个对应病人的id编号，需要说明的是，该id编号是按照病人到达医院进行排队的先后顺序依次生成的。医生根据优先级别选择病人进行诊治，因此程序应该首先查看优先级别最高的队列q2，若队列q2不为空，则对队列q2进行出队操作，否则对应队列q1执行出队操作。
(1) MyEnQueue() ：带有优先级别的队列的入队操作。程序先根据用户从键盘输入的数据来制定病人候诊的优先级别，然后进行入队操作；
(2) MyDeQueue() ：用来模拟医生根据病人的病情选择优先级别高的病人进行诊断治疗过程的出队操作。程序首先判断优先级别高的队列q2是否为空，不为空表示有病情严重的病人在候诊，医生优先诊断该病人，将队列q2中的对头元素出队，否则诊断排在队列q1中队头的病人。如果两个队列均为空，则表示没有候诊病人，返回-1。

5. 源代码
#include <stdio.h>
#include <stdlib.h>

typedef int DataType;
typedef struct qnode
{
DataType data; //data存放病人id
struct qnode *next; //next存放下一个病人id地址
} LinkList;
typedef struct
{
LinkList *front, *rear;
} LinkQueue;

void InQueue(LinkQueue *q,DataType i)
{
LinkList *p;
p=(LinkList *)malloc(sizeof(LinkList));
if(p==NULL)
printf("分配内存失败！\n");
else
{
p->data=i;
p->next=NULL;
q->rear->next=p;
q->rear=p;
}
}

LinkQueue *InitQueue()
{
LinkQueue *q;
LinkList *p;
p=(LinkList *)malloc(sizeof(LinkList));
q=(LinkQueue *)malloc(sizeof(LinkQueue));
p->next=NULL;
q->front=p;
q->rear=q->front;
return q;
}

int EmptyQueue(LinkQueue *q)
{
int r=0;
if(q->front==q->rear)
r=0;
else
r=1;
return r;
}

DataType OutQueue(LinkQueue *q)
{
LinkList *p;
DataType x;
if(q->front->next==q->rear)
{
q->front=q->rear;
x=q->rear->data;
}
else
{
p=q->front->next;
q->front->next=p->next;
x=p->data;
free(p);
}
return x;
}

void MyEnQueue(LinkQueue *q1,LinkQueue *q2,DataType d,int priority)
{
//重新定义带有优先级别的队列的入队操作
if(priority==1)
InQueue(q1,d);
else
InQueue(q2,d);
}

DataType MyDeQueue(LinkQueue *q1,LinkQueue *q2)
{
//重新定义带有优先权限的队列的出对操作
DataType e;
if(EmptyQueue(q2))
e=OutQueue(q2);
else if(EmptyQueue(q1))
e=OutQueue(q1);
else
e=-1;
return e;
}

void main()
{
LinkQueue *q1,*q2; //分别为级别低和高的病人队列
DataType idi=1,ido=-1; //分别为入队和出队病人的id
int menu,priority; //分别为用户选择的菜单编号和病人看病的优先级别
q1=InitQueue();
q2=InitQueue();
printf("****************************欢迎进入排队看病模拟系统****************************\n\n");
printf("****************************1：新的病人加入候诊队列 ****************************\n\n");
printf("*************************2：医生根据优先级别为病人诊治 *************************\n\n");
printf("*********************************3：退出系统************************************\n\n");
while(1)
{
printf("--------------------------------------------------------------------------------\n");
printf("**********************请按菜单编号选择相应的操作（整数）：**********************\n");
scanf("%d",&menu);
if(menu==1) //如果有新的病人则加入队列
{
printf("请输入病人的优先级别（1或2）：");
scanf("%d",&priority);
printf("该病人的id为：%d\n",idi);
MyEnQueue(q1,q2,idi,priority);
idi++;
}
else if(menu==2)
{
ido=MyDeQueue(q1,q2);
if(-1!=ido)
printf("当前被诊治的病人id为：%d\n",ido);
else
printf("无诊治病人，队列为空\n");
}
else if(menu==3)
break;
else
printf("输入错误，请按菜单编号输入\n");
}
}
6. 结果