Другое

Что такое структурирование данных? Вводный инструктаж для чайников

Lorem ipsum dolor

Структурирование данных — это понятие, которое затрагивает не только сферу программирования. Под структурированием понимают процесс, при котором определенные данные объединяются по свойствам или по смыслу в общую группу или несколько групп. Делается это в разных сферах примерно для одних и тех же действий:

  • чтобы было легче запомнить данные;

  • для того, чтобы было удобнее с ними работать.

Самый известный случай структурирования данных в жизни — это запомнить номер телефона. Например, есть телефон сплошным текстом: 89856451311. Запомнить его таким образом будет немного сложно, но если задать ему структуру и запоминать «частями», то будет намного легче: 8-985-645-13-11. 

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

Структурирование данных в программировании

Структуризация данных в программировании занимает важную роль. Жаль, но многие начинающие программисты игнорируют этот момент в процессе изучения. Это незнание не критично во многих сферах программирования, но понимание, что такое структурирование данных, должно быть.

Структурирование данных в программировании — это создание неких «контейнеров», хранящих информацию в определенном формате. Выбранный формат структуры данных задает информации определенные свойства, которые отделяют ее от других структур и определяют варианты сценариев применения этой информации.

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

Виды структурирования данных в программировании

Несколько основных структур данных в программировании:

  1. Массив.

  2. Связанный список.

  3. Стек.

  4. Очередь.

  5. Граф.

  6. Дерево.

  7. Хеш-таблица.

 

Массив

Массив — это самый распространенный вид структуры данных в программировании. Часто на его основе строятся другие виды структур:

  • стек;

  • очередь и др.

Массив образуется из множества элементов. Каждому элементу присваивается собственный индекс — это целое неотрицательное число. Во многих языках программирования исчисление индексов начинается с «0» и далее в порядке возрастания. То есть первому элементу массива присваивается индекс 0. Из-за этого многие начинающие программисты очень путаются.

Массив может быть 2-х видов:

  1. Одномерный — простая линейная структура.

  2. Многомерный имеет сложную структуру и включает в себя другие массивы.

С массивом можно проводить следующие операции:

  • получать элементы массивов по нужному индексу;

  • вставлять элементы массива по нужному индексу;

  • узнать общее число элементов массива;

  • удалять элементы массивов по нужному индексу;

  • обновлять значение или свойство элемента массива по нужному индексу;

  • поиск нужного элемента массива по указанному свойству;

  • и др.

Массивы применяются:

  • для создания более сложных структур;

  • при хранении простых и связанных между собой данных;

  • при создании алгоритмов сортировки;

 

Связанный список

Связанный список представляет собой последовательную структуру из определенных элементов. Каждый отдельный такой элемент называется узлом и имеет 2 свойства:

  1. хранимые данные;

  2. информация о следующем после него узле.

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

Связанные списки бывают:

  1. Односвязанными. Обойти такие узлы можно только в одном направлении.

  2. Двусвязанными. Обойти такие узлы можно в двух направлениях, потому что в узлах присутствует еще один указатель, который содержит информацию о предыдущем узле.

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

Со связанным списком можно проводить следующие операции:

  • добавить узел в список;

  • удалить узел в начале списка или определив его по какому-то ключу;

  • отобразить весь список;

  • найти нужный узел в списке;

  • обновить значение узла по какому-то ключу.

Связанные списки применяются:

  • при создании более сложных структур;

  • при создании слайд-шоу;

  • во время переключения вкладок в операционных системах.

     

Стек

Стеком называется структурирование данных в виде линейной структуры, но с применением массивов или связанных списков. В стеке есть важный принцип: любой элемент, который попал в стек последним, всегда покидает его первым.

Со стеком можно проводить следующие операции:

  • вставить элемент в верхнюю часть стека;

  • удалить элемент из верхней части стека;

  • просмотреть элемент верхней части стека;

  • проверить стек на наличие пустоты.

Стеки применяются:

  • при реализации навигации браузера;

  • когда реализуется рекурсия;

  • когда нужно выделить память, опираясь на стек.

     

Очередь

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

Если стек по своим принципам напоминает стопку книг, то очередь — это как в реальная людская очередь.

С очередью можно проводить следующие операции:

  • вставлять элемент в конец очереди;

  • удалять элемент из начала очереди;

  • возвращать элемент из начала очереди, не удаляя его;

  • проверять содержимое очереди.

Очередь применяется:

  • когда нужно обслуживать несколько запросов в одном ресурсе;

  • когда нужно управлять потоком в многопоточной среде;

  • балансировать нагрузки.

     

Граф

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

  1. ориентированные — когда все ребра вершин указывают направления этих самых вершин;

  2. не ориентированные — когда ребра вершин не указывают направления, поэтому обход вершин можно осуществить с любого направления.

Графы можно обойти 2-мя основными алгоритмами:

  1. Алгоритм поиска в ширину. Это кратчайший путь, который основывается на вершинах граф.

  2. Алгоритм поиска в глубину. Этот алгоритм основывается на ребрах граф.

С графами можно проводить следующие операции:

  • добавлять еще одну вершину;

  • добавлять ребро между вершинами;

  • показать вершину;

  • определить стоимость пути обхода граф.

Графы применяются:

  • при вычислениях в потоках;

  • когда распределяются ресурсы операционной системы;

  • поиск друзей в соцсетях;

  • поиск кратчайшего пути в Гугл-картах.

     

Дерево

Дерево — это сложное структурирование данных, которое состоит из вершин и соединяющих их ребер. Такая структура данных часто используется в сложнейших алгоритмах и в искусственном интеллекте. Структура дерева чем-то напоминает графы, но в то же время имеет отличия. Поэтому в сети можно встретить такой спор: дерево это графы или не графы?

С деревом можно осуществить следующие операции:

  • вставить элемент в дерево;

  • искать нужный элемент;

  • обойти дерево прямым способом;

  • применить центрированный способ обхода;

  • применить обратный способ обхода.

Деревья применяются:

  • внутри виртуальной машины Java;

  • когда нужно представить файловую систему компьютера;

  • химическая формула — это тоже дерево.

     

Хеш-таблица

Это особое структурирование данных в виде таблицы, где все данные хранятся в парах связанных значений «ключ+значение». То есть каждому значению соответствует свой ключ.

Процесс генерации ключей для значений в таблице называется хешированием. Хеширование проводится специальной хеш-функцией.

С хеш-таблицами можно осуществить следующие операции:

  • найти элемент в хеш-таблице;

  • вставить элемент в хеш-таблицу;

  • удалить элемент из хеш-таблицы.

Хеш-таблицы применяются:

  • когда нужно индексировать базы данных;

  • при проверке пары логин/пароль;

  • в реализации «кэша»;

  • и др.

     

Заключение

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

Схожие статьи

Как настроить AirPrint на принтере HP, каким образом наладить печатать с его помощью
Другое

Как настроить AirPrint на принтере HP, каким образом наладить печатать с его помощью

Интересная функция: искусственный интеллект от Гугл угадывает рисунок
Другое

Интересная функция: искусственный интеллект от Гугл угадывает рисунок

Лучшие вузы для программистов в России: какой из них выбрать?
Другое

Лучшие вузы для программистов в России: какой из них выбрать?

Система умного поиска: что это, как оно работает и как можно настроить
Другое

Система умного поиска: что это, как оно работает и как можно настроить