基于数组二叉堆实现的优先队,C语言实现(参考
http://www.jb51.net/article/41978.htm大神的代码)。在VC6.0上运行没问题,想移植到keil C中,可其中一个变量总是不对。求指导。
/*
*File: pq.h
*purpose: declara
tion of priority queue in C
*/
#ifndef _PRIORITY_QUEUE_H
#define _PRIORITY_QUEUE_H
// =============KeyValue Struct==================================
typedef struct key_value_struct KeyValue;
struct key_value_struct
{
int _key;
unsigned int _value;
};
KeyValue *key_value_new(int key, unsigned int value);
void key_value_free(KeyValue *kv, void (*freevalue)(void *));
// =============PriorityQueue Struct==============================
#define PRIORITY_MAX 1
#define PRIORITY_MIN 2
typedef struct priority_queue_struct PriorityQueue;
struct priority_queue_struct
{
KeyValue **_nodes;
int _size;
int _capacity;
int _priority;
};
PriorityQueue *priority_queue_new(int priority);
#endif
/*
*File:pq.c
*purpose: definition of priority queue in C
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pq.h"
//Private Functions
static void priority_queue_realloc(PriorityQueue *pq);
static void priority_queue_adjust_tail(PriorityQueue *pq);
static int priority_queue_compare(PriorityQueue *pq, int pos1, int pos2);
static void priority_queue_swap(KeyValue **nodes, int pos1,int pos2);
//Functions of KeyValue Struct
KeyValue *key_value_new(int key,unsigned int value)
{
KeyValue *pkv = (KeyValue *)malloc(sizeof(KeyValue));
pkv->_key = key;
pkv->_value = value;
return pkv;
}
//Functions of PriorityQueue Struct
PriorityQueue *priority_queue_new(int priority)
{
PriorityQueue *pq = (PriorityQueue *)malloc(sizeof(PriorityQueue));
pq->_capacity = 11; //default initial value
pq->_size = 0;
pq->_priority = priority;
pq->_nodes = (KeyValue **)malloc(sizeof(KeyValue *) * pq->_capacity);
return pq;
}
const KeyValue *priority_queue_top(PriorityQueue *pq)
{
if(pq->_size > 0)
return pq->_nodes[0];
return NULL;
}
void priority_queue_enqueue(PriorityQueue *pq, KeyValue *kv)
{
pq->_nodes[pq->_size] = kv;
priority_queue_adjust_tail(pq);
if(pq->_size >= pq->_capacity)
priority_queue_realloc(pq);
}
int priority_queue_size(PriorityQueue *pq)
{
return pq->_size;
}
int priority_queue_empty(PriorityQueue *pq)
{
return pq->_size <= 0;
}
static void priority_queue_realloc(PriorityQueue *pq)
{
pq->_capacity = pq->_capacity * 2;
pq->_nodes = realloc(pq->_nodes, sizeof(KeyValue *) * pq->_capacity);
}
static void priority_queue_adjust_tail(PriorityQueue *pq)
{
int i, parent, child;
i = pq->_size - 1;
pq->_size++;
while(i > 0)
{
child = i;
parent = (child - 1) / 2;
if(priority_queue_compare(pq, parent, child) > 0)
{
priority_queue_swap(pq->_nodes, child, parent);
i = parent;
}
else
break;
}
}
static int priority_queue_compare(PriorityQueue *pq,
int pos1,
int pos2)
{
int adjust = -1;
int r = pq->_nodes[pos1]->_key - pq->_nodes[pos2]->_key;
if(pq->_priority == PRIORITY_MAX)
r *= adjust;
return r;
}
static void priority_queue_swap(KeyValue **nodes,
int pos1,
int pos2)
{
KeyValue *temp = nodes[pos1];
nodes[pos1] = nodes[pos2];
nodes[pos2] = temp;
}
-
-
一周热门 更多>