Введение в структуры данных Python - хеш-карта, дерево, граф

В этой статье мы рассмотрим нелинейные структуры данных в Python, такие как Tree, Hash-map и Graph.

Предварительное условие

Вы должны иметь базовые знания языка программирования Python.

Весь код для этой статьи доступен в моем репозитории GitHub.

В первой части этой статьи мы рассмотрели основы структур данных и линейных структур данных, таких как стек, очередь, связанный список, массивы.

Теперь в этой статье мы рассмотрим нелинейные структуры данных, такие как Tree, Hash-map и Graph.

Что такое нелинейные структуры данных?

Структура данных, в которой данные не хранятся в линейном формате, таком как массивы или стек. Этот тип структуры данных известен как нелинейные структуры данных.

Нелинейная структура данных - это рекурсивный тип структуры данных.

В нелинейных структурах данных мы не можем перемещаться по структуре данных в линейном формате; есть несколько уровней для хранения данных.

Реализация нелинейных структур данных немного сложнее, чем линейных структур данных.

Существуют различные типы нелинейных структур данных, но мы рассмотрим -

1. Хеш-карта
2. Дерево
3. График

Нелинейные структуры данных

1. Хеш-карта -

По сути, Hash-map - это тип структуры данных пары ключ-значение, в которой ключ вычисляется с использованием функции Hash, а затем эти данные сохраняются как ключ (вычисляется функцией Hash).

Теперь сначала мы должны понять, что такое хеш-функция. Таким образом, хеш-функция - это функция, которая будет вычислять ключ с использованием любой математической функции, чтобы мы могли хранить данные в ключевой позиции. Здесь математическая функция может быть чем угодно. Не существует фиксированной функции для поиска ключа с помощью хеш-функции.

Но основным недостатком этой хеш-функции является то, что хеш-функция возвращает один и тот же ключ для двух разных данных. Таким образом, в этой ключевой позиции произойдет столкновение. Это главный недостаток хеш-функций.

Есть разные способы справиться с этим столкновением. Мы справимся с этим, создав список для этого ключа, если хеш-функция возвращает один и тот же ключ для разных данных. А затем добавьте данные в список этого конкретного ключа.

Хеш-таблицы обычно реализуются с использованием массивов.

Основные операции, которые вы можете выполнять на Hash-карте

1. Insert - вставить элемент в хеш-карту
2. Удалить - удалить элемент из хеш-карты
3. Get Item - получить элемент из хеш-карты с помощью ключей

Реализация хеш-карты с использованием массивов -

class Hashmap:
    def __init__(self):
        self.MAX = 100
        self.arr = [[] for i in range(self.MAX)]
        
    def get_hash(self,key):
        hash_key = 0
        for char in key:
            hash_key += ord(char)
        return hash_key % 100
    def add(self,key,value):
        hash_key = self.get_hash(key)
        found = False
        
        for index,element in enumerate(self.arr[hash_key]):
            if element[0] == key and len(element) == 2:
                self.arr[hash_key][index] = (key,value)
                found = True
                break
        if not found:
            self.arr[hash_key].append((key,value))
                
    def get(self,key):
        hash_key = self.get_hash(key)
        for element in self.arr[hash_key]:
            if element[0] == key:
                return element[1]
            
    def __delitem__(self,key):
        hash_key = self.get_hash(key)
        for index,element in enumerate(self.arr[hash_key]):
            if element[0] == key:
                del self.arr[hash_key][index]
            
    def print_hm(self):
        values = [i for i in self.arr if i != []]
        return values

Объяснение кода -

• Прежде всего, мы должны создать класс с именем Hashmap, и в этом классе мы должны инициализировать список с именем self.arr размера self.MAX. И в этом self.arr у нас будет пустой вложенный список (Список в списке, поэтому, если self.MAX равно 10, в self.arr будет 10 пустых списков).
• Теперь мы реализуем самый важный метод в структурах данных хэш-карты - get_hash. Этот метод принимает ключ в качестве аргумента и вычисляет и возвращает hash_key с помощью функции ord (эта функция возвращает числовое значение для заданного строкового ключа). Таким образом, используя этот метод, вычисляются все hash_key.
• Теперь следующий метод - add , который используется для добавления элемента в хеш-карту. Этот метод принимает в качестве параметра data и key. Во-первых, этот метод вычислит хеш-значение (или хеш-ключ) для данного параметра key с помощью функции get_hash. После этого мы пройдемся по всем спискам, чтобы найти эту hash_key позицию и проверить, есть ли какие-либо элементы, добавленные в этой hash_key перед этими данными. И если в данном списке hash_key есть элемент, то мы добавим новый data как форму кортежа в этот список. Этот кортеж будет включать key и data. И если в этом hash_key нет данных, мы просто добавим эти данные в этот список hash_key.
• Теперь следующий метод - get , который используется для извлечения элементов из хэш-карты. Этот метод примет key в качестве параметра. Во-первых, этот метод вычислит хеш-значение (или hash_key) для данного ключевого параметра с помощью функции get_hash. После этого мы пройдемся по списку данной hash_key позиции и проверим, есть ли какие-либо элементы в этом списке, и если есть (key, data) кортеж, тогда он вернет data для данного key параметра.
• Далее идет __delitem__. Этот метод принимает ключ в качестве параметра и, как и все другие методы, вычисляет hash_key с использованием метода get_hash. После этого он пройдется по списку с заданным hash_key, найдет кортеж с заданным параметром key и удалит этот элемент.
• И print_hm method не требует пояснений, поэтому не нужно его описывать.

