在C中对链表进行排序

Question

我试图通过找到最大值,从其位置删除它,然后将其插入列表顶部来对链表进行排序.

我遇到的困难是实际删除和插入顶部.问题似乎是在sortList函数中包含的while循环中的if条件,但我不确定如何修复它.

任何帮助,将不胜感激.

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int num;
    struct node *next;
} Node, *NodePtr;

void printList(NodePtr np);
NodePtr makeList(void);
NodePtr makeNode(int n);
NodePtr sortList(NodePtr list);

int main(void) {
    NodePtr list;
    printf("Enter numbers for the list (0 to end)\n");
    list = makeList();
    printList(list);
    list = sortList(list);
    printList(list);
    return 0;
}

NodePtr makeList(void) {
    NodePtr makeNode(int), np, top, last;
    int n;
    top = NULL;
    if(scanf("%d", &n) != 1)n = 0;
    while(n != 0) {
        np = makeNode(n);
        if(top == NULL)top = np;
        else last->next = np;
        last = np;
        if(scanf("%d", &n)!=1)n=0;
    }
    return top;
}


void printList(NodePtr np) {
    while(np != NULL) {
        printf("%d\n", np->num);
        np = np->next;
    }
}

NodePtr makeNode(int n) {
    NodePtr np = (NodePtr)malloc(sizeof(Node));
    np->num = n;
    np->next = NULL;
    return np;
}

NodePtr sortList(NodePtr list) {
    NodePtr top = list;
    NodePtr curr = NULL;
    NodePtr largest;
    NodePtr prev;
    prev = NULL;
    curr = top;
    largest = top;

    while(curr != NULL) {
        prev = curr;
        if(curr->num > largest->num) {
            largest = curr;
            prev->next = curr->next;
            largest->next = top;
        }
        curr = curr->next;
    }
    if(prev == NULL) {
        largest->next = top;
        return largest;
    }
    return largest;
}

Answer 1

通过写信给largest->next你覆盖curr->next。所以你最终总是从头开始。

确保：

1. 列表保持一致
2. 你的列表迭代器保持一致

但总的来说，您的代码似乎严重损坏，我相信您的排序逻辑中可能还存在其他一些错误。