Обратный порядок номеров в связанном списке рекурсивно - PullRequest
Новая
       28

Обратный порядок номеров в связанном списке рекурсивно

0 голосов
/ 05 февраля 2019

Я хочу изменить порядок чисел в связанном списке с помощью рекурсии.

(1, (2, (3, ()))) ----> (3, (2, (1, ())))

Мои связанные списки - это вложенные кортежи.First (xs) возвращает первый элемент, в приведенном выше примере это будет 1 или 3 с правой стороны.Rest (xs) возвращает все остальные элементы, (2, (3, ())) или (2, (1, () справа).

мой код выглядит так: 

empty = ()
def reversed(xs):
    if xs == (first(xs), empty):
        return first(xs)
    else:
        return reversed(rest(xs)), first(xs)

но это приводит к следующему выводу: 

((3, 2), 1)

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

Может кто-нибудьпомогите мне?

Спасибо

Ответы [ 2 ]

0 голосов
/ 05 февраля 2019

Вы можете использовать простую рекурсию: 

d = (1,(2,(3,())))
def reverse(_d, _c = ()):
  a, b = _d
  return (a, _c) if not b else reverse(b, (a, _c))

print(reverse(d))

Вывод: 

(3, (2, (1, ())))
0 голосов
/ 05 февраля 2019

Есть разные способы сделать это.Прямо сейчас вы просто объединяете их в новый кортеж, который не создает правильно сформированный связанный список.Вместо этого вы можете append прежний first до reversed rest, используя вторую функцию.Кроме того, ваш базовый случай кажется неправильным, так как вы возвращаете только один элемент вместо связанного списка. 

def reversed(xs):
    if xs == empty:
        return empty
    else:
        return append(reversed(rest(xs)), first(xs))

def append(xs, x):
    if xs == empty:
        return (x, empty)
    else:
        return first(xs), append(rest(xs), x)

>>> reversed((1, (2, (3, (4, empty)))))
(4, (3, (2, (1, ()))))

Обратите внимание, однако, что это имеет квадратичную сложность O (n²), так как вы должны это сделать.итерируйте весь список (или частичный список) до append узла first на каждом шаге функции reversed.Для версии с линейной сложностью O (n) вы можете добавить второй параметр к вашей функции reversed (или создать вторую функцию, которая будет вызываться исходной функцией, если вы не можете изменить сигнатуру).Это создаст перевернутый список в этом втором параметре и, наконец, просто вернет этот список. 

def reversed(xs, tail=empty):
    if xs == empty:
        return tail
    else:
        return reversed(rest(xs), (first(xs), tail))

Кроме того, как отмечено в комментариях, существуют более совершенные языки для определения рекурсивных структур данных, чем Python, и лучшие способы использованиясписки в Python, но я предполагаю, что это только для изучения, а не для практического использования.

...