快捷導(dǎo)航

優(yōu)先隊(duì)列(priority_queue)的C語言實(shí)現(xiàn)代碼

更新時(shí)間：2013年10月10日 09:12:33 作者：

本文簡要介紹一種基于數(shù)組二叉堆實(shí)現(xiàn)的優(yōu)先隊(duì)列，定義的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)的函數(shù)接口說明如下

優(yōu)先隊(duì)列（priority_queue)和一般隊(duì)列(queue)的函數(shù)接口一致，不同的是，優(yōu)先隊(duì)列每次出列的是整個(gè)隊(duì)列中最小（或者最大）的元素。

本文簡要介紹一種基于數(shù)組二叉堆實(shí)現(xiàn)的優(yōu)先隊(duì)列，定義的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)的函數(shù)接口說明如下：

一、鍵值對結(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 *));

鍵值對作為優(yōu)先隊(duì)列的中數(shù)據(jù)的保存形式，其中key用于保存優(yōu)先級，_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

復(fù)制代碼代碼如下:

// =============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í)際存儲的元素個(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ì)列說明如下：

①將隊(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)先級高的兒子節(jié)點(diǎn),設(shè)為nodes[j](j = 2 *i + 1或2 *i + 2)，

④如果當(dāng)前父節(jié)點(diǎn)parent的優(yōu)先級高于nodes[j]，交換nodes[i]和nodes[j]，并更新當(dāng)前父節(jié)點(diǎn),

即令i=j,并循環(huán) ③；

如果當(dāng)前父節(jié)點(diǎn)的優(yōu)先級低于nodes[j],處理結(jié)束。

5）priority_queue_enqueue用于將KeyValue入列

其實(shí)現(xiàn)的基本思路，以最大優(yōu)先隊(duì)列說明如下：

①設(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)先級高于parent, 交換nodes[i]和nodes[j]，并更新當(dāng)前兒子節(jié)點(diǎn)

即令i = j,并循環(huán)③;

如果當(dāng)前兒子節(jié)點(diǎn)的優(yōu)先級低于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語言，可以看到具體的編碼中應(yīng)用了基于對象的思想，我們對數(shù)據(jù)結(jié)構(gòu)和相關(guān)函數(shù)做了一定程度的聚集和封裝。

復(fù)制代碼代碼如下:

/*
*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;
}