Понятие структурированных данных. Определение и назначение базы данных

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

Что включает в себя понятие структуры данных?

Этот термин может иметь несколько близких, но все же отличительных значений. Это:

• абстрактный тип;
• реализация абстрактного вида информации;
• экземпляр типа данных, к примеру, определенный список.

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

Что формирует структуру?

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

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

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

Стоит отметить, что многие языки программирования обладают установленным типом модульности, что позволяет структурам с данными безопасно использоваться в различных приложениях. Яркими примерами являются языки Java, C# и C++. Сейчас классическая структура используемых данных представлена в стандартных библиотеках языков программирования или непосредственно она встроена уже в сам язык. К примеру, хэш-таблицы встроена в Lua, Python, Perl, Ruby, Tcl и другие. Широко применяется стандартная библиотека шаблонов в C++.

Сравниваем структуру в функциональном и императивном программировании

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

1. Фактически все структуры часто применяют на практике присваивание, которое в чисто функциональном стиле не используется.
2. Функциональные структуры - это гибкие системы. В императивном программировании старые версии просто заменяются на новые, а в функциональном все работает, как работало. Иными словами, в императивном программировании структуры являются эфемерными, а в функциональном они постоянные.

Что включает в себя структура?

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

Простейший массив подходит для частого обращения к установленным компонентам по индексам и их изменению, а удаление элементов из средины функционирует за принципом O(N)O(N). Если вам требуется удалить элементы, чтобы разрешить определенные задачи, то придется воспользоваться иной структурой. К примеру, бинарное дерево (std::set) позволяет делать это по O(logN)O(log⁡N), однако оно не поддерживает работу с индексами, выполняется исключительно поочередный обход элементов и их поиск по значению. Таким образом, можно сказать, что структура отличается операциями, что она способна выполнять, а также скоростью их проделывания. Для примера стоит рассмотреть простейшие структуры, что не дают выгоды в эффективности, но имеют точно установленный набор поддерживаемых операций.

Стек

Это один из типов структур данных, представленный в виде ограниченного простейшего массива. Классический стек поддерживает всего лишь три опции:

• Внести элемент в стек (Сложность: O(1)O(1)).
• Извлечение элемента из стека (Сложность: O(1)O(1)).
• Проверка, пустой ли стек или нет (Сложность: O(1)O(1)).

Чтобы пояснить принцип работы стека, можно применить на практике аналогию с банкой печенья. Представьте, что на дне посудины лежит несколько печенюшек. Наверх вы можете положить еще пару кусочков или же вы можете, наоборот, взять одну печеньку сверху. Остальные печеньки будут закрыты верхними, и вы про них ничего не будете знать. Вот так дела обстоят и со стеком. Для описания понятия применяется аббревиатура LIFO (Last In, First Out), которая подчеркивает, что компонент, попавший внутрь стека последним, будет первым же и извлечен из него.

Очередь

Это еще один тип структуры данных, что поддерживает тот же набор опций, что и стек, однако у него противоположная семантика. Для описания очереди применяется аббревиатура FIFO (First In, First Out), потому как вначале извлекается элемент, что добавлен был раньше всех. Название структуры говорит за себя - принцип работы полностью совпадает с очередями, что можно увидеть в магазине, супермаркете.

Дек

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

• Внести элемент в начало (Сложность: O(1)O(1)).
• Извлечь компонент из начала (Сложность: O(1)O(1)).
• Внесение элемента в конец (Сложность: O(1)O(1)).
• Извлечение элемента из конца (Сложность: O(1)O(1)).
• Проверка, пустой ли дек (Сложность: O(1)O(1)).

Списки

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

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

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

Деревья

