LINUX.ORG.RU

Реализация двусвязного списка

 ,


1

1

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

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

Вот пример работы программы:

Меню

Вставить ____ после индекса

Вставить ____ перед индексом

Вставить ____ в начало

Вставить ____ в конец

Удалить данные по индексу

Выйти

The list: Что Вы хотите сделать? Вставить 17 в конец

The list:

Что Вы хотите сделать?

Код программы:

class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None

class DoublyLinkedList:
def __init__(self):
self.first = None
self.last = None

def get_node(self, index):
current = self.first
for i in range(index):
if current is None:
return None
current = current.next
return current

def insert_after(self, ref_node, new_node):
new_node.prev = ref_node
if ref_node.next is None:
self.last = new_node
else:
new_node.next = ref_node.next
new_node.next.prev = new_node
ref_node.next = new_node

def insert_before(self, ref_node, new_node):
new_node.next = ref_node
if ref_node.prev is None:
self.first = new_node
else:
new_node.prev = ref_node.prev
new_node.prev.next = new_node
ref_node.prev = new_node

def insert_at_beg(self, new_node):
if self.first is None:
self.first = new_node
self.last = new_node
else:
self.insert_before(self.first, new_node)

def insert_at_end(self, new_node):
if self.last is None:
self.last = new_node
self.first = new_node
else:
self.insert_after(self.last, new_node)

def remove(self, node):
if node.prev is None:
self.first = node.next
else:
node.prev.next = node.next

if node.next is None:
self.last = node.prev
else:
node.next.prev = node.prev

def display(self):
current = self.first
while current:
print(current.data, end = ' ')
current = current.next


a_dllist = DoublyLinkedList()

print('Меню')
print('Вставить ____ после индекса')
print('Вставить ____ перед индексом')
print('Вставить ____ в начало')
print('Вставить ____ в конец')
print('Удалить данные по индексу') 
print('Выйти')

while True:
print('The list: ', end = '')
a_dllist.display()
print()
do = input('Что Вы хотите сделать? ').split()

operation = do[0].strip().lower()

if operation == 'Вставить':
data = int(do[1])
position = do[3].strip().lower()
new_node = Node(data)
suboperation = do[2].strip().lower() 
if suboperation == 'в':
if position == 'начало':
a_dllist.insert_at_beg(new_node)
elif position == 'конец':
a_dllist.insert_at_end(new_node)
else:
index = int(position)
ref_node = a_dllist.get_node(index)
if ref_node is None:
print('Такого индекса нет')
continue
if suboperation == 'после':
a_dllist.insert_after(ref_node, new_node)
elif suboperation == 'перед':
a_dllist.insert_before(ref_node, new_node)

elif operation == ' Удалить':
index = int(do[1])
node = a_dllist.get_node(index)
if node is None:
print('Такого индекса нет')
continue
a_dllist.remove(node)

elif operation == 'Выйти':
print ('Всего доброго!')
break

Потом решил вставить проверку: при добавлении в конец списка элемента должно печататься слово success. При тестовом прогоне ничего опять же не происходит.

if operation == 'Вставить':
data = int(do[1])
position = do[3].strip().lower()
new_node = Node(data)
suboperation = do[2].strip().lower() 
if suboperation == 'в':
if position == 'начало':
a_dllist.insert_at_beg(new_node)
elif position == 'конец':
a_dllist.insert_at_end(new_node)
print('success')

Большое спасибо за уделенное внимание и помощь.

Ответ на: комментарий от hippi90

Дошло, спасибо. Исправил команды на маленький регистр. Думаю, что так будет удобнее и логичнее, а lower если, что исправит все буквы в введённой пользователем команде на маленький регистр. Только вот команда удалить почему-то не срабатывает.

Вот пример работы:

Что Вы хотите сделать? вставить 7 в конец

The list: 7

Что Вы хотите сделать? удалить 0

Такого индекса нет

The list: 7

Что Вы хотите сделать? удалить 1

Такого индекса нет

The list: 7

Что Вы хотите сделать? вставить 3 в начало

The list: 3 7

