滴水逆向联盟

标题: VC++2012编程演练数据结构《6》优先级队列演练 [打印本页]

作者: 大灰狼 时间: 2014-9-15 08:32
标题: VC++2012编程演练数据结构《6》优先级队列演练
如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了优先级队列这种数据结构。优先级队列（priority queue）是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有（1）查找（2）插入一个新元素（3）删除一般情况下，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。
　　优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有
　　1) 查找;
　　2) 插入一个新元素;
　　3) 删除.
　　在最小优先队列(min priorityq u e u e)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.优先权队列中的元素可以有相同的优先权,查找与删除操作可根据任意优先权进行.
　　最大优先权队列的抽象数据类型描述如ADT 9-1所示,最小优先队列的抽象数据类型描述与之类似,只需将最大改为最小即可.
　　ADT 最大优先队列的抽象数据类型描述抽象数据类型
　　M a x P r i o r i t y Q u e u e
　有限的元素集合,每个元素都有一个优先权
　　操作
　　Create ( ):创建一个空的优先队列
　　Size ( ):返回队列中的元素数目
　　Max ( ):返回具有最大优先权的元素
　　I n s e rt (x):将x插入队列
　　DeleteMax (x):从队列中删除具有最大优先权的元素,并将该元素返回至x
　　}
　　优先队列插入和删除元素的复杂度都是O(lgn)，所以很快。
　　另一种描述方法是采用有序线性表,当元素按递增次序排列,使用链表时则按递减次序排列,这两种描述方法的删除时间均为( 1 ),插入操作所需时间为(n).
　　例：
　　假设我们对机器服务进行收费.每个用户每次使用机器所付费用都是相同的,但每个
　　用户所需要服务时间都不同.为获得最大利润,假设只要有用户机器就不会空闲,我们可以把
　　等待使用该机器的用户组织成一个最小优先队列,优先权即为用户所需服务时间.当一个新的
　　用户需要使用机器时,将他/她的请求加入优先队列.一旦机器可用,则为需要最少服务时间
　　(即具有最高优先权)的用户提供服务.
　　如果每个用户所需时间相同,但用户愿意支付的费用不同,则可以用支付费用作为优先权,

　　一旦机器可用,所交费用最多的用户可最先得到服务,这时就要选择最大优先队列.

打开IDE

我们基于VC++2012创建一个工程

优先队列头文件实现如下

[cpp] view plaincopy

#if !defined(AFX_SQPQUEUE_H__0E52A62B_D94A_4F11_9215_B39D8FE5BD34__INCLUDED_)
#define AFX_SQPQUEUE_H__0E52A62B_D94A_4F11_9215_B39D8FE5BD34__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include<fstream.h>
#define MaxSize 6
typedef struct Datatype
{int taskNo;
int priority;
}datatype;
class SqPqueue
{private:
datatype data[MaxSize];
int count;
public:
//构造函数
SqPqueue(){count=0;}
//析构函数
~SqPqueue(){}
//清空队列
void ClearPq(){count=0;}
// 判断队空
int PQueueEmpty();
// 判断队满
int PQueuefull();
//重载关系运算符小于<
friend int operator <(datatype &,datatype &);
// 队列的插入
void InsertPQ(datatype);
// 队列的删除
datatype DeQueue();
// 取队列的头元素
datatype PQueuefront();
//求队列的元素个数
int PQueueSize();
};
#endif // !defined(AFX_SQPQUEUE_H__0E52A62B_D94A_4F11_9215_B39D8FE5BD34__INCLUDED_)

优先队列类文件实现如下

[cpp] view plaincopy

#include "stdafx.h"
#include "SqPqueue.h"
//顺序优先级队列的实现
#include "SqPQueue.h"
// 判断队空
int SqPqueue::PQueueEmpty() {
return count==0;}
// 判断队满
int SqPqueue::PQueuefull(){
return count==MaxSize;}
//重载关系运算符小于<
int operator <(datatype &b,datatype &c)
{return b.priority<c.priority;}
//队列的插入
void SqPqueue::InsertPQ(datatype x)
{if(PQueuefull())
{cerr<<"队列满.\n";exit(1);}
data[count]=x;
count++;
}
//队列的删除
datatype SqPqueue::DeQueue()
{if(PQueueEmpty())
{cerr<<"队列空.\n";exit(1);}
datatype min=data[0];
int minindex=0;
for(int i=0;i<count;i++)
if(data<min)
{min=data;minindex=i;}
data[minindex]=data[count-1];
count--;
return min;
}
// 取队列的头元素
datatype SqPqueue::PQueuefront()
{if(PQueueEmpty())
{cerr<<"队列空.\n";exit(1);}
datatype min=data[0];
for(int i=1;i<count;i++)
if(data<min)
min=data;
return min;
}
//求队列的元素个数
int SqPqueue::PQueueSize()
{return count;}

插入下列类的操作代码

[cpp] view plaincopy

#include "stdafx.h"

#include "SqPQueue.h"
void main()
{
cout<<"SqPQueuem.cpp运行结果:\n";
SqPqueue MyQueue;
datatype task;
int i,m;
cout<<"输入产生随机数的种子数m:";cin>>m;
srand(m);
cout<<"生成顺序优先级队列MyQueue:\n";
for(i=0;i<MaxSize;i++)
{task.taskNo=i+1;
task.priority=rand()%10;
MyQueue.InsertPQ(task);}
cout<<"求顺序优先级队列MyQueue的长度:";
cout<<MyQueue.PQueueSize()<<endl;
cout<<"输出顺序优先级队列MyQueue:\n";
cout<<"序号任务号优先级\n";
i=1;
while(!MyQueue.PQueueEmpty())
{cout<<setw(2)<<i;
task=MyQueue.DeQueue();
cout<<setw(6)<<task.taskNo;
cout<<setw(7)<<task.priority<<endl;
i++;}
cin.get();
cin.get();
}

欢迎光临滴水逆向联盟 (http://www.dtdebug.com/) Powered by Discuz! X3.2