冒泡排序双链表

我的双链表的泡泡分拣function有问题。 当我以单链接的方式对节点进行排序时（仅使用 – > next），它正在工作，但我无法使用 – > prev指针。 这是我正在使用的代码：

void sort(int count) { struct data *tmp,*current,*nextone; int i,j; for(i=0;i<count;i++) { current = first; for(j=0;jnumber > current->next->number) { nextone = current->next; current->next = nextone->next; nextone->next = current; if(current == first) { first = nextone; current = nextone; } else { current = nextone; tmp->next = nextone; } } tmp = current; current = current->next; } } } 

这是我正在使用的结构（使用列表的第一个和最后一个元素的全局变量）：

 struct data { int id; char name[20]; int number; struct data *next; struct data *prev; }; struct data *first = NULL; struct data *last = NULL; 

Answer 1

以下逻辑可行。

我会遵循类似的算法…如果你想移动整个节点……

 struct data *before, *after; if(current->number > current->next->number) { before = current->prev; after = current->next; if(before != NULL){ before->next = after; } current->next = after->next; current->prev = after; after->next = current; after->previous = before; } 

或者，如果数据的排序是目的，您可以简单地交换节点中的数字而不必费心移动整个节点。 您可以展开以下逻辑，以包括交换char数组和id。

 if(current->number > current->next->number) { int tempNum = current->number; current->number = current->next->number; current->next->number = tempNum; } 

Answer 2

你只需要坐下来思考一下。

首先分配？ 那么前一个必须为null。

分配到最后？ Next必须为null。

你需要做的其他事情与你交换的前一个和下一个元素进行一点交换。

一种更容易的方法（对于更大的数组大小也会很快变得更快）是分配一个指针数组，用指向元素的指针填充它们，然后对数组进行qsort然后再执行另一次传递以重新连接指针（并删除temp数组）。

Answer 3

一种更简单的方法是复制节点的数据，您可以交换数据但指针指向节点。

 if(current->number > current->next->number){ swap(current->id,current->next->id); swap(current->name,current->next->name); swap(current->number,current->next->number); } 

使用您的方法，您根本不会设置前一个指针。 您可以首先将双链表排序为单个列表，然后再次遍历列表以设置所有prev指针。

当然，您可以一次对双链表进行排序，但实现起来有点复杂。 您应该每步考虑4个节点，即current，current-> next，以及current-> prev和current-> next-> next。 当你想要交换电流和电流 – >接下来时，你应该设置current->prev->next=current->next, current->next=current->next->next ，依此类推。