Что Вы хотите сделать? удалить 0

Такого индекса нет

The list: 3 7

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

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.first = None
        self.last = None

    def get_node(self, index):
        current = self.first
        for i in range(index):
            if current is None:
                return None
            current = current.next
            return current

    def insert_after(self, ref_node, new_node):
        new_node.prev = ref_node
        if ref_node.next is None:
            self.last = new_node
        else:
            new_node.next = ref_node.next
            new_node.next.prev = new_node
        ref_node.next = new_node

    def insert_before(self, ref_node, new_node):
        new_node.next = ref_node
        if ref_node.prev is None:
            self.first = new_node
        else:
            new_node.prev = ref_node.prev
            new_node.prev.next = new_node
        ref_node.prev = new_node

    def insert_at_beg(self, new_node):
        if self.first is None:
            self.first = new_node
            self.last = new_node
        else:
            self.insert_before(self.first, new_node)

    def insert_at_end(self, new_node):
        if self.last is None:
            self.last = new_node
            self.first = new_node
        else:
            self.insert_after(self.last, new_node)

    def remove(self, node):
        if node.prev is None:
            self.first = node.next
        else:
            node.prev.next = node.next

        if node.next is None:
            self.last = node.prev
        else:
            node.next.prev = node.prev

    def display(self):
        current = self.first
        while current:
            print(current.data, end = ' ')
            current = current.next


a_dllist = DoublyLinkedList()

print('Меню')
print('вставить ____ после индекса')
print('вставить ____ перед индексом')
print('вставить ____ в начало')
print('вставить ____ в конец')
print('удалить ____ (удалить данные по индексу)') 
print('выйти')

while True:
    print('The list: ', end = '')
    a_dllist.display()
    print()
    do = input('Что Вы хотите сделать? ').split()

    operation = do[0].strip().lower()

    if operation == 'вставить':
        data = int(do[1])
        position = do[3].strip().lower()
        new_node = Node(data)
        suboperation = do[2].strip().lower() 
        if suboperation == 'в':
            if position == 'начало':
                a_dllist.insert_at_beg(new_node)
            elif position == 'конец':
                a_dllist.insert_at_end(new_node)
        else:
            index = int(position)
            ref_node = a_dllist.get_node(index)
            if ref_node is None:
                print('Такого индекса нет')
                continue
            if suboperation == 'после':
                a_dllist.insert_after(ref_node, new_node)
            elif suboperation == 'перед':
                a_dllist.insert_before(ref_node, new_node)

    elif operation == 'удалить':
        index = int(do[1])
        node = a_dllist.get_node(index)
        if node is None:
            print('Такого индекса нет')
            continue
        a_dllist.remove(node)

    elif operation == 'выйти':
        print ('Всего доброго!')
        break

general_ghest ()
Ответ на: комментарий от general_ghest

А список зачем, просто чтобы был или всё-таки полезную нагрузку предполагается нести?

Если да, то у класса DoublyLinkedList должен быть метод прохода по всем элементам, на основе которого уже можно делать поиск, фильтрацию etc внутри класса, да и всё остальное. Или в каждом методе будешь делать обход списка, например как в display?

Например, для печати всего списка напрашивается такой метод:

class DoublyLinkedList:
    ...
    
    def display(self):
        return ', '.join(map(lambda x: str, self.values()))


print(f'The list: {a_dllist.display()}')

Т.е. напрашиваются два генератора items и values.

vvn_black ★★★★★ ()
Последнее исправление: vvn_black (всего исправлений: 2)
Ответ на: комментарий от vvn_black

Наверное я чего-то понял. Компилятор указывает на ошибку на одинарной кавычке ' в строке:

 print(f'The list: {a_dllist.display()}') 

ВОТ ЗДЕСЬ

