Dynamically allocating memory...

So i wrote a function which creates a circularly linked list. But for some reason it cant allocate memory dynamically =(

What am i doin wrong?

Code:

---

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

struct node
{
        int data;
        node *next;
        node *prev;
};

struct circle
{
        node *start;
};

void createCircle(circle *circ, vector<int> v);

int main()
{
        //Main
        circle first;
        first = new circle;
        vector<int> numbers;
        for(int i=0; i<10; i++)
        {
                numbers.push_back(i+1);
        }
        createCircle(first, numbers);
        cin.ignore();
        //End
        return 0;
}

void createCircle(circle *circ, vector<int> v)
{
        //create intitial node
        node *start;
        start = new node;
        start->data = v.at(0);
        //create the rest of the nodes
        int size = v.size();
        size--;
        //data
        node *nodes[size];
        for(size; size>0; size--)
        {
                nodes[size] = new node;
        }
        size = v.size();
        size--;
        //Insert Data
        for(int i=0; i<size-1; i++)
        {
                nodes[i]->data = v.at(i);
        }
        //Connect nodes
        circ->start = start;
        start->next = nodes[0];
        for(int i=1; i<size-1; i++)
        {
                nodes[i-1]->next = nodes[i];
        }
        //do prevs
        start->prev = nodes[size-1];
        for(size-2; size>0; size--)
        {
                nodes[size]->prev = nodes[size-1];
        }
        //DONE
}

---

Thanks!! =D

There's quite a few things wrong with that code, and the best suggestion I can think of is go back and review from whatever source you're using to learn this stuff.

Code:

---

first = new circle;

---

This would work if "first" was a pointer

Code:

---

int size = v.size();
        size--;
        //data
        node *nodes[size];

---

This is nonstandard. The size of an array needs to be a constant value, or you need to dynamically allocate the array. Besides, it kind of defeats the purpose of a list to allocate an array, then copy its contents into the list.

And if you're using std::vector for the data anyway, it seems pointless to make your own container

Finally, you need to have a delete for each new, or you'll leak memory

I'm not using source, i'm doing this myself. ;)

Well i fixed the pointer thing, that was just a stupid error on my part, that's what i meant to type. I'm not going to worry about the memory leak just yet until i can get the memory allocated in the first place ;)

How do i dynamically allocate the memory then?

The circular linked list object is the whole purpose of the program and the computer needs to be able to dynamically allocate the memory. So this is just my concept of doing it, can you even allocate the memory dynamically? Should i create a vector instead of an array for the nodes pointers?

I'll try it ;)

And i just get more errors with using a vector =P

How can i get this thing to work?

I'm sure SOMEONE has to have faced this problem before...

i would think this sorta thing takes place perdy often in programming...


Anyone?

Bitteschon?

=D

Since I really cannot follow what you're trying to do I can only try to give you a few hints why your program crashes.

Code:

---

        int size = v.size();
        size--;
        //data
        node *nodes[size];
        for(size; size>0; size--)
        {
                nodes[size] = new node;
        }

---

you have never created node[0].

Code:

---

for(int i=0; i<size-1; i++)
        {
                nodes[i]->data = v.at(i);
        }

---

boom. you dereference the nonexistant node[0].

Code:

---

        for(int i=1; i<size-1; i++)
        {
                nodes[i-1]->next = nodes[i];
        }

---

again you dereference node[0].

Code:

---

        start->next = nodes[0];

---

start->next points to ????

Code:

---

        for(size-2; size>0; size--)
        {
                nodes[size]->prev = nodes[size-1];
        }

---

and again.
Kurt

Okay so i gotta change the size>0 to size>=0, then what?

I'm trying to allocate a dynamic amount of memory for the structures defined at the top of the page. The user could enter or the program could choose to enter a certain amount of nodes, the function has to be able to adapt to that.


THanks!

You might want to have a look at this tutorial: http://www.cprogramming.com/tutorial/lesson15.html

