Дважды связанный список в C: Почему я должен явно переназначать голову и хвост, даже если они не изменены? - PullRequest
Новая
       14

Дважды связанный список в C: Почему я должен явно переназначать голову и хвост, даже если они не изменены?

0 голосов
/ 02 декабря 2018

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

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

У меня эти "указатели на указатели" инициированы в их собственной функции и сохранены в структуре, которая содержит оба.

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

Я пытаюсь понять, что происходит.Может быть, структура, удерживающая голову / хвост, должна быть определена статически / глобально?

Источник здесь: 

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

typedef struct dcl_node {
  char *content;
  struct dcl_node *next;
  struct dcl_node *prev;
} Node;

Node *create_node (char *content) {
  Node *n = malloc(sizeof(Node));
  n->content = content;
  n->next = NULL;
  n->prev = NULL;
  return n;
}

typedef struct dc_list {
  struct dcl_node **head;
  struct dcl_node **tail;
} DCList ;

DCList *init_list (char *content_head, char *content_tail) {
  Node *head = create_node(content_head);
  Node *tail = create_node(content_tail);
  head->next = tail;
  tail->prev = head;
  DCList *list = malloc(sizeof(DCList));
  list->head = &head;
  list->tail = &tail;
  return list;
}

void insert_head (char *content, DCList *list) {
  Node *old_head = *list->head;
  Node *old_tail = *list->tail; // note the saving here
  Node *node = create_node(content);
  node->next = old_head;
  old_head->prev = node;
  *list->head = node;
  *list->tail = old_tail; // and reassigning here
}

void insert_tail (char *content, DCList *list) {
  Node *old_head = *list->head; // note the saving here
  Node *old_tail = *list->tail;
  Node *node = create_node(content);
  node->prev = old_tail;
  old_tail->next = node;
  *list->head = old_head; // and reassigning here
  *list->tail = node;
}

int main (int argc, char *argv[]) {
  DCList *list = init_list("c", "d");

  insert_head("b", list);

  // If I don't explicitly save and reassign the tail node, 
  // in this case both head and tail would become the "b node".
    printf("head: %s\ntail: %s\n",
      (*list->head)->content, (*list->tail)->content);

  return 0;
}

1 Ответ

0 голосов
/ 02 декабря 2018

Поскольку list->head и list->tail являются указателями на локальные переменные в функции init_list.

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

По совпадению, когда вы сохраняете их в insert_head и insert_tail, ваши сохраненные переменные head и tail (возможно!) Получают одинаковые адреса памяти, поэтому они не перезаписываются.В противном случае старый head может быть перезаписан на node.

Это приблизительное объяснение - трудно сказать, что на самом деле делает компилятор.Но ключевым моментом является то, что head и tail уничтожаются при возврате init_list, а затем ваши list->head и list->tail указывают на свободную память, которую можно использовать повторно.

...