Текущий код:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.first = None
        self.last = None

    def get_node(self, index):
        current = self.first
        for i in range(index):
            if current is None:
                return None
            current = current.next
            return current

    def insert_after(self, ref_node, new_node):
        new_node.prev = ref_node
        if ref_node.next is None:
            self.last = new_node
        else:
            new_node.next = ref_node.next
            new_node.next.prev = new_node
        ref_node.next = new_node

    def insert_before(self, ref_node, new_node):
        new_node.next = ref_node
        if ref_node.prev is None:
            self.first = new_node
        else:
            new_node.prev = ref_node.prev
            new_node.prev.next = new_node
        ref_node.prev = new_node

    def insert_at_beg(self, new_node):
        if self.first is None:
            self.first = new_node
            self.last = new_node
        else:
            self.insert_before(self.first, new_node)

    def insert_at_end(self, new_node):
        if self.last is None:
            self.last = new_node
            self.first = new_node
        else:
            self.insert_after(self.last, new_node)

    def remove(self, node):
        if node.prev is None:
            self.first = node.next
        else:
            node.prev.next = node.next

        if node.next is None:
            self.last = node.prev
        else:
            node.next.prev = node.prev

    def display(self):
        return ', '.join(map(lambda x: str, self.values()))

        '''
        current = self.first
        while current:
            print(current.data, end = ' ')
            current = current.next
        '''

a_dllist = DoublyLinkedList()

print('Меню')
print('вставить ____ после индекса')
print('вставить ____ перед индексом')
print('вставить ____ в начало')
print('вставить ____ в конец')
print('удалить ____ (удалить данные по индексу)') 
print('выйти')

while True:
    print(f'The list: {a_dllist.display()}')
    #print('The list: ', end = '')
    a_dllist.display()
    print()
    do = input('Что Вы хотите сделать? ').split()

    operation = do[0].strip().lower()

    if operation == 'вставить':
        data = int(do[1])
        position = do[3].strip().lower()
        new_node = Node(data)
        suboperation = do[2].strip().lower() 
        if suboperation == 'в':
            if position == 'начало':
                a_dllist.insert_at_beg(new_node)
            elif position == 'конец':
                a_dllist.insert_at_end(new_node)
        else:
            index = int(position)
            ref_node = a_dllist.get_node(index)
            if ref_node is None:
                print('Такого индекса нет')
                continue
            if suboperation == 'после':
                a_dllist.insert_after(ref_node, new_node)
            elif suboperation == 'перед':
                a_dllist.insert_before(ref_node, new_node)

    elif operation == 'удалить':
        index = int(do[1])
        node = a_dllist.get_node(index)
        if node is None:
            print('Такого индекса нет')
            continue
        a_dllist.remove(node)

    elif operation == 'выйти':
        print ('Всего доброго!')
        break

general_ghest ()
Ответ на: комментарий от general_ghest

По ошибке, какая версия python? Синтаксис f-строк появился с 3.6.

И зачем же так в лоб копировать. Я не дал готовое решение, а предложил реализовать вам самостоятельно методы-генераторы items и values для DoublyLinkedList и в качестве примера показал, что display в этом случае будет выглядеть кмк получше.

Если с генераторами непонятно, то как-то так это выглядит и должно работать:

class DoublyLinkedList:
    ...

    def items(self):
        x = self.first
        while x:
            yield x
            x = x.next

    def values(self):
        x = self.first
        while x:
            yield x.data
            x = x.next
    
    def display(self):
        return ', '.join([str(x) for x in self.values()])


print('The list: ', a_dllist.display())

Т.е. теперь можно по порядку перебирать узлы списка или значения совсем просто:

for node in a_dllist.items():
    print(node.data)

...
for data in a_dllist.values():
    print(data)
и делать что-нибудь со значениями, например сумму посчитать:
print(sum(a_dllist.values()))

vvn_black ★★★★★ ()
Последнее исправление: vvn_black (всего исправлений: 2)
Ответ на: комментарий от vvn_black

Версия 3.5.2 . Спасибо за более подробное разъяснение: я новичок в питоне и мне сейчас как-то сложно бывает разобраться. Я так понимаю надо добавить циклы for в функцию обхода значений get_node?

for node in a_dllist.items():
    print(node.data)
for data in a_dllist.values():
    print(data)
