Array of Structurer in C

Question

I was just brushing my pointer concepts and it seems its really messed up over time.

I was trying to implement BFS in binary tree.

Pseudo Code :

1) tempNode = root node
2) while tempNode is not null
       print data at tempNode
       enqueue left and right child
       tempNode = dequeue

Here's my code :

#include <stdio.h>
#include <stdlib.h>

#define MAX_Q_SIZE 100
/**
 * Using Queue to keep track of next nodes to be visited
 */

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

struct node *createQueue(int *front, int *rear)
{
    struct node *queue = (struct node*)malloc(sizeof(struct node) * MAX_Q_SIZE);
    *front = *rear = 0;
    return queue;
}

void enQueue(struct node *queue, int *rear, struct node *newNode)
{
    queue[*rear].data = newNode->data;
    queue[*rear].left = newNode->left;
    queue[*rear].right = newNode->right;
    (*rear)++;
}

struct node *deQueue(struct node *queue, int *front)
{
    (*front)++;
    return &queue[*front - 1];
}

struct node *newNode(int data)
{
    struct node *node = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void printBFS(struct node *root)
{
    int front,rear;
    struct node *queue = createQueue(&front, &rear);
    struct node *tempNode = root;

    while(tempNode != NULL)
    {
        printf("%d ",tempNode->data);

        if(tempNode->left != NULL)
            enQueue(queue,rear,tempNode->left);
        if(tempNode->right != NULL)
            enQueue(queue,rear,tempNode->right);
        tempNode = deQueue(queue,front);
    }
}

int main()
{
    struct node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printBFS(root);
    return 0;
}

I am getting following 4 types of warnings :

BFS2.c: In function ‘printBFS’:
BFS2.c:60:13: warning: passing argument 2 of ‘enQueue’ makes pointer from integer without a cast [enabled by default]
             enQueue(queue,rear,tempNode->left);
             ^
BFS2.c:23:6: note: expected ‘int *’ but argument is of type ‘int’
 void enQueue(struct node *queue, int *rear, struct node *newNode)
      ^

BFS2.c:63:9: warning: passing argument 2 of ‘deQueue’ makes pointer from integer without a cast [enabled by default]
         tempNode = deQueue(queue,front);
         ^
BFS2.c:34:14: note: expected ‘int *’ but argument is of type ‘int’
 struct node *deQueue(struct node *queue, int *front)

Can anyone please help me to clarify the doubts as to why I am getting the warnings. I am unable to figure out the problems here. :(

Answer 1

You are passing int variables where int* (pointer to int) is expected. Pass the address of an int variable with & the address of operator. Multiple examples :

enQueue(queue, &rear, tempNode->left);

enQueue(queue, &rear, tempNode->right);

tempNode = deQueue(queue, &front);

As David has pointed out, the program will crash (segmentation fault). You may want to rethink the design of deQueue and/or what should happen if both tempNode->left and tempNode->right are NULL.

Answer 2

Instead of passing front and rear to enQueue() and deQueue(), pass &front and &rear. The & (address-of operator) takes the address of the variable. Since both front and rear are ints, this operator will create the correct result, an int *.

As an aside: don't cast the return value of malloc().

Answer 3

Your immediate pointer problems come from attempting to pass an int as a pointer:

int front,rear;
    ...
        enQueue(queue,&rear,tempNode->left);
//         enQueue(queue,rear,tempNode->left);

You have the same issue with deQueue immediately following. However, you have larger issues to deal with. Once you fix the pointer issues you will be faced with a Segmentation fault..

And to not leave you hanging, you simply need to go back and rework your queue implementation, it is a wreck. You will generate a Segmentation fault because your value for front in deQueue grows unchecked until i reaches a value of 100 and you attempt to write beyond the end of your MAX_Q_SIZE block of memory.

If you are brushing up on pointers, then don't torture pointers to try and shoehorn them into array syntax. There is no need for passing struct node *queue and then attempting to find array index syntax that will work:

queue[*rear].right = newNode->right;

when a simple pointer expression will do:

(queue + *rear)->right = newNode->right;

The same applies to:

return (queue + *front - 1);  // syntax only your queue logic need fixing

This will make your code much more readable and reduce the chance for error when you pass pointers but then try and make the pointer work with something like:

return &queue[*front - 1];