Сортировка структур в односвязном списке

Тема в разделе "Общие вопросы по С и С++", создана пользователем @LE}{@NDER, 29 сен 2007.

  1. @LE}{@NDER

    @LE}{@NDER Гость

    Нужна помощь в исправлении кода. Есть класс Library и структура Book на основе которых я реализовал односвязный список + различные методы, добавление элементов, удаление элементов, поиск. А вот с сортировкой по полям возникли проблемы. Если кто-то сможет помочь буду очень благодарен.

    Это интерфейс класса:
    Код (Text):
    #include <iostream>
    #include <conio.h>
    #include <stdlib.h>

    #include <string>

    using namespace std;
    ///////////////////////////////////////////////////////////
    struct Book  // один элемент списка
    {
    int index;
    string Name;
    string Author;
    int Year;
    Book* next; // указатель на следующую структуру
    };
    ///////////////////////////////////////////////////////////
    class Library // список
    {
    private:
    Book* first;
    Book* last;
    public:
    Library ( )         // конструктор без параметров
    { first = NULL; }    // первого элемента пока нет
    void AddBook ( int a, string b, string c, int d); // добавление элемента
    void ShowList ( );    // показ данных
    Book* SearchName(string &str);
    bool SearchAuthor(string &str);
    void ShowBook(Book* ptr);
    void SortName(); //[b]вот с этой функцией проблемы[/b]
    bool DeleteBook(const string &sNameBook);
    };
    а вот и сама функция
    Код (Text):
    void Library::SortName()
    {
    Book* previous=NULL;
    Book* current=first;
    Book* next=current->next;
    Book* temp;
    while(current->next!=NULL)
    {
    while(next!=NULL)
    {
    if((current->Name)<(next->Name)) /*используется #include <string> содержащий перегруженные методы < >*/
    {
    previous=next;
    temp=next->next;
    next->next=current;
    current->next=temp;
    }
    else
    next=next->next;
    }
    current=current->next;
    }

    }
    зараннее спасибо! :p
     
  2. Normann

    Normann Well-Known Member

    Регистрация:
    9 авг 2007
    Сообщения:
    168
    Симпатии:
    2
    Не проверял, попробуй

    Код (Text):
    void Library::SortName()
    {
    Book* previous=NULL;
    Book* current=first;
    //Book* next=current->next;
    Book* temp;
    Book *last = NULL;

    while(current->next!=NULL)
    {
    if((current->name) > (current->next->name)) {
    if(previous!=NULL)previous->next = current->next;
    temp = current->next->next;
    current->next->next = current;
    current->next = temp;
    //Они просто меняются указателями, типа местами меняются
    //теперь нужно сравнить это с предидущими (пузырьковый метод)
    if(previous!=NULL) if(last==NULL) last = previous; // сохраняем точку возврата
    current = previous; // и для этого шаг назад

    }
    else {
    if(last!=NULL) { //если есть точка возврата возвращаемся
    previous = last;
    current = previous->next;
    };
    };
    }

    };
    Может это вся лабуда и полный бред, проверять сил нету, хочу спать. :blink:
     
  3. @LE}{@NDER

    @LE}{@NDER Гость

    Проверял, не работает. Там есть ряд ньюансов:
    1. Если в списке всего два элемента.
    2. Если в сортировке участвует первый элемент
    3. Если в сортировке участвует последний элемент.
    Ну и конечно, если элементы сортированы.
    Речь идет о простейшем алгоритме пузырьковой сортировки, который, однако, усложняется связями указателей.

    Привожу работоспособный код, который получился у меня:
    Код (Text):
    void Library::SortName()
    {
    Book* pre = first;
    Book* curr = first;
    Book* next=curr->next;
    for(int i=0; i<GetItemsNumber(first); i++)
    {
    while(curr->next!=NULL)
    {
    if(first->Name>first->next->Name&&first->next==last) //Если в списке 2 несортированных элемента
    {
    first->next=last->next;
    last->next=first;
    first=last;
    last=curr;
    curr=first;
    pre=curr;
    curr=curr->next;
    }
    else if(curr->Name>curr->next->Name&&curr==first) //Если сортируются элементы, и один из них первый
    {
    pre=curr->next;
    curr->next=pre->next;
    pre->next=curr;
    first=pre;
    next=curr->next;
    }
    else if(curr->Name>next->Name&&curr!=first)//Если сортируются элементы, и перывй элемент не учавствует
    {
    if(next->next==NULL){
    curr->next=NULL; last=curr;}
    else
    curr->next=next->next;
    next->next=curr;
    pre->next=next;
    pre=next;
    next=curr->next;
    }
    else if(curr->Name<next->Name)//Если элементы нет необходимости сортировать
    {
    pre=curr;
    curr=next;
    next=curr->next;
    }
    }
    last=curr; //инициализируем указатель на последний элемент!
    pre=first;
    curr=first;
    next=curr->next;
    }
    }
    ЗЫ: Если кто-то найдет более оптимальное решение, буду очень признателен :(
     
  4. @LE}{@NDER

    @LE}{@NDER Гость

    Есть новая задача, не могу найти решение, может кто-то подкорректирует алгоритм.
    Дан однонаправленный связный список, с неизвестным числом элементов и указатель на первый элемент.
    Задача:
    1. Найти есть ли в списке циклы.
    2. Найти количество элементов в списке.
    3. Найти количество элементов в цикле, если таковой имеется.


    Вот ход моих мыслей:
    1. Можно создать два указателя ptr1 и ptr2. Которые изначально принимают значение первого элемента. ptr1 проходит список. ptr2 перемещается с каждым прохождением на один элемент.
    2. Создаем 2 переменные целого типа, одна А будет хранить общее количество элементов, вторая В количество элементов в цикле (если таковой есть). С прохождением списка инкрементируем А.
    3. Если первый указатель достигает NULL, значит циклов нету. Выводим А.
    4. Если ptr2 == ptr1, значит цикл есть. Проходим цикл еще раз до данного елемента инкрементируя В, таким образом получаем. Количество элементов в цикле.


    Проблема: если элемент, на котором зациклен список находится после ptr2, операция зациклится и никогда не завершится.

    У кого-то есть какие-то соображения?
     
Загрузка...

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