Структурирование данных с помощью JavaScript: Что такое структура данных? Понятие структурированных данных. Определение и назначение базы данных

• Перевод

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

Очередь

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Перевод

Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью Beau Carnes об основных типах структур данных.

«Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях», - Линус Торвальдс, создатель Linux.

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

В этой статье я покажу вам 10 самых распространенных структур данных. Для каждой из них приведены видео и примеры их реализации на JavaScript. Чтобы вы смогли попрактиковаться, я также добавил несколько упражнений из бета-версии новой учебной программы freeCodeCamp.

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

Связные списки

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

Так устроен связный список

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

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

Временная сложность связного списка ╔═══════════╦═════════════════╦═══════════════╗ ║ Алгоритм ║Среднее значение ║ Худший случай ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(1) ║ ║ Delete ║ O(1) ║ O(1) ║ ╚═══════════╩═════════════════╩═══════════════╝

Упражнения от freeCodeCamp

Стеки

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

Стек организован по принципу LIFO (Last In First Out, «последним пришёл - первым вышел») . Это значит, что последний элемент, который вы добавили в стек, первым выйдет из него.

Так устроен стек

В стеках можно выполнять три операции: добавление элемента (push), удаление элемента (pop) и отображение содержимого стека (pip).

Временная сложность стека ╔═══════════╦═════════════════╦═══════════════╗ ║ Алгоритм ║Среднее значение ║ Худший случай ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(1) ║ ║ Delete ║ O(1) ║ O(1) ║ ╚═══════════╩═════════════════╩═══════════════╝

Упражнения от freeCodeCamp

Очереди

Эту структуру можно представить как очередь в продуктовом магазине. Первым обслуживают того, кто пришёл в самом начале - всё как в жизни.

Так устроена очередь

Очередь устроена по принципу FIFO (First In First Out, «первый пришёл - первый вышел»). Это значит, что удалить элемент можно только после того, как были убраны все ранее добавленные элементы.

Очередь позволяет выполнять две основных операции: добавлять элементы в конец очереди (enqueue ) и удалять первый элемент (dequeue ).

Временная сложность очереди ╔═══════════╦═════════════════╦═══════════════╗ ║ Алгоритм ║Среднее значение ║ Худший случай ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(1) ║ ║ Delete ║ O(1) ║ O(1) ║ ╚═══════════╩═════════════════╩═══════════════╝

Упражнения от freeCodeCamp

Множества

Так выглядит множество

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

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

Пример реализации на JavaScript

Упражнения от freeCodeCamp

Map

Map - это структура, которая хранит данные в парах ключ/значение, где каждый ключ уникален. Иногда её также называют ассоциативным массивом или словарём. Map часто используют для быстрого поиска данных. Она позволяет делать следующие вещи:

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

Так устроена структура map

Упражнения от freeCodeCamp

Хэш-таблицы

Так работают хэш-таблица и хэш-функция

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

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

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

Временная сложность хэш-таблицы ╔═══════════╦═════════════════╦═══════════════╗ ║ Алгоритм ║Среднее значение ║ Худший случай ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(1) ║ O(n) ║ ║ Insert ║ O(1) ║ O(n) ║ ║ Delete ║ O(1) ║ O(n) ║ ╚═══════════╩═════════════════╩═══════════════╝

Упражнения от freeCodeCamp

Двоичное дерево поиска

Двоичное дерево поиска

Дерево - это структура данных, состоящая из узлов. Ей присущи следующие свойства:

• Каждое дерево имеет корневой узел (вверху).
• Корневой узел имеет ноль или более дочерних узлов.
• Каждый дочерний узел имеет ноль или более дочерних узлов, и так далее.

У двоичного дерева поиска есть два дополнительных свойства:

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

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

Временная сложность двоичного дерева поиска ╔═══════════╦═════════════════╦══════════════╗ ║ Алгоритм ║Среднее значение ║Худший случай ║ ╠═══════════╬═════════════════╬══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(log n) ║ O(n) ║ ║ Insert ║ O(log n) ║ O(n) ║ ║ Delete ║ O(log n) ║ O(n) ║ ╚═══════════╩═════════════════╩══════════════╝

