優(yōu)先隊(duì)列(priority_queue)的C語(yǔ)言實(shí)現(xiàn)代碼
優(yōu)先隊(duì)列（priority_queue)和一般隊(duì)列(queue)的函數(shù)接口一致，不同的是，優(yōu)先隊(duì)列每次出列的是整個(gè)隊(duì)列中最?。ɑ蛘咦畲螅┑脑?。
本文簡(jiǎn)要介紹一種基于數(shù)組二叉堆實(shí)現(xiàn)的優(yōu)先隊(duì)列，定義的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)的函數(shù)接口說(shuō)明如下：
一、鍵值對(duì)結(jié)構(gòu)體：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 *));
鍵值對(duì)作為優(yōu)先隊(duì)列的中數(shù)據(jù)的保存形式，其中key用于保存優(yōu)先級(jí)，_value用于指向?qū)嶋H的數(shù)據(jù)。
key_value_new用于創(chuàng)建一個(gè)KeyValue結(jié)構(gòu)體；key_value_free用于釋放一個(gè)KeyValue結(jié)構(gòu)體的內(nèi)存，
參數(shù)freevalue用于釋放數(shù)據(jù)指針_value指向的內(nèi)存。
二、優(yōu)先隊(duì)列結(jié)構(gòu)體：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字段是二叉堆數(shù)組，_capacity是nodes指向的KeyValue*指針的個(gè)數(shù)，_size是nodes中實(shí)際存儲(chǔ)的元素個(gè)數(shù)。
_priority可以是PRIORITY_MAX或PRIORITY_MIN，分別表示最大元素優(yōu)先和最小元素優(yōu)先。
2) priority_queue_new和priority_queue_free分別用于創(chuàng)建和釋放優(yōu)先隊(duì)列。
3) priority_queue_top用于取得隊(duì)列頭部元素，
4）priority_queue_dequeue用于取得隊(duì)列頭部元素并將元素出列。
其實(shí)現(xiàn)的基本思路，以最大優(yōu)先隊(duì)列說(shuō)明如下：
①將隊(duì)列首部nodes[0]保存作為返回值
②將隊(duì)列尾部nodes[_size-1]置于nodes[0]位置，并令_size=_size-1
③令當(dāng)前父節(jié)點(diǎn)parent(nodes[i])等于新的隊(duì)列首部(i=0)元素，
parent指向元素的兒子節(jié)點(diǎn)為left = nodes[2 * i + 1]和rigth = nodes[2 * i + 2]，
比較left和right得到優(yōu)先級(jí)高的兒子節(jié)點(diǎn),設(shè)為nodes[j](j = 2 *i + 1或2 *i + 2)，
④如果當(dāng)前父節(jié)點(diǎn)parent的優(yōu)先級(jí)高于nodes[j]，交換nodes[i]和nodes[j]，并更新當(dāng)前父節(jié)點(diǎn),
即令i=j,并循環(huán) ③；
如果當(dāng)前父節(jié)點(diǎn)的優(yōu)先級(jí)低于nodes[j],處理結(jié)束。
5）priority_queue_enqueue用于將KeyValue入列
其實(shí)現(xiàn)的基本思路，以最大優(yōu)先隊(duì)列說(shuō)明如下：
①設(shè)置nodes[_size] 為新的KeyValue,并令_size++
②令當(dāng)前兒子節(jié)點(diǎn)child(nodes[i])為新的隊(duì)列尾部節(jié)點(diǎn)（i=_size-1)，child的父節(jié)點(diǎn)parent為nodes[j],
其中j= (i - 1) / 2
③如果當(dāng)前兒子節(jié)點(diǎn)child的優(yōu)先級(jí)高于parent, 交換nodes[i]和nodes[j]，并更新當(dāng)前兒子節(jié)點(diǎn)
即令i = j,并循環(huán)③;
如果當(dāng)前兒子節(jié)點(diǎn)的優(yōu)先級(jí)低于parent,處理結(jié)束。
6) priority_queue_size用于取得隊(duì)列中元素個(gè)數(shù)，priority_queue_empty用于判斷隊(duì)列是否為空。
7）priority_queue_print用于輸出隊(duì)列中的內(nèi)容。
文件pq.h給出了數(shù)據(jù)結(jié)構(gòu)和函數(shù)的聲明，文件pq.c給出了具體實(shí)現(xiàn)，main.c文件用于測(cè)試。雖然是使用過(guò)程化編程的C語(yǔ)言，可以看到具體的編碼中應(yīng)用了基于對(duì)象的思想，我們對(duì)數(shù)據(jù)結(jié)構(gòu)和相關(guān)函數(shù)做了一定程度的聚集和封裝。
/*
*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;
}
相關(guān)文章
QT中刪除信號(hào)于槽的連接的實(shí)現(xiàn)
本文主要介紹了QT中刪除信號(hào)于槽的連接的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
這篇文章主要介紹了C++中的自定義函數(shù)返回類(lèi)型，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
C語(yǔ)言if選擇結(jié)構(gòu)語(yǔ)句詳解
大家好，本篇文章主要講的是C語(yǔ)言if選擇結(jié)構(gòu)語(yǔ)句詳解，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
這篇文章主要為大家介紹了C++核心編程中內(nèi)存分區(qū)模型，C++程序在執(zhí)行時(shí)，將內(nèi)存大方向分為四個(gè)區(qū)域，代碼區(qū)，全局區(qū)，棧區(qū)，堆區(qū)，文章通過(guò)代碼示例介紹的非常詳細(xì)，感興趣的同學(xué)可以參考閱讀下2023-07-07
基于實(shí)現(xiàn)Qt秒表設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了基于實(shí)現(xiàn)Qt秒表設(shè)計(jì)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要介紹了c++動(dòng)態(tài)分配的的相關(guān)資料，文中代碼簡(jiǎn)單易懂，方便大家更好的學(xué)習(xí)參考，感興趣的朋友可以了解下2020-06-06
本章主要介紹C語(yǔ)言與C++的內(nèi)存管理，以C++的內(nèi)存分布作為引入，介紹C++不同于C語(yǔ)言的內(nèi)存管理方式（new?delete對(duì)比?malloc?free)，感興趣的朋友來(lái)看看吧2022-05-05
C/C++中運(yùn)算符的優(yōu)先級(jí)、運(yùn)算符的結(jié)合性詳解
這篇文章主要介紹了C/C++中運(yùn)算符的優(yōu)先級(jí)、運(yùn)算符的結(jié)合性詳解的相關(guān)資料,需要的朋友可以參考下2017-02-02
C語(yǔ)言冷知識(shí)之預(yù)處理字符串操作符詳解
當(dāng)年學(xué)習(xí)C語(yǔ)言的第一門(mén)課就提到過(guò)標(biāo)記(Token)的概念，不過(guò)，相信在多年之后你再次聽(tīng)到這個(gè)術(shù)語(yǔ)時(shí)會(huì)一臉懵逼，比如我。因此特地翻了翻資料，整理下來(lái)這些筆記，希望對(duì)大家有所幫助2022-11-11
C++模板以及實(shí)現(xiàn)vector實(shí)例詳解
模板是為了實(shí)現(xiàn)泛型編程,所謂泛型編程,就是指編寫(xiě)與類(lèi)型無(wú)關(guān)的代碼,下面這篇文章主要給大家介紹了關(guān)于C++模板以及實(shí)現(xiàn)vector的相關(guān)資料,需要的朋友可以參考下2021-11-11