Создание связанного списка в C, получение ошибки сегментации

Question

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

Ошибка сегментации происходит в отмеченной строке

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

typedef struct Node{
    char *value;
    struct Node *next;
}Node;
typedef struct Node** List;

Node *new_node(char *input);
void delete_node(Node *input);
void push(List list, char *value);
List new_list();

Node *new_node(char *input) {
  Node *new;
  new = malloc(sizeof(Node));
  new->value = input;
  return new;
}

void delete_node(Node *input) {
  free(input);
}

void push(List head, char *input) {
  if (*head == NULL) {  
    *head = new_node(input);
  }
  else {
    Node *new = new_node(input);
    while ((*head)->next != NULL) {
      *head = (*head)->next;
    }
    (*head)->next = new;    
  } 
}

List new_list() {
  List list = malloc(sizeof(List));
  *list = NULL;
  return list;
}

int main( void ) {
  List list = new_list();
  push(list, "First!\n");
  push(list, "Second!\n");
  push(list, "Third!\n");
  push(list, "Fourth!");

  printf("%s", (*list)->value);
  printf("%s", (*list)->next->value);
  printf("%s", (*list)->next->next->value);       //Segmentation fault
  printf("%s", (*list)->next->next->next->value);

  return 0;
}

Когда я запустил его с помощью gdb, я получил сообщение:

Third!                                                                                                               

Program received signal SIGSEGV, Segmentation fault.                                                                 
0x0000000000400752 in main () at main.c:54                                                                           
54        printf("%s", (*list)->next->next->value);

Answer 1

Когда вы создаете новый узел, вы никогда не устанавливаете next член вновь созданного узла. Это оставляет его неинициализированным, что приводит к неопределенному поведению при разыменовании указателя.

Исправление простое. Добавьте

new->next = NULL;

в функцию new_node после назначения value.

Answer 2

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

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

Объявление списка как указателей на заголовок (списка) и хвост (списка),

typedef struct {
    Node* head;
    Node* tail;
} List;

Вместо того, чтобы объявлять список как указатель на указатель на узел,

typedef struct Node** List;

Теперь сложность добавления в список и удаления из него составляет O (1) (операции с постоянным временем ...

//enqueue to tail of list (not push)
void enqueue(List* list, char *input) {
  if( !list ) return; //no list
  Node* new = new_node(input); //new node
  if( NULL == list->head ) { //list empty
    list->head = new; //add at tail, tail equals head
  }
  else {
    list->tail->next = new; //list not empty, add at tail
  }
  list->tail = new;
}

//dequeue from head of list
Node* dequeue(List* list) {
    if( !list ) return NULL; //no list
    if( NULL == list->head ) return NULL; //list empty
    Node* node = list->head; //node at head of list
    list->head = list->head->next; //remove from list
    if( NULL == list->head ) list->tail = NULL; //empty now
    //oh, should also: node->next = NULL;
    return node;
}

И, как уже говорили другие, вы должны инициализировать все указатели в вашем "конструкторе",

Node *new_node(char *input) {
  Node *new;
  if( ! (new = malloc(sizeof(Node))) ) return NULL;
  //new = calloc(sizeof(Node)); //calloc fills allocated memory with zero bytes
  //initialize all values in Node structure
  new->value = input;
  new->next = NULL; //either use calloc or init the individual elements
  return new;
}