2. Дерево—

Древовидная структура данных - это иерархический тип структуры данных, в котором есть главный корневой узел, который имеет два поля - данные и дочерние элементы. В поле данных он хранит данные, а в дочернем поле он хранит свои дочерние узлы.

Итак, в основном дерево состоит из двух основных частей - корневого узла и поддерева.

Как следует из названия, деревья имеют ту же структуру, что и настоящее дерево, но только в перевернутом виде.

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

Есть много видов деревьев -

1. Общее дерево (это дерево, у родительского узла которого может быть столько дочерних элементов, сколько мы хотим добавить).
2. Двоичное дерево (в этом типе дерева родительский узел может иметь только 2 или менее 2 дочерних).
3. Двоичное дерево поиска (это дерево такое же, как двоичное дерево; единственная разница в том, что левый дочерний узел родительского узла может иметь значение меньше, чем его родительский узел, а правый дочерний узел может иметь значение больше, чем его родительский).

Есть много других деревьев, таких как красно-черное дерево, AVL-дерево, N-арное дерево и т. Д.

Основные операции, которые вы можете выполнять с деревом -

1. Добавить ребенка (добавить ребенка к узлу)
2. Удалить ребенка (удалить ребенка из узла)
3. Печать (Распечатать все дерево)
4. Get Level (Получить уровень узла)

class TreeNode:
    def __init__(self,data):
        self.data = data
        self.parent = None
        self.children = []
#    For Adding child to tree
    def add_child(self,child):
        child.parent = self
        self.children.append(child)
    
#    For Getting level to any node
    def get_level(self):
        level = 0
        p=self.parent
        while p:
            p=p.parent
            level+=1
        return level
#    For Printinf whole tree
def print_tree(self):
        spaces = " " * self.get_level() * 3
        prefix = spaces+"|---" if self.parent else ''
        print(prefix+self.data)
        if self.children:
            for child in self.children:
                child.print_tree()
    #    For Deleting child from tree
    def delete_child(self,child):
        if child in self.children:
            self.children.remove(child)
            print(f"{child.data} Removed from f{child.parent.data}")
        else:
            print(f'There is no {child.data} in Tree')
#Example for making code explanation Easy
def electronincs_tree():
    root = TreeNode('Electronics')
    
    hp = TreeNode('HP')
    mac = TreeNode('Mac-Book')
    dell = TreeNode('Dell')
    laptops = TreeNode('Laptops')
    laptops.add_child(hp)
    laptops.add_child(mac)
    laptops.add_child(dell)
    
    motorola = TreeNode('Motorola')
    apple = TreeNode('Apple')
    nokia = TreeNode('Nokia')
    mobiles = TreeNode('Mobiles')
    mobiles.add_child(motorola)    
    mobiles.add_child(apple)
    mobiles.add_child(nokia)
    
    reconnect = TreeNode('Reconnect')
    lg = TreeNode('LG')
    samsung = TreeNode('Samsung')
    tvs = TreeNode('TVs')
    tvs.add_child(reconnect)    
    tvs.add_child(lg)
    tvs.add_child(samsung)
    
    root.add_child(laptops)
    root.add_child(mobiles)    
    root.add_child(tvs)
    
    root.print_tree()
    
    tvs.delete_child(lg)
    root.print_tree()

electronincs_tree()

Объяснение кода -

