我正在尝试基于最大排序算法为C中的链表编写通用排序函数。

我目前正在测试字符串上的函数,而我的compareFunction是“ strcmp”,因此数据应按字典顺序降序排列。

该列表的初始数据为:Chupakabra,海滩,沙尘暴,狗,树皮。

然后,在我的排序函数中的while循环进行1次迭代后,我得到了沙尘暴,沙滩,沙尘暴,狗,树皮。

但是,根据printfs,“ findGreatest”在退出时返回正确的值,“交换”也是如此。

谁能帮我找到排序功能的问题?

ListResult listSort(List list, CompareListElements compareElement){
    if(!list || !compareElement){
        return LIST_NULL_ARGUMENT;
    }
    if (HEAD == NULL || HEAD->next == NULL){
        return LIST_SUCCESS;
    }
    ListNode head = HEAD;
    ListNode greatest;
    while (head){
        greatest = findGreatest (head, list, compareElement);
        if (greatest == NULL){
            return LIST_OUT_OF_MEMORY;
        }
        printf("Head data before swap: %s\n", (char*)head->data);
        printf("Greatest data before swap: %s\n", (char*)greatest->data);
        swap(&(head->data), &(greatest->data));
        printf("New head data: %s\n", (char*)head->data);
        printf("New greatest data: %s\n", (char*)greatest->data);
        head = head->next;
    }
    return LIST_SUCCESS;
}


结构,交换和辅助函数定义:

#define ITER list->iter
#define NEXT list->next
#define HEAD list->head

typedef struct ListNode {
    ListElement data;
    struct ListNode* next;
} *ListNode;

struct List_t {
    ListNode head;
    CopyListElement copyElement;
    FreeListElement freeElement;
    ListNode iter;
};

void swap (ListElement* element1, ListElement* element2){
    ListElement* temp = *element1;
    *element1 = *element2;
    *element2 = temp;
}

ListNode findGreatest (ListNode head, List list, CompareListElements compareElement){
    ListNode greatest = malloc(sizeof(*greatest));
    ListNode current = malloc(sizeof(*current));
    if (greatest == NULL || current == NULL){
        return NULL;
    }
    greatest->data = head->data;
    greatest->next = head->next;
    current->data = head->data;
    current->next = head->next;
    while (current){
        if (compareElement(greatest->data, current->data) > 0){
            greatest->data = current->data;
            greatest->next = current->next;
        }
        current = current->next;
    }
    free(current);
    return greatest;
}


我已经测试过main的swap函数,并且看起来工作正常。

最佳答案

清单:Chupakabra, Beach, Sandstorm, Dog, Bark
第一次greatest元素是Sandstorm
head元素交换为Sandstorm元素,但您的findGreatest返回克隆。
所以
&(Sandstorm-> data)!=&greatest-> data因为greatest是新分配的。
(因此您得到Sandstorm, Beach, Sandstorm, Dog, Bark

所以试试这个

void swap (ListElement* element1, ListElement* element2){
    ListElement temp = *element1;//element1 dereference type is ListElement
    *element1 = *element2;
    *element2 = temp;
}

ListNode findGreatest (ListNode head, CompareListElements compareElement){// "List list," unused list
    ListNode greatest = head;
    ListNode current;

    if (greatest == NULL || greatest->next == NULL){
        return greatest;
    }
    current = head->next;
    while (current){
        if (compareElement(greatest->data, current->data) > 0){
            greatest = current;
        }
        current = current->next;
    }
    return greatest;
}

关于c - C中的链表的一般排序,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/36766014/

10-11 21:18