Это совокупность компонентов, что именуются узлами, в котором есть главный (один) компонент в виде корня, а все остальные разбиты на множество непересекающихся элементов. Каждое множество является деревом, а корень каждого древа - потомком корня дерева. Другими словами, все компоненты соединены между собой отношениями предок-потомок. Как результат можно наблюдать иерархическую структуру узлов. Если узлы не имеют потомка, то они называются листьями. Над деревом определены такие операции, как: добавление компонента и его удаление, обход, поиск компонента. Особую роль в информатике играют бинарные деревья. Что это такое? Это частный случай дерева, где каждый узел может иметь не больше пары потомков, являющихся корнями левого и правого поддерева. Если дополнительно для узлов дерева выполняется еще условие, что все значения компонентов левого поддерева меньше значений корня, а значения компонентов правого поддерева больше корня, то такое дерево именуется деревом бинарного поиска, и предназначается оно для быстрого нахождения элементов. Как же работает алгоритм поиска в таком случае? Искомое значение сравнивается со значением корня, и в зависимости от результата поиск либо завершается, либо продолжается, но исключительно в левом или правом поддереве. Общее число операций сравнения не станет превосходить высоту дерева (это наибольшее число компонентов на пути от корня до одного из листьев).

Графы

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

Графами можно описывать объекты какой угодно структуры, они являются главным средством для описания сложных структур и функционирования всех систем.

Детальней об абстрактной структуре

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

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

Анализ структур данных производится следующими объектами:

• Целые и вещественные числа.
• Логические значения.
• Символы.

Для обработки на компьютере всех элементов существуют соответствующие алгоритмы и структуры данных. Типичные объекты можно объединить в сложные структуры. Можно добавить операции над ними, правила к определенным компонентам этой структуры.

Структура организации данных включает в себя:

• Векторы.
• Динамические структуры.
• Таблицы.
• Многомерные массивы.
• Графы.

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

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

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

Мы разобрались с характеристиками структур данных, теперь стоит уделить больше внимания пониманию понятия структуры. При решении абсолютно любой задачи требуется работать с какими-то данными, чтобы произвести операции над информацией. У каждой задачи есть свой набор операций, однако некоторый набор применяется на практике чаще для решения разнообразных заданий. В таком случае полезно придумать определенный способ организации информации, что позволит выполнять эти операции как можно эффективнее. Как только такой способ появился, можно считать, что у вас появился «черный ящик», в котором будут сберегаться данные определенного рода и который станет выполнять те или иные операции с данными. Это позволит отвлечься от деталей и полностью сконцентрироваться на характерных особенностях задачи. Данный «черный ящик» может быть реализован любым образом, при этом необходимо стремиться к как можно более продуктивной реализации.

Кому это необходимо знать?

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

Не забывайте: если говорите о той или иной структуре, то имейте в виду ее логическое представление, ведь физическое представление полностью сокрыто от «внешнего наблюдателя».

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

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

Экзамен Информатика

Информация как ресурс. Способы хранения и обработки информации.

Информация от лат. «Information» означает разъяснение, осведомление, изложение.

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

Информатика рассматривает информацию как концептуально связанные между собой сведения, данные, понятия, изменяющие наши представления о явлении или объекте окружающего мира.

Информационные ресурсы – это отдельные документы и отдельные массивы документов, документы и массивы документов в информационных системах (библиотеках, архивах, фондах, банках).
Чтобы информация могла использоваться, причем многократно, необходимо ее хранить.

Хранение информации – это способ распространения информации в пространстве и времени. Способ хранения информации зависит от ее носителя (книга - библиотека, картина - музей, фотография - альбом). ЭВМ предназначена для компактного хранения информации с возможностью быстрого доступа к ней.
Обработка информации – это преобразование информации из одного вида в другой.
Обработка информации – сам процесс перехода от исходных данных к результату и есть процесс обработки. Объект или субъект, осуществляющий обработку - исполнитель обработки.
1-ый тип обработки: обработка, связанная с получением новой информации, нового содержания знаний.
2-ой тип обработки: обработка, связанная с изменением формы, но не изменяющая содержания (например,
перевод текста с одного языка на другой).

