Двухсвязный список в С++

[Aple]

Добрый день!
Задали задачу:"Отсортировать двухсвязный список методом выбора".
Код я вроде написал, однако, столкнулся с проблемой(после входа в функцию сортировки, программа зависает)
Пытался ее отладить, вводил последовательность из 3х цифр(3,2,1) и он вроде их сортировал, а затем виснет.

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

Код программы:

//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include<conio.h>
#include<iostream.h>


using namespace std;

//---------------------------------------------------------------------------

#pragma argsused
//===========================================================
class DLIST
{
	public:

		int value;
		DLIST *beg;  	//head
		DLIST *end;
		DLIST *next;
		DLIST *prev;
//=============================================================
	DList()		//конструктор
	{
		beg = NULL;
		end = NULL;
		prev = NULL;
		next = NULL;
	}

//==============================================================
	void MakeDList()	//описание и создание Двусвязного списка
	{
		DLIST *rex = new DLIST;
		cin>>rex->value;
			if(beg == NULL)
				beg = rex;
			else
			{
				end->next = rex;
				rex->prev = end;
			}
			end = rex;

	}//	end of create function



//==============================================================

	void ShowDList()	   //печать списка
	{

		bool bhead = true;
		if(beg == NULL)
		{
			cout<<"The List is empty!"<<endl;
		}

		DLIST *rex = beg;
		while(1)
		{
			if(rex == end)
			{
				cout << rex->value;
				break;
			}
			cout<<rex->value<<" ";
			rex = rex->next;
		}
	}//end of printing aunction



//==============================================================
void Sort()
{

		DLIST *temp = new DLIST;
		DLIST *SmallElement;
		DLIST *i, *j;

		for(i = beg; i != NULL; i = i->next)
		{
			SmallElement = i;
			for(j = i->next; j != NULL; j = j->next)
				if(j->value < SmallElement->value)
					SmallElement = j;

			if(i->next != NULL) i->next->prev=SmallElement;
			if(SmallElement->prev != NULL) SmallElement->prev->next=i;


			if(SmallElement==end)
			{
				i->prev=SmallElement->prev;
				SmallElement->prev=i;
				SmallElement->next=i->next;
				i->next=SmallElement;
				end=SmallElement;
			}
			else
			{
				i->prev=SmallElement->prev;
				SmallElement->prev=i;
				SmallElement->next=i->next;
				i->next=SmallElement;
			}
			if(i == end)
				end = SmallElement;

			if(i == beg)
				beg = SmallElement;
		}

	}	//end of Soting function

};//end of Class
//==============================================================


int main(int argc, char* argv[])
{
	DLIST *L;
	L = new DLIST;


	cout<<"Enter amount of elements which you want to add: ";
	int SIZE;
	cin>>SIZE;

	int temp;
	cout<<"Enter Data: "<<endl;
	for(int i = 0; i < SIZE; i++)
	{
		 L->MakeDList();
	}

	cout<<"\nPrinting DList:"<<endl;
	L->ShowDList();

	L->Sort();
	cout<<"\n\nPrinting DList after sorting: "<<endl;
	L->ShowDList();

	getch();
	return 0;
}

[Stilet]

Куча ошибок:
1) Конструктор неправильно описан

class DLIST
{
	public:
...
//=============================================================
	DLIST()		//конструктор
	{
		beg = NULL;
		end = NULL;
		prev = NULL;
		next = NULL;
	}

Имя класса и конструктора должны совпадать с учетом регистра

2)

	void MakeDList()	//описание и создание Двусвязного списка
	{
		DLIST *rex = new DLIST;
		rex->next=NULL;
		cin>>rex->value;
			if(beg == NULL)				beg = rex;
			rex->prev = end;
			if(end)		
				end->next = rex;
			end = rex;

	}//	end of create function

А то что ты написал - ерундище, потому как rex не связывается со следующим элементом.

3)

	while(1)
		{
			if(rex == end)
			{
				cout << rex->value;
				break;
			}

Эх... Ну ладно, работает и на том спасибо, но лучще бы сократить

		while(rex)
		{
			cout << rex->value<<'\t';
			rex = rex->next;
		}

Хотя бы красивее смотрится.
4) Косяк в конце - объект создали, а освобождать кто будет? Пушкин уже устал. Он в отпуске.

[Aple]

я в этом деле почти новичок, потому спрашиваю:
1) Вы говорите , что имя класса и конструктора должны совпадать с учетом регистра.
что это значит? мне казалось что конструктор должен иметь тоже название что и имя класса. разве не так?

2)Теперь, что касается удаления объекта: а освобождать его надо где?(в конце функции MakeDList() )? или же надо описать деструктор?

