Need to Merge Sort a Linked List of names

Question

I need help with my merge sort function that is a linke list of names. I get a seg fault when I run the program, and I feel like something isnt right. Thanks for the help in advance.

The program is supposed to print out the list of names before sorting, then the list of names after sorting.

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

#define MAX_STR_LEN 25

typedef struct Data_ {
    char *name;
    struct Data_ *next;
}Data;

void split_in_half(Data *source, Data **frontRef,Data **backRef);
Data* merge(Data *a, Data *b);
void merge_sort(Data **list);
Data* read_from_file(const char* file, const int size);
void display(Data *list);
void push(Data **head, char *name);

int main(int argc, char **argv){

    if(argc != 2){
            printf("Not enough parameters!");
            exit(0);
    }

    Data *head = NULL;

    int size = 10;
    head = read_from_file(argv[1], size);

    printf("\nBefore sort");

    display(head);

    printf("\nMerge Sort\n");

    merge_sort(&head);

    display(head);
}

void merge_sort(Data **list){

    Data *head = *list;
    Data *temp;
    Data *temp2;

    if((head == NULL) || (head->next == NULL))
    {
    return;
    }
    split_in_half(head, &temp, &temp2);

    head = merge(temp, temp2);


}

Data *merge(Data *a, Data *b){

    Data *result = NULL;

    if(a == NULL)
            return(b);
    else if(b==NULL)
            return (a);

    if(strcmp(a->name, b->name) > 0)
    {
            result = a;
            result->next = merge(a->next, b);
    }
    else
    {
            result = b;
            result->next = merge(a, b->next);
    }
    return (result);

}

void split_in_half(Data *source, Data **frontRef,Data **backRef){

    Data *fast;
    Data *slow;

    if(source == NULL || source->next == NULL)
    {
            *frontRef = source;
            *backRef = NULL;
    }
    else
    {
            slow = source;
            fast = source->next;

            while(fast != NULL)
            {
                   fast = fast->next;
                    if(fast != NULL)
                    {
                            slow = slow->next;
                            fast = fast->next;
                    }
            }
    }
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}



void push(Data **head, char *name){

    Data *temp = malloc(sizeof(Data));
    temp->name = strdup(name);
    temp->next = *head;
    *head = temp;

}

Data* read_from_file(const char* file, const int size){

    FILE *input;
    input = fopen(file, "r");
    Data *new_ = (Data*)malloc(sizeof(Data*));
    new_->next = NULL;

    int i;
    char name[MAX_STR_LEN];
    for(i = 0; i < size; i++){
    fscanf(input, "%24s", &name);
    push(&new_, name);
    }

return new_;
}

void display(Data *list){

    Data *current = list;
    while(current->next != NULL){
            printf("\n%s", current->name);
            current = current->next;
    }
}

The file that I read in is a list of names. It is:

Derek

Drew

Randell

Terrell

Carmen

Colin

Eddy

Pablo

Lamont

Dexter

I fixed the compile errors, yet I still get a seg fault when I run the program — user3699735, Jul 10 '14 at 03:03
i used gdb debugger and it says my segfault is on line 260. Here is the error Program received signal SIGSEGV, Segmentation fault. __strcmp_sse42 () at ../sysdeps/x86_64/multiarch/strcmp.S:260 260 movdqu (%rsi), %xmm2 — user3699735, Jul 10 '14 at 03:07
That means that at least one of the arguments you pass to `strcmp` points to invalid memory. — Jabberwocky, Jul 10 '14 at 13:32

score 0 · Answer 1 · edited May 23 '17 at 12:20

In read_from_file you have:

Data *new_ = (Data*)malloc(sizeof(Data*));
new_->next = NULL;

However, you have only allocated space for a pointer, rather than allocated space for a Data structure. So you will be writing off the end of the allocated space in the second line above.

Instead, write:

Data *new_ = (Data*)malloc(sizeof(Data));
new_->next = NULL;

[ You can read about the cons of casting the result of malloc at Do I cast the result of malloc?, but I am just making the minimal change for progress above ]

Once you've made the fix above, try walking through the program in a debugger, or adding printf statements, so you can see exactly how the program is behaving, and understand where any other problems occur.

Need to Merge Sort a Linked List of names

1 Answers1