使用二叉搜索树的 C 语言简单数据库

问题描述 投票：0回答：1

我的任务是用 C 语言编写一个简单的数据库。该程序将接收标准输入中的指令并打印其结果。说明的格式如下：

<operation>: <year> <month> <day> <name>
。有 3 个操作：“S”（搜索）、“F”（查找）和“D”（删除）。存储指令会将条目存储在数据库中，如果条目已在数据库中，则打印“已存储”或“已存储”。如果该条目在数据库中，查找指令将打印“找到”，否则将打印“未找到”。删除指令将从数据库中删除该条目，如果找到该条目，则打印“已删除”，否则将打印“未找到”。

由于时间限制，我不能简单地使用链表作为我的解决方案。首先，我尝试使用哈希映射（pastebin 链接）。我尝试使用二叉搜索树，但对条目进行哈希处理（pastebin链接）。这些尝试都没有成功（他们通过了简单的测试，但在大型测试中失败了）。最后我只是尝试了“最简单”的方法 - 存储整个条目的二叉树。这次尝试也通过了简单的测试，但在大型测试中失败了......现在我完全陷入困境。这是我当前的代码：

#ifdef __STDC_LIB_EXT1__
    #define __STDC_WANT_LIB_EXT1__ 1
    #define scanf scanf_s // Bit hacky ngl.
#endif

#include <stddef.h> // NULL
#include <stdio.h>  // scanf()/scanf_s(), puts()
#include <stdlib.h> // malloc(), free()
#include <string.h> // strcmp()

typedef struct {
    unsigned short year;
    unsigned char month, day;
    char *name;
} User;

typedef struct BinaryTreeNode {
    struct BinaryTreeNode *left, *right;
    User user;
} BinaryTree;

static inline BinaryTree *BinaryTree_alloc(User user) {
    BinaryTree *tree = (BinaryTree *) malloc(sizeof(BinaryTree));
    tree->left  = NULL;
    tree->right = NULL;
    tree->user  = user;
    return tree;
}

static inline void BinaryTree_dealloc(BinaryTree *tree) {
    if (tree) {
        BinaryTree_dealloc(tree->left);
        BinaryTree_dealloc(tree->right);
        free(tree);
    }
}

int BinaryTree_compare(BinaryTree *tree, User user) {
         if (tree->user.year  > user.year)  return  1;
    else if (tree->user.year  < user.year)  return -1;
    else if (tree->user.month > user.month) return  1;
    else if (tree->user.month < user.month) return -1;
    else if (tree->user.day   > user.day)   return  1;
    else if (tree->user.day   < user.day)   return -1;
    else return strcmp(tree->user.name, user.name);
}

BinaryTree *BinaryTree_store(BinaryTree *tree, User user) {
    if (tree) {
        switch (BinaryTree_compare(tree, user)) {
            case  1: tree->left  = BinaryTree_store(tree->left,  user); break;
            case -1: tree->right = BinaryTree_store(tree->right, user); break;
            default: puts("Already stored");
        }
        return tree;
    }
    puts("Stored");
    return BinaryTree_alloc(user);
}

BinaryTree *BinaryTree_find(BinaryTree *tree, User user) {
    if (tree)
        switch (BinaryTree_compare(tree, user)) {
            case  1: return BinaryTree_find(tree->left,  user);
            case -1: return BinaryTree_find(tree->right, user);
            default: puts("Found");
        }
    else puts("Not found");
    return tree;
}

static inline User BinaryTree_find_min_user(BinaryTree *tree) {
    while (tree->left) tree = tree->left;
    return tree->user;
}

BinaryTree *BinaryTree_delete(BinaryTree *tree, User user) {
    if (tree)
        switch (BinaryTree_compare(tree, user)) {
            case  1: tree->left  = BinaryTree_delete(tree->left,  user); break;
            case -1: tree->right = BinaryTree_delete(tree->right, user); break;
            default:
                if (!tree->left && !tree->right) {
                    free(tree->user.name);
                    free(tree);
                    tree = NULL;
                    puts("Deleted");
                }
                else if (!tree->left || !tree->right) {
                    BinaryTree *root = tree;
                    if (!tree->left)  tree = tree->left;
                    if (!tree->right) tree = tree->right;
                    free(root->user.name);
                    free(root);
                    puts("Deleted");
                }
                else {
                    User min_user = BinaryTree_find_min_user(tree->right);
                    tree->user  = min_user;
                    tree->right = BinaryTree_delete(tree->right, min_user);
                }
        }
    else puts("Not found");
    return tree;
}

int main() {
    char operation;
    User user;
    BinaryTree *tree = BinaryTree_alloc((User) { 0, 0, 0, NULL });
    while (5 == scanf(" %c : %hu %hhu %hhu %m[^\n]",
        &operation,
        &user.year,
        &user.month,
        &user.day,
        &user.name)) {
        switch (operation) {
            case 'S': BinaryTree_store (tree, user); break;
            case 'F': BinaryTree_find  (tree, user); break;
            case 'D': BinaryTree_delete(tree, user); break;
        }
    }
    BinaryTree_dealloc(tree);
}

有人请帮助我：3

