Структуры данных и их разновидности. Типы и структуры данных. Операции реляционной алгебры

Какие виды структур данных бывают?(можете указать название структуры в определенном языке программирования) Хочется узнать их предназначение, сильные и слабые стороны. Так же интересует классификация, верно ли в вики написано? Список структур данных Развернутый ответ пока каждой структуре не нужен, просто кратко, для примера рассказать в чем преимущество этой структуры перед остальными(например самое быстрое время доступа к элементу, способность динамически менять объем памяти и т.д.) Может на всё сразу не стоит отвечать, вдруг объем ответа будет значительным, хотя бы по одной из структур которую хорошо знаете можете отписаться, а я буду добавлять в основной пост информацию. Очень удобно будет иметь перед глазами такой список, сразу по нему сверился и выбрал нужное.

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

1.1 Список Может всё то же самое, что и массив, но позволяет добавлять элементы в любое место, удалять элементы из любого места и получать текущее количество элементов.

1.2 Ассоциативный массив

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

преимущества:

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

недостатки:

• Итерация не в порядке возрастания ключей
• Необходимость «перехеширования» при увеличении числа хранимых объектов (?)
• нельзя реализовать быстро работающие дополнительные операции MIN, MAX и алгоритм обхода всех хранимых пар в порядке возрастания или убывания ключей (?)
• не поддерживает упорядоченности, и не сохраняет порядок следования элементов (?)
• возможность коллизий

общий вид описания структур:

Основное предназначение, описание

Поддерживаемые операции

Преимущества

Недостатки

Готовая реализация в языке программирования (название функции или класса)

условные обозначения

(?) - под сомнением, поправьте пожалуйста если вдруг неправильно написано или наоборот утвердите чтобы исключить неоднозначность.

редактирование продолжается..

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

Банк данных должен соответствовать следующим требованиям:

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

Банк данных состоит из двух основных компонент: базы данных и системы управления базой данных.

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

К организации баз данных предъявляются следующие требования:

• 1) легкое, быстрое и дешевое осуществление разработки приложений базы данных;
• 2) возможность многократного применения данных;
• 3) сохранение затрат умственного труда, выражающееся в существовании программы и логических структур данных, которые не переделываются при внесении изменений в базу данных;
• 4) простота;
• 5) легкость использования;
• 6) гибкость использования;
• 7) большая скорость обработки незапланированных запросов на данные;
• 8) простота внесения изменений;
• 9) небольшие затраты; низкая стоимость хранения и использования данных и минимизация затрат на внесение изменений;
• 10) малая избыточность данных;
• 11) производительность;
• 12) достоверность данных и соответствие одному уровню обновления; нужно применять контроль за достоверностью данных; система предотвращает наличие различных версий одних и тех же элементов данных, доступных пользователям, на различных стадиях обновления;
• 13) секретность; несанкционированный доступ к данным невозможен; ограничение доступа к одинаковым данным для различного вида их использования может осуществляться разными способами;
• 14) защита от искажения и уничтожения; данные необходимо защищать от сбоев;
• 15) готовность; пользователь быстро получает данные всегда, когда это ему необходимо.

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

По типу хранимой информации БД делятся на

• · документальные,
• · фактографические и
• · лексикографические.

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

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

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

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

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

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

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

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

По характеру организации хранения данных и обращения к ним различают

• · локальные (персональные),
• · общие (интегрированные, централизованные) и
• · распределенные базы данных

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

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

БД классифицируются по объему. Особое место здесь занимают так называемые очень большие базы данных. Это вызвано тем, что для больших баз данных по-иному ставятся вопросы обеспечения эффективности хранения информации и обеспечения ее обработки.

По характеру организации данных БД могут быть разделены на

• · неструктурированные,
• · частично структурированные и
• · структурированные.

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

Структурированные БД, в свою очередь, по типу используемой модели делятся на

• · иерархические,
• · сетевые,
• · реляционные,
• · смешанные и
• · мультимодельные.

Классификация по типу модели распространяется не только на базы данных, но и на СУБД.

