C中的PriorityQueue问题
我正在尝试为ac项目编写PriorityQueue。 当我尝试将项目出列时，程序崩溃了; 但是我认为问题来自于我添加项目的方式，因为如果我在添加第三个元素后尝试访问列表中的第一个元素，我也会遇到崩溃。
头文件：
#ifndef PQUEUE_H_INCLUDED #define PQUEUE_H_INCLUDED #include #include #include #include //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代码：
#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-> head->数据时，错误似乎即将到来 – 我将其缩小到注释的区域// ERROR HERE。 这对我来说似乎很奇怪，因为添加第三个元素应该与添加第二个元素相同。 也没有pq-> head == NULL或pq-> head> data == NULL。
我看到以下问题：
-
queue_free不会为其beforeFirst对象释放内存。 - 如果数据分配失败，
add_priority将不释放该元素。 这并不重要，因为你正在退出，但如果你决定返回一个错误（换句话说，它将停止内存泄漏），它将是一个很好的forms。
但是，我已经通过插入一个新元素来测试该代码，在该元素之前插入一个元素，然后在结尾插入一个元素，它看起来很好。 您插入了哪些优先级值（按顺序）？
并且您可能希望发布调用此代码的代码。 很可能它可能是与此实际代码无关的内存损坏问题。
虽然我很感激你试图引入beforeFirst东西以保持代码的美观，但你真的应该咬紧牙关并摆脱它。 它的删除可能会抵消你为处理真正空列表而必须添加的额外代码的最小数量。 这个更简单的代码应该处理所有场景，而不需要额外的处理来保持额外的指针同步。
我实际上没有测试过这个，而不是我的湿软件，但它应该（希望）工作正常：
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;
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); }
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++; }
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会创建内存的副本，以便您可以传递动态分配的内存或其他内容。 该函数不承担释放传递给它的任何已分配内存的责任。 如果它是动态分配的，你仍然必须自己释放它。 它以这种方式完成，因此您可以传递任何类型的内存。
另一方面， queue_remove只会将您分配给已分配的内存，因此您有责任在完成后释放它。 您收到的记忆将始终通过malloc获得。
您可以优化queue_add_priority以便您可以指定传入的内存是通过malloc分配的，并且您通过更改函数的第一部分来传递责任：
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获得的，那么将final参数设置为true，并且您同意放弃对它的责任 – 这样，函数就会按原样占用内存块。
否则，使用false并进行复制。
这是一个导致问题的访问模式。
PQUEUE *queue = queue_new(); int x0 = 0; int x1 = 1; queue_add_priority(queue, &x0, sizeof(x0), x0); //add1 queue_add_priority(queue, &x1, sizeof(x1), x1); //add2 queue_remove(queue); //remove queue_add_priority(queue, &x0, sizeof(x0), x0); //add3 while (queue_has_next(queue)) printf("%d\n", *(int *)queue_remove(queue));
优先级较高的项目应该出现在头部吗？ 如果它应该在您的代码中不会发生这种情况。
在前两次添加之后，计数为2，优先级较低的项目位于头部（ 0 1 ，计数： 2 ）。 以下删除使head元素递减计数。 剩下的是优先级1项（ 1 ，计数： 1 ）。 问题是添加另一个0优先级项，实际上没有向队列添加任何内容，并且计数仍然增加（ 1 ，计数： 2 ）。 然后，由于队列已经记录了当真正只有1时有2个项目，最终删除失败。
问题在于您遍历队列。 更具体地说，在删除后不会更新您启动的位置（ beforefirst指针）。 删除后，它仍然指向“已删除”节点。 实际上，所有正在进行的添加将添加到先前删除的节点的末尾，使实际队列处于不一致状态。 这是为什么在不需要时始终释放内存以及之后将指针设置为NULL的好主意之一。
除了paxdiablo提到的问题之外，在删除队列头部的情况下，您还忘记在beforefirst->next更新。 这是发生了什么：
在queue_remove之前：
在第一个头尾
| | |
VVV
+ ------------- + + ------------- + + ------------- +
| 占位符| - > | x | - > | y | - > NULL
+ ------------- + + ------------- + + ------------- +
在queue_remove之后：
在第一个头尾
| | |
VVV
+ ------------- + + ------------- + + ------------- +
| 占位符| - > | x | - > | y | - > NULL
+ ------------- + + ------------- + + ------------- +
您需要修复queue_remove以便beforefirst->next指向head->next如果head为非NULL（否则为NULL）。
如果插入的元素位于第一个位置，则必须修改queue_add以更改before_first。
一般来说，我不会使用before_first。 只需更改循环以检查ptr到current == null并将start元素更改为第一个。
应该消除所有其他问题。
心连心
马里奥