Сортировка кольцевого списка

[counter]

есть класс реализующий кольцевой список

class Node  {    

	Ring *ring;
	int countStr;       // kol-vo strok v kolce

public:
	...
  	
	void SortRing ();  // сортировка
	
};

class Ring {

	char *str;    // stroka
	int length;   // dlina stroki
   
public:
	
	Ring *Next;
	Ring *Prev;
            ...
};

надо отсортировать список в алфавитном порядке строк


пробовал так но не получается. почему?

void Node::SortRing ()

{
	Ring *buff,*val,*val2;

	val=ring;
	for(int i=0;i<countStr-1;i++)
		
	{   
		val2=val->Next;
		for(int j=i;j<countStr;j++)

		{
						
		if( strcmp(val2->GetStr(),val->GetStr())<0 )

			{
				buff=ring;
				ring=ring->Next;
				ring->Next=buff;
			}
		
		val2=val2->Next;
		}
    
		val=val->Next;
	}
	
}

void main()	

{
	int n; // kol-vo kolec
	
	do {
	cout<<"\nVvedite kolichestvo spiskov : ";
	cin>>n;

	 if (n<=0 || n>30)

	  {
		Exception();
	  }

	} while (n<=0 || n>30);

	cout<<"\nVvedite put' k ishodnomu failu : "; // списки заполняем из файла
	char str[15];
	cin>>str;

	Node *A=new Node[n];
	
	for(int i=0;i<n;i++)

	{	  	
		// тут создаем списки
	}

	for(int i=0;i<n;i++)

	{
		A[i].SortRing(); // тут пытаемся их сортировать
		A[i].FileWrite("C:\\SortRing.txt");  // результат пишем в файл
	}
	
}

[theos]

В тот момент, когда Вы меняете 2 элемента местами, позаботьтесь о присвоении каждому корректных указателей как Next, так и Prev. Иначе у вас список весь рушится.

Далее обратите внимание, что если вы корректно поменяли местами элементы, то val2->Next будет уже далеко не тем, что вы ожидаете. ))

[Ламер_001]

а не проще сначала отсортировать, а потом создать?

[counter]

Сообщение от theos

В тот момент, когда Вы меняете 2 элемента местами, позаботьтесь о присвоении каждому корректных указателей как Next, так и Prev. Иначе у вас список весь рушится.

Далее обратите внимание, что если вы корректно поменяли местами элементы, то val2->Next будет уже далеко не тем, что вы ожидаете. ))

может у вас есть ссылка где есть нечто подобное?

[theos]

У меня дома где-то валяются полностью реализованые списки (одно- и двусвязные), ещё со времён 2 курса универа. Если очень надо, могу сегодня вечером порыться и выложить. А сейчас с работы в падлу писать - долго. Попробуйте всё же сами отладить. Это полезно сделать хотя бы раз в жизни самому )) Для полного понимания.

[counter]

А в принципе ход моих мыслей правилен?

[theos]

Так. Ну во 1х исходя из смысла классов их имена надо поменять местами )) Так Node - "вершина" - как раз базовый элемент из которого строится кольцо. А Ring - весь список.

Это не существенно, как и следующее: выводить результаты всё же лучше в разные файлы

Теперь по существу. Как я понимаю в переменной Ring *ring хранится рут элемент (0й, от которого надо сортировать..). Сортировка пузырьком, в ней: в переменной val - i-й элемент (отсчитывая от ring), в val2 - j-й. Тогда:

Внутренний цикл начинаем не с i-го элемента, а с (i+1)-го. Обязаьтельно. Это логически верно, тк хотя мы и не используем j, получается 1 лишняя итерация при которой мы захватываем 0й элемент ещё раз.

Процедура перемены мест элементов:

val2->Prev = val->Prev;
buff = val2->Next;
val2->Next = val;
val->Prev = val2;
val->Next = buff;
buff = val;
val = val2;
val2 = buff;

Примерно так. Прогу компилить не пробовал, но вроде должно работать с этими изменениями. Попробуйте, если не получится - будем значит компилить и отлаживать.

[counter]

вот додумал еще немного

void Node::SortRing ()

{

	Ring *first,*second,*buff1,*buff2,*buff3;

	first=ring;
    second=ring->Next;

	for(int i=0;i<countStr-1;i++)

	{
		buff3=first;
		for(int j=i+1;j<countStr;j++)

		{
			buff2=second;
			if( strcmp(first->GetStr(),second->GetStr())>0 )

			{
				buff1=first;

				first=second;

				first->Prev=buff1->Prev;

				buff1->Next=second->Next;
				buff1->Prev=first;

				second=buff1;
				first->Next=second;

				second=first->Next;
				
				buff1=first;        // ????????????
				first=buff1;        // ????????????
			}

			else

			{
				second=buff2->Next; // ?????????????
				first=buff3;               // ?????????????
			}
		}

		first=buff3->Next;  // ?????????????????????
	}
}

сама замена элементов происходит правильно указатели тоже корректны.

Я только не знаю как быть с указателями first и second когда они выходят из циклов.