Форум программистов, компьютерный форум CyberForum.ru

Swap для двунаправленного списка - C++

Восстановить пароль Регистрация
 
sd710
1 / 1 / 0
Регистрация: 19.12.2012
Сообщений: 23
19.03.2014, 11:41     Swap для двунаправленного списка #1
Поменять просто значения узлов, не интересно. Я запутываюсь с ссылками. элементы могут быть заглавными или последними.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct node
{
    int k;
    node *next;
    node *pred;
};
 
typedef node* pnode;
...
 
void swap(pnode &a, pnode &b)
{
  ....
}

собственно нужна помощь, подскажите алгоритм.
(а вообще этот swap нужен для реализации сортировки вставками =) )
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.03.2014, 11:41     Swap для двунаправленного списка
Посмотрите здесь:

Сортировка двунаправленного списка C++
C++ Сортировка двунаправленного линейного списка по алгоритму Хоара
C++ Метод списка swap, который меняет информацию двух узлов местами
C++ Реализовать классы фигур и поместить в контейнер на основе двунаправленного линейного списка
Вложенные структуры. Ошибка с создании вложенного двунаправленного списка C++
C++ Сортировка двунаправленного списка
C++ Нахождение и изменение элемента двунаправленного кольцевого списка
C++ Удаление из двунаправленного списка

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kupnu4
26 / 26 / 9
Регистрация: 03.05.2013
Сообщений: 71
19.03.2014, 12:42     Swap для двунаправленного списка #2
попробуйте так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void swap(pnode &a, pnode &b)
{
     pnode tmp_b = b->next;
     pnode tmp_a = a->next;
     b->next = a->next;
     a->next = tmp_b;
     if(tmp_b)
          tmp_b->pred = a;
     if(tmp_a)
          tmp_a->pred = b;
     tmp_b = b->pred;
     tmp_a = a->pred;
     b->pred = a->pred;
     a->pred = tmp_b;
     if(tmp_b)
          tmp_b->next = a;
     if(tmp_a)
          tmp_a->next = b;
}
длинно и может не очень красиво, но это первое, что пришло в голову. я не проверял рабочесть кода, но думаю это или что-то близкое к нему должно помочь вам.(если уж так сильно хочется менять ссылки). а вообще программист должен быть ленивым и реализовывать тот метод, который быстрее и проще.
sd710
1 / 1 / 0
Регистрация: 19.12.2012
Сообщений: 23
20.03.2014, 11:14  [ТС]     Swap для двунаправленного списка #3
Тут та же ошибка, что у меня, теряется кусок списка лежащий между элементами, которые нужно поменять местами;
Появилась идея сделать обмен таким образом:
1) протолкнуть первый элемент A по списку вперед (до элемента B с которым его надо менять) меняя местами с соседним элементом.
2) поменять два соседних элемента A и B (это как раз те заданные)
3) вернуть B на место A;

Но что-то это тоже не получается реализовать.

Кто, что может предложить?
Yandex
Объявления
20.03.2014, 11:14     Swap для двунаправленного списка
Ответ Создать тему
Опции темы

Текущее время: 15:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru