29.Проектирование структур данных.
Структурированные данные. Списки, стеки, очереди. Организация данных. Основные методы обработки данных
Структурированные типы
В случае структурированных типов под одним ключевым словом группируются несколько совместных значений, таких например как координаты точки или имя и фамилия человека. В таком виде набор данных разом легче передавать. В то же время использовать или изменять данные внутри структуры приходиться по одному.
Контент многих веб-сайтов генерируется из данных, которые хранятся в базах данных , а когда они переводятся в код HTML, для поисковый роботов может быть трудно эффективно интерпретировать эту информацию. Структурированные данные это разметка на странице, которая позволяет поисковым системам лучше понять информацию на веб-страницах, чтобы затем использовать ее для улучшения позиции вашего бизнеса в поиске. Например, структурированные данные помогают поисковым роботам определять такую информацию, как имя компании, адрес, контактные данные, а также более сложную информацию, включающую статьи, события, продукты, их описания и т.д.
спи́сок (англ. list) — это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности — кортежа. Экземпляры значений, находящихся в списке, называются элементами списка (англ. item, entry либо element); если значение встречается несколько раз, каждое вхождение считается отдельным элементом.
Свойства
У определённой таким образом структуры данных имеются некоторые свойства:
Размер списка — количество элементов в нём, исключая последний «нулевой» элемент, являющийся по определению пустым списком.
Тип элементов —тип
,
над которым строится список; все элементы
в списке должны быть этого типа.Отсортированность — список может быть отсортирован в соответствии с некоторыми критериями сортировки (например, по возрастанию целочисленных значений, если список состоит из целых чисел).
Возможности доступа — некоторые списки в зависимости от реализации могут обеспечивать программиста селекторами для доступа непосредственно к заданному по номеру элементу.
Сравниваемость — списки можно сравнивать друг с другом на соответствие, причём в зависимости от реализации операция сравнения списков может использовать разные технологии.
Как должно быть понятно из названия рассматриваемой структуры данных, списки используются для хранения наборов однотипных элементов. Такие элементы могут быть отсортированы для использования в функциях поиска или функциях для быстрой вставки новых элементов в список.
Стек (англ. stack — стопка) — структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
Зачастую стек реализуется в виде однонаправленного списка (каждый элемент списка указывает только на следующий). Но в таком случае невозможно применить операцию обхода элементов. А доступ возможен только к верхнему элементу структуры. Для обхода такой проблемы можно взять за основу двусвязный список (каждый элемент указывает на обоих соседей справа и слева). Кроме того можно организовать его на обыкновенном массиве.
Значением переменной стека является указатель на вершину стека. Если стек пуст, то значение указателя равно NULL.
Пример реализации стека на языке Си:
struct stack
{
char *data;
struct stack *next;
};
Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek)[5].
При проталкивании (push) указывается новый элемент, указывающий на элемент бывший до этого головой. Новый элемент теперь становится головным.
При удалении элемента убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент).
О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
Существует несколько способов реализации очереди в языках программирования.
Массив
Первый
способ представляет очередь в виде
массива
и двух целочисленных переменных
start и end.
Обычно
start
указывает на голову очереди, end —
на элемент, который заполнится, когда
в очередь войдёт новый элемент. При
добавлении элемента в очередь в q[end]
записывается новый элемент очереди, а
end
уменьшается на единицу. Если значение
end становится меньше 1, то мы как бы
циклически обходим массив и значение
переменной становится равным n. Извлечение
элемента из очереди производится
аналогично: после извлечения элемента
q[start]
из очереди переменная start
уменьшается на 1. С такими алгоритмами
одна ячейка из n
всегда будет незанятой (так как очередь
с n
элементами невозможно отличить от
пустой), что компенсируется простотой
алгоритмов.
Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.
Недостатки: максимальное количество элементов в очереди ограничено размером массива. При его переполнении требуется перевыделение памяти и копирование всех элементов в новый массив.
Связный список
Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов.
Преимущества данного метода: размер очереди ограничен лишь объёмом памяти.
Недостатки: сложнее в разработке; требуется больше памяти; при работе с такой очередью память сильнее фрагментируется; работа с очередью несколько медленнее.
Очередь может быть построена из двух стеков S1 и S2 как показано ниже:
Процедура enqueue(x):
S1.push(x)
Процедура dequeue():
если S2 пуст:
если S1 пуст:
сообщить об ошибке: очередь пуста
пока S1 не пуст:
S2.push(S1.pop())
return S2.pop()
Такой способ реализации наиболее удобен в качестве основы для построения персистентной очереди.
Операции с данными
Для повышения качества данные преобразуются из одного вида в другой с помощью методов обработки. Обработка данных включает операции:
ввод (сбор) данных — накопление данных с целью обеспечения достаточной полноты для принятия решений;
формализация данных — приведение данных, поступающих из разных источников, к одинаковой форме, для повышения их доступности;
фильтрация данных — это отсеивание «лишних» данных, в которых нет необходимости для повышения достоверности и адекватности;
сортировка данных — это упорядочивание данных по заданному признаку с целью удобства их использования;
архивация — это организация хранения данных в удобной и легкодоступной форме;
защита данных — включает меры, направленные на предотвращение утраты, воспроизведения и модификации данных;
транспортировка данных — приём и передача данных между участниками информационного процесса;
преобразование данных — это перевод данных из одной формы в другую или из одной структуры в другую.