Общее понятие структуры данных

Понятие модели данных

Модели данных

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

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

1. Набор типов структур данных.

Здесь можно провести аналогию с языками программирования, в которых тоже есть предопределённые типы структур данных, такие как скалярные данные, вектора, массивы, структуры (например, тип struct в языке Си) и т.д.

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

Такими операциями являются: создание и модификация структур данных, внесение новых данных, удаление и модификация существующих данных, поиск данных по различным условиям.

1. Набор общих правил целостности, которые прямо или косвенно определяют множество непротиворечивых состояний базы данных и/или множество изменений её состояния.

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

Теперь рассмотрим подробнее наборы, составляющие модель данных.

Структуризация данных базируется на использовании концепций "агрегации" и "обобщения". Один из первых вариантов структуризации данных был предложен Ассоциацией по языкам обработки данных (Conference on Data Systems Languages, CODASYL) (рис. 2.1).

Рис.2.1 Композиция структур данных по версии CODASYL

Элемент данных – наименьшая поименованная единица данных, к которой СУБД может обращаться непосредственно и с помощью которой выполняется построение всех остальных структур. Для каждого элемента данных должен быть определён его тип.

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

Рис.2.2 Примеры агрегатов: а) простой и б) составной агрегат

Запись – поименованная совокупность элементов данных или эле-ментов данных и агрегатов. Запись – это агрегат, не входящий в состав никакого другого агрегата; она может иметь сложную иерархическую структуру, поскольку допускается многократное применение агрегации. Различают тип записи (её структуру) и экземпляр записи, т.е. запись с конкретными значениями элементов данных. Одна запись описывает свойства одной сущности ПО (экземпляра). Иногда термин "запись" за-меняют термином "группа".

Пример записи, содержащей сведения о сотруднике, приведён на рис. 2.3.

Рис.2.3 Пример записи типа СОТРУДНИК

Эта запись имеет несколько элементов данных (Номер пропуска, Должность, Пол и т.д.) и три агрегата: простые агрегаты ФИО и Адрес и повторяющийся агрегат Телефоны . (Повторяющийся агрегат может включаться в запись произвольное число раз).

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

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

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

Рис. 2.4 Пример диаграммы Бахмана для фрагмента БД "Город"

Здесь запись типа ПОЛИКЛИНИКА является владельцем записей типа ЖИТЕЛЬ диспансеризация . Запись типа ОРГАНИЗАЦИЯ также является владельцем записей типа ЖИТЕЛЬ и они связаны групповым отношением работают . Записи типа РЭУ и типа ЖИТЕЛЬ являются владельцами записей типа КВАРТИРА с отношениями соответственно обслуживают и проживают . Таким образом, запись одного и того же типа может быть членом одного отношения и владельцем другого.

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

Значение реквизита, таким образом, есть в каждый заданный момент времени одна из позиций класса значений данного реквизита, отображающая, как предполагается, соответствующее состояние (из множества состояний) того свойства объекта (явления), которое характеризует реквизит. Так, текущим значением реквизита «температура больного» может быть 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. Запись

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Аннотация: Дается общее понятие структуры данных как исполнителя, который организует работу с данными: хранение, добавление и удаление, поиск и т.п. Рассматриваются реализации одних структур на базе других, в частности, реализации на базе массива. Приводятся наиболее важные из простейших структур данных: очередь и стек, а также их непрерывные реализации на базе массива. Даются многочисленные примеры использования стека в программировании. Рассматривается обратная польская запись формулы (знак операции после аргументов) и способ ее вычисления на стековой машине. В качестве примера использования обратной польской записи рассматривается графический язык PostScript. Материал иллюстрируется проектом "Cтековый калькулятор", реализованным на языке Си.

Структуры данных

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

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

Общее понятие структуры данных

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

Структуры данных удобнее всего реализовывать в объектно-ориентированных языках. В них структуре данных соответствует класс , сами данные хранятся в переменных-членах класса (или доступ к данным осуществляется через переменные-члены), системе предписаний соответствует набор методов класса. Как правило, в объектно-ориентированных языках структуры данных реализуются в виде библиотеки стандартных классов: это так называемые контейнерные классы языка C++, входящие в стандартную библиотеку классов STL , или классы, реализующие различные структуры данных из библиотеки Java Developer Kit языка Java .

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

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

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

Данные, хранящиеся в памяти ЭВМ, представляют собой совокупность нулей и единиц (битов). Биты объединяются в последовательности: байты, слова и т.д. Каждому участку оперативной памяти, который может вместить один байт или слово, присваивается порядковый номер (адрес).

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

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

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

