Блог

Я пишу программу на языке Си для обращения вспять кругового односвязного списка. По какой-то причине я продолжаю получать ошибку сегментации. Я уверен, что проблема связана с reverse функцией, поскольку я попытался прокомментировать вызов функции, программа работает нормально.

Для моей reverse() функции я использовал 3 указателя: prev , next и curr . Логика заключается в том, что я буду запускать цикл до curr тех пор, пока не получу адрес head , который будет сохранен в link части последнего узла, поскольку это циклический связанный список. Я буду продолжать обновлять curr->link , используя prev указатель, который изменит свою ссылку со следующего на предыдущий узел.

Когда цикл прерывается, head->link = prev; и head = prev; обновит соответствующие адреса таким образом, чтобы они указывали на первый узел перевернутого списка.

 //reversing CLL

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

struct node {
    int data;
    struct node *link;
} *head;

void reverse() {
    struct node *prev = NULL, *curr = head, *next;
        
    while (curr != head) {
        next = curr->link;
        curr->link = prev;
        prev = curr;
        curr = next;
    }
        
    head->link = prev;
    head = prev; 
}

void createList(int n) {
    int i, data;    
    
    head = (struct node *)malloc(sizeof(struct node));
        
    struct node *ptr = head, *temp;
            
    printf("Enter data of node 1t");
    scanf("%d", amp;data);
            
    head->data = data;
    head->link = NULL;
            
    for (i = 2; i <= n; i  ) {
        temp = (struct node *)malloc(sizeof(struct node));
                        
        printf("Enter data of node %dt", i);
        scanf("%d", amp;data);
                        
        temp->data = data;
        temp->link = NULL;
                        
        ptr->link = temp;
        ptr = ptr->link;
    }
    ptr->link = head;
}

void disp() {
    struct node *ptr = head;
        
    do {
        printf("%dt", ptr->data);   //gdb debugger shows problem is in this line
        ptr = ptr->link;
    } while (ptr != head);
}

int main() {
    int n;
        
    printf("Enter no of nodes to be createdt");
    scanf("%d", amp;n);
        
    createList(n);
            
    printf("nnList is displayed below!n");
        
    disp();
            
    printf("nnReversing list ...n");
            
    reverse();   // on commenting this call, disp() function 
                 // works accurately showing node data non-reversed
                  
    disp();
            
    printf("nnList successfully reversed!n");
}
 

Цикл в reverse() функции завершается немедленно, потому curr что инициализируется значением head so, поэтому тест while (curr != head) false на первой итерации.

reverse() затем устанавливается head->link в NULL и, наконец head , также устанавливается в NULL (начальное значение prev ), что объясняет ошибку сегментации в последующей disp() функции, где вы используете a do { } while (pre != head) , которая не может обрабатывать пустой список.

Вот модифицированная версия:

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

struct node {
    int data;
    struct node *link;
};

struct node *reverse(struct node *head) {
    struct node *prev = NULL, *curr = head;

    if (head) {
        do {
            struct node *next = curr->link;
            curr->link = prev;
            prev = curr;
            curr = next;
        } while (curr != head);
        curr->link = prev;
        head = prev;
    }
    return head;
}

struct node *createList(int n) {
    struct node *head = NULL, *tail = NULL, *temp;
    int i;

    for (i = 1; i <= n; i  ) {
        temp = (struct node *)malloc(sizeof(struct node));
        temp->data = 0;
        temp->link = NULL;

        printf("Enter data of node %dt", i);
        scanf("%d", amp;temp->data);

        if (head == NULL) {
            head = temp;
        } else {
            tail->link = temp;
        }
        tail = temp;
        temp->link = head;
    }
    return head;
}

void disp(struct node *head) {
    if (head) {
        struct node *ptr = head;
        do {
            printf("%dt", ptr->data);
            ptr = ptr->link;
        } while (ptr != head);
    }
}

int main() {
    struct node *head;
    int n = 0;

    printf("Enter no of nodes to be createdt");
    scanf("%d", amp;n);

    head = createList(n);

    printf("nnList is displayed below!n");
    disp(head);

    printf("nnReversing list ...n");

    head = reverse(head);

    disp(head);

    printf("nnList successfully reversed!n");

    // should free the list
    return 0;
}
 

Для начала это плохая идея использовать глобальную переменную head

 struct node {
    int data;
    struct node *link;
} *head;
 

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

Из-за этой инициализации

 struct node *prev = NULL, *curr = head, *next;
                          ^^^^^^^^^^^^
 

условие цикла while

 while (curr != head) {
 

никогда не вычисляется как true, потому что изначально указатель curr равен указателю head .

Более того, если список пуст, то это утверждение

 head->link = prev;
 

вызывает неопределенное поведение.

Вот демонстрационная программа, которая показывает, как список может быть объявлен в main, а затем отменен.

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

struct node 
{
    int data;
    struct node *link;
};

size_t assign( struct node **head, const int a[], size_t n )
{
    while ( *head )
    {
        struct node *tmp = *head;
        *head = ( *head )->link;
        free( tmp );
    }
    
    size_t total = 0;
    
    struct node *first = NULL;
    
    while ( total < n amp;amp; ( *head = malloc( sizeof( struct node ) ) ) != NULL )
    {
        ( *head )->data  = a[total];
        ( *head )->link  = NULL;
          total;
        
        if ( first == NULL ) first = *head;
        
        head = amp;( *head )->link;
    }
    
    if ( first != NULL ) *head = first;
    
    return total;
}

void display( const struct node *head )
{
    if ( head != NULL )
    {
        const struct node *current = head;
        do
        {
            printf( "%d -> ", current->data );
        } while ( ( current = current->link ) != head );
    }       
    
    puts( "null" );
}

struct node * reverse( struct node **head )
{
    if ( *head )
    {
        struct node *last = *head;
        struct node *prev = NULL;

        while ( ( *head )->link != last )
        {
            struct node *current = *head;
            *head = ( *head )->link;
            current->link = prev;
            prev = current;
        }
        
        ( *head )->link = prev;
        last->link = *head;
    }
    
    return *head;
}

int main(void) 
{
    struct node *head = NULL;
    
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    
    assign( amp;head, a, sizeof( a ) / sizeof( *a ) );
    
    display( head );
    
    display( reverse( amp;head ) );
    
    display( reverse( amp;head ) );
    
    return 0;
}
 

Вывод программы

 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null