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

Доброго времени Tequilla!
не мог пройти мимо вашего сообщени даже на сайте зарегился :)) сам когда-то подобное писал, но в большинстве случаев я ответы находил быстрее чем отвечали форумах. Ладно к делу.
На первый взгляд видно что увас список и объекты списка описываются одним и темже классом, что ниесть гуд (за исключением случая когда вы хотите создать список списков %-) ) т.к. вы обязательно запутаетесь где вы должны работать со списком а где с элементом списка, возможно так и произошло, сейчас попробую поправить сие.

Спасибо, я был бы вам признателен, поскольку отлаживаю я плоховато :(
А причина ошибки толком не понятна :(

я так понял что вы под Борландом работаете?? я под Визуалом, у меня следующее компилится на ура. вы уж извините но я поленился отлаживать Ваш код, а точнее вашу хитрую функцию сортировки поэтому написал свою под звучным названием Sort2

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

using namespace std;

//---------------------------------------------------------------------------
#pragma argsused
//================================================== =========
struct NODE_DLIST
{
int value;
NODE_DLIST *next;
NODE_DLIST *prev;
void _null()
{
value=0;
next=NULL;
prev=NULL;
}
};
class DLIST
{
public:

NODE_DLIST *beg; // = head
NODE_DLIST *end; // = end
//================================================== ===========
DLIST() //конструктор
{
beg = NULL;
end = NULL;
}
~DLIST()
{
NODE_DLIST *ptr, *temp;
for(ptr = beg; ; )
{
temp = ptr->next;
delete ptr;
ptr = temp;
if(ptr == end)
{
delete ptr;
break;
}
}

}
//================================================== ============
void MakeDList() //описание и создание Двусвязного списка
{
NODE_DLIST *rex = new NODE_DLIST;
rex->_null();
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;
}

NODE_DLIST *rex = beg;
while(rex)
{
cout<<rex->value<<"\t";
if(rex->next!=NULL)
rex = rex->next;
else break;
}
}//end of printing aunction
//================================================== ============
void Sort2()
{
if(beg==end) return; // если в списке 0 или 1 элемент то выходим

NODE_DLIST *i=beg;
while(i->next!=NULL)
{
if(i->value > i->next->value)
{
int temp=i->value;
i->value=i->next->value;
i->next->value=temp;

while(i->prev!=NULL)
{
if(i->value < i->prev->value)
{
int temp=i->value;
i->value=i->prev->value;
i->prev->value=temp;
}
i=i->prev;
}
}
i=i->next;
}
}
void Sort()
{

NODE_DLIST *SmallElement;
NODE_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<<"Printing DList:"<<endl;
L->ShowDList();

cout<<endl<<"Sort run"<<endl;
L->Sort2();
cout<<"Sort end"<<endl;

cout<<"Printing DList after sorting: "<<endl;
L->ShowDList();

cout<<endl<<"Program end"<<endl;
getch();
return 0;
}
//---------------------------------------------------------------------------

Забыл сказать что при сортировке у вас текущий элемент в какой-то момент начинал ссылаться сам на себя и отсюда зацикливание. Переделал код что бы было по феншую ООП(объекто ориентированного программирования) и добавил функцию тестирования.

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

using namespace std;

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

#pragma argsused
//================================================== =========
struct NODE_DLIST
{
int value;
NODE_DLIST *next;
NODE_DLIST *prev;
void _null()
{
value=0;
next=NULL;
prev=NULL;
}
};
class DLIST
{
public:

NODE_DLIST *beg; // = head
NODE_DLIST *end; // = end
//================================================== ===========
DLIST() //конструктор
{
beg = NULL;
end = NULL;
}
~DLIST()
{
NODE_DLIST *ptr, *temp;
for(ptr = beg; ; )
{
temp = ptr->next;
delete ptr;
ptr = temp;
if(ptr == end)
{
delete ptr;
break;
}
}

}
//================================================== ============
void MakeDList(int i) //описание и создание Двусвязного списка
{
NODE_DLIST *rex = new NODE_DLIST;
rex->_null();
rex->value=i;
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;
}

NODE_DLIST *rex = beg;
while(rex)
{
cout<<rex->value<<"\t";
if(rex->next!=NULL)
rex = rex->next;
else break;
}
}//end of printing aunction



//================================================== ============
void Sort2()
{
if(beg==end) return; // если в списке 0 или 1 элемент то выходим

NODE_DLIST *i=beg;
while(i->next!=NULL)
{
if(i->value > i->next->value)
{
int temp=i->value;
i->value=i->next->value;
i->next->value=temp;

while(i->prev!=NULL)
{
if(i->value < i->prev->value)
{
int temp=i->value;
i->value=i->prev->value;
i->prev->value=temp;
}
i=i->prev;
}
}
i=i->next;
}
}
void Sort()
{

NODE_DLIST *SmallElement;
NODE_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
//================================================== ============
void Test()
{
cout<<"Test run"<<endl;
const int MAX_RAND=10;//максимально возможное случайное число
const int MAX_LEN_RAND=7;//количество случайных элементов

srand(time(0));// сбрасываем генератор случайных чисел
// что бы он у нас все время герерировал разные значения

DLIST *L=new DLIST;

for(int i=0;i<MAX_LEN_RAND;i++)
{
L->MakeDList(rand() % MAX_RAND);//генерируем случайное число [0, MAX_RAND)
}

L->ShowDList();
cout<<endl;
L->Sort2();
L->ShowDList();
cout<<endl<<"Test end"<<endl<<endl;
}
int main(int argc, char* argv[])
{
for(int i=0;i<15;i++)
{
Test();
for(int j=0;j<0xfffffff;j++); //замедлялка, а то у меня на компе все
//слишком быстро и случайные значениякоторые зависят от текущего времени
//просто не успевают генерироваться
}
/*
DLIST *L;
L = new DLIST;



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

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

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

cout<<endl<<"Sort run"<<endl;
L->Sort2();
cout<<"Sort end"<<endl;

cout<<"Printing DList after sorting: "<<endl;
L->ShowDList();

cout<<endl<<"Program end"<<endl;
*/
getch();
return 0;
}

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

в моем коде идет сравнение значений и изменение значений, могу сделать изменение адрессов если надо

как я понимаю изменение адресов - это тоже самое , что и изменение связей между элементами списка? так?
о_0)) Идея с тестированием - просто изумительная , никогда не задумывался о таком(а наверно стоило бы)))

