Linked List problem.

[Ben]

Hi,

I am a newbie with C and am trying to get a simple linked list working
for my program. The structure of each linked list stores the char
*data and *next referencing to the next link. The problem I get is
that I am trying to link a struct that I have defined and its refusing
to link. I have tried casting my struct into char * but attempts to
cast it back to its original struct to access its contents only seg
faults.

I'd attempt to change the type of data in the linked list to that my
struct but that just doesnt seem right.
Any advice is appreciated.

Thanks
Ben

[Mike Wahler]

Re: Linked List problem.


"Ben" <ben19777@hotma il.com> wrote in message
news:8748465b.0 410100939.77407 a1a@posting.goo gle.com...[color=blue]
> Hi,
>
> I am a newbie with C and am trying to get a simple linked list working
> for my program. The structure of each linked list stores the char
> *data and *next referencing to the next link. The problem I get is
> that I am trying to link a struct that I have defined and its refusing
> to link. I have tried casting my struct into char * but attempts to
> cast it back to its original struct to access its contents only seg
> faults.
>
> I'd attempt to change the type of data in the linked list to that my
> struct but that just doesnt seem right.
> Any advice is appreciated.[/color]

Your bug is on line 42.

-Mike

[Tim Rentsch]

Re: Linked List problem.

ben19777@hotmai l.com (Ben) writes:
[color=blue]
> I am a newbie with C and am trying to get a simple linked list working
> for my program. The structure of each linked list stores the char
> *data and *next referencing to the next link. The problem I get is
> that I am trying to link a struct that I have defined and its refusing
> to link. I have tried casting my struct into char * but attempts to
> cast it back to its original struct to access its contents only seg
> faults.
>
> I'd attempt to change the type of data in the linked list to that my
> struct but that just doesnt seem right.
> Any advice is appreciated.[/color]


First, don't do any casting. Casting is unnecessary for coding a
simple linked list, and if casting is unnecessary it usually is best
to avoid it.


Second, start with defining the type, perhaps something like this:

typedef struct node_struct_tag *List, ListElement;

struct node_struct_tag {
char *data;
List next;
};


Now, a simple function:

unsigned int
list_length( List head_of_list ){
List remainder; unsigned int result;

remainder = head_of_list;
result = 0;

while( remainder != 0 ){
result++;
remainder = remainder->next;
}

return result;
}


A function for list formation:

List
lisp_style_cons ( char *value, List tail ){
List result;

result = malloc( sizeof( *result ) );
assert( result != 0 );

result->data = value;
result->next = tail;

return result;
}


A function for more typical C-style manipulation:

void
splice_one_elem ent_into_list( List element, List *list_address ){
assert( list_address != 0 );
assert( element != 0 );

element->next = *list_address;
*list_address = element;
}


That function might be used in a function that inserts into
a sorted list:

void
insert_into_sor ted_list( List element, List *sorted_list_ad dress ){
List *insertion_poin t;

assert( element != 0 );
assert( sorted_list_add ress != 0 );

insertion_point = sorted_list_add ress;
while( *insertion_poin t != 0 ){
if( strcmp( (*insertion_poi nt)->data, element->data ) > 0 ){
break;
}
insertion_point = & (*insertion_poi nt)->next;
}

splice_one_elem ent_into_list( element, insertion_point );
}


Before trying to compile this code, read through it and make sure
you understand what you think it's doing and why.

If you want to try compiling, first find the appropriate headers for
assert(), malloc() and strcmp(), and #include them.

The functions above almost certainly aren't what you want, but if
you can understand these you should be able to write the functions
that you do want.

Disclaimer: the code above has not been compiled or even syntax
checked (except manually by myself). I'm confident the many
readers of the NG will graciously report any bonehead errors
I've made. :)

[Al Bowers]

Re: Linked List problem.



Tim Rentsch wrote:[color=blue]
> ben19777@hotmai l.com (Ben) writes:
>
>[color=green]
>>I am a newbie with C and am trying to get a simple linked list working
>>for my program. The structure of each linked list stores the char
>>*data and *next referencing to the next link. The problem I get is
>>that I am trying to link a struct that I have defined and its refusing
>>to link. I have tried casting my struct into char * but attempts to
>>cast it back to its original struct to access its contents only seg
>>faults.
>>
>>I'd attempt to change the type of data in the linked list to that my
>>struct but that just doesnt seem right.
>>Any advice is appreciated.[/color]
>
>[/color]
[color=blue]
>
> typedef struct node_struct_tag *List, ListElement;
>
> struct node_struct_tag {
> char *data;
> List next;
> };
>
>[/color]

