c - 二叉搜索树上的段错误 - 大排序

Question

尝试做this Big Sorting problem on Hackerrank 。我知道有更简单的方法来编写算法，但我正在努力温习我的 C 知识，因此想挑战自己并为该问题编写一个二叉搜索树。

我编写的二叉搜索树似乎适用于整数，但是，问题的输入类型是数字形式的字符串。所以我尝试将其更改为使用字符数组，并且 strcmp()为了比较数字字符串。

有人可以帮我弄清楚这里发生了什么以及我如何解决这个问题吗？

段错误:

GDB trace:
Reading symbols from solution...done.
[New LWP 11287]
Core was generated by `solution'.
Program terminated with signal SIGSEGV, Segmentation fault.
#0  strlen () at ../sysdeps/x86_64/strlen.S:106
#0  strlen () at ../sysdeps/x86_64/strlen.S:106
#1  0x00007f4f76b2e455 in __strcpy_chk (dest=0xfb0020 "", src=0x0, 
    destlen=105) at strcpy_chk.c:28
#2  0x00000000004007e3 in strcpy (__src=0x0, __dest=<optimized out>)
    at /usr/include/x86_64-linux-gnu/bits/string3.h:110
#3  create_node (key=0x0) at solution.c:25
#4  0x00000000004006af in main () at solution.c:70

代码:

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

#define MAXLEN 105

struct tree_node {
    char key[MAXLEN];
    struct tree_node *left;
    struct tree_node *right;
}; typedef struct tree_node Node;

Node *create_node(char *key) {
    Node *new_node;

    if ((new_node = (Node*)malloc(sizeof(Node))) == NULL) {
        printf("Cannot allocate memory for new node");
        exit(1);
    }

    strcpy(new_node->key, key);

    //new_node->key = key;
    new_node->left = NULL;
    new_node->right = NULL;

    return (new_node);
}

Node *insertNode(Node *node, char *keyInput) {
    if (node == NULL) {
        return (create_node(keyInput));
    } else {
        if (strcmp(keyInput, node->key) <= 0) {
            node->left = insertNode(node->left, keyInput);
        } else {
            node->right = insertNode(node->right, keyInput);
        }
        return (node);
    }
    return 0;
}

void printTree(Node *tree) {
    if (tree != NULL) {
        printTree(tree->left);
        printf("%s\n", tree->key);
        printTree(tree->right);
    }
}

int main() {
    // Enter your code here. Read input from STDIN. Print output to STDOUT
    int i, n = 0;
    char *input;
    Node *tree = NULL;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf("%s", input);
        tree = insertNode(tree, input);
    }

    printTree(tree);

    return 0;
}

Answer 1

您将未初始化的指针传递给 scanf() 来读取字符串。您应该将 input 定义为数组:

int main(void) {
    // Enter your code here. Read input from STDIN. Print output to STDOUT
    int i, n;
    char input[105];
    Node *tree = NULL;

    if (scanf("%d", &n) == 1) {
        for (i = 0; i < n; i++) {
            if (scanf("%104s", input) != 1)
                break;
            tree = insertNode(tree, input);
        }
        printTree(tree);
    }
    return 0;
}

这种方法的问题是它不适合问题空间:

• 该网站表示，这些行包含以十进制编码的数字，不带前导零，但长度最多为 10⁶ 字节。您无法使用“scanf()”轻松高效地解析此类输入。
• 此外，strcmp() 不适合比较这些条目:您应该首先比较长度，并且仅对具有相同位数的条目使用 strcmp()。