C++ Pointers & Structures Question

[mosdef]

Let's say I want to create a linked list of strucutres, is the following format correct?

struct S {
int i;
S* next;
};

And when I create/delete the pointer, what would I do? The following?

void main() {
S* blah = ???;
/* */
delete blah; ???
}

Thanks!

-mosdef

 

[GoldenBear]

<< S* next; >>

Should be

S *next;

I'm not sure about the second part, but I think it's something like

new *s...I don't know, should have NEW in it though I think.

 

[mosdef]

I'm pretty sure whitespace doesn't matter, but I'll make that change. Maybe it's S *blah = new S(); ?

-mosdef

 

[mjquilly]

<< S *blah = new S(); >>



you don't need the () - just:

S *blah = new S;

 

[GoldenBear]

<< I'm pretty sure whitespace doesn't matter, but I'll make that change. Maybe it's S *blah = new S(); ?

-mosdef >>

Hmm, don't think you need the (). But I THINK that's right otherwise..

And the placement of the * does make a difference..trust me =-)

 

[mosdef]

Alright, thanks guys!

-mosdef

 

[mosdef]

Oh, and to delete?

S *blah = new S;
delete blah;

-mosdef

 

[mosdef]

Oh one thing I forgot, when I pass the pointer when do I use the *?

void func1(S ?blah) { /* */ }

void main() {
S *blah = new S;
func1(?blah)
delete ?blah;
}

Which '?' should I replace with '*'? Also, when would I use &amp; (address)?

-mosdef

 

[mosdef]

^

-mosdef

 

[HigherGround]

1. operator placement does not make any difference, it's a style preference as the parser will pick up the preceding and trailing white spaces anyway, so char* s, char *s, char * s are all valid declarations of string s.

2. the more valid way ( at least from a C programmer point of view ) of declaring, allocating and deallocating structure S instance would be with a word struct

struct S { int i; struct S* next; };
struct S* s = new S;
s->i = 0;
s->next = NULL;
delete s;


keyword struct is optional in C++ implemetations ( but again, it is required by C ) so for compatibility sake I always use it ( it's also a good reminder that it is a aggregate type ). If you want to get rid of the keyword struct, but still want to play nice with the C compilers you can create a synonym for your declaration....

typedef struct __S { int i; struct __S* next; } S; // S type is now the same as struct __S
S* s = new S;
s->i = 0;
s->next = NULL; // this is ok as struct __S is equivalent to S
delete s;


3. if your function is declared as
void func1(S* blah) than when calling it you'd pass a pointer to the struct S

void main() {
S *blah = new S;
func1(blah) // blah is a pointer to memory block containing structure S
delete blah; // same here, delete operator takes a pointer to the allocated memory and frees it
}


on the other hand if your function is declared as
void func1(S blah) than when calling it you'd pass a value of struct S

void main() {
S *blah = new S;
func1(*blah) // dereference blah and pass a copy to function func1
delete blah; // this does not change as delete operator still wants a valid address
}


finally usage of the reference operator &amp;, lets say your function is declared as follows
void func1(S* blah) func1 expects a pointer to structure S, but lets say you did not instantiate S as a pointer;

void main() {
S blah;
func1(&amp;blah) // pass the address of blah to func1
// no delete as you did not allocate memory on the heap, but underneath stack memory is being freed to delete the temp objects.
}


hope this helps

 

[mosdef]

Wow that was perfect! I just remembered one more thing.

void func1( ... ) {
/* ... */
tempS->next = S;
S = tempS;
/* ... */
}

If I use this code to bring tempS to the front of the list, do I need to delete tempS when I'm done with the function?

-mosdef

 

[HigherGround]

nope, in a single linked list you only need to hold one reference ( to the first node ), if you have that you can always traverse through the list and delete all previously allocated nodes.

S* func(S* s) { // allocate a node and stick in front of the list
S* t = new S;
t->next = s;
s = t;
return s; // return a new address
}

main(){
S* s = new S;
s->next = NULL;
s = func(s); // now s is pointing to the beginning of the list with a first element being t and the second being s
// assuming that the next members have been initialized to NULL you can walk through the nodes and delete them in sequence
while(s){
S* it = s->next;
delete s;
s = it;
}
}

 

[mosdef]

In my question, I should have asked can I delete tempS when I'm done with the function (prevent memory leaks)?

-mosdef

 

[br0wn]

<< In my question, I should have asked can I delete tempS when I'm done with the function (prevent memory leaks)? >>



It is considered a bad programming style to allocate memory in a function like what your function does.

The answer to your question is NO.
If you delete tempS, the pointer that you set to tempS will point to NULL.
Thus next time if you deferenced that pointer you will get seg fault !!!

 

[HigherGround]

oopps, i overcomplicated the question didn't I?

short answer: no
long asnswer: no, because variables names referening a pointer are irrelevant. When I said


S* t = new S; // allocate memory on the heap
t->next = s;
s = t; // ok, since memory is allocated in the heap


So in above example s is now pointing where t was allocated, and s->next is pointing to where the original s was stored. The fact that variable t goes out of scope when the function terminates makes no difference since you are still holding to its reference ( via s ) and as long as you hold it you can always delete it. This is memory allocation on the heap, example below does not requests memory from the heap and potentialy will not execute correctly ...


S t; // allocate memory on the stack
t.next = s;
s = &amp;t; // problem, when function terminates t can be internally deleted

 

[mosdef]

So deleting t would not only be inappropriate, it would cause a seg fault?

-mosdef