问题的PriorityQueue用C

本文介绍了问题的PriorityQueue用C的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我试图写一个C项目的PriorityQueue。当我试图出列项目的程序崩溃;然而，我认为这个问题是从专程前来我加的项目，因为如果我尝试添加第三个元素我得到一个崩溃以及后访问的第一个元素在列表中。

I am trying to write a PriorityQueue for a c project. The program is crashing when I try to dequeue items; however I think the issue is coming from the way I add the items, as If I try to access the first element in the list after adding the third element I get a crash as well.

头文件：

#ifndef PQUEUE_H_INCLUDED 
#define PQUEUE_H_INCLUDED

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

//Data structure for holding one element in pqueue
typedef struct _e {
    void *data;
    size_t datalen;
    int priority;
    struct _e *next;
} ELEMENT;

//data structure for the whole pqueue
typedef struct {
    ELEMENT *head;          //reference to first element 
    ELEMENT *tail;          //reference to last element
    ELEMENT *beforefirst;   //dummy element before first element;
    int elements;
} PQUEUE;


extern PQUEUE*  queue_new(void);
extern void     queue_free(PQUEUE *);
extern void     queue_add_end(PQUEUE *, void *, size_t);
extern void     queue_add_priority(PQUEUE *, void *, size_t,int);
extern void*    queue_remove(PQUEUE *);
extern bool     queue_has_next(PQUEUE *);
extern int      queue_size(PQUEUE *);


#endif

的PriorityQueue code：

PriorityQueue code:

#include "pqueue.h"

PQUEUE *queue_new(void) {
    PQUEUE *pq = malloc(sizeof(PQUEUE));
    if (pq == NULL) {
        perror("queue_new");
        exit(EXIT_FAILURE);
    }
    pq->head = NULL;
    ELEMENT *newelement;
    newelement = calloc(1,sizeof(ELEMENT));
    pq->beforefirst = newelement;
    pq->beforefirst->next = pq->head;
    pq->tail = NULL;
    pq->elements = 0;

    return pq;
}

void queue_free(PQUEUE *pq) {
    ELEMENT *this, *save;
    this = pq->head;
    while(this!= NULL) {
        save = this;
        this = this->next;
        free(save->data);
        free(save);
    }
    free(pq);
}


void queue_add_priority(PQUEUE *pq, void *data, size_t datalen,int priority) {
    ELEMENT *newelement;
    newelement = calloc(1,sizeof(ELEMENT));
    if (newelement == NULL) {
        perror("queue_add");
        exit(EXIT_FAILURE);
    }
    newelement->data = malloc(datalen);
    newelement->priority = priority;
    if(newelement->data == NULL) {
        perror("queue_add");
        exit(EXIT_FAILURE);
    }
    memcpy(newelement->data,data,datalen);
    newelement->datalen = datalen;
    newelement->next = NULL;
    //sets pointer at beforefirst element and iterates through queue until ptr->next
    // priority is greater than newlement priority, or until end of queue.
    ELEMENT *ptr = pq->beforefirst;
    while (ptr->next != NULL) {
        if (ptr->next->priority > priority) break;
        ptr = ptr->next;
    }
    if (ptr == pq->beforefirst) {
        pq->head = newelement;
    }
    if (ptr->next == NULL) {
        pq->tail = newelement;
    }
    newelement->next = ptr->next;
    ptr->next = newelement;


    //ERROR HERE
    //void* d;
    //d = pq->head->data;
    pq->elements++;
}

void* queue_remove(PQUEUE *pq) {
    //ERROR HERE
    void* item = pq->head->data;
    pq->head = pq->head->next;
    pq->elements--;
    return item;
}

bool queue_has_next(PQUEUE *pq) {
    return !(pq->elements == 0);
}

基本上，错误似乎是未来，当我尝试访问pq->流浆>数据后，我已经添加了第三个要素 - 我把范围缩小到区域评论//错误这里。这似乎很奇怪我，因为增加的第三个元素应相同的工作，加入第二。
还没有pq->头== NULL或pq->头>数据== NULL。

Basically, the error seems to be coming when I try to access pq->head->data after I've added the third element - I narrowed it down to the areas commented //ERROR HERE. It seems odd to me because adding the third element should work identically to adding the second.Also neither pq->head == NULL or pq->head>data == NULL.

推荐答案

我看到以下问题：

queue_free 不会释放其 beforeFirst 对象的内存。

add_priority 如果数据分配失败不会释放的元素。这不管那么多了，因为你退出，但它会在情况下，你决定返回一个错误的好形式（换句话说，它会停止内存泄漏）。

queue_free does not free the memory for its beforeFirst object.
add_priority won't free the element if the data allocation fails. This doesn't matter that much since you're exiting but it would be good form in case you ever decide to return an error (in other words, it will stop a memory leak).

不过，我已经通过插入一个新的元素，一个然后在最后一个元素之前的元素测试了code，似乎罚款。什么优先值是插入你（按顺序）？

However, I've tested that code by inserting a new element, an element before that one then an element at the end, and it seems fine. What priority values are you inserting (in order)?

和你可能要张贴的code，它的调用这个code。它很可能它可能是一个内存损坏问题无关，这实际code。

And you may want to post the code that's calling this code. It's quite possible it may be a memory corruption issue unrelated to this actual code.

虽然我AP preciate您在介绍 beforeFirst 东西的尝试，让您的code不错，你真的应该只是咬紧牙关，摆脱它。其去除可能会远远抵消额外的$ C $的最小量c，你将必须添加处理一个真正的空单。这个简单的code应该处理所有方案，而不会保持同步额外的指针所需要的加工增值。