Упражнения от freeCodeCamp

Префиксное дерево

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

Так устроено префиксное дерево

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

Посмотрите на иллюстрацию и попробуйте составить слова. Всегда начинайте с корневого узла вверху и спускайтесь вниз. Это дерево содержит следующие слова: ball, bat, doll, do, dork, dorm, send, sense.

Упражнения от freeCodeCamp

Двоичная куча

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

Так устроены минимальная и максимальная кучи

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

Порядок уровней в двоичной куче важен, в отличие от порядка узлов на одном и том же уровне. На иллюстрации видно, что в минимальной куче на третьем уровне значения идут не по порядку: 10, 6 и 12.

Временная сложность двоичной кучи ╔═══════════╦══════════════════╦═══════════════╗ ║ Алгоритм ║ Среднее значение ║ Худший случай ║ ╠═══════════╬══════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(log n) ║ ║ Delete ║ O(log n) ║ O(log n) ║ ║ Peek ║ O(1) ║ O(1) ║ ╚═══════════╩══════════════════╩═══════════════╝

Упражнения от freeCodeCamp

Граф

Графы - это совокупности узлов (вершин) и связей между ними (рёбер). Также их называют сетями.

Графы делятся на два основных типа: ориентированные и неориентированные. У неориентированных графов рёбра между узлами не имеют какого-либо направления, тогда как у рёбер в ориентированных графах оно есть.

Чаще всего граф изображают в каком-либо из двух видов: это может быть список смежности или матрица смежности.

Граф в виде матрицы смежности

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

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

Существуют специальные алгоритмы для просмотра рёбер и вершин в графах - так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search ) и в глубину (depth-first search ). Как вариант, с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа. В видео ниже показано, как на JavaScript выполнить поиск в ширину.

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

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

Определение 1

Структурой данных называется множество элементов данных и внутренних связей между ними.

Существуют простые и интегрированные структуры данных. Простые структуры данных сводятся к битам и организуются непосредственно из битов. К простым структурам относятся:

• числовые;
• битовые;
• символьные;
• логические;
• указатели.

Интегрированные структуры данных организуются из простых и других интегрированных структур.

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

Определение 2

Изменчивостью структуры называется изменение числа элементов и связей между ними.

В соответсвии с признаком изменчивости структуры делятся на

• Статические (векотр, массив, множество, запись, таблица);
• Динамические (стек, очередь, строка, линейные связанные списки, разветвленные связанные списки, графы, деревья.).

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

• Нелинейные(многосвязный список, граф, дерево);
• Линейные с последовательным распределением (вектор, строка, массив, стек, очередь);
• Линейные с произвольным связным распределением (односвязный, и двусвязный список).

Простые структуры и типы данных

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

Целый тип используется для представления количества дискретных объектов. Целые числа могут быть беззнаковыми или отрицательными. Внутреннее представление целого числа может занимать 1, 2 или 4 байта.

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

В случае двоичной системы счисления B=2.

Десятичный тип поддерживают не все языки программирования. Число такого типа представляется в виде m десятичных цифр из которых d цифр находятся справа от десятичной точки.

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

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

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

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

Примеры статических структур

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

Пример 1

Пусть дан массив с именем A.

Тогда элемент А равен 30.

Пример 2

Двумерный массив – это массив, каждый элемент которого сам является одномерным массивом.

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

Определение 4

Записи (хеш-массивы, ассоциативные массивы) – это массивы, которые индексируются не натуральными числами, а строками.

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

Пример 3

Пусть дан хеш-массив с именем B.

Тогда элемент массива B[‘овощ’] равен ‘огурец’.

Примеры динамических структур

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

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

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

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

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

Уроки 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. Представьте параметры объектов конкретной предметной области в виде таблицы. Укажите в таблице поля, записи, структуру записи.