Важный вид обработки - кодирование – преобразование информации в символьную форму,
удобную для ее хранения, передачи, обработки. Другой вид обработки информации – структурирование данных (внесение определенного порядка в хранилище информации, классификация, каталогизация данных).
Ещё один вид обработки информации – поиск в некотором хранилище информации нужных данных, удовлетворяющих определенным условиям поиска (запросу).

Понятие структурированных данных. Определение и назначение базы данных.

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

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

Структурированные данные - это упорядоченные данные.

Неструктурированные данные – это данные, записанные, например, в текстовом файле: Личное дело № 1 Сидоров Олег Иванович, дата рожд. 14.11.92, Личное дело № 2 Петрова Анна Викторовна, дата рожд. 15.03.91.

Чтобы автоматизировать поиск и систематизировать эти данные, необходимо выработать определенные соглашения о способах предоставления данных, т.е. дату рожд. нужно записывать одинаково для каждого студента, она должна иметь одинаковую длину и опред. место среди остальной информации. Эти же замечания справедливы и для остальных данных (№ личного дела, Ф., И., О.) После проведения несложной структуризации с информацией, она будет выглядеть так:

Пример структурированных данных: № Ф. И. О. Дата рожд.

1 Сидоров Олег Иванович 14.11.92

Элементы структурированных данных:

1) А – поле (столбец) – это элементарная неделимая единица организации информации

2) Б – запись (строка) – это совокупность логически связанных полей

3) В – таблица (файл) – это совокупность экземпляров записей одной структуры.

База данных – это организованная на машинном носителе совокупность взаимосвязанных структурированных данных, содержащая сведения о различных сущностях некоторой предметной области (объектах, процессах, событиях, явлениях).

В широком смысле слова база данных – это совокупность сведений о конкретных объектах реального мира в какой-либо предметной области.

Под предметной областью понимается часть реального мира, подлежащая изучению для организации управления, автоматизации, например, предприятии, ВУЗ и т.д.

Назначение базы данных:

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

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

3)Совместное использование данных. Файлы обычно принадлежат отдельным лицам или целым отделам, которые используют их в своей работе. В то же время база данных принадлежит всей организации в целом и может совместно использоваться всеми зарегистрированными пользователями. При такой организации работы большее количество пользователей может работать с большим объемом данных. Более того, при этом можно создавать новые приложения на основе уже существующей в базе данных информации и добавлять в нее только те данные, которые в настоящий момент еще не хранятся в ней, а не определять заново требования ко всем данным, необходимым новому приложению.

4)Поддержка целостности данных. Целостность базы данных означает корректность и непротиворечивость хранимых в ней данных. Целостность обычно описывается с помощью ограничений, т.е. правил под­держки непротиворечивости, которые не должны нарушаться в базе данных. Ограничения можно применять к элементам данных внутри одной записи или к связям между записями. Например, ограничение целостности может гласить, что зарплата сотрудника не должна превышать 40 000 рублей в год или же что в записи с данными о сотруднике номер отделения, в котором он работает, должен соответствовать реально существующему отделению компании.

5)Повышенная безопасность. Безопасность базы данных заключается в защите базы данных от несанкционированного доступа со стороны пользователей. Без привлечения соответствующих мер безопасности интегрированные данные становятся более уязвимыми, чем данные в файловой системе. Однако интеграция позволяет определить требуемую систему безопасности базы данных, а СУБД привести ее в действие. Система обеспечения безопасности может быть выражена в форме учетных имен и паролей для идентификации пользователей, которые зарегистрированы в этой базе данных. Доступ к данным со стороны зарегистрированного пользователя может быть ограничен только некоторыми операциями (извлечением, вставкой, обновлением и удалением).

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

Кольцевой список

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

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

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

