Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

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

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

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

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

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

В этой главе рассматривается процесс проектирования типов данных — процесс сопоставления алгоритмов с представлениями данных. Здесь вы столкнетесь с рядом распространенных форм данных, таких как очередь, список и двоичное дерево поиска.

В главе будет также представлена концепция абстрактного типа данных (abstract data type — ADT). Тип ADT упаковывает методы и представления данных проблемно-ориентированным, а не языково-ориентированным способом. После того как вы спроектировали тип ADT, его можно легко многократно использовать при различных обстоятельствах. Понимание типов ADT концептуально подготовит вас к вступлению в мир объектно-ориентированного программирования и языка C++.

Расширенное представление данных 719

Исследование представления данных

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

А как вы представите растровые графические изображения, которые должны храниться в памяти? В растровом изображении каждый пиксель на экране устанавливается индивидуально. Во времена черно-белых экранов для представления одного пикселя можно было использовать один бит (1 или 0) — отсюда и английское название растровых графических изображений bitmapped (побитовое отображение). На цветных мониторах описание одного пикселя занимает более одного бита. Например, выделение по 8 бит каждому пикселю позволяет получить 256 цветов. В настоящее время произошел переход к 65 536 цветам (16 бит на пиксель), 16 777 216 цветам (24 бита на пиксель), 2 147 483 648 (32 била на пиксель) и даже больше. При наличии 32-битовых цветов и разрешающей способности монитора 2560x1440 пикселей для представления одного экрана растровой графики вам понадобится около 118 миллионов битов (14 Мбайт). Следует ли смириться с этим или же разработать какой-то метод сжатия информации? Должно ли это сжатие выполняться без потерь или с потерями (сравнительно неважных данных)? И снова, прежде чем погружаться в кодирование, придется принять множество проектных решений.