Is this a valid data structure??

[Dan]

I'm trying to creat a data structure, that can be either a integer,
double, string, or linked list. So I created the following, but don't
know if it is the data structure itself causing problems, or something
I am doing in the rest of the program.

This is the data structure.

struct node
{
char type;
union data
{
int integer;
double number;
char* word;
struct node* list;
}data;

struct node *next;
};


And this is the program I am using it in.

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct node
{
char type;
union data
{
int integer;
double number;
char* word;
struct node* list;
}data;

struct node *next;
};

typedef struct node node;
typedef struct node* node_ptr;


node_ptr new_node(char type);
void add_node(node_ptr destination, node_ptr source);
void print_node(node_ptr value);

int main()
{


node_ptr A;
node_ptr B;
node_ptr C;
node_ptr D;

A=new_node('I');
A->data.integer = 1;
printf("%i ", A->data.integer);

B=new_node('S');
B->data.word = "Hello";
printf("%s ", B->data.word);

C=new_node('D');
C->data.number = 1.567;
printf("%f ", C->data.number);

D=new_node('L');
add_node (D,A);
print_node(D);
}


node_ptr new_node(char type)
{
node_ptr ret_ptr = (node_ptr) malloc (sizeof(node));
ret_ptr->type = type;
switch (toupper(type))
{
case 'I':

ret_ptr->data.integer=0;
break;

case 'D':

ret_ptr->data.number=0;
break;

case 'S':

ret_ptr->data.word = "";
break;

case 'L':

ret_ptr->data.list = NULL;
break;

default:

printf("Error");
return NULL;
}

ret_ptr->next = NULL;
return ret_ptr;
}

void add_node(node_ptr destination, node_ptr source)
{
node_ptr next_ptr;
node_ptr prev_ptr;
printf("%c ", destination->type);
if (destination->type =! 'L')
{
printf("Error");
return;
}


if (destination->data.list == NULL)
{
destination->data.list = source;
printf("%c ", destination->type);
return;
}


next_ptr = destination->data.list;
while (next_ptr->data.list != NULL)
{
prev_ptr = next_ptr;
next_ptr= next_ptr->next;
}

prev_ptr->next = next_ptr;
}


void print_node(node_ptr value)
{
if (value == NULL)
return;

printf("%c ",value->type);

switch (value->type)
{
case 'I':

printf("% i", value->data.integer);
break;

case 'D':
printf("% f", value->data.number);
break;

case 'S':
printf("% s", value->data.word);
break;

case 'L':
printf("[");
print_node(value->data.list);
printf("]");
break;

default:
printf("Error");
return;
}

print_node(value->next);
}

The bug is in add node with a list, 'L', why does it change the actual
node itself. Maybe I don't see the logic but why does this line

destination->data.list = source;

change the actual destination node itself to something else. It seems
to me it would just change the list data member in the inner union to
point to the source pointer. But it seems change the actual
destination pointer itself.

Arggh...C drives me nuts.

Any help would be appreciated.

Thanks,

Dan

 

[Sheldon Simms]

I'm trying to creat a data structure, that can be either a integer,
double, string, or linked list. So I created the following, but don't
know if it is the data structure itself causing problems, or something
I am doing in the rest of the program.

This is the data structure.

struct node
{
char type;
union data
{
int integer;
double number;
char* word;
struct node* list;
}data;

struct node *next;
};


And this is the program I am using it in.

#include <stdio.h>
#include <malloc.h>

#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct node
{
char type;
union data
{
int integer;
double number;
char* word;
struct node* list;
}data;

struct node *next;
};

typedef struct node node;
typedef struct node* node_ptr;

I think you're better off not typedefing pointers. It makes it harder
to read your code. It does solve the problem of putting the '*'s in
right place, but that can also be solved by putting each variable
declaration on a line by itself, which is good to do anyway.

