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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 54, средняя оценка - 4.94
VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
#1

Односвязный список. Поменять местами элементы - C++

01.06.2011, 22:05. Просмотров 7507. Ответов 28
Метки нет (Все метки)

Привет. Есть односвязный список. Например: 5 элементов, поменять местами 2 и 3
Как поменять местами элементы p1 и p2.
Что я сделал?
нашел позиции этих p1 и p2 через циклы.
Как поменять? Я думаю, что нужно поменять указатели, как конкретно их поменять?
Что на что должно указывать? Напишите кодом, пожалуйста.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void list::change(int first,int last) {
 
    nodes *p1 = new nodes;
    nodes *p2 = new nodes;
    nodes *tmp_pos = new nodes;
 
    p1 = begin;
    p2 = begin;
    tmp_pos = begin;
 
    for(int i = 1; i < first; i++) {
        p2 = p2->next;
    }
    for(int i = 1; i < last; i++) {
        p1 = p1->next;
    }
    p2->data.vivod(); printf("\n");
    p1->data.vivod(); printf("\n");
 
 
    tmp_pos->next = p1->next;
    p1->next = p2->next;
    p2->next = tmp_pos->next;
 
    delete tmp_pos;
}
мой нерабочий вариант

Добавлено через 2 минуты
Нерабочий почему? потому что запуска такой функции и вывода на экран список не выводится, вернее выводится через *опу!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.06.2011, 22:05     Односвязный список. Поменять местами элементы
Посмотрите здесь:
C++ Односвязный список, поменять местами элементы (максимальный и последний)
Односвязный список (псевдокод) - поменять два элемента местами (посмотреть, правильно ли написан код) C++
C++ Создать динамический список, поменять местами последний и первый элементы списка, предпоследний и второй и т.д.
C++ Однонаправленный список типа "Очередь". Поменять элементы местами
Задали односвязный линейный список с целыми числами. Создать новый список, который содержит элементы заданного списка в обратном порядке C++
Некорректно удаляет элементы(односвязный список) C++
C++ Реализовать односвязный список, элементы которого содержат целые числа
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
01.06.2011, 22:13     Односвязный список. Поменять местами элементы #2
Из кода не совсем понятно, что такое begin? Указатель на первый элемент?
Далее, изменяться должны только ссылки (указатели) на следующие элементы, никакие новые узлы тут не создаются, так что никаких new и delete здесь быть не должно.
Непонятно почему циклы с единицы начинаются.

В общем попробую набросать пример.
VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
01.06.2011, 22:17  [ТС]     Односвязный список. Поменять местами элементы #3
Попробуйте свой вариант, а я его разберу.
begin собственно начало.
циклы с 1 чтобы не проскакивать нужный элемент.
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
01.06.2011, 22:20     Односвязный список. Поменять местами элементы #4
Вообще-то надо найти не сами элементы, а предыдущие для них, так что цикл пусть останется с единицы
Но тогда особым образом надо обрабатывать начальный элемент (здесь не привожу)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void list::change(int first,int last) {
 
        nodes *p1, *p2, *tmp_pos;
 
        p1 = begin;
        p2 = begin;
 
        for(int i = 1; i < first; i++) {
                p2 = p2->next;
        }
        for(int i = 1; i < last; i++) {
                p1 = p1->next;
        }
        p2->data.vivod(); printf("\n");
        p1->data.vivod(); printf("\n");
 
        tmp_pos = p1->next;
        p1->next = p2->next;
        p2->next = tmp_pos;
}
Не проверял
VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
01.06.2011, 22:23  [ТС]     Односвязный список. Поменять местами элементы #5
Ваш вариант, список выводится, но таким образом:
был 1 2 3 4 5
стал 1 2 4 5

