Файл: Операции, производимые с данными..pdf

где i — битовая глубина.

Если известны размеры (в пикселях) рисунка по высоте X и ширине У экрана, а также битовая глубина £, то занимаемый объем рисунка V будет равен

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

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

В палитре имеется 8 цветов. При подстановке N = 8 в

формулу (1.9):

вычисляется битовая глубина i = 3.

При подстановке битовой глубины i = 3, объема рисунка V = 2400 х В = 19200 бит в формулу (1.10):

определяется величина произведения:

Из X = У вытекает, что X х У = 80 х 80.

Ответ: размер рисунка в пикселях равен 80 х 80.

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

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

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

Программы для работы с графическими данными делятся на растровые графические редакторы (Paint, Photoshop) и векторные графические редакторы (Corel Draw, Visio).

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

BMP (Bit Map image) — растровый формат, используемый в системе Windows. Поддерживается большинством графических редакторов (в частности, Paint и Photoshop).

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

TIFF (Tagged Image File Format) — растровый формат. Поддерживается различными операционными системами. Включает алгоритм сжатия без потери качества изображения. Используется в сканерах, а также для хранения и обмена данными.

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

JPEG (Joint Photographic Expert Group) — растровый формат, содержащий алгоритм сжатия, который уменьшает объем файла в десятки раз, но приводит к необратимой потере части информации. Поддерживается большинством операционных систем. Используется в основном в Интернете.

PNG (Portable Network Graphic) — растровый формат, аналогичный GIF. Используется для размещения графики в Интернете.

WMF (Windows Metafile) — векторный формат для Windows-приложений.

EPS (Encapsulated PostScript) — векторный формат, поддерживаемый большинством операционных систем.

CDR — векторный формат, используемый графической системой Corel Draw.

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

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

Цветовая модель RGB (Red-Green-Blue, красный-зе леный-синий) основана на том, что любой цвет может быть

представлен как сумма трех основных цветов: красного, зеленого и синего. В основе цветовой модели лежит декартова система координат. Цветовое пространство представляет собой куб, показанный на рис. 1.10. Любой оттенок цвета (сочетание трех базовых цветов с разной интенсивностью) выражается набором из трех чисел. На каждое число отводится один байт, поэтому интенсивность одного цвета имеет 256 значений (0-255), а общее количество оттенков цвета (2²⁴) — примерно 16,7 млн. Белый цвет в модели RGB представляется как (255, 255, 255), черный — (0, 0, 0), красный — (255, 0, 0), зеленый — (0, 255, 0), синий — (О, 0, 255), а оттенки серого — (К, К, К), где 0 < К 255.

Другая цветовая модель — CMY — является производной модели RGB и также построена на базе трех цветов: С — Cyan (голубого), М — Magenta (пурпурного) и У — Yellow (желтого), которые образуются следующим образом. Голубой цветС(0, 255, 255) является комбинацией синего и зеленого, желтый цвет У(255, 255, 0) — зеленого и красного, а пурпурный цветМ(255, 0, 255) — красного и синего. Преобразование данных из RGB в CMY выполняется с помощью простой операции

Выражение (1.11) показывает, что свет, отраженный от поверхности чисто голубого цвета, не содержит красного (поскольку в этом выражении С = 255 - R).

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

7. СТРУКТУРЫ ДАННЫХ

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

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

Различают одномерные и многомерные массивы.

Одномерный массив имеет одно измерение, его примером является вектор

который имеет размерность т ив котором индекс у = 1, ..., т указывает номер элемента.

Многомерный массив имеет несколько измерений. Его примером может служить двумерный массив данных

с двумя индексами (измерениями) i = 1, ..., /г, у = 1, ..., т и размерностью п х т.

Многомерные массивы бывают однородными и неоднородными.

Однородный массив состоит из элементов одного типа, а неоднородный массив — из элементов разного типа.

Двумерный неоднородный массив, у которого типы данных одинаковы только в столбцах, называется таблицей. В табл. 1.8 приводятся данные трех типов: в столбце «Газета» — символьные, «Цена» и «Стоимость» —вещественные числа, «Количество» — целые числа.

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

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

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

На рис. 1.11 показан расположенный в алфавитном порядке список имен, каждое из которых занимает 8 ячеек памяти.

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

переместить список для освобождения блока ячеек, необходимого для расширения списка.

Связный список состоит из элементов, снабженных указателями на имена смежных элементов. Структура связного списка показана на рис. 1.12.

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

От указателя идет стрелка к адресу имени, на который тот указывает. Для прохождения списка надо начать с указателя головы и найти первое имя (запись). Далее необходимо по указателям записей переходить от одного имени к другому до достижения пустого указателя (Nil). Здесь удаление записи (например, записи «Имя 2, Указатель 2»)оз- начает, что меняется Указатель 1, при этом пунктирной линией со стрелкой показана связь с новым элементом, имеющим Имя 3. Важно подчеркнуть, что расположение записей связного списка в памяти компьютера может быть произвольным.

Деревья — это последняя структура данных, которым соответствует организационная схема типичного вуза (рис. 1.13).

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

дящиеся на самом низком уровне, — терминальными. Нетерминальные узлы связаны с нижестоящими узлами, называемыми потомками.

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

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

После ячейки с данными следуют ячейки-указатели на левого потомка (УЛП) и правого потомка (УПП). В терминальных узлах значения обоих указателей равны Nil.

Пример 1.21. Построить бинарное дерево, в узлах которого находятся буквы исходной упорядоченной последовательности А, В, С, D, Е, F>G и соответствующую ему структуру связных списков — узлов.

Бинарное дерево, изображенное на рис. 1.15, строится с помощью бинарного поиска. Первым корневым узлом становится центральный элемент D, разбивающий исходный список на два одинаковых по числу букв подсписка А, В, С и Е, В, G, в которых определяются два центральных элемента — узлы В и Fj являющиеся левым и правым потомками D. Оставшиеся элементы А, С и В, G образуют левые и правые

потомки узлов BnF соответственно.

Согласно принятой на рис. 1.14 структуре узла структура связных списков, соответствующая бинарному дереву на рис. 1.15, будет иметь вид, показанный на рис. 1.16.

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

8. ЕДИНИЦЫ ХРАНЕНИЯ ДАННЫХ

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

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

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

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

Исполняемые файлы — это такие файлы, которые могут выполняться самостоятельно, т. е. не требуют каких-

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

.ехе — готовый к исполнению файл (tetris.exe; win- word.ехе);

.сот — файл операционной системы (command.com);