А.С.Деревянко

Опорный конспект лекций

по курсу

“Организация и структуры данных”

Тема 1. Структуры данных и алгоритмы

1.1. Основные понятия

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

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

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

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

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

1.2. Хранение информации

В ЦВМ можно выделить три основных вида запоминающих устройств: сверхоперативная, оперативная и внешняя память.

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

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

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

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

 

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

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

Под СТРУКТУРОЙ ДАННЫХ в общем случае понимают множество элементов данных и множество связей между ними.

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

Понятие ФИЗИЧЕСКОЙ структуры данных отражает способ физического представления данных в памяти машины. Рассмотрение же структуры данных без учета ее представления в машинной памяти называется абстрактной или ЛОГИЧЕСКОЙ структурой. Существуют процедуры, осуществляющие отображение логической структуры в физическую и, наоборот. Эти процедуры обеспечивают, кроме того, доступ к физическим структурам и выполнение над ними различных операций, причем каждая операция рассматривается применительно к логической или физической структуре данных.

ПРОСТЫМИ (базовыми, примитивными) структурами (типами) данных называются такие, которые не могут быть расчленены на составные части, большие, чем биты. ИНТЕГРИРОВАННЫМИ (структурированными, композитными, сложными) называются такие структуры данных, составными частями которых являются другие структуры - простые или в свою очередь интегрированные.

В зависимости от отсутствия или наличия явно заданных связей между элементами данных принято различать НЕСВЯЗНЫЕ и СВЯЗНЫЕ структуры.

Весьма важный признак структуры данных - ее изменчивость - изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ и ДИНАМИЧЕСКИЕ.

Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры.

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

1) структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, с одной стороны, и интерпретацию двоичного представления, с другой;

2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа;

3) множество допустимых операций, которые применимы к объекту описываемого типа.

 

1.4. Операции над структурами данных

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

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

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

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

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

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

 

1.5 Структурность данных и технология программирования

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

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

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

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

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

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

Тема 2. Простые структуры данных

 

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

 

2.1. Числовые типы

2.1.1.Целые типы

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

Представление целых типов в языке Pascal – integer, shortint, longint.

 

 

2.1.2. Вещественные типы

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

ПРЕДСТАВЛЕНИЕ ВЕЩЕСТВЕННЫХ ЧИСЕЛ В ПАМЯТИ. Формат для представления чисел с плавающей точкой содержит одно или два поля фиксированной длины для знаков. Количество позиций для значащих цифр различно в разных ЭВМ, но существует, тем не менее, общий формат, приведенный на рисунке 2.1a. В соответствии с этой записью формат вещественного числа содержит в общем случае поля мантиссы, порядка и знаков мантиссы и порядка.

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

а).

 

б).

 

Число бит для хранения мантиссы и порядка зависит от типа вещественного числа.

2.1.3. Десятичные типы

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

ДЕСЯТИЧНЫЙ ТИП С ФИКСИРОВАННОЙ ТОЧКОЙ. Данное представляется в виде числа, состоящего из m десятичных цифр, из которых d цифр расположены после десятичной точки.

Внутримашинное представление данного типа носит название десятичного упакованного формата. Каждая десятичная цифра числа занимает полбайта (4 двоичных разряда) и представляется в этом полубайте ее двоичным кодом. Еще полбайта занимает знак числа, который представляется двоичным кодом 1010 - знак "+" или 1011 - знак "-". Представление занимает целое число байт и при необходимости дополняется ведущим нулем.

ТИП ШАБЛОНА. Представляет данные с ограниченным числом десятичных цифр. Внутримашинное представление этого типа: каждая десятичная цифра представляется байтом, содержащим код символа соответствующей цифры. Знак не входит в общее число цифр в числе, для представления знака в старшем полубайте последней цифры числа код 1111 заменяется на 1010 - знак "+" или 1011 - знак "-".

 

2.1.4. Операции над числовыми типами

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

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

 

2.2. Битовые типы

ПРЕДСТАВЛЕНИЕ БИТОВЫХ ТИПОВ. В ряде задач может потребоваться работа с отдельными двоичными разрядами данных. Данные такого типа представляются в виде набора битов, упакованных в байты или слова, и не связанных друг с другом. Операции над такими данными обеспечивают доступ к выбранному биту данного. Над этими типами помимо операций, характерных для числовых типов, допускаются и побитовые операции.

