Сортировка списка

  • Автор темы MErovingian
  • Дата начала
M

MErovingian

#1
:)
Помогите))

Требуется исправить работу функции сортировки односвязного списка методом пузырька:
Сортировка проходит успешно, единственное - не обновляется указатель на конец списка, следовательно, если после сортировки я хочу ввести новый элемент(идет добавка в конец), то получается очень плохо.....
Примерно так:
числа: 3 7 8 6 4 1 9 5 2
сортируем, получаем: 1 2 3 4 5 6 7 8 9, конец списка не обновлён, остается по прежнему элементом, с инф. полем "2", при добавлении элемента "777" получаю список:
1 2 777.

Код:
void bubble(s1** start,s1** end, int n)
{
int i;
s1* p1=*start;
s1* p0;
s1* p2;

while(n>1)
{
p0=NULL;
p1=*start;
p2=p1->next;
i=0;
while(i<n-1)
{
if(p1->mark>p2->mark)
{
if(p0==NULL)
{
p1->next=p2->next;
p2->next=p1;
*start=p2;
}
else
{
p1->next=p2->next;
p2->next=p1;
p0->next=p2;

}
p0=p2;
p2=p1->next;

}
else
{
p0=p1;
p1=p2;
p2=p2->next;
}
i++;
}
n--;
}
}
p0 - указатель на предыдущий элемент
p1 - указатель на элемент
p2 - указатель на следущий элемент
mark - сравниваемое инф. поле.
i - счетчик элементов.
n - количество элементов, в необходимости этого параментра сомневаюсь.
 

sergg

Member
09.05.2010
18
0
#2
C++:
<list>*current=begin;
bool isDone=false;

while(current->next)
{ 
while(!isDone)
{
isDone=true;
if(current->value > current->next->value)
{
isDone=false;
<list>*temp=new <list>;
temp=current;
current=current->next;
current->next=temp;
delete temp;
}
}
current=current->next;
}
вроде бы так должно работать.

<list> - тип списка (имя класса твоего списка)
current - текущий элемент списка
begin - перый элемент списка
isDone - флажок, указывающий на завершение сортировки. Если в списке найдется беспорядок(текущее значение больше следующего), то isDone=false указывает на то, что список не отсортирован.
value - значение, хранящееся в информационном поле списка.
temp - временный элемент, для того, что бы произвести замену.
next - указатель на следующий элемент списка.

Я не проверял, но логически вроде все правильно.