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

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

1.1. МАТЕМАТИКА НА СТЕКЕ Вычисление формул без грамматического разбора

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

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

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

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

Таблица 1.1. Примерный набор операций на стеке

I Если быть точнее, в оригинале Брукс называет код блок-схемами , а структуры данных - таблицами , но сути дела это не меняет.

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

SWAP

на вершине стека окажется значение sin(X) + cos(X).

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

1.2. РАЗРЕЖЕННЫЕ МАТРИЦЫ

Программирование разреженных структур данных

Обычно матрица представляется в компьютере с помощью двумерного массива, однако далеко не всегда такой подход будет самым экономным. Например, рабочий лист Excel состоит из 65536 строк и 256 столбцов; если

количество строк и столбцов матрицы int> data; каждый элемент матрицы

представлен своими коорди- натами и значением

public:

SparseMatrix(int h, int w) : height(h), width(w) {}

int Height() const { return height; ) int Width() const { return width; }

записать элемент

void SetElement(int row, int col, int element)

{ data[pair<int, int>(row, col)] = element; }

прочитать значение элемента

int GetElement(int row, int col) const

inap<pair<int, int>, int>: :const iterator p =

data.find(pair<int, int>(row, col)); если элемент (row, col) не существует, вернуть нуль иначе - значение элемента return (р == data.endO) ? О : p->second;

SparseMatrix operator+(const SparseMatrix rhs) const; SparseMatrix operator*(const SparseMatrix& rhs) const;

С операциями дело обстоит несколько сложнее. Теоретически можно запрограммировать их точно таким же образом, как и в случае обычных, не разрежённых матриц. Однако эффективность такого решения крайне низка. Представьте, что вы складываете две матрицы размером 100x100, каждая из которых содержит лишь десять ненулевых элементов. Классическое поэлементное сложение потребует 10 ООО операций, хотя изначально понятно, что в результирующей матрице будет не более двадцати ненулевых элементов.

Очевидное решение - рассматривать лишь ненулевые элементы каждой из матриц:

SparseMatrix SparseMatrix::operator+(const SparseMatrix& rhs) const {

копируем левую матрицу в результат SparseMatrix result = *this;

for(map<pair<int, int>, int>::const iterator p = rhs.data.begin(); p != rhs.data.end 0; p++)

извлекаем координаты и значение очередного элемента

правой матрицы

int row = p->first.first;

int col = p->first.second;

int value = p->second;

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

result.SetElement(row, col, value + result.GetElement(row, col));

return result;

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

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

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

создавать новую разреженную матрицу указанной размерности;

считывать и записывать отдельные элементы матриц (начальные значения каэвдого элемента новой матрицы равны нулю);

складывать и умножать разреженные матрицы. Решение

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

С первой подзадачей легко справиться, если использовать класс тар из библиотеки С++.

class SparseMatrix {

private:

int height, width; map<pair<int, int>.

int j = rp->first.second; int n = rp->second;

если строка к равна столбцу b k, увеличиваем сумму по адресу (i, j) if(к == b k)

result..SetEleraent(i, j, result. GetElemenc {i , j) + in*n) ;

return result;

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

J.R. Gilbert, С. Moler, and R. Schreiber. Sparse matrices in Matlab: design and implementation (http: www.mathworks.com/access/helpdesk rl3/ help/pdf doc/otherdocs/simax.pdf).

R. Yuster, U. Zwick, Fast sparse matrix multiplication (http: www.cs.tau. ac.il/%7Ezwick/papers/sparse.pdf).

1.3. БИНАРНЫЕ ДЕРЕВЬЯ - ЭТО ТАКИЕ ДЕРЕВЬЯ...

1.3.1. Игра Животные , или развлечение с бинарными деревьями

Этот проект был впервые опубликован Г. Щегловым в журнале Наука и жизнь (№ 12,1986г.). Игра состоит в том, что компьютер пытается отгадать животное, задуманное человеком, задавая вопросы, на которые человек может отвечать да или нет .

Компьютер начинает игру, располагая единственным вопросом, выводящим на единственное животное: оно мяукает? - кошка . Эти данные можно представить в виде бинарного дерева (рис. 1.1).

оно мяукает?

кошка

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

Рис. 1.1. Исходное бинарное дерево для игры Животные

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

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

for (inap<pair<int, int>, int>: : const iterator p = data .begin {) ; p !- data.end0; p++)

int i = p->f irst. first ; int к - p->first.second; int Ш - p->second;

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

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

SparseMatrix SparseMatrix::operator*(const SparseMatrix& rhs) const {

результирующая матрица содержит столько строк, сколько левая и столько столбцов, сколько правая SparseMatrix result(Height(), rhs.Width());

цикл по элементам левой матрицы

for(map<pair<int, int>, int>::const iterator p = data.begin(); p J= data.end0; p++)

значение элемента по адресу (i, к) равно m int i = p->first.first; int к = p->first.second; int m = p->second;

цикл no элементам правой матрицы for(niap<pair<int, int>, int>::consc iterator rp = rhs.data.begin(); rp != rhs.data.end0; rp++)

значение очередного элемента по адресу (b k, j) равно n int b k = rp->first.first;