ОПЕРАЦИИ НАД БИТОВЫМИ ТИПАМИ. Над битовыми типами возможны три группы специфических операций: операции булевой алгебры, операции сдвигов, операции сравнения.

Операции булевой алгебры - НЕ (not), ИЛИ (or), И (and), исключающее ИЛИ (xor). Эти операции и по названию, и по смыслу похожи на операции над логическими операндами, но отличие в их применении к битовым операндам состоит в том, что операции выполняются над отдельными разрядами операндов.

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

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

 

2.3. Логический тип

Значениями логического типа может быть одна из предварительно объявленных констант false (ложь) или true (истина).

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

Над логическими типами возможны операции булевой алгебры - НЕ (not), ИЛИ (or), И (and), исключающее ИЛИ (xor) - последняя реализована для логического типа не во всех языках. В этих операциях операнды логического типа рассматриваются как единое целое - вне зависимости от битового состава их внутреннего представления.

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

 

2.4. Символьный тип

Значением символьного типа являются символы из некоторого предопределенного множества. В большинстве современных персональных ЭВМ этим множеством является ASCII (American Standard Code for Information Intechange - американский стандартный код для обмена информацией). Значение символьного типа занимает в памяти 1 байт. Код от 0 до 255 в этом байте задает один из 256 возможных символов ASCII таблицы. ASCII, однако, не является единственно возможным множеством. Другим достаточно широко используемым множеством является код EBCDIC (Extended Binary Coded Decimal Interchange Code - расширенный двоично-кодированный десятичный код обмена), применяемый в системах IBM средней и большой мощности. В EBCDIC код символа также занимает один байт, но с иной кодировкой, чем в ASCII.

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

 

2.5. Перечислимый тип

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

 

2.6. Интервальный тип

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

 

2.7. Указатели

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

2.7.1. Физическая структура указателя

Физическое представление адреса существенно зависит от аппаратной архитектуры вычислительной системы.

2.7.2. Представление указателей в языках программирования

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

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

2.7.3. Операции над указателями

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

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

Операция выборки - одноместная, ее операндом является типизированный указатель, результат - данные, выбранные из памяти по адресу, заданному операндом. Тип результата определяется типом указателя-операнда.

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

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

Операции адресной арифметики выполняются только над типизированными указателями. Единицей измерения в адресной арифметике является размер объекта, который указателем адресуется.

 

Тема 3. Статические структуры данных

 

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

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

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

 

3.1. Векторы

ЛОГИЧЕСКАЯ СТРУКТУРА. Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа. Каждый элемент вектора имеет уникальный в рамках заданного вектора номер. Обращение к элементу вектора выполняется по имени вектора и номеру требуемого элемента.

МАШИННОЕ ПРЕДСТАВЛЕНИЕ. АДРЕСАЦИЯ ЭЛЕМЕНТОВ СТРУКТУР. Элементы вектора размещаются в памяти в подряд расположенных ячейках памяти. Под элемент вектора выделяется количество байт памяти, определяемое базовым типом элемента этого вектора. Размер памяти для хранения вектора определяется произведением длины элемента на число элементов.

В языках программирования вектор представляется одномерным массивом с синтаксисом описания вида (Pascal):

<Имя> : array [n..k] of <тип>;

где n-номер первого элемента, k-номер последнего элемента.

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

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

ByteSise = ( k - n + 1 ) * Sizeof (тип)

Обращение к i-тому элементу вектора выполняется по адресу вектора плюс смещение к данному элементу. Смещение i-ого элемента вектора определяется по формуле:

ByteNumer = ( i- n ) * Sizeof (тип),

а адрес его: @ ByteNumber = @ имя + ByteNumber.

где @ имя - адрес первого элемента вектора.

При доступе к вектору задается имя вектора и номер элемента вектора. Таким образом, адрес i-го элемента может быть вычислен как:

@Имя[i] = @Имя + i*Sizeof(тип) - n*Sizeof(тип) (3.1)

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

Но для этого на этапе выполнения, во-первых, должны быть известны параметры формулы (3.1): @Имя Sizeof(тип), n, а во-вторых, при каждом обращении должны выполняться две операции умножения и две - сложения. Преобразовав формулу (3.1) в формулу (3.2), получим:

@Имя[i] = A0 + i*Sizeof(тип)щ (3.2)

A0 = @Имя - n*Sizeof(тип) ы

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

 

