合併排序循環鏈表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; 
}