用无序循环单链表格完成优先级队列抽象大数据类型1405110002王一杰.docx
《用无序循环单链表格完成优先级队列抽象大数据类型1405110002王一杰.docx》由会员分享，可在线阅读，更多相关《用无序循环单链表格完成优先级队列抽象大数据类型1405110002王一杰.docx（14页珍藏版）》请在冰点文库上搜索。
用无序循环单链表格完成优先级队列抽象大数据类型1405110002王一杰
轻工大学
数学与计算机学院
数据结构课程设计
设计题目：
用无序循环单链表完成优先级队列抽象数据类型
专业计算机大类
班级计算机1404班
学号1405110002
姓名王一杰
指导教师
2015年12月31日
数 据 结 构 实验报告成绩_____
学号
1405110002
王一杰
授课教师
专业
计算机大类
实验报告递交日期
2015.1.5
实验题目
用无序循环单链表完成优先级队列抽象数据类型。
1．需求分析
1.程序的实现功能：
基本操作：
（1）Make：
构造空的优先级队列。
（2）Size：
返回优先队列中元素个数。
（3）IsEmpty：
如果优先级队列是否为空则返回真，否则返回假。
（4）Insert：
插入一个数据元素到优先级队列。
（5）FindMax：
查找、返回优先级最高的元素
（6）DeleteMax：
删除、返回优先级最高的元素。
编写函数：
（1）建立循环队列，返回尾指针函数linkqueue*create（）
（2）X入队，返回尾指针函数linkqueue*enqueue（linkqueue*rear,intx）
（3）出队返回队头元素函数linkqueue*outqueue（linkqueue*rear）
（4）显示队列元素函数voidlist（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
#include
#include
#include
typedefintStatus;
typedefstruct{
unsignedintnumber;
unsignedintpriority;
}job;
typedefstructlnode{
job*data;
structlnode*next;
}LNode,*LinkList;
2．参数表（列出所有的符号常量与全局变量）
参数名
数据传递方式
数据容
传递
所属函数
NULL
符号常量
宏定义
0
所有函数
3.列出每个函数的函数声明、函数作用、函数值、形参容与形式、主要算法步骤等
1）．构造空的优先级队列
StatusMake（LinkList&L）
{
if（L）return-1;
L=（LNode*）malloc（sizeof（LNode））;
L->data=NULL;
L->next=L;
return0;
}
2）．返回优先级队列中的元素个数。
StatusSize（LinkListL）
{
inti;
LNode*p;
for（i=0,p=L;p->next!
=L;p=p->next,i++）;
returni;
}
3）.如果优先级队列为空则返回真，否则返回假。
StatusIsEmpty（LinkListL）
{
return（L->next==L）;
}
4）.将队列重置为空。
voidClear（LinkListL）
{
LNode*p,*ptmp;
for（p=L->next;p!
=L;）
{
ptmp=p;
p=p->next;
free（ptmp->data）;
free（ptmp）;
}
L->next=L;
}
5）．//插入一个数据元素到优先级队列。
StatusInsert（LinkListL,job*data）
{
LNode*ptmp;
ptmp=（LNode*）malloc（sizeof（LNode））;
if（!
ptmp）return-2;
ptmp->data=（job*）malloc（sizeof（job））;
if（!
ptmp->data）{free（ptmp）;return-2;}
memcpy（ptmp->data,data,sizeof（job））;
ptmp->next=L->next;
L->next=ptmp;
return0;
}
6）.查找、返回优先级最高的元素。
job*FindMax（LinkListL）
{
LNode*p;
p=L->next;
if（p==L）returnNULL;
LNode*p0;
for（p0=p;p0!
=L;p0=p0->next）
if（p0->data->prioritydata->priority||p0->data->priority==p->data->priority&&p0->data->numberdata->number）
p=p0;
returnp->data;
}
7）.//删除、返回优先级最高的元素。
job*DeleteMax（LinkListL）
{
LNode*p;
job*pD;
p=L->next;
if（p==L）returnNULL;
LNode*p0;
LNode*p1;
for（p1=p0=L;p0->next!
=L;p0=p0->next）
if（p0->next->data->prioritydata->priority||p0->next->data->priority==p->data->priority&&p0->next->data->numberdata->number）
{p=p0->next;p1=p0;}
p1->next=p1->next->next;
pD=p->data;
free（p）;
returnpD;
}
四.调试分析：
1．调试中出现的问题，解决的办法
1）没有把头结点表示出来，不知道把最高优先级怎么表示。
2）．写list函数时，没有注意到循环队列，陷入死循环。
2．每个函数的时、空复杂性分析
1）．linkqueue*create（）建单链表函数
T（n）=O（n），S（n）=O（n）;
2）．linkqueue*enqueue（linkqueue*rear,intx）输出队列函数
T（n）=O
（1）,S（n）=O
（1）;
3）.linkqueue*outqueue（linkqueue*rear）入队函数
T（n）=O
（1）,S（n）=O
（1）;
4）.voidlist（linkqueue*rear）出队函数
T（n）=O（n）,S（n）=O
（1）;
5）.linkqueue*del（linkqueue*rear）删除队列
T（n）=O
（1）,S（n）=O
（1）;
6）.Intmain（）主函数
T（n）=O（n），S（n）=O（n）.
3．改进设想，经验体会
在优先级队列中无法找出最高优先级。
五.使用说明：
如何使用你编制的程序、操作步骤.
输入R---删除，取出优先级最高的作业并从队列中删除之
输入A---添加新作业
输入L---列举全部作业
输入Q---退出
六.测试结果：
输入输出数据容：
窗口显示如下：
（下划线部分为输入部分，其余为输出部分）
测试数据固定输出：
用无序循环单链表完成优先级队列抽象数据类型
王一杰
班级计算机大类1404班
学号1405110002
日期2015年12月30日
输入R:
输入A：
输入Q:
输入L:
7．源代码：
#include
#include
#include
#include
typedefintStatus;
typedefstruct{
unsignedintnumber;
unsignedintpriority;
}job;
typedefstructlnode{
job*data;
structlnode*next;
}LNode,*LinkList;
//构造空的优先级队列。
StatusMake（LinkList&L）
{
if（L）return-1;
L=（LNode*）malloc（sizeof（LNode））;
L->data=NULL;
L->next=L;
return0;
}
//返回优先级队列中的元素个数。
StatusSize（LinkListL）
{
inti;
LNode*p;
for（i=0,p=L;p->next!
=L;p=p->next,i++）;
returni;
}
//如果优先级队列为空则返回真，否则返回假。
StatusIsEmpty（LinkListL）
{
return（L->next==L）;
}
//将队列重置为空。
voidClear（LinkListL）
{
LNode*p,*ptmp;
for（p=L->next;p!
=L;）
{
ptmp=p;
p=p->next;
free（ptmp->data）;
free（ptmp）;
}
L->next=L;
}
//插入一个数据元素到优先级队列。
StatusInsert（LinkListL,job*data）
{
LNode*ptmp;
ptmp=（LNode*）malloc（sizeof（LNode））;
if（!
ptmp）return-2;
ptmp->data=（job*）malloc（sizeof（job））;
if（!
ptmp->data）{free（ptmp）;return-2;}
memcpy（ptmp->data,data,sizeof（job））;
ptmp->next=L->next;
L->next=ptmp;
return0;
}
//查找、返回优先级最高的元素。
job*FindMax（LinkListL）
{
LNode*p;
p=L->next;
if（p==L）returnNULL;
LNode*p0;
for（p0=p;p0!
=L;p0=p0->next）
if（p0->data->prioritydata->priority||p0->data->priority==p->data->priority&&p0->data->numberdata->number）
p=p0;
returnp->data;
}
//删除、返回优先级最高的元素。
job*DeleteMax（LinkListL）
{
LNode*p;
job*pD;
p=L->next;
if（p==L）returnNULL;
LNode*p0;
LNode*p1;
for（p1=p0=L;p0->next!
=L;p0=p0->next）
if（p0->next->data->prioritydata->priority||p0->next->data->priority==p->data->priority&&p0->next->data->numberdata->number）
{p=p0->next;p1=p0;}
p1->next=p1->next->next;
pD=p->data;
free（p）;
returnpD;
}
intmain（）
{
constchar*prtstr="----------------------";
job*pfindData,*premoveData,tmpData;
LNode*ptmp;
intSerialNum=0;
intc;
LinkListpHead=NULL;
pfindData=premoveData=NULL;
Make（pHead）;
while
（1）
{
system（"cls"）;
printf（"用无序循环单链表完成优先级队列抽象数据类型\n"）;
printf（"王一杰\n"）;
printf（"班级计算机大类1404班\n"）;
printf（"学号1405110002\n"）;
printf（"日期2015年12月31日\n"）;
printf（"%s选择菜单%s",prtstr,prtstr）;
printf（"\n\tR---删除，取出优先级最高的作业并从队列中删除之\n\tA---添加新作业\n\tL---列举全部作业\n\tQ---退出\n"）;
if（premoveData）
{
printf（"\n\t\t最近取出的作业号:
%06d",premoveData->number）;
}
else
{
printf（"\n\n\n"）;
}
printf（"请选择操作菜单:
"）;
fflush（stdin）;
c=getchar（）;
if（c>='a'&&c<='z'）c-=（'a'-'A'）;
if（c!
='R'&&c!
='A'&&c!
='L'&&c!
='Q'）continue;
fflush（stdin）;
switch（c）
{
case'R':
if（premoveData）free（premoveData）;
premoveData=DeleteMax（pHead）;
continue;
case'A':
memset（&tmpData,0,sizeof（tmpData））;
printf（"增加新作业:
\n请输入作业优先级:
"）;scanf（"%d",&tmpData.priority）;
fflush（stdin）;
tmpData.number=++SerialNum;
if（!
Insert（pHead,&tmpData））printf（"插入成功\n"）;
elseprintf（"插入失败\n"）;
break;
case'L':
printf（"全部作业队列:
\n"）;
if（IsEmpty（pHead））
printf（"当前作业队列为空\n"）;
for（ptmp=pHead->next;ptmp!
=pHead;ptmp=ptmp->next）
printf（"\n作业号:
%06d优先级:
%d",ptmp->data->number,ptmp->data->priority）;
break;
case'Q':
Clear（pHead）;free（pHead）;
if（premoveData）free（premoveData）;
printf（"Byebye"）;
exit（0）;
}
printf（"\n按回车键继续......"）;
fflush（stdin）;
getchar（）;
}
return0;
}
源代码共106行
升级会员 