按多个参数对链表进行排序 [英] Sorting linked list by multiple parameters

问题描述

我正在尝试在单链表上使用插入排序，其中每个节点都有多个参数，例如:

I am trying to use insertion sort on a singly linked list, where each node has multiple parameters, say:

typedef struct _node {
    char param1[10];
    char param2[10];
    char param3[10];
    struct _node *next;
} node;

该算法将按param1对列表进行排序，并且在等效项的情况下，按param2和类似地根据param3决定顺序.我无法在线找到解决此问题的方法.对于单个参数，我可以使用以下排序算法实现:

The algorithm would sort the list by param1, and in case of equivalent items decide the order by param2, and similarly by param3. I was unable to find a solution to this problem online. For a single parameter, I've got the following implementation of the sorting algorithm to work:

void insertionSort(node **head) {

    //Initialize sorted list
    node *sorted = NULL;
    node *current = *head;

    //Insert every node into sorted list
    while (current != NULL) {
        // Store next for next iteration
        node *next = current->next;

        sortedInsert(&sorted, current);

        // Update current
        current = next;
    }

    //Replace old empty list with sorted list
    *head = sorted;
}

void sortedInsert(node **head, node *new) {
    node *current = *head;
    // Special case for the head
    if (current == NULL || strcmp(current->param1, new->param1) >= 0) {
        new->next = current;
        *head = new;
    }

    else {
        while (current->next!=NULL && strcmp(current->next->param1, new->param1) < 0){
            current = current->next;
        }

        new->next = current->next;
        current->next = new;
    }
}

我的猜测是我必须创建一个比较函数，而不是下面的位，也许是一个整数函数，返回对应于两种情况的0或1:

My guess would be that I have to create a comparison function instead of the following bits, maybe an integer function returning 0 or 1 corresponding to the two cases:

current->param1 >= new->param1
current->next->param1 < new->param1

但是，我无法提出这样的功能.有人能帮我解决这个问题吗?

However, I am unable to come up with such a function. Could anyone help me out with this?

推荐答案

一个排序例程，通过比较来确定前后发生的事情.如果比较是在函数中完成的，则元素的顺序由返回值确定(例如，小于零(通常为 -1 )，零，大于零(通常为 1 )).

A sort routine, makes decisions about what comes before or after by comparison. If the comparison is done in a function, then the order of the elements is determined by the return (e.g. less than zero (generally -1), zero, greater than zero (generally a return of 1)).

如果要对主要参数进行排序并遇到等价问题，请按辅助字符串进行比较，并将这些结果用于放置.在大多数情况下，比较功能将使用一个空指针指向要比较的每个节点.这样，您就可以访问sort函数中的主要和次要字符串.仅在您的排序函数中包含辅助比较，以防第一个比较的结果等于零，并根据该辅助比较的结果返回( -1，0，1 ).

If you are sorting on primary parameters and encounter an equivalence, then compare by your secondary string and use those results for the placement. In most cases, the comparison function will take a void pointer to each node being compared. Done this way, you will have access to both the primary and secondary strings within the sort function. Just include a secondary comparison in your sort function in case the result of the first comparison equals zero and return (-1, 0, 1) based on the results of that secondary comparison.

这篇关于按多个参数对链表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！