我想爲c項目寫一個PriorityQueue。當我嘗試出列物品時,程序崩潰;但是我認爲問題來自我添加項目的方式,因爲如果我在添加第三個元素後嘗試訪問列表中的第一個元素,我也會崩潰。問題與C中的PriorityQueue
頭文件
#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代碼:
#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-> head == NULL或pq-> head> data == NULL。
這對我的作品。你可以發佈添加對象到隊列的代碼嗎? – Samaursa 2010-10-14 03:54:05