....snip....
[color=blue]
> List
> lisp_style_cons ( char *value, List tail ){
> List result;
>
> result = malloc( sizeof( *result ) );
> assert( result != 0 );
>
> result->data = value;
> result->next = tail;
>
> return result;
> }
>[/color]

....snip...
[color=blue]
>
> Disclaimer: the code above has not been compiled or even syntax
> checked (except manually by myself). I'm confident the many
> readers of the NG will graciously report any bonehead errors
> I've made. :)[/color]

I haven't noticed in bonehead errors but function lisp_style_cons ,
listed above, scares me. The function requires that 'value'
point to storage allocated somewhere else. I prefer to encapsulate
the allocation and assignment in the function that creates the node.
Examples below:

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

typedef struct NODE
{
char *data;
struct NODE *next;
} NODE;

unsigned NodesInList( NODE *p );
int AddListHead( NODE **p, const char *s );
int AddListTail( NODE **p, const char *s );
void PrintList( NODE *p );
void FreeList( NODE **p );

int main(void)
{
NODE *head = NULL;

AddListTail(&he ad,"Hello World");
AddListTail(&he ad,"Goodbye World");
AddListHead(&he ad,"The list head");
printf("There are %u Nodes in the list.\n",
NodesInList(hea d));
PrintList(head) ;
FreeList(&head) ;
printf("\nFreed the list. Now there are %u "
"nodes in the list.\n",NodesI nList(head));
return 0;
}

unsigned NodesInList( NODE *p )
{
unsigned nelem;

for(nelem = 0; p; p = p->next,nelem++ ) ;
return nelem;
}

int AddListHead( NODE **p, const char *s )
{
NODE *new;

if((new = malloc(sizeof *new)) == NULL) return 0;
if((new->data = malloc(strlen(s )+1)) == NULL)
{
free(new);
return 0;
}
strcpy(new->data,s);
new->next = *p;
*p = new;
return 1;
}

int AddListTail( NODE **p, const char *s )
{
NODE **tmp, *new;

if((new = malloc(sizeof *new)) == NULL) return 0;
if((new->data = malloc(strlen(s )+1)) == NULL)
{
free(new);
return 0;
}
strcpy(new->data,s);
new->next = NULL;
for(tmp = p; *tmp != NULL;tmp = &(*tmp)->next) ;
*tmp= new;
return 1;
}

void PrintList( NODE *p )
{
unsigned i;

for(i = 1 ; p; p = p->next,i++)
printf("Node %u: Data is \"%s\"\n",i, p->data);
return;
}

void FreeList( NODE **p )
{
NODE *tmp;

for( ; *p; *p = tmp)
{
tmp = (*p)->next;
free((*p)->data);
free(*p);
}
return;
}



--
Al Bowers
Tampa, Fl USA
mailto: xabowers@myrapi dsys.com (remove the x to send email)

http://www.geocities.com/abowers822/

[Ben]

Re: Linked List problem.

Hello,

Dont quite understand how your code fixes my query.
I already have a working, linkedlist.c. I know it works because I have
tested it using strings as data.
My linkedlist has the following struct

struct link {
char *data
link *next
}
#excluding respective typedef statements

#enqueue adds a new element to list
enqueue(*link, char *data)

In my main.c program.
I have another structure which i want to put into a linked list

struct people {
char *name
int *age
char *address
}

Now I have included my linkedlist.c into my main.c
However I cant do enqueue(peoplel ist, *newpeople)
where peoplelist is a *link and *newpeople is a people
because gcc complains that it wants char instead of people

and enqueue(peoplel ist, (char *) newpeople) only gives me
*name when i try to access the element again (because of the string
terminator?). It also wont let me cast it back to (people) and wont
let me access within newpeople (eg newpeople.age).

I was wondering if there was a way to allow linkedlist to use people
as an element but without changing the struct link's char *data to
people *data
Is this possible or is there another better solution?