Некоторые структуры:

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

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

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

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

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

Рис. 1.1. Классификация типов данных

1.1.2.Обобщенные структуры или модели данных.

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

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

Любая модель данных должна содержать три компоненты:

1. структура данных - описывает точку зрения пользователя на представление данных.

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

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

В процессе исторического развития в СУБД использовалось следующие модели данных:

· иерархическая,

· сетевая,

· реляционная.

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

1.2.Методы доступа к данным

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

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

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

Существуют два класса методов, реализующих доступ к данным по ключу:

· методы поиска по дереву,

· методы хеширования.

1.2.1.Методы поиска по дереву

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

1. между узлами имеет место отношение типа "исходный - порожденный";

2. есть только один узел, не имеющий исходного узла. Он называется корнем;

3. все узлы за исключением корня имеют только один исходный; каждый узел может иметь несколько порожденных узлов;

4. отношение "исходный - порожденный" действует только в одном направлении, т.е. ни один потомок некоторого узла не может стать для него предком.

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

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

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

Пример: Пусть дан список студентов, содержащий их фамилии и средний бал успеваемости (см. таблицу 1.1). В качестве ключа используется фамилия студента. Предположим, что все записи имеют фиксированную длину, тогда в качестве указателя можно использовать номер записи. Смещение записи в файле в этом случае будет вычисляться как ([номер_записи ] -1) * [длина_записи ] . Пусть аргумент поиска "Петров". На рисунке 1.2 показано одно из возможных для этого набора данных бинарное дерево поиска и путь поиска.

Таблица 1.1
Васильев
Кузнецов
Тихомиров

Рис. 1.2. Поиск по бинарному дереву

Заметим, что здесь используется следующее правило сравнения строковых переменных: считается, что значение символа соответствует его порядковому номеру в алфавите. Поэтому "И" меньше "К", а "К" меньше "С". Если текущие символы в сравниваемых строках совпадают, то сравниваются символы в следующих позициях.

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

Определение: Бинарное дерево называют сбалансированным (balanced ), если высота левого поддерева каждого узла отличается от высоты правого поддерева не более чем на 1.

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

Определение: В-деревом порядка n называется сильно ветвящееся дерево степени 2n+1, обладающее следующими свойствами:

1. Каждый узел, за исключением корня, содержит не менее n и не более 2n ключей.
2. Корень содержит не менее одного и не более 2n ключей.
3. Все листья расположены на одном уровне.
4. Каждый промежуточный узел содержит два списка: упорядоченный по возрастанию значений список ключей и соответствующий ему список указателей (для листовых узлов список указателей отсутствует).

Для такого дерева:

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

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

Рис. 1.3.Сбалансированное дерево

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

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

R -дерево (R -Tree ) это индексная структура для доступа к пространственным данным, предложенная А. Гуттманом (Калифорнийский университет, Беркли). R-дерево допускает произвольное выполнение операций добавления, удаления и поиска данных без периодической переиндексации.

Для представления данных используются записи, каждая из которых имеет уникальный идентификатор (tuple-identifier ). В каждом концевом узле (листе) дерева содержится запись вида (I,tuple-identifier ) , где I - n -мерный параллелепипед, содержащий указатели на пространственные данные (его также называют minimal bounding rectangle , MBR), а каждый элемент в tuple-identifier содержит верхнюю и нижнюю границу параллелепипеда в соответствующем измерении.

Неконцевые узлы содержат записи вида (I, childnode-pointer ) , где I минимальный ограничивающий параллелепипед для MBR всех узлов, производных по отношению к данному. Childnode-pointer - это указатель на производные узлы.

Пусть M и m <= M/2 соответственно максимальное и мимимальное количество элементов, которое может быть размещено в узле. Тогда свойства R-дерева можно описать следующим образом:

· R-Tree является сильно сбалансированным деревом, т.е. все листья находятся на одном уровне.

· Корневой узел имеет, как минимум, двух потомков.

· Для каждого элемента (I, childnode-pointer ) в неконцевом узле I является наименьшим возможным параллелепипедом, т.е. содержит все параллелепипеды производных узлов.

· Каждый концевой узел (лист) содержит от m до M индексных записей.

· Для каждой индексной записи (I, tuple-identifier ) в концевом узле I является параллелепипедом, который содержит n -мерный объект данных, на который указывает tuple-identifier .

1.2.2.Хеширование

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

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