Блог

Главная - Вопросы по программированию - О связанных списках в python

О связанных списках в python

#python

Вопрос:

Мне нужно создать функцию для удаления узла из связанного списка из значения, заданного вручную внутри этой функции, но я точно не знаю, как это сделать. Мой алгоритм выглядит так:

 noRaiz = None

def novoNo(valor):
    return {
        "valor": valor,
        "proximo": None
    }
def remove(valor):
global noRaiz
if noRaiz is None:
    return
noAtual = noRaiz
if noRaiz["valor"] == valor:
    noRaiz = noRaiz["proximo"]


def imprimir():
    noAtual = noRaiz
    while noAtual is not None:
        print(noAtual["valor"])
        noAtual = noAtual["proximo"]


noRaiz = novoNo(54)
no2 = novoNo(26)
no3 = novoNo(93)
no4 = novoNo(17)
no5 = novoNo(77)
no6 = novoNo(31)

noRaiz["proximo"] = no2
no2["proximo"] = no3
no3["proximo"] = no4
no4["proximo"] = no5
no5["proximo"] = no6
no6["proximo"] = None


imprimir()

noRaiz-это первый узел в списке, noAtual-это текущий узел в списке во время печати при запуске кода, а imprimir () — это функция для печати узлов. Как бы выглядела функция, если бы я хотел удалить узел 54 или 17?

Комментарии:

1. Пройдитесь по нему, как вы это делаете, imprimir() чтобы найти его. Когда вы найдете его, назначьте "valor" prev следующему "valor" .

Ответ №1:

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

Вот функция:

 def remove(valor):
    global noRaiz
    if noRaiz is None:  # Nothing to do
        return
    noAtual = noRaiz
    if noRaiz["valor"] == valor:  # Special case
        noRaiz = noRaiz["proximo"]
        return
    while noAtual["proximo"] is not None:
        if noAtual["proximo"]["valor"] == valor:
            noAtual["proximo"] = noAtual["proximo"]["proximo"]
            break
        noAtual = noAtual["proximo"]

Примечание: рассмотрите возможность реализации связанного списка с узлом class вместо глобального словаря.

Метки: