C语言优先队列,代码问题

2019-07-15 20:28发布

基于数组二叉堆实现的优先队,C语言实现(参考http://www.jb51.net/article/41978.htm大神的代码)。在VC6.0上运行没问题,想移植到keil 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;
      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;
}







1.jpg
2.jpg
友情提示: 此问题已得到解决,问题已经关闭,关闭后问题禁止继续编辑,回答。
该问题目前已经被作者或者管理员关闭, 无法添加新回复
4条回答
chimple
1楼-- · 2019-07-15 22:52
求帮助啊,弄了好久就是不行啊。
依然落叶飘零
2楼-- · 2019-07-16 01:44
进入函数里面单步调试看看是什么问题。这个实在是爱莫能助。
1522495332
3楼-- · 2019-07-16 04:37
看了很久我也没找到原因,只能是单步调试,跳进函数内部,观察一下那个变量是在什么时候自己改变的,最好能同时留意一下各个变量在内存中的地址。
chimple
4楼-- · 2019-07-16 09:49
 精彩回答 2  元偷偷看……

一周热门 更多>