seqpqueue2.h

C++版的数据结构源代码

struct DataType
{
	ElemType elem;						//数据元素
	int priority;						//优先级
};

class SeqPQueue
{
private:
	DataType data[MaxQueueSize];			//顺序队列数组
	int front;							//队头指示器
	int rear;							//队尾指示器
	int count;							//元素个数计数器
public:
	SeqPQueue(void)				  		//构造函数
		{front = rear = 0; count = 0;}; 
	~SeqPQueue(void){};  				//析构函数

	void Append(const DataType& item);	//入队列
	DataType Delete(void);       		//出队列
	DataType GetFront(void)const; 		//取优先级最高元素
	int NotEmpty(void)const  			//非空否
		{return count != 0;};
	DataType SPQDelete(void);
};

void SeqPQueue::Append(const DataType& item)	//入队列
//把数据元素item插入队列作为当前的新队尾
{
   if(count >= MaxQueueSize)
   {
      cout << "队列已满!" << endl;
	  exit(0);
   }

   data[rear] = item;						//把元素item加在队尾
   rear = rear + 1;							///队尾指示器加1
   count++;									//计数器加1
}

DataType SeqPQueue::Delete(void)			//出队列
//把优先级最高的元素出队列并由函数返回
//优先级相同时按先进先出的原则出队列
{
	if(count == 0)
	{
		cout << "队列已空!" << endl;
		exit(0);
	}

	DataType min = data[0];			//初始选data[0]为优先级最高的元素
	int minIndex = 0;				//minIndex为优先级最高元素的下标
	for(int i = 1; i < count; i++)	//寻找优先级最高的元素及对应下标
		if(data[i].priority < min.priority)
		{
			min = data[i];
			minIndex = i;
		}

	for(i = minIndex+1; i < count; i++)	//数据元素依次前移
		data[i-1] = data[i];

	count--;								//计数器减1
	return min;							//返回
}

DataType SeqPQueue::GetFront(void)const	//取优先级最高元素
//取优先级最高的元素并由函数返回
//优先级相同时按先进先出的原则取元素
{  
   if(count == 0)
   {
      cout << "队列空!" << endl;
	  exit(0);
   }

	DataType min = data[0];			//初始选data[0]为优先级最高的元素
	int minIndex = 0;				//minIndex为优先级最高元素的下标
	for(int i = 1; i < count; i++)	//寻找优先级最高的元素即对应下标
		if(data[i].priority < min.priority)
		{
			min = data[i];
			minIndex = i;
		}

	return min;							//返回
}

DataType SeqPQueue::SPQDelete(void)
{ 
	DataType x, min = data[0];		//初始选data[0]为优先级最高的元素
	int i, minIndex = 0;		//minIndex为优先级最高元素的下标
	if(count <= 0)
		exit(0);

	for(i = 1; i < count; i++)	//寻找优先级最高的元素及对应下标
		if(data[i] < min)
		{
			min = data[i];
			minIndex = i;
		}

	x = data[minIndex];

	//把最后一个元素放在被删除元素的位置
	data[minIndex] = data[count - 1];

	count--;							//数据元素个数减1
	return x;						
}