ошибка сегментации (ядро сброшено) в бинарном дереве поиска

Question

Я пытаюсь реализовать дерево r & b, но сначала я хочу простое двоичное дерево (которое не сохраняет содержимое на его листьях), а затем реализую свойства r & b.Проблема в том, что я получаю ошибку сегментации, которую я не могу объяснить.

Программа выглядит следующим образом:

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

typedef struct node
{
    unsigned long int val;
    bool black;
    struct node* parent;
    struct node* lchild;
    struct node* rchild;
}mynode;

mynode* createNode(unsigned long int ival, mynode* father);
mynode* createLeaf(unsigned long int ival, mynode* father);
mynode* search (unsigned long int ival, mynode *root);
void insert ( unsigned long int ival, mynode *root);


int main()
{
    mynode root;
    mynode *rootptr;
    mynode *leafptr;
    FILE *fp;
    int ch;
    unsigned long long lines=0, i=0;
    unsigned long *myArr;
    unsigned long int ival;

   fp = fopen("integers.txt","r");
   if(fp == NULL)
   {
      printf("Error in opening file.");
      return(-1);
   }

    while(!feof(fp))
    {
    ch = fgetc(fp);
    if(ch == '\n')
    {
        lines++;
    }
    }
    lines++;
    printf("lines = %lu", lines);
    myArr = (unsigned long*)calloc(lines, sizeof(unsigned long));

    fseek(fp, 0, SEEK_SET);
    while(!feof(fp))
    {
          fscanf(fp, "%lu,", &myArr[i] ); // des ta pos k giati tou input.
          i++;
    }
    fclose(fp);

    root.val = myArr[0];
    root.parent = NULL;
    root.lchild = NULL;
    root.rchild = NULL;
    root.black = true;
    rootptr = &root;
    leafptr = createLeaf(rootptr->val, rootptr);
    rootptr->lchild = leafptr;
    leafptr = createLeaf(rootptr->val, rootptr);
    rootptr->rchild = leafptr;
    for(i=1; i<lines; i++)
    {
        ival = myArr[i];
        insert(ival, rootptr);
    }

    return 0;
}

mynode* createNode(unsigned long int ival, mynode* father)
{
  mynode* nodeptr;
  mynode node;
  nodeptr = &node;
  nodeptr->val = ival;
  nodeptr->lchild = NULL;
  nodeptr->rchild = NULL;
  nodeptr->parent = father;
  nodeptr->black = true;
  return nodeptr;
}

mynode* createLeaf(unsigned long int ival, mynode* father)
{
  mynode* nodeptr;
  mynode leaf;
  nodeptr = &leaf;
  nodeptr->val = ival;
  nodeptr->lchild = NULL;
  nodeptr->rchild = NULL;
  nodeptr->parent = father;
  nodeptr->black = true;
  return nodeptr;
}

mynode* search (unsigned long int ival, mynode *rootptr)
{
    mynode* myptr;

    myptr = rootptr;

    while ( ( (myptr->lchild) != NULL) && ( (myptr->rchild) != NULL))
    {
        if ( ival < myptr->val)
        {
            myptr = myptr->lchild;
        }
        else
        {
            myptr = myptr->rchild;
        }
    }
    return myptr;
    }

void insert (unsigned long int ival, mynode *root)
{
    mynode * current;
    mynode * leafptr;
    mynode * father;
    unsigned long int max, min;
    unsigned long int num;

    current = search(ival, root);
    num = current->val;
    if((current->val) == ival)
    {
        return ;
    }
    else
    {
        if(ival>(current->val))
        {
            max = ival;
            min = current->val;
        }
        else
        {
            max = current->val;
            min = ival;
        }
        father = current->parent;
        current = createNode(min, father);
        if(num == (father->lchild)->val)
        {
            father->lchild = current;
        }
        else
        {
            father->rchild = current;
        }
        leafptr = createLeaf(min, current);
        current->lchild = leafptr;
        leafptr = createLeaf(max, current);
        current->rchild = leafptr;
       return ;
    }
}

Я открываю файл.Подсчитайте количество строк, потому что я знаю, что каждая строка имеет один номер.Создайте массив, используя вышеуказанную информацию.Затем я создаю корень и его 2 листа.И затем я вставляю (там я получаю ошибку сегментации) остальную часть массива в мою структуру данных.Я думаю, что проблема заключается в функциях.

Вот текстовый файл с цифрами.

Answer 1

Слишком много ошибок и проблем, чтобы разобраться.

Давайте вместо этого рассмотрим правильный пример с проверкой ошибок, который выводит сгенерированное двоичное дерево поиска в формате Graphviz DOT.

Во-первых, вы хотите сохранить указатели в начале структуры, потому что они наиболее часто используются и требуют правильного выравнивания.(Если вы не ставите наибольшие члены первыми, компилятор может вставить заполнение в ваши структуры, тратя впустую память. Нет, компилятору не разрешается переупорядочивать элементы структуры в C, поэтому он не может сделать это за вас.)

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

struct node {
    struct node *parent;
    struct node *left;
    struct node *right;
    double       value;
};