Yeah i how to setup and traverse the lists and all, and i fixed the mistakes mentioned earlier, but i still get the same errors. The problem is that i need to dynamically allocate it and i cant figure out how to =(

Thanks everyone, and DWKS, always a help! =D

i havent been following this thread but from the looks of it youve had feedback on your code. can you post the updated version (if any) of your code?

you said you get 'errors'.. you mean actual errors, ie runtime/compiletime errors? if so what are they?

If you want to create an array of nodes in runtime, you'd probably have to

Code:

---

node** nodes;
nodes = new node*[size];

---

rather than

Code:

---

node *nodes[size]

---

As previously mentioned, you can't STATICALLY define an array with a variable, which is what you're doing.

alrighty, i gotta get out my other computer, i'll post it up in a jiff =)

Code:

---

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

struct node
{
        int data;
        node *next;
        node *prev;
};

struct circle
{
        node *start;
};

void createCircle(circle *circ, vector<int> v);

int main()
{
        //Main
        circle *first;
        first = new circle;
        vector<int> numbers;
        for(int i=0; i<10; i++)
        {
                numbers.push_back(i+1);
        }
        createCircle(first, numbers);
        cin.ignore();
        //End
        return 0;
}

void createCircle(circle *circ, vector<int> v)
{
        //create intitial node
        node *start;
        start = new node;
        start->data = v.at(0);
        //create the rest of the nodes
        int size = v.size();
        size--;
        //data
        node *nodes[size];
        for(size; size>=0; size--)
        {
                nodes[size] = new node;
        }
        size = v.size();
        size--;
        //Insert Data
        for(int i=0; i<size-1; i++)
        {
                nodes[i]->data = v.at(i);
        }
        //Connect nodes
        circ->start = start;
        start->next = nodes[0];
        for(int i=1; i<size-1; i++)
        {
                nodes.[i-1]->next = nodes[i];
        }
        //do prevs
        start->prev = nodes[size-1];
        for(size-2; size>=0; size--)
        {
                nodes[size]->prev = nodes[size-1];
        }
        //DONE
}

---

3:53 is a jiff? ;)

The first thing I noticed with your code is that you're passing a vector by value. Usually it's a much better idea to pass STL containers as references or pointers because it can be quite expensive to copy them.

When I compile your code, I get two warnings and one error. Here's the error:

Code:

---

nodes.[i-1]->next = nodes[i];

---

It seems you have an extra '.'.

The warnings are on these lines:

Code:

---

        for(size; size>=0; size--)
        for(size-2; size>=0; size--)

---

The first part of those for loops does nothing and can be left out.

Once I removed the bothersome '.', your program compiled correctly and ran without segfaulting.

[edit] I ran your program quickly though GDB.

Code:

---

GNU gdb 5.2.1
Copyright 2002 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License,
welcome to change it and/or distribute copies of it under certain
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" fo
This GDB was configured as "i686-pc-mingw32"...
(gdb) break 33
Breakpoint 1 at 0x401549: file tempjunior2.cpp, line 33.
(gdb) r
Starting program: tempjunior2.exe

Breakpoint 1, main () at tempjunior2.cpp:33
33              cin.ignore();
(gdb) p first
$1 = (circle *) 0x3d24b0
(gdb) p *$
$2 = {start = 0x3d25e0}
(gdb) p $.start
$3 = (node *) 0x3d25e0
(gdb) p *$
$4 = {data = 1, next = 0x3d2770, prev = 0x3d2630}
(gdb) p $.next
$5 = (node *) 0x3d2770
(gdb) p *$
$6 = {data = 1, next = 0x3d2748, prev = 0x411c23}
(gdb) p *$->next
$7 = {data = 2, next = 0x3d2720, prev = 0x3d2770}
(gdb) p *$->next
$8 = {data = 3, next = 0x3d26f8, prev = 0x3d2748}
(gdb) p *$->next
$9 = {data = 4, next = 0x3d26d0, prev = 0x3d2720}
(gdb) p *$->prev
$10 = {data = 3, next = 0x3d26f8, prev = 0x3d2748}
(gdb) p *$->next
$11 = {data = 4, next = 0x3d26d0, prev = 0x3d2720}
(gdb) p *$->next
$12 = {data = 5, next = 0x3d26a8, prev = 0x3d26f8}
(gdb) p *$->next
$13 = {data = 6, next = 0x3d2680, prev = 0x3d26d0}
(gdb) p *$->next
$14 = {data = 7, next = 0x3d2658, prev = 0x3d26a8}
(gdb) p *$->next
$15 = {data = 8, next = 0xbaadf00d, prev = 0x3d2680}
(gdb) p *$->next
$16 = {data = 1768763235, next = 0x3377676e, prev = 0x2e332f32}
(gdb) p *$->next
Cannot access memory at address 0x3377676e
(gdb)

---

It looks like your loop was created correctly up until the element with data 8.

Looking at your code again, I would guess that that is because of this:

Code:

---

        size = v.size();
        size--;
        //Insert Data
        for(int i=0; i<size-1; i++)

---

