Ошибка сегментации в реализации Mergesort - PullRequest
Новая
       10

Ошибка сегментации в реализации Mergesort

4 голосов
/ 10 февраля 2020

У меня есть программа Mergesort, которая работает с неупорядоченным связанным списком. Проблема, которую я получаю, - это ошибка сегментации (ядро сброшено).

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

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

typedef struct node_t node;
typedef struct node_t { int key; node *next; } node;
static node *head, *z;
node *merge(node *a, node *b)
{
    z->next =z;
    node *c = z;
    do
    {
        if (a->key > b->key)
        {
            c->next = a; c = a; a = a->next;
        }
        else
        {
            c->next = b; c = b; b = b->next;
        }
    } while (c != z);
    c = z->next;
    z->next = NULL;
    return c;
}
node *mergesort(node *c) {
    node *a = NULL; 
    node *b = NULL;
    if (c != NULL && c->next->next != NULL) {
        a = c; b = c;
        while (b->next != NULL && b->next->next != NULL) {
            c = c->next;
            b = b->next->next;
        }
        b = c->next;
        c->next = NULL;
        return merge(mergesort(a), mergesort(b));
    }
    return c;
}
void printList(node* node) 
{ 
    while (node != NULL) { 
        printf("%d ", node->key); 
        node = node->next; 
    } 
} 
node *listcreate(int n, node *a)
{
    node *head = NULL;
    node *temp = NULL;
    node *p = NULL;
    int i=0;
    while(i<n)
    {
        temp = (node*) malloc(sizeof(node*));
        printf("Please insert the number: ");
        scanf("%d", &(temp->key));
        temp->next = NULL;
        if(head == NULL)
        head = temp;
        else
        {
            p = head;
            while(p->next != NULL)
            p = p->next;
            p->next = temp;
        }
        i++;
    }
    a = head;
}
int main() 
{ 
    node *a = NULL;
    listcreate(3, a);
    a = mergesort(a);
    printf("Sorted Linked List is: \n"); 
    printList(a); 

    getchar(); 
    return 0; 
}

Ответы [ 2 ]

0 голосов
/ 10 февраля 2020

Прежде всего вызов вашей функции mergesort при включении stdlib.h некорректен и должен вызывать ошибку с недавними компиляторами C.

Затем эта последовательность кода вызывает неопределенное поведение путем разыменования нулевого значения. указатель: 

node *z = NULL;
node *c = z;
c->next = a;  //  UB!

В этот момент c равен NULL, поэтому вы не должны использовать c->next. При обычной реализации C попытка записи в запрещенную память вызывает ошибку сегмента.

Ваш алгоритм пытается использовать sentinel , но ИМХО это нецелесообразное использование дело. Проще просто запомнить первое значение. И вы должны также обработать случай, когда вы достигнете конца одного из обоих отсортированных списков. Код может стать: 

node *merge(node *a, node *b)
{
    node *c = z;           // current node initialized to null
    node *top;             // declare the future return value
    do
    {
        if (a->key > b->key)
        {
            if (c == z) top = a;    // if first value, remember it
            else c->next = a;       // else add the node to current list
            c = a; a = a->next;
            if (a == NULL) {        // explicitely handle end of input list
                c->next = b;
                break;
            }
        }
        else
        {
            if (c == z) top = b;
            else c->next = b; 
            c = b; b = b->next;
            if (b == NULL) {
                c->next = a;
            break;
            }
        }
    } while (c != z);
    return top;
}

Но это еще не все. Ваш код представляет собой смесь C и C ++. Вы используете только библиотечные функции C, но компилируете код с помощью компилятора C ++. Язык C не допускает перегрузок функций, поэтому не следует повторно использовать имя функции стандартной библиотеки с другим набором параметров (mergesort). И на C языке вам не нужно приводить mallo c.

Даже с моим исправлением ваш код будет работать на любом приличном компиляторе C если вы не измените имя функции mergesort. Вы были предупреждены.

0 голосов
/ 10 февраля 2020

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

Доступ к массиву вне границ

Разыменование NULL-указателей

Разыменование освобожденной памяти

Разыменование неинициализированных указателей

Неправильное использование операторов "&" (адрес) и "*" (разыменование)

Неправильное форматирование спецификаторов в операторах printf и scanf

Переполнение стека

Запись в постоянную память

...