《数据结构实验与实训教程（第4版）》程序代码(6)

int q_h=0, q_t=0; /* 初始化队首,队尾指针为0 */ int op, i;

while( 1 ) { printf( \请选择操作，1：进队 2：出队 0：退出 \ fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( \

switch( op ) {

case 0: /* 退出 */ return; case 1: /* 进队 */ printf( \请输入进队元素：\ scanf( \ if( 1 != 0 ) printf( \队列满\\n\ else {

printf( \入队成功, 队内元素为:\\n\ OutputQueue( q, MAXN, q_h, q_t ); } break; case 2: /* 出队 */ if( 2 == 0 ) {/* 出队成功 */ printf( \出队元素为: [%d] , 队内元素为:\\n\

OutputQueue( q, MAXN, q_h, q_t ); } else printf( \队空\\n\

break;

}

}

}

程序5：题5 医务室模拟程序 #include #include #include typedef struct { int arrive; /* 病人到达时间 */

int treat;

/* 病人处理时间 */

25

}PATIENT;

typedef struct queue { /* 定义队列结构 */ PATIENT data; /* 队列元素类型为int */ struct queue *link; }QUEUE;

void EnQueue( QUEUE **head, QUEUE **tail, PATIENT x ) /* 进队操作 */ { /*编写进队操作子程序*/ }

int DeQueue( QUEUE **head, QUEUE **tail, PATIENT *cp ) /* 出队操作 1:对空 */ {

/*编写出队操作子程序*/ }

void OutputQueue( QUEUE *head ) /* 输出队列中元素 */ { while( 1 ) { printf( \到达时间: [%d] 处理时间: [%d]\\n \head->data.arrive,

head->data.treat ); head = head->link; } }

void InitData( PATIENT *pa, int n ) /* 生成病人到达及处理时间的随机数列 */ {

int parr = 0; /* 前一个病人到达的时间 */ int i; for( i = 0; i < n; i++ ) { pa[i].arrive = parr + random( 15 ); /* 假设病人到达的时间间隔为 0~14 */ pa[i].treat = random( 9 ) + 1; /* 假设医生处理时间为 1~9 */ parr = pa[i].arrive;

printf( \第[%d]个病人到达时间为[%d]处理时间为[%d]\\n\ } }

void main()

26

{ QUEUE *head, *tail; PATIENT *p, curr; /* 病人到达及处理时间信息, 当前出队病人信息 */ int n, i, finish; int nowtime; /* 时钟 */ int dwait, pwait; /* 医生累计等待时间, 病人累计等待时间 */ head = tail = NULL; while( 1 ) {

/* 将队列头和尾置为空 */

n = 0;

nowtime = dwait = pwait = 0; printf( \请输入病人总数(1~20),= 0：退出 \ scanf( \ if( n == 0 ) /* 退出 */ return; if( n > 20 || n < 0 ) continue;

if( ( p = ( PATIENT *)malloc( n * sizeof( PATIENT ) ) ) == 2 ) { printf( \内存申请错误\\n\ return;

} 3 /* 生成病人到达及处理时间的随机数列 */ for( i = 0; 4 ; ) {/* 病人到达未结束或还有等待, 处理 */ if( head == NULL ) { /* 等待队列为空 */

if(p[i].arrive - nowtime > 0)/* 病人到达时间与上次处理时间迟 */ 5 /* 累计医生等待时间 */ nowtime = p[i].arrive; /* 时钟推进 */ 6 /* 病人入队 */

}

DeQueue( &head, &tail, &curr ); /* 出队一位病人 */ 7 /* 累计病人等待时间 */ finish = nowtime + curr.treat; /* 当前病人处理结束时间 */ while( i < n && p[i].arrive <= finish ) /* 下一位病人到达时间在当前病人等待时间结束之前, 入队 */ 8 nowtime = finish; /* 时钟推进到当前病人处理结束时间 */

}

free( p ); /* 释放空间 */ printf( \医生等待时间[%d], 病人平均等待时间[%.2f]\\n\dwait, (float)pwait/n );

27

}

}

程序6：题6 招聘程序 #include #include

#include #define DEMARK 5 /* 按第二批录用的扣分成绩 */ typedef struct stu { /* 定义招聘人员信息结构 */

int no, total, z[2], sortm, zi; /* 编号, 总成绩, 志愿, 排除成绩, 录取志愿号 */ struct stu *next; }STU;

typedef struct job{ int lmt, count; /* 计划录用人数, 已录用人数 */ STU *stu; /* 录用者有序队列 */ }JOB;

STU *head=NULL, *over=NULL;

int all;

void OutPutStu( STU *p ) /* 输出应聘人员有序队列中编号和成绩 */ { for( ; 1 ; p = p->next ) printf( \}

void FreeStu( STU **p ) { STU *q; while( *p != NULL ) { q = *p; 2 free( q ); }

}

void Insert( STU **p, STU *u ) {

/* 释放应聘人员空间 */

/* 按排除成绩从大到小顺序插队 */

STU *v, *q; /* 插队元素的前后元素指针 */ for( q = *p; q != NULL; v = q, q = q->next ) if( 3 ) /* 队中工人成绩<插入元素成绩 */ break;

28

if( q == *p ) /* 插入到队首 */ *p = u; else /* 不为队首插入 */ 4 u->next = q; /* 新元素的后继元素指针 */ }

int InitJob( JOB **h, int n, int *all ) /* 随机生成工种信息 */

{

int i;

JOB *p; *all = 0;

printf( \工种信息{工种号(计划招聘人数)}\\n\ if( ( p = ( JOB * )malloc( n * sizeof( JOB ) ) ) == NULL ) { printf( \内存申请错误!\\n\ return -1; } for( i = 0; i < n; i++ ) { p[i].lmt = random( 10 ) + 1; /* 假设工种招聘人数为 1~10 */ p[i].count = 0; p[i].stu = NULL; *all += p[i].lmt;

printf( \ } printf( \总招聘人数[%d]\\n\ *h = p;

return 0; }

int InitStu( STU **h, int n, int m ) /* 随机生成应聘人员信息 */ { STU *p; int i;

printf( \应聘人员信息{编号, 成绩, 志愿1, 志愿2}\\n\ for( i = 0; i < n; i++ ) { if( ( p = ( STU * )malloc( sizeof( STU ) ) ) == NULL ) { printf( \内存申请错误!\\n\ return -1; } p->no = i;

29