Что касается самой сортировки, то тут нужен обмен вот этими адресами, в них то я видимо и накосячил. :(

рад что вы находите в программировании для себя что то новое. могу поинтресоваться лабораторку делаем или мир пытаемся пороботить двухсвязными списками :))))))
добавил новые функции как говорится не нужное закоментировать

void Chahge_Node(NODE_DLIST *node1,NODE_DLIST *node2)
{
NODE_DLIST temp=*node1,node1_old=*node1,node2_old=*node2;

node1_old=node2_old;
node2_old=temp;
}
void Chahge_Value(NODE_DLIST *node1,NODE_DLIST *node2)
{
int temp=node1->value;
node1->value=node2->value;
node2->value=temp;
}
void Change_Addr(NODE_DLIST *node1,NODE_DLIST *node2)
{
if(node1==NULL || node2==NULL)return;

NODE_DLIST *node0=node1->prev,
*node3=node2->next;

node1->next=node3;
node1->prev=node2;
node2->next=node1;
node2->prev=node0;

if(node0!=NULL) node0->next=node2;
if(node3!=NULL) node3->prev=node1;
}
void Sort3()
{
if(beg==end) return; // если в списке 0 или 1 элемент то выходим

NODE_DLIST *i=beg;
while(i->next!=NULL)
{
if(i->value > i->next->value)
{
//Chahge_Node(i,i->next);
Chahge_Value(i,i->next);
//Change_Addr(i,i->next);

while(i->prev!=NULL)
{
if(i->value < i->prev->value)
{
//Chahge_Node(i,i->next);
Chahge_Value(i,i->next);
//Change_Addr(i,i->next);
}
i=i->prev;
}
}
i=i->next;
}
}

Ого го ... Похоже я сейчас запутаюсь с двухсвязным списком еще больше))))))
ДА вы правы-это лабораторная работа, но делая ее мы и познаем Мир)) не правда ли?)

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

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

чето форум глючит

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