While I appreciate your attempt in introducing the beforeFirst stuff to keep your code nice, you really should just bite the bullet and get rid of it. Its removal will probably more than offset the minimal amount of extra code you're going to have to add for handling a truly empty list. This simpler code should handle all scenarios without the added processing required to keep extra pointers synchronised.

我实际上没有比我的湿件测试这等，但它应该（希望）好工作：

I haven't actually tested this other than in my wetware but it should (hopefully) work okay:

typedef struct _e {
    void *data;
    size_t datalen;
    int priority;
    struct _e *next;
} ELEMENT;

typedef struct {
    ELEMENT *head;          //reference to first element 
    ELEMENT *tail;          //reference to last element
    int elements;
} PQUEUE;

＆NBSP;

PQUEUE *queue_new(void) {
    PQUEUE *pq = malloc(sizeof(PQUEUE));
    if (pq == NULL) {
        perror("queue_new");
        exit(EXIT_FAILURE);
    }
    pq->head = pq->tail = NULL;
    pq->elements = 0;
    return pq;
}

void queue_free(PQUEUE *pq) {
    ELEMENT *this, *save;
    this = pq->head;
    while(this!= NULL) {
        save = this;
        this = this->next;
        free(save->data);
        free(save);
    }
    free(pq);
}

＆NBSP;

void queue_add_priority(PQUEUE *pq, void *data, size_t datalen, int priority) {
    ELEMENT *newelement;
    newelement = calloc(1,sizeof(ELEMENT));
    if (newelement == NULL) {
        perror("queue_add");
        exit(EXIT_FAILURE);
    }
    newelement->data = malloc(datalen);
    if(newelement->data == NULL) {
        perror("queue_add");
        free (newelement);
        exit(EXIT_FAILURE);
    }
    memcpy(newelement->data,data,datalen);
    newelement->datalen = datalen;
    newelement->priority = priority;
    newelement->next = NULL;

    // Inserting into empty list.
    if (pq->elements == 0) {
        pq->head = pq->tail = newelement;
        pq->elements = 1;
        return;
    }

    // Inserting beyond tail.
    if (pq->tail->priority <= priority) {
        pq->tail->next = newelement;
        pq->tail = newelement;
        pq->elements++;
        return;
    }

    // Inserting before head.
    if (pq->head->priority > priority) {
        newelement->next = pq->head;
        pq->head = newelement;
        pq->elements++;
        return;
    }

    // Otherwise, we're inserting somewhere in the middle.
    ELEMENT *ptr = pq->head;
    while (ptr->next->priority <= priority)
        ptr = ptr->next;
    newelement->next = ptr->next;
    ptr->next = newelement;
    pq->elements++;
}

＆NBSP;

void* queue_remove(PQUEUE *pq) {
    if (pq->elements == 0)        // added, just in case.
        return NULL;
    void* item = pq->head->data;
    pq->head = pq->head->next;
    pq->elements--;
    return item;
}

bool queue_has_next(PQUEUE *pq) {
    return (pq->elements > 0);    // better, IMNSHO.
}

记

请即 queue_add_priority 使得内存的副本，以便您可以通过它动态分配的内存或其他。这个函数不接受释放您传递给它的任何分配的内存责任。如果它是动态分配的，你还是要自己释放它。有人做过这样，所以你可以在通过的任何的排序内存。

Keep in mind that queue_add_priority makes a copy of the memory so that you can pass it dynamically allocated memory or otherwise. That function doesn't accept responsibility for freeing any allocated memory that you pass to it. If it's dynamically allocated, you still have to free it yourself. It was done this way so you could pass in any sort of memory.

在另一方面， queue_remove 只是传递回你所分配的内存，使您的是的负责释放它，当你完成。您收到的内存将拥有的总是的通过了的malloc 。

On the other hand, queue_remove just passes you back the allocated memory so you are responsible for freeing it when you're done. The memory you receive will have always been obtained via malloc.

您的可能的优化 queue_add_priority ，这样你可以指定该内存通过分配的malloc 和你是从改变功能的第一部分传递的责任：

You could optimise queue_add_priority so that you could specify that the memory being passed in is allocated via malloc and you are passing responsibility by changing the first part of the function from:

void queue_add_priority(PQUEUE *pq, void *data, size_t datalen, int priority) {
    ELEMENT *newelement;
    newelement = calloc(1,sizeof(ELEMENT));
    if (newelement == NULL) {
        perror("queue_add");
        exit(EXIT_FAILURE);
    }
    newelement->data = malloc(datalen);
    if(newelement->data == NULL) {
        perror("queue_add");
        free (newelement);
        exit(EXIT_FAILURE);
    }
    memcpy(newelement->data,data,datalen);

到

void queue_add_priority(PQUEUE *pq, void *data, size_t datalen, int priority, int xfer) {
    ELEMENT *newelement;
    newelement = calloc(1,sizeof(ELEMENT));
    if (newelement == NULL) {
        perror("queue_add");
        exit(EXIT_FAILURE);
    }
    if (!xfer) {
        newelement->data = malloc(datalen);
        if(newelement->data == NULL) {
            perror("queue_add");
            free (newelement);
            exit(EXIT_FAILURE);
        }
        memcpy(newelement->data,data,datalen);
    } else {
        newelement->data = data;
    }

在换句话说，如果是通过的malloc 获得的数据的最后一个参数设置为true，您同意放弃责任为它 - 这样，函数只是需要你的内存块的。

In other words, set the final parameter to true if the data was obtained via malloc and you agree to give up responsibility for it - that way, the function just takes your memory block as is.

否则，使用虚假和副本将会作出修改。

Otherwise, use false and a copy will be made.

                        这篇关于问题的PriorityQueue用C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！