泡沫分类双向链表

我对双向链表的气泡排序功能有问题。它正在工作，当我以单向链接的方式排序节点（只有 - >下一个），但我不能使它与 - > prev指针一起工作。这里是我使用的代码：泡沫分类双向链表

void sort(int count) 
{ 
    struct data *tmp,*current,*nextone; 
    int i,j; 
    for(i=0;i<count;i++) 
    { 
     current = first; 
     for(j=0;j<count-1-i;j++) 
     { 
      if(current->number > 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;

来源

2014-01-16 user1630441

发布使用双链表节点移动时给您带来麻烦的代码。 – Buddha

下面的逻辑将工作。

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

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; 
}

来源

2014-01-16 02:04:53 Buddha

工作正常，但由于某种原因，最后一个节点在排序中丢失。当我添加新节点时，它取代了最后一个节点，并且当我阅读它时，最后一个节点根本不显示。 –

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

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等等。

来源

2014-01-16 01:28:54

虽然的确如此，但我确实认为这是一个不好的答案。链表的全部要点之一是避免移动大量数据。根本没有理由为链表做这样的事情。 – klutt

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

先指定？那么以前必须为空。

分配最后？接下来必须为空。

其他任何你需要与之前的&做交换跳舞的下一个要交换的元素。

一个更简单的方法（对于较大的数组大小，它会快速变得更快）是分配一个指针数组，然后用指向这些元素的指针填充这些数组，然后再执行另一次通过重新连线指针并删除临时数组）。

来源

2014-01-16 01:35:15 LoztInSpace

泡沫分类双向链表

回答

相关问题