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

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

  1. MErovingian

    MErovingian Гость

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

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

    Код (Text):
    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

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

    Я не проверял, но логически вроде все правильно.
     
Загрузка...
Похожие Темы - Сортировка списка
  1. vera2014
    Ответов:
    0
    Просмотров:
    1.071
  2. Liori
    Ответов:
    2
    Просмотров:
    1.005
  3. FCDK
    Ответов:
    0
    Просмотров:
    1.264
  4. ленарано
    Ответов:
    1
    Просмотров:
    1.103
  5. Creder
    Ответов:
    0
    Просмотров:
    1.346

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