12 Replies - 980 Views - Last Post: 27 October 2009 - 04:45 PM Rate Topic: -----

#1 Scorpiion   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 117
  • Joined: 23-April 09

Confused by pointers in struct

Posted 25 October 2009 - 03:44 AM

Hi, I have this struct and function:
typedef void *datapointer;

typedef struct
{
  datapointer value;
  datapointer next;
} queue_t;

/**
 * Creates empty queue
 * @return The created queue
 */
queue_t *createQueue();



And I'm trying to implement it like this:
queue_t *createQueue()
{
  queue_t *queue;
  queue->value = NULL;
  queue->next = NULL;
  return queue;
}


But it gives my segmentation fault... I don't understand how I should do this the right way, since *queue is a pointer, I should be able to do "q->XXX" to reach some of the things in the struct, at least if they had been just int values, but now that does not work, since there are pointers in there I guess. But I don't understand how to do it the right way? I have tested all combination I could think of... :/

Is This A Good Question/Topic? 0
  • +

Replies To: Confused by pointers in struct

#2 Lillefix   User is offline

  • D.I.C Head
  • member icon

Reputation: 37
  • View blog
  • Posts: 204
  • Joined: 19-September 08

Re: Confused by pointers in struct

Posted 25 October 2009 - 03:52 AM

Change
queue_t *queue;
to
queue_t *queue = new queue_t;

Also, remember to delete that pointer at the end. Such as this:

#include <cstdlib>

typedef void *datapointer;

typedef struct
{
  datapointer value;
  datapointer next;
} queue_t;

queue_t *createQueue()
{
  queue_t *queue = new queue_t;
  queue->value = NULL;
  queue->next = NULL;
  return queue;
}

int main()
{
	queue_t * queue;
	queue = createQueue();
	delete que;
	return 0;
}

This post has been edited by Lillefix: 25 October 2009 - 03:55 AM

Was This Post Helpful? 1
  • +
  • -

#3 Scorpiion   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 117
  • Joined: 23-April 09

Re: Confused by pointers in struct

Posted 25 October 2009 - 03:57 AM

Oh, you mean that I forget to allocate memory for it? :) I guess it would be "malloc" for me since I use C.. "new" is for C++? But thanks for pointing that out! ;)

EDIT: I answered before you had finished your reply..

I have this function later to do that:
void freeQueue( queue_t *q )
{
  free( q );
}


:)

This post has been edited by Scorpiion: 25 October 2009 - 03:59 AM

Was This Post Helpful? 0
  • +
  • -

#4 Lillefix   User is offline

  • D.I.C Head
  • member icon

Reputation: 37
  • View blog
  • Posts: 204
  • Joined: 19-September 08

Re: Confused by pointers in struct

Posted 25 October 2009 - 04:10 AM

Yep, I mixed some C and C++ there, but you got it anyway. Good work.
Was This Post Helpful? 0
  • +
  • -

#5 Scorpiion   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 117
  • Joined: 23-April 09

Re: Confused by pointers in struct

Posted 25 October 2009 - 04:17 AM

Thanks for a quick answer. :)
Was This Post Helpful? 0
  • +
  • -

#6 JackOfAllTrades   User is offline

  • Saucy!
  • member icon

Reputation: 6246
  • View blog
  • Posts: 24,014
  • Joined: 23-August 08

Re: Confused by pointers in struct

Posted 25 October 2009 - 07:39 AM

By the way, "hiding" your pointers through typedefs is a sure way to confusion.
Was This Post Helpful? 0
  • +
  • -

#7 Scorpiion   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 117
  • Joined: 23-April 09

Re: Confused by pointers in struct

Posted 25 October 2009 - 08:17 AM

View PostJackOfAllTrades, on 25 Oct, 2009 - 06:39 AM, said:

By the way, "hiding" your pointers through typedefs is a sure way to confusion.


Well thanks for the tip, but I have not written the queue.h file by my self, it came with the assignment. But good to know that it can create confusion.
Was This Post Helpful? 0
  • +
  • -

#8 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7233
  • View blog
  • Posts: 15,066
  • Joined: 16-October 07

Re: Confused by pointers in struct

Posted 25 October 2009 - 11:16 AM

// typedef void *datapointer;

typedef struct queue_s {
	void *value;
	// having next as a void pointer makes little sense
	struct queue_s *next;
} queue_t;

