Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > Скриптовые языки программирования > Python
Регистрация

Восстановить пароль
Повторная активизация e-mail


Донат для форума - использовать для поднятия настроения себе и модераторам

А ещё здесь можно купить рекламу за 25 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

Ответ
 
Опции темы
Старый 10.10.2019, 16:42   #1
General_ghest
Новичок
 
Регистрация: 10.10.2019
Сообщений: 2
Репутация: 10
По умолчанию Двунаправленный линейный список на python

Всем здравствуйте.
Я пишу программу реализующую двусвязный список.
Вот код который у меня получился:
Код:
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())
    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
Мне нужно написать к нему сортировку и поиск.
Попробовал реализовать сортировку так, но это явно не подходит в таком виде:
Код:
    def sort(self)
        x=self.first #берём самый 1 элемент x
        for x in self.values() 
            y=x.next #берём элемент следующий за x
            if (x<y) #сравниваем
                swap(x,y) #меняем местами
            x=x.next #переходим к следующему элементу x для следующего цикла
Понимаю что в swap нужно менять не x и y, а объекты в списке, но не очень понимаю как это написать.
Спасибо за уделённое внимание и помощь.
General_ghest вне форума   Ответить с цитированием
Старый 10.10.2019, 21:36   #2
General_ghest
Новичок
 
Регистрация: 10.10.2019
Сообщений: 2
Репутация: 10
По умолчанию

Забыл про двоеточия и ещё кое-что по мелочи подправил. Ошибок теперь нет, продолжаю дорабатывать:
Код:
    def sort(self):
        x=self.first # берём самый 1 элемент x
        for x in self.values():
            y=x.next # берём элемент следующий за x
            if (x<y):
                swap(x,y) # меняем местами
            x=x.next # переходим к следующему элементу x для следующего цикла
А вот поиск не получилось добавить.
General_ghest вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
линейный двунаправленный список c++ luibrain Помощь студентам 3 17.04.2016 13:36
Линейный двунаправленный список BaTpyXaaa Общие вопросы C/C++ 0 07.12.2014 20:26
линейный двунаправленный список мария герасимова Паскаль 1 22.09.2011 19:04
Линейный Двунаправленный Список D1mon Помощь студентам 1 14.04.2009 21:37
Линейный двунаправленный список Seg_62 Паскаль 4 28.08.2008 21:02


10:27.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.