Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Определяем: базовый класс для узла, где он хранится
- # данные того же узла
- # индекс следующего узла
- # индекс предыдущего узла
- 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()])
- def sort(self):
- #Current(текущий элемент) будет указывать на голову списка
- current = self.first
- while(current.next != None):
- #Index будет указывать на следующий элемент после текущего
- index = current.next;
- while(index):
- #Если текущий узел>следующий, то меняем их местами
- yield(index.data)
- temp = current.data;
- current.data = index.data;
- index.data = temp;
- index = index.next
- current = current.next
- #Опредедение размера списка
- def size(self):
- temp = self.first
- count = 0
- while temp is not None:
- count = count + 1
- temp = temp.next
- return count
- #Поиск в списке
- def search (self, element):
- current=self.head
- index=1
- while current != None:
- if current.data == element:
- return index
- current = current.next_node
- index += 1
- return -1
- a_dllist = DoublyLinkedList()
- print('Меню')
- print('вставить ____ после индекса')
- print('вставить ____ перед индексом')
- 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 == 'сортировать':
- a_dllist.sort()
- elif operation == 'удалить':
- index = int(do[1])
- node = a_dllist.get_node(index)
- if node is None:
- print('Такого индекса нет')
- continue
- a_dllist.remove(node)
- elif operation == 'найти':
- element = input("Введите поисковый запрос: ")
- search_index=a_dllist.search(element)
- if search_index is None:
- print('Такого элемента нет')
- elif operation == 'определить размер':
- a_dllist.size()
- elif operation == 'выйти':
- print ('Всего доброго!')
- break
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement