循环链表中的队列

Question

你好，我正在用 C 进行广度优先遍历，因此我需要实现一个队列，我想用双指针和循环链表来实现它。我知道这一定不是最简单的，但我想了解更多！

这是我的结构：

struct queue
{
    void         *val;
    struct queue *next;
};

这是我的推送：

void queue_push(struct queue **q, void *p) {
    struct queue *tmp = malloc(sizeof(struct queue));
    tmp->val = p;
    if(q)
    {
            tmp->next = (*q)->next;
            (*q)->next = tmp;
    }
    else
    {
            tmp->next = tmp;
    }
}

如果我在每一行都打印 printf，它会告诉我 "Illegal instruction (core dumped)" 在“(*q)->next = tmp;”而且我不知道我哪里出了问题。

编辑：我必须保持这个结构不变

void tree_breadth_print(struct tree *t)
{
    struct queue **q = malloc(sizeof(struct queue));
    struct tree *tmp = malloc(sizeof(struct queue));

    if(t == NULL)
    {
            printf("Tree is empty\n");
            return;
    }
    queue_push(q, t);

    while(!queue_is_empty(*q))
    {
            tmp = queue_pop(q);
            printf("%d", tmp->key);

            if(tmp->left != NULL)
                    queue_push(q, tmp->left);
                    printf("tmp->left->key = %d \n", tmp->left->key);
            if(tmp->right != NULL)
                    queue_push(q, tmp->right);
    }
    free(q);
    printf("\n");
}

树结构很简单：

struct tree {
    int           key;
    struct tree  *left, *right;
};

Answer 1

您可以改用此结构来编写您的程序。我将稍微更改您使用的名称：考虑以下结构：

struct Node{
    int val;//supposing the type is int
    struct Node *next;
    struct Node *prev;
};typedef struct Node Node;
//
//
//
typedef struct queue{
    Node *head;
    Node *tail;
}//got a doubly queue

现在推送一个元素：

void queue_push(queue *q,int value)
{
    Node *n=(Node*)malloc(sizeof(Node));
    n->val=value;
    n->prev=NULL;
    if(q->head==NULL && q->tail==NULL)
    {
        n->next=NULL;
        q->head=n
        q->tail=n;
    }
    else
    {
        n->next=q->head;
        n->head->prev=n;
        q->head=n;
    }
}

我现在不知道我是否能帮助你学到新东西，但不管怎样，我不介意尝试一下，我认为它会奏效。

Answer 2

这是我的问题的答案：

void queue_push(struct queue **q, void *p) {
    struct queue *tmp = malloc(sizeof(struct queue));
    tmp->val = p;
    if(*q)
    {
        tmp->next = (*q)->next;
        (*q)->next = tmp;
    }
    else
        tmp->next = tmp;
    *q = tmp;
}

我也把queue_pop送给大家，有兴趣的可以用！

void* queue_pop(struct queue **q) {
    struct queue *tmp = (*q)->next;
    void *x = tmp->val;
    if(tmp == tmp->next)
        *q = NULL;
    else
        (*q)->next = tmp->next;
    free(tmp);
    return x;
}

循环链表中的队列

Queue in circular linked list

c

queue

linked-list