Я уже делал эту задачу, но внезапно у меня исчезает способность сделать задачу.
Ищите в поиске по запросу "сортировка односвязного списка" или по запросу "сортировка двусвзяного списка".
Наработка
#include <stdio.h>
template<class T>
class list
{
public:
list<T>* next;
T* e;
list()
{
this->next = NULL;
this->e = new e;
}
list(int a)
{
this->next = NULL;
this->e = new e;
(this->e)->a = a;
}
void add_next()
{
list<T>* iterator;
iterator = this;
while (iterator->next != NULL)
{
iterator = iterator->next;
}
iterator->next = new list<T> ;
}
void add_next(int a)
{
list<T>* iterator;
iterator = this;
while (iterator->next != NULL)
{
iterator = iterator->next;
}
iterator->next = new list<T> (a) ;
}
void print_list()
{
list<T>* iterator;
iterator = this;
while (iterator != NULL)
{
printf("%x %d\n", iterator, (iterator->e)->a);
iterator = iterator->next;
}
}
// сортировка по e.a (пузырьковая сортировка)
void sort_list()
{
list<T>* iterator;
list<T>* iterator1;
list<T>* iterator2;
list<T>* iterator3;
list<T>* iterator4;
list<T>* temp;
list<T>* iterator5;
iterator = this;
iterator2 = NULL;
while (iterator != NULL)
{
iterator1 = iterator->next;
iterator4 = iterator; // iterator4 - это то, что указывает на iterator1
iterator5 = iterator->next; // iterator5 - это то, на что указывает iterator
while ( iterator1 != NULL )
{
iterator3 = iterator1->next;
if ( (iterator1->e)->a > (iterator->e)->a) //сравнение для сортировки
{
// данные шаблонного класса не должны трогаться (так как объект может быть очень крупным по размеру)
// кто указывает на iterator (iterator2)
// кто указывает на iterator должен указывать на iterator1
//
if (iterator2 != NULL)
{
iterator2->next = iterator1;
}
else
{
//
//?
// я попал в тупик
}
// если iterator указывает на iterator1;
if (iterator-> next == iterator1)
{
iterator1->next = iterator;
iterator->next = iterator3;
}
else
{
iterator1->next = iterator5;
iterator->next = iterator3;
iterator4->next = iterator;
}
} // end if
iterator4 = iterator1;
iterator1 = iterator1->next;
} // end while ( iterator1 != NULL)
iterator2 = iterator;
iterator = iterator->next;
} // end while (iterator != NULL )
} // end sort_list()
};
// наследование от list не нужно для atd. ,
class atd
{
public:
int a;
void print_class()
{
printf("%d\n", a);
}
};
int main()
{
// один элемент списка
list <atd> t;
//t.a = 5;
(t.e)->a = 5;
(t.e)->print_class();
t.add_next();
((t.next)->e)->a = 6;
((t.next)->e)->print_class();
printf("\n");
t.print_list();
printf("\n");
t.add_next(7);
t.print_list();
//t.sort_list();
printf("\n");
t.add_next(8);
t.print_list();
printf("\n");
t.sort_list();
t.print_list();
return 0;
}