0

これは、c で再帰関数を作成する初めての試みです。次のコードが機能します。長い投稿で申し訳ありませんが、できるだけ明確にしようとしています。

各ノード (inode) が整数フィールド "n" を持つツリーを生成しようとしています。これに対応して、各 i ノードには、「n」個の他の i ノードへのポインタの配列があります。関数inode *I = gen_tree(inode *I, int nlevels);は、各レベルで乱数の inode を持つツリーを生成します。ツリーは深さ優先で生成されます。いくつか質問があります。

(a) 関数を書くためのより良い方法はありますか?? フィードバック/提案をいただければ幸いです。

(b) ツリーは BF 形式で生成できますか?

(c)I->iツリーがトラバースされるインデックスが必要です。計算する関数を作成するにはどうすればよいI->iですか?

(d)I->c特定のノードの下にあるすべての inode の累積合計が必要です。計算する関数を作成するにはどうすればよいI->cですか?

前もって感謝します、

〜ラス

//.h file:
typedef struct integerNode {
  int n;
  int c;
  int i;
  struct integerNode **nodes;
} inode;
inode *new_inode( int n );
inode *gen_itree( inode *I, int nlevels );


//Constructor:
inode *new_inode( int n ){
    inode *I;
    I = malloc( sizeof (inode ) );
    I->n = n;
    I->nodes = malloc( n * sizeof (inode* ) );
    return (I );
};

//Generating tree with random-number of nodes:
inode *gen_itree( inode *I, int nlevels ){
    int i, next_level, next_n;
    printf( " \n" );
    printf( " I : %p\n", I );
    printf( " ***** nlevels : %d\n", nlevels );
    printf( " *************\n" );
    if ( nlevels == 0 ) {
        printf( " nlevels == 0!\n");
    } else {
        printf( " I->n : %d\n", I->n );
        printf( " *************\n" );
        next_level = nlevels - 1;
        for ( i = 0; i < I->n; i++ ) {
            printf( " I: %p\n",I);
            printf( " adding node number: %d\n", i );
            next_n = 0 + rand( ) % 3;
            I->nodes[i] = new_inode( next_n );
            printf( " I->nodes[%d]->n: %p, %d\n",i, I->nodes[i],next_n);
            I->nodes[i] = gen_itree( I->nodes[i], next_level );
        }
    }
    printf( " *************\n" );
    printf( " returning I : %p\n", I );//This part is unclear to me!
    printf( " *************\n" );
    return (I);
}

//Main.c
int main( int argc, char** argv ){
    inode *I;
    I = new_inode( 2 );
    I = gen_itree(I,3);
    return ( 1 );
}
4

2 に答える 2

1

初めに。エラーチェックはありません。あなたは幸せな道をコード化しただけです。malloc が NULL を返さないことを確認してください!!!

if (malloc returned NULL){
          free memory
          exit(error_code)
}

それで

 I->nodes[i] = new_inode( next_n );
 I->nodes[i] = gen_itree( I->nodes[i], next_level );

この部分はかなり不明です。あなたはこれを行うことができます

 I->nodes[i] = gen_itree( new_inode( next_n ), next_level );

ここも同じ

I = new_inode( 2 );
I = gen_itree(I,3);

になり得る

 I = gen_itree(new_inode( 2 ),3);

また、割り当てられたメモリを解放することを忘れないでください。

(d)については

unsigned int get_node_count(inode* i){
    unsigned int counter =0;

    if (!i->nodes) return 0;

     //pseudocode
     for each inode* node in i->nodes{
        counter++
        counter+= get_node_count(node);//accumulate node count in child node
     }

      return counter;
于 2009-10-14T04:38:26.987 に答える
1

すべてがかなり良さそうです。デバッグ目的でない限り、関数内にprintfを入れません。

#define RANGE 3 // this eliminates 'magic constants'

//Generating tree with random-number of nodes:
inode *gen_itree( inode *I, int nlevels ){
        int i, next_level, next_n;

    if ( nlevels ) { // if nlevels != 0
        next_level = nlevels - 1;
        for ( i = 0; i < I->n; i++ ) {
            next_n = rand( ) % RANGE; // no need for a zero
            I->nodes[i] = new_inode( next_n );
            I->nodes[i] = gen_itree( I->nodes[i], next_level );
        }
    }

    return I;
}

見た目は良くなりますが、さらに一歩進んで、不要なローカル変数をいくつか削除します。これらは 1 回しか使用されないためです (int i を除く)。

(c) の場合、これは機能するはずです。

//This computes the C's for all nodes under this, including this node  
int computeAllCs( inode *I ){
        int i;
        I->c = 0;
        for ( i = 0; i < I->n; i++ )
            I->c += computeAllCs(I->nodes[i]) + 1;
}

「すべての再帰関数は反復的に記述できる (別名ループ)」ことに注意してください。そのため、反復ソリューションを検討することをお勧めします。

于 2009-10-14T04:40:57.060 に答える