Page 2 of 2
Re: Linked lists and stuff (C++)
Posted: Sat Feb 26, 2011 3:42 pm
by Zacariaz
Synon wrote:Zacariaz wrote:In my langu7age links and nodes are two different things. I don't think we will come to an understanding here. It may or may not be my fault as I'm not always the best at explaining things, but the problem is solves and furthermore I now know the name of the concept that I'm actually interested in.
By links, I assume you mean a link between two nodes? I thought you were trying to understand the concept of a linked list...
Yes, I thought so
Anyway, unless people want to make further comments on the code in question (Like explaining who or what deallocated the dynamically allocated memory since apparently I don't need to do it, which I don't really understand) I really don't think there's anything left to discuss at this time.
Thanks for all.
Re: Linked lists and stuff (C++)
Posted: Sat Feb 26, 2011 3:52 pm
by Tosi
By the representation of a graph I think you are getting at, it would be represented by something like this:
Code: Select all
typedef struct tag_node
{
void *data;
size_t num_links;
struct tag_node **links; /* array of pointers to nodes */
} graph_node;
From wikipedia I see this is called an
adjacency list. It speeds some graph algorithms up by having an O(1) access time for the destination nodes of a source node, but it takes up more space than some of the alternatives. In this case, it would be valid to use a c++ vector to hold the adjacency list.
When I was in discrete math, the main representation I studied for graphs was the adjacency matrix. Let's say you have a graph with N nodes. For the nodes themselves I would store the data they hold in an array, separate from the matrix. The adjacency matrix is a N x N matrix which represents the relationships between the nodes. For a given row
i, if the value of column
k is 1, then the two nodes
i and
k are connected. If the value is 0, then they are not connected. The main advantage of this representation is that it takes up much less space than the adjacency list, and maybe some graph problems could be reformulated as linear algebra problems. The disadvantage is that it has at least O(n) access time for the destination nodes of a source node.
Unfortunately, I don't think there is an STL graph type, but there are probably tons of libraries that implement one you could use if you don't feel like re-inventing the wheel.
Re: Linked lists and stuff (C++)
Posted: Sat Feb 26, 2011 4:28 pm
by Zacariaz
Tosi wrote:By the representation of a graph I think you are getting at, it would be represented by something like this:
Code: Select all
typedef struct tag_node
{
void *data;
size_t num_links;
struct tag_node **links; /* array of pointers to nodes */
} graph_node;
From wikipedia I see this is called an
adjacency list. It speeds some graph algorithms up by having an O(1) access time for the destination nodes of a source node, but it takes up more space than some of the alternatives. In this case, it would be valid to use a c++ vector to hold the adjacency list.
When I was in discrete math, the main representation I studied for graphs was the adjacency matrix. Let's say you have a graph with N nodes. For the nodes themselves I would store the data they hold in an array, separate from the matrix. The adjacency matrix is a N x N matrix which represents the relationships between the nodes. For a given row
i, if the value of column
k is 1, then the two nodes
i and
k are connected. If the value is 0, then they are not connected. The main advantage of this representation is that it takes up much less space than the adjacency list, and maybe some graph problems could be reformulated as linear algebra problems. The disadvantage is that it has at least O(n) access time for the destination nodes of a source node.
Unfortunately, I don't think there is an STL graph type, but there are probably tons of libraries that implement one you could use if you don't feel like re-inventing the wheel.
Reinventing the wheel is all I do. Otherwise I'd have to come up with new stuff and my creativity is rather... limited.
Anyway, the line:
Code: Select all
struct tag_node **links; /* array of pointers to nodes */
make me kinda dizzy. Won't the array of pointers still be of fixed size? The whole idea is to be able to add nodes later on as needed. Yes I know there are ways of extending, but as discussed in another thread it is rather troublesome and vectors seem the better choice.
Re: Linked lists and stuff (C++)
Posted: Sat Feb 26, 2011 5:22 pm
by Zacariaz
berkus wrote:Anyway, I believe this is not OSdev related in any way?
Thus it's in "General Programming"
I suppose I could argue that it's related to OS programming, but that would be a waste of time as if I'm ever going to bring my weird ideas to life, it won't be any time soon.
In any case, as long a people don't complain about me bringing my stupid questions here, which so far they haven't, at least not that I remember, I'm going to continue to do so as I know that the people here are smart, unlike basically everywhere else on the net (that I know of.)
Re: Linked lists and stuff (C++)
Posted: Sat Feb 26, 2011 5:54 pm
by Zacariaz
sometimes it's a bit like learning Chinese by by watching old Chinese movies with no subtitles.
I do know a lot of stuff, but there's also a lot of very big holes. The holes are relatively easy to fill when you are aware of them, but when you're not, it's a whole lot harder. Like I'd never considered graph theory to be the answer because that's not an area I've studied.
I know more or less what there is to know about pointers. It's really just a types like everything else, but when it come to allocating memory, it's not anything I know a lot about. So when I allocate memory Type* data = new Type[5] the only way I know of to allocate more memory later on, is the method I brought up earlier in the other thread. From what I leaned there, this method would not really be beneficial in anyway as we already have powerful tolls, like vectors, which is better optimized and easier to use.
Re: Linked lists and stuff (C++)
Posted: Sun Feb 27, 2011 8:53 am
by Tosi
I just wrote it in C because that is what I know the best. You could use C++, with classes and vectors to implement the same thing if you like. One thing that C has that C++ is missing is realloc, which is good for extending/shrinking dynamic arrays:
Code: Select all
int *some_array;
size_t array_len = 50;
some_array = malloc(array_len * sizeof(int));
/* Do something with the array */
...
/* Add 50 more elements */
array_len += 50;
some_array = realloc(some_array, array_len * sizeof(int));
And the values stored in the array will remain unchanged after the call to realloc. To do something like this in C++ you have to create a new array, copy all the elements from the old array, and then delete the old array.
Re: Linked lists and stuff (C++)
Posted: Sun Feb 27, 2011 7:11 pm
by gravaera
Hi:
Simplest implementation would be similar to:
Code: Select all
struct vnode_t
{
vnode_t **links, *parent;
int nLinks;
};
struct vnode_t *head;
struct vnode_t *findItem(T criterion);
struct vnode_t *getParent(vnode_t node);
int addLink(struct vnode_t *node, T item);
int removeItem(struct vnode_t *node, T item);
// ...
Where nLinks holds the number of links currently on the node, and each node can be resized dynamically to fit more elements into the array (links).
--All the best
reavengrey