基于C语言的链表QuickSort问题求助（需移动节点而非交换值）

我需要用QuickSort算法对单链表元素排序，要求必须移动节点本身而非仅交换键值。目前编写的C语言代码无法正常运行，怀疑递归部分有问题，求解决方案。

排序依据是chave[0]，输入元素顺序为30, 50, 40, 10, 5, 20，期望排序后顺序为5, 10, 20, 30, 40, 50。

原代码 #

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

///ELEMENTO TEM DUAS CHAVES E SEU PRÓXIMO (ENCADEAMENTO SIMPLES)///

struct elemento {
    int chave[2];
    struct elemento *prox;
};

///MOSTRAR A LISTA GERADA///

void mostrar_chaves(struct elemento *lista){

    int i;
    struct elemento *aux;
    aux = lista;
    printf("\n\n\n");

    while(lista){
       printf("%d - ", lista->chave[0]);
       lista = lista->prox;
    }

    printf("\n\n\n");

    while(aux){
       printf("%d - ", aux->chave[1]);
       aux = aux->prox;
    }

}

///QUICK SORT///

struct elemento *particiona(struct elemento *ini, struct elemento *fim){

    struct elemento *pivo, *aux, *t1, *t2, *t3, *teste;
    t1 = ini;
    t2 = ini;
    teste = ini;

    int flag = 0;

    /*printf("\nini = %d\n", ini->chave[0]);
    printf("\nfim = %d\n", fim->chave[0]);*/

    for(pivo = aux = ini; aux && aux != fim; ) {

        if(aux->chave[0] < fim->chave[0]){

            if(ini != aux){
                pivo = aux;
                flag = 1;

                if(t1 == ini){
                    if(t1 != t2){
                        teste = aux;
                        ini = ini->prox;
                        t1->prox = aux->prox;
                        aux->prox = ini;
                        t2->prox = t1;

                        t1 = aux;
                        aux = t2->prox->prox;
                    }
                    else if(t1 == t2){

                        teste = aux;
                        aux = aux->prox;
                        t1 = t1->prox;
                        t1->prox = ini;
                        ini->prox = aux;
                    }
                }

                else{

                    t1->prox = aux; //10 liga no 5
                    aux = aux->prox; //aux 20
                    t1->prox->prox = ini->prox; //5 liga no 40
                    t2->prox = ini; //10 liga no 50
                    ini = ini->prox; //ini 40
                    t2->prox->prox = aux;
                }
            }

            else{
                ini = ini->prox;
            }
        }


        if(flag == 0)
            aux = aux->prox;
        if(t1 != ini && t1->prox != ini){
            t1 = t1->prox;
        }
        if(t2 != aux && t2->prox != aux)
            t2 = t2->prox;

        flag = 0;
    }

    t1->prox = fim; //50 liga no 20
    t3 = fim->prox; //NULL
    t1->prox->prox = ini->prox; //5 liga no 40
    t2->prox = ini; //10 liga no 50
    ini->prox = t3;

    fim = ini;
    ini = aux;

    printf("\npivo = %d\n", pivo->chave[0]);*/
    mostrar_chaves(teste);

    return pivo;
}

void quick_sort(struct elemento *ini, struct elemento *fim){

    struct elemento *pivo;
    printf("\nINI_Q - %d   FIM_Q - %d\n",ini->chave[0], fim->chave[0]);
    if (ini == fim) {
        printf("\nreturn estado anterior\n");
        return;
    }
    pivo = particiona(ini, fim);

    if (pivo && pivo->prox) {
        quick_sort(pivo->prox, fim);
    }

    if (pivo && ini != pivo) {
        quick_sort(ini, pivo);
    }
}

struct elemento *fim(struct elemento *ini){
    struct elemento *fim;

    for(fim = ini; fim && fim->prox; fim = fim->prox);

    return fim;
}

void main(){
setlocale(LC_ALL, "portuguese");

    struct elemento *lista_um, *lista_dois;

    lista_um = NULL;

    lista_um = (struct elemento *) malloc(sizeof(struct elemento)*6);

    lista_dois = lista_um;
    lista_dois->chave[0] = 30;
    lista_dois = lista_dois->prox;
    lista_dois->chave[0] = 50;
    lista_dois = lista_dois->prox;
    lista_dois->chave[0] = 40;
    lista_dois = lista_dois->prox;
    lista_dois->chave[0] = 10;
    lista_dois = lista_dois->prox;
    lista_dois->chave[0] = 5;
    lista_dois = lista_dois->prox;
    lista_dois->chave[0] = 20;
}

问题分析与修正方案 #

原代码存在三个核心问题：