Далее нам нужна функция для создания нового узла.Рекомендуется проверить malloc(), возвращающие NULL, и, если это так, прервать программу:

struct node *new_node(const double value)
{
    struct node *n;

    n = malloc(sizeof (struct node));
    if (!n) {
        fprintf(stderr, "Out of memory.\n");
        exit(EXIT_FAILURE);
    }

    n->parent = NULL;
    n->left = NULL;
    n->right = NULL;
    n->value = value;

    return n;
}

Далее вам понадобится функция, которая вставит узел в дерево.Само дерево является просто дескриптором своего корневого члена, и, поскольку новый узел может быть новым корнем, нам нужно передать указатель на указатель на корневой элемент:

void insert_node(struct node **root, struct node *leaf)
{
    struct node *parent;

    /* Make sure we have a pointer to the root pointer, and a leaf node. */
    if (!root) {
        fprintf(stderr, "insert_node(): root == NULL!\n");
        exit(EXIT_FAILURE);
    }
    if (!leaf) {
        fprintf(stderr, "insert_node(): leaf == NULL!\n");
        exit(EXIT_FAILURE);
    }

    /* Make sure leaf pointers are all NULL. */
    leaf->parent = NULL;
    leaf->left = NULL;
    leaf->right = NULL;

Приведенный выше кодпросто проверки работоспособности, но я хотел включить их для полноты.В любом случае, если дерево пусто, корневой указатель указывает на нулевой указатель, то есть *root == NULL.В этом случае leaf является новым (единственным) узлом в дереве:

    /* Is this a new root node? */
    if (!*root) {
        /* Yes. */
        *root = leaf;
        return;
    }

В противном случае нам нужно спуститься в дерево.Я решил, что left означает «меньше или равно» , потому что это легко запомнить.Если мы идем налево, а левый узел родителя пуст, именно туда мы поместим новый листовой узел.Точно так же, если мы идем правильно, и правый узел родителя пуст, мы помещаем лист там.В противном случае мы спускаемся.

    /* Find the parent node where leaf belongs. */
    parent = *root;
    while (1)
        if (parent->value >= leaf->value) {
            if (parent->left) {
                parent = parent->left;
                continue;
            }

            /* This belongs at parent->left. */
            parent->left = leaf;
            leaf->parent = parent;
            return;

        } else {
            if (parent->right) {
                parent = parent->right;
                continue;
            }

            /* This belongs at parent->right. */
            parent->right = leaf;
            leaf->parent = parent;
            return;
        }
}

Чтобы пройти по дереву и напечатать его структуру на языке DOT, нужно всего две функции: рекурсивная функция для печати узла и основная функция для печати шаблона, ивызвать рекурсивную функцию.Я использую %p или значение указателя узла в качестве идентификатора узла, потому что это просто и надежно:

static void dot_recurse(FILE *out, struct node *one)
{
    fprintf(out, "    \"%p\" [ label=\"%.3f\" ];\n", (void *)one, one->value);

    if (one->parent)
        fprintf(out, "    \"%p\" -> \"%p\";\n", (void *)one, (void *)(one->parent));

    if (one->left) {
        dot_recurse(out, one->left);
        fprintf(out, "    \"%p\" -> \"%p\" [ label=\"≤\" ];\n", (void *)one, (void *)(one->left));
    }

    if (one->right) {
        dot_recurse(out, one->right);
        fprintf(out, "    \"%p\" -> \"%p\" [ label=\">\" ];\n", (void *)one, (void *)(one->right));
    }
}

void dot(FILE *out, struct node *tree)
{
    if (out && tree) {
        fprintf(out, "digraph {\n");
        dot_recurse(out, tree);
        fprintf(out, "}\n");
    }
}

Выше стрелки на родительском элементе будут помечены, стрелки на левом дочернем элементе будут помечены ≤,и стрелки справа от ребенка будут помечены > рядом с серединой стрелки.

Обратите внимание, что для dot() первый параметр - это поток, в который будет отправлен файл, а второй параметр - этоуказатель на корневой узел.Поскольку мы не модифицируем дерево, достаточно указателя на корневой узел;нам не нужен указатель на указатель на корневой узел.

Наконец, нам нужно прочитать значения из потока (здесь, стандартный ввод), построить узел дерева из каждого проанализированного значения и вставитьих к дереву.Нет абсолютно никакой причины читать файл дважды, так как количество значений не имеет значения: мы можем просто читать значения, пока не сможем!

int main(void)
{
    struct node *tree = NULL;
    double       value;

    while (scanf(" %lf", &value) == 1)
        insert_node(&tree, new_node(value));

    /* Dump tree in DOT format. Use Graphviz to visualize the output. */
    dot(stdout, tree);

    return EXIT_SUCCESS;
}

Последняя часть main() просто выводит дерево в DOTотформатировать в стандартный вывод и выйти (успешно).Нет необходимости освобождать динамически выделенную память перед выходом, поскольку операционная система сделает это автоматически.

Допустим, у нас есть входной файл in.txt, содержащий