node_ptr new_node(char type)
{
node_ptr ret_ptr = (node_ptr) malloc (sizeof(node));

node * ret_ptr = malloc(sizeof *ret_ptr);

void add_node(node_ptr destination, node_ptr source)
{
node_ptr next_ptr;
node_ptr prev_ptr;
printf("%c ", destination->type);
if (destination->type =! 'L')

I suspect this is the problem you are talking about. It should be

if (destination->type != 'L')

You really should turn on all of the warnings on your compiler to
help you catch this sort of thing. If they are already on, then stop
ignoring them.

if (destination->data.list == NULL)
{
destination->data.list = source;
printf("%c ", destination->type);
return;
}

This looks fine

next_ptr = destination->data.list;
while (next_ptr->data.list != NULL)
{
prev_ptr = next_ptr;
next_ptr= next_ptr->next;
}

prev_ptr->next = next_ptr;

Big problems here. First, I assume you want to tack the struct
pointed to by 'source' onto the end of the list, but 'source' doesn't
ever appear in this piece of code, so that will never work.

Second, you appear to be confusing your 'head of list' pointer with
your 'link' pointers. destination->data.list is supposed to point
at the first element in a linked list, but presumably you mean to
use next_ptr->next to link the elements in the list.

Third, you don't need a previous pointer for a singly linked list
like this.

Look at this replacement code. notice that the new elements are
simply linked onto the end of the list using the 'next' pointer.

next_ptr = destination->data.list;
while (next_ptr->next != NULL)
next_ptr = next_ptr->next;

next_ptr->next = source;

void print_node(node_ptr value)
{ ...
case 'L':
printf("[");
print_node(value->data.list);
printf("]");
break;

this will only print out the value of the first element of the
list. You can write a loop to traverse the list as above, or
simply recurse (assuming the list isn't too long) like this:

case 'L':
printf("[");
print_node(value->data.list); /* print this node */
print_node(value->next); /* print the next node */
printf("]");
break;

-Sheldon

 

[Dan]

I think you're better off not typedefing pointers. It makes it harder
to read your code. It does solve the problem of putting the '*'s in
right place, but that can also be solved by putting each variable
declaration on a line by itself, which is good to do anyway.


node * ret_ptr = malloc(sizeof *ret_ptr);


I suspect this is the problem you are talking about. It should be

if (destination->type != 'L')

Oh thanks for spotting this. That is the kind of bug that would have
me pulling my hair out.

You really should turn on all of the warnings on your compiler to
help you catch this sort of thing. If they are already on, then stop
ignoring them.

if (destination->data.list == NULL)
{
destination->data.list = source;
printf("%c ", destination->type);
return;
}

This looks fine

next_ptr = destination->data.list;
while (next_ptr->data.list != NULL)
{
prev_ptr = next_ptr;
next_ptr= next_ptr->next;
}

prev_ptr->next = next_ptr;

Big problems here. First, I assume you want to tack the struct
pointed to by 'source' onto the end of the list, but 'source' doesn't
ever appear in this piece of code, so that will never work.

Second, you appear to be confusing your 'head of list' pointer with
your 'link' pointers. destination->data.list is supposed to point
at the first element in a linked list, but presumably you mean to
use next_ptr->next to link the elements in the list.

Third, you don't need a previous pointer for a singly linked list
like this.

Look at this replacement code. notice that the new elements are
simply linked onto the end of the list using the 'next' pointer.

next_ptr = destination->data.list;
while (next_ptr->next != NULL)
next_ptr = next_ptr->next;

next_ptr->next = source;

void print_node(node_ptr value)
{ ...
case 'L':
printf("[");
print_node(value->data.list);
printf("]");
break;

this will only print out the value of the first element of the
list. You can write a loop to traverse the list as above, or
simply recurse (assuming the list isn't too long) like this:

case 'L':
printf("[");
print_node(value->data.list); /* print this node */
print_node(value->next); /* print the next node */
printf("]");
break;

-Sheldon

I was thinking that the recursive call at the end of the function
would take care of this. But you're suggestion is probably better.

 

[Sheldon Simms]

Oh thanks for spotting this. That is the kind of bug that would have
me pulling my hair out.

My compiler spotted it.

 

[Floyd Davidson]

Oh thanks for spotting this. That is the kind of bug that would have
me pulling my hair out.

Format comparisons to constants with the constant first, as

if ('L' =! destination->type)

That will get an error from you compiler because it attempts
assignment to an improper lvalue, the constant 'L'. This also
works for the typo "=" where "==" was meant, though many
compilers can catch that one anyway.

Here are other examples,

if (0 != ioctl(...)) {

and

if (NULL == (fp = fopen(...))) {