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

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

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

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

Самый известный случай структурирования данных в жизни — это запомнить номер телефона. Например, есть телефон сплошным текстом: 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;

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

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

   

Хеш-таблица

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

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

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

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

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

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

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

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

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

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

• и др.

   

Заключение

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