Самореференциальная структура, содержащая три указателя (называемые left, right и parent) - PullRequest
Новая
       1

Самореференциальная структура, содержащая три указателя (называемые left, right и parent)

0 голосов
/ 13 апреля 2019

У меня есть этот вопрос в моем задании, и я понятия не имею, если кто-нибудь может помочь мне с этим

Мне нужно создать самоссылочную структуру, содержащую три указателя (называемые left, right и parent) к другим экземплярам той же структуры, а также к указателю на массив 1d, тип которого может изменяться. 

    struct node { 
        int* left; 
        int* right;
        int* parent;
        struct node* link; 
    }; 

    int main() 
    { 
        struct node ob; 
        return 0; 
    }

Ответы [ 3 ]

1 голос
/ 13 апреля 2019

, содержащий три указателя (называемых left, right и parent) на другие экземпляры той же структуры,

Это требование приведет к: 

    struct node { 
        struct node * left; 
        struct node * right;
        struct node * parent;

, а также указатель на 1d массив, тип которого может меняться.

И это можно сделать с помощью void*: 

        void * data;
    };
1 голос
/ 13 апреля 2019

Если вы все еще застряли, то, чтобы помочь вам направить вас в правильном направлении, структура данных, с которой вы работаете, будет очень похожа на двоичное дерево .Дешевой раздачей являются указатели left и right, которые будут указывать на другие узлы в дереве.Единственное добавление, которое вы добавляете, - это указатель parent, который, по-видимому, вы хотите указать назад на узел над текущим в дереве, что позволит выполнять итерацию от текущего узла обратно к корневому узлу дерева по любому пути в пределахtree.

В этом случае базовая структура, которая вам нужна: 

typedef struct node { 
    struct node* left; 
    struct node* right;
    struct node* parent;
    int *data; 
} node;

( note: a typedef было добавлено, чтобы разрешить использованиеnode как тип, вместо того, чтобы всегда вводить struct node)

То, что вы делаете со структурой, зависит от вас, но логически это будет использоваться подобно двоичному дереву с единственными добавлениями - назначить узел для предыдущего уровня в дереве как узел parent в каждом листе.Базовая функция для создания каждого узла (с минимальным количеством сообщений об ошибках) может быть: 

void *create_node (int *data)
{
    node *p = malloc (sizeof *p);

    if (!p) {
        perror ("malloc-create_node");
        return NULL;
    }

    p->data = data ? data : NULL;
    p->left = NULL;
    p->right = NULL;
    p->parent = NULL;

    return p;
}

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

Функция вставки для добавления узла будет обычной вставкой btree с добавлением присваивания указателю узла parent адреса адресаузел непосредственно над ним в дереве, например, 

void insert (node *tree, int *data)
{
    if (!tree->data)
        tree->data = data;
    else if (data && *data <= *tree->data) {
        if (!tree->left) {
            tree->left = create_node (data);
            tree->left->parent = tree->left;
        }
        else
            insert (tree->left, data);
    }
    else if (data && *data > *tree->data) {
        if (!tree->right) {
            tree->right = create_node (data);
            tree->right->parent = tree->right;
        }
        else
            insert (tree->right, data);
    }
}

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

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

typedef struct node { 
    struct node* left; 
    struct node* right;
    struct node* parent;
    int *data; 
} node;

void *create_node (int *data)
{
    node *p = malloc (sizeof *p);

    if (!p) {
        perror ("malloc-create_node");
        return NULL;
    }

    p->data = data ? data : NULL;
    p->left = NULL;
    p->right = NULL;
    p->parent = NULL;

    return p;
}

void insert (node *tree, int *data)
{
    if (!tree->data)
        tree->data = data;
    else if (data && *data <= *tree->data) {
        if (!tree->left) {
            tree->left = create_node (data);
            tree->left->parent = tree->left;
        }
        else
            insert (tree->left, data);
    }
    else if (data && *data > *tree->data) {
        if (!tree->right) {
            tree->right = create_node (data);
            tree->right->parent = tree->right;
        }
        else
            insert (tree->right, data);
    }
}

void preorder (node *tree)
{
    if (tree) {
        printf ("%10p  %10p  %10p  ->  %p   {%d, %d}\n", 
                (void*)tree->left, (void*)tree->parent, (void*)tree->right,
                (void*)tree->data, tree->data[0], tree->data[1]);
        preorder (tree->left);
        preorder (tree->right);
    }
}

void inorder (node *tree)
{
    if (tree) {
        inorder (tree->left);
        printf ("%10p  %10p  %10p  ->  %p   {%d, %d}\n", 
                (void*)tree->left, (void*)tree->parent, (void*)tree->right,
                (void*)tree->data, tree->data[0], tree->data[1]);
        inorder (tree->right);
    }
}

void postorder (node *tree)
{
    if (tree) {
        postorder (tree->left);
        postorder (tree->right);
        printf ("%10p  %10p  %10p  ->  %p   {%d, %d}\n", 
                (void*)tree->left, (void*)tree->parent, (void*)tree->right,
                (void*)tree->data, tree->data[0], tree->data[1]);
    }
}

void freetree (node *tree)
{
    if (tree) {
        if (tree->left)
            freetree (tree->left);
        if (tree->right)
            freetree (tree->right);
        free (tree);
    }
}

