用无序循环单链表完成优先级队列抽象数据类型1405110002王一杰.doc

武汉轻工大学 数学与计算机学院 数据结构课程设计 设计题目：用无序循环单链表完成优先级队列抽象数据类型 专 业 计算机大类 班 级 计算机1404班 学 号 1405110002 姓 名 王一杰 指导教师 2015 年 12 月 31 日  数　据　结　构　实 验 报 告 成绩_____ 学号 1405110002 姓名 王一杰 授课教师 专业 计算机大类 实验报告递交日期 2015.1.5 实验题目 用无序循环单链表完成优先级队列抽象数据类型。 需求分析 程序的实现功能： 基本操作： （1）Make：构造空的优先级队列。 （2）Size：返回优先队列中元素个数。 （3）IsEmpty：如果优先级队列是否为空则返回真，否则返回假。 （4）Insert：插入一个数据元素到优先级队列。 （5）FindMax：查找、返回优先级最高的元素 （6）DeleteMax：删除、返回优先级最高的元素。 编写函数： 建立循环队列，返回尾指针函数 linkqueue *create( ) X入队，返回尾指针函数 linkqueue * enqueue(linkqueue *rear,int x) 出队返回队头元素函数 linkqueue * outqueue(linkqueue *rear) (4)显示队列元素函数 void list(linkqueue *rear) (5)删除队列函数 linkqueue * del(linkqueue *rear) (6)主函数完成功能： a). 调用 rear=creat( ) ; b). 调用 list(rear); c). 输入x值； d). 调用 enqueue(rear,x); e). 调用 list(rear); f). 调用 outqueue(rear) g).调用 list(rear); h) 调用 del(rear) i) list(rear). 2．从文件读入或随机产生作业的信息，作业的信息包括作业id（一个6字符字符串）、作业长度（一个表示秒数的int）、作业优先级。每一作业同样会被赋予一个到达编号（作业号）。该模拟程序应该输出作业id、作业优先级、作业长度以及完成时间（相对于从时间0开始的模拟程序而言的，可以设一个全局变量模拟）。 二. 主要算法的算法思想. 1．构造空的优先级队列. 2. 返回优先级队列中的元素个数. 3. 如果优先级队列为空则返回真，否则返回假。 4. 将队列重置为空. 5.插入一个数据元素到优先级队列. 6.查找、返回优先级最高的元素. 7.删除、返回优先级最高的元素. 三. 设计： 1．#include stdio.h #include stdlib.h #include malloc.h #include string.h typedef int Status; typedef struct{ unsigned int number; unsigned int priority; } job; typedef struct lnode{ job *data; struct lnode *next; } LNode, *LinkList; 2．参数表（列出所有的符号常量与全局变量） 参数名 数据传递方式 数据内容 传递 所属函数 NULL 符号常量 宏定义 0 所有函数 3.列出每个函数的函数声明、函数作用、函数值、形参内容与形式、主要算法步骤等 1)．构造空的优先级队列 Status Make(LinkList L) { if(L) return -1; L = (LNode*)malloc(sizeof(LNode)); L-data = NULL; L-next = L; return 0; } 2）．返回优先级队列中的元素个数。 Status Size(LinkList L) { int i; LNode* p; for(i=0,p=L; p-next!=L; p=p-next,i++); return i; } 3). 如果优先级队列为空则返回真，否则返回假。