1. Наш канал codeby в telegram. Пишем об информационной безопасности, методах защиты информации, о программировании. Не пропускай новости с кодебай, будь в тренде ! Подробнее ...

    Скрыть объявление

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

Тема в разделе "С и С++", создана пользователем MErovingian, 25 июн 2010.

  1. MErovingian

    MErovingian Гость

    Репутация:
    0
    :)
    Помогите))

    Требуется исправить работу функции сортировки односвязного списка методом пузырька:
    Сортировка проходит успешно, единственное - не обновляется указатель на конец списка, следовательно, если после сортировки я хочу ввести новый элемент(идет добавка в конец), то получается очень плохо.....
    Примерно так:
    числа: 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 - количество элементов, в необходимости этого параментра сомневаюсь.
     
  2. sergg

    sergg Member

    Репутация:
    0
    Регистрация:
    9 май 2010
    Сообщения:
    18
    Симпатии:
    0
    Код:
    <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 - указатель на следующий элемент списка.

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

Поделиться этой страницей