C++ Structure within itself?

Question

I've been trying to port this code to python, but there is something I do not quite understand in C++ (I do know a bit of C++ but this is beyond me):

typedef struct huffnode_s
{
 struct huffnode_s *zero;
 struct huffnode_s *one;
 unsigned char val;
 float freq;
} huffnode_t;

What I don't get is how huffnode_s can be within itself, I've never seen this before and don't quite understand it. What does this mean, and if someone can, what would be the python equivalent?

• Troubadour: It's only a pointer to an object of the structure that it contains, not an actual object of that structure. The most common example I can think of is in a linked list node where each node holds a pointer to the previous and next nodes.
• tomlogic: Added the C++ tag -- the structure itself is ANSI C, but some of the answers reference C++.
• S.Lott: @KaluSingh Gabbar: This is a tree, not a list. Python doesn't have a built-in tree.

Answer 1

huffnode_s isn't within itself, only pointers to huffnode_s are in there. Since a pointer is of known size, it's no problem.

Answer 2

This.

class Huffnode(object):
 def __init__(self, zero, one, val, freq):
 """zero and one are Huffnode's, val is a 'char' and freq is a float."""
 self.zero = zero
 self.one = one
 self.val = val
 self.freq = freq

You can then refactor your various C functions to be methods of this class.

Or maybe this.

from collections import namedtuple
Huffnode = namedtuple( 'Huffnode', [ 'zero', 'one', 'val', 'freq' ] )

If you want your C functions to remain functions.

That's it.

h0 = Huffnode(None, None, 'x', 0.0)
h1 = Huffnode(None, None, 'y', 1.0)
h2 = Huffnode(h0, h1, 'z', 2.0)

That's all that's required.

• S.Lott: @dash-tom-bang: Single char and "pointer to" (i.e. string) is a possibly irrelevant difference in Python. The original might have meant byte (i.e., actual ASCII character) or "small integer". Can't tell from the problem. Doesn't much matter with a late-binding language like Python.

Answer 3

it does not have a structure in itself. it has a pointer to that structure.

in memory struct huffnode_s would look like (32 bit machine):

---

|------------------ huffnode_s* zero - 4 bytes --------------|

|------------------ huffnode_s* one - 4 bytes----------------|

|unsigned char val - 1 byte + 3 bytes padding=======|

|------------------- float freq - 4 bytes -------------------------|

---

these sizes would vary machine to machine, and how it looks in memory is decided by compiler .

Answer 4

To add to Carl's answer, the same thing in C++ is also possible:

class Foo {
public:
 Foo() {}
 Foo *anotherFoo;
}; 

(Note the above class is silly, but the point is you can have a pointer inside a class that is of the class type)

Answer 5

(struct huffnode_s *) declares a pointer to another structure that includes same variables as the structure that it's declared in. See this question.

Answer 6

This is a pointer to a huffnode inside of a huffnode. What this means is that you can say:

huffnode_t *node = ...;
huffnode_t *greatgreatgreatgrandchild = node->zero->zero->zero->zero->zero;

This will compile, and it will work as long as all those huffnode descendents are actually allocated and pointed to correctly.

Pointers are much like object references in JavaScript. They don't actually contain data, they just refer to it. Rest assured that you are not looking at an infinite type.

Answer 7

This is known as a self referential structure and it is exactly what it sounds like: a structure which contains a reference to itself. A common occurrence of this is in a structure which describes a node for a linked list. Each node needs a reference to the next node in the chain.

struct linked_list_node { 
 int data; 
 struct linked_list_node *next; // <- self reference 
}; 

• xiao 啸: But the code given by Douglas demonstrates a structure of binary tree.

Answer 8

As others have noted, the references to itself are simply pointers to other instances of that structure.

The pointers within the structure would allow one to connect instances together as a linked list.