Вполне вероятно, читателю приходилось сталкиваться со структурами данных непосредственно в информатике, например, с теми, что встроены в язык программирования. Часто они именуются типами данных. К таковым относятся: массивы, числа, строки, файлы и т. д.

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

Массивы.

Массив – это структура данных с фиксированным и упорядоченным набором однотипных элементов (компонентов). Доступ к какому-либо из элементов массива осуществляется по имени и номеру (индексу) этого элемента. Количество индексов определяет размерность массива. Так, например, чаще всего встречаются одномерные (вектора) и двумерные (матрицы) массивы.

Первые имеют один индекс, вторые – два. Пусть одномерный массив называется A, тогда для получения доступа к его i-ому элементу потребуется указать название массива и номер требуемого элемента: A[i]. Когда A – матрица, то она представляема в виде таблицы, доступ к элементам которой осуществляется по имени массива, а также номерам строки и столбца, на пересечении которых расположен элемент: A, где i – номер строки, j – номер столбца.

В разных языках программирования работа с массивами может в чем-то различаться, но основные принципы, как правило, везде одни. В языке Pascal, обращение к одномерному и двумерному массиву происходит точно так, как это показано выше, а, например, в C++ двумерный массив следует указывать так: A[i][j]. Элементы массива нумеруются поочередно. На то, с какого значения начинается нумерация, влияет язык программирования. Чаще всего этим значением является 0 или 1.

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

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

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

Списки.

Список – абстрактный тип данных, реализующий упорядоченный набор значений. Списки отличаются от массивов тем, что доступ к их элементам осуществляется последовательно, в то время как массивы – структура данных произвольного доступа. Данный абстрактный тип имеет несколько реализаций в виде структур данных. Некоторые из них будут рассмотрены здесь.

Список (связный список) – это структура данных, представляющая собой конечное множество упорядоченных элементов, связанных друг с другом посредствам указателей. Каждый элемент структуры содержит поле с какой-либо информацией, а также указатель на следующий элемент. В отличие от массива, к элементам списка нет произвольного доступа.

В односвязном списке, приведенным выше, начальным элементом является Head list (голова списка [произвольное наименование]), а все остальное называется хвостом. Хвост списка составляют элементы, разделенные на две части: информационную (поле info) и указательную (поле next). В последнем элементе вместо указателя, содержится признак конца списка – nil.

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

Двусвязный список

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

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

Кольцевой список

Помимо рассмотренных видов списочных структур есть и другие способы организации данных по типу «список», но они, как правило, во многом схожи с разобранными, поэтому здесь они будут опущены.

Кроме различия по связям, списки делятся по методам работы с данными. О некоторых таких методах сказано далее.

Стек.

Стек

Стек характерен тем, что получить доступ к его элементом можно лишь с одного конца, называемого вершиной стека, иначе говоря: стек – структура данных, функционирующая по принципу LIFO (last in - first out, «последним пришёл - первым вышел»). Изобразить эту структуру данных лучше в виде вертикального списка, например, стопки каких-либо вещей, где чтобы воспользоваться одной из них нужно поднять все те вещи, что лежат выше нее, а положить предмет можно лишь на вверх стопки.

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

Очередь.

Структура данных «Очередь» использует принцип организации FIFO (First In, First Out - «первым пришёл - первым вышел»). В некотором смысле такой метод более справедлив, чем тот, по которому функционирует стек, ведь простое правило, лежащее в основе привычных очередей в различные магазины, больницы считается вполне справедливым, а именно оно является базисом этой структуры. Пусть данное наблюдение будет примером. Строго говоря, очередь – это список, добавление элементов в который допустимо, лишь в его конец, а их извлечение производиться с другой стороны, называемой началом списка.

Дек

Дек (deque - double ended queue, «двухсторонняя очередь») – стек с двумя концами. Действительно, несмотря конкретный перевод, дек можно определять не только как двухстороннюю очередь, но и как стек, имеющий два конца. Это означает, что данный вид списка позволяет добавлять элементы в начало и в конец, и то же самое справедливо для операции извлечения.

