c - C:Quicksort链表

Closed. This question needs details or clarity。它当前不接受答案。
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            想改善这个问题吗？添加详细信息并通过editing this post阐明问题。
                        
                        4年前关闭。
                                                                                            
                
        
我应该写一个程序，从文件中读取密码和数字，例如jskskfj 128938，将它们放在链接列表中，并使用quicksort对它们进行排序。该文件包含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);
    }
}

最佳答案

好的，这是一项任务，因此您必须在列表上实现快速排序。
查看您的代码，有些问题阻止了正确的行为：


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


我使用第一个元素作为枢轴实现了一个简单的分区。我使用2个实用程序功能：


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


我将concatenate合并到qsort_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链表，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35103855/