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

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

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

Так, для записи, описанной в начале п.3.4.1, конструкции: stud1.num и stud1.math будут обеспечивать обращения к полям num и math соответственно.

Над выбранным полем записи возможны любые операции, допустимые для типа этого поля.

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

3.5. Таблицы

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

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

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

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

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

3.6.1. Общие сведения о сортировке

Изучение методов сортировки данных в курсе “САОД ” обусловлено необходимостью освоения двух основных навыков в алгоритмизации и программировании задач обработки данных:

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

- оценка эффективности алгоритмов на примере алгоритмов сортировки.

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

В общем случае под сортировкой понимается перестановка элементов

A1, A2, A3, ... An , втакомпорядке Ak1, Ak2, Ak3, ... Akn , что при заданной функции упорядочения F справедливо отношение

F(A k1) ≤ F(A k2) ≤ F (A k3) ≤,.. ≤ F (A kn).

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

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

struct element {field;field y;}

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

Важным свойством алгоритма является его сфера применения:

внутренние сортировки работают с данным в оперативной памяти с произвольным доступом;

внешние сортировки упорядочивают информацию, расположенную на внешних носителях, при этом:

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

- объем данных не позволяет им разместиться в ОЗУ.

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

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

Для того, чтобы обоснованно сделать выбор алгоритма необходимо оценить следующие параметры:

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

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

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

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

Методы или классы алгоритмов сортировки представлены на рис. 3.7

Рис. 3.7 Методы или классы алгоритмов сортировки

Разделение методов внутренней сортировки на сложные (модифицированные) и простые, связано с оценкой эффективности алгоритмов по двум основным параметрам:

- число сравнений ключей элементов (С);

- число перестановок элементов (М).

Для простых методов сортировки эти параметры имеют в среднем порядок n2 а для сложных (модифицированных) - nlog n , где n - количество сортируемых ключей