Добавлено через 26 секунд
Да именно поэтому цикл начинался с еденицы
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
01.06.2011, 22:23     Односвязный список. Поменять местами элементы #6
Хотя так тоже не должно работать. В общем надо немного подумать, а то опять неправильно получится
VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
01.06.2011, 22:26  [ТС]     Односвязный список. Поменять местами элементы #7
Кстати чтобы найти элемент предыдущий заменяемому и заменителю надо цикл делать i = 1; i < first-1; и так же с ласт.
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
01.06.2011, 22:27     Односвязный список. Поменять местами элементы #8
не спеши. подумай еще. создание таких списков хорошо приучает к работе с указателями. я когда делал двусвязный список и процедуры сортировки и реверса к нему - на бумаге рисовал - помогает
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
01.06.2011, 22:29     Односвязный список. Поменять местами элементы #9
Перестановка двух элементов в общем случае изменяет 4 связи, или 3 связи если элементы смежные.
VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
01.06.2011, 22:30  [ТС]     Односвязный список. Поменять местами элементы #10
А вот хрен! Нарисовал я на бумаге, не понимаю я как)))) ну в упор не понимаю что на что поменять)

я уже делаю 3ю работу где то на списке и проблемы везде где нужно что-то на что-то менять.

Добавлено через 35 секунд
Односвязный список.
По одной связи меняют.
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
01.06.2011, 22:42     Односвязный список. Поменять местами элементы #11
Я цифры для односвязного и написал
Пробуй так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void list::change(int first,int last) {
        nodes *p1, *prev_p1, *p2, *prev_p2, *tmp_pos;
 
        prev_p1 = begin;
        prev_p2 = begin;
 
        for(int i = 1; i < first; i++) {
                prev_p2 = prev_p2->next;
        }
        p1 = prev_p1->next;
        for(int i = 1; i < last; i++) {
                prev_p1 = prev_p1->next;
        }
        p2 = prev_p2->next;
 
        p2->data.vivod(); printf("\n");
        p1->data.vivod(); printf("\n");
 
        tmp_pos = p1->next;
        p1->next = p2->next;
        p2->next = tmp_pos
        prev_p1->next = p2;
        prev_p2->next = p1
}
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
01.06.2011, 22:47     Односвязный список. Поменять местами элементы #12
если я правильно понимаю, то односвязный список позволит такую замену только в одном направлении.
например элементы 1-2-3-4-5. поменять местами 3 и 4 можно только двигая вперед 3.

node* tmp = 2->next
node* tmp2 = 4->next;
2->next = 3->next
4->next = tmp;
3->next = tmp2

1-2-4-3-5

как то так.

Добавлено через 3 минуты
это общая мысль. уж кодом думаю ты и сам...оформишь
VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
01.06.2011, 22:50  [ТС]     Односвязный список. Поменять местами элементы #13
Почему не знаю, но после вариант гризлик запустился бесконечный цикл. Программу выключил

Добавлено через 58 секунд
2 Kendler
а 2 тут при чем? каким боком?
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
01.06.2011, 22:51     Односвязный список. Поменять местами элементы #14
а я в циклах там перепутал цифры
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.06.2011, 22:51     Односвязный список. Поменять местами элементы
Еще ссылки по теме:
Поменять местами первый и последний элементы. Все единичные элементы массива заменить нулями C++
Односвязный список (за первым вхождением элемента с заданным значением z добавить все элементы списка В) C++
C++ Поменять местами элементы главной и побочной диагонали матрицы и найти столбцы, элементы которых убывают
C++ Односвязный список. Подсчитать сумму N первых элементов. Удалить эти элементы и вставить в конец списка
Поменять местами элементы C++

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

Или воспользуйтесь поиском по форуму:
VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
01.06.2011, 22:51  [ТС]     Односвязный список. Поменять местами элементы #15
какие именно?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    void list::change(int first,int last) {
        nodes *p1, *prev_p1, *p2, *prev_p2, *tmp_pos;
 
        prev_p1 = begin;
        prev_p2 = begin;
 
        for(int i = 1; i < first; i++) {
                prev_p2 = prev_p2->next;
        }
        p1 = prev_p1->next;
        for(int i = 1; i < last; i++) {
                prev_p1 = prev_p1->next;
        }
        p2 = prev_p2->next;
 
        p2->data.vivod(); printf("\n");
        p1->data.vivod(); printf("\n");
 
        tmp_pos = p1->next;
        p1->next = p2->next;
        p2->next = tmp_pos;
        prev_p1->next = p2;
        prev_p2->next = p1;
}
Yandex
Объявления
01.06.2011, 22:51     Односвязный список. Поменять местами элементы
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru