C語言上的排序關聯串列 -有解無憂

我有一個問題，我想用3個資料輸入對我的關聯串列進行排序，但是當我執行這個操作時，只有一個資料被排序了。我試著把將被替換的臨時資料映射到一個新的節點，但是映射只對num_id資料有效。哪里是

？

例如：

資料需要排序。
資料需要被排序

21507 - John - Mathematics
21477 - Andrew - 生物學
21905 - James - 物理學
21322 - Sophia - 化學

預期結果

21322 - Sophia - Chemistry
21477 - Andrew - 生物學
21507 - John - 數學
21905 - James - 物理學

我得到了什么

21322 - John - Mathematics
21477 - Andrew - 生物學
21507 - James - 物理學
21905 - Sophia - 化學

這是我的腳本：

節點

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; /span>
    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->classes)。
                strcpy(temp_sorted->classes, temp_sorted->link->classes)。
                strcpy(temp_sorted->link->classement, 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
", count_data, temp_sorted->num_id, temp_sorted->name, temp_sorted-> lesson)。
        temp_sorted = temp_sorted->鏈接。
    }

最后，這是我的腳本，用于將資料推送到鏈接串列：

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->classes, lesson);

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

uj5u.com熱心網友回復：

你的sorted函式中的一個問題是，它將節點的不同成員相互獨立地交換。您將num_id成員與下一個成員交換的條件與對name做同樣處理的條件不同。然而，這兩者應該總是在一起的！所以，要么你不應該交換任何東西。因此，要么你不應該交換任何東西，要么你應該交換所有成員。

由于您的代碼負責將新資料推入串列，為什么不確保新節點被放置在串列中的排序位置？那么你就不需要sorted。事實上，你的push_data已經有這樣的邏輯，當一個節點的num_id恰好小于當前頭部節點的時候，它就會被放在串列的前面。如果你對其他節點做同樣的處理，你的串列就會一直被排序：

void push_data （int num_id。char name[], char lesson[]） { //使用區域變數來參考新節點： struct nodes *nodeNode = (struct) keyword">struct nodes*)malloc(sizeof(struct nodes))。 nodeNode->num_id = num_id。 strcpy(nodeNode->name, name) 。 strcpy(nodeNode->classes, 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 { //加入這個條件： ///尋找插入點，假設串列被排序。 //為current使用一個區域變數；而不是一個成員。 struct nodes *current = head; while (num_id > current->link-> num_id) { current = current->link。 } newNode->link = current->link。 current->link = newNode。 } }

現在你的串列將總是被排序的。

uj5u.com熱心網友回復：

當比較成功時，你只更新比較成功的值。例如在下面的片段中

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內的所有值，而是寫一個方法來直接交換節點的參考。

uj5u.com熱心網友回復：

對于足夠大的輸入，很難做到比標準庫的qsort更快。(在許多C庫中，它的靈感來自Bentley, McIlroy, 1993, Engineering a Sort Function。) 因此，在問題達到一定規模后，用你的鏈接串列的內容分配一個全新的陣列，將整個鏈接串列復制到這個陣列中，qsort，并糾正指標，可能會更快。

#include <stdlib.h>/span>
#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] = ''/span>;
    i = rand() / (RAND_MAX / ((sizeof n->教訓 - 1) / 2)   1)
          ((sizeof n->教訓 - 1) / 2）。)
    for(j = 0; j < i; j  )
        n->教訓[j] = rand() / (RAND_MAX / ('z'/span> - 'a'/span>   1)   1)   'a';
    n->教訓[j] = ''。
}

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.
", node->num_id,
        node->name, node->classic）。)
    return EXIT_SUCCESS。
}

對于小規模的問題，它可能比較慢，因為它改變了你的資料結構的性質，并且有一個非微不足道的設定時間。然而，這也是非常習慣性的。你也可以分配一個指標陣列，qsort它，并在重新索引時使用指標作為標記。

uj5u.com熱心網友回復：

對鏈接串列使用合并排序。查看https://www.geeksforgeeks.org/merge-sort-for-linked-list/

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/310843.html

標籤：

上一篇：使用具有變化值的自定義順序對一個向量進行通用排序

下一篇：如何挑選比較兩個不同的excel列的唯一值？