queue_t *createQueue() {
	queue_t *queue = malloc(sizeof(queue_t));
	queue->value = NULL;
	queue->next = NULL;
	return queue;
}

void freeQueue( queue_t *q ) {
	// does this queue have nodes?
	// then this is not helpful
	free( q );
}



You're defining a node. A proper queue would keep track of head and tail, for enqueue and dequeue operations. You really want another struct.

e.g.
typedef struct QueueNodeStruct {
	void *value;
	struct QueueNodeStruct *next;
} QueueNode;

typedef struct  {
	QueueNode *head, *tail;
} Queue;

// why return a pointer, extra effort
Queue createQueue() {
	Queue q = {NULL, NULL};
	return q;
}

void freeQueue( Queue *q ) {
	while(q->head!=NULL) {
		QueueNode *node = q->head;
		q->head = q->head->next;
		// do you want to free the data?
		free(node->value);
		free(node);
	}
	q->head = q->tail = NULL;
}

// this is pretty dangerous
// you might consider copying the data
//void enqueue(Queue *q, void *value);
void enqueue(Queue *q, void *value, int size);

// destroy the node, move the head, return the value pointer
void *dequeue(Queue *q);

int isEmpty(Queue *q);
int isFull(Queue *q);

// if your functions are working properly
// then you can rewrite freeQueue
void freeQueue( Queue *q ) {
	while(!isEmpty(q)) { free(dequeue(q)); }
}



Hope this helps.
Was This Post Helpful? 1
  • +
  • -

#9 Scorpiion   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 117
  • Joined: 23-April 09

Re: Confused by pointers in struct

Posted 26 October 2009 - 08:07 AM

Hi, baavgai and thanks for your reply.

About the head and tail... In my book they said that you could do a queue without an "extra" struct for head and tail? At least that's how I read it... It was using what it called a "circular list with 1-cells".. I was trying to do one like that but I had not figured out yet how it should work since my code so far does not work completely.

So is what I tried to explain a bad idea? " A proper queue would keep track of head and tail", you mean that it is better to have a struct for this? More professional?

about:
// why return a pointer, extra effort
Queue createQueue() {
		Queue q = {NULL, NULL};
		return q;
}


I have a predefined queue.h that I have to follow... (I translated the comments really fast just now might be spell errors)
#ifndef QUEUE_H
#define QUEUE_H

typedef void *datapointer;

/* Data in this struct is does by the student */
typedef struct
{

} queue_t;

/**
 * Create empty queue
 * @return The queue
 */
queue_t *createQueue();

/**
 * Remove a queue  
 * @param q The queue that should be removed
 */
void freeQueue(queue_t *q);


/* Queue ADT starts here */
	
/**
 * Insert object last in queue
 * @param q Queue in process
 * @param p Object to be processed
 */
void queue_enqueue(queue_t *q, datapointer p);

/**
 * Test if queue is empty.
 * @param q Queue
 * @return True if queue is empty
 */
int queue_isEmpty(queue_t *q);

/**
 * Give the value of first object, if the queue is not empty
 * @param q Queue in process
 * @return Object first in queue
 */
datapointer queue_front(queue_t *q);

/**
 * Remove the first element in queue, if the queue is not empty
 * @param q Queue in process 
 * @return Object that were first in queue
 */
datapointer queue_dequeue(queue_t *q);

/**
 * Return the number of elements in queue
 * @param q Queue in process
 * @return Total number of elements
 */

int queue_size(queue_t *q);

/* --------- */

#endif /*QUEUE_H*/


Was This Post Helpful? 0
  • +
  • -

#10 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7233
  • View blog
  • Posts: 15,066
  • Joined: 16-October 07

Re: Confused by pointers in struct

Posted 26 October 2009 - 09:56 AM

View PostScorpiion, on 26 Oct, 2009 - 09:07 AM, said:

In my book they said that you could do a queue without an "extra" struct for head and tail?


That's true. Why would you want to? An extra struct costs you nothing. It adds clarity and ease of use. This is the same source that recommends using a typedef for a pointer, I'm guessing.


View PostScorpiion, on 26 Oct, 2009 - 09:07 AM, said:

" A proper queue would keep track of head and tail", you mean that it is better to have a struct for this? More professional?


More standard. If you're learning about queues, the idea of a head and a tail are fundamental.

