Запутался в узле при создании связанных списков

ProgramBox

Запутался в узле при создании связанных списков

Post author:admin
Запись опубликована:25 февраля, 2023
Post category:Вопросы по программированию

#python #linked-list

#python #связанный список

Вопрос:

Я пытаюсь создать связанный список на python без использования классов. Но я немного смущен.

Вот пример того, чего я пытаюсь достичь: head = [None,None] n = целое число, и функция вызывается из цикла

 def append(head, n):
    node = head
    while node[1] != None: # Find last node
        node = node[1]
    node[1] = [n,None]  # Attach new node

В основном используется узел, который содержит значение и указывает на next. Теперь я пытаюсь сделать что-то подобное со своей программой, основное отличие заключается в том, что в примере отображается заголовок, содержащий [None,None], а в моей программе вместо этого я получаю 10 пустых списков. Это то, что я получил:

 def add(word_set,word):
    node = word_set
    node[-1] = [word,None]
    while node[1] != None:
        node = node[1]
        node[1] = [word,None]

вызывается этим из main:

 names = ["Ella", "Owen", "Fred", "Zoe", "Adam", "Ceve", "Adam", "Ceve", "Jonas", "Ola", "Morgan", "Fredrik", "Simon", "Albin", "Måns", "Amer", "David"]

word_set = ws.new_empty_set()
for s in names:
    ws.add(word_set,s)

Я не совсем понимаю, как воспроизвести пример функции с моим кодом. Я всегда получаю индекс вне диапазона, когда пытаюсь. Также я не хочу вносить какие-либо изменения в main.py

1. Если word_set это пустая последовательность, node[-1] она будет вне границ, поскольку node будет пустой. Вы могли бы передать список [None, None] или что-то вместо этого? Или просто node = [word,None] .

2. Я предполагаю, что последняя строка вашей add функции имеет отступ на одну позицию слишком далеко и не должна быть частью while . Если это правда, то единственным существенным различием между этими двумя функциями является строка node[-1] = [word,None] . Но если узлы всегда имеют 2 элемента, что, похоже, они делают и в вашей версии, то это то же самое, что node[1] = [word,None] . Похоже, что kubw тогда отсекает список, на который word_set указывал, гарантируя, что в вашем списке всегда будет первый узел плюс два узла, следующие за обоими, содержащие одно и то же слово.

3. @Steve ws , похоже, является именем модуля, а не объектом. Так ws.add(word_set, s) что, по-видимому, добавляет s word_set .

4. Строка node[1] = [word,None] не должна находиться внутри while цикла. Это должно быть после цикла, как и в append() функции.

5. О да. Не думал, что такой простой код будет разбит на модули, но это имеет смысл (без классов, верно?). Я согласен с вами в том, что одна строка имеет слишком большой отступ… Я сказал то же самое выше.

Ответ №1:

Некоторые проблемы:

Предполагая, что new_empty_set возвращает пустой список, при add назначении node[-1] = будет выдана ошибка, о которой вы упоминаете. Сначала вы должны проверить, является ли список пустым, и разобраться с этим граничным случаем отдельно.
Последняя строка add не должна быть частью цикла. Он должен быть выполнен после завершения цикла.
Менее важно, но использование имени «set» сбивает с толку, так как set это собственный тип, который является не списком, а набором хэшей. Поэтому я бы использовал термин «linked_list» вместо этого

Исправленный код:

 # assuming this definition, but don't call it *set
#   but *linked_list:
def new_empty_linked_list():
    return []

def add(word_linked_list, word):   # change of name
    node = word_linked_list
    if not node:  # the list is empty
        node.extend([word, None])
    else:
        while node[1] != None:
            node = node[1]
        node[1] = [word, None]  # outside of loop

names = ["Ella", "Owen", "Fred", "Zoe", "Adam", "Ceve", "Adam", "Ceve", "Jonas", "Ola", "Morgan", "Fredrik", "Simon", "Albin", "Måns", "Amer", "David"]

word_linked_list = new_empty_linked_list()
for s in names:
    add(word_linked_list, s)

print(word_linked_list)

В вашем вводе есть несколько повторяющихся имен. Вы не упомянули, что должно произойти с ними, и ваша add функция не обрабатывает их по-другому. Но если список не должен хранить дубликаты, тогда вам следует добавить некоторое условие в свой цикл:

 def add(word_linked_list, word):
    node = word_linked_list
    if not node:
        node.extend([word, None])
    else:
        # add condition to spot duplicate value
        while node[0] != word and node[1] != None:
            node = node[1]
        if node[0] != word:  # only add when unique
            node[1] = [word, None]

1. Я попробовал ваш код, и, к сожалению, он по-прежнему выдает мне индекс списка вне диапазона.

2. Он отлично работает на repl.it . Должен быть другой код, ответственный за эту ошибку.