优先队列(priority_queue)的C语言实现代码_C 语言

优先队列(priority_queue)和一般队列(queue)的函数接口一致,不同的是,优先队列每次出列的是整个队列中最小(或者最大)的元素。

本文简要介绍一种基于数组二叉堆实现的优先队列,定义的数据结构和实现的函数接口说明如下:

一、键值对结构体: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指向的内存。

二、优先队列结构体: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;
}

时间: 2024-09-23 00:34:32

优先队列(priority_queue)的C语言实现代码_C 语言的相关文章

马尔可夫链算法(markov算法)的awk、C++、C语言实现代码_C 语言

1. 问题描述 马尔可夫链算法用于生成一段随机的英文,其思想非常简单.首先读入数据,然后将读入的数据分成前缀和后缀两部分,通过前缀来随机获取后缀,籍此产生一段可读的随机英文. 为了说明方便,假设我们有如下一段话:   复制代码 代码如下:    Show your flowcharts and conceal your tables and I will be mystified. Show your tables and your flowcharts will be obvious.   假

k均值算法c++语言实现代码_C 语言

复制代码 代码如下: //k-mean.h #ifndef KMEAN_HEAD #define KMEAN_HEAD  #include <vector> #include <map>  //空间点的定义 class Node {     public:        double pos_x;        double pos_y;        double pos_z;      Node()      {          pos_x = 0.0;          p

哈夫曼的c语言实现代码_C 语言

我们设置一个结构数组 HuffNode 保存哈夫曼树中各结点的信息.根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有 2n-1 个结点,所以数组 HuffNode 的大小设置为 2n-1 .HuffNode 结构中有 weight, lchild, rchild 和 parent 域.其中,weight 域保存结点的权值, lchild 和 rchild 分别保存该结点的左.右孩子的结点在数组 HuffNode 中的序号,从而建立起结点之间的关系.为了判定一个结点是否已加入到要建立的哈夫曼树

C语言冒泡排序算实现代码_C 语言

冒泡排序是排序算法的一种,思路清晰,代码简洁,常被用在大学生计算机课程中. "冒泡"这个名字的由来是因为越大的元素会经由交换慢慢"浮"到数列的顶端,故名. 这里以从小到大排序为例进行讲解. 基本思想及举例说明 冒泡排序的基本思想就是不断比较相邻的两个数,让较大的元素不断地往后移.经过一轮比较,就选出最大的数:经过第2轮比较,就选出次大的数,以此类推. 下面以对 3  2  4  1 进行冒泡排序说明. 第一轮 排序过程3  2  4  1    (最初) 2  3 

C/C++实现的游戏角色名称名字随机生成代码_C 语言

#ifndef __NAME_H__ #define __NAME_H__ class CName { public: CName(); virtual ~CName(); const char* GetName(); protected: void InitSurname(); void InitName(); char* m_pSurname_OneDimensional; char** m_ppSurname; // 姓 char* m_pName_OneDimensional; char

基于C语言实现的扫雷游戏代码_C 语言

本文详细讲述了基于C语言实现的扫雷游戏代码,代码中备有比较详细的注释,便于读者阅读和理解.希望对学习游戏开发的朋友能有一点借鉴价值. 完整的实例代码如下: /* 模拟扫雷游戏 */ #include <graphics.h> #include <math.h> #include <stdio.h> #include <dos.h> #include <stdlib.h> #include <conio.h> #include <

基于C语言实现的贪吃蛇游戏完整实例代码_C 语言

本文以实例的形式讲述了基于C语言实现的贪吃蛇游戏代码,这是一个比较常见的游戏,代码备有比较详细的注释,对于读者理解有一定的帮助. 贪吃蛇完整实现代码如下: #include <graphics.h> #include <conio.h> #include <stdlib.h> #include <dos.h> #define NULL 0 #define UP 18432 #define DOWN 20480 #define LEFT 19200 #defi

基于C语言实现五子棋游戏完整实例代码_C 语言

本文实例讲述了基于C语言实现五子棋游戏的方法,代码备有比较完整的注释,可以帮助读者更好的加以理解. 五子棋游戏代码如下: /* * 使用键盘的上下左右键移动棋盘,空格键表示下棋,ESC键退出程序 */ #include <stdio.h> #include <stdlib.h> #include <bios.h> #include <graphics.h> #include<malloc.h> /* * 对应键盘键的十六进制数字 */ #defi

VC++基于Dx实现的截图程序示例代码_C 语言

本文所述的程序示例为VC++图象特效的截图示例,需要DirectX 3.0以上版,代码中的GetScreen函数是本截图程序的关键.运行这个程序可用Esc键结束.代码中需要ddutil.h与ddutil.cpp文件,请自行下载添加.关于InitDDraw()函数,功能是初始化DirectDraw环境,创建换页链(主页面,一个后台缓冲区),以及创建一个定时器. 具体的功能代码如下: #include <windows.h> #include <windowsx.h> #include