1

This question sounds super confusing even for me, and it may seem obvious or already answered, but I have searched a lot and although I found interesting things, I didn't find an answer exactly for my question. Here is some C code that will show much better my doubt: 

typedef struct Node_struct {
   char keyLine[100];
   int occurrences;
   struct Node* leftChild;
   struct Node* rightChild;
   struct Node* parent;
} Node;

typedef struct Tree_struct {
   Node* root;
} Tree;

int insertNode(Tree* myTree, Node* newNode) {
    ...
    Node* currentNode = myTree->root;
    ...
    if (caseSenCmpString(newNode->keyLine, currentNode->keyLine) == -1) {
        currentNode = (Node*)currentNode->leftChild;
    }
    ...
 }

Is this code correct? Since currentNode is of type Node*, and currentNode->leftChild is of type struct Node*, I had to cast (Node*)currentNode->leftChild so that it could be assigned to currentNode. But I am not sure if this is correct, necessary, or if there is a better way to do the same.

Similarly, I also have this:

Node* coverNode = NULL;
...
coverNode->leftChild = (struct Node*)newNode;
Karol Phung
  • 25
  • 4
  • Related:https://stackoverflow.com/questions/588623/self-referential-struct-definition – jarmod Oct 13 '18 at 00:08
  • The name `Node` is a synonym for `struct Node`. (For any `typedef X Y;`, `Y` becomes a synonym for `X` — where in your case, `X` is `struct Node` and `Y` is `Node`.) The cast in `currentNode = (Node*)currentNode->leftChild;` is unnecessary because it is a no-op — the types `struct Node *` and `Node *` are two names for the same pointer type. – Jonathan Leffler Oct 13 '18 at 00:17
  • @JonathanLeffler What about `typedef struct Node_struct { /* ... */ struct Node* leftChild; /* ... */ } Node;` ... are `struct Node_struct` and `struct Node` and `Node` the same? I get that `Node` is the same as `struct Node_struct`, but what about the `struct Node *` used to declare a member of the struct? – Swordfish Oct 13 '18 at 00:30
  • @JonathanLeffler You may thank me properly later. Hush ... go fix your ;) – Swordfish Oct 13 '18 at 00:36
  • @Swordfish: Thanks for pointing out that I'd misread the question. I've 'adjusted' (extended) my answer to deal with 'practice' as well as 'theory'. – Jonathan Leffler Oct 13 '18 at 00:45
  • @JonathanLeffler \*hands-bonbon\* – Swordfish Oct 13 '18 at 00:47

2 Answers2

4

What should be written

Suppose the code in the question were written like this:

typedef struct Node {     // Not Node_struct as in the question!
   char keyLine[100];
   int occurrences;
   struct Node* leftChild;
   struct Node* rightChild;
   struct Node* parent;
} Node;

Then the name Node would be a synonym (alias) for struct Node. (For any typedef X Y;, Y becomes a synonym for type X — where in your case, X would be struct Node and Y would be Node.)

The cast in:

currentNode = (Node *)currentNode->leftChild;

would be unnecessary (but mostly harmless) because it would be a no-op — the types struct Node * and Node * would be two names for the same pointer type. Similarly for:

coverNode->leftChild = (struct Node *)newNode;

The cast would be unnecessary but (mostly) harmless. There would be a small risk of confusing people with the cast. It is better to avoid casts when possible, and these would be better written without the casts:

currentNode = currentNode->leftChild;
coverNode->leftChild = newNode;

What is written

typedef struct Node_struct {
   char keyLine[100];
   int occurrences;
   struct Node* leftChild;
   struct Node* rightChild;
   struct Node* parent;
} Node;

Now we have three type names in play: struct Node_struct, struct Node, and Node. In this case, struct Node_struct and Node are synonyms, and struct Node is an incomplete structure type (or, at least, it is not completed by any code in the question). It is wholly unrelated to either struct Node_struct or Node except by the coincidence that it is referenced inside the structure.

With this notation, the casts are 'necessary' because you're converting between pointers to unrelated types (struct Node * and struct Node_struct *). Fortunately, there are rules that say all structure type pointers are inter-convertible and must have the same size and alignment requirements (C11 §6.2.5 Types ¶28 and §6.3.2.3 Pointers ¶7).

