c言語でUnion-findというアルゴリズムを実装しているときに、動くけど理解できないコードを書いてしまいました。
ルートを見つける関数で、ルートがあったら返し、なかったら親をたどります。たどる際に、再帰で親をルートに代入します。
まず構造体があります。
c
1typedef struct node{ 2 int key; 3 struct node* par; 4} node;
これだとmainの中でx->par
になにも代入できなかったことになっています。
c
1node *findRoot(node *x){ 2 if (x->par->key == x->key) return x->par; 3 else { 4 x->par = findRoot(x->par); 5 } 6}
しかし、関数内でダブルポインタを使うと思った通りにうごいてくれます。代入できてしまうのです。
c
1node *findRoot(node *x){ 2 if (x->par->key == x->key) return x->par; 3 else { 4 node **p = &x; 5 (*p)->par = findRoot(x->par); 6 } 7}
これがどうして動くのか、前者が動かないのか説明できなくて困っています。ざっくりでも、詳しくでも教えていただけると嬉しいです。
動かせる全体コードを書いてもらえますか?
回答2件
あなたの回答
tips
プレビュー