構造体を動的に確保する意味

Question

基礎的な質問で申し訳ありませんが皆さんのお力をお借りしたいです

学校の授業で以下のようなコードを組みました
（２分探索木についてのコードですが、内容そのものは質問とは
関係ありません）

#include<stdio.h>
#include<stdlib.h>

typedef struct bst_node{
    int value;
    struct bst_node *left;
    struct bst_node *right;
} NODE;

NODE *root;


NODE *create_node(int d){
    NODE *p;

    p=malloc(sizeof(NODE));
    p->value=d;

    return p;
}

void insert_bst(int d){
     NODE *p;

     if(root==NULL){
         root=create_node(d);
         return;
     }

     p=root;
     while(1){
         if(p->value==d)return ;
         
         if(p->value>d){
             if(p->left==NULL){
                 p->left=create_node(d);
                 return;
             }else{
                 p=p->left;
             }
          }else {
                 if(p->right==NULL){
                     p->right=create_node(d);
                     return;
                 }else{
                     p=p->right;
                 }
             }
         }
}



void preorder(NODE *node){
    if(node==NULL) return;
    printf("%d->",node->value);
    preorder(node->left);
    preorder(node->right);
}

void inorder(NODE *node){
    if(node==NULL)return;
    preorder(node->left);
    printf("%d->",node->value);
    preorder(node->right);

}
void pastorder(NODE *node){

    if(node==NULL)return;
    pastorder(node->left);
    pastorder(node->right);
    printf("%d->",node->value);
}

int max_bst(){
    if(root==NULL){
        return -1;
    }
   NODE *p=malloc(sizeof(NODE));
   NODE *p=root;
    while(p->right!=NULL){
        p=p->right;
    }

    return p->value;
}


int main(){
    int i;
    int a[7]={17,24,4,9,11,2,23};

    for(i=0;i<7;i++){
        insert_bst(a[i]);
    }

    printf("preorder");
    preorder(root);
    printf("\ninorder");
    inorder(root);
    printf("\npastorder");
    pastorder(root);

    printf("\n Max value of BST is %d\n",max_bst());
}

ここで気になったのはところどころで、構造体のポインタを宣言したあとに、領域を動的に
確保していることです

（例えばcreate_node関数内におけるポインタp）

今までの私のイメージでは、動的確保は例えば配列の要素数分の領域を跡付けで定義するように
前もってわかっていない大きさの領域を後から確保する場合に使うものでした

ところが今回の場合、（私のイメージでは）確保する領域は構造体１つ分で前もってわかって
いるように思えます

このような場合に動的確保を行わなければいけないのはなぜでしょうか？

Answer 1

こんにちは。

確保する領域は構造体１つ分で前もってわかっているように思えます

create_node()関数内では１つしか生成していませんが、確保した領域へのポインタを戻り値で返却し、create_node関数の呼出し側でそのポインタを保持するようまた別のNODE構造体のleftやrightへ設定しています。
つまり、NODE構造体はプログラム全体では複数保持されており、その数は配列aの要素数で決まります。

今回は配列aのサイズは固定ですが、配列aをmalloc等で動的に確保することで可変にすることができますので、プログラムの構造的には、NODE構造体のインスタンスの数を可変にできるようになっています。
従って、malloc等を用いて動的に確保する必要があります。

Answer 2

ところが今回の場合、（私のイメージでは）確保する領域は構造体１つ分で前もってわかって
いるように思えます

ここの観点がずれていると思います。
一回に確保するのはあくまでも構造体１つ分ですが、これをノード数分必要です。
このノード数が固定でわかっているのであれば構造体を配列で用意しても良いのでしょうが、ノード数が可変数でも対応できるように動的に確保していることになります。

Answer 3

NODE *create_node(int d){
    NODE n;
    /* 処理 */
    NODE *p = &n;
    return p;
}

では何がマズイのかということですね。

こう書くと、nの生存期間(=メモリ上にデータが有ることが保証される期間)は
create_node内のみです。

p1 = create_node(1);

などと書いても、データが残っていることが保証されないアドレスが帰ってきます。

---

NODE create_node(int d){
    NODE n;
    /* 処理 */
    return n;
}

こう書いた場合は、nの生存期間(=メモリ上にデータが有ることが保証される期間)は
create_node内のみですが、返すときにコピーするので、動作に問題ありません。