Seg Fehler in binären Suchbaum - große Sortierung

Question

Versuch zu tun this Big Sorting problem on Hackerrank. Ich weiß, dass es einfachere Möglichkeiten gibt, den Algorithmus zu schreiben, aber ich versuche, mein C-Wissen aufzufrischen und wollte mich daher selbst herausfordern und einen Binärsuchbaum für das Problem schreiben.

Der binäre Suchbaum, den ich geschrieben habe, scheint für Ganzzahlen zu funktionieren, das Problem hat jedoch einen Eingabetyp von Strings in Form von Zahlen. Also habe ich versucht, es zu ändern, um Zeichenarrays zu verwenden, und strcmp(), um die Zeichenketten von Zahlen zu vergleichen.

Kann mir jemand helfen, herauszufinden, was hier vor sich geht und wie ich das Problem beheben könnte?

Seg-Fehler:

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 

Code:

#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

Sie übergeben einen nicht initialisierten Zeiger auf scanf() eine Zeichenfolge zu lesen. Sie sollten stattdessen definieren input als Array:

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; 
} 

Das Problem bei diesem Ansatz ist es nicht das Problem Raum paßt:

• Die Website sagt die Linien Zahlen in Dezimal ohne führende Nullen codiert enthalten, aber bis zu 10 Bytes lang. Sie können solche Eingaben nicht portabel und effizient mit `scanf() parsen.
• Außerdem ist strcmp() nicht geeignet, diese Einträge zu vergleichen: Sie sollten zuerst die Längen vergleichen und nur strcmp() auf Einträge mit der gleichen Anzahl von Ziffern verwenden.

Answer 2

Fokus hier:

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

Wo wird die Lese String gehen gespeichert werden? input ist char Zeiger, der nicht in der Nähe von gültigen Speicherplatz zeigt!

Lassen Sie uns für sie etwas Speicher zuweisen, indem sie es als ein Array definieren:

char input[MAXLEN]; 
for (i = 0; i < n; i++) { 
    scanf("104%s", input); 
} 

den Raum durch die Nullabschluss benötigt Vergessen Sie nicht, das ist, warum ich 104 verwendet (MAXLEN-1), die a Vorsichtsmaßnahme, um nicht mehr Speicher als input zu speichern.

Außerdem könnten Sie die Vorteile von dem, was scanf() kehrt nehmen und dies tun:

for (i = 0; i < n; i++) { 
    if(scanf("%104s", input) != 1) 
     break; // didn't read a one string, break the loop! 
    // I got the input, let's insert it to the tree.. 
}