C中的链表的一般排序

爱丽丝312

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

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

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

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

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

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

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测试了交换功能，并且看起来工作正常。

蓝精灵

list：Chupakabra, Beach, Sandstorm, Dog, Bark
第一次greatest元素是Sandstorm。
头元素交换为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;
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。