You are not logged in. Please login at www.codechef.com to post your questions!

×

Graphs in C++

Can someone please explain me what does this struct inside a struct mean??? I am just trying to learn graphs representation.

struct AdjListNode { int dest; struct AdjListNode* next; };

asked 27 Dec '14, 18:45

geeky159's gravatar image

2★geeky159
203
accept rate: 33%


Hello,

As others pointed out correctly, this is not a structure inside a structure, it's instead a very simple example of what is called a self-referenced data structure because it's a data structure defined in terms of "itself".

In fact, if you think on a simple linked list as being composed of simple blocks which contain two fields:

  • Useful information;
  • Pointer to the next block;

you will see that defining such data structure "recursively" is the most intuitive way of doing things... Namely:

struct AdjListNode { 
   int dest; 
   struct AdjListNode* next;
    };

is defining the node which will represent an element on an adjacency list (at least, by the name given) and it is composed of useful information (an int called dest) and support information (namely a pointer to the next element on the list).

Say you have this (in pseudocode):

AdjListNode* x = malloc(sizeof(AdjListNode));

To access the next element if you are at x, you use: x->next which means that the next element is a new "recursive instance" of the same data structure :)

link

answered 27 Dec '14, 23:03

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

I have a little doubt that while defining regular pointers we use variable but not variable. So i am bit confused is AdjListNode* a pointer variable or not?

(28 Dec '14, 00:04) geeky1592★

Hum? When defining a regular pointer (whatever that is) we use a pointer variable as in, writing int x is the same as saying that the variable x will store the address of a memory position which holds an integer. For this structure, the logic is all the same, except that instead of being a memory location storing an integer, it's a memory location storing a structure of type AdjListNode (AND NOT AdjListNode )

(28 Dec '14, 18:43) kuruma3★

In this structure , dest is of int type and next is a pointer which contains address of AdjListNode structure. I hope you know that pointer stores address not data.

For example
int d = 5 Here d is variable of int type. And suppose, d is stored at 0x1 memory address.

  1. int ptr*
  2. ptr = &d , Here ptr will contain 0x1 memory address. And will refer to d.

Similary , pointer "next" will contain address of a AdjListNode structure and refer to it.

It is not struct inside a struct. The name of the structure is AdjListNode which has two fields, one is of int type and second one is a pointer.

link

answered 27 Dec '14, 18:50

shivam217's gravatar image

4★shivam217
8383515
accept rate: 20%

edited 27 Dec '14, 20:19

"next" is pointer to structure "AdjListNode".As pointers are used to store address of the variable.Like (intx) x will be used to store memory address of a variable of int type similarly,next will be storing address of structure.so the line struct AdjListNode next; stating that next is a pointer to structure..Hope i was clear.

link

answered 27 Dec '14, 20:53

emin3m's gravatar image

2★emin3m
629
accept rate: 3%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,914
×368

question asked: 27 Dec '14, 18:45

question was seen: 981 times

last updated: 28 Dec '14, 18:43