私は C の初心者で、K&R の本 The C Programming Language から学んでいます。バイナリ ツリーの演習を行った後、char*、long、および double のバイナリ ツリーのヘッダーを作成したいと考えました。
次のコードには、私を悲しませている関数があります。文字ポインタの配列に、辞書順でツリーに格納された値を入力する必要がありますが、どこかにバグがあります。文字列ツリー ヘッダー btree.h のコードは次のとおりです。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/************** TYPES **************/
typedef struct ctree
{
char *name;
ctree *left;
ctree *right;
};
/************** Globals **************/
static int c_inc = 0;
/************** Function Prototypes **************/
ctree *add_to_c_tree (ctree *cnode, char *name);
void print_c_tree (ctree *cnode);
ctree *c_tree_alloc (void);
void c_tree_free (ctree *cnode);
void return_c_tree (ctree *cnode, char **array);
/************** Function Definitions **************/
/* add_to_c_tree() : Adds a new node to a *character binary tree */
ctree *add_to_c_tree (ctree *cnode, char *name){
/* If the node is null, allocate memory for it,
* copy the name and set the internal nodes to null*/
if(cnode == NULL){
cnode = c_tree_alloc();
cnode->name = strdup(name);
cnode->left = cnode->right = NULL;
}
/* If initialised then add to the left node if it is lexographically
* less that the node above it else add it to the right node */
else{
if(strcmp(name, cnode->name) < 0)
cnode->left = add_to_c_tree(cnode->left,name);
else if(strcmp(name, cnode->name) > 0)
cnode->right = add_to_c_tree(cnode->right,name);
}
return cnode;
}
/* print_c_tree() : Print out binary tree */
void print_c_tree(ctree *cnode){
if (cnode != NULL) {
print_c_tree(cnode->left);
printf("%s\n",cnode->name);
print_c_tree(cnode->right);
}
}
/* return_c_tree() : return array of strings containing all values in binary tree */
void return_c_tree (ctree *cnode, char **array){
if (cnode != NULL) {
return_c_tree (cnode->left,array+c_inc);
c_tree_free(cnode->left);
*(array+c_inc++) = strdup(cnode->name);
// printf("arr+%d:%s\n", c_inc-1,*(array+(c_inc-1)));
return_c_tree (cnode->right,array+c_inc);
c_tree_free(cnode->right);
}
}
/* c_tree_alloc() : Allocates space for a tree node */
ctree *c_tree_alloc(void){
return (ctree *) malloc(sizeof(ctree));
}
/* c_tree_free() : Free's Memory */
void c_tree_free (ctree *cnode){
free(cnode);
}
私はbt.cでテストしています：
#include "btree.h"
int main(void){
ctree *node = NULL; char *arr[100];
node = add_to_c_tree(node, "foo");
node = add_to_c_tree(node, "yoo");
node = add_to_c_tree(node, "doo");
node = add_to_c_tree(node, "woo");
node = add_to_c_tree(node, "aoo");
node = add_to_c_tree(node, "boo");
node = add_to_c_tree(node, "coo");
print_c_tree(node);
return_c_tree(node,arr);
for (int i = 0; i < 7; ++i)
{
printf("%d:%s ..\n",i, arr[i]);
}
return 0;
}
この質問の理由は、return_c_tree() 関数に問題があったためです。この関数は、NULL ptr まで再帰的に自分自身を呼び出してノードの名前を出力する代わりに、K&R の print_c_tree() 関数の動作を模倣することを目的としています。辞書式の順序で、それらの名前を文字ptrの配列に追加し、ノードのメモリを解放することを意味します。
ただし、上記のように実行すると得られる出力は次のとおりです。
aoo
boo
coo
doo
foo
woo
yoo
0:aoo ..
1:(null) ..
2:boo ..
3:doo ..
4:foo ..
5:coo ..
6:(null) ..
これは、print 関数は正常に動作しますが、return 関数は明らかにそうではないことを示しています。紛らわしいのは、return_c_tree() 内の printf() の呼び出しがコメント化されていない場合、次の結果になることです。
aoo
boo
coo
doo
foo
woo
yoo
arr+0:aoo
arr+1:boo
arr+2:coo
arr+3:doo
arr+4:foo
arr+5:woo
arr+6:yoo
0:aoo ..
1:(null) ..
2:boo ..
3:doo ..
4:foo ..
5:coo ..
6:(null) ..
これは、実際に文字列を正しい順序で追加することを意味します。また、c_inc変数なしで試しました->つまり、正しいノードに渡す前に配列をインクリメントするだけで、return_c_tree()のprintfから同じ結果が生成されますが、メインとは異なります:
arr+-1:aoo
arr+-1:boo
arr+-1:coo
arr+-1:doo
arr+-1:foo
arr+-1:woo
arr+-1:yoo
0:foo ..
1:yoo ..
2:coo ..
3:(null) ..
4:(null) ..
5:(null) ..
6:(null) ..
私はかなり混乱しているので、誰かが助けてくれれば幸いです。間違った場所でインクリメントしているだけだと確信していますが、どこで解決できません。
ようやくポインターを理解したと思ったのですが、どうやらそうではありませんでした。
ベストP