Tim Rentsch <txr@alumnus.ca ltech.edu> wrote in message news:<kfn3c0mct 19.fsf@alumnus. caltech.edu>...[color=blue]
> ben19777@hotmai l.com (Ben) writes:
>[color=green]
> > I am a newbie with C and am trying to get a simple linked list working
> > for my program. The structure of each linked list stores the char
> > *data and *next referencing to the next link. The problem I get is
> > that I am trying to link a struct that I have defined and its refusing
> > to link. I have tried casting my struct into char * but attempts to
> > cast it back to its original struct to access its contents only seg
> > faults.
> >
> > I'd attempt to change the type of data in the linked list to that my
> > struct but that just doesnt seem right.
> > Any advice is appreciated.[/color]
>
>
> First, don't do any casting. Casting is unnecessary for coding a
> simple linked list, and if casting is unnecessary it usually is best
> to avoid it.
>
>
> Second, start with defining the type, perhaps something like this:
>
> typedef struct node_struct_tag *List, ListElement;
>
> struct node_struct_tag {
> char *data;
> List next;
> };
>
>
> Now, a simple function:
>
> unsigned int
> list_length( List head_of_list ){
> List remainder; unsigned int result;
>
> remainder = head_of_list;
> result = 0;
>
> while( remainder != 0 ){
> result++;
> remainder = remainder->next;
> }
>
> return result;
> }
>
>
> A function for list formation:
>
> List
> lisp_style_cons ( char *value, List tail ){
> List result;
>
> result = malloc( sizeof( *result ) );
> assert( result != 0 );
>
> result->data = value;
> result->next = tail;
>
> return result;
> }
>
>
> A function for more typical C-style manipulation:
>
> void
> splice_one_elem ent_into_list( List element, List *list_address ){
> assert( list_address != 0 );
> assert( element != 0 );
>
> element->next = *list_address;
> *list_address = element;
> }
>
>
> That function might be used in a function that inserts into
> a sorted list:
>
> void
> insert_into_sor ted_list( List element, List *sorted_list_ad dress ){
> List *insertion_poin t;
>
> assert( element != 0 );
> assert( sorted_list_add ress != 0 );
>
> insertion_point = sorted_list_add ress;
> while( *insertion_poin t != 0 ){
> if( strcmp( (*insertion_poi nt)->data, element->data ) > 0 ){
> break;
> }
> insertion_point = & (*insertion_poi nt)->next;
> }
>
> splice_one_elem ent_into_list( element, insertion_point );
> }
>
>
> Before trying to compile this code, read through it and make sure
> you understand what you think it's doing and why.
>
> If you want to try compiling, first find the appropriate headers for
> assert(), malloc() and strcmp(), and #include them.
>
> The functions above almost certainly aren't what you want, but if
> you can understand these you should be able to write the functions
> that you do want.
>
> Disclaimer: the code above has not been compiled or even syntax
> checked (except manually by myself). I'm confident the many
> readers of the NG will graciously report any bonehead errors
> I've made. :)[/color]

[Al Bowers]

Re: Linked List problem.



Ben wrote:[color=blue]
> Hello,
>
> Dont quite understand how your code fixes my query.
> I already have a working, linkedlist.c. I know it works because I have
> tested it using strings as data.
> My linkedlist has the following struct
>
> struct link {
> char *data
> link *next
> }
> #excluding respective typedef statements
>
> #enqueue adds a new element to list
> enqueue(*link, char *data)[/color]

This doesn't look right. You need to provide the definition
of function enqueue plus code on how you use it. Provide actual
code, not pseudo code.
[color=blue]
>
> In my main.c program.
> I have another structure which i want to put into a linked list
>
> struct people {
> char *name
> int *age
> char *address
> }
>
> Now I have included my linkedlist.c into my main.c
> However I cant do enqueue(peoplel ist, *newpeople)
> where peoplelist is a *link and *newpeople is a people
> because gcc complains that it wants char instead of people
>
> and enqueue(peoplel ist, (char *) newpeople) only gives me
> *name when i try to access the element again (because of the string
> terminator?). It also wont let me cast it back to (people) and wont
> let me access within newpeople (eg newpeople.age).[/color]

It will not let you because it is erroneous.
[color=blue]
>
> I was wondering if there was a way to allow linkedlist to use people
> as an element but without changing the struct link's char *data to
> people *data
> Is this possible or is there another better solution?[/color]

The solution requires you to change your struct link.

Perhaps:

struct link
{
struct people data;
struct link *next;
};

