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

@VladSharikov · Регистрация: 02.12.2010

Студворк — интернет-сервис помощи студентам

Привет. Есть односвязный список. Например: 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 минуты
Нерабочий почему? потому что запуска такой функции и вывода на экран список не выводится, вернее выводится через *опу!

@grizlik78 · 01.06.2011, 22:13

Из кода не совсем понятно, что такое begin? Указатель на первый элемент?
Далее, изменяться должны только ссылки (указатели) на следующие элементы, никакие новые узлы тут не создаются, так что никаких new и delete здесь быть не должно.
Непонятно почему циклы с единицы начинаются.

В общем попробую набросать пример.

@VladSharikov · 01.06.2011, 22:17 **[ТС]**

Попробуйте свой вариант, а я его разберу.
begin собственно начало.
циклы с 1 чтобы не проскакивать нужный элемент.

@grizlik78 · 01.06.2011, 22:20

Вообще-то надо найти не сами элементы, а предыдущие для них, так что цикл пусть останется с единицы

Но тогда особым образом надо обрабатывать начальный элемент (здесь не привожу)

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 · 01.06.2011, 22:23 **[ТС]**

Ваш вариант, список выводится, но таким образом:
был 1 2 3 4 5
стал 1 2 4 5

Добавлено через 26 секунд
Да именно поэтому цикл начинался с еденицы

@grizlik78 · 01.06.2011, 22:23

Хотя так тоже не должно работать. В общем надо немного подумать, а то опять неправильно получится

@VladSharikov · 01.06.2011, 22:26 **[ТС]**

Кстати чтобы найти элемент предыдущий заменяемому и заменителю надо цикл делать i = 1; i < first-1; и так же с ласт.

@AzaKendler · 01.06.2011, 22:27

не спеши. подумай еще. создание таких списков хорошо приучает к работе с указателями. я когда делал двусвязный список и процедуры сортировки и реверса к нему - на бумаге рисовал - помогает

@grizlik78 · 01.06.2011, 22:29

Перестановка двух элементов в общем случае изменяет 4 связи, или 3 связи если элементы смежные.

@VladSharikov · 01.06.2011, 22:30 **[ТС]**

А вот хрен! Нарисовал я на бумаге, не понимаю я как)))) ну в упор не понимаю что на что поменять)

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

Добавлено через 35 секунд
Односвязный список.
По одной связи меняют.

@grizlik78 · 01.06.2011, 22:42

Я цифры для односвязного и написал
Пробуй так

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 · 01.06.2011, 22:47

если я правильно понимаю, то односвязный список позволит такую замену только в одном направлении.
например элементы 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 · 01.06.2011, 22:50 **[ТС]**

Почему не знаю, но после вариант гризлик запустился бесконечный цикл. Программу выключил

Добавлено через 58 секунд
2 Kendler
а 2 тут при чем? каким боком?

@grizlik78 · 01.06.2011, 22:51

а я в циклах там перепутал цифры

@VladSharikov · 01.06.2011, 22:51 **[ТС]**

какие именно?

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;
}

@grizlik78 · 01.06.2011, 22:52

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;
        }
        p2 = prev_p2->next;
        for(int i = 1; i < last; i++) {
                prev_p1 = prev_p1->next;
        }
        p1 = prev_p1->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 · 01.06.2011, 22:52

ну 2 содержит в себе указатель на 3, этот указатель мы меняем на 4. вобщем постарайся вникнуть в сссссуть

@grizlik78 · 01.06.2011, 22:53

ну в цикле в первом двигается prev_p2 а использовался после цикла prev_p1 и наоборот

@VladSharikov · 01.06.2011, 22:54 **[ТС]**

2 Kendler
дак если нам надо не 3 на 4 а 100 на 1000 ? менять тысячу указателей?
2 гризлик
а да я это увидел - поменял.
не важно . всеравно бесконечный цикл.

то есть меняет все нормально, но при выводе - бесконечный цикл.

@AzaKendler · 01.06.2011, 22:57

под конкретный случай и свои циклы ты напиши сам. а смысл таков что 2 должен иметь next 4
4 должен иметь next 3 а 3 должен иметь next 5. и тогда будет 1-2-4-3-5.

