归并排序循环链表 C

Question

我正在尝试对 C 中的列表进行合并排序。我看到了代码 here on French Wikipedia，但它给了我一个不正确的列表（即未排序）。尽管该函数可以完美编译。请注意，我并没有真正使用 top，我可能很快就会将其从结构中删除。你能帮我弄清楚这段代码有什么问题吗？我不得不将它从算法伪代码翻译成 C 代码。谢谢。

P 是未排序的输入列表。 n 是列表的长度。

typedef struct s_stack t_stack;

struct s_stack {
    int     nbr;
    int     top;
    struct s_stack  *previous;
    struct s_stack  *next;
};

typedef t_stack *Pile;

t_stack *merge_sort(Pile p, int n) {
    Pile    q;
    int     Q;
    int     P;

    q = NULL;
    Q = n / 2;
    P = n - Q;

    if (P >= 2) {
        q = merge_sort(p, P);
        if (Q >= 2)
            p = merge_sort(q, Q);
    } else {
        q = p->next;
    }
    q = fusion(p, P, q, Q);
    return (q);
}

t_stack *fusion(Pile p, int P, Pile q, int Q) {
    t_stack *tmp;

    tmp = NULL;
    while (1) {
        if (p->next->nbr > q->next->nbr) {
            /* my input list (not sorted) is circular and 
            I checked it is well linked ! This is the reason 
            why I need to do all that stuff with the nodes 
            It is basically supposed to move the node q->next
            after node p */

            tmp = q->next;
            q->next = tmp->next;
            q->next->previous = q;
            tmp->previous = p;
            tmp->next = p->next;
            p->next->previous = tmp;
            p->next = tmp;

            if (Q == 1)
                break;
            Q = Q - 1;
        } else {
            if (P == 1) {
                while (Q >= 1) {
                    q = q->next;
                    Q = Q - 1;
                }
                break;
            }
            P = P - 1;
        }
        p = p->next;
    }
    return (q);
}

Answer 1

你的方法有点复杂，但问题没那么简单，但是你漏掉了一些必要的步骤：

merge_sort 应该将列表分成两半并递归，除非该列表很简单。
fusion 必须使用 3 个阶段：通过取最小值合并列表每个列表中的元素，然后附加第一个的其余部分列出并最后附加剩余元素形成第二个列表。
将指针隐藏在 typedef 后面通常不是一个好主意，它使代码的可读性降低。

这是一个修正后的版本，带有一个 main 函数用于测试命令行参数。

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

typedef struct s_stack t_stack;

struct s_stack {
    int     nbr;
    int     top;
    struct s_stack  *previous;
    struct s_stack  *next;
};

t_stack *fusion(t_stack *p, int P, t_stack *q, int Q) {
    t_stack *s;
    t_stack *e;

    s = NULL;
    while (P > 0 && Q > 0) {
        if (p->nbr <= q->nbr) {
            /* select element from p list */
            e = p;
            p = p->next;
            P--;
        } else {
            /* select element from q list */
            e = q;
            q = q->next;
            Q--;
        }
        /* detach e */
        e->previous->next = e->next;
        e->next->previous = e->previous;
        e->next = e->previous = e;
        if (s == NULL) {
            s = e;
        } else {
            /* insert e after s */
            e->previous = s->previous;
            e->next = s;
            s->previous->next = e;
            s->previous = e;
        }
    }
    if (P > 0) {
        /* insert p at the end of s */
        if (s == NULL) {
            s = p;
        }  else {
            /* insert p after s */
            e = p->previous; /* end element of p */
            p->previous = s->previous;
            e->next = s;
            s->previous->next = p;
            s->previous = e;
        }
    }
    if (Q > 0) {
        /* insert q at the end of s */
        if (s == NULL) {
            s = q;
        }  else {
            /* insert q after s */
            e = q->previous; /* end element of p */
            q->previous = s->previous;
            e->next = s;
            s->previous->next = q;
            s->previous = e;
        }
    }
    return s;
}

t_stack *merge_sort(t_stack *s, int S) {
    t_stack *p;
    t_stack *q;
    int     P;
    int     Q;

    if (S < 2) {
        /* single or no elements, already sorted */
        return s;
    }

    /* split p in 2 halves: p[0..P] and q[0..Q] */
    for (q = p = s, P = 0, Q = S; P < Q; P++, Q--) {
        q = q->next;
    }

    p = merge_sort(p, P);
    q = merge_sort(q, Q);
    s = fusion(p, P, q, Q);
    return s;
}

t_stack *append(t_stack *s, int value) {
    t_stack *e = malloc(sizeof(*e));
    e->top = 0;
    e->nbr = value;
    e->next = e->previous = e;
    if (s == NULL) {
        s = e;
    } else {
        /* insert e after s */
        e->previous = s->previous;
        e->next = s;
        s->previous->next = e;
        s->previous = e;
    }
    return s;
}

void print_stack(const char *legend, t_stack *s, int S) {
    printf("%s:", legend);
    while (S-- > 0) {
        printf(" %d", s->nbr);
        s = s->next;
    }
    printf("\n");
    fflush(stdout);
}

int main(int argc, char *argv[]) {
    t_stack *s = NULL;
    int S = 0;
    int i;

    for (i = 1; i < argc; i++) {
        s = append(s, atoi(argv[i]));
        S++;
    }
    print_stack("original stack", s, S);
    s = merge_sort(s, S);
    print_stack("sorted stack", s, S);
    return 0;
}

归并排序循环链表 C

Merge sort circular linked list C

c

merge

mergesort

doubly-linked-list

circular-list