Блог

Я реализовал связанный список на C.

Проблема в том, что всякий раз, когда я пытаюсь распечатать данные узлов с помощью функции print_list(struct linked_list *list) , я получаю ошибку сегментации.

Я не уверен, что является причиной этого, потому что, когда я пытаюсь print(struct linked_list *list) , это работает нормально.

И, когда я пытаюсь динамически выделять память, она также работает нормально. Но мне любопытно, что не так с кодом таким образом? И почему использование print не приведет к той же ошибке?

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

struct node{
    char data;
    struct node* next;
};

struct linked_list{
    struct node *head;
};

void concat(struct linked_list* list1, struct linked_list* list2)
{
    struct node* tmp = list1->head;
    
    while(tmp->next != NULL)
        tmp = tmp->next;
    tmp->next = list2->head;
}

void print_list(struct linked_list *list)
{
    struct node* tmp = list->head;
    while(tmp != NULL){
        printf("%c - ", tmp->data);
    tmp = tmp->next;}
    printf("n");
}

void print(struct linked_list *list)
{
    struct node* tmp = list->head;
    printf("%cn", tmp->data);
    tmp = tmp->next;
    printf("%cn", tmp->data);
    tmp = tmp->next;
    printf("%cn", tmp->data); 
}

int main()
{
    struct linked_list list1,list2;
    struct node n1,n2,n3,n4,n5;
    n1.data = 'A';
    n2.data = 'B';
    n3.data = 'C';
    n4.data = 'D';
    n5.data = 'E';
    n1.next = amp;n2;
    n2.next = amp;n3;
    
    n4.next = amp;n5;
    list1.head = amp;n1;
    list2.head = amp;n4;
    printf("List 1 containes :n");
    print_list(amp;list1);
    concat(amp;list1,amp;list2);
    printf("List 1 after concat: n" );
    print_list(amp;list1);

    return 0;
}
 

Здесь:

 struct node n1,n2,n3,n4,n5;
 

вы создаете пять узлов без их инициализации. C не инициализирует локальные переменные равными нулю или нулю, поэтому поля узлов имеют неопределенные («мусорные») значения. Позже вы инициализируете некоторые поля, но не next поля последних узлов в списке.

Существует несколько решений, например:

(1) Явно инициализируйте next поля последних узлов:

 n1.next = amp;n2;
n2.next = amp;n3;
n3.next = NULL;

n4.next = amp;n5;
n5.next = NULL;
 

(2) Инициализируйте узлы данными, затем установите ссылки:

 struct node n1 = {'A'};
struct node n2 = {'B'};
struct node n3 = {'C'};
struct node n4 = {'D'};
struct node n5 = {'E'};

n1.next = amp;n2;
n2.next = amp;n3;

n4.next = amp;n5;
 

Как только вы инициализируете структуру, все поля будут инициализированы, даже если значения (например, для next ) не заданы явно. В зависимости от типа эти поля неявно инициализируются нулем или нулем. Теперь у вас есть действительные (но не связанные) узлы, прежде чем вы установите ссылки.

(3) Определите все путем инициализации:

 struct node n5 = {'E', NULL};
struct node n4 = {'D', amp;n5};
struct linked_list list2 = {amp;n4};

struct node n3 = {'C', NULL};
struct node n2 = {'B', amp;n3};
struct node n1 = {'A', amp;n2};
struct linked_list list1 = {amp;n1};
 

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

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

Сначала попытайтесь понять, что segmentation fault это такое.

Согласно Википедии:

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

Итак, это происходит потому, что ваша программа обращается к ограниченному местоположению, к которому она не предназначена для доступа. Но почему? Потому что в while(tmp->next != NULL) программе не обязательно находить NULL , когда выполняется обход всех элементов. Таким образом, в этом случае цикл не прерывается, и это позволяет циклу продолжаться дальше, и в конечном итоге программа пытается получить доступ к ограниченному местоположению.

Поэтому, чтобы бороться с этим, инициализируйте node* Next = NULL в определении вашей node структуры. Нравится:

 struct node{
    char data;
    struct node* next = NULL;
};
 

Теперь значение по умолчанию для next устанавливается NULL явно. Следовательно, если вы не измените его, чтобы указать на другой узел, он все равно останется NULL . И проблема должна быть решена.