Иерархические, сетевые, реляционные

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

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

Корневым называется узел, который имеет подчиненные узлы и сам не является подузлом. Подчиненный узел (подузел) является потомком по отношению к узлу, который выступает для него в роли предка (родителя). Потомки одного и того же узла являются близнецами по отношению друг к другу В целом «дерево» представляет собой иерархически организованный набор типов «узел». Иерархическая БД представляет собой упорядоченную совокупность деревьев, содержащих экземпляры типа «узел» (записи). Часто отношения родства между типами переносят на отношения между самими записями. Поля записей хранят собственно числовые или символьные значения, составляющие основное содержание БД. Обход всех элементов иерархической БД обычно производится сверху вниз и слева направо.

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

Для описания схемы сетевой БД используется две группы типов: «запись» и «связь». Тип «связь» определяется для двух типов «запись»: предка и потомка Переменные типа «связь» являются экземплярами связей.

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

Реляционная модель данных предложена сотрудником фирмы IВМ Удгаром Коддом и основывается на понятии отношение (relation).

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

Таблица имеет строки (записи) и столбцы (колонки). Каждая строка таблицы имеет одинаковую структуру и состоит из полей. Строкам таблицы соответствуют кортежи, а столбцам -- атрибуты отношения.

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

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

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

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

Информация от лат. «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.

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

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

• Перевод

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

Очередь

Итак, поздоровайтесь с Лупи!

Лупи обожает играть в хоккей со своей семьей. И под “игрой”, я подразумеваю:

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

Как насчет операций вставки и удаления?

Q = def insert(elem): q.append(elem) #добавляем элемент в конец очереди print q def delete(): q.pop(0) #удаляем нулевой элемент из очереди print q

Стек

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

Когда все блинчики готовы, Лупи подает их всей семье, один за одним.

Заметьте, что первый сделанный ею блинчик - будет подан последним. Это называется Стек . Последний элемент, добавленный в список - покинет его первым. Также эту структуру данных называют LIFO (Last In First Out).

Добавление и удаление элементов?

S = def push(elem): #Добавление элемента в стек - Пуш s.append(elem) print s def customPop(): #удаление элемента из стека - Поп s.pop(len(s)-1) print s

Куча

Вы когда-нибудь видели башню плотности?

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

Он займет место, в зависимости от своей плотности.

Примерно так работает Куча .

Куча - двоичное дерево. А это значит, что каждый родительский элемент имеет два дочерних. И хотя мы называем эту структуру данных кучей, но выражается она через обычный массив.
Также куча всегда имеет высоту logn, где n - количество элементов

На рисунке представлена куча типа max-heap, основанная на следующем правиле: дочерние элементы меньше родительского. Существуют также кучи min-heap, где дочерние элементы всегда больше родительского.

Несколько простых функций для работы с кучами:

Global heap global currSize def parent(i): #Получить индекс родителя для i-того элемента return i/2 def left(i): #Получить левый дочерний элемент от i-того return 2*i def right(i): #Получить правый дочерний элемент от i-того return (2*i + 1)

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

Алгоритм:

1. Добавляем элемент в самый низ кучи.
2. Сравниваем добавленный элемент с родительским; если порядок верный - останавливаемся.
3. Если нет - меняем элементы местами, и возвращаемся к предыдущему пункту.

Код:

Def swap(a, b): #меняем элемент с индексом a на элемент с индексом b temp = heap[a] heap[a] = heap[b] heap[b] = temp def insert(elem): global currSize index = len(heap) heap.append(elem) currSize += 1 par = parent(index) flag = 0 while flag != 1: if index == 1: #Дошли до корневого элемента flag = 1 elif heap > elem: #Если индекс корневого элемента больше индекса нашего элемента - наш элемент на своем месте flag = 1 else: #Меняем местами родительский элемент с нашим swap(par, index) index = par par = parent(index) print heap
Максимальное количество проходов цикла while равно высоте дерева, или logn, следовательно, трудоемкость алгоритма - O(logn).

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

MaxHeapify().

Алгоритм:

