1.优先队列的理解和概念
优先队列将数据按照优先级顺序排列。一个优先队列有许多有序的元素组成,所以可以快速的确定优先级最高的元素。
优先队列能通过多种方式来实现,最简单是用一个有序数据集(数组,链表),此时数据集中优先级最高的元素位于数据集的头部。但是每次插入或提取元素后,必须重新排序数据集,复杂度为n。更加有效的方法是由堆来实现,相同的操作复杂度为lg n。因此可以通过typedef struct Pueue Heap来实现优先队列。
2.具体实现
#include"Heap.h"
typedef Heap PQueue;
#define pqueue_init heap_init
#define pqueue_destroy heap_destroy
#define pqueue_insert heap_insert
#define pqueue_extract heap_extract
#define pqueue_peek(pqueue) ((pqueue)->tree == NULL ? NULL:(pqueue)->tree[0])
#define pqueue_size heap_size
3.包裹分拣函数的实现
一般来说,邮费越高越优先送达(相同路径下),此时邮费的高低也就是优先级的高低。
定义一个parcel的优先级队列来表示邮费的从高到低数据。
#include"Heap.h"
typedef Heap PQueue;
#define pqueue_init heap_init
#define pqueue_destroy heap_destroy
#define pqueue_insert heap_insert
#define pqueue_extract heap_extract
#define pqueue_peek(pqueue) ((pqueue)->tree == NULL ? NULL:(pqueue)->tree[0])
#define pqueue_size heap_size
//包裹分拣函数的实现
int get_parcel(PQueue *parcels, Parcel *parcel)
{
Parcel *data;
//如果没有包裹,则返回-1
if (pqueue_size(parcels) == 0)
return -1;
else
{
//如果未取到最大数据
if (pqueue_extract(parcels, (void **)*data) != 0)
return -1;
else
{
//取到最优先数据】
memcpy(parcel,data,sizeof(Parcel));
//取出的数据data,存在空间。之后不再使用时,应释放空间
free(data);
}
}
return 0;
}
int put_parcel(PQueue *parcels, const Parcel *parcel)
{
Parcel *data;
if ((data = (Parcel*)malloc(sizeof(Parcel))) == NULL)
{
return -1;
}
memcpy(data, parcel, sizeof(Parcel));
//将优先级数据插入到对应优先级队列中
if (pqueue_insert(parcels, data) != 0)
return -1;
return 0;
}