4.695 5.108 3.518 4.698 8.496
7.956 9.435 5.341 0.583 7.074
7.661 5.966 0.557 4.332 1.436
6.170 7.936 4.630 7.694 0.220

, и мывыполнил нашу программу, передал этот файл на его стандартный ввод и передал вывод, чтобы сказать out.dot.(В Linux, Mac OS и BSD это будет просто ./binary < in.txt > out.dot после компиляции вышеуказанного исходного кода C в исполняемый файл с именем binary в текущем каталоге.)

В этом случае out.dot будет содержать

digraph {
    "0x13dd020" [ label="4.695" ];
    "0x13dd080" [ label="3.518" ];
    "0x13dd080" -> "0x13dd020";
    "0x13dd1a0" [ label="0.583" ];
    "0x13dd1a0" -> "0x13dd080";
    "0x13dd260" [ label="0.557" ];
    "0x13dd260" -> "0x13dd1a0";
    "0x13dd3b0" [ label="0.220" ];
    "0x13dd3b0" -> "0x13dd260";
    "0x13dd260" -> "0x13dd3b0" [ label="≤" ];
    "0x13dd1a0" -> "0x13dd260" [ label="≤" ];
    "0x13dd2c0" [ label="1.436" ];
    "0x13dd2c0" -> "0x13dd1a0";
    "0x13dd1a0" -> "0x13dd2c0" [ label=">" ];
    "0x13dd080" -> "0x13dd1a0" [ label="≤" ];
    "0x13dd290" [ label="4.332" ];
    "0x13dd290" -> "0x13dd080";
    "0x13dd350" [ label="4.630" ];
    "0x13dd350" -> "0x13dd290";
    "0x13dd290" -> "0x13dd350" [ label=">" ];
    "0x13dd080" -> "0x13dd290" [ label=">" ];
    "0x13dd020" -> "0x13dd080" [ label="≤" ];
    "0x13dd050" [ label="5.108" ];
    "0x13dd050" -> "0x13dd020";
    "0x13dd0b0" [ label="4.698" ];
    "0x13dd0b0" -> "0x13dd050";
    "0x13dd050" -> "0x13dd0b0" [ label="≤" ];
    "0x13dd0e0" [ label="8.496" ];
    "0x13dd0e0" -> "0x13dd050";
    "0x13dd110" [ label="7.956" ];
    "0x13dd110" -> "0x13dd0e0";
    "0x13dd170" [ label="5.341" ];
    "0x13dd170" -> "0x13dd110";
    "0x13dd1d0" [ label="7.074" ];
    "0x13dd1d0" -> "0x13dd170";
    "0x13dd230" [ label="5.966" ];
    "0x13dd230" -> "0x13dd1d0";
    "0x13dd2f0" [ label="6.170" ];
    "0x13dd2f0" -> "0x13dd230";
    "0x13dd230" -> "0x13dd2f0" [ label=">" ];
    "0x13dd1d0" -> "0x13dd230" [ label="≤" ];
    "0x13dd200" [ label="7.661" ];
    "0x13dd200" -> "0x13dd1d0";
    "0x13dd320" [ label="7.936" ];
    "0x13dd320" -> "0x13dd200";
    "0x13dd380" [ label="7.694" ];
    "0x13dd380" -> "0x13dd320";
    "0x13dd320" -> "0x13dd380" [ label="≤" ];
    "0x13dd200" -> "0x13dd320" [ label=">" ];
    "0x13dd1d0" -> "0x13dd200" [ label=">" ];
    "0x13dd170" -> "0x13dd1d0" [ label=">" ];
    "0x13dd110" -> "0x13dd170" [ label="≤" ];
    "0x13dd0e0" -> "0x13dd110" [ label="≤" ];
    "0x13dd140" [ label="9.435" ];
    "0x13dd140" -> "0x13dd0e0";
    "0x13dd0e0" -> "0x13dd140" [ label=">" ];
    "0x13dd050" -> "0x13dd0e0" [ label=">" ];
    "0x13dd020" -> "0x13dd050" [ label=">" ];
}

и, если визуализируется (например, dot -Tsvg out.dot > out.svg), будет выглядеть так:

Как видите, каждый левый ребенок равенили меньше, чем его родитель, и каждый правый ребенок больше, чем его родитель.Использование вывода на языке DOT, как этот, также является отличным методом отладки функций дерева;Вы даже можете использовать форму узла (например, овал или прямоугольник), чтобы указать красный / черный - или использовать фактические цвета.Список атрибутов DOT здесь .

Answer 2

mynode* nodeptr;
mynode node;
nodeptr = &node;

Здесь node живет в стеке в памяти, которая будет возвращена при выходе из функции.Вы возвращаете указатель на память, которой вы не владеете!Вы захотите использовать функцию malloc(), например, так:

mynode* nodeptr = malloc(sizeof(mynode));

Это выделит память в куче, на которую будет указывать nodeptr.Эта память не будет возвращена при выходе из функции.Чтобы восстановить эту память, вам нужно будет позвонить free().