int main(void) {

    int array[][2] = {{1, 2}, {3, 4}, {5, 6}, {2, 4}, {4, 5}},
        n = sizeof array / sizeof *array;
    struct node *ob = create_node (NULL);

    for (int i = 0; i < n; i++)
        insert (ob, array[i]);

    puts ("\n    left       parent       right          data\n"
          "---------------------------------------------------------------\n"
          "preorder:\n");
    preorder (ob);
    puts ("\ninorder:\n");
    inorder (ob);
    puts ("\npostorder:\n");
    postorder (ob);

    freetree (ob);
}

Пример использования / Вывод 

$ ./bin/treelrp

    left       parent       right          data
---------------------------------------------------------------
preorder:

     (nil)       (nil)    0xad2040  ->  0x7ffc0dbd68a0   {1, 2}
  0xad20a0    0xad2040    0xad2070  ->  0x7ffc0dbd68a8   {3, 4}
     (nil)    0xad20a0       (nil)  ->  0x7ffc0dbd68b8   {2, 4}
  0xad20d0    0xad2070       (nil)  ->  0x7ffc0dbd68b0   {5, 6}
     (nil)    0xad20d0       (nil)  ->  0x7ffc0dbd68c0   {4, 5}

inorder:

     (nil)       (nil)    0xad2040  ->  0x7ffc0dbd68a0   {1, 2}
     (nil)    0xad20a0       (nil)  ->  0x7ffc0dbd68b8   {2, 4}
  0xad20a0    0xad2040    0xad2070  ->  0x7ffc0dbd68a8   {3, 4}
     (nil)    0xad20d0       (nil)  ->  0x7ffc0dbd68c0   {4, 5}
  0xad20d0    0xad2070       (nil)  ->  0x7ffc0dbd68b0   {5, 6}

postorder:

     (nil)    0xad20a0       (nil)  ->  0x7ffc0dbd68b8   {2, 4}
     (nil)    0xad20d0       (nil)  ->  0x7ffc0dbd68c0   {4, 5}
  0xad20d0    0xad2070       (nil)  ->  0x7ffc0dbd68b0   {5, 6}
  0xad20a0    0xad2040    0xad2070  ->  0x7ffc0dbd68a8   {3, 4}
     (nil)       (nil)    0xad2040  ->  0x7ffc0dbd68a0   {1, 2}

ПамятьПроверка использования / ошибок

В любом написанном вами коде, который динамически распределяет память, у вас есть 2 обязанностей в отношении любого выделенного блока памяти: (1) всегда сохраняется указательк начальному адресуess для блока памяти, таким образом, (2) он может быть освобожден , когда он больше не нужен.

Обязательно, чтобы вы использовали программу проверки ошибок памяти для обеспеченияВы не пытаетесь получить доступ к памяти или выполнить запись за пределами / за пределами выделенного блока, пытаетесь прочитать или основать условный переход на неинициализированном значении и, наконец, подтвердить, что вы освобождаете всю выделенную память.

Для Linux valgrind является нормальным выбором.Для каждой платформы есть похожие проверки памяти.Все они просты в использовании, просто запустите вашу программу через нее. 

$ valgrind ./bin/treelrp
==24386== Memcheck, a memory error detector
==24386== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==24386== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==24386== Command: ./bin/treelrp
==24386==

    left       parent       right          data
---------------------------------------------------------------
preorder:

     (nil)       (nil)   0x51db0a0  ->  0xffefffc00   {1, 2}
 0x51db160   0x51db0a0   0x51db100  ->  0xffefffc08   {3, 4}
     (nil)   0x51db160       (nil)  ->  0xffefffc18   {2, 4}
 0x51db1c0   0x51db100       (nil)  ->  0xffefffc10   {5, 6}
     (nil)   0x51db1c0       (nil)  ->  0xffefffc20   {4, 5}

inorder:

     (nil)       (nil)   0x51db0a0  ->  0xffefffc00   {1, 2}
     (nil)   0x51db160       (nil)  ->  0xffefffc18   {2, 4}
 0x51db160   0x51db0a0   0x51db100  ->  0xffefffc08   {3, 4}
     (nil)   0x51db1c0       (nil)  ->  0xffefffc20   {4, 5}
 0x51db1c0   0x51db100       (nil)  ->  0xffefffc10   {5, 6}

postorder:

     (nil)   0x51db160       (nil)  ->  0xffefffc18   {2, 4}
     (nil)   0x51db1c0       (nil)  ->  0xffefffc20   {4, 5}
 0x51db1c0   0x51db100       (nil)  ->  0xffefffc10   {5, 6}
 0x51db160   0x51db0a0   0x51db100  ->  0xffefffc08   {3, 4}
     (nil)       (nil)   0x51db0a0  ->  0xffefffc00   {1, 2}
==24386==
==24386== HEAP SUMMARY:
==24386==     in use at exit: 0 bytes in 0 blocks
==24386==   total heap usage: 5 allocs, 5 frees, 160 bytes allocated
==24386==
==24386== All heap blocks were freed -- no leaks are possible
==24386==
==24386== For counts of detected and suppressed errors, rerun with: -v
==24386== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

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

Ваша реализациянужды могут быть немного другими, но основы будут похожими.Дайте мне знать, если у вас есть дополнительные вопросы.

0 голосов
/ 13 апреля 2019 
struct node
{
    void *left;
    void *right;
    void *parent;
    struct node *link;
}

Я думаю, вы должны использовать указатель void.Но вы должны знать, что означает этот указатель.Может представлять собой массив 1d или структуру.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...