Поменять местами ноды в односвязном списке
Я застрял на применении односвязного списка. Проблема в том, что я не могу понять почему не меняются местами последний и предпоследние элементы списка.
Чтобы поменять первый и последний узлы в односвязном списке, можно три случая рассмотреть:
- меньше двух узлов: вернуть список как есть
- ровно два узла: поменять узлы местами
- больше двух: сделать, чтобы последний узел указывал бы на второй узел, а предпоследний — на первый.
где next_to_last() ищет предпоследний узел:
Это достаточно прямолинейное решение в лоб, возможно есть более элегантный подход.
Поменять местами узлы в односвязном списке
Я пытаюсь поменять местами два узла. Например, если узлы a и b Я передаю указатели
(a-1)->next и (b-1)->next которые в основном являются узлами a и b .
Что я делаю не так? Когда я пытаюсь распечатать узлы после вызова функции, это бесконечный цикл. Пожалуйста помоги.
задан 09 марта ’13, 21:03
Хотя можно осить только данные, если хочешь вместо узла! — Grijesh Chauhan
Там не так много C++, только C. Если вы использовали C++, вы должны использовать std::stack и использовать существующий std::swap вместо. — Some programmer dude
Я думаю, было бы гораздо проще просто поменять местами данные: data_type temp = (*a)->data; (*a)->data = (*b)->data; (*b)->data = temp; — Zeta
@ребята, в чем проблема с моим кодом.. 🙂 — CodeRat
@ us2012- Причина, по которой вы не используете это, заключается в том, что вас просят это понять. Вероятно, это школьный проект, и профессор не позволяет ОП делать это, пока ОП не сделает это сам. Я понимаю аргументы против этого стиля обучения, так как я читал их здесь сотни раз раньше. Это не меняет того факта, что некоторые из нас, включая меня, подвержены этому. Нет правила, согласно которому вы должны использовать STL это просто самый умный поступок. — ChiefTwoPencils
3 ответы
Почему бесконечный цикл?
Бесконечный цикл из-за цикла в вашем списке после вызова swap() функция. В swap() код, следующий за оператором, ошибочен.
Почему?: Поскольку после оператора присваивания в swap() функция temp1 следующий начинает указывать на b узел. А также node[b] следующая точка на себя в цикле. И самостоятельная петля является причиной бесконечная петля, где-то в вашем коде, где вы просматриваете связанный список.
Ниже я нарисовал, чтобы показать, как swap() работает поэтапно. Может быть, это поможет вам понять ваше ошибка:
Вы не упомянули, но я предполагаю, что связанный список имеет следующую связь между a и b : (читать красные комментарии)
(шаг 1):
(шаг 3): Глючное заявление
Видеть (temp1)->next; на самом деле b а ты присваиваешь (*b)->next = (*b) при выполнении (*b)->next = (temp1)->next; следовательно, добавление цикла.
(шаг 4):
Думаю, по схеме вы без труда поймете, какие последние две строчки вашего swap() код делает:
Ниже приведена моя диаграмма для этих двух строк:
(шаг 5): Даже последняя строка вашей функции swap() левая петля, как показано ниже:
Так что петля все еще там two узел так бесконечный цикл.
Как поменять местами два узла в одном связанном списке?
Одним из способов является замена данных узла вместо того, чтобы менять позицию узла в связанном списке (как я прокомментировал ваш вопрос). Но вы хотите поменять узлы положение в списке.
Ну это хорошо! если размер данных узла больше, в этот раз лучше поменять местами положение узла, а не поменять местами данные узла (обмен данными будет плохим выбором)
Потому что у тебя есть односвязный список, чтобы поменять местами любые два произвольных узла в списке, который вы необходимость там адреса предыдущих узлов тоже. (это то, что вы не учитываете в своей логике обмена)
ПОЧЕМУ нужны предыдущие указатели?:
Предположим, что после некоторых успешных операций вставки (вставки) ваш список становится следующим:
Горизонтальная диаграмма. Предположим, ты хочешь поменяться скажем два узла (q) и (p) :
Как я уже сказал, для обмена нам нужны предыдущие указатели. Вам нужно подумать о том, чтобы следовать
(По идее я пишу для конкретных узлов (p) и (q) просто чтобы объяснение было простым. но моя реализация вышла из общего):
В списке предыдущих указателей:
ВНИМАНИЕ: Если вы хотите поменять местами два узла, скажите node[ 9 ] и node[ 6 ] тогда вы должны использовать указатели узлов, предшествующих этим двум узлам.
Например: два обмена node[ 9 ] и [ 6 ] , вам также нужно изменить следующий указатель node[ 0 ] и следующий указатель node[ 2 ] на приведенной выше схеме.
Каким будет список после замены этих двух узлов?
Что сейчас в предыдущих нодах [o] и [2] ?
После замены в списке предыдущие указатели
Итак, если вы хотите поменять местами два узла; там также действует непосредственный предыдущий узел, и поскольку список представляет собой список с одной ссылкой, вам также нужны предыдущие указатели.
Как найти предыдущие указатели узлов?
Предположим, вы хотите поменять местами любые два узла node[p] и node[q] тогда вы можете использовать head pointer чтобы найти предыдущий узел.
Итак, функция обмена синтаксис (В моей реализации) как:
И вы будете вызывать функцию, например:
Определение: (Чтобы понять код, пожалуйста, прочитайте комментарии, которые я добавил почти к каждой строке.)
In swap() вы можете заметить, что я вызываю вспомогательную функцию get_prevnd(, ); . Эта функция возвращает адрес предыдущего узла в списке. В функции get_prevnd(, ); , первый аргумент — это заголовок списка, а второй аргумент — это узел, который вы ищете.
И, к счастью, код РАБОТАЕТ :). Ниже приведена ссылка для онлайн-тестирования этого кода. Я тестировал различные входы.
Как поменять местами позиции двух узлов в односвязном списке, изменяя только указатели?
Я пытаюсь поменять местами два узла односвязного списка с заданными нулями индексами. В моем коде я обрабатываю много случаев, но этот подход действителен только тогда, когда j-i<=2 , Если разница между 3 и более i а также j Я не могу справиться с этим.
Пожалуйста, помогите мне исправить мой подход.
Решение
Основы указателя-жокея для замены узлов в связанном списке просты:
- Найдите в списке указатели, которые указывают на узлы, которые вы хотите поменять местами. Один из этих указателей может быть head указатель, но хотя бы один будет какой-то next указатель в списке. Помните, что это указатели, которые указывают на узлы, которые вы меняете.
- Поменяйте местами эти указатели
- Поменять местами next указатели этих узлов, чтобы восстановить оставшийся порядок в списке.
- Вот и все.
Чтобы достичь этого, самый простой подход заключается в использовании указатели на указатели. Это позволяет избежать необходимости носить с собой prev полностью указатели, что делает алгоритм ужасно более сложным, чем он должен быть.
Ваш подход доблестный, но явно сложный. Придерживайтесь алгоритма, приведенного выше, и это станет намного понятнее, что нужно. Найдите несколько указателей, указывающих на то, что вы хотите поменять, поменяйте местами, а затем поменяйте местами их внутренние следующие указатели.
Учитывая все это, алгоритм реализован следующим образом (сохраняя ваше желание сканировать список только один раз, чтобы найти оба узла для обмена). Комментарии о том, как алгоритм соответствует коду, встроены:
пример
Это не сделало бы справедливости без действующего примера. Далее будет построен упорядоченный список из десяти элементов, пронумерованных 1..10. Затем он использует описанную выше процедуру подстановки с нулевым индексом, чтобы поменять местами различные элементы, в частности что-то, что меняет головной узел, хвостовой узел и некоторые внутренние узлы, а затем отменяет все это, изменяя свопы, чтобы прийти к списку, который мы начали с.
Выход
Резюме
Большинство крайних случаев, которые вы пытаетесь избежать, просто исчезают, если вы помните, что пытаетесь сделать: поменять местами указатели, а не узлы. Хитрость заключается в том, чтобы найти указатели (не их значения; фактические указатели), которые указывают на узлы, которые вы хотите поменять, и поменять значения этих указателей.
Другие решения
Кажется, что вы стараетесь справиться с угловыми случаями, но ваш код все еще не в состоянии справиться с базовыми случаями, и это потому, что вы делаете его сложным.
Попробуйте еще раз проанализировать — что это за задача и каковы требования для ее решения.
Позвольте мне помочь вам : —
- Задача 1 — Нахождение i-го индексного узла и j-го индексного узла путем обхода связанного списка (нет необходимости находить расстояние между ними)
- Задача 2 — Замена обоих узлов
Требования — Чтобы поменять узел, получить доступ к его предыдущему узлу (что кажется вам известным, так как вы пробовали это в своем коде)
Некоторые угловые случаи —
- Если я == j или i> j (управляется вашим кодом)
- Если у i-го узла нет предыдущего узла (т. Е. Он возглавляет связанный список)
Теперь попробуйте проанализировать ваш код.
Для справки смотрите код ниже
Надеюсь, это поможет.
Продолжайте спрашивать, продолжайте расти ��
Вы делаете свою логику свопинга более сложной, чем она должна быть. Попробуйте что-то вроде этого:
Как поменять местами узлы в односвязном списке
При замене соседних узлов переустановка указателей выглядит следующим образом:
При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом: 
При переустановке указателей необходима также проверка, является ли какой-либо из заменяемых узлов корнем списка, поскольку в этом случае не существует узла, предшествующего корневому.
using namespace std;
struct NODE char value;
struct NODE* next;
>;
struct DbCircleList size_t size;
struct NODE* head;
>;
void addNode(DbCircleList* list, char elem)
NODE* newElem = new NODE;
newElem->value = elem;
if (list->size == 0)
list->head = newElem;
list->head->next = list->head;
>
else
struct NODE* temp;
temp = list->head;
list->head = newElem;
newElem->next = temp;
>
++list->size;
>
void printList(DbCircleList* list)
NODE* tmp = list->head;
cout << «List values: » << endl;
for ( int i = 0; i < list->size; ++i)
cout << «Value: » << tmp->value << endl;
tmp = tmp->next;
>
>
int main()
DbCircleList* list = new DbCircleList;
list->size = 0;
list->head = NULL ;
DbCircleList* list1 = new DbCircleList;
list1->size = 0;
list1->head = NULL ;
DbCircleList* list2 = new DbCircleList;
list2->size = 0;
list2->head = NULL ;
delete list;
delete list1;
delete list2;
return 0;
>
#define _CRT_SECURE_NO_WARNINGS
#include <Windows.h>
#include <stdio.h>
#include <math.h>
#include <malloc.h>
struct book
char name[30];
char author[30];
int num_page;
int year;
char style[30];
struct book* next;
>;
struct book* poperedbook, * element, * pershiy, * novii, * ostan;
void Stvorutu( void )
element = ( struct book*)malloc( sizeof ( struct book));
pershiy = element;
do
poperedbook = element;
element->next = ( struct book*)malloc( sizeof ( struct book));
element = element->next;
> while (poperedbook->num_page != 0);
ostan = poperedbook;
poperedbook->next = NULL ;
>
void hood( void )
element = pershiy;
int main()
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
struct list int ptr;
list *next;
>;
void input_list(list *&first, int n) first = new list;
cinn >> first->ptr;
list *q = first;
for ( int i = 0; i < n — 1; i++) q->next = new list;
q = q->next;
cin >> q->ptr;
>
q->next = 0;
>
void print_list(list *q) while (q) cout << q->ptr << » » ;
q = q->next;
>
cout << endl;
>
void razbienie_list(list *&first) list *q = first;
list *chet = new list;
list *nechet = new list;
list *q1 = chet;
list *q2 = nechet;
list *w1 = q1;
list *w2 = q2;
while (p) if (q->ptr % 2) q2->ptr = p->ptr;
q2->next = new list;
w2 = q2;
q2 = q2->next;
>
else q1->ptr = p->ptr;
q1->next = new list;
q1 = q1;
q1 = q1->next;
>;
q = q->next;
>
w1->next = 0;
w2->next = 0;
>
int main() list *first = 0;
int n = 5;
input_list(first, n);
print_list(first);
razbienie_list(first);
print_list(first);
return 0;
>
void FreeWood(Wood*& pbeg)
Wood* p;
while (pbeg != NULL )
p = pbeg;
pbeg = pbeg->Next;
delete p;
>
>
int main()
char name[maxSize] = ;
char type[maxSize] = ;
double MaximumHeight;
double lifespan;