C 链表中的冒泡排序

Question

我正在尝试对双向链表进行排序，但遇到了一些麻烦。我是 C 菜鸟，我想我的问题是指针..

我只是不知道如何交换列表中的两个位置，所以也许这就是问题所在。

我尝试使用冒泡排序对其进行排序，即使知道它的复杂性不太好，因为我仍在学习，认为这是一种简单的开始方法。

我还尝试阅读一些有关交换链表中的元素以及如何对它们进行排序的内容，但我真的遇到了这个问题......

PS:我用 m->next 开始 for，因为我的列表有一个标题(m)。

PS2:我收到错误“在非结构或 union 中请求成员‘下一个’”，并且不知道如何修复它

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

请阅读评论并尝试理解节点的链接。

它基于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;
            }
        }
    }
}