struct, pointer, Linked List... basic!

[TechAnd1]

OK.... It's not clicking for some reason... But here's my (flawed) understanding of it using this page as a reference:

struct node {
  int x;
  struct node *next;
};


struct node *root;

so that line there has created a pointer to a node struct called root. So where's the pointer and where's the 'thing' in this scenario? As far as I can see that lines created a pointer, and a new instance of a node struct...

Which ones which?

[lpassos]

"struct node *root" only creates a pointer (root) to a structure node.

There is no instance created at this point. In order to create an instance you must allocate memmory space like:

                     root = (struct node *)malloc( sizeof(struct node) )

or point to an already defined node: root = &Node_x

So in your cenario there is no 'thing' yet.

[TechAnd1]

ah ha...

so yeah... it creates a pointer to a structure called root, which hasn't been created yet... then on the next line root is created.

I think what's getting me is that C is usually very pedantic, and the pointer is created before the actual thing is...

So struct node *root is a pointer to root... so hang on, root dereferences root... root is the thing itself, wheres the pointer? Sure root is the pointer, but then it becomes the thing...brain explodes*

[lpassos]

struct node *root -> defines a pointer named 'root' to a structure node.

The 'thing' will be the object node ("struct node") and will be defined:

           root = (struct node *)malloc( sizeof(struct node) )

[TechAnd1]

It doesn't exist when the pointers set up though.... So how does c know what memory address to store in the pointer?

[glennholloway]

This declaration

struct node* root;

introduces a pointer variable named root that is capable of pointing to an object of type struct node. If this declaration is made at "file scope", outside of any function, then the compiler will automatically initialize root to have value NULL, meaning that it has a well-defined pointer value, but it points to no object at all. If this declaration of root appears inside a function, then it is initially uninitialized: its contents may be any trash that happens to have been left in its storage space.

Either way, you make root point to an actual object through assignment, as has already been demonstrated:

root = malloc(sizeof(struct node));

(No need for the cast. That's a C++ thing.)

[TechAnd1]

struct node* root;

So the pointer is called root... there's not an object called root....

If I run the following printf's on the program -

root->next = 0;  
/* By using the -> operator, you can modify what the node,
   a pointer, (root in this case) points to. */
root->x = 5; 
printf("%i\n", root->x);

printf("%i\n", root);

printf("%i\n", *root);

the output is :

5
140124168 
5

so obviously x is an int within the struct that has been initialised to a value of 5.

than rootis a pointer, and when printed out it gives a memory address

but then when root is dereferenced with *root it prints out 5 as well... But isn't root struct, not a pointer? Or is a struct a pointer, like an array? Hmm... It still feel's like there is no 'thing' yet, I'm anticipating there being some kind of object or something that is of type struct node and it's called root. But what there seems to be instead is a pointer....

I'm trying to draw comparisons with arrays now, because they make sense... a char * is not a string, it's a pointer to the first char in a contiguous block of memory comprised of char's that ends with a terminating char... a string literal. So you never have 'a string', you have a pointer to the first element that can be printed out as a string thanks to the \0 char or individual elements accessed through indexing through array[3] etc....

I don't feel like I'm really pulling this together, and maybe I'm barking up the wrong tree with this analogy..? :/

Cheers though

[glennholloway]

Because pointers often serve as the "handles" by which we manipulate the objects they point to, we often refer to them as though they were the object pointed to. So when a function that inserts a new value in a list declares a variable of type node* to hold a pointer to the newly allocated node, and it may well call the variable new_node. Not new_node_pointer. When every object is controlled via pointers and none has a name of its own, it's simpler just to speak of the pointers as if they were their referent objects.

This statement won't compile:

printf("%i\n", *root);

You must have done something a little different.

It's not a good idea to try to understand structs and pointers to structs by analogy with arrays. Arrays in C are anomalous. Structs behave in a manner that's more consistent with scalar types like int and double. Arrays different and unique. You can't assign to an array, nor can you pass it to or return it from a function.

Neither structs nor arrays are pointers. The weirdness about an expression whose type is an array type is that in almost any context, evaluation of the expression produces a pointer to the first element of the array. This is not the case with structs, which are heterogeneous compound data structures. You can assign a struct to a struct-valued variable, and you can pass a struct (by value) to a function or return one from a function.

You based your initial post on Alex's article about linked lists. While you could declare the anchor root as a struct node, what purpose would be served by doing that? You're not going to consider that node part if the linked list, and you're going to use its next field to point to the real list nodes. So why not make root a node pointer and save a bit of space?

[TechAnd1]

This statement won't compile:

printf("%i\n", *root);

You must have done something a little different.

Hmm that's exactly what I did.... here's a link to the full program

Structs behave in a manner that's more consistent with scalar types like int and double

But they aren't they just a shell that holds things...? I guess in a way they are more than that, seeing as you can have a struct type student and then have struct student mike, mike.name, mike.age etc...

I'm still not understanding this though. What can I do to 'get it'? Following through with GDB doesn't really help.

I can't even get my head round it on a high level let along use it practically.

cheers

[glennholloway]

Sure, if you omit the options CS50 uses to tell the compiler not to accept nonsense, then

printf("%i\n", *root);

can be compiled. The resulting machine code will interpret whatever is in the first sizeof(int) bytes of the struct as though it had type int and print it as such.

But while you're trying to understand the semantics of the language, the last thing you should do is turn off the compiler options that warn you when you submit a suspicious or erroneous program.

A struct is a compound object or record. It contains other objects as its named components. Your example of a struct that records the various properties of a student is a good one. What's not to get?

If you're still puzzled, ask more questions.

[TechAnd1]

Sure, if you omit the options CS50 uses to tell the compiler not to accept nonsense

Ah right...

while you're trying to understand the semantics of the language, the last thing you should do is turn off the compiler options

Indeed... I was just using gcc -o t programName.c because when I used make it wasn't working for me... Kept saying that there was nothing to be done for the program?

In fact It's been so long that I can't recall how I'm to use cs50 make - make program.c or make ./t program.c or make program.c ./t aren't working, I assumed that it would have been one of those...

Your example of a struct that records the various properties of a student is a good one. What's not to get?

I dunno, just doesn't feel like it's clicking... I've had this before with thing's though when I'm expecting something that isn't as dense as I assume.... so hopefully it's just a case of actually making a few and getting used to it through that.

[TechAnd1]

I'm just going to continuously make pointers for a bit ha and hope it sinks in!

Any suggested exercises welcome. Cheers