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

Таблицы

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

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

Структуры

Структуры в C# аналогичны записям в Delphi в том смысле, что являются данными, передаваемыми по значению, а не по ссылке.

На самом деле семантика структур в C# ближе к классам, за исключением двух основных ограничений:

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

Пример структуры:

struct Point { public int x, y; public Point(int x, int y) { this.x = x; this.y = y; } }

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

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

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

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

Так, для записи, описанной в начале п.3.5.1, конструкции:

stud1.num и stud1.math будут обеспечивать обращения к полям num и math соответственно.

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

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

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

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

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

Во втором случае идентификация немного усложняется:

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

Рассмотрим использование записей с вариантами на примере.

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

Запись с вариантами для такой задачи в языке PASCAL выглядит, как:

type figure = record

fig_type: char; { тип фигуры }

x0, y0: word; { координаты опорной точки }

color: byte; { цвет }

case fig_t: char of

'C': (radius: word);{ радиус окружности }

'R': (len1, len2: word); { длины сторон прямоугольника }

'T': (x1,y1,x2,y2: word); { координаты двух вершин }

end;

а в языке C, как:

typedef struct

{ char fig_type; /* тип фигуры */

unsigned int x0, y0; /* координаты опорной точки */

unsigned char color; /* цвет */

union{

struct{ unsigned short radius; /* радиус окружности */

} cyrcle;

struct { unsigned short len1, len2; /*длины сторон прямоугольн.*/

} rectangle;

struct{ unsigned short t x1,y1,x2,y2; /*координаты двух вершин */

} triangle; } fig_t; } figure;

И если в программе определена переменная fig1 типа figure, в которой хранится описание окружности, то обращение к радиусу этой окружности в языке PASCAL будет иметь вид: fig1.radius, а в C: fig1.circle.radius

Поле с именем fig_type введено для представления идентификатора вида фигуры, который, например, может кодироваться символами: "C"- окружность или "R"- прямоугольник, или "T"- треугольник.

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

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

Рис. 5.1. Выделение памяти для записи с вариантами

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

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

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

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

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

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

* константу N- целое положительное число, число элементов в массиве;

* константу EMPTY - целое число, признак "пусто" (EMPTY=-1);

* массив – int mas[N]; сортируемые последовательности. В функцию будет передоваться указатель на первый элемент.

Дата добавления: 2014-01-07