Связанный список с пузырьковой сортировкой, замена указателей. С - PullRequest
Новая
       47

Связанный список с пузырьковой сортировкой, замена указателей. С

1 голос
/ 24 января 2012

Я пытаюсь поменять местами два указателя в односвязном списке с помощью пузырьковой сортировки. Я сделал функцию сравнения, и она работает хорошо. В функции свопинга своп работает хорошо, мне удалось поменять местами узел и node->next, хотя связанный список «теряет» информацию об узле (после свопа), поэтому первый узел в связанный список node->next. Я использую универсальную функцию, которая выполняет сортировку пузырьков и вызывает функцию сравнения и функцию обмена.

Есть идеи, почему это происходит? 

void swap_arr(void **arr,int i , int j)
{

  Team *teamList = (Team*) arr ;    
  Team *teamI = (Team*) arr , *teamJ ;
  Team *temp ;
  Team *temp1;
  int z;


  // Receives instead i
  for(z=0; z<i; z++)
    teamI = teamI->next;

  //teamJ is the i+1    
  teamJ =  teamI->next;

  temp = teamI;
  temp1 = teamJ->next;


  teamI = teamJ ;

  teamJ = temp;

  if (temp1->next->next==NULL)
     teamJ->next = NULL;
  else
     teamJ->next = temp1->next;

  teamI->next = teamJ;

   if (temp1==NULL)
     teamJ->next=NULL;
  else
     teamJ->next = temp1;  
}

Ответы [ 2 ]

3 голосов
/ 24 января 2012

Для замены двух узлов (a, b) вам необходим доступ к «внешнему» узлу (o), который указывает на первый. (и есть также узел p после a и b. (p также может быть NULL, но это не важно)

Старая ситуация: 

o->next == a
a->next == b
b->next == p

Новая ситуация: 

o->next == b
b->next == a
a->next == p

Этот обмен может быть выполнен только , если o на самом деле является узлом . (и поэтому: имеет указатель o-> next), поэтому вам понадобится специальный код для обработки случая, когда a является главой цепочки.

Но нет: o-> next - это только "struct list *", поэтому можно использовать любой указатель на список. В большинстве случаев простейшим решением является использование аргумента указатель-на-указатель для функции подкачки; указатель на указатель может указывать либо на начало цепочки, либо на указатель некоторого узла -> следующий.

0 голосов
/ 25 июня 2013

Я также пытался реализовать сортировку связанных списков с помощью пузырьковой сортировки, хотя изменение, которое вы можете сделать в своем коде, было бы вместо написания функции подкачки, вы можете просто поменять их только в своем коде, и каждый раз, когда вам понадобится 3 разных указателя, указывающих на соседние узлы. Вы можете найти реализованный код здесь .

...