при сортировке возникает момент когда надо менять элементы списка, это можно делать изменением значений, адрессов(на которые ссылаются элементы) или заменой самих элементов. все три способа я вам написал Chahge_Node, Chahge_Value, Change_Addr.

Да, но ведь сортировка выбором относится к какому-то из этих 3х вариантов(правда я не знаю к какому, к медленны или к быстрым?)

Что касается обмена адресами, то тут я могу лишь сказать , что нас учили так, как было представлено в первоначальном моем варианте(т.е. переставлять связи на соседние элементы так, затем иначе, писать куча исключительных ситуаций, когда переставляемый элемент является первым, когда он является последним и тд). Других вариантов увы я не знаю.

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

быстрая или медленная сортировка это субъективные оценки в зависимости от ситуации, бывает одно сортировать лучше одним а другое другим, о сортировках можно почитать в "теории алгоритмов" или в книжке "жемчужены программирования". А вот сортировку пузырьком советую изучить (это наше все!! :) )

поверте я до этого тоже не сразу дошел, возьмите карандаш с листком и начертите начальное состаяние(до сортировки) и конечное состаяние (после сортировки) и все будет просто и легко видно, дерзайте!!

уж поверьте я ни один листок уже исписал))))

Позвольте задать вопрос: вот этот метод сортировки(который вы описали)- если я не ошибаюсь это же пузырек?

а так писаь пробывали:
назв. до после
node1_next node3 node2
node1_prev node2 node0
node2_next node1 node1
node2_prev node0 node3
node0_next node2 node1
node3_prev node1 node2

все приходит с опытом, уверен и вы в скором времени будите блистать элегантными решениями

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

Сочувствую вам :( меня тоже может ждать та же участь, если я не подчищу за собой хвосты:( А Вы где учились, если не секрет?
Так , теперь осталось применить этот же метод только сортируя методом выбора(иначе не примут, поскольку в задании так и ставилось- по методу выборки)

Задание звучит примерно так:
Отсортировать двухсвязный список по методу выборки(выбора).
При сортировке менять не значения , а связи между элементами двухсвязного списка.



//пример кода для сортировки МАССИВА методом ВЫБОРА
voidSelectSort(int A[], int n)
{
int smallIndex;
int i, j;
for(int i = 0; i < n -1; i++)
{
smallIndex = i;
for(j = i + 1; j < n; j++)
if(A[j] < A[smallIndex])
smallIndex = j;
int temp = A;
A = A[smallIndex];
A[smallIndex] = temp;
}
}

добавьте это должно сработать, потестил вроде все ок

Спасибо) вернусь с Военки обязательно посмотрю)))
я вчера пытался 3-ю функцию сортировки запустить))) либо я вчера уже тупить стал, либо что-то было не так, поскольку при вызоче 2-й сортировки все было ОК.
А когда вызывал 3-ю функцию Sort3() он передавал в нее данные и повис :(

эээ.... вчера тупить я начал т.к. время у меня было два часа ночи, не работают фукции Change_adres и Change_adres2, чет я там с адрессами перемудрил, вечером будет время займусь.

да я тоже на это обратил внимание, что он что то не пашет :(
щас тоже буду пытаться шаманить :)

Ahh... This is a terrible...
на кой черт вообще придумали эти списки? :( у меня к ним уже личная вражда начинается)))

для начала было бы неплохо прокомментировать свой код и добавить его в теги "[ CODE ][/ CODE ]"(есть кнопочка # в расширенном режиме редактирования) чтобы можно было быстрее и лучше разобраться, что у вас написано. А так сидеть гадать чего у вас там за переменные, простите увольте.

Сортировку каким методом делали?

Код:

по правил код наконец то, была ошибка в том что при замене элементов меняются их логические места в списке и если это были элементы начала или конца то элементы начинали оказываться в не границ (beg,end) списка
Tequilla у вас вполне возможно таже проблема, аока исправил сортировку пузырьком сейчас разберусь в сортировкой необходимой вам
з.ы. прошу извинить за "медвежью услугу"

Медвежья услуга? я так не считаю)) у каждого бывают ошибки! у меня их еще больше :( так что не стоит извиняться)))
//-----------------
50bites Спасибо тебе большое! за ВСЕ! особенно за уделенное время и большую дружескую помощь!)