Bubble сортировать двойной связанный список

Question

Привет всем Я стараюсь сортировать свой двойной связанный список в C, используя алгоритм сортировки пузырьков. Вот мой код:

struct node { 
       unsigned char key; 
       unsigned char num; 
       struct node *left; 
       struct node *right; 
      }; 

Вот мой род несильно:

void sort(int count, struct node *t_node) 
{ 
    struct node *tmp,*nextnode, *node1, *node2; 

    for(node1 = t_node;node1->right != NULL ;node1 = node1->right) { 
     for(node2 = node1->right; node2->right != NULL; node2 = node2->right) { 
      if(node2->key > node2->right->key) 
      {    
       nextnode = node2->right; 
       tmp = node2->left; 
       node2->right = nextnode->right;    
       node2->left = nextnode->left; 
       nextnode->right = node2; 
       nextnode->left = tmp; 
      } 
     } 
    } 

} 

Он работает в 80%, так как, например, данные:

node1 key=3 
node2 key=144 
node3 key=49 
node4 key=207 

Результат после сортировки:

node1 key=3 
node2 key=144 
node4 key=207 

Почему мой третий узел исчез? В чем проблема?

Answer 1

Это двойной связанный список. Чтобы заменить два узла, обычно необходимо обновить 6 указателей. Скажем, у нас есть A <-> B <-> C <-> D и вы хотите поменять B и C: вам необходимо обновить right из A, B и C, а также left из B, C и D.

Ваш код только обновления 4 указателей здесь:

 if(node2->key > node2->right->key) 
     {    
      nextnode = node2->right; 
      tmp = node2->left; 
      node2->right = nextnode->right;    
      node2->left = nextnode->left; 
      nextnode->right = node2; 
      nextnode->left = tmp; 
     } 

Это должно устранить проблему:

 if(node2->key > node2->right->key) 
     {    
      nextnode = node2->right; 
      tmp = node2->left; 
      if (tmp) 
       tmp->right = nextnode; 
      if (nextnode->right) 
       nextnode->right->left = node2; 
      node2->right = nextnode->right;    
      node2->left = nextnode->left; 
      nextnode->right = node2; 
      nextnode->left = tmp; 
     } 

Answer 2

Кроме того, необходимо заменить предыдущий узел (tmp в вашем коде, но я хотел бы предложить более явное имя ...) right указатель, а левый указатель следующего следующего узла:

tmp <-> node1 <-> node2 <-> nextnext 

Вы находятся на node1 и обнаружить вы должны поменять его с node2:

• вы должны иметь tmp ->node1 изменен tmp ->node2
• Вы должны иметь node2 < - изменено на node1 < - а