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

[@LE}{@NDER]

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

Это интерфейс класса:

#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);
};

а вот и сама функция

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;
}

}

зараннее спасибо!

 

[Normann]

Не проверял, попробуй

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:

 

[@LE}{@NDER]

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

Привожу работоспособный код, который получился у меня:

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;
}
}

ЗЫ: Если кто-то найдет более оптимальное решение, буду очень признателен

 

[@LE}{@NDER]

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

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

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

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