CODEWITHSUNDEEP
clinked-listqueue
BeGreen
BeGreen

Reputation: 941

Queue in circular linked list

Hello i'l doing a Breadth First Traversal in C, thus I needed to implement a Queue, I wanted to implement it with double pointers and in a circular linked list. I know it must not be the simplest, but I want to learn more!

Here is my struct:

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

Here is my Push:

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;
    }
}

If I make printf at each lines it tells me "Illegal instruction (core dumped)" at "(*q)->next = tmp;" And I don't know what i'm going wrong.

Edit: I have to keep this struct unchanged

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");
}

The Tree struct is simple:

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

Upvotes: 1

Views: 494

Answers (2)

BeGreen
BeGreen

Reputation: 941

Here is the answer to my Question:

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;
}

I'll give you the queue_pop too if people are interested, feel free to use!

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;
}

Upvotes: 0

A. Harkous
A. Harkous

Reputation: 252

you may follow this structure for your program instead. I will change the names you used slightly: Consider the following structures:

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

now to push an element:

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;
    }
}

I don`t now if I helped you learn something new, but any way it does not heart to try this out, I think it will work.

Upvotes: 0

Related Questions