Как работает этот метод сортировки?

Question

Я изучаю C из «Книги C». Я думаю, что это хорошая книга, и я понимаю большую часть ее, как указатели. Но я не могу придумать пример сортировки со связанными структурами списков.

Если я нарисую его на бумаге, я все равно поймаю, что указатели второго объекта не настроены на первый, если они переключаются. Возможно, я неправильно думаю об этих указателях в структурах. Может кто-нибудь объяснить этот обмен очень короткий, может быть, на примере, как я сделал в коде с 5, 99 и 1. Я хотел бы понять этот вид сортировки со связанным списком, потому что он кажется довольно полезным позже.

Это код: #include #include

struct list_ele{ 
    int data; 
    struct list_ele *pointer; 
}ar[3]; 

struct list_ele * 
sortfun(struct list_ele *list); 

int 
main(){ 
    struct list_ele *lp; 

    ar[0].data = 5; 
    ar[0].pointer = &ar[1]; 
    ar[1].data = 99; 
    ar[1].pointer = &ar[2]; 
    ar[2].data = 1; 
    ar[2].pointer = 0;/* mark end of list */ 

    /* sort list */ 
    lp = sortfun(ar); 
    /* follow pointers */ 
    while(lp){ 
     printf("contents %d\n", lp->data); 
     lp = lp->pointer; 
    } 
    exit(EXIT_SUCCESS); 
} 

struct list_ele * 
sortfun(struct list_ele *list) 
{ 
    int exchange; 
    struct list_ele *nextp, *thisp, dummy; 

    /* 
    * Algorithm is this: 
    * Repeatedly scan list. 
    * If two list items are out of order, 
    * link them in the other way round. 
    * Stop if a full pass is made and no 
    * exchanges are required. 
    * The whole business is confused by 
    * working one element behind the 
    * first one of interest. 
    * This is because of the simple mechanics of 
    * linking and unlinking elements. 
    */ 

    dummy.pointer = list; 
    do{ 
     exchange = 0; 
     thisp = &dummy;  
      while((nextp = thisp->pointer) && nextp->pointer) { 
       if(nextp->data > nextp->pointer->data){ 
        /* exchange */ 
        exchange = 1; 
        thisp->pointer = nextp->pointer; 
        nextp->pointer = this->pointer->pointer; 
        thisp->pointer = nextp; 
       } 
      thisp = thisp->pointer; 
     } 
    }while(exchange); 

    return(dummy.pointer); 
} 

Answer 1

Это пузырьковая сортировка. Он работает, обменивая элементы не по порядку, повторяя, пока не осталось больше предметов. Это полезно, если не так много предметов, в противном случае требуются другие методы. tricki часть, вероятно, это:

   thisp->pointer = nextp->pointer; 
       nextp->pointer = this->pointer->pointer; 
       thisp->pointer = nextp; 

, который предназначен для замены порядка двух элементов в связанном списке.