ポインタについてわからないところがでたのでアドバイスをお願いします。

Question

構造体とポインタについての質問です。関数の定義は変えないでmain関数のポインタを弄りたいです。

###条件
関数の定義は変えないでください

struct node {
    int key;
    struct node *parent, *left, *right;
};

struct node *new_node(int key) {
    struct node *p;
    
    p = (struct node*)malloc(sizeof(struct node));
    
    p->key = key;
    
    p->left = NULL;
    p->right = NULL;
    p->parent = NULL;
    
    return p;
}

int insert(int key, struct node *root){
    
    while(root != NULL){
        
        if (key > root->key) {
            root = root->right;
        }else if (key < root->key) {
            root = root->left;
        }else{
            return 0;
        }
                
    }
    root = new_node(key);
    
    return 1;
}

int main(){
    
    struct node *root = NULL;
    int key = 0;
    
    printf("ask:");
    scanf("%d",&key);
    
    insert(key, root);
    ////////////ここでデバッグしたら///////////////
    free(root);
    
    return 0;
}

デバッグの結果
root = NULL

###考察
関数の変数にnew_nodeをしているだけ

Comments

[maisumakun]

本当に関数の「定義」を変えてはいけないのでしょうか？（それでは「関数全体を書き換えてはいけない」ということと等しいので、何もできません）

Answer 1

insert(key, root);

これではrootのナカミが関数に渡るだけで、rootは変わりようがありません
rootを変更するなら、rootのアドレスを渡しましょう

＃当然insertの方もそれに合わせて修正の必要あり

Comments

[GAKU_SAY]

そう思っているのですが、仕様をint insert(int key, struct node* root)と言われてましてどうしたらいいのかわからないんです。

[y_waiwai]

そこ、insertじゃなくて、
root=new_node(key);
じゃないんですか？

Answer 2

関数の定義というと関数の本体のことですが、
変えてはいけないのは、関数の仕様、すなわち引数と返却値のことではありませんか？

そうであれば struct node は parent を持っているので、
int insert(int key, struct node *root); のままで二分木を構成することはできます。

#include <stdio.h>   // printf
#include <stdlib.h>  // malloc, free

struct node {
    int key;
    struct node *parent, *left, *right;
};

struct node *new_node(int key)
{
    struct node *p = (struct node*)malloc(sizeof(struct node));
    p->key = key;
	p->parent = p->left = p->right = NULL;
    return p;
}

int insert(int key, struct node *root)
{
    if (key > root->key) {
		if (root->right) return insert(key, root->right);
		struct node *p = new_node(key);
		p->parent = root;
		root->right = p;
		return 1;
	}
    if (key < root->key) {
		if (root->left) return insert(key, root->left);
		struct node *p = new_node(key);
		p->parent = root;
		root->left = p;
		return 1;
	}
	return 0;
}

void print(struct node *p)
{
	if (p) print(p->left), printf("%d\n", p->key), print(p->right);
}

void freeAll(struct node *p)
{
	if (p) freeAll(p->left), freeAll(p->right), free(p);
}

int main(void)
{
	struct node dummy = { -2147483648 };
    struct node *root = &dummy;
    int key[6] = { 5, 3, 1, 4, 2, 6 };

	for (int i = 0; i < 6; i++) insert(key[i], root);
	print(root->right);
	freeAll(root->right);
}

Comments

[episteme]

「空要素をrootに置いちゃダメ」縛りがあるとツラいもんがありますね...

Answer 3

void increment(int count) {
  count = count + 1;
}

int main() {
  int count = 123;
  increment(count);
  // さてここでcountはいくつになるかな?
  // 124? 違うよね、123のままだよね。
  // それと同じこと。
  return 0;
}