キュー/デキューの奇妙さ？

Question

私はvoidポインターを保持するキューを実装して、どのタイプのデータでも一般化できるようにする作業を行ってきました。私は現在、奇妙な問題に直面していますが、ノードをデキューしてリストのサイズを減らしても、期待するノードは返されません。デキュー操作でfree（）の呼び出しを省略すると、これが修正されますが、デキューされたノードを解放したいので、これは望ましくありません。任意のヒント？

試運転：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は不定ビットパターンだったので、多くの場合、その原因となりますsegfault。

私は、建設に headと tailを初期化 is_empty_queueを固定し、あなたの作業プログラムを提供します dequeueに空虚をチェックし、何かを見落としていない限り。

しかし、キューが長い場合は、最後の最後の要素を見つけるためにキュー全体を移動する必要があるため、デキュー操作は遅くなりますtail。 tailの位置にエンキューする場合はenqueueとdequeue、O（1）の操作はheadからdequeueにすることができます。