Структурирование данных — это понятие, которое затрагивает не только сферу
программирование. Под структурированием понимают процесс, при котором
определенные данные объединяются по свойствам или смыслу в общую группу или
несколько групп. Делается это в разных сферах примерно для одних и тех же
действий:
- чтобы было легче запомнить данные;
- для того, чтобы было удобнее с ними работать.
Самый известный случай структурирования данных в жизни — это запомнить номер
телефона. Например, есть телефон сплошным текстом: 89856451311. Запомнить его
таким образом будет немного сложно, но если задать ему структуру и запоминать
«частями», то будет намного легче: 8-985-645-13-11.
Примерно такая же ситуация и в программировании. Только не столько для того,
чтобы запоминать данные, а скорее, чтобы удобно были с ними работать.
Структурирование данных в программировании
Структуризация данных в программировании занимает важную роль. Жаль, но
многие начинающие программисты, игнорируют этот момент в процессе изучения.
Это незнание не критично во многих сферах программирования, но понимание что
такое структурирование данных должно быть.
Структурирование данных в программировании — это создание определенных
«контейнеров», хранящих информацию в определенном формате. Выбранный
формат структуры данных, задает информации определенные свойства, которые
выделяют ее от других структур и определяют варианты сценариев применения этой
информации.
В программировании можно выделить несколько важных элементов
структурирования данных, которые нужно понимать.
Виды структурирования данных в программировании
Несколько основных структур данных в программировании:
- Массив.
- Связанный список.
- Стек.
- Очередь.
- Граф.
- Дерево.
- Хэш-таблица.
Массив
Массив — это самый распространенный вид структуры данных в программировании.
Часто на его основе строятся другие виды структур:
- стек,
- очередь и др.
Массив образуется из множества элементов. Каждому элементу присваивается
собственный индекс — это целое неотрицательно число. Во многих языках
программирования исчисление индексов начинается с «0» и далее в порядке
возрастания. То есть первому элементу массив, присваивается индекс 0. Из-за этого
многие начинающие программисты очень путаются.
Массив может быть 2-х видов:
- Одномерный — простая линейная структура.
- Многомерный – имеют сложную структуру и включают в себя другие массивы.
С массивом можно проводить следующие операции:
- получать элементы массивов по нужному индексу;
- вставлять элементы массива по нужному индексу;
- узнать общее число элементов массива;
- удалять элементы массивов по нужному индексу;
- обновлять значение или свойство элемента массива по нужному индексу;
- поиск нужного элемента массива по указанному свойству;
- и др.
Массивы применяются:
- для создания более сложных структур;
- при хранении простых и связанных между собой данных;
- при создании алгоритмов сортировки;
Связанный список
Связанный список представляет собой последовательную структуру из определенных элементов. Каждый отдельный такой элемент называется узлом и
имеет 2 свойства:
- хранимые данные;
- информацию о следующем после него узле.
То есть, сам узел содержит какие-то собственные данные и знает кто у него по
соседству. Поэтому список и называется связанным, потому что все узлы связаны
между собой.
Связанные списки бывают:
- Односвязанными. Обойти такие узлы можно только в одном направлении.
- Двусвязанные. Обойти такие узлы можно как в двух направлениях, потому что
в узлах присутствует еще один указатель, который содержит информацию о
предыдущем узле. - Связанные по кругу. В этих списках начальный указатель одного узла
указывает на конечный указатель другого, а конечный указатель указывает на
начальный.
Со связанным списком можно проводить следующие операции:
- добавить узел в список;
- удалить узел в начале списка или определив его по какому-то ключу;
- отобразить весь список;
- найти нужный узел в списке;
- обновить значение узла по какому-то ключу.
Связанные списки применяются:
- при создании более сложных структур;
- при создании слайд-шоу;
- во время переключения вкладок в операционных системах.
Стек
Стеком называется структурирование данных в виде линейной структуры, но
применяя массивы или связанные списки. В стеке есть важный принцип: любой
элемент, который попал в стек последним всегда покидает его первым.
Со стеком можно проводить следующие операции:
- вставить элемент в верхнюю часть стека;
- удалить элемент из верхней части стека;
- просмотреть элемент верхней части стека;
- проверить стек на наличие пустоты;
Стеки применяются:
- при реализации навигации браузера;
- когда реализуется рекурсия;
- когда нужно выделить память, опираясь на стек;
Очередь
Очередь — это структурирование данных в виде линейной структуры из массивов
или связанных списков. Очередь очень похожа на стек, однако отличается своим
основным принципом: первый элемент, который попал в очередь, покидает ее тоже
первым.
Если стек по своим принципам напоминает стопку книг, то очередь — это как в
реальная людская очередь.
С очередью можно проводить следующие операции:
- вставлять элемент в конец очереди;
- удалять элемент из начала очереди;
- возвращать элемент из начала очереди, не удаляя его;
- проверять содержимое очереди.
Очередь применяется:
- когда нужно обслуживать несколько запросов в одном ресурсе;
- когда нужно управлять потоком в многопоточной среде;
- балансировать нагрузки.
Граф
Графом называется структурирование данных из определенных узлов, которые
называют вершинами. Графы бывают 2-х типов и отличаются направлениями пути
между 2-х связанных между собой вершин:
- ориентированные — когда все ребра вершин указывают направления этих
самых вершин; - не ориентированные — когда ребра вершин не указывают направлений,
поэтому обход вершин можно осуществить с любого направления.
Графы можно обойти 2-мя основными алгоритмами:
- Алгоритм поиска в ширину. Это кратчайший путь, который основывается на
вершинах граф. - Алгоритм поиска в глубину. Этот алгоритм основывается на ребрах граф.
С графами можно проводить следующие операции:
- добавлять еще одну вершину;
- добавлять ребро между вершинами;
- показать вершину;
- определить стоимость пути обхода граф.
Графы применяются:
- при вычислениях в потоках;
- когда распределяются ресурсы операционной системы;
- поиск друзей в соцсетях;
- поиск кратчайшего пути в Гугл картах.
Дерево
«Дерево» — это сложное структурирование данных, которое состоит из вершин и
соединяющих их ребер. Такая структура данных часто используется сложнейших
алгоритмах и в искусственном интеллекте. Структура «дерево» чем-то напоминает
графы, но в тоже время имеет отличия. Поэтому в сети можно встретить спор о том,
что «дерево» – это графы или не графы?
С «деревом» можно осуществить следующие операции:
- вставить элемент в дерево;
- искать нужный элемент;
- обойти дерево прямым способом;
- применить центрированный способ обхода;
- применить обратный способ обхода.
Деревья применяются:
- внутри виртуальной машины Java;
- когда нужно представить файловую систему компьютера;
- химическая формула — это тоже «дерево».
Хэш-таблица
Это особое структурирование данных в виде таблицы, где все данные хранятся в
парах связанных значений «ключ+значение». То есть, каждому значению
соответствует свой ключ.
Процесс генерации ключей для значений в таблице называется хешированием.
Хеширование проводится специальной хэш-функцией.
С хэш-таблицами можно осуществить следующие операции:
- найти элемент в хэш-таблице;
- вставить элемент в хэш-таблицу;
- удалить элемент из хэш-таблицы.
Хэш-таблицы применяются:
- когда нужно индексировать базы данных;
- при проверки пары логин/пароль;
- в реализации «кеша»;
- и др.
Возможно вам будет интересно почитать статью “СИ шарп команды. Обзор условных операторов C”
Заключение
Правильное структурирование данных призвано повысить функциональность вашей
программы или приложения. Поэтому, если в планах создавать что-то эффективное , функциональное и сложное, то знание как правильно применять структуры данных
обязательно. Если пока нет таких грандиозных планов, то хотя бы понимание этих
структур должно присутствовать.