3.2. Массивы

3.2.1. Логическая структура

Массив - такая структура данных, которая характеризуется:

· фиксированным набором элементов одного и того же типа;

· каждый элемент имеет уникальный набор значений индексов;

· количество индексов определяют мерность массива, например, два индекса - двумерный массив, три индекса - трехмерный массив, один индекс - одномерный массив или вектор;

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

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

Синтаксис описания массива представляется в виде:

<Имя> : Array [n1..k1] [n2..k2] .. [nn..kn] of <Тип>.

Для случая двумерного массива:

Mas2D : Array [n1..k1] [n2..k2] of <Тип>, или

Mas2D : Array [n1..k1 , n2..k2] of <Тип>

Наглядно двумерный массив можно представить в виде таблицы из (k1-n1+1) строк и (k2-n2+1) столбцов.

 

3.2.2. Физическая структура

Многомерные массивы хранятся в непрерывной области памяти. Количество элементов массива и размер элемента определяют размер памяти для хранения массива. Принцип распределения элементов массива в памяти определен языком программирования. Так в FORTRAN элементы распределяются по столбцам - так, что быстрее меняется левые индексы, в Pascal - по строкам - изменение индексов выполняется в направлении справа налево.

Количество байтов памяти, занятых двумерным массивом, определяется по формуле :

ByteSize = (k1-n1+1)*(k2-n2+1)*SizeOf(Тип) (3.3)

Адресом массива является адрес первого байта начального компонента массива. Смещение к элементу массива Mas[i1,i2] определяется по формуле:

ByteNumber = [(i1-n1)*(k2-n2+1)+(i2-n2)]*SizeOf(Тип) (3.4)

его адрес : @ByteNumber = @mas + ByteNumber.

 

3.2.3. Операции

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

В соответствии с формулами (3.3), (3.4) и по аналогии с вектором (3.1), (3.2)для двумерного массива с границами изменения индексов:

[B(1)..E(1)][B(2)..E(2)], размещенного в памяти по строкам, адрес элемента с индексами [I(1),I(2)] может быть вычислен как:

Addr[I(1),I(2)] = Addr[B(1),B(2)] +

+ { [I(1)-B(1)] * [E(2)-B(2)+1] + [I(2)-B(2)] }*SizeOf(Тип) (3.5)

Обобщая (3.5) для массива произвольной размерности:

Mas[B(1)..E(2)][B(2)..E(2)]...[B(n)..E(n)]

получим:

Addr[I(1),I(2),…,I(n)] = Addr[B(1),B(2),…B(n) –

_{n n} (3.6)

SizeOf(тип) * S[B(m)*D(m)] + SizeOf(тип) * S[I(m)*D(m)]

^{m=1 m=1}

где Dm зависит от способа размещения массива. При размещении по строкам:

D(m)=[E(m+1)-B(m+1)+1]*D(m+1), где m = n-1,...,1 и D(n)=1

при размещении по столбцам:

D(m)=[E(m-1)-B(m-1)+1]*D(m-1), где m = 2,...,n и D(1)=1

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

· начальный адрес массива - Addr[I(1),I(2),...,I(n)];

· число измерений в массиве - n;

· постоянную составляющую формулы линеаризации (первые две составляющие формулы (3.6);

· для каждого из n измерений массива:

· значения граничных индексов - B(i), E(i);

· множитель формулы линеаризации - D(i).

 

3.2.5. Специальные массивы

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

РАЗРЕЖЕННЫЕ МАССИВЫ. Разреженный массив - массив, большинство элементов которого равны между собой, так что хранить в памяти достаточно лишь небольшое число значений отличных от основного (фонового) значения остальных элементов.

МАССИВЫ С МАТЕМАТИЧЕСКИМ ОПИСАНИЕМ МЕСТОПОЛОЖЕНИЯ НЕФОНОВЫХ ЭЛЕМЕНТОВ. К данному типу массивов относятся массивы, у которых местоположения элементов со значениями, отличными от фонового, могут быть математически описаны, т. е. в их расположении есть какая-либо закономерность.

РАЗРЕЖЕННЫЕ МАССИВЫ СО СЛУЧАЙНЫМ РАСПОЛОЖЕНИЕМ ЭЛЕМЕНТОВ. К данному типу массивов относятся массивы, у которых местоположения элементов со значениями отличными от фонового, не могут быть математически описаны, т. е. в их расположении нет какой-либо закономерности.

 

3.3. Множества

ЛОГИЧЕСКАЯ СТРУКТУРА. Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, char и производные от них типы.

ФИЗИЧЕСКАЯ СТРУКТУРА. Множество в памяти хранится как массив битов, в котором каждый бит указывает, является ли элемент принадлежащим объявленному множеству или нет. Т.о. максимальное число элементов множества 256, а данные типа множество могут занимать не более 32-ух байт.

3.3.5. Операции над множествами

Пусть S1, S2, S3 : set of byte , Над этими множествами определены следующие специфические операции.

1) Объединение множеств: S2+S3. Результатом является множество, содержащее элементы обоих исходных множеств.

2) Пересечение множеств: S2*S3. Результатом является множество, содержащее общие элементы обоих исходных множеств.

