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

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

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

while (*а++ = *Ь++) ;

вместо

for (i = 0; a[i] != 0; i++) a[i] = b[i];

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

Распределение памяти для строк сложнее, чем для связных списков, поскольку строки имеют различный размер. Действительно, совершенно обобщенный механизм резервирования пространства для строк представляет собой ни что иное, как предоставляемые системой функции new[] и delete[]. Как указывалось в разделе 3.6, для решения этой задачи разработаны различные алгоритмы. Их характеристики производительности зависимы от системы и компьютера. Часто распределение памяти при работе со строками является не такой сложной проблемой, как это может показаться, поскольку используются указатели на строки, а не сами символы. Действительно, обычно мы не предполагаем, что все строки занимают индивидуально вьщеленные блоки памяти. Мы склонны предполагать, что каждая строка занимает область памяти с неопределенным адресом, но достаточно большую, чтобы вмещать строку и ее символ завершения. Следует очень тщательно обеспечивать вьщеление памяти при выполнении операций создания либо удлинения строк. В качестве примера в разделе 3.7 приводится программа, которая читает строки и управляет ими.

Упражнения

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

о 3.56 Написать программу, которая определяет, является ли данная строка палиндромом (одинаково читается в прямом и обратном направлениях), если игнори-

ровать пробелы. Например, программа должна давать положительный ответ для строки if i had а hifi .

3.57 Предположим, что для строк индивидуально выделена память. Создать версии функций strcpy и strcat, которые выделяют память и возвращают указатель на новую результирующую строку.

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

3.59 Написать программу, которая заменяет в данной строке подстроки, состоящие из нескольких пробелов, одним пробелом.

3.60 Реализовать версию программы 3.15, в которой будут использоваться указатели.

о 3.61 Написать эффективную программу, которая вычисляет длину самой большой последовательности пробелов в данной строке, анализируя как можно меньшее количество символов. Подсказка: с возрастанием длины последовательности пробелов программа должна выполняться быстрее.

3.7 Составные структуры данных

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

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

for (i = 0; i < N; i++) for (j = 0; j < N; j++) c[i] [j] = 0.0; for (i = 0; i < N; i++) for (j = 0; j < N; j++) for (k = 0; к < N; k++)

c[i] [j] += a[i] [k]*b[k] [j] ;

Математические расчеты часто естественно выражаются многомерными массивами.

Помимо математических применений привычный способ структурирования информации состоит в использовании таблиц чисел, организованных в виде строк и столбцов. В таблице оценок можно выделить по одной строке для каждого студента и по одному столбцу для каждого предмета. Такая таблица будет представлять двумерный массив с одним индексом для строк и вторым - для столбцов. Если студентов 100, а предметов 10, можно объявить массив в виде grades[100] [10], а затем ссылаться

на оценку /-го студента по у-тому предмету следующим образом: grade[i][j]. Для вычисления средней оценки по предмету необходимо сложить элементы соответствующего столбца и разделить сумму на количество строк. Чтобы вычислить среднюю оценку определенного студента, нужно сложить элементы строки и разделить сумму на количество столбцов и т.п. Двумерные массивы широко используются в приложениях подобного типа. В программе часто целесообразно использовать более двух измерений. Например, в таблице оценок можно использовать третий индекс для учета всех таблиц на протяжении учебного года.

Двумерные массивы - вид удобной записи, поскольку числа хранятся в памяти компьютера, которая, по сути, является одномерным массивом. Во многих языках профаммирования двумерные массивы хранятся в порядке старшинства строк в одномерных массивах. Так в массиве a[M][N] первые N позиций будут заняты первой строкой (элементы от а[0][0] до a[0][N-l]), вторые N позиций - второй строкой (элементы от а[1][0] до a[l][N-l]) и т.д. При организации хранения в порядке старшинства строк последняя сфока кода перемножения матриц из предыдущего абзаца в точности эквивалентна выражению:

ctN*i+j] = a[N*i+k]*b[N*k+j]

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

В программе 3.6 представлен метод динамического выделения памяти массивам, который позволяет использовать программы для различных задач без повторной компиляции. Воспользуемся подобным методом для многомерных массивов. Как выделять память многомерным массивам, размер которых неизвестен на этапе компиляции? Другими словами, необходима возможность ссылаться в программе на элемент массива, такой как a[i]J], но не объявлять массив типа int a;M][N] (например), поскольку значения М и N неизвестны. При организации хранения в порядке старшинства строк выражение вида

int* а = malloc(M*N*sizeof(int));

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

Программа 3.16 Распределение памяти под двумерный массив

Эта функция динамически выделяет память двумерному массиву как массиву массивов. Сначала выделяется пространство массиву указателей, а затем - каждой строке. В этой функции выражение

int **а = malloc2d(M, N) ;

выделяет память массиву целых чисел размером MxN.