1. 链表初始化错误：未正确设置节点的prox指针，最后一个节点的prox未置为NULL，导致链表结构混乱，引发非法内存访问。
2. Partition逻辑复杂易出错：原分区函数的指针操作过于繁琐，极易出现链表断裂、循环等问题。
3. 递归边界处理错误：原递归函数的参数传递和范围判断逻辑错误，导致递归无法正确覆盖所有子链表。

以下是修正后的完整代码：

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

///ELEMENTO TEM DUAS CHAVES E SEU PRÓXIMO (ENCADEAMENTO SIMPLES)///
struct elemento {
    int chave[2];
    struct elemento *prox;
};

///MOSTRAR A LISTA GERADA///
void mostrar_chaves(struct elemento *lista){
    printf("Chave[0]序列: ");
    while(lista){
       printf("%d - ", lista->chave[0]);
       lista = lista->prox;
    }
    printf("\n");
}

// 辅助函数：获取链表尾节点
struct elemento *get_tail(struct elemento *head) {
    while (head != NULL && head->prox != NULL) {
        head = head->prox;
    }
    return head;
}

// 单链表分区函数：返回pivot节点，同时输出左右子链表的头尾
struct elemento *particiona(struct elemento *head, struct elemento *tail, struct elemento **new_head, struct elemento **new_tail) {
    struct elemento *pivot = tail;
    struct elemento *prev = NULL, *curr = head, *tailer = pivot;

    // 遍历链表，将小于pivot的节点移到左链，大于等于的移到右链
    while (curr != pivot) {
        if (curr->chave[0] < pivot->chave[0]) {
            if (*new_head == NULL) {
                *new_head = curr;
            }
            prev = curr;
            curr = curr->prox;
        } else {
            if (prev != NULL) {
                prev->prox = curr->prox;
            }
            struct elemento *temp = curr->prox;
            curr->prox = NULL;
            tailer->prox = curr;
            tailer = curr;
            curr = temp;
        }
    }

    // 若左链为空，pivot即为新表头
    if (*new_head == NULL) {
        *new_head = pivot;
    }
    *new_tail = tailer;
    return pivot;
}

// 递归排序子链表
struct elemento *quick_sort_rec(struct elemento *head, struct elemento *tail) {
    if (head == NULL || head == tail) {
        return head;
    }

    struct elemento *new_head = NULL, *new_tail = NULL;
    struct elemento *pivot = particiona(head, tail, &new_head, &new_tail);

    // 递归排序pivot左侧子链表
    if (new_head != pivot) {
        struct elemento *temp = new_head;
        while (temp->prox != pivot) {
            temp = temp->prox;
        }
        temp->prox = NULL;

        new_head = quick_sort_rec(new_head, temp);
        // 连接左链与pivot
        temp = get_tail(new_head);
        temp->prox = pivot;
    }

    // 递归排序pivot右侧子链表
    pivot->prox = quick_sort_rec(pivot->prox, new_tail);

    return new_head;
}

// 对外接口：接收链表头指针，完成排序
void quick_sort(struct elemento **head) {
    *head = quick_sort_rec(*head, get_tail(*head));
}

int main(){
    setlocale(LC_ALL, "portuguese");

    struct elemento *lista_um = NULL;

    // 正确初始化链表：分配6个连续节点并设置prox
    lista_um = (struct elemento *) malloc(sizeof(struct elemento)*6);
    struct elemento *temp = lista_um;
    
    temp->chave[0] = 30;
    temp->prox = temp + 1;
    temp = temp->prox;
    
    temp->chave[0] = 50;
    temp->prox = temp + 1;
    temp = temp->prox;
    
    temp->chave[0] = 40;
    temp->prox = temp + 1;
    temp = temp->prox;
    
    temp->chave[0] = 10;
    temp->prox = temp + 1;
    temp = temp->prox;
    
    temp->chave[0] = 5;
    temp->prox = temp + 1;
    temp = temp->prox;
    
    temp->chave[0] = 20;
    temp->prox = NULL; // 尾节点prox置空

    printf("排序前：");
    mostrar_chaves(lista_um);

    quick_sort(&lista_um);

    printf("排序后：");
    mostrar_chaves(lista_um);

    // 释放内存
    temp = lista_um;
    while (temp != NULL) {
        struct elemento *next = temp->prox;
        free(temp);
        temp = next;
    }

    return 0;
}

修正关键点说明 #

1. 链表初始化：利用连续内存分配的特性，通过temp->prox = temp +1设置节点间的关联，最后一个节点的prox置为NULL，确保链表结构合法。
2. 分区函数重构：采用左右链分离的逻辑，将小于pivot的节点归到左链，大于等于的归到右链，指针操作清晰易懂，避免原代码的逻辑混乱。
3. 递归逻辑修正：递归函数通过返回排序后的子链表头，正确处理左右子链的排序与连接，确保递归范围准确，边界条件判断清晰。

内容的提问来源于stack exchange，提问作者Besouro Branco