or
struct link
{
struct people *data;
struct link *next;
};

Then rewrite function enqueue and other functions that manipulates
the link list. A simple cast will not work.

Example:

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

struct people
{
char *name;
unsigned age;
char *address;
};

typedef struct NODE
{
struct people data;
struct NODE *next;
} NODE;

unsigned NodesInList( NODE *p );
int enqueue( NODE **p, const char *name, unsigned age,
const char *addr );
void PrintList( NODE *p );
void FreeList( NODE **p );

int main(void)
{
NODE *head = NULL;

enqueue(&head," George Washington",46,
"2000 Adams Blvd\nWashingto n DC");
enqueue(&head," Bill Clinton", 43,
"152 E. Hickory Ave\nLittle Rock, AR");
enqueue(&head," George Bush",37,
"1401 Vine St\nHouston, TX");
printf("There are %u Nodes in the list.\n\n",
NodesInList(hea d));
PrintList(head) ;
FreeList(&head) ;
printf("\nFreed the list. Now there are %u "
"nodes in the list.\n",NodesI nList(head));
return 0;
}

unsigned NodesInList( NODE *p )
{
unsigned nelem;

for(nelem = 0; p; p = p->next,nelem++ ) ;
return nelem;
}

int enqueue( NODE **p, const char *name, unsigned age,
const char *addr )
{
NODE **tmp, *new;

if((new = malloc(sizeof *new)) == NULL) return 0;
if((new->data.name = malloc(strlen(n ame)+1)) == NULL)
{
free(new);
return 0;
}
if((new->data.address = malloc(strlen(a ddr)+1)) == NULL)
{
free(new->data.name);
free(new);
return 0;
}
strcpy(new->data.name, name);
strcpy(new->data.address , addr);
new->data.age = age;
new->next = NULL;
for(tmp = p; *tmp != NULL;tmp = &(*tmp)->next) ;
*tmp= new;
return 1;
}

void PrintList( NODE *p )
{
unsigned i;

for(i = 1 ; p; p = p->next,i++)
printf("Node %u:\n%s Age %u\n%s\n\n",i,p->data.name,
p->data.age, p->data.address );
return;
}

void FreeList( NODE **p )
{
NODE *tmp;

for( ; *p; *p = tmp)
{
tmp = (*p)->next;
free((*p)->data.name);
free((*p)->data.address );
free(*p);
}
return;
}

--
Al Bowers
Tampa, Fl USA
mailto: xabowers@myrapi dsys.com (remove the x to send email)

http://www.geocities.com/abowers822/

[Tim Rentsch]

Re: Linked List problem.

Al Bowers <xabowers@rapid sys.com> writes:
[color=blue]
> Tim Rentsch wrote:
> [some cutting here]
>[color=green]
> > List
> > lisp_style_cons ( char *value, List tail ){
> > List result;
> >
> > result = malloc( sizeof( *result ) );
> > assert( result != 0 );
> >
> > result->data = value;
> > result->next = tail;
> >
> > return result;
> > }
> >
> > [some cutting here][/color]
>
> I haven't noticed in bonehead errors but function lisp_style_cons ,
> listed above, scares me. The function requires that 'value'
> point to storage allocated somewhere else. I prefer to encapsulate
> the allocation and assignment in the function that creates the node.
> [Example code omitted][/color]

I take your point. What is the "right" way to do storage allocation
in C is a non-trivial topic, and the pattern shown above certainly
isn't typical. I thought it would help illustrate a linked-list
function that the person asking the question might be familiar with
and so be helpful in that way. The storage allocations issues were
definitely glossed over in my posting, so as not to overcomplicate the
example.

[Tim Rentsch]

Re: Linked List problem.

ben19777@hotmai l.com (Ben) writes:
[color=blue]
> Hello,
>
> Dont quite understand how your code fixes my query.
> I already have a working, linkedlist.c. I know it works because I have
> tested it using strings as data.
> My linkedlist has the following struct
>
> struct link {
> char *data
> link *next
> }
> #excluding respective typedef statements
>
> #enqueue adds a new element to list
> enqueue(*link, char *data)
>
> In my main.c program.
> I have another structure which i want to put into a linked list
>
> struct people {
> char *name
> int *age
> char *address
> }
>
> Now I have included my linkedlist.c into my main.c
> However I cant do enqueue(peoplel ist, *newpeople)
> where peoplelist is a *link and *newpeople is a people
> because gcc complains that it wants char instead of people
>
> and enqueue(peoplel ist, (char *) newpeople) only gives me
> *name when i try to access the element again (because of the string
> terminator?). It also wont let me cast it back to (people) and wont
> let me access within newpeople (eg newpeople.age).
>
> I was wondering if there was a way to allow linkedlist to use people
> as an element but without changing the struct link's char *data to
> people *data
> Is this possible or is there another better solution?[/color]

