C：快速排序链表

Question

我应该编写一个程序，从文件中读取密码和数字，例如jskskfj 128938，将它们放在链表中，并使用快速排序对它们进行排序。该文件包含 100 个条目。我已经设法将其读入链表，效果很好。但是，我在使用快速排序和分区函数时遇到了麻烦，因为大多数在线教程使用交换而不是移动，但是我应该将小于主元的数字移动到一个新列表中，与更大的数字相同并将它们连接起来到底。到目前为止，这是我的努力：

主要：

#include "blatt10.h"

int main(int argc, char **args) {
    if (argc != 2) {
        printf("Nutzung: %s <Dateiname>\n", args[0]);
        return 1;
    }
    list mylist;
    init_list(&mylist);
    read_data(args[1], &mylist);
    qsort_list(&mylist);
    printf("Sortierte Liste:\n");
    print_list(&mylist);
    free_list(&mylist);
    return 0;
}

帮助文件：

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

typedef struct passwort passwort;

struct passwort {
    char name[100];
    int anzahl;
};

typedef struct list_element list_element;

struct list_element {
    passwort data;
    list_element *next;
};

typedef struct list list;

struct list {
    list_element *first;
    list_element *last;
};

void init_list(list *mylist);
void insert_front(list_element *le, list *mylist);
void free_list(list *mylist);
void read_data(char *filename, list *mylist);
list_element *partition(list *input, list *left, list *right);
void qsort_list(list *mylist);
void print_list(list *mylist);

我的代码（我只复制了必要的功能，没有全部复制）：

void init_list(list *mylist) {    
    mylist->first = NULL;
    mylist->last = NULL;

}

void insert_front(list_element *le, list *mylist) {
    if (mylist->first == NULL) {
        mylist->first = le;
        mylist->last = le;
    } else {
        le->next = mylist->first;
        mylist->first = le; 
    }
}

list_element *partition(list *input, list *left, list *right) {
    list_element *pivot = malloc(sizeof(list_element));
    pivot->next = NULL;

    if (input->first != NULL) {
        input->first = pivot;
    } else {
        printf("Liste leer!\n");
    }

    if (input->first == input->last) {
        return (input->first);
    }

    list_element *tmp = input->first;
    while (tmp != NULL) {
        if (tmp->data.anzahl >= pivot->data.anzahl) {
            insert_front(tmp, right);
            printf("%s\n", tmp->data.name);
        } else {
            insert_front(tmp, left);
        }
        tmp = tmp->next;
    }
    return (pivot);
}

void qsort_list(list *mylist) {
    int length = 100;
    if (length > 1) {
        list *A;
        init_list(A);
        list *B;
        init_list(B);
        list_element *pivot;
        pivot = partition(mylist, A, B);
        qsort_list(A);
        qsort_list(B);
        mylist = concatenate(A, pivot, B);
    }
}

Answer 1

好的，这是一个作业，所以你必须对列表进行快速排序。查看您的代码，存在一些妨碍正常行为的问题：

在 partition 函数中，您为 pivot 分配了一个虚拟 list_element 没有明显的目的并且永远不会释放它，除非它是副作用concatenate 你没有 post.
在 partition 函数中，您使用 tmp = tmp->next; 迭代到下一项，但是 tmp 被插入到其中一个子列表的前面，所以它的下一个元素不是你所期望的。
在qsortlist中，你用未初始化的列表指针调用init_list。
concatenate的语义不明显，应该分配list它returns？你什么时候释放它？

我实现了一个简单的分区，使用第一个元素作为主元。我使用 2 个实用函数：

list_take_first(list) 删除列表的第一个元素并 return 它，
list_append(list, element) 将 list_element 及其所有链推到列表的末尾。

我将 concatenate 合并到 qsort_list 函数中。

代码很简单，不分配内存，但是针对list已经排序的病态情况进行深度递归。通过选择列表中间的枢轴，或者随机选择，或者通过检查排序的子列表，很容易改进它。您也可以尝试避免在较大的子列表上递归，就像您对数组 qsort 所做的那样，但这有点棘手。您还可以将比较函数传递给 qsortlist 和 partition 以实现不同的排序顺序。

list_element *list_take_first(list *mylist) {
    list_element *le = mylist->first;
    if (le != NULL) {
        mylist->first = le->next;
        le->next = NULL;
        if (mylist->first == NULL) {
            mylist->last = NULL;
        }
    }
    return le;
}

void list_append(list *mylist, list_element *le) {
    if (le) {
        if (mylist->first == NULL) {
            mylist->first = le;
        } else {
            mylist->last->next = le;
        }
        while (le->next) {
            le = le->next;
        }
        mylist->last = le;
    }
}

list_element *partition(list *input, list *left, list *right) {
    /* simplistic partitioning: use first element as pivot */
    list_element *pivot = list_take_first(input);

    if (pivot != NULL) {
        list_element *tmp;
        while ((tmp = list_take_first(input)) != NULL) {
            if (tmp->data.anzahl >= pivot->data.anzahl) {
                list_append(right, tmp);
            } else {
                list_append(left, tmp);
            }
        }
    }
    return pivot;
}

void qsort_list(list *mylist) {
    if (mylist->first != mylist->last) {
        list left, right;
        init_list(&left);
        init_list(&right);
        list_element *pivot = partition(mylist, &left, &right);
        qsort_list(&left);
        qsort_list(&right);
        list_append(mylist, left.first);
        list_append(mylist, pivot);
        list_append(mylist, right.first);
    }
}

C：快速排序链表

C: Quicksort linked list

c

quicksort