Пока не очень понял куда их добавить получилось вот:
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.first = None
        self.last = None

    def get_node(self, index):
        current = self.first
        for i in range(index):
            if current is None:
                return None
            current = current.next
            return current

    def insert_after(self, ref_node, new_node):
        new_node.prev = ref_node
        if ref_node.next is None:
            self.last = new_node
        else:
            new_node.next = ref_node.next
            new_node.next.prev = new_node
        ref_node.next = new_node

    def insert_before(self, ref_node, new_node):
        new_node.next = ref_node
        if ref_node.prev is None:
            self.first = new_node
        else:
            new_node.prev = ref_node.prev
            new_node.prev.next = new_node
        ref_node.prev = new_node

    def insert_at_beg(self, new_node):
        if self.first is None:
            self.first = new_node
            self.last = new_node
        else:
            self.insert_before(self.first, new_node)

    def insert_at_end(self, new_node):
        if self.last is None:
            self.last = new_node
            self.first = new_node
        else:
            self.insert_after(self.last, new_node)

    def remove(self, node):
        if node.prev is None:
            self.first = node.next
        else:
            node.prev.next = node.next

        if node.next is None:
            self.last = node.prev
        else:
            node.next.prev = node.prev

    def items(self):
        x = self.first
        while x:
            yield x
            x = x.next

    def values(self):
        x = self.first
        while x:
            yield x.data
            x = x.next
    
    def display(self):
        return ', '.join([str(x) for x in self.values()])

        '''
        current = self.first
        while current:
            print(current.data, end = ' ')
            current = current.next
        '''

a_dllist = DoublyLinkedList()

print('Меню')
print('вставить ____ после индекса')
print('вставить ____ перед индексом')
print('вставить ____ в начало')
print('вставить ____ в конец')
print('удалить ____ (удалить данные по индексу)') 
print('выйти')

while True:
    print('The list: ', a_dllist.display())
    #print('The list: ', end = '')
    a_dllist.display()
    print()
    do = input('Что Вы хотите сделать? ').split()

    operation = do[0].strip().lower()

    if operation == 'вставить':
        data = int(do[1])
        position = do[3].strip().lower()
        new_node = Node(data)
        suboperation = do[2].strip().lower() 
        if suboperation == 'в':
            if position == 'начало':
                a_dllist.insert_at_beg(new_node)
            elif position == 'конец':
                a_dllist.insert_at_end(new_node)
        else:
            index = int(position)
            ref_node = a_dllist.get_node(index)
            if ref_node is None:
                print('Такого индекса нет')
                continue
            if suboperation == 'после':
                a_dllist.insert_after(ref_node, new_node)
            elif suboperation == 'перед':
                a_dllist.insert_before(ref_node, new_node)

    elif operation == 'удалить':
        index = int(do[1])
        node = a_dllist.get_node(index)
        if node is None:
            print('Такого индекса нет')
            continue
        a_dllist.remove(node)

    elif operation == 'выйти':
        print ('Всего доброго!')
        break

general_ghest ()
Ответ на: комментарий от general_ghest

Я так понимаю надо добавить циклы for в функцию обхода значений get_node?
Пока не очень понял куда их добавить

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

Для примера, напечатать все значения data из списка, можно так:

node = a_dllist.first
while node:
    print(node.data)
    node = node.next

а можно так:

for node in a_dllist.items():
    print(node.data)

второе немного лаконичнее и более python way, а в некоторых случаях ещё и сильно удобнее.

А теперь представь, что у тебя есть уже заполненный твой список и тебе надо что-то с данными делать, например отобрать только четные, или сумму посчитать, или ещё чего. Всё это приятнее делать «по-питоньи», посмотри для примера как метод display до одной строки сократился.

Попробуй без методов items и values написать код отбора в список, например, только чётных значений, что у тебя получится? А с генераторами это всего одна строка:

e = [x for x in a_dllist.values() if x % 2 == 0]

Кстати, возвращаясь к твоей реализации, разве не интересно знать размер списка, т.е. напрашивается метод size(). )

vvn_black ★★★★★ ()
Последнее исправление: vvn_black (всего исправлений: 2)