C语言排序链表

Question

我这里有一个问题，我想用 3 个数据输入对我的链表进行排序，但是当我执行这个时，只有 1 个数据被排序。我尝试将要替换的临时节点映射到新节点，但映射仅适用于 num_id 数据。在哪里

例如：

数据需要排序

21507 - John - Mathematics
21477 - Andrew - Biology
21905 - James - Physics
21322 - Sophia - Chemistry

预期结果

21322 - Sophia - Chemistry
21477 - Andrew - Biology
21507 - John - Mathematics
21905 - James - Physics

我得到了什么

21322 - John - Mathematics
21477 - Andrew - Biology
21507 - James - Physics
21905 - Sophia - Chemistry

这是我的脚本：

节点

struct nodes{
    int num_id;
    char name[30], lesson[30];
    struct nodes *link;
}*head, *current, *temp, *tail;

排序链表

void linked_list_sorted() {
    struct nodes *node, *temp_sorted;
    int temp_sortedvar_num_id, count_data=0;
    char temp_sortedvar_name[30], temp_sortedvar_lesson[50];
    node = head;
    while(node != NULL)
    {
        temp_sorted=node; 
        while (temp_sorted->link !=NULL)
        {
            if(temp_sorted->num_id > temp_sorted->link->num_id)
                {
                temp_sortedvar_num_id = temp_sorted->num_id;
                temp_sorted->num_id = temp_sorted->link->num_id;
                temp_sorted->link->num_id = temp_sortedvar_num_id;
                }
            else if(temp_sorted->name > temp_sorted->link->name)
                {
                strcpy(temp_sortedvar_name, temp_sorted->name);
                strcpy(temp_sorted->name, temp_sorted->link->name);
                strcpy(temp_sorted->link->name, temp_sortedvar_name);
                }
            else if(temp_sorted->lesson > temp_sorted->link->lesson)
                {
                strcpy(temp_sortedvar_lesson, temp_sorted->lesson);
                strcpy(temp_sorted->lesson, temp_sorted->link->lesson);
                strcpy(temp_sorted->link->lesson, temp_sortedvar_lesson);
                }
            temp_sorted = temp_sorted->link;
        }
        node = node->link;
    }
    temp_sorted = head;
    while(temp_sorted != NULL) {
        count_data++;
        printf("%d. %d - %s - %s\n", count_data, temp_sorted->num_id, temp_sorted->name, temp_sorted->lesson);
        temp_sorted = temp_sorted->link;
    }
}

最后，这是我的脚本，用于将数据推送到链表：

void push_data (int nim, char name[], char lesson[]) {
    // Push Step (Head, Mid, Tail)
    current = (struct nodes*)malloc(sizeof(struct nodes));
    current->nim = nim;
    strcpy(current->name, name);
    strcpy(current->lesson, lesson);

    if (head == NULL){
        head = tail = current;
    } else if (current->nim < head->nim) {
        current->link = head;
        head = current;
    } else{
        tail->link = current;
        tail = current;
    }
}

Answer 1

对链表使用归并排序。查看 https://www.geeksforgeeks.org/merge-sort-for-linked-list/

Answer 2

当比较成功时，您只是更新比较成功的值。例如在下面的片段中

temp_sortedvar_num_id = temp_sorted->num_id;
temp_sorted->num_id = temp_sorted->link->num_id;
temp_sorted->link->num_id = temp_sortedvar_num_id;

您只是交换数字，因为数字比较失败，您需要交换节点内的所有值。

建议：不要交换 nodes 中的所有值，而是编写一个直接交换节点引用的方法。

Answer 3

对于足够大的输入，很难比标准库的 qsort 更快。（在许多 C 库中，它受到 Bentley, McIlroy, 1993, Engineering a Sort Function 的启发。）这么多，在一定的问题大小之后，用链表的内容分配一个全新的数组，复制整个链表可能会更快进入这个数组，qsort，并更正指针。

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

struct nodes{
    int num_id;
    char name[30], lesson[30];
    struct nodes *link;
};

static void fill(struct nodes *n) {
    size_t i, j;
    assert(n);
    n->num_id = rand();
    i = rand() / (RAND_MAX / ((sizeof n->name - 1) / 2) + 1)
        + ((sizeof n->name - 1) / 2);
    for(j = 0; j < i; j++)
        n->name[j] = rand() / (RAND_MAX / ('z' - 'a' + 1) + 1) + 'a';
    n->name[j] = '[=10=]';
    i = rand() / (RAND_MAX / ((sizeof n->lesson - 1) / 2) + 1)
        + ((sizeof n->lesson - 1) / 2);
    for(j = 0; j < i; j++)
        n->lesson[j] = rand() / (RAND_MAX / ('z' - 'a' + 1) + 1) + 'a';
    n->lesson[j] = '[=10=]';
}

static int compare(const struct nodes *a, const struct nodes *b) {
    return (a->num_id > b->num_id) - (a->num_id < b->num_id);
}

static int compar(const void *a, const void *b) { return compare(a, b); }

int main(void) {
    size_t n;
    struct nodes ns[100000], *node, *head;
    const size_t ns_size = sizeof ns / sizeof *ns;
    srand((unsigned)clock());
    for(n = 0; n < ns_size; n++) fill(ns + n);
    qsort(ns, ns_size, sizeof *ns, &compar);
    for(n = 0; n < ns_size - 1; n++) ns[n].link = ns + n + 1;
    ns[n].link = 0;
    head = ns;
    for(node = head; node; node = node->link)
        printf("No. %d; name: %s; lesson: %s.\n", node->num_id,
        node->name, node->lesson);
    return EXIT_SUCCESS;
}

对于小问题，它可能会更慢，因为它改变了数据结构的性质并且设置时间很长。但是，它也非常地道。您还可以分配一个指针数组，qsort 它，并在重新索引时使用指针作为标记。

Answer 4

您的 sorted 函数中的一个问题是它 独立地 交换节点的不同成员。将 num_id 成员与下一个成员交换的条件不同于对 name 执行相同操作的条件。然而，这些应该始终在一起！所以要么你不应该交换任何东西，要么你应该交换所有成员。

由于您的代码负责将新数据推送到列表中，为什么不确保将新节点放置在列表中的排序位置？那你就不需要sorted了。事实上，您的 push_data 已经具有将节点 放在列表前面 的逻辑，当它的 num_id 恰好小于当前头节点的节点时.如果您对其他节点执行相同的操作，您将始终对列表进行排序：

void push_data (int num_id, char name[], char lesson[]) {
    // Use a local variable for referencing the new node:
    struct nodes *nodeNode = (struct nodes*)malloc(sizeof(struct nodes));
    nodeNode->num_id = num_id;
    strcpy(nodeNode->name, name);
    strcpy(nodeNode->lesson, lesson);

    if (head == NULL){
        head = tail = nodeNode;
    } else if (num_id <= head->num_id) {
        nodeNode->link = head;
        head = newNode;
    } else if (num_id >= tail->num_id) { // Add this condition
        tail->link = newNode;
        tail = newNode;
    } else { // Add this case:
        // Look for the insertion point, assuming list is sorted.
        // Use a local variable for current; not a member
        struct nodes *current = head;
        while (num_id > current->link->num_id) {
            current = current->link;
        }
        newNode->link = current->link;
        current->link = newNode;
    }
}

现在您的列表将始终排序。

C语言排序链表

Sorted Linked List on C Language

c

sorting

linked-list

sortedlist