[Stilet]

разве не так?

Абсолютно верно. А теперь вспомни что Си регистрозависимый язык, и посмотри как ты написал у себя имя конструктора. Кстати - для конструктора тип не указывается.

а освобождать его надо где?

Где угодно, но в твоем случае видимо в конце программы.

или же надо описать деструктор?

Однозначно, чтоб освободить память занятую под список, тоже в цикле это можно сделать - это будет тебе домашнее задание

[Aple]

Кошмар, опять невнимательность(поэтому я не заметил что конструктор и название класса отличаются по регистру)

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

вот к чему я пришел на текущий момент:

//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include<conio.h>
#include<iostream.h>


using namespace std;

//---------------------------------------------------------------------------

#pragma argsused
//===========================================================
class DLIST
{
	public:

		int value;
		DLIST *beg;  // = head
		DLIST *end;	 // = end
		DLIST *next;
		DLIST *prev;
//=============================================================
	DLIST()		//конструктор
	{
		beg = NULL;
		end = NULL;
		prev = NULL;
		next = NULL;
	}

	~DLIST()
	{
		DLIST *ptr, *temp;
		for(ptr = beg; ; )
		{
			temp = ptr->next;
			delete ptr;
			ptr = temp;
			if(ptr == end)
			{
				delete ptr;
				break;
            }
        }
	}
//==============================================================
	void MakeDList()	//описание и создание Двусвязного списка
	{
		DLIST *rex = new DLIST;
		cin>>rex->value;
			if(beg == NULL)
				beg = rex;
			else
			{
				end->next = rex;
				rex->prev = end;
			}
			end = rex;

	}//	end of create function



//==============================================================

	void ShowDList()	   //печать списка
	{

		bool bhead = true;
		if(beg == NULL)
		{
			cout<<"The List is empty!"<<endl;
		}

		DLIST *rex = beg;
		while(rex)
		{
			cout<<rex->value<<"\t";
			rex = rex->next;
		}
	}//end of printing aunction



//==============================================================
void Sort()
{

		DLIST *SmallElement;
		DLIST *i, *j;

		for(i = beg; i != NULL; i = i->next)
		{
			SmallElement = i;
			for(j = i->next; j != NULL; j = j->next)
				if(j->value < SmallElement->value)
					SmallElement = j;

			if(i->next != NULL) i->next->prev=SmallElement;
			if(SmallElement->prev != NULL) SmallElement->prev->next=i;


			if(SmallElement==end)
			{
				i->prev=SmallElement->prev;
				SmallElement->prev=i;
				SmallElement->next=i->next;
				i->next=SmallElement;
				end=SmallElement;
			}
			else
			{
				i->prev=SmallElement->prev;
				SmallElement->prev=i;
				SmallElement->next=i->next;
				i->next=SmallElement;
			}
			if(i == end)
				end = SmallElement;

			if(i == beg)
				beg = SmallElement;
		}

	}	//end of Sorting function

};//end of Class
//==============================================================


int main(int argc, char* argv[])
{
	DLIST *L;
	L = new DLIST;


	cout<<"Enter amount of elements which you want to add: ";
	int SIZE;
	cin>>SIZE;

	int temp;
	cout<<"Enter Data: "<<endl;
	for(int i = 0; i < SIZE; i++)
	{
		 L->MakeDList();
	}

	cout<<"\nPrinting DList:"<<endl;
	L->ShowDList();

	L->Sort();
	cout<<"\n\nPrinting DList after sorting: "<<endl;
	L->ShowDList();

	getch();
	return 0;
}

//---------------------------------------------------------------------------

[Stilet]

Когда я поправил твою программу так как описал мне выдало результат:

Enter amount of elements which you want to add: 20
Enter Data:

Printing DList:
41 18467 6334 26500 19169 15724 11478 29358 26962 24464
5705 28145 23281 16827 9961 491 2995 11942 4827 5436

Единственное что я вместо ввода ручками поставил случайное число.
Твоя программа работоспособна, если ты верно учел мои коментарии.

[Aple]

Виталий, а тот скрин который вы сейчас представили кажется он не самый последний, ведь я вначале просто вывел то, что содержится в списке.
А уже после этого начал сортировать, а затем еще раз вывел содержимое списка(но уже в отсортированном порядке).

Или же я просто чего-то совсем не понимаю
Что касается кода то в последний раз когда я его исправлял я изменил имя Конструктора и дописал к нему деструктор.
Может быть где-то не так понял?
Я прошу извинить меня за тупость, я просто многого не понимаю.

И еще, то что изображено на этом скрине-оно ведь не отсортированно

[Stilet]