3) Проверка на вхождение элемента в множество: a in S1. Результатом этой операции является значение логического типа - true, если элемент a входит в множество S1, false - в противном случае.

 

3.4. Записи (структуры)

3.4.1. Логическое и машинное представление записей

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

В памяти эта структура записи может быть представлена в одном из двух видов :

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

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

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

 

3.4.2. Операции над записями

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

<имя переменной-записи>.<имя поля>

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

 

3.4.3. Записи с вариантами

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

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

 

3.6. Таблицы

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

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

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

· степенные - O(N^a);

· линейные - O(N);

· логарифмические - O(log_a(N)).

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

В последующем изложении все описания алгоритмов даны для работы с таблицей, состоящей из записей R[1], R[2], ..., R[N] с ключами K[1], K[2], ..., K[N]. Во всех случаях N – количество элементов таблицы.

 

3.6.1. Операции логического уровня над таблицами. Поиск

3.6.1.1. Последовательный или линейный поиск

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

Для последовательного поиска в среднем требуется (N+1)/2 сравнений. Таким образом, порядок алгоритма - линейный - O(N).

 

3.6.1.2. Бинарный поиск (дихотомический, двоичный)

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

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

 

3.6.2. Операции логического уровня над таблицами. Сортировка

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

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

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

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

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

4). Сложность алгоритма. Простой алгоритм требует меньшего времени для его реализации и вероятность ошибки в реализации его меньше.

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

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

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

3). Стратегия распределения. Входное множество разбивается на ряд подмножеств (возможно, меньшего объема) и сортировка ведется внутри каждого такого подмножества.

4). Стратегия слияния. Выходное множество получается путем слияния маленьких упорядоченных подмножеств.

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

 

3.6.2.1. Сортировки выборкой

СОРТИРОВКА ПРОСТОЙ ВЫБОРКОЙ. Данный метод реализует практически "дословно" сформулированную выше стратегию выборки.

ОБМЕННАЯ СОРТИРОВКА ПРОСТОЙ ВЫБОРКОЙ. Входное и выходное множество располагаются в одной и той же области памяти; выходное - в начале области, входное - в оставшейся ее части. В исходном состоянии входное множество занимает всю область, а выходное множество - пустое. По мере выполнения сортировки входное множество сужается, а выходное - расширяется.

ПУЗЫРЬКОВАЯ СОРТИРОВКА. Входное множество просматривается, при этом попарно сравниваются соседние элементы множества. Если порядок их следования не соответствует заданному критерию упорядоченности, то элементы меняются местами. В результате одного такого просмотра при сортировке по возрастанию элемент с самым большим значением ключа переместится ("всплывет") на последнее место в множестве. При следующем проходе на свое место "всплывет" второй по величине ключа элемент и т.д. Для постановки на свои места N элементов следует сделать N-1 проходов. Выходное множество, таким образом, формируется в конце сортируемой последовательности, при каждом следующем проходе его объем увеличивается на 1, а объем входного множества уменьшается на 1.

СОРТИРОВКА ШЕЛЛА. Модификация пузырьковой сортировки. Здесь выполняется сравнение ключей, отстоящих один от другого на некотором расстоянии d. Исходный размер d обычно выбирается соизмеримым с половиной общего размера сортируемой последовательности. Выполняется пузырьковая сортировка с интервалом сравнения d. Затем величина d уменьшается вдвое и вновь выполняется пузырьковая сортировка, далее d уменьшается еще вдвое и т.д. Последняя пузырьковая сортировка выполняется при d=1.

3.6.2.2. Сортировки включением

СОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ. Этот метод - "дословная" реализации стратегии включения. Порядок алгоритма сортировки простыми вставками - O(N^2), если учитывать только операции сравнения. Но сортировка требует еще и в среднем N^2./4 перемещений, что делает ее в таком варианте значительно менее эффективной, чем сортировка выборкой.

ПУЗЫРЬКОВАЯ СОРТИРОВКА ВСТАВКАМИ. Входное и выходное множества находятся в одной последовательности, причем выходное - в начальной ее части. В исходном состоянии можно считать, что первый элемент последовательности уже принадлежит упорядоченному выходному множеству, остальная часть последовательности - неупорядоченное входное. Первый элемент входного множества примыкает к концу выходного множества. На каждом шаге сортировки происходит перераспределение последовательности: выходное множество увеличивается на один элемент, а входное - уменьшается. Это происходит за счет того, что первый элемент входного множества теперь считается последним элементом выходного. Затем выполняется просмотр выходного множества от конца к началу с перестановкой соседних элементов, которые не соответствуют критерию упорядоченности. Просмотр прекращается, когда прекращаются перестановки. Это приводит к тому, что последний элемент выходного множества "выплывает" на свое место в множестве.

СОРТИРОВКА УПОРЯДОЧЕННЫМ ДВОИЧНЫМ ДЕРЕВОМ. Алгоритм складывается из построения упорядоченного двоичного дерева и последующего его обхода. Если нет необходимости в построении всего линейного упорядоченного списка значений, то нет необходимости и в обходе дерева, в этом случае применяется поиск в упорядоченном двоичном дереве. Алгоритмы работы с упорядоченными двоичными деревьями рассмотрены в теме 6. Порядок алгоритма - O(N*log₂N)), но в конкретных случаях все зависит от упорядоченности исходной последовательности, который влияет на степень сбалансированности дерева

 

3.6.2.3. Сортировки распределением

ПОРАЗРЯДНАЯ ЦИФРОВАЯ СОРТИРОВКА. Алгоритм требует представления ключей сортируемой последовательности в виде чисел в некоторой системе счисления P. Число проходов сортировка равно максимальному числу значащих цифр в числе - D. В каждом проходе анализируется значащая цифра в очередном разряде ключа, начиная с младшего разряда. Все ключи с одинаковым значением этой цифры объединяются в одну группу. Ключи в группе располагаются в порядке их поступления. После того, как вся исходная последовательность распределена по группам, группы располагаются в порядке возрастания связанных с группами цифр. Процесс повторяется для второй цифры и т.д., пока не будут исчерпаны значащие цифры в ключе. Основание системы счисления P может быть любым, в частном случае 2 или 10. Для системы счисления с основанием P требуется P групп.

БЫСТРАЯ СОРТИРОВКА ХОАРА. Данный алгоритм относится к распределительным и обеспечивает показатели эффективности O(N*log2(N)) даже при наихудшем исходном распределении.

Используются два индекса - i и j - с начальными значениями 1 и N соответственно. Ключ K[i] сравнивается с ключом K[j]. Если ключи удовлетворяют критерию упорядоченности, то индекс j уменьшается на 1 и производится следующее сравнение. Если ключи не удовлетворяют критерию, то записи R[i] и R[j] меняются местами. При этом индекс j фиксируется и начинает меняться индекс i (увеличиваться на 1 после каждого сравнения). После следующей перестановки фиксируется i и начинает изменяться j и т.д. Проход заканчивается, когда индексы i и j становятся равными. Запись, находящаяся на позиции встречи индексов, стоит на своем месте в последовательности. Эта запись делит последовательность на два подмножества. Все записи, расположенные слева от нее имеют ключи, меньшие чем ключ этой записи, все записи справа - большие. Тот же самый алгоритм применяется к левому подмножеству, а затем к правому. Записи подмножества распределяются по двум еще меньшим подмножествам и т.д., и т.д. Распределение заканчивается, когда полученное подмножество будет состоять из единственного элемента - такое подмножество уже является упорядоченным.

 

3.6.2.4. Сортировки слиянием

Алгоритмы сортировки слиянием, как правило, имеют порядок O(N*log2(N)), но отличаются от других алгоритмов большей сложностью и требуют большого числа пересылок. Алгоритмы слияния применяются в основном, как составная часть внешней сортировки. Здесь же для понимания принципа слияния приведен простейший алгоритм слияния в оперативной памяти.