More importantly, at the expense of a struct and keeping track of an extra pointer, you gain a lot of efficiency. Let's consider your operations.

// this one is easy
// your pointer is essentally your head
// just return the value
datapointer queue_front(queue_t *q);


// So, queue_t *q is your head, how do you find your tail?
// the answer is you must iterate through all your existing nodes
// until you get to the last one, and then add the node
// there is another problem here, explained below
void queue_enqueue(queue_t *q, datapointer p);

// this should be easy, do the same as queue_front
// but also change the value of q to point to the next node
// the problem is, you can't do it with this prototype.
datapointer queue_dequeue(queue_t *q);


// it would have to look more like this
// because in addition to passing back datapointer
// you must also be able to update the value of queue_t *q
// so you need a pointer pointer
datapointer queue_dequeue(queue_t **q);



Simply, what you're showing me won't work in a normal way.

You can make it work if the first node is a "dummy" node. In such a design, your first node always exists, holds no data, and points to the actual first node. When the list is empty, it points to NULL. It is an awkward solution. Knowing your first node is a dummy node, you could set the data pointer to the tail. It's still a waste of brain cells.

In such a design, all your prototypes are valid, except this one:
// fail
// void freeQueue(queue_t *q);
// needs to be
void freeQueue(queue_t **q);


Was This Post Helpful? 1
  • +
  • -

#11 Scorpiion   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 117
  • Joined: 23-April 09

Re: Confused by pointers in struct

Posted 26 October 2009 - 10:55 AM

Okey, thanks a lot for all the facts!

As I think I said before, I have not written the queue.h file. We have got that file and are not allowed to change the function prototypes except for the struct... :(

So I guess my implementation needs to be done with a dummy then... Since I can't change the prototypes. I'we been trying to do one without a dummy but it have been hard.. And if you say the prototypes require a dummy then it's not so weird that it was hard for me do to it without one.. :P :)
Was This Post Helpful? 0
  • +
  • -

#12 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7233
  • View blog
  • Posts: 15,066
  • Joined: 16-October 07

Re: Confused by pointers in struct

Posted 26 October 2009 - 12:18 PM

View PostScorpiion, on 26 Oct, 2009 - 11:55 AM, said:

So I guess my implementation needs to be done with a dummy then... Since I can't change the prototypes.


That would be my guess. Here's a little content to get you started:
queue_t *createQueue() {
	queue_t *q = malloc(sizeof(queue_t));
	q->next = NULL;
	return q;
}

int queue_isEmpty(queue_t *q) { return (q->next == NULL); }

datapointer queue_front(queue_t *q) {
	return queue_isEmpty(q) ? NULL : q->next->value;
}



Hope this helps. Good luck.
Was This Post Helpful? 0
  • +
  • -

#13 Scorpiion   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 117
  • Joined: 23-April 09

Re: Confused by pointers in struct

Posted 27 October 2009 - 04:45 PM

Hi again, now my queue works and I thought I could post it here as a followup on the tread and also maybe get some tips on what I could have done better...

Here is the queue.h I had to follow: (execpt from the struct I should make up myself)
#ifndef QUEUE_H
#define QUEUE_H

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

typedef void *datapointer;

typedef struct queue_node_s {
  datapointer *value;
  struct queue_node_s *next;
} queue_node_t;

typedef struct queue_s {
  queue_node_t *head;
  queue_node_t *tail;
} queue_t;

queue_t *createQueue();

void freeQueue(queue_t *q);

void queue_enqueue(queue_t *q, datapointer p);

int queue_isEmpty(queue_t *q);

datapointer queue_front(queue_t *q);

datapointer queue_dequeue(queue_t *q);

int queue_size(queue_t *q);

#endif /*QUEUE_H*/



And here is my queue.c :)
#include "queue.h"

queue_t *createQueue()
{
  queue_t *q = malloc( sizeof( queue_t ) );
  q->head = NULL;
  q->tail = NULL;
  return q;
}

void freeQueue( queue_t *q )
{
  queue_node_t *pointer;
  
  if( q->head != NULL ) {
	while( q->head->next != NULL ) {
	  free( q->head->next );
	}
	free( q->head );
	free( q->tail );
	free( q );
  }
  else {
	free( q->head );
	free( q->tail );
	free( q );
  }
}