c database binary-tree binary-search-tree binary-search
1个回答
0
投票

  1. 我不确定问题是什么，但您提到“大型”测试失败，因此在递归函数上从传递 

    User
    切换到 
    User *
    将使用更少的堆栈空间。 （不固定）C 不保证尾部调用优化，因此您应该更喜欢迭代而不是递归算法，后者本质上具有未绑定的堆栈大小要求。

  2. 如果您先处理特殊情况，那么通常很长的正常情况的缩进就会较少。这也是您通常期望的递归函数（首先是基本情况）。

  3. BinaryTree_compare()
    很奇怪，因为您正在比较两个用户，因此将其更改为 
    User_compare()
    并传入两个 
    User *
    。调用者假定函数返回 
    -1
    、
    0
    或 
    1
    ，但 
    strcmp()
    的情况并非如此，因此请确保现在确实如此。在通话中，我还切换了参数，因为对我来说，-1 表示树的 
    left
    侧和 
    +1
    右侧更有意义。

  4. （未修复）考虑重构 

    BinaryTree_find()
    和/或 
    BinaryTree_store()
    以消除非常相似的代码。

  5. main()
    分配一个空节点，但我认为仅仅盯着 NULL 更有意义。

  6. 我删除了

    inline
    ，因为编译器可能比你更了解它是否使用它。我可能会删除 
    BinaryTree_find_min_user()
    并只在 
    BinaryTree_delete()
    中添加那句台词。

#ifdef __STDC_LIB_EXT1__
#define __STDC_WANT_LIB_EXT1__ 1
#define scanf scanf_s // Bit hacky ngl.
#endif

#include <stddef.h> // NULL
#include <stdio.h>  // scanf()/scanf_s(), puts()
#include <stdlib.h> // malloc(), free()
#include <string.h> // strcmp()

typedef struct {
    unsigned short year;
    unsigned char month, day;
    char *name;
} User;

typedef struct BinaryTreeNode {
    struct BinaryTreeNode *left, *right;
    User user;
} BinaryTree;

static BinaryTree *BinaryTree_alloc(const User *user) {
    BinaryTree *tree = malloc(sizeof *tree);
    tree->left  = NULL;
    tree->right = NULL;
    tree->user  = *user;
    return tree;
}

static void BinaryTree_dealloc(BinaryTree *tree) {
    if (!tree) return;
    BinaryTree_dealloc(tree->left);
    BinaryTree_dealloc(tree->right);
    free(tree);
}

int User_compare(const User *a, const User *b) {
    if (a->year > b->year)  return  1;
    else if (a->year  < b->year)  return -1;
    else if (a->month > b->month) return  1;
    else if (a->month < b->month) return -1;
    else if (a->day   > b->day)   return  1;
    else if (a->day   < b->day)   return -1;
    int rv = strcmp(a->name, b->name);
    return rv < 0 ? -1 : rv > 0 ? 1 : 0;
}

BinaryTree *BinaryTree_store(BinaryTree *tree, const User *user) {
    if (!tree) {
        puts("Stored");
        return BinaryTree_alloc(user);
    }
    switch (User_compare(user, &tree->user)) {
        case -1: tree->left = BinaryTree_store(tree->left, user); break;
        case 1: tree->right = BinaryTree_store(tree->right, user); break;
        default: puts("Already stored");
    }
    return tree;
}

BinaryTree *BinaryTree_find(BinaryTree *tree, const User *user) {
    if (!tree) {
        puts("Not found");
        return NULL;
    }
    switch (User_compare(user, &tree->user)) {
        case -1: return BinaryTree_find(tree->left, user);
        case  1: return BinaryTree_find(tree->right, user);
        default: puts("Found");
    }
    return tree;
}

static User *BinaryTree_find_min_user(BinaryTree *tree) {
    for (; tree->left; tree = tree->left);
    return &tree->user;
}

BinaryTree *BinaryTree_delete(BinaryTree *tree, User *user) {
    if (!tree) {
        puts("Not found");
        return tree;
    }
    switch (User_compare(user, &tree->user)) {
        case -1: tree->right = BinaryTree_delete(tree->right, user); break;
        case  1: tree->left  = BinaryTree_delete(tree->left,  user); break;
        default:
            if (!tree->left && !tree->right) {
                free(tree->user.name);
                free(tree);
                tree = NULL;
                puts("Deleted");
            }
            else if (!tree->left || !tree->right) {
                BinaryTree *root = tree;
                if (!tree->left)  tree = tree->left;
                if (!tree->right) tree = tree->right;
                free(root->user.name);
                free(root);
                puts("Deleted");
            }
            else {
                User *min_user = BinaryTree_find_min_user(tree->right);
                tree->user  = *min_user;
                tree->right = BinaryTree_delete(tree->right, min_user);
            }
    }
    return tree;
}

int main() {
    char operation;
    User *user = &(User) {0};
    BinaryTree *tree = NULL;
    while (5 == scanf(" %c : %hu %hhu %hhu %m[^\n]",
            &operation,
            &user->year,
            &user->month,
            &user->day,
            &user->name)) {
        switch (operation) {
            case 'S': tree = BinaryTree_store (tree, user); break;
            case 'F': BinaryTree_find  (tree, user); break;
            case 'D': BinaryTree_delete(tree, user); break;
        }
    }
    BinaryTree_dealloc(tree);
}

和示例运行：

$ cat input.txt
S : 2023 11 28 m
S : 2023 11 28 m
S : 2023 11 28 a
S : 2023 11 28 z
F : 2023 11 28 m
D : 2023 11 28 m
F : 2023 11 28 m
$ ./a.out < input.txt
Stored
Already stored
Stored
Stored
Found
Deleted
Not found
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.