СОРТИРОВКА ПОПАРНЫМ СЛИЯНИЕМ. Входное множество рассматривается, как последовательность подмножеств, каждое из которых состоит из единственного элемента и, следовательно, является уже упорядоченным. На первом проходе каждые два соседних одноэлементных множества сливаются в одно двухэлементное упорядоченное множество. На втором проходе двухэлементные множества сливаются в 4-элементные упорядоченные множества и т.д. В конце концов получается одно большое упорядоченное множество.

 

3.6.3. Прямой доступ и хеширование

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

 

3.6.3..1. Таблицы прямого доступа

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

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

 

3.6.3.2. Таблицы со справочниками

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

 

3.6.3.3. Хешированные таблицы и функции хеширования

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

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

Если функция H, преобразующая ключ в адрес, может порождать коллизии, то однозначной обратной функции: k = H`(r), позволяющей восстановить ключ по известному адресу, существовать не может. Поэтому ключ должен обязательно входить в состав записи хешированной таблицы как одно из ее полей.

К функции хеширования в общем случае предъявляются следующие требования:

* она должна обеспечивать равномерное распределение отображений фактических ключей по пространству записей;

* она должна порождать как можно меньше коллизий для данного фактического множества записей;

* она не должна отображать какую-либо связь между значениями ключей в связь между значениями адресов;

* она должна быть простой и быстрой для вычисления.

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

 

3.6.3.3.1. Проблема коллизий в хешированных таблицах

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

ПОВТОРНОЕ ХЕШИРОВАНИЕ. Повторное хеширование предусматривает следующее: если при попытке записи в таблицу оказывается, что требуемое место в таблице уже занято, то значение записывается в ту же таблицу на какое-то другое место. Другое место определяется при помощи вторичной функции хеширования H2, аргументом которой в общем случае может быть и исходное значение ключа и результат предыдущего хеширования: r = H2(k,r`), где r` - адрес, полученный при предыдущем применении функции хеширования. Если полученный в результате применения функции H2 адрес также оказывается занятым, функция H2 применяется повторно - до тех пор, пока не будет найдено свободное место.

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

ОБЩАЯ ОБЛАСТЬ ПЕРЕПОЛНЕНИЙ. Для таблицы выделяются две области памяти: основная область и область переполнений. Функция хеширования на выходе дает адрес записи или пакета в основной области. При вставке записи, если ее "законное" место в основной области уже занято, запись заносится на первое свободное место в области переполнения. При поиске, если "законное" место в основной занято записью с другим ключом, выполняется линейный поиск в области переполнения.

РАЗДЕЛЬНЫЕ ЦЕПОЧКИ ПЕРЕПОЛНЕНИЙ. В структуру каждой записи добавляется еще одно поле - указатель на следующую запись. Через эти указатели записи с ключами-синонимами связываются в линейный список, начало которого находится в основной таблице, а продолжение - вне ее. При вставке записи в таблицу по функции хеширования вычисляется адрес записи (или пакета) в основной таблице. Если это место в основной таблице свободно, то запись заносится в основную таблицу. Если же место в основной таблице занято, то запись располагается вне ее. Память для такой записи с ключом-синонимом может выделяться либо динамически для каждой новой записи, либо для синонима назначается элемент из заранее выделенной области переполнения. После размещения записи-синонима поле указателя из записи основной таблицы переносится в поле указателя синонима, а на его место в записи основной таблицы записывается указатель на только что размещенный синоним.

 

Тема 4. Полустатические структуры данных

 

4.1. Общие характеристики полустатических структур

Полустатические структуры данных характеризуются такими признаками:

*имеют переменную длину и простые процедуры ее изменения;

* изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения.

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

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

 

4.2 Стеки (очереди LIFO)

4.2.1 Логическая структура стека

Стек - такой последовательный список с переменной длиной, для которого включение и исключение элементов выполняются только с одной стороны списка, называемого вершиной стека (Last In - First Out - "последним пришел - первым исключается"). Основные операции над стеком:

· включение нового элемента (английское название push - заталкивать),

· исключение элемента из стека (англ. pop - выскакивать).

Полезными могут быть также вспомогательные операции:

* определение текущего числа элементов в стеке;

* очистка стека;

неразрушающее чтение элемента из вершины стека

 

4.2.2 Машинное представление стека и реализация операций

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