void queue_enqueue( queue_t *q, datapointer p )
{
// printf("Input pointer %d\n", p); /** TESTVARIBLE for main.c **/

  queue_node_t *pointer;
  if( q->head != NULL ) {
	pointer = q->head;
	
	while( pointer->next != NULL ) {
	  pointer = pointer->next;
	}
	
	pointer->next = malloc( sizeof( queue_node_t ) );
	pointer = pointer->next;
	pointer->next = NULL;
	pointer->value = p;
  }
  
  else if( q->head == NULL ) {
	q->tail = malloc(sizeof(queue_node_t));
	pointer = q->tail;
	pointer->value = p;
	pointer->next = NULL;
	q->head = q->tail;
  }
}

int queue_isEmpty( queue_t *q )
{
  if( q->head == NULL ) {
	return 1;
  }
  else {
	return 0;
  }
}

datapointer queue_front( queue_t *q )
{
  if( q->head != NULL ) {
	return q->head->value;
  }
}

datapointer queue_dequeue( queue_t *q )
{
  datapointer *returnValue;
  if( q->head != NULL ) {
	returnValue = q->head->value;
	free( q->head );
	q->head = q->head->next;
	return returnValue;
  }
}
  
int queue_size( queue_t *q )
{
  int size = 0;
  queue_node_t *pointer;
  
  if( q->head != NULL ) {
	pointer = q->head;
	size++;
	while( pointer->next != NULL ) {
	  pointer = pointer->next;
	  size++;
	}
  }
  
  return size;
}



If you have time and want to test it out here is my testprogram:
#include "queue.h"

void isEmpty( queue_t *q );

int main()
{
  printf("Testprogram for Queue\n");

  queue_t *umea;
  int i1 = 1, i2 = 2, i3 = 3, i4 = 4;
  datapointer *a, *b, *c, *d, *temp;
  a = &i1;
  b = &i2;
  c = &i3;
  d = &i4;
  
printf("\ncreateQueue\n");
  umea = createQueue();
printf("\nisEmpty\n");
  isEmpty( umea );
  
printf("\nSize is %d\n", queue_size( umea ));

printf("\nqueue_enqueue( umea, a )\n");
  queue_enqueue( umea, a );
  
printf("\nSize is %d\n", queue_size( umea ));
  
printf("\nqueue_enqueue( umea, b )\n");
  queue_enqueue( umea, b );
  
printf("\nSize is %d\n", queue_size( umea ));
  
printf("\nqueue_enqueue( umea, c )\n");
  queue_enqueue( umea, c );
  
printf("\nSize is %d\n", queue_size( umea ));
  
printf("\nqueue_enqueue( umea, d )\n");
  queue_enqueue( umea, d );
  
printf("\nSize is %d\n", queue_size( umea ));
  
printf("\nisEmpty\n");
  isEmpty( umea );
  
printf("\nqueue_front( umea )\n");
  temp = queue_front( umea );
  printf("%d\n", temp);
printf("queue_dequeue( umea )\n");
  temp = queue_dequeue( umea );
  printf("%d\n", temp);

printf("\nSize is %d\n", queue_size( umea ));
  
printf("\nqueue_front( umea )\n");
  temp = queue_front( umea );
  printf("%d\n", temp);
printf("queue_dequeue( umea )\n");
  temp = queue_dequeue( umea );
  printf("%d\n", temp);
  
printf("\nSize is %d\n", queue_size( umea ));
  
printf("\nqueue_front( umea )\n");
  temp = queue_front( umea );
  printf("%d\n", temp);
printf("queue_dequeue( umea )\n");
  temp = queue_dequeue( umea );
  printf("%d\n", temp);
  
printf("\nSize is %d\n", queue_size( umea ));
  
printf("\nqueue_front( umea )\n");
  temp = queue_front( umea );
  printf("%d\n", temp);
printf("queue_dequeue( umea )\n");
  temp = queue_dequeue( umea );
  printf("%d\n", temp);

printf("\nSize is %d\n", queue_size( umea ));
  
printf("\nqueue_front( umea )\n");
  temp = queue_front( umea );
  printf("%d\n", temp);
printf("queue_dequeue( umea )\n");
  temp = queue_dequeue( umea );
  printf("%d\n", temp);

  free( umea );

  return 0;
}

void isEmpty( queue_t *q )
{
  if( queue_isEmpty( q ) == 1 ) {
	printf("Queue is empty\n");
  }
  else {
	printf("Queue is not empty\n");
  }
}


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1