c - 如何以正确的方式对链表进行排序 C

Question

我尝试按字段年份对链接列表进行排序，但我的代码不正确。我有这样的列表和函数来对链接列表进行排序:

struct sputnik {
char nazvanie[30];
char nazvanie_main[30];
int year;
float d;
int period;
struct sputnik *next;
};

int f_sort (struct sputnik **head,int*count) {
struct sputnik *prev,*current,*buffer, *buf;
int i;
current=*head;

for (i=0;i<*count;i++) {
while (current!=NULL){
prev=current;
buf=current->next;
if (prev->year>buf->year){
buffer=buf->next;
buf->next=prev->next;
prev->next=buffer;
current=prev->next;

}
else{
current=buf->next;
}
}
}
return 0;
}

我的代码中的计数是列表中元素的数量。

Answer 1

您需要根据需要更新列表的头部，并在 for(i = 0 ...) 循环之后将 current 重置回列表的头部。如果您使用指向当前而不是“上一个”的指针，这会更容易。例如:

struct sputnik **ppcurrent;
    /* ... */
    for(i=0 ...
        ppcurrent = head;
        while(NULL != *ppcurrent && NULL != (*ppcurrent)->next){
            /* ... if swap */
                *ppcurrent = ... ;  /* update head or a next pointer */
            /* ... */
            ppcurrent = &((*ppcurrent)->next); /* advance ppcurrent */

有更好的方法对列表进行排序，但首先看看您是否可以让当前版本正常工作。

<小时/>

对于阅读本文的其他人，更好的方法:

链表自底向上归并排序:

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

C 代码示例:

Merge Sort a Linked List

在大多数情况下，由于分散节点的顺序访问涉及内存的随机访问，这对缓存不友好，因此将列表复制到数组，对数组进行排序，然后从数组创建排序列表通常会更快。这就是 Java 在 collections.sort() 中对 native 链表所做的事情。