Эта структура одновременно работает по двум способам организации данных: FIFO и LIFO. Поэтому ее допустимо отнести к отдельной программной единице, полученной в результате суммирования двух предыдущих видов списка.

Графы.

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

Граф – совокупность точек, соединенных линиями. Точки называются вершинами (узлами), а линии – ребрами (дугами).

Как показано на рисунке различают два основных вида графов: ориентированные и неориентированные. В первых ребра являются направленными, т. е. существует только одно доступное направление между двумя связными вершинами, например из вершины 1 можно пройти в вершину 2, но не наоборот. В неориентированном связном графе из каждой вершины можно пройти в каждую и обратно. Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.

Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.

Ребра графа необязательно должны быть прямыми, а вершины обозначаться именно цифрами, так как показано на рисунке. К тому же встречаются такие графы, ребрам которых поставлено в соответствие конкретное значение, они именуются взвешенными графами, а это значение – весом ребра. Когда у ребра оба конца совпадают, т. е. ребро выходит из вершины F и входит в нее, то такое ребро называется петлей.

Графы широко используются в структурах, созданных человеком, например в компьютерных и транспортных сетях, web-технологиях. Специальные способы представления позволяют использовать граф в информатике (в вычислительных машинах). Самые известные из них: «Матрица смежности», «Матрица инцидентности», «Список смежности», «Список рёбер». Два первых, как понятно из названия, для репрезентации графа используют матрицу, а два последних – список.

Деревья.

Неупорядоченное дерево

Дерево как математический объект это абстракция из соименных единиц, встречающихся в природе. Схожесть структуры естественных деревьев с графами определенного вида говорит о допущении установления аналогии между ними. А именно со связанными и вместе с этим ациклическими (не имеющими циклов) графами. Последние по своему строению действительно напоминают деревья, но в чем то и имеются различия, например, принято изображать математические деревья с корнем расположенным вверху, т. е. все ветви «растут» сверху вниз. Известно же, что в природе это совсем не так.

Поскольку дерево это по своей сути граф, у него с последним многие определения совпадают, либо интуитивно схожи. Так корневой узел (вершина 6) в структуре дерева – это единственная вершина (узел), характерная отсутствием предков, т. е. такая, что на нее не ссылается ни какая другая вершина, а из самого корневого узла можно дойти до любой из имеющихся вершин дерева, что следует из свойства связности данной структуры. Узлы, не ссылающиеся ни на какие другие узлы, иначе говоря, ни имеющие потомков называются листьями (2, 3, 9), либо терминальными узлами. Элементы, расположенные между корневым узлом и листьями – промежуточные узлы (1, 1, 7, 8). Каждый узел дерева имеет только одного предка, или если он корневой, то не имеет ни одного.

Поддерево – часть дерева, включающая некоторый корневой узел и все его узлы-потомки. Так, например, на рисунке одно из поддеревьев включает корень 8 и элементы 2, 1, 9.

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

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

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

Я всегда считал, что «структура данных » — это термин, придуманный специально, чтобы сбить нас с толку. В конце концов, мне удалось выяснить, что такое структура данных, просто переставив местами слова в термине «структура данных » — с «data structure » на «structure of data «. В таком контексте акцент внимания смещается с данных (вещи ) на структуру (организацию ). Другими словами, мы акцентируем внимание не на вещах, а на процессе организации вещей.

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

Различные типы структур данных

Книги, подобно данным, могут быть организованы по-разному. Давайте представим, что у нас есть 20 книг. Как мы их структурируем?

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

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

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

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

Мы должны понять, что можно использовать и создавать эти структуры данных без каких-либо узкоспециализированных навыков программирования. Все что нам нужно — это понимание JavaScript , его простейших типов данных (например, логических выражений ) и ссылочных типов (например, объектов ).

