数据结构队列---优先级队列-白红宇

数据结构队列---优先级队列

阅读量：3575 次

发布时间：2019-05-20

本文共 3113 字，大约阅读时间需要 10 分钟。

优先级队列（priorityqueue）是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有（1）查找（2）插入一个

（3）删除一般情况下，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。

优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。队列下方的数组用二叉树来处理.

AfxStd.h

#pragma once#ifndef AFXSTD_H#define AFXSTD_H#include
   
    #include
    
     #include
     
      #endif // !AFXSTD_H

heap.h

#pragma once#include"AfxStd.h"#ifndef HEAP_H#define HEAP_Hvoid MeakHeap(int *arr, int length);void AdjustHeap_Down(int *arr, int start, int end);void AdjustHeap_Up(int *arr, int start);#endif // !HEAP_H

PerioryQueue.h

#pragma once#include"heap.h"#ifndef PERIORYQUEUE_H#define PERIORYQUEUE_Htypedef int ElemType;const int size = 20;typedef struct  PriorityQueue{	int capacity;	int cursize;	ElemType *elements;}*PriQueue;void InitQueue(PriorityQueue &p);void DestoryQueue(PriorityQueue &p);void ClearQueue(PriorityQueue &p);bool EmptyQueue(PriorityQueue &p);bool FullQueue(PriorityQueue &p);bool InsertQueue_Arr(PriorityQueue &p,ElemType *e,int length);bool EnQueue(PriorityQueue &p,ElemType e);bool DeQueue(PriorityQueue &p,ElemType &temp);ElemType GetFront(PriorityQueue &p);#endif // !PERIORYQUEUE_H

heap.cpp

#include"heap.h"/*制堆函数,将给定的数组变成最小堆*/void MeakHeap(int *arr, int length){	if (arr == NULL)	{		return;	}	for (int i = (length -1)/2; i >= 0; i--)/*从第一个非叶子节点从下至上,从右至左调整结构*/	{				AdjustHeap_Down(arr, i, length - 1);  /*调整函数中传入了数组,起始坐标,末尾坐标*/	}}//AdjustHeap_Down,向下调整函数.作用是将数组转化为逻辑上的大堆,//从而方便升序排序,如果要降序排序,该制堆函数将数组转化为小堆即可.void AdjustHeap_Down(int *arr, int start, int end){	int i = start;	int j = 2 * i + 1;	int temp = arr[i];	while (j <= end)	{		if (j + 1 <= end && arr[j]
   
    temp)		{			arr[i] = arr[j];			i = j;			j = 2 * i + 1;		}		else		{			break;		}	}	arr[i] = temp;}//Up,向下调整函数.作用是向上回溯使其符合小堆,也可稍作修使其符合大堆.void AdjustHeap_Up(int *arr, int start){	int i = start;	int j = (start-1)/2;	int temp = arr[i];	while (j >=0)	{				if (arr[j]>temp)		{			arr[i] = arr[j];			i = j;			j = (j - 1) / 2;		}		else		{			break;		}	}	arr[i] = temp;}

PerioryQueue.cpp

#include"PerioryQueue.h"/*初始化队列*/void InitQueue(PriorityQueue &p){	p.elements = (ElemType *)malloc(sizeof(ElemType)*size);	p.cursize = 0;	p.capacity = 20;}/*摧毁队列*/void DestoryQueue(PriorityQueue &p){	free(p.elements);	p.cursize = p.capacity = 0;}/*清空队列*/void ClearQueue(PriorityQueue &p){	p.cursize = 0;}/*判空*/bool EmptyQueue(PriorityQueue &p){	return p.cursize == 0;}/*判满*/bool FullQueue(PriorityQueue &p){	return p.cursize == p.capacity;}/*将一个长度为length的数组入队*/bool InsertQueue_Arr(PriorityQueue &p,ElemType *e,int length){	if (p.cursize + length > p.capacity)	{		return false;	}		for (int i=0;i
   
     1) {		p.elements[0] = p.elements[p.cursize - 1];	}	p.cursize--;	AdjustHeap_Down(p.elements,0, p.cursize - 1);	return true;}/*取得队首元素*/ElemType GetFront(PriorityQueue &p){	return p.elements[0];}

main.cpp

#include"PerioryQueue.h"int main(){	int  arr[] = { 8,18,12,34,90,56,45,78 };		PriorityQueue p;	InitQueue(p);	EnQueue(p,2);	EnQueue(p,3);	InsertQueue_Arr(p,arr,8);	   int temp;	   int n = p.cursize;	   for (int i = 0; i < n; i++)	   {		   DeQueue(p,temp);		   printf("%d\t",temp);	   }	return 0;}

转载地址：http://ynxgj.baihongyu.com/

你可能感兴趣的文章