You're not looping as far as maybe you could. With 10 elements in v, the loop executes with i from 0 to 7, inclusive.

Also, don't forget to terminate the last link with pointers to NULL or to the list's head. [/edit]

Thanks, that little '.' musta got in there while i was copying and pasting =P

Haha, well it still won't compile for me (MSVC++ Express).

Problem is with the line:

Code:

---

node *nodes[size]

---

=(

I get 3 errors with that line. But other than that the program seems to be alright.

That has beem pointed out earlier. (#2, #11). This works for g++ only.
You have to use

Code:

---

node *nodes = new node*[size];

---

Kurt

Quote:

---

Originally Posted by ZuK

That has beem pointed out earlier. (#2, #11). This works for g++ only.
You have to use

Code:

---

node *nodes = new node*[size];

---

Kurt

---

And what do you want to allocate here? array of structs or array of pointers?

It should be or

Code:

---

node *nodes = new node[size];

---

or

Code:

---

node **nodes = new node*[size];

---

It should be

Code:

---

std::vector<node*> nodes(size);

---

I can't think of a good reason to use a dynamic array here.

If you are getting errors with the vector, post your attempt and the errors you get.

alrighty, i'll give it a shot ;)

It compiled!!!


But then it had a runtime error, segfault =( it didn't give me a readout of the variables though like it normally does, it pointed me to the vector header file. =(

Here it is:

Code:

---

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

struct node
{
        int data;
        node *next;
        node *prev;
};

struct circle
{
        node *start;
};

void createCircle(circle *circ, vector<int> &v);

int main()
{
        //Main
        circle *first;
        first = new circle;
        vector<int> numbers;
        for(int i=0; i<10; i++)
        {
                numbers.push_back(i+1);
        }
        createCircle(first, numbers);
        cin.ignore();
        //End
        return 0;
}

void createCircle(circle *circ, vector<int> &v)
{
        //create intitial node
        node *start;
        start = new node;
        start->data = v.at(0);
        //create the rest of the nodes
        int size = v.size();
        size--;
        //data
        vector<node*> nodes(size);
        for(size; size>=0; size--)
        {
                nodes.at(size) = new node;
        }
        size = v.size();
        size--;
        //Insert Data
        for(int i=0; i<size-1; i++)
        {
                nodes.at(i)->data = v.at(i);
        }
        //Connect nodes
        circ->start = start;
        start->next = nodes.at(0);
        for(int i=1; i<size-1; i++)
        {
                nodes.at(i-1)->next = nodes.at(i);
        }
        //do prevs
        start->prev = nodes.at(size-1);
        for(size-2; size>=0; size--)
        {
                nodes.at(size)->prev = nodes.at(size-1);
        }
        //DONE
}

---

Code:

---

vector<node*> nodes(size);
for(size; size>=0; size--)
{
        nodes.at(size) = new node;
}

---

Here nodes.at() throws an out of range exception. Not really much reason to use at() if you're not going to handle the exceptions.

>> Not really much reason to use at() if you're not going to handle the exceptions.
Actually, there is in that it will throw an exception every time instead of having undefined behavior which might silently break something. Even if you don't handle the exception it still indicates why the "crash" occured. It's actually probably better to always use at() unless you have some specific efficiency issue. Most people use operator[] because they are just used to array syntax (or are prematurely optimizing).

In this case, nodes.at(size) is out of bounds. Valid indexes are 0 to size-1. You'll want to start looping at size-1. I'd also use a separate loop variable instead of re-using size for this.

Personally I find at() a little obscure-looking (in addition to being longer), and prefer to use it only during debugging, if only for that reason.

well i know at() uses bounds checking which is why i prefer it as do most others, yeah it's obscure but if you were used to using .at() [] might look obscure too ;) haha

okay, so i used a new variable and all and it stills throws the exception =(

Code:

---

size = v.size();
size--;
for(int i=0; i < size; i++)
{
    nodes.at(i) = new node;
}
...

---

:(

Are you sure it is throwing the exception there? You use at() several times, it is possible that it is being called from a different line of code.

Yeah its throwing an unhandled exception and if i click continue then an assertion error, the part it is showing me is in the vector.h file, _XRan or something, out of range memory location

Right, but where in your code is the exception being thrown? Look down the call stack until you see some of your own code, and identify the call to at() that is causing the problem. You can also add cout statements between each for loop to see how many cause the error.

You can also post more complete current code to make sure you implemented the changes properly.

alrighty, i'll give it a shot, thanks for the help!