1

c でビット文字列からバイナリ ツリーを作成しています。つまり、1100100 はツリーを作成します。

  1
 / \
1   1

このツリーを構築するために再帰関数を使用することにしましたが、Debug assertion failed... というエラーが表示され続けます。 Expression : CrtIsValidHeapPointer(pUserData)

ここに私のコードの断片があります

typedef
struct Node {
  char key;
  struct Node *left;
  struct Node *right; 
} Node;

char string[1000];
int i = 0;

void insertRecursivePreorder(Node **node)
{
    Node* parent = *node;
    if(string[i] == '0')
    {
        parent = NULL;
        i++;
    }
    else
    {
        Node *newn = (Node*)malloc(sizeof(Node));
        newn->key = string[i];
        parent = newn;
        i++;
        insertRecursivePreorder(&newn->left); //errors occur here
        insertRecursivePreorder(&newn->right); //errors occur here
        free(newn);
        free(parent);
    }
}

int main(void)
{
    void printTree(Node* node);
    Node* root = NULL;
    scanf("%s", string);
    insertRecursivePreorder(&root);
    //... do other junk
}

このエラーが発生する理由と、それを修正するために何ができるのか疑問に思っていました。

4

2 に答える 2

1

free当面の問題は、ポインターを 2 回呼び出す可能性があります。ではinsertRecursivePreorder、 に設定parentしてからnewn、両方を呼び出しますfree。free(..)この例として、次のプログラムは失敗します (ただし、 s の1 つをコメントアウトすると機能します)。

#include <stdlib.h>
int main() {
  int *a = malloc(sizeof(int)),
      *b = a;
  free(a);
  free(b);
  return 0;
}

ただし、ここでのロジックにはいくつかの問題があります。ポインターを完全freeに使い終わったときにのみ呼び出す必要があるため、後でツリーを使用する場合は、構築中に解放することはできません。ツリーを通過して呼び出す2 番目の関数 を作成する必要があります (下から上へ!)。recursiveDestroyTreefree

そして、後者は実際に を変更する唯一のものであるため、おそらく*node = newnではなく が必要です。parent = newnnode

Node *(ポインタを返すように関数を変更してから、次のようにすることもできます。

root = insertRecursivePreorder();

と

newn->left = insertRecursivePreorder();
newn->right = insertRecursivePreorder();

ポインターへのポインターなどを追跡しようとする代わりに)

(さらに、文体上の点で、グローバル変数を使用することはしばしば悪い習慣であるため、グローバル変数の代わりにinsertRecursivePreorderテイクint iとchar * stringパラメーターを使用することができます。)

于 2012-04-28T02:39:58.403 に答える
0

問題は、「insertRecursivePreorder」でダブルポインタに割り当てていなかったため、rootが常にNULLのままだったことです。

#include <stdio.h>
#include <stdlib.h>

typedef
struct Node {
  char key;
  struct Node *left;
  struct Node *right;
} Node;

        /* slightly changed the syntax for the str
        ** ; now '.' indicates a NULL pointer, values represent themselves.
        */
char *string = "12..3.." ;
/* Removed the global index 'i' */

void printTree(Node* node, int level);
unsigned insertRecursivePreorder(Node **pp, char *str);

unsigned insertRecursivePreorder(Node **pp, char *str)
{
    unsigned pos =1;
    if (!*str) { *pp = NULL; return 0; } /* safeguard for end of string */
    if (*str == '.') { *pp = NULL; return pos; }

    *pp  = malloc(sizeof **pp);
    (*pp)->key = *str;
    pos += insertRecursivePreorder(&(*pp)->left, str+pos);
    pos += insertRecursivePreorder(&(*pp)->right, str+pos);
    return pos;
}

void printTree(Node* node, int level)
{
unsigned pos,len;
len = level> 0 ? level : -level;

    for (pos =0; pos < len; pos++) putchar (' ');
    if (!level) printf ("Root=");
    else if (level<0) printf ("Left=");
    else printf ("Right=");
    if (!node) { printf( "Null\n" ); return; }
    printf("Key=%c\n", node->key );
    printTree(node->left, -(len+1) ) ;
    printTree(node->right, len+1) ;
}

int main(void)
{   
    Node *root = NULL;
    unsigned result = 0;
    result = insertRecursivePreorder(&root, string);
    printf( "Result=%u\n", result);
    printTree(root, 0);
    return 0; printTree(root, 0);
}

出力：

Result=7
Root=Key=1
 Left=Key=2
  Left=Null
  Right=Null
 Right=Key=3
  Left=Null
  Right=Null
于 2012-04-28T12:37:01.950 に答える