Блог

Моя очередь приоритетов работает и печатается так, как я ожидал, но free недействителен, и я не уверен, почему, я следую всем протоколам для кучи, которые я изучил до сих пор, но моя программа не завершится.

 #include <stdlib.h>
#include "priority_queue.h"

struct item{
    int priority;
    int value;
};
typedef struct item Item;

struct priority_queue{
    int size;
    int capacity;
    int front;
    Item* data;
};
typedef struct priority_queue Priority_queue;

void priority_queue_fix_down(PRIORITY_QUEUE hQueue, int index, int size);

PRIORITY_QUEUE priority_queue_init_default(void){
    Priority_queue* pQueue_ptr;
    pQueue_ptr = (Priority_queue*)malloc(sizeof(Priority_queue));
    if(pQueue_ptr != NULL){
        pQueue_ptr->size = 0;
        pQueue_ptr->capacity = 1;
        pQueue_ptr->data = (Item*)malloc(sizeof(Item)*pQueue_ptr->capacity);
        if (pQueue_ptr->data == NULL){
            free(pQueue_ptr);
            pQueue_ptr = NULL;
        }
    }
    return pQueue_ptr;
}
Status priority_queue_insert(PRIORITY_QUEUE hQueue, int priority_level, int data_item)
{
    Priority_queue* pQueue_ptr = (Priority_queue*)hQueue;
    Item* temp, temp2;
    //temp = (Item*)malloc(sizeof());
    int i;
    if (pQueue_ptr->size >= pQueue_ptr->capacity)
    {
        //not enough space
        temp = (Item*)malloc(sizeof(Item) * 2 * pQueue_ptr->capacity);
        if (temp == NULL)
        {
            return FAILURE;
        }
        for (i = 0; i < pQueue_ptr->size; i  )
        {
            temp[i] = pQueue_ptr->data[i];

        }
        pQueue_ptr->front = 0;
        pQueue_ptr->capacity *= 2;
        free(pQueue_ptr->data);
        pQueue_ptr->data = temp;
    }
    i = pQueue_ptr->size;
    (pQueue_ptr->data[i]).priority = priority_level;
    (pQueue_ptr->data[i]).value = data_item;
    int index_of_parent;
    index_of_parent = (i - 1) / 2;
    while (i >= 1 amp;amp; ((pQueue_ptr->data[i]).priority > (pQueue_ptr->data[index_of_parent]).priority))
    {

        temp2 = pQueue_ptr->data[index_of_parent];
        pQueue_ptr->data[index_of_parent] = pQueue_ptr->data[i];
        pQueue_ptr->data[i] = temp2;
        i = index_of_parent;
        index_of_parent = (i - 1) / 2;
    }
    pQueue_ptr->size  ;
    // pQueue_ptr->front = 0;
    // pQueue_ptr->back = pQueue_ptr->size-1;
    return SUCCESS;
}
void print_heap(PRIORITY_QUEUE hQueue){
    Priority_queue* pQueue_ptr = (Priority_queue*) hQueue;
    for(int x = 0; x<pQueue_ptr->size;x  ){
        printf("%dn", pQueue_ptr->data[x].priority);
    }

}
Status priority_queue_service(PRIORITY_QUEUE hQueue){
    //set variables
    Priority_queue* pQueue_ptr = (Priority_queue*) hQueue;
    Item temp;
    int size, index, index_left_child, index_right_child;
    
    
    if(pQueue_ptr->size == 0){
        return FAILURE;
    }
    
    index = 0;
    temp = pQueue_ptr->data[0];
    pQueue_ptr->data[0] = pQueue_ptr->data[pQueue_ptr->size-1];
    pQueue_ptr->data[size-1] = temp;
    pQueue_ptr->size--;
    priority_queue_fix_down(pQueue_ptr, pQueue_ptr->front, pQueue_ptr->size); 
    return SUCCESS;
}

int priority_queue_front(PRIORITY_QUEUE hQueue, Status* status)
{
    Priority_queue* pPriority_queue = (Priority_queue*)hQueue;
    if (priority_queue_is_empty(pPriority_queue))
    {
        if (status != NULL)
        {
            *status = FAILURE;
        }
        return 0;
    }
    if (status != NULL)
    {
        *status = SUCCESS;
    }
    return (pPriority_queue->data[pPriority_queue->front]).value;
}

Boolean priority_queue_is_empty(PRIORITY_QUEUE hQueue){
    Priority_queue* pQueue_ptr = (Priority_queue*) hQueue;
    if (pQueue_ptr->size <= 0)
        return TRUE;
    else
        return FALSE;
}
 

Вот где я получаю ошибку при отладке, на free (pPriority_queue-> data); Он даже не доходит до строки ниже. Я попытался использовать чужую «сервисную» функцию, и это сработало, но они внедрили «исправление» в свою сервисную функцию, в то время как я пытаюсь сделать это снаружи в отдельной функции.

 void priority_queue_destroy(PRIORITY_QUEUE* phQueue){
    Priority_queue* pPriority_queue = (Priority_queue*)*phQueue;
    free(pPriority_queue->data);
    free(*phQueue);
    
   // *phQueue = NULL;
    return;
}

void priority_queue_fix_down(PRIORITY_QUEUE hQueue, int index, int size){
    Priority_queue* pQueue_ptr = (Priority_queue*) hQueue;
    Item* temp;
    temp = (Item*)malloc(sizeof(Item));
    if (temp == NULL)
        return NULL;
    //int front = priority_queue_front(pQueue_ptr, NULL);
    int index_left_child = 2* index   1;
    int index_right_child = 2* index   2;
    
    
//     print_heap(pQueue_ptr);
//     printf("nsize: %dnindex: %dn", size, index);
//   // printf("Front: %dn", pQueue_ptr->data[0]);
//     if(pQueue_ptr->data[index_left_child].priority > (pQueue_ptr->data[index]).priority){
//         printf("Left child index %dnRight child index: %dnLeft child has highest priority of: %dn",index_left_child, index_right_child, pQueue_ptr->data[index_left_child].priority);
//     }
//     else
//         printf("Right child index: %dnLeft child index %dnRight child has highest priority of: %dn",index_right_child, index_left_child, pQueue_ptr->data[index_right_child].priority);
    
    
    if (index_left_child < size){
        if (index_right_child < size amp;amp; pQueue_ptr->data[index_right_child].priority > (pQueue_ptr->data[index_left_child]).priority){
            if(pQueue_ptr->data[index_right_child].priority > (pQueue_ptr->data[index]).priority){
                *temp = pQueue_ptr->data[index];
                pQueue_ptr->data[index] = pQueue_ptr->data[index_right_child]  ;
                pQueue_ptr->data[index_right_child] = *temp;
                priority_queue_fix_down(pQueue_ptr, index_right_child, size);
            }
        }   
        if(pQueue_ptr->data[index_left_child].priority > (pQueue_ptr->data[index]).priority){
                *temp = pQueue_ptr->data[index];
                pQueue_ptr->data[index] = pQueue_ptr->data[index_left_child];
                pQueue_ptr->data[index_left_child] = *temp;
                priority_queue_fix_down(pQueue_ptr, index_left_child, size);
            }
        }
    }