• Итак, в этом объяснении кода я использовал пример, иначе было бы очень сложно объяснить, используя только код.
• Итак, сначала мы создадим класс для узла дерева. Здесь мы инициализируем три переменные self.data, self.parent, self.children, используя метод __init__. Здесь self.data будет хранить данные этого узла дерева. self.parent сохранит ссылку на родительский узел этого узла дерева, а self.children будет хранить список всех узлов дочернего дерева текущего узла дерева.
• Теперь первый метод, который мы реализуем, - это add_child, который имеет один параметр с именем child. Этот метод просто добавит новый дочерний элемент к родительскому узлу дерева (например, в методе electronincs_tree сначала мы создали несколько экземпляров узла дерева, а затем добавляем этот узел дерева к их родительским узлам с помощью метода add_child).
• Второй метод, который мы реализуем, - это delete_child, который также имеет один параметр с именем child. Во-первых, этот метод проверяет, есть ли у родительского узла дерева дочерний элемент, который мы хотим удалить; и если да, то он удалит его из списка self.children. И если нет дочернего элемента, который мы хотим удалить, он напечатает, что «нет такого дочернего элемента в self.children списке» (например, в методе electronincs_tree мы удаляем lg дерево узел из tvs узла родительского дерева).
• Теперь реализуем метод get_level. Этот метод не принимает никаких параметров. Этот метод вернет уровень узла дерева, по которому мы вызываем этот метод. Таким образом, этот метод будет создавать одну переменную с именем level и присваивать значение 0, а затем мы создадим цикл while и переберем все родительские элементы данного узла дерева, и если узел дерева имеет родительский узел дерева, тогда значение level будет увеличивается на 1. И цикл завершится, когда мы достигнем вершины дерева, то есть корневого узла дерева. А затем мы вернем этот level.
• Теперь последний метод - это метод print_tree. Этот метод просто печатает все иерархии узлов, чтобы мы могли визуализировать все дерево. Этот метод определяет иерархию методом get_level. Затем назначьте соответствующий префикс для данных, чтобы распечатать их в иерархии в соответствии с уровнем узла дерева.

3. График—

График - это нелинейная структура данных, состоящая из вершины и ребра. Здесь вершина также называется узлом. В структуре данных Graph вершина или узел содержат данные или какое-то значение для сохранения. И ребра соединяют эти вершины. И, комбинируя одну или несколько вершин и ноль или несколько ребер, мы получаем структуру данных графа.

Графические и древовидные структуры данных являются наиболее распространенными и любимыми структурами данных, которые задают при собеседовании.

Существует так много проблем, которые мы можем решить с помощью структуры данных Graph.

Например:

1. Нахождение кратчайшего пути между точкой А и точкой Б.
2. Поиск связи между двумя пользователями в социальных сетях (Facebook, LinkedIn).
3. Поиск оптимального маршрута в компьютерных сетях.
4. Поиск лучшего маршрута между двумя городами или местами.

Есть еще много проблем, которые можно решить с помощью структуры данных графа.

Кроме того, существует много типов графиков, таких как Null Graph, Infinite Graph, но мы не можем охватить все о графиках в этой статье, поэтому здесь - это ссылка, чтобы узнать больше об этом.

Объяснение кода -

• Теперь в этом коде мы создали класс с именем Graph , который принимает параметры edges as в качестве списка кортежей. Здесь routes variable - это пример переменной Edge, которая имеет список кортежей, в которых первое значение кортежа представляет начало края, а второе значение представляет конец этого конкретного края ((“Mumbai”, “Paris”) Mumbai - начало этого края и Париж является концом этого края, и все города представлены в виде узлов).
• Теперь в __init__ method этого класса мы создадим переменную graph_dict, которая представляет график в виде словаря. Итак, в этом методе мы пройдемся по всем кортежам списка edges и соответственно создадим график. Он проверит, добавлен ли какой-либо другой элемент начала ребра к graph_dict variable или нет, и если он добавлен, то добавит конечное значение к graph_dict[start]. И если значение start добавляется впервые к graph_dict, тогда будет создана новая пара "ключ-значение".
• Теперь второй метод, который мы реализовали в классе Graph, - это метод get_paths, который принимает в качестве параметров три аргумента - start, end, paths. Здесь start обозначает начало пути, от которого мы хотим найти путь, а end обозначает конец пути, которым путь должен заканчиваться или заканчиваться. Этот метод найдет все пути от начала до конца.
• Во-первых, этот метод проверяет, совпадают ли start и end variables, и если да, то он просто вернет start variable в качестве пути. Этот метод также проверяет, есть ли start node в списке ключей graph_dict. А если start node нет в списке ключей graph_dict, это означает, что нет пути от start к end . Итак, тогда этот метод просто вернет пустой список. В противном случае этот метод создаст пустой список с именем paths. В разделе for loop этого метода мы пройдемся по всем смежным узлам узла start и на этом соседнем узле мы будем использовать рекурсию, чтобы найти путь от соседнего узла к узлу end, а затем добавим его к основная path переменная. И он добавит этот путь в список paths, а в конце метода мы вернем список paths, содержащий все пути от start до end.

Заключение

Итак, в этой статье мы рассмотрели основы структур данных и нелинейных структур данных.

Если вы пропустили первую часть этой статьи, вот ссылка.

Надеюсь, вам понравилось читать и учиться.

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

Больше контента на plainenglish.io