c - 需要对名称链接列表进行合并排序

Question

我需要有关合并排序函数的帮助，该函数是名称的链接列表。运行程序时出现段错误，我感觉有些不对劲。感谢您提前提供的帮助。

程序应该打印排序前的姓名列表，然后打印排序后的姓名列表。

#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;
    }
}

我读入的文件是一个名称列表。它是:

德里克

德鲁

兰德尔

特雷尔

卡门

科林

艾迪

巴勃罗

拉蒙特

德克斯特

Answer 1

在 read_from_file 中，您有:

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

但是，您只为指针分配了空间，而不是为数据结构分配了空间。因此，您将在上面第二行中注销分配空间的末尾。

相反，写:

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

[ 您可以在 Do I cast the result of malloc? 阅读有关强制转换 malloc 结果的缺点的信息。 ，但我只是为上面的进展做了最小的改变]

完成上述修复后，请尝试在调试器中遍历程序，或添加 printf 语句，以便您可以准确地看到程序的行为方式，并了解出现任何其他问题的位置。