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

Я всегда считал, что «структура данных » — это термин, придуманный специально, чтобы сбить нас с толку. В конце концов, мне удалось выяснить, что такое структура данных, просто переставив местами слова в термине «структура данных » — с «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. Запись

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

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

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

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

Личное дело № 16493, Сергеев Петр Михайлович, дата рождения 1 января 1976 г.; ГУд Na 16593, Петрова Анна Владимировна, дата рожд. 15 марта 1975 г.; Na личн.дела 16693, д.р. 14.04.76, Анохин Андрей Борисович.

Рис. 2.1. Неструктурированные данные

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

Рис. 2.2. Структурированные данные

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

Иерархическая структура данных. Иерархический тип структуры предполагает расположение частей или элементов целого в порядке от высшего к низшему. Объекты, связанные иерархическими отношениями, образуют ориентированный граф (перевернутое дерево), вид которого представлен на рис. 2.3. К основным понятиям иерархической структуры относятся: уровень, элемент (узел), связь. Узел - это совокупность атрибутов данных, описывающих некоторый объект. На схеме иерархического дерева узлы представляются вершинами графа. Каждый узел на более низком уровне связан только с одним узлом, находящимся на более высоком уровне. Такой узел называется порожденным. Иерархическое дерево имеет только одну вершину (корень дерева), не подчиненную никакой другой вершине и находящуюся на самом верхнем (первом) уровне. Зависимые (порожденные) узлы находятся на втором, третьем и т. д. уровнях. Количество деревьев в базе данных определяется числом корневых записей. К каждой записи базы данных существует только один (иерархический) путь от корневой записи. Например, как видно из рис. 2.3, для записи С4 путь проходит через записи А и ВЗ. В такой структуре связь имеет характер подчинения и направлена от исходного (родительского) узла к зависимому (порожденному).

Рис. 2.3. Графическое изображение иерархической структуры БД

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

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

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

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

Рис. 2.4. Пример иерархической структуры данных

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

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

Рис. 2.5. Графическое изображение сетевой структуры

Примером сложной сетевой структуры может служить структура базы данных, содержащей сведения о дорожной сети какого-либо региона (рис. 2.6). Такая структура сложнее, чем иерархи-

Рис. 2.6. Пример сетевой структуры базы данных

ческая. Следовательно, в ней труднее организовать поиск нужных данных. Реальным примером использования такой структуры на практике является структура глобальной информационной сети, которая получила название WWW (World Wide Web), или «всемирная паутина». Именно сложность поиска информации в этой структуре вызвали появление специальных средств поиска, таких, как «поисковые машины» и «каталоги».

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

В ячейку таблицы помещается только один элемент данных;

Все столбцы в таблице однородные, т. е. все элементы в столбце имеют одинаковый тип (числовой, символьный и т. д.) и длину;

Каждый столбец имеет уникальное имя;

Одинаковые строки в таблице отсутствуют;

Порядок следования строк и столбцов может быть произвольным.

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

Таблица 2.8. Пример реляционной таблицы

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

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

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

• Перевод

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

Очередь

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

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

Когда черепашки залетают в ворота, их выбрасывает на верх стопки. Заметьте, первая черепашка, добавленная в стопку - первой ее покидает. Это называется Очередь . Так же, как и в тех очередях, что мы видим в повседневной жизни, первый добавленный в список элемент - первым его покидает. Еще эту структуру называют 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 элементов, в обратном случае, хеширование работает плохо, и нужно менять хеш-функцию.

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

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

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

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

| Представление о базах данных

Уроки 35 - 37
Представление о базах данных

Изучив эту тему, вы узнаете:

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

Роль информационной системы

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

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

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

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

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

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

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

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

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

Как же организована подобная информационная система и каким образом можно организовать хранение и представление информации в ней?

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

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

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

Рассмотрим другой пример. В предметной области Поликлиника можно выделить следующие классы объектов: врачи, пациенты, диагнозы, специальности врачей и пр. Связи между объектами выделенной предметной области отображены на рис. 4.1.

Рис. 4.1. Пример взаимосвязи классов объектов предметной области Поликлиника

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

Возникает вопрос: как следует представить информацию об этих объектах?

Можно было бы привести такое описание: песня «Spice up your life» в исполнении группы из Англии «Spice Girls», написанная в стиле «Hip-hop» в 1997 году, или, например, песня 1996 года российской группы «Иванушки International» под названием «Тучи» в стиле «Рор».

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

Представить такую информацию можно разными способами, например в виде списка:

1. «Spice up your life», «Spice Girls», Hip-hop, 1997, Англия;
2. «Тучи», «Иванушки International», Pop, 1996, Россия;
3. «Моряк», «Агата Кристи», Rock, 1997, Россия.

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

Таблица 4.1. Сведения о песнях

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

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

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

Основные понятия базы данных

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

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

Основными понятиями базы данных являются поле и запись .

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

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

База данных содержит сведения о многих параметрах объектов предметной области. Поэтому важно, в какой последовательности будут располагаться (записываться) эти параметры. Например, сведения об ученике логично представить в виде записи, где порядок расположения параметров будет следующий: Фамилия, Имя, Отчество, Дата рождения, Улица, Дом, Квартира. Для сравнения рассмотрим неудачный порядок расположения тех же параметров: Невский пр., Тихонов, 07.12.1989, д. 15, Виктор, кв. 48, Николаевич.

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

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

Запись - это совокупность значений параметров конкретного объекта.

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

Контрольные вопросы и задания

1. Какова роль информационной системы при работе с информацией?

2. В чем состоит цель создания информационной системы?

3. Что такое предметная область?

4. Приведите примеры, когда возникает необходимость отбора нужной информации? Как вы это делаете? Важно ли при этом понятие «предметная область»?

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

6. Что такое структурирование данных?

7. Что такое база данных?

8. Что такое поле?

9. Что такое структура записи?

10. Что такое запись?

11. Представьте параметры объектов конкретной предметной области в виде таблицы. Укажите в таблице поля, записи, структуру записи.