Граф, содержащий структуру узла с двумя указателями

ProgramBox

Граф, содержащий структуру узла с двумя указателями

Post author:admin
Запись опубликована:25 декабря, 2022
Post category:Вопросы по программированию

#c #graph-theory

#c #теория графов

Вопрос:

Я пытаюсь написать простой график для хранения размеров созданных таблиц. Я новичок в C, поэтому прошу прощения, если я пропустил некоторые простые операции с указателями.

Мой график содержит prev долговые расписки и next указатели, где первый next будет указывать на последний узел и служить итератором для захвата next->next . Я не хочу хранить больше информации, чем эти два указателя и размер графика, поэтому можно добраться до узлов только через итерацию next указателя.

Вот минимальный воспроизводимый пример моего кода:

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

struct GC {
  uint data;
  uint size;
  struct GC *next;
  struct GC *prev;
};

void build_gc_root(struct GC **self) {
  // Build root node
  printf("Allocating gc.n");
  struct GC *tmp = malloc(sizeof *tmp);
  tmp->size = 0;
  tmp->data = 666;
  tmp->prev = tmp;
  tmp->next = tmp;
  printf("Saving allocation of gc.n");
  (*self) = tmp;
}

void gc_clean(struct GC **self) {
  uint _;
  printf("Cleaning the gc table.n");
  for (_ = 0; _ < (*self)->size   1;   _) {
    printf("Free node %hd.n", (*self)->next->next->data);
    free((*self)->next->next);
      (*self)->next;
  }
  printf("Free last node %hd.n", (*self)->next->data);
  free((*self)->next);
}

void gc_store(struct GC **self, uint data) {
  printf("Storing GC value node.n");
  (*self)->next = malloc(sizeof *(*self)->next);
  (*self)->next->data = data;
  (*self)->next->prev = (*self)->prev;
  (*self)->next->next = (*self);
  (*self)->prev = (*self)->next;
    (*self)->size;
}

typedef struct {
  void (*clean)();
  void (*get_size)(uint size);
  void (*print_table)();
  struct GC *gc;
}__controller;

__controller controller;

void controller_clean() {
  gc_clean(amp;controller.gc);
}

void controller_get_size(uint size) {
  gc_store(amp;controller.gc, size);
}

void controller_print_table() {
  uint index;
  printf("GC catch: n");
  for (index = 0; index < controller.gc->size   1;   index) {
    printf("  %hdn", controller.gc->next->next->data);
    --controller.gc->next;
  }
  putchar('n');
}

__controller controller = {
  controller_clean, controller_get_size, controller_print_table
};

int main (void) {
  build_gc_root(amp;controller.gc);
  controller.get_size(1);
  controller.get_size(2);
  controller.get_size(3);
  controller.print_table();
  controller.clean();
  return 0;
}

После выполнения этого controller.print_table() метода будут выведены только данные двух первых узлов и в конечном итоге произойдет ошибка сегментации.

1. (*self)->next = malloc(sizeof self); При этом выделяется память размером с указатель, next указывающий на элемент структуры. Вы должны использовать sizof (struct GC) или sizeof (* (*self)->next)`

2. Также (*self)->next; выглядит подозрительно. Вы не выделяете массивы. Арифметика указателей разрешена только в границах одного объекта данных, то есть массива. Также эта строка совершенно бесполезна, потому что вы присваиваете (*self)->next новое значение в следующей строке

3. Что вы подразумеваете под «итерацией»? Теперь указатель next указывает на amp;next[1] . Вы никогда не выделяете память более чем для 1 элемента next .

4. Вы имеете в виду, мне нужно выделить массив для хранения этих адресов? Разве это невозможно сделать, просто используя указатели?

5. @DanielFreeman Указатель похож на уличный адрес. Если вам нужен дом на данной улице, все, что вы делаете, просто добавляете 1 к адресу улицы? Нет, вы могли бы сделать это, только если у вас уже было несколько смежных лотов. В противном случае вам придется сначала купить участок и построить дом. Только тогда у вас может быть уличный адрес, который указывает на него, и тогда адрес действителен. C не мешает вам писать фиктивные адреса улиц, но они не делают воображаемый дом реальностью больше, чем это произошло бы в реальной жизни 🙂 malloc покупает землю. memset или функция конструктора строит дом.

Ответ №1:

По сути, вы создаете стек, который связан с помощью prev указателя. Это next довольно бесполезно, и вам следует подумать о его удалении.

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

Операторы и -- используемые для указателей перемещают их на следующий / предыдущий последовательный элемент в памяти. Это допустимо только в пределах массива, который вы не используете.

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

Это будет выглядеть так:

 void gc_clean(struct GC** self) {
    uint _;
    printf("Cleaning the gc table.n");
    struct GC* gc = (*self)->prev;
    for (_ = 0; _ < (*self)->size;   _) {
        printf("Free node %hd.n", gc->data);
        struct GC* tmp = gc;
        gc = gc->prev;
        free(tmp);
    }

    printf("Free last node %hd.n", gc->data);
    free(gc);
}

void controller_print_table() {
    uint index;
    printf("GC catch: n");
    struct GC* gc = controller.gc->prev;
    for (index = 0; index < controller.gc->size   1;   index) {
        printf("  %hdn", gc->data);
        gc = gc->prev;
    }
    putchar('n');
}

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

В качестве побочного узла вам следует подумать об именовании. Вызывается функция для добавления элемента в ваш стек, get_size что, мягко говоря, сбивает с толку…

Ответ №2:

Я публикую рабочий код ниже на случай, если кто-то захочет увидеть рабочий стек:

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

// Garbage collector stack
struct GC {
  uint data;
  uint size;
  struct GC *prev;
};

void build_gc_root(struct GC **self) {
  // Build root node
  printf("Allocating gc.n");
  struct GC *tmp = malloc(sizeof *tmp);
  tmp->size = 0;
  tmp->data = 666;
  tmp->prev = tmp;
  printf("Saving allocation of gc.n");
  (*self) = tmp;
}

void gc_clean(struct GC **self) {
  uint _;
  printf("Cleaning the gc table.n");
  struct GC *gc = (*self)->prev;
  for (_ = 0; _ < (*self)->size;   _) {
    printf("Free node %hdn", gc->data);
    struct GC* tmp = gc;
    gc = gc->prev;
    free(tmp);
  }
  printf("Free the last node %hdn", gc->data);
  free(gc);
}

void gc_store(struct GC **self, uint data) {
  printf("Storing GC value node.n");
  struct GC *node;
  node = malloc(sizeof *(*self)->prev);
  node->data = data;
  node->prev = (*self)->prev;
  (*self)->prev = node;
    (*self)->size;
}

void gc_print(struct GC *self) {
  uint index;
  struct GC *gc = self->prev`;
  printf("GC catch: ");
  for (index = 0; index < self->size   1;   index) {
    printf(" %hd", gc->data);
    gc = gc->prev;
  }
  putchar('n');
}

typedef struct {
  void (*clean)();
  void (*get_size)(uint size);
  void (*print_table)();
  struct GC *gc;
}__controller;

__controller controller;

void controller_clean() {
  gc_clean(amp;controller.gc);
}

void controller_get_size(uint size) {
  gc_store(amp;controller.gc, size);
}

void controller_print_table() {
  gc_print(controller.gc);
}

__controller controller = {
  controller_clean, controller_get_size, controller_print_table
};

int main (void) {
  build_gc_root(amp;controller.gc);
  controller.get_size(1);
  controller.get_size(2);
  controller.get_size(3);
  controller.print_table();
  controller.clean();
  return 0;
}