Act さんが書きました: ↑5年前
探索する関数に関しては、今いるノードが空だったらデータが見つからなかったということでNULLを返すという認識でよろしいのでしょうか?
その通りです。
Act さんが書きました: ↑5年前
その次の
コード:
diff = strcmp(name, p->name);
if (diff < 0) return search(p->left, name);
if (diff > 0) return search(p->right, name);
return p;
この部分は探索するnameの文字列がpの文字列と比べて探索したいデータのほうが先になるときはdiff<0の場合でまたsearchを呼び出して、探索したいデータのほうが後になるときはdiff>0の場合で同様にsearchを呼び出してpがなにもないところまでひたすら繰り返すということでしょうか。
name が見つかるか、または p が NULL になるまで繰り返します。
name が見つかったら p は NULL ではありません。
Act さんが書きました: ↑5年前
次の消去する関数については、最初にpが何もないときの処理を明確にしておき、探索のばあいと同様に対象のnameとノードのnameを比較し、等しくならないときに対象のnameが大きければ左下のノードに、小さければ右下のノードに移り、また繰り返していく。
これは探索の場合と同じです。
Act さんが書きました: ↑5年前
その次の
コード:
else {
if (p->left == NULL) p = p->right;
else {
NODE *q = p;
p = p->left;
if (q->right) {
NODE *r = q->left;
while (r->right) r = r->right;
r->right = q->right;
free(q);
}
}
}
この部分が、対象のnameと等しかった時の条件というのはわかるのですが、次にqを使うのには理由があるのでしょうか。おそらく理解が追い付いていないので、説明をしていただけるとありがたいです。
p が指している現在の NODE を削除しないといけないのですが、
free(p); を実行すると、p の更新で p = p->left; が実行
できないのです。なぜなら、p->left はもう使えないからです。
そこで、NODE *q = p; p = p->left; free(q); とします。
または、Node *q = p->left; free(p); p = q; でもよいでしょう。
ここでバグを見つけてしまいました。その削除のコードは
free し忘れでメモリーリークするので、次のように修正します。
コード:
NODE *del(NODE *p, char name[])
{
if (p == NULL) { puts(" データが見つかりません。"); return NULL; }
int diff = strcmp(name, p->name);
if (diff < 0) p->left = del(p->left, name);
else if (diff > 0) p->right = del(p->right, name);
else {
NODE *q = p;
if (p->left == NULL) p = p->right;
else {
p = p->left;
if (q->right) {
NODE *r = q->left;
while (r->right) r = r->right;
r->right = q->right;
}
}
free(q);
}
return p;
}
まず、p == NULL のとき、すぐに return することで、
次の行から後を else に入れなくてよいようにし、
ネストが一段深くなるのを防いでいます。
diff < 0 や diff > 0 で del の再帰呼出しをするのは
検索と同じことです。
strdmp の結果を diff に入れるのは、次のように
strcmp を 2回実行するのは無駄だからです。
コード:
if (strcmp(name, p->name) < 0) ...
else if (strcmp(name, p->name) > 0) ...
else {
さて、削除したい NODE が見つかった時、
その NODE は free するのですが、子の left か
rightを親に繋ぎなおさなければなりません。
p->left が NULL のときは p->right を返せばよいので
p = p->right; です。
p->left が NULL でないときは p->left を返すので、
p = p->left; です。
このとき、p->right が NULL なら問題ないのですが、
そうでないとき、p->right を p->left の右側に
繋がないといけないので、NODE *r を使って、right が
NULL になっている NODE を探しに行き、そこに繋ぎます。
以上の処理を行うと free(q) で NODE を削除できます。
Act さんが書きました: ↑5年前
最後に、main()内のファイルを開く部分ですが、
コード:
fp = fopen("namelist5.txt", "r"); /*ファイルを開く */
if (!fp) return puts("fopen failed"), 1;
ここの2行目の書き方は、このような書き方もできるという認識でよろしいのでしょうか。
質問や疑問ばかりで申し訳ないのですが、よろしくお願いします。
次のように書くのと同じです。
コード:
if (fp == NULL) { puts("fopen failed"); return 1; }
100,000件のデータを扱う実用的なものにするんだったら、
malloc が失敗した場合の処理も入れたほうが良いでしょう。
また、メニューで 0~4以外の数字を入れても大丈夫ですが、
数字以外の文字を間違って入力したとき、とんでもないことに
なります。その対処方法は分かりますか?