Например, мы можем хранить список элементов, имеющих одинаковый тип данных, используя структуру данных массива.
Алгоритм, с другой стороны, представляет собой пошаговый набор инструкций для обработки данных с определенной целью. Таким образом, алгоритм объединяет различные структуры данных логическим образом для решения конкретной вычислительной задачи. Это очень важная концепция в информатике. Она дает нам больше понимания данных, с которыми мы работаем. Она позволяет специалистам по изучению данных делать более точные прогнозы машинного обучения. Однако, по мнению большинства людей в технологической индустрии, это сложная тема.
Списки
Список — это наиболее универсальный тип данных, доступный в Python, который может быть записан как список значений (элементов), разделенных запятыми, заключенных в квадратные скобки. Списки являются изменяемыми и упорядоченными. Они могут содержать смесь различных типов данных.
list1 = ['chicken', 'pizza', 2022, 2000]
list2 = [1, 2, 3, 4, 5 ]
list3 = ["a", "b", "c", "d"]
Мы можем получить доступ к значениям в списке, используя их индекс.
ПРИМЕЧАНИЕ: отсчет начинается с 0.
print (list1[0]) #prints the element in the 0 index
Мы также используем метод .append() для добавления новых элементов в список eg
list2.append(6) #add 6 to the existing list2
Если вы хотите добавить в определенное место в списке, мы делаем это следующим образом
list3[2] = "e" # returns ["a", "b", "e", "d"]
Некоторые основные операции со списком включают:
- len([1, 2, 3]) в результате 3, что проверяет длину
- [1, 2, 3] + [4, 5, 6]- результат[1, 2, 3, 4, 5, 6]|Конкатенация
- [‘Hi!’] * 3, что приводит к [‘Hi!’, ‘Hi!’, ‘Hi!’], что проверяет Повторение
- 3 в [1, 2, 3] в результате True, что проверяет Членение
- for x in [1, 2, 3]:print x result to 1 2 3 which tests Iteration
Словари
Словарь — это изменяемая и неупорядоченная структура данных. Он позволяет хранить пару элементов (т.е. ключи и значения). Каждый ключ отделяется от своего значения двоеточием (:), элементы разделяются запятыми, и все это заключено в фигурные скобки. Пустой словарь без элементов записывается только с двумя фигурными скобками, например, так — {}.
Ключи уникальны в словаре, в то время как значения могут быть не уникальны. Значения словаря могут быть любого типа, но ключи должны быть неизменяемыми типами данных, такими как строки, числа или кортежи.
Доступ к значениям в словаре
Для доступа к элементам словаря можно использовать привычные квадратные скобки вместе с ключом, чтобы получить его значение.
Пример:
dict = {'Name': 'Marrie', 'Age': 27, 'Language': 'Python'}
print "dict['Name']: ", dict['Name']
print "dict['Age']: ", dict['Age']
При выполнении приведенного выше кода получается следующий результат:
dict['Name']: Marrie
dict['Age']: 27
Если мы попытаемся получить доступ к элементу данных с ключом, который не является частью словаря, мы получим ошибку, как показано ниже:
Пример
#Using the data above.
print "dict['Alice']: ", dict['Alice']
При выполнении приведенного выше кода получается следующий результат:
dict['Alice']:
Traceback (most recent call last):
File "test.py", line 4, in <module>
print "dict['Alice']: ", dict['Alice'];
KeyError: 'Alice'
Обновление словаря
Вы можете обновить словарь, добавив новую запись или пару ключ-значение, изменив существующую запись или удалив существующую запись, как показано ниже на простом примере:
dict = {'Name': 'Marrie', 'Age': 27, 'Language': 'Python'}
dict['Age'] = 28; # update existing entry
dict['School'] = "LuxAcademy"; # Add new entry
print "dict['Age']: ", dict['Age']
print "dict['School']: ", dict['School']
При выполнении приведенного выше кода получается следующий результат:
dict['Age']: 28
dict['School']:LuxTech
Удаление элементов словаря
Вы можете удалить отдельные элементы словаря или очистить все содержимое словаря. Вы также можете удалить весь словарь за одну операцию.
Чтобы явно удалить весь словарь, просто используйте оператор del.
dict = {'Name': 'Marrie', 'Age': 27, 'Language': 'Python'}
del dict['Name']; # remove entry with key 'Name'
dict.clear(); # remove all entries in dict
del dict ; # delete entire dictionary
print "dict['Age']: ", dict['Age']
print "dict['School']: ", dict['School']
Обратите внимание, что возникает исключение, так как после del dict словарь больше не существует:
dict['Age']:
Traceback (most recent call last):
File "test.py", line 8, in <module>
print "dict['Age']: ", dict['Age'];
TypeError: 'type' object is unsubscriptable
Свойства ключей словаря
Значения словаря не имеют ограничений. Они могут быть любыми произвольными объектами Python, как стандартными, так и определенными пользователем. Однако то же самое не относится к ключам.
Есть два важных момента, которые следует помнить о ключах словаря:
* Не допускается более одной записи на ключ. Это означает, что дублирование ключей не допускается. Если во время задания встречаются дубликаты ключей, побеждает последнее задание.
dict = {'Name': 'Marrie', 'Age': 27, 'Name': 'Python'}
print "dict['Name']: ", dict['Name']
При выполнении приведенного выше кода получается следующий результат:
dict['Name']: Python
*Ключи должны быть неизменяемыми. Это означает, что вы можете использовать строки, числа или кортежи в качестве ключей словаря, но что-то вроде [‘key’] не допускается.
Пример следующий:
dict = {['Name']: 'Marrie', 'Age': 27}
print "dict['Name']: ", dict['Name']
При выполнении приведенного выше кода получается следующий результат:
Traceback (most recent call last):
File "test.py", line 3, in <module>
dict = {['Name']: 'Marrie', 'Age': 27};
TypeError: list objects are unhashable
Кортежи
Кортеж — это еще один контейнер. Это тип данных для неизменяемых упорядоченных последовательностей элементов. Неизменных потому, что вы не можете добавлять и удалять элементы из кортежей или сортировать их на месте.
Создать кортеж очень просто — нужно поместить в него различные значения, разделенные запятыми. По желанию вы можете поместить эти значения, разделенные запятыми, между круглыми скобками.
Например:
tuple_one = ('python', 'javascript', 'c++', 2000);
tuple_two = (1, 2, 3, 4, 5 );
tuple_3 = "a", "b", "c", "d";
Пустой кортеж записывается как две круглые скобки, не содержащие ничего —
languages = ();
Чтобы записать кортеж, содержащий одно значение, необходимо поставить запятую, даже если значение только одно…
tup1 = (50,);
Как и индексы строк, индексы кортежей начинаются с 0, и их можно нарезать, конкатенировать и так далее.
Доступ к значениям в кортежах
Чтобы получить доступ к значениям в кортеже, используйте квадратные скобки для нарезки вместе с индексом или индексами, чтобы получить значение, доступное по этому индексу.
Например
tuple_one = ('python', 'javascript', 'c++', 2000);
tuple_two = (1, 2, 3, 4, 5 );
print "tuple_one[0]: ", tuple_two[0];
print "tuple_two[1:5]: ",tuple_two[1:5];
При выполнении приведенного выше кода получается следующий результат :
tuple_one[0]: python
tuple_two[1:5]: [2, 3, 4, 5]
Обновление кортежей
Кортежи неизменяемы, что означает, что вы не можете обновить или изменить значения элементов кортежа. Вы можете брать части существующих кортежей для создания новых кортежей, как показано в следующем примере.
tup1 = (12, 34.56);
tup2 = ('abc', 'xyz');
# Following action is not valid for tuples
# tup1[0] = 100;
# So let's create a new tuple as follows
tup3 = tup1 + tup2;
print tup3;
При выполнении приведенного выше кода получается следующий результат:
(12, 34.56, 'abc', 'xyz')
Удаление элементов кортежа
Удаление отдельных элементов кортежа невозможно. Конечно, нет ничего плохого в том, чтобы составить другой кортеж с отброшенными ненужными элементами.
Чтобы явно удалить весь кортеж, просто используйте оператор del.
Например:
tuple_one = ('python', 'javascript', 'c++', 2000);
print tuple_one;
del tuple_one;
print "After deleting tup : ";
print tuple_one;
Обратите внимание — возникло исключение, это потому, что после del tup кортеж больше не существует.
Это дает следующий результат:
('python', 'javascript', 'c++', 2000)
После удаления tup :
Traceback (most recent call last):
File "test.py", line 9, in <module>
print tuple_one;
NameError: name 'tuple_one' is not defined.
Предположим, что имя нашего файла «test.py».
Основные операции с кортежами
Кортежи реагируют на операторы + и * так же, как и строки; они означают конкатенацию и повторение, за исключением того, что результатом является новый кортеж, а не строка.
На самом деле, кортежи отвечают на все общие операции последовательности, которые мы использовали для строк в предыдущей главе.
- len((1, 2, 3)), результатом которого является 3, используемое для проверки длины
- (1, 2, 3) + (4, 5, 6), что приводит к (1, 2, 3, 4, 5, 6) и используется для проверки конкатенации
- (‘Hi!’,) * 4, что приводит к(‘Hi!’, ‘Hi!’, ‘Hi!’, ‘Hi!’, ‘Hi!’) и используется для проверки Повторение
- 3 в (1, 2, 3), что приводит к True и используется для проверки Членения
- for x in (1, 2, 3): print x which results to 1 2 3 and is used to test Iteration
Наборы
Набор — это изменяемая и неупорядоченная коллекция уникальных элементов. Оно позволяет быстро удалять дубликаты из списка. Множества в python обычно используются для математических операций, таких как объединение, пересечение, разность, дополнение и т.д.
Множество в Python похоже на это математическое определение со следующими дополнительными условиями:
*Элементы в множестве не могут быть дубликатами.
*Элементы в множестве неизменяемы (не могут быть изменены), но множество в целом является изменяемым.
*Не существует индекса, привязанного к какому-либо элементу в множестве python. Поэтому они не поддерживают никаких операций индексирования или нарезки.Создание множества
Набор создается с помощью функции set() или помещением всех элементов в пару фигурных скобок.
Days=set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"])
Months={"Jan","Feb","Mar"}
Dates={21,22,17}
print(Days)
print(Months)
print(Dates)
Обратите внимание, как изменился порядок элементов в результате.
set(['Wed', 'Sun', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])
set(['Jan', 'Mar', 'Feb'])
set([17, 21, 22])
Доступ к значениям в наборе
Мы не можем получить доступ к отдельным значениям в наборе. Мы можем получить доступ только ко всем элементам вместе, как показано выше. Но мы также можем получить список отдельных элементов, перебирая набор.
#Considering the data above.
Days=set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"])
for d in Days:
print(d)
При выполнении приведенного выше кода получается следующее:
Wed
Sun
Fri
Tue
Mon
Thu
Sat
Добавление элементов в набор
Мы можем добавлять элементы в набор с помощью метода add(). Помните, что у вновь добавленного элемента нет определенного индекса.
#Adding to the data above.
Days.add("Sun")
print(Days)
результаты
set(['Wed', 'Sun', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])
Удаление элемента из множества
Мы можем удалять элементы из множества с помощью метода discard().
Пример
#Using the data above.
Days.discard("Sun")
print(Days)
Вывод
set(['Wed', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])
Объединение множеств
Операция объединения двух множеств дает новое множество, содержащее все различные элементы из обоих множеств. В приведенном ниже примере элемент «Wed» присутствует в обоих наборах.
DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Wed","Thu","Fri","Sat","Sun"])
AllDays = DaysA|DaysB
print(AllDays)
Результат будет выглядеть так, как показано на рисунке, обратите внимание, что результат содержит только один элемент «wed».
set(['Wed', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])
Пересечение множеств
Операция пересечения двух множеств дает новое множество, содержащее только общие элементы из обоих множеств. В приведенном ниже примере элемент «Wed» присутствует в обоих множествах.
DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Wed","Thu","Fri","Sat","Sun"])
AllDays = DaysA & DaysB
print(AllDays)
Выход
set(['Wed'])
Разность множеств
Операция разности двух множеств создает новое множество, содержащее только элементы из первого множества и ни одного из второго. В приведенном ниже примере элемент «Wed» присутствует в обоих наборах, поэтому он не будет найден в результирующем наборе.
DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Wed","Thu","Fri","Sat","Sun"])
AllDays = DaysA - DaysB
print(AllDays)
Вывести
При выполнении приведенного выше кода получается следующий результат. Обратите внимание, что результат содержит только один символ «wed».
set(['Mon', 'Tue'])
Сравнение множеств
Мы можем проверить, является ли данное множество подмножеством или надмножеством другого множества. Результатом будет True или False в зависимости от того, какие элементы присутствуют в множествах.
Пример
DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"])
SubsetRes = DaysA <= DaysB
SupersetRes = DaysB >= DaysA
print(SubsetRes)
print(SupersetRes)
Вывод
True
True
Очередь
Очередь — это линейная структура данных, в которой элементы располагаются последовательно. Она следует механизму F.I.F.O, что означает «первым пришел — первым ушел».
Ниже приведены аспекты, характеризующие очередь.
Два конца:
*передний → указывает на начальный элемент
*задний → указывает на последний элемент
Две операции:
*enqueue → вставка элемента в очередь. Это будет сделано на заднем конце.
*dequeue → удаление элемента из очереди. Она будет выполняться спереди.
Есть два условия:
*переполнение → вставка в переполненную очередь.
*underflow → удаление из пустой очереди
Давайте посмотрим пример кода:
class myqueue:
def __init__(self):
self.data = []
def length(self):
return len(self.data)
def enque(self, element): # put the element in the queue
if len(self.data) < 5:
return self.data.append(element)
else:
return "overflow"
def deque(self): # remove the first element that we have put in queue
if len(self.data) == 0:
return "underflow"
else:
self.data.pop(0)
b = myqueue()
b.enque(2) # put the element into the queue
b.enque(3)
b.enque(4)
b.enque(5)
print(b.data)
b.deque()# # remove the first element that we have put in the queue
print(b.data)
Это приведет к следующим результатам.
[2, 3, 4, 5]
[3, 4, 5]
Стек
В английском словаре слово stack означает расположение объектов друг над другом. Стек — это линейная структура данных, в которой операции выполняются в определенном порядке. Этот порядок может быть LIFO (Last In First Out) или FILO (First In Last Out).
В следующей программе мы реализуем его как функции add и remove. Мы объявляем пустой список и используем методы append() и pop() для добавления и удаления элементов данных.
Перемещение в стек
Пример
class Stack:
def __init__(self):
self.stack = []
def add(self, dataval):
# Use list append method to add element
if dataval not in self.stack:
self.stack.append(dataval)
return True
else:
return False
# Use peek to look at the top of the stack
def peek(self):
return self.stack[-1]
AStack = Stack()
AStack.add("Mon")
AStack.add("Tue")
AStack.peek()
print(AStack.peek())
AStack.add("Wed")
AStack.add("Thu")
print(AStack.peek())
Вывод
Tue
Thu
POP из стека
Поскольку мы знаем, что из стека можно удалить только самый верхний элемент данных, мы реализуем программу на языке python, которая это делает. Функция remove в следующей программе возвращает самый верхний элемент. Мы проверяем верхний элемент, сначала вычисляя размер стека, а затем используем встроенный метод pop(), чтобы узнать самый верхний элемент.
class Stack:
def __init__(self):
self.stack = []
def add(self, dataval):
# Use list append method to add element
if dataval not in self.stack:
self.stack.append(dataval)
return True
else:
return False
# Use list pop method to remove element
def remove(self):
if len(self.stack) <= 0:
return ("No element in the Stack")
else:
return self.stack.pop()
AStack = Stack()
AStack.add("Mon")
AStack.add("Tue")
AStack.add("Wed")
AStack.add("Thu")
print(AStack.remove())
print(AStack.remove())
Выход:
Thu
Wed
Связанный список
Связанный список — это линейная структура данных, в которой элементы не хранятся в смежных областях памяти. Элементы в связанном списке связаны между собой с помощью указателей, как показано на рисунке ниже:
Теперь создадим связный список
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
Обход связанного списка
Односвязные списки можно просматривать только в прямом направлении, начиная с первого элемента данных. Мы просто печатаем значение следующего элемента данных, присваивая указатель следующего узла текущему элементу данных.
Пример
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
list.listprint()
Выход:
Mon
Tue
Wed
Вставка в связный список
Вставка элемента в связный список подразумевает переназначение указателей от существующих узлов к вновь вставляемому узлу. В зависимости от того, вставляется ли новый элемент данных в начало, середину или конец связанного списка, мы имеем следующие сценарии.
Вставка в начале
При этом следующий указатель нового узла данных указывается на текущую голову связанного списка. Таким образом, текущая голова связанного списка становится вторым элементом данных, а новый узел становится головой связанного списка.
Пример
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
def AtBegining(self,newdata):
NewNode = Node(newdata)
# Update the new nodes next val to existing node
NewNode.nextval = self.headval
self.headval = NewNode
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
list.headval.nextval = e2
e2.nextval = e3
list.AtBegining("Sun")
list.listprint()
Выход:
Sun
Mon
Tue
Wed
Вставка в конец
При этом указатель текущего последнего узла связанного списка направляется на новый узел данных. Таким образом, текущий последний узел связанного списка становится вторым последним узлом данных, а новый узел становится последним узлом связанного списка.
Пример
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
# Function to add newnode
def AtEnd(self, newdata):
NewNode = Node(newdata)
if self.headval is None:
self.headval = NewNode
return
laste = self.headval
while(laste.nextval):
laste = laste.nextval
laste.nextval=NewNode
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
list.headval.nextval = e2
e2.nextval = e3
list.AtEnd("Thu")
list.listprint()
Выход
Mon
Tue
Wed
Thu
Вставка между двумя узлами данных
Это предполагает изменение указателя определенного узла, чтобы он указывал на новый узел. Это возможно путем передачи как нового узла, так и существующего узла, после которого будет вставлен новый узел. Поэтому мы определяем дополнительный класс, который будет менять следующий указатель нового узла на следующий указатель среднего узла. Затем присвоим новому узлу следующий указатель среднего узла.
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
# Function to add node
def Inbetween(self,middle_node,newdata):
if middle_node is None:
print("The mentioned node is absent")
return
NewNode = Node(newdata)
NewNode.nextval = middle_node.nextval
middle_node.nextval = NewNode
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Thu")
list.headval.nextval = e2
e2.nextval = e3
list.Inbetween(list.headval.nextval,"Fri")
list.listprint()
Выход:
Mon
Tue
Fri
Thu
Удаление элемента
Мы можем удалить существующий узел, используя ключ для этого узла. В приведенной ниже программе мы находим предыдущий узел узла, который должен быть удален. Затем указываем указатель этого узла на следующий узел узла, который должен быть удален.
Пример
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class SLinkedList:
def __init__(self):
self.head = None
def Atbegining(self, data_in):
NewNode = Node(data_in)
NewNode.next = self.head
self.head = NewNode
# Function to remove node
def RemoveNode(self, Removekey):
HeadVal = self.head
if (HeadVal is not None):
if (HeadVal.data == Removekey):
self.head = HeadVal.next
HeadVal = None
return
while (HeadVal is not None):
if HeadVal.data == Removekey:
break
prev = HeadVal
HeadVal = HeadVal.next
if (HeadVal == None):
return
prev.next = HeadVal.next
HeadVal = None
def LListprint(self):
printval = self.head
while (printval):
print(printval.data),
printval = printval.next
llist = SLinkedList()
llist.Atbegining("Mon")
llist.Atbegining("Tue")
llist.Atbegining("Wed")
llist.Atbegining("Thu")
llist.RemoveNode("Tue")
llist.LListprint()
Выход:
Thu
Wed
Mon
Алгоритмы
Алгоритмы — это инструкции, которые формулируются в конечном и последовательном порядке для решения проблем.
Слово алгоритм происходит от имени персидского математика IX века Мухаммада ибн Муса аль-Хваризми, чье имя было латинизировано как Algorithmi. Аль-Хваризми был также астрономом, географом и ученым Дома мудрости в Багдаде.
Как вы уже знаете, алгоритмы — это инструкции, которые формулируются в конечном и последовательном порядке для решения проблем.
Когда мы пишем алгоритм, мы должны знать, в чем именно заключается проблема, определить, где нам нужно начать и остановиться, и сформулировать промежуточные шаги.
Существует три основных подхода к решению алгоритмов:
*Divide et Impera (также известный как «разделяй и властвуй») → он делит проблему на подчасти и решает каждую из них отдельно
*Динамическое программирование → он делит задачу на подчасти, запоминает результаты подчастей и применяет их к аналогичным задачам.
*Жадные алгоритмы → предполагают выполнение самого простого шага при решении задачи, не заботясь о сложности последующих шагов.
Алгоритм обхода дерева
Деревья в python — это нелинейные структуры данных. Они характеризуются корнями и узлами. Я беру класс, который я построил ранее для бинарного дерева.
Обход дерева означает посещение каждого узла, присутствующего в дереве, ровно один раз, чтобы обновить или проверить их.
# create the class Node and the attrbutes
class Node:
def __init__(self, letter):
self.childleft = None
self.childright = None
self.nodedata = letter
# create the nodes for the tree
root = Node('A')
root.childleft = Node('B')
root.childright = Node('C')
root.childleft.childleft = Node('D')
root.childleft.childright = Node('E')
Существует три типа обхода дерева:
* Обход в порядке → означает посещение левого узла, затем корня, а затем правых узлов.
Здесь D — самый левый узел, где ближайшим корнем является B. Справа от корня B находится E. Теперь левое поддерево завершено, поэтому я двигаюсь к корневому узлу A, а затем к узлу C.
def InOrd(root):
if root:
InOrd(root.childleft)
print(root.nodedata)
InOrd(root.childright)
InOrd(root)
Выход:
D
B
E
A
C
*Предварительный обход → означает посещение корневого узла, затем левых узлов, а затем правых узлов.
В данном случае я перехожу к корневому узлу A, затем к левому дочернему узлу B и к поддочернему узлу D. После этого я могу перейти к узлам E и затем C.
def PreOrd(root):
if root:
print(root.nodedata)
PreOrd(root.childleft)
PreOrd(root.childright)
PreOrd(root)
выход:
A
B
D
E
C
*Порядковый обход → означает посещение левых узлов, затем правых узлов, а затем корневого узла.
Я иду к самому левому узлу D, затем к правому узлу E. Затем я могу перейти от левого узла B к правому узлу C. Наконец, я двигаюсь к корневому узлу A.
def PostOrd(root):
if root:
PostOrd(root.childleft)
PostOrd(root.childright)
print(root.nodedata)
PostOrd(root)
выход:
D
E
B
C
A
Алгоритм сортировки
Алгоритм сортировки используется для сортировки данных в некотором заданном порядке. Его можно классифицировать на Merge Sort и Bubble Sort.
*Сортировка слиянием → она следует правилу divide et Impera. Заданный список сначала делится на меньшие списки, сравниваются соседние списки, а затем они упорядочиваются в нужной последовательности. Таким образом, в итоге из неупорядоченных элементов на входе мы должны получить упорядоченные элементы на выходе. Ниже приведен код с описанием каждого шага.
def merge_sort(ourlist, left, right): #left and right corresponds to starting and ending element of ourlist
if right -left > 1: # check if the length of ourlist is greater than 1
middle = (left + right) // 2 # we divide the length in two parts
merge_sort(ourlist, left, middle) # recursevely I call the merge_sort function from left to middle
merge_sort(ourlist, middle, right) # then from middle to right
merge_list(ourlist, left, middle, right) # finally I create ourlist in complete form(left, middle and right)
def merge_list(ourlist, left, middle, right):# I create the function merged_list
leftlist = ourlist[left:middle] # I define the leftlist
rightlist = ourlist[middle:right] # I define the right list
k = left # it is the the temporary variable
i = 0 # this variable that corespond to the index of the first group help me to iterate from left to right
j = 0 # this variable that corespond to the index of the second group help me to iterate from left to right
while (left + i < middle and middle+ j < right): # the condition that I want to achive before to stop my iteration
if (leftlist[i] <= rightlist[j]): #if the element in the leftlist is less or equal to the element in the rightlist
ourlist[k] = leftlist[i] # In this case I fill the value of the leftlist in ourlist with index k
i = i + 1 #now I have to increment the value by 1
else: # if the above codition is not match
ourlist[k] = rightlist[j] # I fill the rightlist element in ourlist with index k
j = j + 1 # I increment index j by 1
k = k+1 # now I increment the value of k by 1
if left + i < middle: # check if left + i is less than middle
ourlist[k] = leftlist[i] # I place all elements of my leftlist in ourlist
i = i + 1
k = k + 1
else: # otherwise if my leftlist is empty
while k < right: # untill k is less then right
ourlist[k] = rightlist[j] # I place all elements of rightlist in ourlist
j = j + 1
k = k + 1
ourlist = input('input - unordered elements: ').split() # insert the input and split
ourlist = [int(x) for x in ourlist]
merge_sort(ourlist, 0, len(ourlist))
print('output - ordered elements: ')
print(ourlist)
Выход:
input - unordered elements: 15 1 19 93
output - ordered elements:
[1, 15, 19, 93]
*Пузырьковая сортировка → сначала сравнивает, а затем сортирует соседние элементы, если они расположены не в заданном порядке.
def bubble_sort(ourlist): # I create my function bubble_sort with the argument called ourlist
b=len(ourlist)-1 # for every list, I will have a minus 1 iteration
for x in range(b): # for each element in the range of b, I check if they are ordered or not
for y in range(b-x):
if ourlist[y]>ourlist[y+1]: # if one element is greater than the nearest elemnt in the list
ourlist[y],ourlist[y+1]=ourlist[y+1],ourlist[y] # I have to swap the elemnts, in other words
# I exchange the position of the two elements
return ourlist
ourlist=[15,1,9,3]
bubble_sort(ourlist)
Выход:
[1, 3, 9, 15]
*Insertion Sort → выбирает один элемент из заданного списка за один раз и помещает его точно в то место, куда он должен быть помещен.
def ins_sort(ourlist):
for x in range(1, len(ourlist)): # loop for each element starting from 1 to the length of our list
k = ourlist[x] # element with the index x
j = x-1 # j is the index previus the index x
while j >=0 and k < ourlist[j]: # untill each elermnt of the list are less than their previous element my loop don't stop
ourlist[j+1] = ourlist[j] # the elemnt indexed before the element considered is set to the next one index
j -= 1 # I decrement index j by 1
ourlist[j+1] = k # now k is the element in the index j+1
return ourlist
ourlist = [15, 1, 9, 3]
ins_sort(ourlist)
выход:
[1, 3, 9, 15]
Существуют и другие алгоритмы сортировки, такие как сортировка выбором и сортировка оболочкой.
Алгоритмы поиска
*Алгоритмы поиска используются для поиска некоторых элементов, присутствующих в заданном наборе данных. Существует множество типов алгоритмов поиска, таких как линейный поиск, бинарный поиск, экспоненциальный поиск, интерполяционный поиск и так далее. В этом разделе мы рассмотрим линейный поиск и бинарный поиск.
*Линейный поиск → в одномерном массиве нужно найти определенный ключевой элемент. На вход подается группа элементов и ключевой элемент, который мы хотим найти. Таким образом, мы должны сравнить ключевой элемент с каждым элементом группы. В следующем коде мы попытаемся найти элемент 27 в нашем списке.
def lin_search(ourlist, key):
for index in range(0, len(ourlist)):
if (ourlist[index] == key):
return index
else:
return "not fund"
ourlist = [15, 1, 9, 3]
lin_search(ourlist, 27)
Выход:
'not fund'
*Двоичный поиск → в этом алгоритме мы предполагаем, что список расположен в порядке возрастания. Таким образом, если значение ключа поиска меньше, чем элемент в середине списка, мы сужаем интервал до нижней половины. В противном случае мы сужаем интервал до верхней половины. Мы продолжаем проверку до тех пор, пока значение не будет найдено или список не станет пустым.
def bin_search(ourlist, key):
left = 0 # I assign left position to zero
right = len(ourlist)-1 # I assign right position by defining the length of ourlist minus one
matched = False
while(left<=right and not matched): # the loop will continue untill the left element is less or equal to the right element and the matched is True
mid = (left+right)//2 # I find the position of the middle element
if ourlist[mid] == key: # if the middle element correponds to the key element
matched = True
else: #otherwise
if key < ourlist[mid]: # if key element is less than the middle element
right = mid - 1 #I assign the position of the right element as mid - 1
else: #otherwise
left = mid + 1 #left position will become the middle position plus 1
return matched
print(bin_search([1, 3, 9, 15], 17))
print(bin_search([1, 3, 9, 15], 3))
выход:
False
True