Graphs in C++

c-plus-plus
graphs

#1

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; };


#2

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.


#3

“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.


#4

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 :slight_smile:


#5

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?


#6

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* )