Вначале это трудно представить, но не волнуйтесь. Раньше я представлял себе набор, который тоже является типом структуры данных, как просто набор. Но набор это не вещь, а название, присвоенное конкретному способу организации данных. Что не менее важно, набор создается с использованием объектов.

Наша цель

Эта серия статей о структурировании данных с помощью JavaScript должна показать вам, что структуры данных используются, чтобы сделать нашу жизнь проще.

Поскольку структур данных слишком много, чтобы их можно было полностью описать в этой серии статей, мы рассмотрим лишь некоторые из них, но самые распространенные:

• Стек и Очередь;
• Односвязные и двусвязные списки;
• Дерево.

Заключение

Когда мы закончим рассмотрение данной серии статей, я надеюсь, вы не только узнаете, как реализовать распространенные структуры данных, но и поймете, что они используются вокруг вас. Тогда вы по-другому начнете относиться к данным и к их организации.

Перевод статьи «Data Structures With JavaScript: What’s a Data Structure? » был подготовлен дружной командой проекта .

Хорошо Плохо

Дерево - одна из наиболее часто используемых в веб-разработке структур данных. Каждый веб-разработчик, который писал HTML-код и загружал его в браузер, создавал…

ТИПЫ И СТРУКТУРЫ ДАННЫХ

Методические указания по дисциплине «Алгоритмы и структуры данных»

Составитель О.Л. Чагаева

Подготовлены кафедрой «Программные средства и системы» ФУО УрФУ

Введение

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

Каждая представляемая информацией сущность (объект, явление) имеет ряд характерных для нее свойств (черт, признаков, параметров, характеристик, моментов). Например, свойствами материала являются его вес, габариты, сорт, цена, номенклатурный номер и др. Свойствами-признаками, характеризующими такую сущность, как организация-покупатель, являются наименование, ведомственная принадлежность, адрес, номер расчетного счета в Госбанке и др.

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

Реквизит - это логически неделимый элемент любой сложной информационной совокупности, соотносимый с определенным свойством отображаемого информацией объекта или процесса.

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

Другими часто встречающимися в литературе синонимами реквизита являются элемент, поле, терм, признак иатрибут .

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

Каждому реквизиту присуще некоторое конечное множество значений в зависимости от характеристики того свойства объекта (явления), которое информационно отображает данный реквизит. Это множество, именуемое классом значений, одно, например, для параметра «температура больного» и другое - для признака «пол больного».

Значение реквизита, таким образом, есть в каждый заданный момент времени одна из позиций класса значений данного реквизита, отображающая, как предполагается, соответствующее состояние (из множества состояний) того свойства объекта (явления), которое характеризует реквизит. Так, текущим значением реквизита «температура больного» может быть 37,4°, а реквизита «пол больного» - «мужской». Другими словами, значение реквизита используется для представления значения соответствующего свойства сущности.

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

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

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

Реквизиты текстового типа выражают, как правило, качественные свойства сущностей и характеризуют обстоятельства, при которых имел место изучаемый процесс и были получены те или

иные числовые значения. Поэтому такие реквизиты называются признаками.

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

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

Размер алфавита (число разнообразных символов, которые могут быть в одном разряде величины) и его состав (набор) имеют прямое отношение к решению следующих проблем:

кодирования и дешифровки,

компактной записи значений единиц информации,

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

получения от машин информации в наиболее удобной для потребления форме,

снижения затрат на всевозможные перезаписи.

Поэтому выбору алфавита придается немаловажное значение.

Для использования информации, в алгоритмизации и программировании очень большое значение уделяется таким понятиям, как тип и структура данного.

1. ТИПЫ ДАННЫХ

Вычислительный процесс на ЭВМ реализуется, как известно, с помощью программ и данных. Сама программа тоже относится к данным. Поэтому можно сказать, что данные описывают любую информацию, с которой может работать ЭВМ. При этом под информацией понимаются любые факты и знания об объектах реального мира, процессах и отношениях и связях между ними. Все данные характеризуются рядом атрибутов (признаков, реквизитов), в том числе значением.

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

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

