通过 C 中的一次遍历交换节点，对由 1、2 和 0 组成的单向链表进行排序

Question

我试图通过仅遍历列表一次来解决我需要对值由 1、2 和 0 组成的给定链表进行排序的问题，并且我需要交换节点而不是值。我的代码是：

    #define max 3

void sortList(node **headRef)
{
    if(*headRef==NULL){
        return;
    }
    node* head[max];
    node*tail[max];
    node* curr=*headRef;
    int i;
    for(i=0; i<max; i++){
        head[i]=tail[i]=NULL;
    }
    while(curr!=NULL){
        i=curr->data;
        if(head[i]==NULL){
            head[i]=tail[i]=curr;
        }
        else{
            tail[i]=tail[i]->next=curr;
        }
        curr=curr->next;
    }
    for(int i=0, curr=(*headRef)=NULL; i<max; i++){
        if(head[i]!=NULL){
            if(*headRef==NULL){
                *headRef=head[i];
            }
            else{
                curr = curr->next =head[i];
            }
            curr=tail[i];
        }
        
    }
    curr->next=NULL;
}

但它一直给我一个错误，我不知道如何解决，如果有人能帮助我。

Answer 1

你的问题是这样的：

for(int i=0, curr=(*headRef)=NULL; i<max; i++)
             ^^^^^^^ here ^^^^^^^

然后你在使用它们之前通过better-understanding你正在使用的语言的特性来解决它。 for-loop 的可选声明 + 初始化部分允许您不仅初始化，而且声明变量（在本例中，shadow/hide 现有变量）。上面将声明 two loop-scope int 变量：i 和 curr，将第一个初始化为 0，然后(*headRef)=NULL 的表达式结果的第二个，对于 near-all C 实现，将等同于 (void*)0。但是现在curr是一个int，之前声明的curr作为节点指针被隐藏了。因此，这：

curr = curr->next =head[i];

现在是废话。

将您的代码更改为：

curr=(*headRef)=NULL;
for(int i=0; i<max; i++)

它应该可以工作。

Answer 2

你的代码是close，但是有点繁琐

每当我看到并行数组由相同 [类型] 索引索引时，我就会想到创建一个 struct。你有 head[] 和 tail[] 所以我会创建一个“桶”结构。

单行中的多个赋值 [尽管 doable/legal] 使代码难以（呃）阅读。注意：

x = y = z;

不比

快吗

x = z;
y = z;

if z 是一个简单的标量。编译器将生成相同的代码，但后者通常是 cleaner/clearer.

您的代码可能[或可能不]处理列表中缺少一个或多个0,1,2的所有情况] 值。即，以下形式的列表：

0,0,0
1,1,1
2,2,2

0,1
0,2

1,2

在这里使用 for 循环也有助于提高代码的可读性。

这是重构后的代码（我编译了它，但是没有测试它）：

#include <stdio.h>

#define max 3

typedef struct node node;
struct node {
    int value;
    node *next;
};

typedef struct {
    node *head;
    node *tail;
} list;

void
sortList(node **headRef)
{
    node *head = *headRef;
    node *tail;
    node *curr;
    node *next;

    if (head == NULL)
        return;

    list *buck;
    list buckets[max] = { 0 };

    // split into buckets
    for (curr = head;  curr != NULL;  curr = next) {
        next = curr->next;
        curr->next = NULL;

        buck = &buckets[curr->value];

        if (buck->head == NULL)
            buck->head = curr;
        else
            buck->tail->next = curr;

        buck->tail = curr;
    }

    // combine buckets into [new] single list
    head = NULL;
    tail = NULL;
    for (int i = 0;  i < max;  ++i) {
        buck = &buckets[i];

        // skip empty buckets
        if (buck->head == NULL)
            continue;

        // point to _first_ non-empty bucket
        if (head == NULL)
            head = buck->head;

        // append _next_ non-empty bucket
        else
            tail->next = buck->head;

        tail = buck->tail;
    }

    *headRef = head;
}

通过 C 中的一次遍历交换节点，对由 1、2 和 0 组成的单向链表进行排序

sort a singly linked list formed of 1, 2 and 0s by swapping the nodes through one traversal in C

c

sorting

linked-list

imperative-programming