C Bubblesort in LinkedList

Question

Ich versuche, eine doppelt verknüpfte Liste zu sortieren, aber ich habe einige Probleme. Ich bin ein Noob in C und ich denke, mein Problem ist mit Zeigern.

Ich kann einfach nicht sehen, wie man zwei Positionen innerhalb der Liste und so ist vielleicht das ist das Problem.

Ich habe versucht, es mit Bubblesort zu sortieren, auch wenn ich weiß, dass die Komplexität nicht so gut ist, weil, wie ich noch lerne, ich dachte, dass es ein einfacher Start ist.

ich tryied auch einige Dinge über Leseelemente in einem LinkedList swaping und wie sie sortieren, aber ich bin wirklich mit diesem Problem stecken ...

PS: Ich begann die für mit dem m-> weiter weil meine Liste eine Überschrift hat (m).

PS2: Ich erhalte die Fehlermeldung „Anfrage Mitglied‚next‘in etwas keine Struktur oder Union“, und weiß nicht, wie es die Kommentare lesen zu beheben

struct segment { 
    int x, y; /// position 
    char c; // letter 
    struct segment* next; 
    struct segment* prev; 
}; 


void sortingSegments(struct segment* m) { 
    struct segment **j; struct segment **i; 

    for(i = &((m->next)->next); i !=NULL; i = i->next) { 
      for(j = &(m->next); j == i; j = j->next) { 
       if ((*j)->c > (*i)->c) { 
        struct segment **aux; 
        aux = i; 
        (*aux)->next = (*i)->next; 
        (*aux)->prev = (*i)->prev; 

        i = j; 
        (*i)->next = (*j)->next; 
        (*i)->prev = (*j)->prev; 

        j = aux; 
        (*j)->prev = (*aux)->prev; 
        (*j)->next = (*aux)->next; 
       } 
      } 
    } 
} 

Answer 1

Bitte und versuchen die Verknüpfung von Knoten zu verstehen.

Es basiert auf der simple bubble sort described in wikipedia.

void sortingSegments(struct segment** m) { 
    struct segment *i, *tmp, *prev, *next; 
    int swapped = 1; 
    /* 
    * https://en.wikipedia.org/wiki/Bubble_sort#Pseudocode_implementation 
    * n = length(A) 
    * repeat 
    * swapped = false 
    * for i = 1 to n-1 inclusive do 
    *  //if this pair is out of order 
    *  if A[i - 1] > A[i] then 
    *  // swap them and remember something changed 
    *  swap(A[i - 1], A[i]) 
    *  swapped = true 
    *  end if 
    * end for 
    * until not swapped 
    */ 

    // looping until no more swaps left 
    while (swapped) { 
     swapped = 0; 
     // we begin from the second item at each iteration 
     for (i = (*m)->next; i; i = i->next) { 
      // we need to swap i with i->prev 
      if (i->prev->c > i->c) { 
       prev = i->prev; 
       next = i->next; 
       // swapping first and second elements, 
       // so update m to reflect the change made 
       // to the head of the list 
       if (prev == *m) { 
        *m = i; 
       } 
       // so there is a prev of prev, update that two links 
       else { 
        prev->prev->next = i; 
        i->prev = prev->prev; 
       } 
       // so there is a next, update that two links 
       if (next) { 
        next->prev = prev; 
        prev->next = next; 
       } 
       // no next element, mark the end of the list 
       else { 
        prev->next = NULL; 
       } 
       // this is obvious, prev now becomes i's next 
       prev->prev = i; 
       i->next = prev; 

       // this is needed to reflect the change in i 
       i = prev; 
       swapped = 1; 
      } 
     } 
    } 
}