2. СТРУКТУРЫ ДАННЫХ

Особенностью данного того или иного типа является простота организации (неструктурированность).

Структура данных – это совокупность элементов данных, между которыми существуют некоторые отношения, причем элементами данных могут быть как простые данные (скаляры), так и структуры данных.

Таким образом, структуру можно определить следующим образом: S = (D, R), где D - множество элементов данных, R – множество отношений между элементами данных.

Все связи одного элемента данных с другими образуют элемент отношений, ассоциированный с соответствующим элементом данных.

Графическое изображение структуры должно отражать ее элементы данных и связи (отношения между ними), поэтому структуру удобно изображать в виде графа. При этом вершины графа можно интерпретировать как элементы данных, а отношениям между элементами данных соответствуют ориентированные дуги или неориентированное ребра (рис. 1).

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

Рис 1. Неориентированный (а) и ориентированный (б) граф

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

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

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

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

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

Операции над логической структурой

Логическая структура данных

Операции над физической структурой

Физическая структура данных

Рис. 2. Отображение между логическим и физическим представлением структуры данных

2.1. Классификация структур данных

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

Важные признак структуры – ее изменчивость – изменение числа элементов и/или связей между элементами структуры. Значение элемента данных не имеется в виду, так как в этом случае это свойство было бы характерно для всех структур данных за исключением, может быть, констант и данных, хранящихся в ПЗУ. По признаку изменчивости различают статические, полустатические и динамические структуры.

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

В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с последовательным распределением их элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с произвольным связным распределением элементов в памяти (односвязные, двусвязные, циклически связанные, ассоциативные списки). Примером нелинейных структур являются многосвязные списки, древовидные структуры и графовые структуры общего вида.

2.2. Простейшие статические структуры

К простейшим структурам данных обычно относят векторы, массивы, записи, таблицы. Они характеризуются следующими свойствами:

постоянство структуры в течение всего времени ее существования;

смежность элементов и непрерывность области памяти, отводимой сразу для всех элементов структуры;простота и постоянство отношений между элементами

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

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

2.2.1. Вектор

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

Элементы вектора находятся друг с другом в единственно возможном отношении – отношении непосредственного следования. Строгая последовательность элементов вектора позволяет

пронумеровать их последовательными целыми числами – индексами. Логическая структура вектора полностью описывается числом и типом его элементов. Например, int array – целочисленный массив, состоящий из 10 элементов.

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

На логическом уровне для доступа к элементу вектора достаточно указать имя вектора и значение индекса соответствующего элемента. Например: array + array.

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

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

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

2.2.2. Массив

Массивом называется такой вектор, каждый элемент которого - вектор. В свою очередь, элементы вектора, являющегося элементом массива, также могут быть векторами. Процесс перехода от элемента к элементу этого элемента и так далее рано или поздно должен завершиться скаляром некоторого типа данных, причем этому типу должны соответствовать все скалярные элементы массива (рис. 3).

Рис. 3. Вид многомерного массива

На рис.3 представлен вид многомерного массива: в каждом узле решетки находится элемент массива. Таким образом, размерность его равна (3,3,2).

Как и для вектора, важнейшей элементарной операцией для массива является доступ к его элементу. На уровне логической структуры она осуществляется при помощи имени массива и упорядоченного набора индексов, однозначно идентифицирующих элемент массива. Например: array[i][j].

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

Несмотря на это, дескриптор многомерного массива отличается от дескриптора вектора. Например, в нем должна хранится информация о размерности массива, способе упорядочения элементов (по строкам или столбцам).

2.2.3. Запись

Запись – это конечное упорядоченное множество элементов, содержащее в общем случае данные различных типов.

Элементы записи часто называют полями. Запись – это обобщенное понятие вектора, при котором не требуется однотипность или