1. Заменить корневой элемент самым нижним.
2. Сравнить новый корневой элемент с дочерними. Если они в правильном порядке - остановиться.
3. Если нет - заменить корневой элемент на одного из дочерних (меньший для min-heap, больший для max-heap), и повторить шаг 2.

Def extractMax(): global currSize if currSize != 0: maxElem = heap heap = heap #Заменяем корневой элемент - последним heap.pop(currSize) #Удаляем последний элемент currSize -= 1 #Уменьшаем размер кучи maxHeapify(1) return maxElem def maxHeapify(index): global currSize lar = index l = left(index) r = right(index) #Вычисляем, какой из дочерних элементов больше; если он больше родительского - меняем местами if l <= currSize and heap[l] > heap: lar = l if r <= currSize and heap[r] > heap: lar = r if lar != index: swap(index, lar) maxHeapify(lar)
И вновь максимальное количество вызовов функции maxHeapify равно высоте дерева, или logn, а значит трудоемкость алгоритма - O(logn).

Делаем кучу из любого рандомного массива
Окей, есть два пути сделать это. Первый - поочередно вставлять каждый элемент в кучу. Это просто, но совершенно неэффективно. Трудоемкость алгоритма в этом случае будет O(nlogn), т.к. функция O(logn) будет выполняться n раз.

Более эффективный способ - применить функцию maxHeapify для ‘под-кучи ’, от (currSize/2) до первого элемента.

Сложность получится O(n), и доказательство этого утверждения, к сожалению, выходит за рамки данной статьи. Просто поймите, что элементы, находящиеся в части кучи от currSize/2 до currSize, не имеют потомков, и большинство образованных таким образом ‘под-куч’ будут высотой меньше, чем logn.

Def buildHeap(): global currSize for i in range(currSize/2, 0, -1): #третий агрумент в range() - шаг перебора, в данном случае определяет направление. print heap maxHeapify(i) currSize = len(heap)-1

Действительно, зачем это все?

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

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

Def heapSort(): for i in range(1, len(heap)): print heap heap.insert(len(heap)-i, extractMax()) #вставляем максимальный элемент в конец массива currSize = len(heap)-1
Чтобы обобщить все вышесказанное, я написала несколько строчек кода, содержащего функции для работы с кучей, а для фанатов ООП оформила все в виде класса .

Легко, не правда ли? А вот и празднующая Лупи!

Хеш

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

Через некоторое время черепашки окончательно запутались

Поэтому она достала еще одну игрушку, чтобы немного упростить процесс

Стало намного легче, ведь черепашки уже знали, что фигуры рассортированы по форме. А что, если мы пометим каждый столб?

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

Допустим, номер столба вычисляется следующим образом:

Фио летовый тре угольник
ф+и+о+т+р+е = 22+10+16+20+18+6 = Столб 92

Кра сный пря моугольник
к+р+а+п+р+я = 12+18+1+17+18+33 = Столб 99

Мы знаем, что 6*33 = 198 возможных комбинаций, значит нам нужно 198 столбов.

Назовем эту формулу для вычисления номера столба - Хеш-функцией .

Код:
def hashFunc(piece): words = piece.split(" ") #разбиваем строку на слова colour = words shape = words poleNum = 0 for i in range(0, 3): poleNum += ord(colour[i]) - 96 poleNum += ord(shape[i]) - 96 return poleNum
(с кириллицей немного сложнее, но я оставил так для простоты . - прим.пер. )

Теперь, если нам нужно будет узнать, где хранится розовый квадрат, мы сможем вычислить:
hashFunc("розовый квадрат")

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

Ладно, но допустим мы ищем “кар амельный пря моугольник” (если, конечно, цвет “карамельный” существует).

HashFunc("карамельный прямоугольник")
вернет нам 99, что совпадает с номером для красного прямоугольника. Это называется “Коллизия ”. Для разрешения коллизии мы используем “Метод цепочек ”, подразумевающий, что каждый столб хранит список, в котором мы ищем нужную нам запись.

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

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

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

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

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

Переведено для Хабра запертым на