Обмен узлами в связанном списке - PullRequest
Новая
       16

Обмен узлами в связанном списке

1 голос
/ 02 апреля 2012

Я пытаюсь поменять местами два смежных узла в связанном списке, и мне кажется, что я понимаю идею, как сделать это, используя временный узел.*

Не могу придумать, как сделать так, чтобы предыдущий узел в списке указывал на новый переставленный узел.Нужна ли мне другая временная переменная?Кроме того, как мне учесть случай, когда два узла, подлежащие обмену, являются первыми двумя в списке.

Ответы [ 5 ]

1 голос
/ 02 апреля 2012

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

[1]->[2]->[3]->[4]

Предположим, это ваш связанный список, и вы хотите поменять местами [2] и [3].

  1. используйте цикл для достижения до [2]. так что ваш temp на [2].
  2. Теперь temp1 = temp->next; Следовательно, temp1 находится на [3].

  3. temp->next = temp1->next;

    temp1->next = temp;

так что теперь temp->next = [4] и temp1->next = [2]

1 голос
/ 02 апреля 2012

С такими маленькими данными вы можете просто поменять все, кроме указателей next: 

partType tmp = *item;
memcpy(item, item->next, offsetof(item, next));
memcpy(item->next, &tmp, offsetof(item, next));

Если ваши данные становятся слишком большими для этого, вам понадобится указатель на узел перед двумя нужными вам. Приятно то, что ваше исправление prev next указателя действует как временная переменная, позволяя вам не нуждаться в ней. 

prev->next = item->next;
item->next = item->next->next;
prev->next->next = item;
1 голос
/ 02 апреля 2012

Игнорировать ответы о двусвязных списках. Чтобы ответить на ваш вопрос, вам нужно подумать о том, как вы вызываете свою функцию.

Прямо сейчас у вас есть функция, которая берет указатель на указатель. В настоящее время он указывает на узел (узел A), который, в свою очередь, указывает на другой узел (узел B). Представьте себе этот сценарий: 

partType a, b, c, d;
a->next = &b;
b->next = &c;
c->next = &d;
d->next = NULL;

Теперь вы хотите поменять местами порядок B и C, чтобы A-> C-> B-> D, используя вашу функцию. Ну, ты бы сделал: 

swap_node(&a->next);

A указывал на B; теперь он указывает на C. Как видите, «предыдущий» узел уже указывает на C, как вы и ожидали. Другими словами, вы уже достигли своей цели. Ура!

Примечания: Что именно происходит в вашей функции подкачки? Давайте разберемся с этим. Во-первых, заданный вами параметр - это указатель на указатель . Об этом стоит подумать из-за формулировок - не позволяйте формулировкам обмануть вас. Точно так же, как «скорость изменения скорости изменения» - сука, но «ускорение» намного проще. Вы хотите разобрать его, помня, что параметр - это, в первую очередь, указатель на некоторые данные, и ваша функция собирается изменить данные, на которые она указывает.

Таким образом, ваша функция получает указатель на этот «p», который указывает на точку в связанном списке, которая (вы предполагаете, см. PS) указывает на два узла (назовите их X и Y). Диаграмма: 

[p] --> X[next] --> Y[next] --> Z[next]

Ваш алгоритм делает:

  1. Сделайте [p] указанием на Y: * item = (* item) -> next
  2. Сделать X [следующий] точкой Z: temp-> next = (* item) -> next
  3. Сделать так, чтобы Y [следующий] указывал на X: (* item) -> next = temp

Итак, если вы рассмотрите мой пример A, B, C, D, связанный список будет: 

A[next] --> B[next] --> C[next] --> D[next] --> NULL

Вы можете более четко видеть, какой указатель я передаю. Это место в памяти (читай: указатель), в котором хранится A [next], и ваша функция должна выполнить обмен.

Кстати, другой способ закодировать это можно сделать: 

a->next = swap_node(&a->next);

но не делай этого. Это избыточно.

PS Задумывались ли вы о том, что происходит, когда вы просите поменять местами последний узел в серии? Прямо сейчас, вещи взрываются: P

1 голос
/ 02 апреля 2012

Из кода похоже, что вы хотите поменять местами элемент и элемент-> следующий.

Если у вас нет двусвязного списка, вам нужно установить linkPtr в заголовок, а затем выполнять итерацию до элемента linkPtr-> next == *. Оттуда вы можете начать переключение между linkPtr, linkPtr-> next и linkPtr-> next-> next.

Вам также нужно отдельное условие, сравнивающее linkPtr с головой, и если да, то вам нужно установить head на новую голову.

0 голосов
/ 02 апреля 2012

Четыре простых варианта:

Первый вариант: отслеживать указатель на prev (возможно, направление, в котором ожидается назначение).

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

Третий вариант: реализовать односвязный список (как, вероятно, требует ваше назначение), но дать каждому узлу два указателя: один указывает на «следующий», а другой указывает на полезную нагрузку данных (которая может быть практически любой; структура, массив или простой старый тип данных). Затем вы просто меняете местами указатели полезной нагрузки, не беспокоясь о «next» и «prev».

Четвертый вариант: поменять местами сами данные (возможно, направление, в котором ожидается назначение).

Существуют варианты использования для каждого из вышеперечисленных.

...