대기열/대기열에서 이탈합니다.

Question

나는 모든 유형의 데이터에 대해 일반화 될 수 있도록 void 포인터를 보유하는 큐를 구현하는 작업을 수행하고 있습니다. 나는 dequeuing 노드가 목록의 크기를 줄이지 만 예상 할 노드를 반환하지 않는 곳에서는 현재 이상한 문제를 겪고 있습니다. dequeue 작업에서 free()에 대한 호출을 생략하면이 문제가 해결되지만, dequeued 노드를 해제하려면 바람직하지 않습니다. 어떤 팁?

테스트 실행 : routine.c

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h> 
#include "queue.h" 

int main() { 
    queue test = make_queue(); 
    enqueue("One", test); 
    enqueue("Two", test); 
    printf("Item is %s!\n", (char *)dequeue(test)); 
    printf("Item is %s!\n", (char *)dequeue(test)); 
    return 0; 
} 

queue.h

#include <stdbool.h> 
#include <stdlib.h> 
#include <stdio.h> 
/* A queue is implemented as a pointer to a structure not specified here. */ 

typedef struct queue_structure *queue; 

struct node { 
    struct node * next; 
    void * data; 
}; 

struct queue_structure { 
    struct node * head; 
    struct node * tail; 
}; 

/* List of function protocols. */ 
bool is_empty_queue(queue q); 

/* The make_queue function returns a newly created queue with no values 
    stored in it. 
*/ 

queue make_queue() { 
    queue newQueue = malloc(sizeof(struct queue_structure)); 
    return newQueue; 
} 

/* The enqueue function adds a value to a queue. Although this function 
    does not change the pointer q, fields of the structure to which q 
    points may be modified in the course of a call to this function. 
*/ 

void enqueue(void *value, queue q) { 
    struct node * newNode = (struct node *)malloc(sizeof(struct node)); 
    newNode->data = value;  
    if(is_empty_queue(q)) 
    q->tail = newNode; 
    newNode->next = q->head; 
    q->head = newNode; 
} 

/* The dequeue function removes a value from a queue and returns it. 
    Although this function does not change the pointer q, fields of the 
    structure to which q points may be modified in the course of a call to 
    this function. 

    It is a precondition of this function that at least one value is stored 
    in the queue. 
*/ 

void *dequeue(queue q) { 
    if(!q->head->next) { // Only a single item in the queue. 
    printf("Only one item in queue!\n"); 
    struct node * to_dequeue = q->tail; 
    void * data = q->head->data; 
    free(to_dequeue); 
    q->head = NULL; 
    q->tail = NULL; 
    return data; 
    } 
    else { // Multiple items in the queue. 
    printf("Several items in queue!\n"); 
    struct node * to_dequeue = q->tail; 
    void * data = q->tail->data; 
    struct node * trace = q->head; 
    while(trace->next && trace->next != q->tail) 
     trace = trace->next; 
    free(to_dequeue); 
    q->tail = trace; 
    q->tail->next = NULL; 
    return data; 
    } 
} 

/* The front_of_queue function returns the value at the front of a queue 
    (that is, the one least recently added to the queue) without removing 
    that value from the queue. It has no side effect. 

    It is a precondition of this function that at least one value is stored 
    in the queue. 
*/ 

void *front_of_queue(queue q) { 
    return q->head->data; 
} 

/* The is_empty_queue function determines whether a queue is empty, 
    returning the true Boolean value if no values are stored in the queue 
    and the false Boolean value if one or more values are stored in the 
    queue. 
*/ 

bool is_empty_queue(queue q) { 
    if(q->head) 
    return 1; 
    return 0; 
} 

Answer 1

당신은 make_queue에서 NULL에 head 및 tail를 초기화하지 않고 당신은 당신의 공허함 테스트를 가지고있다 잘못됨,

bool is_empty_queue(queue q) { 
    if(q->head) 
    return 1; 
    return 0; 
} 

그러면 enqueue이 이상하게 동작합니다.

void enqueue(void *value, queue q) { 
    struct node * newNode = (struct node *)malloc(sizeof(struct node)); 
    newNode->data = value;  
    if(is_empty_queue(q)) 
    q->tail = newNode; 
    newNode->next = q->head; 
    q->head = newNode; 
} 

사례 1, 우연히 head 및 tail 처음

head -> 0; tail -> 0 // now enqueue 1 
is_empty_queue(q) returns 0 since q->head == NULL, so q->tail still points to 0 
n(1)->next = 0 
head = n(1) 

results in 
head -> n(1) -> 0; tail -> 0 // next enqueue 2 
is_empty_queue(q) returns 1 since q->head = n(1) != 0, so 
q->tail = n(2) 
n(2)->next = n(1) 
q->head = n(2) 

result: 
head -> n(2) -> n(1) -> 0; tail -> n(2) 

NULL하고 모든 추가 enqueue 작업 head == tail을 떠날 것이다. 하지만 지금 dequeue 당신 경우 :

struct node * to_dequeue = q->tail; // n(2) 
void * data = q->tail->data; 
struct node * trace = q->head;  // n(2) 
while(trace->next && trace->next != q->tail) // n(2) -> n(1) -> 0 
    trace = trace->next;    // trace = n(1) 
free(to_dequeue);      // free n(2) 
q->tail = trace;      // tail -> n(1) 
q->tail->next = NULL;     // already had that 

및 head 댕글 링 포인터이다.

사례 2, head은 처음에는 NULL이 아닙니다.

head -> x; tail -> y // enqueue 1 
is_empty_queue(q) returns 1 because q->head == x != 0 
q->tail = n(1) 
n(1)->next = x 
q->head = n(1) 

head -> n(1) -> x; tail -> n(1) // now enqueue 2 
is_empty_queue(q) returns 1 because q->head == n(1) 
q->tail = n(2) 
n(2)->next = n(1) 
q->head = n(2) 

head -> n(2) -> n(1) -> x; tail -> n(2) 

유일한 차이점은 큐에서이라면, trace는 야생 '포인터'x로 설정됩니다, 이제 n(1)->next != 0하고 다음 x->next이 선택되어 있지만, x가 불확실한 비트 패턴 이후, 종종 그 원인이됩니다 세그 폴트.

나는, 건설에 head 및 tail를 초기화하는 is_empty_queue을 고정하고 당신에게 작업 프로그램을 제공합니다 dequeue에 공허함 확인, 뭔가를 간과하지 않는 한.

그러나 대기열이 긴 경우, 전체 대기열을 트래버스하여의 끝에서 두 번째 요소를 찾아야하므로 대기열 해제 작업이 느립니다. tail 위치에 대기 중이고 dequeue 위치가 head 인 경우 enqueue 및 dequeue, O (1) 연산을 모두 가질 수 있습니다.