If you've been reading comp.lang.c for a while then you know that
people with questions are told to post actual code rather than
summaries or descriptions. And, if the actual code is lots of lines,
to prepare an example as reasonably small as they can that still
demonstrates the problem they want to ask about.

There are various reasons for doing this, some having to do with
courtesy and politeness, some having to do with NG readers being able
to actually supply an answer, and some having to do with maximizing
*your* value from any answers you might get.

A. Working on preparing the posting might let you see the answer
yourself. That's more valuable to you than if it has to be explained.

B. "[gcc] won't let me cast it back." The problem with this statement
is almost everyone reading it won't know what you mean. Of course,
the few readers of CLC who are true mindreaders will, but they
generally don't like posting answers. [:)]

C. I appreciate that you probably think you're making it easier on
people by posting only a short description rather than some long code
body, etc. Most readers, though, are frustrated because they don't
have enough information to answer the question, and it seems obvious
to them that there isn't enough information to answer the question.
So, to really make it easier for the readers, put in the time to get
*real code* that illustrates the problem in as short a space as
you can.

Based on what you wrote, it seems clear that you're confused
about _something_ related to casting and/or pointers; beyond
that, I'm not going to guess.

Oh, one more thing - I think I'd be remiss if I didn't put in
a reminder to read the comp.lang.c FAQ for starters. I'm sure
these points must be covered in there somewhere.

[Mike Deskevich]

Re: Linked List problem.

send the code you're trying to run (or better - a simplified version
that exhibits the problems you're having). it's impossible to help
unless we know where you're coming from.

[Ben]

Re: Linked List problem.

"Mike Deskevich" <mikedeskevich@ gmail.com> wrote in message news:<109755210 5.883148.133290 @z14g2000cwz.go oglegroups.com> ...[color=blue]
> send the code you're trying to run (or better - a simplified version
> that exhibits the problems you're having). it's impossible to help
> unless we know where you're coming from.[/color]

Thanks to all who have been advising and sorry for the long overdue reply.
My question is all about casting and pointers and what conditions allow it.

Please correct my following assumptions,

1) Int can be casted into a char
int i=0;
char a;
a=(char *) i;


2) Structure casted into an array of char
typedef struct {
char name[20];
int age;
int id;
} person;

person p = (person *) malloc(sizeof(p erson));
p.name="hello";
p.age=2;
p.id=2;

char *a;
a=(char *)p;

[Richard Bos]

Re: Linked List problem.

ben19777@hotmai l.com (Ben) wrote:
[color=blue]
> Please correct my following assumptions,
>
> 1) Int can be casted into a char
> int i=0;
> char a;
> a=(char *) i;[/color]

This is confused. _Either_ you assign an int to a char, in which case
you don't need the cast (and the cast as written is wrong), _or_ you
assign it to a char * (and the declaration of a is wrong), in which
case:
Yes, you can, but the result is not necessarily meaningful. It may not
be a valid pointer at all; it may not point to memory you can write to
or even read; and even when it does, it may not point where you expect
it to point. In particular, in the above example, a need _not_ be a null
pointer.
At least a char * is always correctly aligned. Had a been an int *, for
example, it might have been an incorrectly aligned pointer.
[color=blue]
> 2) Structure casted into an array of char
> typedef struct {
> char name[20];
> int age;
> int id;
> } person;
>
> person p = (person *) malloc(sizeof(p erson));
> p.name="hello";
> p.age=2;
> p.id=2;
>
> char *a;
> a=(char *)p;[/color]

No. You cannot cast a struct into a pointer. And what would you do this
for, anyway? Do you suppose that the bytes represented by "hello"
somehow form a valid pointer?
I suspect you meant to access the struct itself _through_, not _as_, a
pointer to char. In that case, you need to do

a = (char *)&p;

which is perfectly legal, and can be useful - though rarely. Beware the
padding bytes!

Richard