Добавлено через 1 минуту
тебе надо поменять например элемент 100 местами с элементов 456?

бери в оборот 99->next 100->next 455->next 456->next. схема та же

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	01.06.2011, 22:13
	Из кода не совсем понятно, что такое begin? Указатель на первый элемент? Далее, изменяться должны только ссылки (указатели) на следующие элементы, никакие новые узлы тут не создаются, так что никаких new и delete здесь быть не должно. Непонятно почему циклы с единицы начинаются. В общем попробую набросать пример. 0

@VladSharikov 25 / 25 / 7 Регистрация: 02.12.2010 Сообщений: 824
	01.06.2011, 22:17 [ТС]
	Попробуйте свой вариант, а я его разберу. begin собственно начало. циклы с 1 чтобы не проскакивать нужный элемент. 0

@VladSharikov 25 / 25 / 7 Регистрация: 02.12.2010 Сообщений: 824
	01.06.2011, 22:23 [ТС]
	Ваш вариант, список выводится, но таким образом: был 1 2 3 4 5 стал 1 2 4 5 Добавлено через 26 секунд Да именно поэтому цикл начинался с еденицы 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	01.06.2011, 22:23
	Хотя так тоже не должно работать. В общем надо немного подумать, а то опять неправильно получится 0

@VladSharikov 25 / 25 / 7 Регистрация: 02.12.2010 Сообщений: 824
	01.06.2011, 22:26 [ТС]
	Кстати чтобы найти элемент предыдущий заменяемому и заменителю надо цикл делать i = 1; i < first-1; и так же с ласт. 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	01.06.2011, 22:27
	не спеши. подумай еще. создание таких списков хорошо приучает к работе с указателями. я когда делал двусвязный список и процедуры сортировки и реверса к нему - на бумаге рисовал - помогает 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	01.06.2011, 22:29
	Перестановка двух элементов в общем случае изменяет 4 связи, или 3 связи если элементы смежные. 0

@VladSharikov 25 / 25 / 7 Регистрация: 02.12.2010 Сообщений: 824
	01.06.2011, 22:30 [ТС]
	А вот хрен! Нарисовал я на бумаге, не понимаю я как)))) ну в упор не понимаю что на что поменять) я уже делаю 3ю работу где то на списке и проблемы везде где нужно что-то на что-то менять. Добавлено через 35 секунд Односвязный список. По одной связи меняют. 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	01.06.2011, 22:47
	если я правильно понимаю, то односвязный список позволит такую замену только в одном направлении. например элементы 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 минуты это общая мысль. уж кодом думаю ты и сам...оформишь 0

@VladSharikov 25 / 25 / 7 Регистрация: 02.12.2010 Сообщений: 824
	01.06.2011, 22:50 [ТС]
	Почему не знаю, но после вариант гризлик запустился бесконечный цикл. Программу выключил Добавлено через 58 секунд 2 Kendler а 2 тут при чем? каким боком? 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	01.06.2011, 22:51
	а я в циклах там перепутал цифры 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	01.06.2011, 22:52
	ну 2 содержит в себе указатель на 3, этот указатель мы меняем на 4. вобщем постарайся вникнуть в сссссуть 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	01.06.2011, 22:53
	ну в цикле в первом двигается prev_p2 а использовался после цикла prev_p1 и наоборот 0

@VladSharikov 25 / 25 / 7 Регистрация: 02.12.2010 Сообщений: 824
	01.06.2011, 22:54 [ТС]
	2 Kendler дак если нам надо не 3 на 4 а 100 на 1000 ? менять тысячу указателей? 2 гризлик а да я это увидел - поменял. не важно . всеравно бесконечный цикл. то есть меняет все нормально, но при выводе - бесконечный цикл. 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	01.06.2011, 22:57
	под конкретный случай и свои циклы ты напиши сам. а смысл таков что 2 должен иметь next 4 4 должен иметь next 3 а 3 должен иметь next 5. и тогда будет 1-2-4-3-5. Добавлено через 1 минуту тебе надо поменять например элемент 100 местами с элементов 456? бери в оборот 99->next 100->next 455->next 456->next. схема та же 0