struct Node{
int data_birth;
string family;
Node *next;
Node *prev;
};
Указатели в связных списках [C++]
Здравствуйте уважаемые форумчане.
Задача - обменять местами элементы двухсвязного списка. Рассматриваем случай, когда меняем первый элемент в списке со вторым, причем второй не последний.
Узел списка объявляю так:
Функция обмена вот:
На бумаге раза три эту функцию прорисовывал, все связи должны вставать нормально, но откомпилированая программа циклично выводит только 2-й и 3-й элемент, после применения этой функции.
Где в моей функции содержится ошибка, подскажите пожалуйста.
Задача - обменять местами элементы двухсвязного списка. Рассматриваем случай, когда меняем первый элемент в списке со вторым, причем второй не последний.
Узел списка объявляю так:
Код:
Функция обмена вот:
Код:
void change_elem(Node **elem, Node **pbeg)
// elem - элемент, который меняем
// pbeg - адрес головы списка
{
Node *tmp = (*elem);
if( (*elem)->prev == NULL && ( (*elem)->next)->prev != NULL )
{
(*elem)->prev = (*elem)->next;
(*elem)->next = ( (*elem)->next )->next;
( ( (*elem)->next)->next)->next = ( (*elem)->next)->prev;
( (*elem)->next)->next = ( (*elem)->next)->prev;
( (*elem)->next)->prev = tmp->prev;
(*pbeg) = tmp->next;
}
}
// elem - элемент, который меняем
// pbeg - адрес головы списка
{
Node *tmp = (*elem);
if( (*elem)->prev == NULL && ( (*elem)->next)->prev != NULL )
{
(*elem)->prev = (*elem)->next;
(*elem)->next = ( (*elem)->next )->next;
( ( (*elem)->next)->next)->next = ( (*elem)->next)->prev;
( (*elem)->next)->next = ( (*elem)->next)->prev;
( (*elem)->next)->prev = tmp->prev;
(*pbeg) = tmp->next;
}
}
На бумаге раза три эту функцию прорисовывал, все связи должны вставать нормально, но откомпилированая программа циклично выводит только 2-й и 3-й элемент, после применения этой функции.
Где в моей функции содержится ошибка, подскажите пожалуйста.
Ты менять должен не элементы местами а связи между ними
Для односвязного:
для двусвязного списка
Написал для 2 -х списков чтобы понятно было как что. На самом деле все очень просто, рисунки в подарок :)
Для односвязного:
Код:
elem=pbeg;
node *buf=NULL,*ptr=NULL;
buf=elem->next;//следующий элемент(как бы 2-й)
if(elem==pbeg)
if(buf->next!=NULL)
{
ptr=buf->next;//следующий после следующего(ну как бы 3-й)
buf->next=elem;
elem->next=ptr;
pbeg=buf;
}
node *buf=NULL,*ptr=NULL;
buf=elem->next;//следующий элемент(как бы 2-й)
if(elem==pbeg)
if(buf->next!=NULL)
{
ptr=buf->next;//следующий после следующего(ну как бы 3-й)
buf->next=elem;
elem->next=ptr;
pbeg=buf;
}
для двусвязного списка
Код:
elem=pbeg;
node *buf1=NULL,*buf2=NULL;
buf1=elem->next;//следующий элемент(как бы 2-й)
if(elem==pbeg)
if(buf1->next!=NULL)
{
buf2=buf1->next;//следующий после следующего(ну как бы 3-й) elem->prev=buf1;
buf1->prev=NULL;
elem->next=buf2;
buf1->next=elem;
buf2->prev=elem;
pbeg=buf1;
}
node *buf1=NULL,*buf2=NULL;
buf1=elem->next;//следующий элемент(как бы 2-й)
if(elem==pbeg)
if(buf1->next!=NULL)
{
buf2=buf1->next;//следующий после следующего(ну как бы 3-й) elem->prev=buf1;
buf1->prev=NULL;
elem->next=buf2;
buf1->next=elem;
buf2->prev=elem;
pbeg=buf1;
}
Цитата: Apach47
Код:
void change_elem(Node **elem, Node **pbeg)
// elem - элемент, который меняем
// pbeg - адрес головы списка
{
Node *tmp = (*elem);
if( (*elem)->prev == NULL && ( (*elem)->next)->prev != NULL )
{
(*elem)->prev = (*elem)->next;
(*elem)->next = ( (*elem)->next )->next;
[COLOR="Green"]//Начиная с этой строчки вы запутались, т.к. (*elem)->next уже указывает на третий элемент.[/COLOR]
[COLOR="Red"]( ( (*elem)->next)->next)->next = ( (*elem)->next)->prev;[/COLOR]
[COLOR="Green"]//Сначала необходимо выполнить следующие 2 строчки, а потом уже предыдущую. [/COLOR]
( (*elem)->next)->next = ( (*elem)->next)->prev;
( (*elem)->next)->prev = tmp->prev;
(*pbeg) = tmp->next;
}
}
// elem - элемент, который меняем
// pbeg - адрес головы списка
{
Node *tmp = (*elem);
if( (*elem)->prev == NULL && ( (*elem)->next)->prev != NULL )
{
(*elem)->prev = (*elem)->next;
(*elem)->next = ( (*elem)->next )->next;
[COLOR="Green"]//Начиная с этой строчки вы запутались, т.к. (*elem)->next уже указывает на третий элемент.[/COLOR]
[COLOR="Red"]( ( (*elem)->next)->next)->next = ( (*elem)->next)->prev;[/COLOR]
[COLOR="Green"]//Сначала необходимо выполнить следующие 2 строчки, а потом уже предыдущую. [/COLOR]
( (*elem)->next)->next = ( (*elem)->next)->prev;
( (*elem)->next)->prev = tmp->prev;
(*pbeg) = tmp->next;
}
}
навскидку надо так:
Код:
if( (*elem)->prev == NULL && ( (*elem)->next)->prev != NULL )
{
(*elem)->prev = (*elem)->next;
( (*elem)->next)->next = ( (*elem)->next)->prev;
( (*elem)->next)->prev = tmp->prev;
(*elem)->next = ( (*elem)->next )->next;
( ( (*elem)->next)->prev = tmp;
(*pbeg) = tmp->next;
}
}
{
(*elem)->prev = (*elem)->next;
( (*elem)->next)->next = ( (*elem)->next)->prev;
( (*elem)->next)->prev = tmp->prev;
(*elem)->next = ( (*elem)->next )->next;
( ( (*elem)->next)->prev = tmp;
(*pbeg) = tmp->next;
}
}
cronya, то что связи менять это я знаю, вот только понять не могу, разве набирая в коде [COLOR="Blue"]elem->next[/COLOR] я сразу перехожу на следующий за [COLOR="blue"]elem[/COLOR] элемент? Разве я не получаю этой инструкцией только его адрес?
Видимо не знаете что такое указатель в принципе и как он устроен :) Это очень печально.
Смотрите вложение там все понятно расписано.
Совет: Разобраться как работают сначала односвязные списки, так как без них вы не поймете как работают 2-связные. Впрочем так и получилось. :) Да, кстати, надо разбираться не в коде а в алгоритме самом
Смотрите вложение там все понятно расписано.
Цитата: Apach47
Разве набирая в коде [COLOR="Blue"]elem->next[/COLOR] я сразу перехожу на следующий за [COLOR="blue"]elem[/COLOR] элемент? Разве я не получаю этой инструкцией только его адрес?
Вы работаете с памятью:
elem - указатель на память, где хранится ваши данные
next - указатель на указатель(он указывает что поэтому адресу хранится указатель на память, где ваши данные)
Надо знать как вы создавали список,а вы получается не знаете как он создан.
Пример:
Код:
struct node//это все структура данных для каждого элемента
{
даные;
node *next;//указатель на следующий элемент
};
int main()
{
node *pbeg;//указатель на голову
node *elem;//указатель на текущий элемент
node *temp;//доп указатель для служебных целей
pbeg=elem=temp=NULL;
elem=new node;//память выделили
elem->date=ваши_данные_вводите;//ввели данные
elem->next=NULL;//связь на следующий элемент, при 1 элементе она равна 0, так как нету следующего
pbeg=temp=elem;//так как он только первый 1, значит он глава
for(int idx=0; idx<9; idx++)
{
elem=new node;
elem->date=ваши_данные_вводите;
elem->next=temp;//temp указывает на главу, значит на 1 элемент,которому выделяли память в 10 строке и т.д.
temp=elem;//сохраняем указатель на текущий элемент(2,3,..., n), он как бы всегда будет головой
}
pbeg=temp;//ну и голове указываем последний введенный элемент, т.е. голову
return 0;
}
{
даные;
node *next;//указатель на следующий элемент
};
int main()
{
node *pbeg;//указатель на голову
node *elem;//указатель на текущий элемент
node *temp;//доп указатель для служебных целей
pbeg=elem=temp=NULL;
elem=new node;//память выделили
elem->date=ваши_данные_вводите;//ввели данные
elem->next=NULL;//связь на следующий элемент, при 1 элементе она равна 0, так как нету следующего
pbeg=temp=elem;//так как он только первый 1, значит он глава
for(int idx=0; idx<9; idx++)
{
elem=new node;
elem->date=ваши_данные_вводите;
elem->next=temp;//temp указывает на главу, значит на 1 элемент,которому выделяли память в 10 строке и т.д.
temp=elem;//сохраняем указатель на текущий элемент(2,3,..., n), он как бы всегда будет головой
}
pbeg=temp;//ну и голове указываем последний введенный элемент, т.е. голову
return 0;
}
Совет: Разобраться как работают сначала односвязные списки, так как без них вы не поймете как работают 2-связные. Впрочем так и получилось. :) Да, кстати, надо разбираться не в коде а в алгоритме самом
Цитата: Apach47
cronya, то что связи менять это я знаю, вот только понять не могу, разве набирая в коде [COLOR="Blue"]elem->next[/COLOR] я сразу перехожу на следующий за [COLOR="blue"]elem[/COLOR] элемент? Разве я не получаю этой инструкцией только его адрес?
Товарищ cronya вас абсолютно запутал.
Если у вас сам список объявлен как указатель на структуру Node,
и в функцию вы передаете адреса указателей,
то внутри функции операция (*elem)->prev получает адрес предыдущего объекта.
Дабы поверить всему, что я наговорил, открываем отладчик и внимательно созерцаем увиденное.
Код:
Node *elem0 = new Node;
...
change_elem(&elem0,&elem0); // меняем первый элемент со вторым
//внутри функции любым образом смотрите содержимое (*elem)->next
...
change_elem(&elem0,&elem0); // меняем первый элемент со вторым
//внутри функции любым образом смотрите содержимое (*elem)->next
А то что я вчера написал, исправляет не все ошибки, поэтому проще всего использовать несколько временных указателей, для первого, второго и третьего объектов например, чтобы точно быть уверенным что ошибки нет.
так, относительная ясность появилась. z0rch и cronya, спасибо