Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Сортировка связ. списка

Автор: gepard 13.3.2005, 09:32

Есть связанный(не кольцевой) список класса, один из элементов класса - переменная типа bool.
Нужно: просортировать этот список так, чтобы вначале списка шли все элементы, у которых эта переменная принемает значение false.

Автор: black fox 13.3.2005, 14:12

А какие проблемы то?

Нужно один раз пройти по списку и перенести все элементы у которых нужная переменная =false в начало списка.

Автор: De Gray 13.3.2005, 14:35

Можно сделать так.
Создаешь 2 других списка.
В один заносишь только тип -- true, в другой false, потом объявляешь последним элементом второго начало первго. Память под эти элементы не выделяешь просто ссылаешься на места в старом списке. потом объявляешь второй списко старым.
З.Ы. Псевдокод с псевдорезультатом

Код


List FalseList();
List TrueList();
pelement Current;
pelement Temp;
for(Temp = Current = List.First;Current;)
{
  if(Current->BoolVariable == false)
  {
    Temp = Current->Next;
    if(!FalseList.First)
      FalseList.First = Current;
    FalseList.Last = Current;
    FalseList.Last->Next = 0;
  }
   else if(Current->BoolVariable == true)
  {
    Temp = Current->Next;
    if(!TrueList.First)
      TrueList.First = Current;
    TrueList.Last = Current;
    TrueList.Last->Next = 0;
  }
  Current = Temp;
}
FalseList.Last->Next = TrueList.First;

Список предполагался односвязным.

Автор: gepard 14.3.2005, 07:04

black fox
Всё верно!
Блин, и почему меня иногда клинит на такой элементаршене smile

У списка ведь есть указатель на предыдущий элемент!
Просто берём и первому элементу списка ставим указатель на предыдущий - который надо перенести!