優先隊列(priority_queue)的C說話完成代碼。本站提示廣大學習愛好者：（優先隊列(priority_queue)的C說話完成代碼）文章只能為提供參考，不一定能成為您想要的結果。以下是優先隊列(priority_queue)的C說話完成代碼正文
優先隊列（priority_queue)和普通隊列(queue)的函數接口分歧，分歧的是，優先隊列每次出列的是全部隊列中最小（或許最年夜）的元素。
本文扼要引見一種基於數組二叉堆完成的優先隊列，界說的數據構造和完成的函數接口解釋以下：
1、鍵值對構造體：KeyValue
// =============KeyValue Struct==================================
typedef struct key_value_struct KeyValue;
struct key_value_struct
{
int _key;
void *_value;
};
KeyValue *key_value_new(int key, void *value);
void key_value_free(KeyValue *kv, void (*freevalue)(void *));
鍵值對作為優先隊列的中數據的保留情勢，個中key用於保留優先級，_value用於指向現實的數據。
key_value_new用於創立一個KeyValue構造體；key_value_free用於釋放一個KeyValue構造體的內存，
參數freevalue用於釋放數據指針_value指向的內存。
2、優先隊列構造體：PriorityQueue
// =============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);
void priority_queue_free(PriorityQueue *pq, void (*freevalue)(void *));
const KeyValue *priority_queue_top(PriorityQueue *pq);
KeyValue *priority_queue_dequeue(PriorityQueue *pq);
void priority_queue_enqueue(PriorityQueue *pq, KeyValue *kv);
int priority_queue_size(PriorityQueue *pq);
int priority_queue_empty(PriorityQueue *pq);
void priority_queue_print(PriorityQueue *pq);
1) 個中nodes字段是二叉堆數組，_capacity是nodes指向的KeyValue*指針的個數，_size是nodes中現實存儲的元素個數。
_priority可所以PRIORITY_MAX或PRIORITY_MIN，分離表現最年夜元素優先和最小元素優先。
2) priority_queue_new和priority_queue_free分離用於創立和釋放優先隊列。
3) priority_queue_top用於獲得隊列頭部元素，
4）priority_queue_dequeue用於獲得隊列頭部元素並將元素出列。
其完成的根本思緒，以最年夜優先隊列解釋以下：
①將隊列首部nodes[0]保留作為前往值
②將隊列尾部nodes[_size-1]置於nodes[0]地位，並令_size=_size-1
③令以後父節點parent(nodes[i])等於新的隊列首部(i=0)元素，
parent指向元素的兒子節點為left = nodes[2 * i + 1]和rigth = nodes[2 * i + 2]，
比擬left和right獲得優先級高的兒子節點,設為nodes[j](j = 2 *i + 1或2 *i + 2)，
④假如以後父節點parent的優先級高於nodes[j]，交流nodes[i]和nodes[j]，並更新以後父節點,
即令i=j,並輪回 ③；
假如以後父節點的優先級低於nodes[j],處置停止。
5）priority_queue_enqueue用於將KeyValue出列
其完成的根本思緒，以最年夜優先隊列解釋以下：
①設置nodes[_size] 為新的KeyValue,並令_size++
②令以後兒子節點child(nodes[i])為新的隊列尾部節點（i=_size-1)，child的父節點parent為nodes[j],
個中j= (i - 1) / 2
③假如以後兒子節點child的優先級高於parent, 交流nodes[i]和nodes[j]，並更新以後兒子節點
即令i = j,並輪回③;
假如以後兒子節點的優先級低於parent,處置停止。
6) priority_queue_size用於獲得隊列中元素個數，priority_queue_empty用於斷定隊列能否為空。
7）priority_queue_print用於輸入隊列中的內容。
文件pq.h給出了數據構造和函數的聲明，文件pq.c給出了詳細完成，main.c文件用於測試。固然是應用進程化編程的C說話，可以看到詳細的編碼中運用了基於對象的思惟，我們對數據構造和相干函數做了必定水平的集合和封裝。
/*
*File: pq.h
*purpose: declaration 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;
void *_value;
};
KeyValue *key_value_new(int key, void *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);
void priority_queue_free(PriorityQueue *pq, void (*freevalue)(void *));
const KeyValue *priority_queue_top(PriorityQueue *pq);
KeyValue *priority_queue_dequeue(PriorityQueue *pq);
void priority_queue_enqueue(PriorityQueue *pq, KeyValue *kv);
int priority_queue_size(PriorityQueue *pq);
int priority_queue_empty(PriorityQueue *pq);
void priority_queue_print(PriorityQueue *pq);
#endif
/*
*File:pq.c
*purpose: definition of priority queue in C
*Author:puresky
*Date:2011/04/27
*/
#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_head(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,
void *value)
{
KeyValue *pkv = (KeyValue *)malloc(sizeof(KeyValue));
pkv->_key = key;
pkv->_value = value;
return pkv;
}
void key_value_free(KeyValue *kv,
void (*freevalue)(void *))
{
if(kv)
{
if(freevalue)
{
freevalue(kv->_value);
}
free(kv);
}
}
//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;
}
void priority_queue_free(PriorityQueue *pq,
void (*freevalue)(void *))
{
int i;
if(pq)
{
for(i = 0; i < pq->_size; ++i)
key_value_free(pq->_nodes[i], freevalue);
free(pq->_nodes);
free(pq);
}
}
const KeyValue *priority_queue_top(PriorityQueue *pq)
{
if(pq->_size > 0)
return pq->_nodes[0];
return NULL;
}
KeyValue *priority_queue_dequeue(PriorityQueue *pq)
{
KeyValue *pkv = NULL;
if(pq->_size > 0)
{
pkv = pq->_nodes[0];
priority_queue_adjust_head(pq);
}
return pkv;
}
void priority_queue_enqueue(PriorityQueue *pq,
KeyValue *kv)
{
printf("add key:%d\n", kv->_key);
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;
}
void priority_queue_print(PriorityQueue *pq)
{
int i;
KeyValue *kv;
printf("data in the pq->_nodes\n");
for(i = 0; i < pq->_size; ++i)
printf("%d ", pq->_nodes[i]->_key);
printf("\n");
printf("dequeue all data\n");
while(!priority_queue_empty(pq))
{
kv = priority_queue_dequeue(pq);
printf("%d ", kv->_key);
}
printf("\n");
}
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_head(PriorityQueue *pq)
{
int i, j, parent, left, right;
i = 0, j = 0;
parent = left = right = 0;
priority_queue_swap(pq->_nodes, 0, pq->_size - 1);
pq->_size--;
while(i < (pq->_size - 1) / 2)
{
parent = i;
left = i * 2 + 1;
right = left + 1;
j = left;
if(priority_queue_compare(pq, left, right) > 0)
j++;
if(priority_queue_compare(pq, parent, j) > 0)
{
priority_queue_swap(pq->_nodes, i, j);
i = j;
}
else
break;
}
}
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;
}
/*
*File: main.c
*purpose: tesing priority queue in C
*Author:puresky
*Date:2011/04/27
*/
#include <stdio.h>
#include <stdlib.h>
#include "pq.h"
int main(int argc, char **argv)
{
int i;
PriorityQueue *pq = priority_queue_new(PRIORITY_MAX);
int a[]={1, 9, 7, 8, 5, 4, 3, 2, 1, 100, 50, 17};
for(i = 0; i < sizeof(a)/ sizeof(int); ++i)
{
KeyValue *kv = key_value_new(a[i], NULL);
priority_queue_enqueue(pq, kv);
}
priority_queue_print(pq);
priority_queue_free(pq, NULL);
system("pause");
return 0;
}