But you should drop the _struct part of Node_struct to make the rules of the first part of this answer apply. In C, it is (IMO) sensible to use:

typedef struct SomeTag SomeTag;

so that you can subsequently use SomeTag * etc. The first SomeTag is in the tags name space and does not conflict with the second SomeTag, which is in the ordinary identifiers name space. See C11 §6.2.3 Name spaces of identifiers.

See also:

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
2

In c++, when you say struct Node, Node [immediately] becomes a type. So, you could say:

struct Node {
    char keyLine[100];
    int occurrences;
    Node *leftChild;
    Node *rightChild;
    Node *parent;
};

struct Tree {
    Node *root;
};

int
insertNode(Tree *myTree, Node *newNode)
{
    Node *currentNode = myTree->root;
    if (caseSenCmpString(newNode->keyLine, currentNode->keyLine) == -1) {
        currentNode = currentNode->leftChild;
    }
}

But, in c, it is merely in the "tag" namespace and does not define a type. Thus, you want:

typedef struct Node {
    char keyLine[100];
    int occurrences;
    struct Node *leftChild;
    struct Node *rightChild;
    struct Node *parent;
} Node;

typedef struct Tree_struct {
    Node *root;
} Tree;

int
insertNode(Tree *myTree, Node *newNode)
{
    Node *currentNode = myTree->root;
    if (caseSenCmpString(newNode->keyLine, currentNode->keyLine) == -1) {
        currentNode = currentNode->leftChild;
    }
}

As an alternative, you can use a forward declaration:

// forward declaration
struct Node;
typedef struct Node Node;

struct Node {
    char keyLine[100];
    int occurrences;
    Node *leftChild;
    Node *rightChild;
    Node *parent;
};

typedef struct Tree_struct {
    Node *root;
} Tree;

int
insertNode(Tree *myTree, Node *newNode)
{
    Node *currentNode = myTree->root;
    if (caseSenCmpString(newNode->keyLine, currentNode->keyLine) == -1) {
        currentNode = currentNode->leftChild;
    }
}

Note that the struct name does not have to match the type name:

// forward declaration
struct Node_struct;
typedef struct Node_struct Node;

struct Node_struct {
    char keyLine[100];
    int occurrences;
    Node *leftChild;
    Node *rightChild;
    Node *parent;
};

typedef struct Tree_struct {
    Node *root;
} Tree;

int
insertNode(Tree *myTree, Node *newNode)
{
    Node *currentNode = myTree->root;
    if (caseSenCmpString(newNode->keyLine, currentNode->keyLine) == -1) {
        currentNode = currentNode->leftChild;
    }
}

To allow cross linking of your two structs, we could do:

// forward declaration
struct Node_struct;
typedef struct Node_struct Node;

struct Tree_struct;
typedef struct Tree_struct Tree;

struct Node_struct {
    char keyLine[100];
    int occurrences;
    Node *leftChild;
    Node *rightChild;
    Node *parent;
    Tree *tree;
};

struct Tree_struct {
    Node *root;
};

int
insertNode(Tree *myTree, Node *newNode)
{
    Node *currentNode = myTree->root;
    if (caseSenCmpString(newNode->keyLine, currentNode->keyLine) == -1) {
        currentNode = currentNode->leftChild;
    }
}
Craig Estey
  • 30,627
  • 4
  • 24
  • 48
  • You mean the 'tag' namespace? C11 [§6.2.3 Name spaces of identifiers](http://port70.net/~nsz/c/c11/n1570.html#6.2.3) – Jonathan Leffler Oct 13 '18 at 00:33
  • @JonathanLeffler Thanks. Accurate as always. And, I marvel at how fast you were able to call up the online doc, find the relevant section, and post the link here. – Craig Estey Oct 13 '18 at 00:50
  • I 'cheated' — I'd just written a very similar [comment](https://stackoverflow.com/questions/506366/c-pointer-to-struct-in-the-struct-definition#comment92498340_508990) to another answer to an old question, and still had the link stashed in my paste buffer, even. – Jonathan Leffler Oct 13 '18 at 00:52