c - 如何在BST中搜索节点？

Question

我试图在 BST 中搜索字符串键。

节点和keydata_t的结构如下。

struct node {
char *key;
char *details;
BST* left;
BST* right;
};

typedef struct{
 char *name;
 char *data;
}datatype_t;    

typedef struct{
 char *name;
}keydata_t;

我的搜索功能代码:

struct node*search(BST *root, keydata_t *t){
    BST *r = root;  

    if (r != NULL){
        printf("here\n");   
    if(strcmp(r->key, t->name) == 0){
        printf("found\n");
    }
    else if(strcmp(r->key,t->name) < 0){
        printf("left\n");
        return search(r->left, t);
    }
    else {
        printf("right\n");
        return search(r->right, t);
}
}

插入函数:

struct node*insert(struct node*r, datatype_t *d){

if(r == NULL)
{
    //printf("empty\n");
    r = (struct node*)malloc(sizeof(struct node));
    r->key = d->name;
    r->details = d->data; 
    r->left = r->right = NULL;
    return r; 
}

else if(strcmp(r->key, d->name ) <= 0){
    r->left = insert(r->left ,d);
}
else if(strcmp(r->key, d->name ) > 0){
    r->right = insert(r->right,d);
}
return r;

}

读取函数:

FILE* safe_open_file(const char* file_name, const char* mode)
{
FILE* csv = fopen(file_name,mode);
if(csv==NULL){
    printf("%s %c ad\n",file_name,*mode);
    exit(EXIT_FAILURE);
    return NULL;
}
return csv;
}
void printfile(FILE* fp, datatype_t* d)
{
char name[64+1];
char data[1465+1];
fprintf(fp, "%s--> %s", d->name, d->data);
}

datatype_t*read(FILE* fp)
{
 char name[66];
 char data[1466];
 if (fscanf(fp, "%[^,] %[^\n]", name, data) == 2) {
    datatype_t *d = (datatype_t*)malloc(sizeof(datatype_t));
    d->name = strdup(name);
    d->data = strdup(data);
    return d;
}
return NULL;
}
keydata_t*read_key(FILE* fp){

char buffer[66];
if (fgets(buffer,sizeof buffer, fp) != NULL ) {
    keydata_t *k = (keydata_t*)malloc(sizeof(keydata_t));
    size_t len = strlen(buffer);
    if(buffer > 0 &&  buffer[len-1] == '\n'){
        buffer[--len] = '\0';
    }
    k->name = strdup(buffer);
    return k;
}
return NULL;
}

主要功能:

int main(int argc, char** argv)
{
char* dataset = NULL;
char* dataset1 = NULL;
char* key = NULL;
char* read_mode="r";
char* write_mode="w+";
struct node* root = NULL;

if(argv[1]!=NULL && argv[2] != NULL && argv[3] != NULL)
{
    dataset=argv[1];
    dataset1 = argv[2];
    key = argv[3];
}
else
{
    return EXIT_FAILURE;
}
FILE* Data_input = safe_open_file(dataset,read_mode);
FILE* Data_output = safe_open_file(dataset1, write_mode);
FILE* keyfile = safe_open_file(key, read_mode);

datatype_t **ptr = (datatype_t**)malloc(MAX_NUM_LINE*sizeof(datatype_t *));
datatype_t *ptr_one;
keydata_t *keyt;


int index = 0;
while((ptr_one = read(Data_input)) != NULL)
{
    root = insert(root, ptr_one);

}

while((keyt = read_key(keyfile))!= NULL){
    search(root, keyt);
}




fclose(Data_input);
fclose(Data_output);
fclose(keyfile);

}

由于某种原因，它在任何时候都不会打印找到。

这些是我使用 fgets 从 txt 文件中获取的 key 。

尼尔先生
威瑞森
key

因此，从我的 Bst 来看，它应该返回找到第一个键，但不返回其余键。我的输出不会打印任何内容，它只是执行。

Answer 1

你的代码有很多问题

1. 您的search()函数是递归的，但是当 root == NULL 时它不会返回，并调用未定义行为。

2. 有一个类型 datatype_t在您的代码中未在任何地方定义，并且 BST也不是 defiend，所以我怀疑这是真正的代码，因为它无法编译。

3. 您转换 void *从 malloc() 返回其中is not only unecessary but can be a problem 。但你从不检查它是否返回 NULL我认为这不是问题，而是很好的做法。

4. 你永远不会free() malloc() ed内存，这也不是问题，但总体来说很糟糕。特别是，如果您的程序需要保存很长时间。