pointers to struct members

E

Emanuele Blanco

Hi there,

I just compiled a program that uses linked lists (needed it as an homework
for my Programming course at University). It works flawlessly, even if I
notice a thing. Here's my linked list declaration:

struct node {
float item;
struct node *next;
};

typedef struct node *list;

I need a function that removes a node in that list, without checking the
emptyness of the list. So here's my code:

void remove_key(list *lista, float key) {
list temp=*lista;
if (temp->item == key) {
*lista=temp->next;
free(temp);
}
else
remove_key((list *)(temp->next), key);
}

My question is: I needed the casting to list * to make the recursive call
work. I wasn't able to get it work using a syntax like
remove_key(*(temp->next), key). There's a proper syntax to point to a struct
member, or do I need the cast ? Compiling with gcc makes the incompatible
parameter type error.

Thanks in advance and sorry for my English.
 
B

Barry Schwarz

Hi there,

I just compiled a program that uses linked lists (needed it as an homework
for my Programming course at University). It works flawlessly, even if I
notice a thing. Here's my linked list declaration:

struct node {
float item;
struct node *next;
};

typedef struct node *list;

I need a function that removes a node in that list, without checking the
emptyness of the list. So here's my code:

void remove_key(list *lista, float key) {
list temp=*lista;
if (temp->item == key) {
*lista=temp->next;
free(temp);
}
else
remove_key((list *)(temp->next), key);
}

My question is: I needed the casting to list * to make the recursive call
work. I wasn't able to get it work using a syntax like
remove_key(*(temp->next), key). There's a proper syntax to point to a struct
member, or do I need the cast ? Compiling with gcc makes the incompatible
parameter type error.

The compiler diagnostic is not the problem. It is a description of
the problem. While the cast silences the compiler, it does nothing
about the problem itself.

remove_key requires a pointer to pointer to struct as its first
argument. That means when you dereference your argument, the value
you end up with is a pointer to struct. Phrased another way, the
value in lista is an address. If you examine the appropriate number
of bytes at that address, you will find another address. It is this
second address which identifies the location of the struct.

What did your code do? You took the value of temp->next which is a
pointer to struct, that is the address of a struct. You told the
compiler: don't change the value but convert it to the form of pointer
to pointer to struct. (On most machines, the form of a pointer to
struct and pointer to pointer to struct are the same. However, the
compiler recognizes a difference between struct* and struct** so the
cast makes the compiler happy and also performs whatever magic is
necessary in case the two forms are not the same.) You then pass this
value to the next incarnation (or whatever the correct term is for the
target of the recursive call) of remove_key. remove_key knows that
the (new) value of lista points to address. Unfortunately it doesn't.
The new value of lista points to exactly what the old value of
temp->next pointed to. Namely, another instance of the struct. It
turns out that the bytes at the beginning of the struct, which
remove_key is trying to interpret as an address, are actually part of
the float that is the first item in the struct. Welcome to undefined
behavior.

The moral of the story is you cannot lie to your compiler. When you
use a cast, what you are really saying to the compiler is that even if
this expression doesn't look like this new type, it really is.
Therefore, don't change the value but do "reformat" it so it "looks
like" the type specified. If this is not the situation in your code,
then the cast is the wrong solution.

remove_key requires a value (C always passes by value) that points to
a pointer. The proper method of constructing such a value when all
you have is the original pointer is the "address of" operator, the &.
What your code needs is
remove_key(&(temp->next), key);
Since -> has higher precedence than &, the internal parentheses are
superfluous but some like to keep them for the visual hint.

The next question is: why are you doing this recursively? It is
relatively simple (and much easier to debug) to do this with a loop.


<<Remove the del for email>>
 
E

Emanuele Blanco

"Barry Schwarz" <[email protected]> ha scritto nel messaggio

[CUT]
remove_key requires a value (C always passes by value) that points to
a pointer. The proper method of constructing such a value when all
you have is the original pointer is the "address of" operator, the &.
What your code needs is
remove_key(&(temp->next), key);
Since -> has higher precedence than &, the internal parentheses are
superfluous but some like to keep them for the visual hint.

Thanks for explanations. I'm new into managing dynamic data structures (like
linked lists) and programming it in C, as I'm studying Computer Sciences.
Now I understand it. I was not sure about the casting, but it worked and
that was good. But not good enough to live without asking :) I used to
manage passing pointers with & operator, but haven't thought about it in
this case. It's really kind of you. Thanks a lot.
The next question is: why are you doing this recursively? It is
relatively simple (and much easier to debug) to do this with a loop.

I'm also learning programming using recursion ... and a code like this is
also simple in the recursive way.
 
C

Christopher Benson-Manica

Emanuele Blanco said:
I'm also learning programming using recursion ... and a code like this is
also simple in the recursive way.

If this is your first attempt at recursion, you might start with
something simpler, say the canonical factorial program.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top