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

1、 武汉轻工大学数学与计算机学院数据结构课程设计设计题目：用无序循环单链表完成优先级队列抽象数据类型 专 业 计算机大类 班 级 计算机1404班 学 号 1405110002 姓 名 王一杰 指导教师 2015 年 12 月 31 日 数据结构实 验 报 告 成绩_学号1405110002姓名王一杰授课教师专业计算机大类实验报告递交日期2015.1.5实验题目用无序循环单链表完成优先级队列抽象数据类型。1 需求分析1. 程序的实现功能：基本操作：（1）Make：构造空的优先级队列。（2）Size：返回优先队列中元素个数。（3）IsEmpty：如果优先级队列是否为空则返回真，否则返回假。（4）I

2、nsert：插入一个数据元素到优先级队列。（5）FindMax：查找、返回优先级最高的元素（6）DeleteMax：删除、返回优先级最高的元素。编写函数：(1) 建立循环队列，返回尾指针函数 linkqueue *create( )(2) X入队，返回尾指针函数 linkqueue * enqueue(linkqueue *rear,int x)(3) 出队返回队头元素函数 linkqueue * outqueue(linkqueue *rear)(4)显示队列元素函数 void list(linkqueue *rear)(5)删除队列函数 linkqueue * del(linkqueue

3、*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、作业优先级、作业长度以及完成时间（相对于从

4、时间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 uns

5、igned 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);

6、 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). 如果优先级队列为空则返回真，否则返回假。 Status IsEmpty(LinkList L) return (L->next = L); 4). 将队列重置为空。void Clear(LinkList L) LNode* p,*ptmp; for(p=L->n

7、ext; p!=L ; ) ptmp = p; p = p->next; free(ptmp->data); free(ptmp); L->next = L; 5）/插入一个数据元素到优先级队列。Status Insert(LinkList L,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; memcp

8、y(ptmp->data,data,sizeof(job); ptmp->next = L->next; L->next=ptmp; return 0; 6）.查找、返回优先级最高的元素。job* FindMax(LinkList L) LNode* p; p=L->next; if(p=L) return NULL; LNode* p0; for(p0=p;p0!=L;p0=p0->next) if(p0->data->priority < p->data->priority | p0->data->priorit

9、y=p->data->priority&&p0->data->number<p->data->number) p = p0; return p->data; 7)./删除、返回优先级最高的元素。job* DeleteMax(LinkList L) LNode* p; job* pD; p = L->next; if(p=L) return NULL; LNode* p0; LNode* p1; for(p1=p0=L; p0->next!=L; p0=p0->next) if(p0->next->da

10、ta->priority < p->data->priority | p0->next->data->priority=p->data->priority&&p0->next->data->number<p->data->number) p = p0->next;p1=p0; p1->next = p1->next->next; pD = p->data; free(p); return pD; 四. 调试分析：1调试中出现的问题，解决的办法 1）没有把头结点

11、表示出来，不知道把最高优先级怎么表示。 2）写list函数时，没有注意到循环队列，陷入死循环。2每个函数的时、空复杂性分析 1）linkqueue * create()建单链表函数 T(n)=O(n)， S(n)=O(n); 2）linkqueue * enqueue(linkqueue *rear,int x) 输出队列函数 T(n)=O(1), S(n)=O(1); 3). linkqueue * outqueue(linkqueue *rear) 入队函数 T(n)=O(1) , S(n)=O(1); 4). void list(linkqueue *rear) 出队函数 T(n)=O(

12、n) , S(n)=O(1); 5).linkqueue * del(linkqueue *rear) 删除队列 T(n)=O(1) , S(n)=O(1); 6). Int main() 主函数 T(n)=O(n) ， S(n)=O(n).3改进设想，经验体会 在优先级队列中无法找出最高优先级。 五. 使用说明：如何使用你编制的程序、操作步骤. 输入R-删除，取出优先级最高的作业并从队列中删除之输入A-添加新作业输入L-列举全部作业输入Q-退出六. 测试结果：输入输出数据内容：窗口显示如下：(下划线部分为输入部分，其余为输出部分)测试数据固定输出：用无序循环单链表完成优先级队列抽象数据类型姓

13、名 王一杰班级 计算机大类1404班学号 1405110002日期 2015年12月30日输入R: 输入A： 输入Q: 输入L: 7 源代码：#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 *ne

14、xt; LNode, *LinkList; /构造空的优先级队列。Status Make(LinkList &L) if(L) return -1; L = (LNode*)malloc(sizeof(LNode); L->data = NULL; L->next = L; return 0;/返回优先级队列中的元素个数。Status Size(LinkList L) int i; LNode* p; for(i=0,p=L; p->next!=L; p=p->next,i+); return i;/如果优先级队列为空则返回真，否则返回假。Status IsEm

15、pty(LinkList L) return (L->next = L);/将队列重置为空。void Clear(LinkList L) LNode* p,*ptmp; for(p=L->next; p!=L ; ) ptmp = p; p = p->next; free(ptmp->data); free(ptmp); L->next = L;/插入一个数据元素到优先级队列。Status Insert(LinkList L,job *data) LNode *ptmp; ptmp = (LNode*)malloc(sizeof(LNode); if(!ptmp)

16、 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; return 0; /查找、返回优先级最高的元素。job* FindMax(LinkList L) LNode* p; p=L->next; if(p=L) return NULL; LNode* p0; for(p0=p;p0!=L;p0

17、=p0->next) if(p0->data->priority < p->data->priority | p0->data->priority=p->data->priority&&p0->data->number<p->data->number) p = p0; return p->data;/删除、返回优先级最高的元素。job* DeleteMax(LinkList L) LNode* p; job* pD; p = L->next; if(p=L) return NU

18、LL; LNode* p0; LNode* p1; for(p1=p0=L; p0->next!=L; p0=p0->next) if(p0->next->data->priority < p->data->priority | p0->next->data->priority=p->data->priority&&p0->next->data->number<p->data->number) p = p0->next;p1=p0; p1->next =

19、 p1->next->next; pD = p->data; free(p); return pD; int main() const char *prtstr = "-" job* pfindData,*premoveData,tmpData; LNode *ptmp; int SerialNum = 0; int c; LinkList pHead = NULL; pfindData = premoveData = NULL; Make(pHead); while(1) system("cls");printf(" 用无序

20、循环单链表完成优先级队列抽象数据类型 n");printf("姓名 王一杰n");printf("班级 计算机大类1404班n");printf("学号 1405110002n"); printf("日期 2015年12月31日n"); printf("%s 选择菜单 %s",prtstr,prtstr); printf("ntR-删除，取出优先级最高的作业并从队列中删除之ntA-添加新作业ntL-列举全部作业ntQ-退出n"); if(premoveData) p

21、rintf("ntt最近取出的作业号:%06d",premoveData->number); else printf("nnn"); 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(&tmpD