Функция ввода в дважды связанном списке произвольно указывает на элемент заголовка после вызова pop()

Question

EDIT: Я думаю, что мой вопрос полностью отличается от предлагаемого дубликата. Он спрашивает об общем случае, в то время как мой вопрос задает очень конкретный случай, когда причина для странного поведения должна быть прослеживаемой, учитывая, насколько она конкретна.

У меня есть действительно странное поведение в моей двойной реализации LL. В принципе, если я pop() (с головы) элемент и , тоinject() (добавить в хвост) какой-то другой элемент, который последний элемент хвоста теперь указывает на голову списка, по-видимому, без причины (я предполагаю вместо NULL по умолчанию или хотя бы случайный адрес).

Я понял, как исправить проблему. При инъекции я не указывал «следующий» нового узла на NULL.

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

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

EDIT: Так что я попытался распечатывания адрес, указатель, указывающий только после вызова таНос в inject(), и по какой-то сумасшедшей причине указатель создано уже указывает на адрес голова; но это происходит только в том случае, если я вызываю pop() перед вызовом inject(). Невероятно странно ...

int pop() 
{ 
    node* temp = head; 
    int value = temp->value;  
    head = temp->next; 
    free(temp); 
    head->previous = NULL; 
    size--; 
    return value; 
} 

void inject(int value) 
{ 
    if (tail == NULL) 
    {    
     tail = malloc(sizeof(node)); 
     tail->value = value; 
     tail->next = NULL; 
     tail->previous = NULL; 
     head = tail; 
     size++; 
    } 
    else 
    { 
     node* new_node = malloc(sizeof(node)); 
     printf("pointing to: %p\n", new_node->next);// points to head after pop() call 
     new_node->value = value; 
     tail->next = new_node; 
     new_node->previous = tail; 
     tail = new_node; 
     //new_node->next = NULL; 
     size++; 
    } 
} 

Закомментированный из линии в Inject() решает эту проблему, но до сих пор не объясняет, почему хвост будет указывать обратно на голову, если я впрыснуть после поп-музыки.

Ниже приведен код, прежде чем основной() в случае, если:

typedef struct node{ 
    int value;  
    struct node* next; 
    struct node* previous;  
}node; 

node* head = NULL; 
node* tail = NULL; 

int head_value(); 
int tail_value(); 
void push(int); 
int pop(); 
void inject(int); 
int eject(); 

int size = 0; 

Answer 1

node* new_node = malloc(sizeof(node)); 
    printf("pointing to: %p\n", new_node->next);// points to head after pop() call 

new_node->next будет содержать все, что мусор malloc хочет поставить там. Возможно, произойдет, чтобы указать на голову, но вы никогда не инициализировали его, так что printf пытается найти смысл в мусоре.

Ваш код рассеивает память по всему месту. Вместо того, чтобы пытаться это исправить, давайте перепишем его, используя мою рекомендацию по контенту о структурах: always писать функции для их инициализации и уничтожения. Всегда, даже если это кажется глупым и тривиальным. Это позволяет избежать рассеяния этого кода повсюду, делая это немного по-разному каждый раз. Это позволяет вам тестировать основные функции структуры, прежде чем пытаться ее использовать. Это позволяет вам сосредоточиться на алгоритме, а не на управлении памятью.

---

Во-первых, давайте сделаем настройку для вашей структуры. node - очень плохое имя для типа. Вероятно, вам (или кому-то еще) захочется вызвать переменную node и вызвать конфликт. Я назвал его Node, заглавными, чтобы избежать путаницы с переменными и встроенными.

typedef struct Node { 
    int value;  
    struct Node* next; 
    struct Node* previous;  
} Node; 

Теперь мы можем написать Node_new и Node_destroy.

Node *Node_new() { 
    Node *node = malloc(sizeof(Node)); 
    node->value = 0; 
    node->next = NULL; 
    node->previous = NULL; 

    return node; 
} 

void Node_destroy(Node *node) { 
    free(node); 
} 

Node_destroy может показаться глупым, но это освобождает вас (или кого-либо еще) от того, чтобы вспомнить, как уничтожить Node. И он позволяет вам изменить внутреннюю структуру Node без изменения остальной части кода (что произошло при написании этого).

---

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

typedef struct { 
    Node *head; 
    Node *tail; 
    size_t size; 
} LinkedList; 

И ему нужны свои собственные функции создания и уничтожения.

LinkedList *LinkedList_new() { 
    LinkedList *list = malloc(sizeof(LinkedList)); 
    list->head = NULL; 
    list->tail = NULL; 
    list->size = 0; 

    return list; 
} 

void LinkedList_destroy(LinkedList *list) { 
    for(Node *node = list->head; node != NULL; node = node->next) { 
     Node_destroy(list->head); 
    } 

    free(list); 
} 

Обратите внимание, что LinkedList_destroy берет на себя ответственность за очистку всех его узлов, его одна вещь меньше для пользователя LinkedList беспокоиться о потенциально завинтить.

LinkedList_destroy может звонить в Node_destroy, не зная ничего о том, как Node работает. Так мы сразу получаем выгоду от инкапсуляции и абстракции Node. Но не используйте рекурсию, список может быть произвольно длинным, а рекурсия - переполнением стека.

Теперь мы можем написать push и pop, чтобы все было правильно создано и уничтожено. Обратите внимание, что они берут LinkedList, а не используют глобальные переменные.

void LinkedList_push(LinkedList *list, int value) 
{ 
    Node *node = Node_new(); 
    node->value = value; 

    switch(list->size) { 
     /* The list is empty, this is the first node */ 
     case 0: 
      list->head = list->tail = node; 
      break; 
     default: 
      list->tail->next = node; 
      node->previous = list->tail; 
      list->tail = node; 
      break; 
    } 

    list->size++; 
} 

int LinkedList_pop(LinkedList *list) { 
    Node *popped = list->tail; 

    switch(list->size) { 
     /* The list is empty, nothing to pop */ 
     case 0: 
      fprintf(stderr, "LinkedList was empty when popped.\n"); 
      exit(1); 
      break; 
     /* Popped the last node */ 
     case 1: 
      list->head = list->tail = NULL; 
      break; 
     /* Only one node left, it's both the head and tail */ 
     case 2: 
      list->tail = list->head; 
      list->tail->previous = list->tail->next = NULL; 
      break; 
     default: 
      list->tail = popped->previous; 
      list->tail->next = NULL; 
      break; 
    } 

    /* Have to do this at the end because size_t is unsigned 
     it can't go negative */ 
    list->size--; 

    int value = popped->value; 
    Node_destroy(popped); 

    return value; 
} 

я использовал switch так что я могу четко разграничить все особые случаи.

Я не говорю, что это лучшая реализация push и pop, или что это даже ошибка, но они могут быть написаны, не беспокоясь о том, правильно ли они были инициализированы или освобождены. Вы можете сосредоточиться на логике, а не на управлении памятью.

---

А затем, чтобы продемонстрировать это все работает ...

void LinkedList_print(LinkedList *list) { 
    for(Node *node = list->head; node != NULL; node = node->next) { 
     printf("%d\n", node->value); 
    } 
} 

int main() { 
    LinkedList *list = LinkedList_new(); 

    for(int i = 0; i < 3; i++) { 
     LinkedList_push(list, i); 
    } 

    while(list->size != 0) { 
     printf("list->size: %zu\n", list->size); 
     LinkedList_print(list); 
     LinkedList_pop(list); 
    } 

    LinkedList_destroy(list); 
} 

$ ./test 
list->size: 3 
0 
1 
2 
list->size: 2 
0 
1 
list->size: 1 
0