Вот тебе полный код:

// rwerw.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include<conio.h>
#include<iostream>
using namespace std;

class DLIST
{
	public:

		int value;
		DLIST *beg;  	//head
		DLIST *end;
		DLIST *next;
		DLIST *prev;
//=============================================================
	DLIST()		//конструктор
	{
		beg = NULL;
		end = NULL;
		prev = NULL;
		next = NULL;
	}

//==============================================================
	void MakeDList()	//описание и создание Двусвязного списка
	{
		DLIST *rex = new DLIST;
		rex->next=NULL;
		//cin>>rex->value;
		rex->value=rand();
			if(beg == NULL)				beg = rex;
			rex->prev = end;
			if(end)
				end->next = rex;
			end = rex;

	}//	end of create function



//==============================================================

	void ShowDList()	   //печать списка
	{

		bool bhead = true;
		if(beg == NULL)
		{
			cout<<"The List is empty!"<<endl;
		}

		DLIST *rex = beg;
		while(rex)
		{
			cout << rex->value<<'\t';
			rex = rex->next;
		}
	}//end of printing aunction



//==============================================================
void Sort()
{

		DLIST *temp = new DLIST;
		DLIST *SmallElement;
		DLIST *i, *j;

		for(i = beg; i != NULL; i = i->next)
		{
			SmallElement = i;
			for(j = i->next; j != NULL; j = j->next)
				if(j->value < SmallElement->value)
					SmallElement = j;

			if(i->next != NULL) i->next->prev=SmallElement;
			if(SmallElement->prev != NULL) SmallElement->prev->next=i;


			if(SmallElement==end)
			{
				i->prev=SmallElement->prev;
				SmallElement->prev=i;
				SmallElement->next=i->next;
				i->next=SmallElement;
				end=SmallElement;
			}
			else
			{
				i->prev=SmallElement->prev;
				SmallElement->prev=i;
				SmallElement->next=i->next;
				i->next=SmallElement;
			}
			if(i == end)
				end = SmallElement;

			if(i == beg)
				beg = SmallElement;
		}

	}	//end of Soting function

};//end of Class
//==============================================================



int _tmain(int argc, _TCHAR* argv[])
{
		DLIST *L;
	L = new DLIST();


	cout<<"Enter amount of elements which you want to add: ";
	int SIZE;
	cin>>SIZE;

	int temp;
	cout<<"Enter Data: "<<endl;
	for(int i = 0; i < SIZE; i++)
	{
		 L->MakeDList();
	}

	cout<<"\nPrinting DList:"<<endl;
	L->ShowDList();

	L->Sort();
	cout<<"\n\nPrinting DList after sorting: "<<endl;
	L->ShowDList();

	getchar();

	return 0;
}

Только чти он тут на VS, так что не копипасти его весь тупо.

[Aple]

видимо я точно, чего-то не понял
у меня возникло несколько вопросов?:
1) Я скомпилировал этот файл на Visual C++(visual studio 2008)
и при компиляции он выдал мне ошибку
fatal error C1083: Не удается открыть файл include: stdafx.h: No such file or directory

2) если закоментить этот файл и изменить в заголовке функции main() название, то он скомпилируется. Но как я и говорил он введет Случайные числа, после чего выведет их на экран и зависнет(как раз при вызове сортировки. )

3)я запустил этот же файл в Turbo C++.
Как и в VS он предложил мне ввести количество записей которые я хочу добавить в список. После ввода он случайным образом записывает их в список и выводит, А при вызове сортировки он виснет(та же самая проблема)

4) Вы говорили что надо освобождать память из под списка, а в предложенном вами варианте деструктор отсутствует. В таком случае возникает вопрос, зачем он нужен был(если мы его не используем)

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

И для чего она вообще нужна(директива stdafx.h)?

[Stilet]

и зависнет(как раз при вызове сортировки. )

Вот твоя задача выяснить почему зависает. Заодно познакомишься с методами пошаговой отладки.

а в предложенном вами варианте деструктор отсутствует.

Правильно. Я всего лишь поправил твой код, но не собираюсь за тебя все делать как двое из ларца. Если ты используешь классы и объекты хорошим тоном будет не только их правильное создание, а и то о чем ты не позаботился - освобождение памяти - это тоже рекомендую изучить самостоятельно, ибо только на своих ошибках можно чему-то научится.

И для чего она вообще нужна(директива stdafx.h)?

Это всего лишь хеадер для :

// stdafx.h: включаемый файл для стандартных системных включаемых файлов
// или включаемых файлов для конкретного проекта, которые часто используются, но
// не часто изменяются

VS любит его, а у меня рука не поднимается от него избавляться