@WhozCraig は、質問の主旨に対して適切な回答を提供してくれましたが、その他の問題についてはもう少しお役に立ちたいと思います。
最初のステップ
OK、最初に、コードに関する非常に重要なことがいくつかあります。
中かっこ。神への愛のために、if..else構文に中括弧を使用してください。以下を参照してくださいBstInsert。
void BstInsert( Bst *root, int key )
{
if( !root->key )
root->key = key;
else if ( key <= root->key)
if( root-> left )
BstInsert( root->left, key );
else
root->left = NewNode( key );
else
if ( root -> right )
BstInsert( root->right, key);
else
root->right = NewNode( key );
}
あるキーが別のキーよりも小さいか大きいかに基づいて BST をウォークする関数を作成する場合は、何よりも一貫性を保つ必要があります。A < B1 か所で使用するA <= Bと、悲惨な結果になる可能性があります。また、ターゲット ノード (探しているノード) を固定する側を選択し、常に同じ方法で比較を行うと、読みやすさにも役立ちます。
技術的な問題
メモリ割り当てが失敗する可能性があります。その場合、さまざまな割り当て方法 ( malloc、callocなど) が返されNULLます。これを確認する必要があります。callocはメモリをゼロに初期化 (クリア) しますが、そうでmallocはないことに注意してください。この種の状況 (練習問題として基本的なデータ構造を作成する) では、割り当て方法を次のようにラップするのが好きです。
void *ecalloc(size_t n, size_t s) {
void *o = calloc(n, s);
if (NULL == o) {
fprintf(stderr, "Memory allocation failed!\n");
exit(EXIT_FAILURE);
}
return o;
}
これは、a) 面倒な割り当てチェックを常に入力する必要がないことif (NULL == thing)、および b) 割り当てが失敗した場合にメッセージを出力した後にプログラムが終了することを意味します。後者は常に望ましいとは限りません (少なくとも、終了の部分は、メモリが不足している場合に多くのオプションはありませんが) が、この場合は十分すぎるほどです。
設計上の問題
警告: この用語Designはここでは大まかに使用されています。
BST にいくつかの整数を格納したいとしましょう。BST のノードが整数と (ノードへの) 2 つのポインターを格納することを決定します。それは結構です。ただし、ノードが使用されているかどうかを判断するために、キーをセンチネル値として賢明に使用できないことを意味します。
幸いなことに、その必要はありません。ツリーが空のときにルートとしてノードを使用する代わりに、ノードへのポインターを使用します。ノードがない場合、ポインターはNULLです。これは、remove メソッドで発生した問題に関連しています。
BST は、リンクされたノードで構成されるツリーですよね? またはそれは？各ノードが実際にはサブツリーであるツリーと考えることもできます。そのため、再帰に適しているので、可能な場合は再帰を使用してエレガントに表現してみましょう。
ここで、いくつかのオプションがあります。
- 不変の bst を作成できます (すべての変更呼び出しは、古いものを変更せずにツリーの新しい変更されたコピーを返すため、
b = bst_insert(b, 10)すべての変更呼び出しは次のようになります)。bst_insert
void bst_insert(bst **b, int key)as と呼ばれるの行に沿ってさらに進むことができますbst_insert(&b, 10)。ここでは、ノードへのポインターへのポインターを渡すことにより、追加レベルの間接化を使用してツリーを変更します。- または、前の 2 つのオプションの間の何かを選択することもできます。ここでは
bst *b(bst *b, int key)、できるもの*b(キーと子ポインター) を変更し、できないものを代入します。これにより、余分な間接化 (少し醜い) が回避されますが、目的を達成するために関数の戻り値と関数の副作用の割り当てを組み合わせて使用している場合、少し一貫性がなくなります。
使用するオプション 2 を選択しました。
デバッグ
1BST にa を挿入するとします。おそらく、を削除し2ます。これが機能したことをどのように知っていますか？BST が何をしているかを確認できれば、デバッグが容易になると思いませんか?
(特に、基本的なデータ構造を書き始めるとき、gdb のような複雑なデバッグ環境が a) 過剰で b) 情報が過負荷になる可能性がある場合)、データ構造の状態を非常に早い段階で出力する方法をコーディングすることをお勧めします。
また、*nix を実行している場合、valgrind("Val grinned" のように発音) はあなたの親友です。これはメモリ チェッカーであり、割り当てたメモリが常に解放されていることを確認したり (もちろん、メモリの使用が終わったら)、範囲外などの他のメモリ エラーを探すために使用できます。使い方を学びましょう (実際にはとても簡単です)。Windows を使用している場合は、Purify がありますが、無料ではないと思います...とにかく、その環境に詳しい人が何かを推奨できると確信しています。
コンパイラの警告も素晴らしいものです。それらをオンにして、エラーとして扱います。gcc を使用するときは、 を使用する傾向があります-W -Wall -ansi -pedantic。関連して-g、GDB が使用する情報を生成する必要があります。
BST の作成
私はあなたのコードを調べて分析するつもりでしたが、同様のスタイルの BST を自分で書くことになり、各部分を説明するコードを調べました。私は2ファイルのアプローチを採用しました。と がbst.cありbst.hます。
bst.h
このビットは、ヘッダーが大規模なシステムに複数回含まれている場合に、誤って同じものを複数回定義または宣言しようとしないようにするため、また、誤って無限のプリプロセッサ ループを引き起こさないようにするためです。循環ヘッダー参照があります。
#ifndef BST_H_
#define BST_H_
これは typedef であり、常に入力する必要がなく、BST を使用しているだけの人から型struct bstnodeの内容を隠すことができます。struct bstnode
typedef struct bstnode bst;
extern基本的に、これらの機能は別の場所に実装されていると言います。
extern bst *bst_new(int k);
extern void bst_insert(bst **b, int k);
extern bst *bst_search(bst *b, int k);
extern void bst_remove(bst **b, int k);
extern void bst_delete(bst **b);
extern void bst_newick(const bst *b);
#endif /* BST_H_ */
bst.c
#include <stdlib.h>
#include <stdio.h>
#include "bst.h"
これが完全struct bstnodeです。bstが含まれているため、typedefにアクセスできますbst.h。
struct bstnode {
int key;
bst *left, *right;
};
このコンテキストでは、静的とは、これらの関数にファイル スコープがあることを意味します。
static void bst_swap_keys(bst *a, bst *b);
static void bst_newick_rec(const bst *b);
static void *ecalloc(size_t n, size_t s); /* Here for compactness - normally I would put it in a utility file somewhere else. */
さて、bst.h別のファイル に簡単にインクルードしてmain.c、そこにメイン メソッドを配置することもできましたが、コンパクトにするためにそうしませんでした。
int main(void)
{
bst* b = bst_new(5);
bst_newick(b);
bst_insert(&b, 7);
bst_newick(b);
bst_insert(&b, 3);
bst_insert(&b, 8);
bst_insert(&b, 2);
bst_insert(&b, 1);
bst_newick(b);
bst_remove(&b, 7);
bst_newick(b);
bst_delete(&b);
printf("%p\n", (void*) b);
return EXIT_SUCCESS;
}
この方法の欠点はbst_new、最初の有効なノードを作成する前にキーが必要になることです。bst_new代わりに割り当てを破棄して実行することもできましたが、ここでは/パラダイムbst_insertを維持したかったのです。newdelete
bst *bst_new(int k) {
bst *b = ecalloc(1, sizeof *b);
b->key = k;
return b;
}
これが私たちの挿入方法です。私はできる限りショートカットを避けようとしており、このコードをよりコンパクトにする方法はたくさんあることに注意してください。強迫観念的な中括弧の使用に注意してください。これは余分な作業になる可能性がありますが、特に後でコードを変更するときに、意図しない動作を避けるために使用することをお勧めします。
void bst_insert(bst **b, int k) {
if (NULL == b) { /* I wanted to avoid additional levels of nesting so I did this instead of NULL != b */
return;
}
if (NULL == *b) {
*b = bst_new(k);
} else if ((*b)->key > k) {
bst_insert(&(*b)->left, k);
} else if ((*b)->key < k) {
bst_insert(&(*b)->right, k);
}
}
可能であればノードを見つけます。const変更しないことを示すためにb を作成することもできましたが、その場合は戻り値の型も変更してから、検索したものを変更するためにキャストする必要がありましたが、これは少しいたずらです。
bst *bst_search(bst *b, int k) {
if (NULL == b) {
return NULL;
} else if (b->key == k) {
return b;
} else if (b->key > k) {
return bst_search(b->left, k);
} else {
return bst_search(b->right, k);
}
}
これはメソッドに対してのみ存在しbst_removeますが、このファイルの外部でも役立つ可能性があるため、ヘッダーからも利用できます。
bst *bst_min(bst *b) {
if (NULL != b && NULL != b->left) {
return bst_min(b->left);
} else {
return b;
}
}
ノード自体を交換するのではなく、ターゲット ノード (削除されるノード) とそれを置き換えるノードのキーを交換し、再帰的にターゲット値を再度削除することに注意してください。キーが文字列またはヒープに割り当てられた何かである場合、ノードを解放する直前にキーも解放する必要があります。
void bst_remove(bst **b, int k) {
bst *temp;
if (NULL == b || NULL == *b) { /* Doing it like this avoids extra indentation, which is harder to read*/
return;
}
temp = *b;
if ((*b)->key > k) {
bst_remove(&(*b)->left, k);
} else if ((*b)->key < k) {
bst_remove(&(*b)->right, k);
} else {
if (NULL != (*b)->left && NULL != (*b)->right)
{
temp = bst_min((*b)->right);
bst_swap_keys((*b), temp);
bst_remove(&(*b)->right, k);
}
else if (NULL != (*b)->left)
{
*b = (*b)->left;
}
else if (NULL != (*b)->right)
{
*b = (*b)->right;
}
else
{
(*b) = NULL;
}
free(temp);
}
}
bst_deleteはかなり重要です。渡した bst に割り当てたすべてのメモリを解放します。割り当て呼び出しごとに、無料呼び出しもある必要があることを忘れないでください。キーが文字列またはヒープに割り当てられた何かである場合、ノードを解放する直前にキーも解放する必要があります。
void bst_delete(bst **b) {
if (NULL == b) {
return;
}
if (NULL != *b) {
bst_delete(&(*b)->left);
bst_delete(&(*b)->right);
free(*b);
*b = NULL;
}
}
Newick 形式で BST を出力して値を読み取るのは、私にとっては常にちょっとしたハックのように感じます (Newick では L->R と R->L の区別がないため...)。そのため、私もそれを読むことに慣れており、過去にデバッグに便利であることがわかりました. そして、あなたが頭がおかしくない限り、印刷を行う方法はとにかく順序が一貫している必要があります。これは、再帰的な作業を別のメソッドに分割して再帰的なタスクをラップする方法も示しています。このメソッドは、公開されているメソッドから呼び出されます。後者は、再帰にはあまり適していない他のタスクを処理します (たとえば、セミコロンと改行をトップレベルで 1 回だけ出力するなど)。
void bst_newick(const bst *b)
{
if (NULL != b)
{
bst_newick_rec(b);
printf(";\n");
}
else
{
printf("NULL!\n");
}
}
static void bst_newick_rec(const bst *b)
{
if (NULL == b) {
return;
}
if (NULL != b->left || NULL != b->right) {
printf("(");
if (NULL != b->left && NULL != b->right) {
bst_newick_rec(b->left);
printf(",");
bst_newick_rec(b->right);
} else if (NULL != b->left) {
bst_newick_rec(b->left);
} else {
bst_newick_rec(b->right);
}
printf(")");
}
printf("%d", b->key);
}
キー スワッピング メソッドを作成することは、実際にはちょっとした便利さにすぎません。
static void bst_swap_keys(bst *a, bst *b)
{
int temp;
if (NULL != a && NULL != b && a != b)
{
temp = a->key;
a->key = b->key;
b->key = temp;
}
}
static void *ecalloc(size_t n, size_t s) {
void *o = calloc(n, s);
if (NULL == o) {
fprintf(stderr, "Memory allocation failed!\n");
exit(EXIT_FAILURE);
}
return o;
}
これは基本的に私のコーヒーブレイクで組み立てられたものであり、厳密にテストされていないことに注意してください. これが役立つことを願っています。