Связанный список сортировки слияния 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 должен разделить список на 2 половинки и рекурсии, если только в список тривиален.
• fusion должен использовать 3 фазы: объединение списков путем приема самого маленького элемента из каждого списка, а затем добавления оставшейся части первого списка и, наконец, добавления оставшихся элементов из второго списка.
• Как правило, плохая идея скрывать указатели позади typedef s, это делает код менее читаемым.

Вот исправленная версия с 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; 
}