Мой код для обхода предварительного бинарного дерева поиска работает, но как работает стек, каждый элемент которого является указателем на структуру? - PullRequest
Новая
       6

Мой код для обхода предварительного бинарного дерева поиска работает, но как работает стек, каждый элемент которого является указателем на структуру?

0 голосов
/ 09 февраля 2019

Это мой код обхода предзаказа BST.На Ubuntu работает нормально.Но я не понимаю одну вещь.В функции iterative_preorder() я действительно хотел, чтобы в стеке сохранялись указатели на структуру, которую я определил сверху.Я хочу знать концепцию, как это работает.Поскольку, выделяя память для стека, я нигде отдельно не указывал, что в стеке должно содержаться size количество указателей на структуру.

Например, когда мы определяем: 

int stack[size];

Мы знаем, что stack[1] будет вторым блоком в стеке.Но здесь я использовал malloc, который на самом деле просто делает один блок размером, заданным как size * sizeof(node *).

Итак, когда программа выполняется: 

stack[++top] = root;

Как программа понимаетчто он должен перейти к следующему указателю на структуру в стеке?Надеюсь, мой вопрос ясен.

Я сделал еще одну небольшую программу, основанную на путанице, которая у меня была.Здесь вместо структуры я использовал int.Я попытался создать стек размером 2, который хранит указатели на целое число.Вот код: 

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

void main() {
    int** stack = (int**)malloc(2 * sizeof(int*));
    printf("%d", *stack[0]);
}

Но этот код выбрасывает segmentation fault (core dumped).Поскольку оба кода использовали одну и ту же логику, но этот код использовал вместо структуры, я не понимаю, почему это вызывает ошибку.

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

int size = 0;

typedef struct mylist {
    int data;
    struct mylist *left;
    struct mylist *right;
} node;
node *root;

void create_root(node *root) {
    root = NULL;
}

//Inserting nodes
node *insert(node *root, int val) {
    node *ptr, *parentptr, *nodeptr;
    ptr = (node*)malloc(sizeof(node));
    ptr->data = val;
    ptr->left = NULL;
    ptr->right = NULL;
    if (root == NULL)
        root = ptr;
    else {
        parentptr = NULL;
        nodeptr = root;
        while (nodeptr != NULL) {
            parentptr = nodeptr;
            if (val < nodeptr->data)
                nodeptr = nodeptr->left;
            else
                nodeptr = nodeptr->right;
        }
        if (val < parentptr->data)
            parentptr->left = ptr;
        else
            parentptr->right = ptr;
    }
    return root;
}

void iterative_preorder(node *root) {
    if (root != NULL) {
        int top = -1;
        node **stack = (node**)malloc(size * sizeof(node*));
        node *cur;
        stack[++top] = root;
        while (top > -1) {
            cur = stack[top--];
            printf("%d\t", cur->data);
            if (cur->right != NULL)
                stack[++top] = cur->right;
            if (cur->left != NULL)
                stack[++top] = cur->left;
        }
    }
}

void main() {
    int option, val;
    node *ptr;
    int flag = 1;
    create_root(root);
    while (flag != 2) {
        printf("\nChoose-\n1-Insert\n2-Iterative Preorder Traversal\n3-Exit\n");
        scanf("%d", &option);
        switch (option) {
        case 1: {
                printf("\nEnter the value of new node\n");
                size++;
                scanf("%d", &val);
                root = insert(root, val);
            }
            break;
        case 2:
            iterative_preorder(root);
            break;
        case 3:
            flag = 2;
            break;
        default:
            printf("\nWrong entry\n");
        }
    }
}

1 Ответ

0 голосов
/ 09 февраля 2019

Ваш код имеет разыменование ошибки неинициализированного указателя.

    int** stack = (int**)malloc(2*sizeof(int*));
    printf("%d",*stack[0]);

В приведенном выше коде stack указывает на массив из двух int указателей, на что указывает стек [0]?это не инициализировано.

Доступен живой тест вашего кода здесь segfault .Вы можете изменить и протестировать его снова.

...