1

二分探索木を実装する必要がある uni の課題があります。情報を取得してディスクに書き込み、インデックスをツリーに格納しておく必要があります。ただし、ツリーに関係する関数を呼び出すたびに、プログラムがクラッシュします。次のコード スニペットは、私の bTree.h ファイルと、クラッシュの原因となったコードです。

/* binary tree ADT */

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

#define DATA_LENGTH 12
#define POS_LENGTH 8

struct INFO
{
    char data[DATA_LENGTH];
    int filePos;
};

struct NODE
{
    struct INFO data;
    struct NODE *left;
    struct NODE *right;
};


/* 
format for index data file

data identifier     12 bytes
position in file    8 bytes
--end of record--   total 20 bytes

*/

/* 
 Given a binary tree, return true if a node 
 with the target data is found in the tree. Recurs 
 down the tree, chooses the left or right 
 branch by comparing the target to each node. 
*/ 

int lookupPos(struct NODE *node, char target[]) 
{ 
    int length = strlen(target);

    // 1. Base case == empty tree 
    // in that case, the target is not found so return false 
    if (node == NULL) 
    { 
        return -1; 
    }        

    else 
    { 
        // 2. see if found here, in which case return file pos. 
        if (strncmp(target, node->data.data, length) == 0)
        {
            return node->data.filePos;
        }       

        else 
        { 
            // 3. otherwise recur down the correct subtree 
            if (strncmp(target, node->data.data, length) < 0)
        {
            return lookupPos(node->left, target);
        }

            else 
            {
                return lookupPos(node->right, target); 
            }
        }    
    } 
} 


/* 
 Give a binary search tree and a number, inserts a new node 
 with the given number in the correct place in the tree. 
 Returns the new root pointer which the caller should 
 then use (the standard trick to avoid using reference 
 parameters). 
*/ 
struct NODE *insert(struct NODE *node, char info[], int pos) 
{ 
    int length = strlen(info);
    // 1. If the tree is empty, return a new, single node 
    if (node == NULL) 
    { 
        struct INFO stuff; 
        strncpy(stuff.data, info, DATA_LENGTH);
        stuff.filePos = pos;

        node->data = stuff; 
        node->left = NULL; 
        node->right = NULL;

        return(node); 

    }    

    else 
    { 
        // 2. Otherwise, recur down the tree 
        if (strncmp(info, node->data.data, length) <= 0) 
        {
            node->left = insert(node->left, info, pos); 
        }

        else 
        {
            node->right = insert(node->right, info, pos);
        }

        return(node); // return the (unchanged) node pointer 
    } 
} 

struct NODE *loadTree(char filename[]) //cIndex.dat for customers, pIndex.dat for products
{
    struct NODE *node;
    char data[DATA_LENGTH];
    char posStr[POS_LENGTH];

    FILE* file; 
    file = fopen(filename,"rb");

    char c;
    fseek(file, 0, SEEK_SET);

    while((c = fgetc(file)) != EOF) //reads until EOF char
    {
        fseek(file, -1, SEEK_CUR); 


        fread(data, sizeof(char), DATA_LENGTH, file);
        fread(posStr, sizeof(char), POS_LENGTH, file);

        insert(node, data, atoi(posStr));

    }       

    fclose(file);

    return node;
}

int saveTree(struct NODE *node, char filename[], int posInFile)
{
    FILE *file;
    file = fopen(filename, "r+b");

    char c;
    char posStr[POS_LENGTH];

    fseek(file, posInFile, SEEK_SET);

    while((c = fgetc(file)) != EOF)
    {
        fseek(file, -1, SEEK_CUR);

        fwrite(node->data.data, sizeof(char), DATA_LENGTH, file);
        sprintf(posStr, "%d", node->data.filePos);
        fwrite(posStr, sizeof(char), POS_LENGTH, file);

        posInFile = ftell(file);

        saveTree(node->left, filename, posInFile);
        saveTree(node->right, filename, posInFile);
    }

    fclose(file);

    return 1;
}

int getSize(struct NODE *node)
{
    if (node==NULL) 
    { 
        return 0; 
    }

    else 
    { 
        return( getSize(node->left) + 1 + getSize(node->right)); 
    } 
}

そして今、問題のコードスニペット:

int filePos = getSize(tree);

と

insert(tree, cust.id, filePos);
saveTree(tree, "cIndex.dat", 0);

誰でも私を助けることができますか？

4

1 に答える 1

2

メモリを割り当てることはありません。あなたのinsert機能では：

if (node == NULL) 
{ 
    struct INFO stuff; 
    strncpy(stuff.data, info, DATA_LENGTH);
    stuff.filePos = pos;

    node->data = stuff; 
    node->left = NULL; 
    node->right = NULL;

    return(node); 

}

「それならnode、NULLそれに何かを割り当て始めます」。うわぁ！

あなたがする必要があるのはこれです：

node = malloc( sizeof(struct NODE) );

そして、私が大きな問題として見ているもう1つのことはこれです：

struct NODE *loadTree(char filename[])
{
    struct NODE *node;
    ...
}

後で内部でその値を使用nodeするため、に初期化する必要があります。NULLinsert

また、Daniel Fischer は、文字列が 1 バイト短すぎる可能性があることを既に指摘しています(したがって、文字列関数をloadTree確実に呼び出して関連付けることはできません)。strlen

于 2013-01-10T02:20:11.197 に答える