Указатели с++ двусвязный список

[Анная]

Здравствуйте уважаемые форумчанины!
Мое задание:
Разработать класс, содержащий численные элементы. Составить двусвязный список из объектов этого класса и отсортировать его по любому полю.
Я нашла вот такую программу http://ci-plus-plus-snachala.ru/?p=60
Я понимаю эта программа создает только двусвязный список, а надо еще сделать сортировкy...Правильно ли я понимаю? И что значит отсортировать по любому полю, ведь все что мы можем отсортировать в этой программе это наши значения....
p.s. Это первая программа на с++, поэтомy вот такие проблемы...

[Helloween]

Сортировка хауноу.

#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "iostream.h"


template <typename T>
class DoubleLinkedList
{
public:
	DoubleLinkedList() : _first(NULL), _last(NULL) {}
	~DoubleLinkedList();
	DoubleLinkedList& operator=(const DoubleLinkedList<T>&);
	explicit DoubleLinkedList(const DoubleLinkedList<T>&);
	void clear();
	void insert(T val);
	void print();
	void sort();
	unsigned long size() {return _size;}
private:
   struct node
   {
	  T value;
	  node* next;
	  node* prev;
   };
   node* _first;
   node* _last;
   unsigned long _size;
};

template <typename T>
DoubleLinkedList<T>::~DoubleLinkedList()
{
	clear();
}

template <typename T>
void DoubleLinkedList<T>::clear()
{
	if(_last)
	{
	  node* cur = _last->prev;
	  while(cur)
	  {
		  node* tmp = cur->prev;
		  delete cur;
		  cur = tmp;
	  }
	  delete _last;
	  _last = NULL;
	  _first = NULL;
	}
	_size = 0;
}

template <typename T>
DoubleLinkedList<T>& DoubleLinkedList<T>::operator=(const DoubleLinkedList<T>& rh)
{
   clear();
   if(rh._first)
   {
       _size = rh._size;
	   node* tmp = rh._first;
	   _first = new node();
	   _first->value = rh._first->value;
	   _first->prev = NULL;
	   node* cur = _first;
	   while(tmp->next)
	   {
		  cur->next = new node();
		  cur->next->value = tmp->next->value;
		  tmp = tmp->next;
		  cur->next->prev = cur;
		  cur = cur->next;
	   }
	   cur->next = NULL;
   }
   return *this;
}

template <typename T>
DoubleLinkedList<T>::DoubleLinkedList(const DoubleLinkedList<T>& rh)
{
    operator=(rh);
}

template <typename T>
void DoubleLinkedList<T>::insert(T val)
{
	node* tmp = new node();
    memset(tmp,0,sizeof(node));
	tmp->value= val;
	if(!_first)
	{
		_first = tmp;
		_size++;
	}
	else if(!_last)
	{
		_last = tmp;
		_first->next = _last;
		_last->prev = _first;
		_size++;
	}else
	{
		node* _temp = _last;
		_last = tmp;
		_temp->next = _last;
		_last->prev = _temp;
		_size++;
    }
}

template <typename T>
void DoubleLinkedList<T>::print()
{
	if(_first)
	{
		std::cout<<_first->value<<" ";
        node* cur = _first;
		while(cur->next)
		{
			std::cout<<cur->next->value<<" ";
			cur = cur->next;
        }
	}
	std::cout<<std::endl;
}

template <typename T>
void DoubleLinkedList<T>::sort()
{
	if(_first)
	{
		node* cur = _first;
		while(cur)
		{
            node* cur2 = _first;
			while(cur2)
			{
				cur2 = cur2->next;
				if(cur2)
				{
					if(cur2->prev->value > cur2->value)
					{
						T tmp = cur2->value;
						cur2->value = cur2->prev->value;
						cur2->prev->value = tmp;
                    }
                }
			}
			cur = cur->next;
        }
    }
}

typedef DoubleLinkedList<int> IntDoubleLinkedList;

int main()
{
	IntDoubleLinkedList l;
	unsigned long seed = time(NULL);
	srand(seed);
	for(int i = 0; i < 10; i++)
	   l.insert(rand() % 100 + 1);
	l.print();
	l.sort();
	l.print();
	return 0;
}

[Bugrimov]

Анная что у Вас у самой получилось сделать...??? Выкладывайте посмотрим.

[daslex]

Сообщение от Анная

Здравствуйте уважаемые форумчанины!
И что значит отсортировать по любому полю, ведь все что мы можем отсортировать в этой программе это наши значения....

По́ле кла́сса или атрибу́т (переменная-член, data member, class field, instance variable) в объектно-ориентированном программировании — переменная, связанная с классом или объектом
http://ru.wikipedia.org/wiki/%CF%EE%...EB%E0%F1%F1%E0

Если брать тот пример, то делаете внутри структуры несколько переменных, например 3

struct Node //Структура являющаяся звеном списка
{
int age; //Возраст
bool sem_pol; //Состоит в браке или нет
string name; //ФИО
Node *Next,*Prev; //Указатели на адреса следующего и предыдущего элементов списка
};

Теперь каждая из 3 переменных есть поле, по которому можно выполнять сортировку. Если вам достаточно одного поля, то выбираете age и делаете сортировку. (Просто можно сделать меню Сортировать по, но тогда, возможно, придется сделать различные сортировки (одна для строк, вторая для чисел и т.п.))

Сортировку можно выполнять разными способами. Например меняя сами указатели местами (те, что Next,Prev, Head,Tail) Такая сортировка возможна, но скорее всего вам можно проще.

Если вам можно проще, то достаточно выполнять проход по списку, вытаскивать из списка значение (по которому сортируете), но переставлять надо не 1 значение, а все значения структуры. Т.е. вы нашли одно значение (одно поле), которое надо переставить, а меняете местами не только его, но и все значения, которые относятся к этому полю.

Условно это выглядит так

//Первый элемент списка
int age = 18; //Возраст 18
bool sem_pol = true; //Состоит в браке
string name = Герасимво Сергей Николаевич; //Герасимво Сергей Николаевич
Node *Next,*Prev; //Указатели на адреса следующего и предыдущего элементов списка

//Второй элемент списка
int age = 23; //Возраст 23
bool sem_pol = false; //НЕ состоит в браке
string name; //Бышовец Анна Григоръевна
Node *Next,*Prev; //Указатели на адреса следующего и предыдущего

Далее вы выполняет сортировку по убыванию по возрасту.
Во время сортировки вам достаточно вытаскивать только age, сравнивать его со следующим age
18<23? Да, значит надо поменять местами поля. Только менять местами надо не одно поле, а все поля, которые относятся к найденному age.

18 c 23
true с false
Герасимво Сергей Николаевич с Бышовец Анна Григоръевна
//////////////////

Таким образом и получается, что выбирая только одно поле, вы сортируете именно весь список по полю.

Если условно считать, что ключевое поле есть Name и выполнить сортировку только по значению age, то получится только переназначить возраст каждому человеку.

===================
И я знаю, что объяснил не идеально, но надеюсь достаточно, чтобы понятно было.