包含具有两个指针的节点结构的图

Question

我正在尝试编写一个简单的图形来存储已创建表的大小。我是 C 的新手，所以如果我错过了一些简单的指针操作，我很抱歉。

我的图表包含 previous 和 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(&controller.gc);
}

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

void controller_print_table() {
  uint index;
  printf("GC catch: \n");
  for (index = 0; index < controller.gc->size + 1; ++index) {
    printf("  %hd\n", 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(&controller.gc);
  controller.get_size(1);
  controller.get_size(2);
  controller.get_size(3);
  controller.print_table();
  controller.clean();
  return 0;
}

在运行之后，controller.print_table()方法将只输出两个第一个节点的数据并以分段错误结束。

Answer 1

基本上您正在创建一个通过 prev 指针链接的堆栈。 next 没什么用，您应该考虑删除它。

在打印或删除内容时，您使用了错误的机制来遍历您的列表。

运算符 ++ 和 -- 用于指针将它们移动到内存中的 next/previous 连续元素。这仅在您不使用的数组中有效。

相反，您需要按照结构中的链接到达下一个元素。

这看起来像这样：

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("  %hd\n", gc->data);
        gc = gc->prev;
    }
    putchar('\n');
}

请注意，这还会从您在创建过程中添加的堆栈中删除初始元素。此外，您 controller.gc 的指针不再有效。清空列表后需要重新初始化

作为侧节点，你应该考虑一下命名。将元素添加到堆栈的函数称为 get_size，委婉地说这很容易混淆...

Answer 2

我post下面的工作代码以防有人想看到工作堆栈：

#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 %hd\n", gc->data);
    struct GC* tmp = gc;
    gc = gc->prev;
    free(tmp);
  }
  printf("Free the last node %hd\n", 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(&controller.gc);
}

void controller_get_size(uint size) {
  gc_store(&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(&controller.gc);
  controller.get_size(1);
  controller.get_size(2);
  controller.get_size(3);
  controller.print_table();
  controller.clean();
  return 0;
}

包含具有两个指针的节点结构的图

Graph containing node structure with two pointers

c

graph-theory