ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 442
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
93
const int NUM_CATEGORIES = 4;
X const double categoryThresholds[NUM_CATEGORIES ] =
{0.0, 50000.0, 150000.0, 500000.0};
Y const double licenseCost[NUM_CATEGORIES ] =
{50.0, 200.0, 1000.0, 5000.0};
Z category = 0;
[ while (category < NUM_CATEGORIES && categoryThresholds[category] <= grossSales) {
category++;
}
\ cost = licenseCost[category — 1];
В этом коде используется два массива фиксированных значений.
В первом массиве хранится значение границы объема продаж для каждой категории бизнеса
X
. Например, компания с годовым вало- вым объемом продаж в 65 000 долларов США относится к категории
II, поскольку эта сумма превышает границу в 50 000 долларов США категории II, но не достигает границы в 150 000 долларов США ка- тегории III. Во втором массиве хранится значение стоимости бизнес- лицензии для каждой категории
Y
. Определившись с массивами, мы инициализируем переменную category нулем
Z
и выполняем поиск в массиве categoryThresholds, пока не превысим границу валового объема продаж или пока не закончатся категории
[
. В любом случае, когда цикл завершится, категории 1–4 будут правильно присвоены, исходя из валового объема продаж. Последним шагом станет исполь- зование переменной category для того, чтобы сослаться на стоимость лицензии из массива licenseCost
\
. Как и раньше, мы должны внести небольшую корректировку, преобразовав значения категорий бизне- са в диапазоне 1–4 в диапазон 0–3 нашего массива.
Нескалярные массивы
До сих пор мы работали только с массивами таких простых типов дан- ных, как int и double. Однако часто программисты вынуждены иметь дело с массивами сложных данных — структур или объектов (struct или class)
. Хотя использование сложных типов данных обязательно услож- няет код, оно не обязано делать то же с ходом наших размышлений об обработке массивов. Обычно обработка массива включает только один элемент данных struct или class, и мы можем проигнорировать другие части структуры данных. Тем не менее иногда использование сложных типов данных требует от нас несколько изменить свой подход.
Например, рассмотрим задачу нахождения наибольшего значе- ния среди оценок студентов. Предположим, что вместо массива int у нас есть массив структур, каждая из которых представляет собой набор данных о студенте:
struct student {
int grade;
int studentID;
string name;
};
94 Глава 3
Одно из удобств при работе с массивами заключается в том, что целый массив можно легко инициализировать буквенными значени- ями для осуществления простого тестирования, даже в случае с мас- сивом struct: const int ARRAY_SIZE = 10;
student studentArray[ARRAY_SIZE] = {
{87, 10001, "Fred"},
{28, 10002, "Tom"},
{100, 10003, "Alistair"},
{78, 10004, "Sasha"},
{84, 10005, "Erin"},
{98, 10006, "Belinda"},
{75, 10007, "Leslie"},
{70, 10008, "Candy"},
{81, 10009, "Aretha"},
{68, 10010, "Veronica"}
};
Данное объявление означает, что в массиве studentArray[0] хра- нится значение 87 для переменной grade, 10001 — для переменной studentID,
«Fred» — для переменной name и так далее для остальных девяти элементов массива. Что касается остальной части кода, то его написание могло бы сводиться к элементарному копированию кода из начала этой главы и дальнейшей замене каждой ссылки на форму intArray[subscript] на studentArray[subscript].grade. Это привело бы к следующему результату: int highest = studentArray[0].grade;
for (int i = 1; i < ARRAY_SIZE; i++) {
if (studentArray[i].grade > highest) highest = studentArray[i].grade;
}
Вместо этого предположим, что, поскольку у нас теперь есть до- полнительная информация по каждому студенту, мы хотим найти имя студента с самой высокой оценкой, а не саму оценку. Это потре- бует дополнительной модификации. После завершения цикла мы имеем единственный статистический показатель — лучшую оцен- ку, и это не позволяет напрямую определить ученика, которому она принадлежит. Мы должны снова осуществить поиск в массиве, что- бы найти структуру struct с соответствующим значением grade, что кажется дополнительной работой, которую мы не должны делать.
Чтобы избежать этой проблемы, следует либо дополнительно отсле- живать имя студента, соответствующее текущему значению в пере- менной highest, либо вместо отслеживания наивысшей оценки от- слеживать позицию в массиве, в которой была найдена наивысшая оценка, как мы это делали ранее с histogram. Последний подход яв- ляется наиболее общим, поскольку отслеживание позиции массива позволяет позднее извлечь любой элемент данных для конкретного студента:
X int highPosition = 0;
for (int i = 1; i < ARRAY_SIZE; i++) {
Решение задач с массивами 95
if (studentArray[i].grade >
Y studentArray[highPosition].grade) {
Z highPosition = i;
}
}
Здесь переменная highPosition
X
занимает место highest. По- скольку мы напрямую не отслеживаем наивысшую оценку, когда при- ходит время сравнить наивысшую оценку с текущей, мы используем highPosition в качестве ссылки на studentArray
Y
. Если оценка в те- кущей позиции массива выше, то позиция в нашем цикле обработки присваивается переменной highPosition
Z
. По завершении цикла мы можем получить доступ к имени студента с наивысшей оценкой, используя studentArray[highPosition].name, кроме того, мы можем получить доступ к любым другим данным, относящимся к этому сту- денту.
Многомерные массивы
До сих пор мы обсуждали только одномерные массивы, поскольку они наиболее распространены. Двумерные массивы необычны, а массивы с тремя или более измерениями еще более редки. Это свя- зано с тем, что большинство данных одномерны по своей природе.
Кроме того, данные, которые по своей сути многомерны, могут быть представлены в качестве нескольких одномерных массивов, поэто- му использование многомерного массива всегда остается на усмо- трение программиста. Рассмотрим данные по бизнес-лицензиям в табл. 3.1. Они явно многомерные. Взгляните на них. Это же табли- ца. Тем не менее я представил эти многомерные данные в виде двух одномерных массивов — categoryThresholds и licenseCost. Я мог бы представить таблицу с данными в виде двумерного массива, напри- мер, следующим образом: const double licenseData[2][numberCategories] = {
{0.0, 50000.0, 150000.0, 500000.0},
{50.0, 200.0, 1000.0, 5000.0}
};
Трудно выявить какое-либо преимущество от объединения двух массивов в один. Ни одна часть нашего кода не упрощается, по- скольку нет никаких причин для одновременной обработки всех данных таблицы. Однако ясно то, что мы ухудшили удобочитае- мость и простоту использования табличных данных. В исходной версии имена двух отдельных массивов ясно дают понять, какие данные хранятся в каждом из них. В случае с объединенным мас- сивом нам, программистам, придется помнить о том, что ссылки на форму licenseData[0][] относятся к границам валового объ- ема продаж различных категорий бизнеса, а ссылки на форму licenseData[1][]
— к стоимости бизнес-лицензий.
Однако иногда использование многомерного массива оправдано.
Предположим, мы обрабатываем данные о ежемесячных объемах
96 Глава 3
продаж для трех агентов по продажам, и одна из задач заключается в нахождении самых высоких уровней ежемесячных продаж у любого агента. Имея все данные в одном массиве 3
*
12, мы можем обработать весь этот массив за один раз, используя вложенные циклы: const int NUM_AGENTS = 3;
const int NUM_MONTHS = 12;
X int sales[NUM_AGENTS][NUM_MONTHS] = {
{1856, 498, 30924, 87478, 328, 2653, 387, 3754, 387587, 2873, 276, 32},
{5865, 5456, 3983, 6464, 9957, 4785, 3875, 3838, 4959, 1122, 7766, 2534},
{23, 55, 67, 99, 265, 376, 232, 223, 4546, 564, 4544, 3434}
};
Y int highestSales = sales[0][0];
for (
Zint agent = 0; agent < NUM_AGENTS; agent++) {
for (
[int month = 0; month < NUM_MONTHS; month++) {
if (sales[agent][month] > highestSales)
highestSales = sales[agent][month];
}
}
Несмотря на то, что это простая адаптация базового кода для на- хождения наибольшего числа, здесь есть несколько нюансов. Ког- да мы объявляем двумерный массив, обратите внимание, что ини- циализатор организован по агентам, то есть в виде 3 групп по 12, а не 12 групп по 3
X
. Как вы увидите в следующей задаче, это реше- ние может иметь определенные последствия. Мы инициализируем highestSales первым элементом массива, как обычно
Y
. Вы можете осознать, что при первом прохождении вложенных циклов значе- ния обоих счетчиков циклов будут равны 0, поэтому мы будем срав- нивать это начальное значение highestSales с самим собой. Это не влияет на результат, однако иногда начинающие программисты мо- гут попытаться обойти эту небольшую проблему путем добавления второй инструкции if в тело внутреннего цикла: if (agent != 0 || month != 0)
if (sales[agent][month] > highestSales)
highestSales = sales[agent][month];
Однако это гораздо менее эффективно, чем предыдущая версия, поскольку нам придется выполнять 50 дополнительных сравнений, избегая при этом только одного.
Также обратите внимание на то, что я использовал для пере- менных цикла выразительные имена: agent для внешнего цикла
Z
и month для внутреннего
[
. В одном цикле, который обрабатывает одномерный массив, описательный идентификатор мало что дает.
Однако в двойном цикле, который обрабатывает двумерный массив, выразительные идентификаторы помогают мне поддерживать по- рядок в измерениях и индексах, поскольку я могу посмотреть и уви- деть, что я использую agent в том же измерении, в котором я исполь- зовал NUM_AGENTS при объявлении массива.
Даже при наличии многомерного массива иногда лучше всего иметь дело только с одним измерением за раз. Предположим, ис-
Решение задач с массивами 97
пользуя тот же массив sales, что и в предыдущем коде, мы захотели бы отобразить наивысшее среднемесячное значение объема про- даж. Мы могли бы сделать это, используя двойной цикл, как было показано ранее, однако код был бы более понятным для чтения и простым для написания, если бы мы обращались со всем массивом как с тремя отдельными массивами и обрабатывали их по отдель- ности.
Помните код, который мы неоднократно использовали для вы- числения среднего значения в массиве целых чисел? Давайте пере- делаем его в функцию: double arrayAverage(int intArray[], int ARRAY_SIZE) {
double sum = 0;
for (int i = 0; i < ARRAY_SIZE; i++) {
sum += intArray[i];
}
double average = sum / ARRAY_SIZE; return average;
}
С помощью этой функции мы можем снова изменить базовый код для нахождения наибольшего числа, чтобы отыскать агента с са- мым высоким среднемесячным объемом продаж: double highestAverage =
XarrayAverage(sales[0], 12);
for (int agent = 1; agent < NUM_AGENTS; agent++) {
double agentAverage =
YarrayAverage(sales[agent], 12);
if (agentAverage > highestAverage)
highestAverage = agentAverage;
}
cout << "Highest monthly average: " << highestAverage << "\n";
Изменение здесь заключается в двух вызовах функции arrayAverage
. Первым параметром, принятым этой функцией, яв- ляется одномерный массив типа int. В первом вызове мы передаем sales[0]
в качестве первого аргумента
X
, а во втором вызове пере- даем sales[agent]
Y
. Поэтому в обоих случаях мы указываем индекс для первого измерения двумерного массива sales, но не для второ- го измерения. Из-за прямой взаимосвязи между массивами и адреса- ми в C++ эта ссылка указывает адрес первого элемента конкретной строки, который затем может использоваться нашей функцией в ка- честве базового адреса одномерного массива, состоящего только из этой строки.
Если вы запутались, посмотрите еще раз на объявление масси- ва sales, в частности, на инициализатор. Значения в инициализа- торе перечислены в том же порядке, в котором они будут сохране- ны в памяти при выполнении программы. Таким образом, значение sales[0][0]
, которое равно 1856, будет первым, за ним последует значение sales[0][1] 498 и так далее до последнего значения для первого агента sales[0][11], равного 32. Затем будут перечисле- ны значения для второго агента, начиная со значения sales[1][0],
98 Глава 3
равного 5865. Поэтому несмотря на то, что концептуально массив представляет собой 3 строки по 12 значений, в памяти он сохранен как одна большая последовательность из 36 значений.
Важно отметить, что эта техника работает из-за порядка, в кото- ром мы поместили данные в массив. Если бы массив был организован вдоль другой оси, то есть по месяцам, а не по агентам, мы не смогли бы сделать то, что сделали. Хорошая новость заключается в том, что есть простой способ убедиться в правильности настройки массива — для этого достаточно проверить инициализатор. Если данные, которые требуется обработать индивидуально, не являются непрерывными в инициализаторе массива, это значит, что вы организовали данные не- правильно.
Последнее, что следует отметить в этом коде, — это использова- ние временной переменной agentAverage. Поскольку на значение среднемесячного объема продаж для текущего агента мы потенциаль- но ссылаемся дважды, один раз в условном выражении в инструкции if и затем снова в инструкции присваивания в теле, эта временная пе- ременная исключает возможность того, что функция arrayAverage бу- дет вызвана дважды для одних и тех же данных агента.
Этот метод рассмотрения многомерного массива в качестве мас- сива массивов непосредственно вытекает из основного принци- па разбиения задачи на более простые компоненты и значительно упрощает концептуализацию задачи с многомерными массивами.
Тем не менее эта техника может показаться вам несколько сложной, и если вы относитесь к большинству начинающих программистов на C++, то, вероятно, немного побаиваетесь адресов и стоящей за ними арифметики. Думаю, что лучший способ справиться с этим — это максимально разграничить измерения, поместив один уровень массива внутри структуры struct или класса class. Предположим, что мы создали структуру agentStruct: struct agentStruct {
int monthlySales[12];
};
Взяв на себя труд по созданию структуры struct, мы могли бы подумать о добавлении других данных, вроде идентификационно- го номера агента, однако это и так упростит ход наших размышле- ний. После добавления структуры struct вместо создания двумерно- го массива с данными о продажах мы создаем одномерный массив с данными об агентах: agentStruct agents[3];
Теперь, когда мы вызываем нашу функцию, возвращающую сред- нее значение элементов в массиве, мы не используем специальный прием C++, а просто передаем одномерный массив. Например: int highestAverage = arrayAverage(agents[1].monthlySales, 12);
Решение задач с массивами 99
В каких случаях использовать массивы
Массив — это всего лишь инструмент. Как и с любым другим инстру- ментом, важная часть процесса освоения заключается в понимании, когда его следует использовать, а когда — нет. Обсуждавшиеся до сих пор примеры задач в самих описаниях предполагали использование массивов. Тем не менее в большинстве случаев никто вам этого не подскажет, и вам придется самим принять решение относительно использования массива. Самые распространенные ситуации, в кото- рых может потребоваться принять это решение, — это те, в которых даны агрегированные данные, но не указано, как они должны хра- ниться. Например, в задаче определения моды задание «Напишите
код для обработки массива данных опроса... звучало бы так: «Напишите
код для обработки набора данных опроса... В данном случае выбор отно- сительно использования массива будет за вами. Как вы его сделаете?
Помните, что мы не можем изменить размер массива после его создания. Если бы у нас закончилось свободное пространство, в на- шей программе произошел бы сбой. Таким образом, первое, о чем нужно подумать, — это будем ли мы знать в том месте нашей програм- мы, где потребуется структура агрегированных данных, сколько зна- чений мы будем хранить или, по крайней мере, каково их примерное максимальное количество. Это не значит, что при написании про- граммы мы должны знать размер массива. C++, как и большинство других языков, позволяет создать массив, размер которого опреде- ляется во время выполнения программы. Предположим, что задача определения моды была изменена таким образом, что мы заранее не знаем, сколько у нас есть ответов на опрос, а вместо этого данное значение поступает в программу в виде пользовательского ввода.
В этом случае мы могли бы объявить динамический массив для хра- нения данных опроса. int ARRAY_SIZE;
cout << "Number of survey responses: ";
cin >> ARRAY_SIZE;
Xint *surveyData = new int[ARRAY_SIZE];
for(int i = 0; i < ARRAY_SIZE; i++) {
cout << "Survey response " << i + 1 << ": ";
Ycin >> surveyData[i];
}
Мы объявляем массив, используя нотацию указателей, инициа- лизируя его через вызов оператора new
X
. Из-за связи между указа- телем и типами массивов в языке C++ доступ к этим элементам мож- но получить, используя массивную нотацию
Y
, несмотря на то, что surveyData объявлен как указатель. Обратите внимание, что, по- скольку память для данного массива выделяется динамически, в кон- це программы, когда массив нам больше не нужен, мы должны осво- бодить память: delete[] surveyData;
100 Глава 3
Для массивов используется оператор delete[], а не обычный оператор delete. Хотя в случае с массивом целых чисел это не име- ет никакой разницы, при создании массива объектов оператор delete[]
гарантирует то, что отдельные объекты в массиве будут удалены до удаления самого массива. Поэтому вам следует вырабо- тать привычку всегда использовать оператор delete[] с динамиче- скими массивами.
Необходимость очищать динамическую память — это проклятие для программиста, работающего с C++, однако если вы программи- руете на данном языке, вам этого не избежать. Начинающие про- граммисты часто уклоняются от этой ответственности, поскольку их программы настолько малы и выполняются в такие короткие сроки, что они никогда не замечают вредных последствий от утечек памяти
(когда память, которая больше не используется программой, не ос- вобождается и, следовательно, остается недоступной для остальной системы). Не развивайте эту дурную привычку.
Обратите внимание на то, что мы можем использовать динами- ческий массив только в том случае, если пользователь заранее сооб- щит нам количество ответов на опрос. Рассмотрим другой вариант, когда пользователь начинает вводить ответы опроса, не сообщая нам их количество и указывая на отсутствие дальнейших ответов пу- тем ввода –1 (метод записи данных, известный как значение-метка).
Можем ли мы использовать массив для решения этой задачи?
Это «серая зона». Мы могли бы использовать массив, если бы точно знали максимальное количество ответов. В этом случае мы могли бы объявить массив конкретного размера и предположить, что код в безопасности. Тем не менее в долгосрочной перспективе у нас все равно могли бы возникнуть проблемы. Что, если в будущем количество участников исследования увеличится? Что, если мы за- хотим использовать ту же программу с другим участником? В общем, зачем создавать программу с известным ограничением, если этого можно избежать?
Тогда лучше использовать набор данных нефиксированного раз- мера. Как говорилось ранее, класс векторов из стандартной библио- теки шаблонов C++ действует как массив, но увеличивается по мере необходимости. После объявления и инициализации вектор может обрабатываться точно так же, как и массив. Мы можем присвоить вектору значение или извлечь значение, используя стандартную мас- сивную нотацию. Если вектор заполнил свой изначальный размер и нам нужно добавить дополнительный элемент, мы можем сделать это, используя метод push_back. Решение модифицированной зада- чи с помощью вектора выглядит следующим образом:
X vector surveyData;
Y surveyData.reserve(30);
int surveyResponse;
cout << "Enter next survey response or -1 to end: ";
Z cin >> surveyResponse;
const int NUM_CATEGORIES = 4;
X const double categoryThresholds[NUM_CATEGORIES ] =
{0.0, 50000.0, 150000.0, 500000.0};
Y const double licenseCost[NUM_CATEGORIES ] =
{50.0, 200.0, 1000.0, 5000.0};
Z category = 0;
[ while (category < NUM_CATEGORIES && categoryThresholds[category] <= grossSales) {
category++;
}
\ cost = licenseCost[category — 1];
В этом коде используется два массива фиксированных значений.
В первом массиве хранится значение границы объема продаж для каждой категории бизнеса
X
. Например, компания с годовым вало- вым объемом продаж в 65 000 долларов США относится к категории
II, поскольку эта сумма превышает границу в 50 000 долларов США категории II, но не достигает границы в 150 000 долларов США ка- тегории III. Во втором массиве хранится значение стоимости бизнес- лицензии для каждой категории
Y
. Определившись с массивами, мы инициализируем переменную category нулем
Z
и выполняем поиск в массиве categoryThresholds, пока не превысим границу валового объема продаж или пока не закончатся категории
[
. В любом случае, когда цикл завершится, категории 1–4 будут правильно присвоены, исходя из валового объема продаж. Последним шагом станет исполь- зование переменной category для того, чтобы сослаться на стоимость лицензии из массива licenseCost
\
. Как и раньше, мы должны внести небольшую корректировку, преобразовав значения категорий бизне- са в диапазоне 1–4 в диапазон 0–3 нашего массива.
Нескалярные массивы
До сих пор мы работали только с массивами таких простых типов дан- ных, как int и double. Однако часто программисты вынуждены иметь дело с массивами сложных данных — структур или объектов (struct или class)
. Хотя использование сложных типов данных обязательно услож- няет код, оно не обязано делать то же с ходом наших размышлений об обработке массивов. Обычно обработка массива включает только один элемент данных struct или class, и мы можем проигнорировать другие части структуры данных. Тем не менее иногда использование сложных типов данных требует от нас несколько изменить свой подход.
Например, рассмотрим задачу нахождения наибольшего значе- ния среди оценок студентов. Предположим, что вместо массива int у нас есть массив структур, каждая из которых представляет собой набор данных о студенте:
struct student {
int grade;
int studentID;
string name;
};
94 Глава 3
Одно из удобств при работе с массивами заключается в том, что целый массив можно легко инициализировать буквенными значени- ями для осуществления простого тестирования, даже в случае с мас- сивом struct: const int ARRAY_SIZE = 10;
student studentArray[ARRAY_SIZE] = {
{87, 10001, "Fred"},
{28, 10002, "Tom"},
{100, 10003, "Alistair"},
{78, 10004, "Sasha"},
{84, 10005, "Erin"},
{98, 10006, "Belinda"},
{75, 10007, "Leslie"},
{70, 10008, "Candy"},
{81, 10009, "Aretha"},
{68, 10010, "Veronica"}
};
Данное объявление означает, что в массиве studentArray[0] хра- нится значение 87 для переменной grade, 10001 — для переменной studentID,
«Fred» — для переменной name и так далее для остальных девяти элементов массива. Что касается остальной части кода, то его написание могло бы сводиться к элементарному копированию кода из начала этой главы и дальнейшей замене каждой ссылки на форму intArray[subscript] на studentArray[subscript].grade. Это привело бы к следующему результату: int highest = studentArray[0].grade;
for (int i = 1; i < ARRAY_SIZE; i++) {
if (studentArray[i].grade > highest) highest = studentArray[i].grade;
}
Вместо этого предположим, что, поскольку у нас теперь есть до- полнительная информация по каждому студенту, мы хотим найти имя студента с самой высокой оценкой, а не саму оценку. Это потре- бует дополнительной модификации. После завершения цикла мы имеем единственный статистический показатель — лучшую оцен- ку, и это не позволяет напрямую определить ученика, которому она принадлежит. Мы должны снова осуществить поиск в массиве, что- бы найти структуру struct с соответствующим значением grade, что кажется дополнительной работой, которую мы не должны делать.
Чтобы избежать этой проблемы, следует либо дополнительно отсле- живать имя студента, соответствующее текущему значению в пере- менной highest, либо вместо отслеживания наивысшей оценки от- слеживать позицию в массиве, в которой была найдена наивысшая оценка, как мы это делали ранее с histogram. Последний подход яв- ляется наиболее общим, поскольку отслеживание позиции массива позволяет позднее извлечь любой элемент данных для конкретного студента:
X int highPosition = 0;
for (int i = 1; i < ARRAY_SIZE; i++) {
Решение задач с массивами 95
if (studentArray[i].grade >
Y studentArray[highPosition].grade) {
Z highPosition = i;
}
}
Здесь переменная highPosition
X
занимает место highest. По- скольку мы напрямую не отслеживаем наивысшую оценку, когда при- ходит время сравнить наивысшую оценку с текущей, мы используем highPosition в качестве ссылки на studentArray
Y
. Если оценка в те- кущей позиции массива выше, то позиция в нашем цикле обработки присваивается переменной highPosition
Z
. По завершении цикла мы можем получить доступ к имени студента с наивысшей оценкой, используя studentArray[highPosition].name, кроме того, мы можем получить доступ к любым другим данным, относящимся к этому сту- денту.
Многомерные массивы
До сих пор мы обсуждали только одномерные массивы, поскольку они наиболее распространены. Двумерные массивы необычны, а массивы с тремя или более измерениями еще более редки. Это свя- зано с тем, что большинство данных одномерны по своей природе.
Кроме того, данные, которые по своей сути многомерны, могут быть представлены в качестве нескольких одномерных массивов, поэто- му использование многомерного массива всегда остается на усмо- трение программиста. Рассмотрим данные по бизнес-лицензиям в табл. 3.1. Они явно многомерные. Взгляните на них. Это же табли- ца. Тем не менее я представил эти многомерные данные в виде двух одномерных массивов — categoryThresholds и licenseCost. Я мог бы представить таблицу с данными в виде двумерного массива, напри- мер, следующим образом: const double licenseData[2][numberCategories] = {
{0.0, 50000.0, 150000.0, 500000.0},
{50.0, 200.0, 1000.0, 5000.0}
};
Трудно выявить какое-либо преимущество от объединения двух массивов в один. Ни одна часть нашего кода не упрощается, по- скольку нет никаких причин для одновременной обработки всех данных таблицы. Однако ясно то, что мы ухудшили удобочитае- мость и простоту использования табличных данных. В исходной версии имена двух отдельных массивов ясно дают понять, какие данные хранятся в каждом из них. В случае с объединенным мас- сивом нам, программистам, придется помнить о том, что ссылки на форму licenseData[0][] относятся к границам валового объ- ема продаж различных категорий бизнеса, а ссылки на форму licenseData[1][]
— к стоимости бизнес-лицензий.
Однако иногда использование многомерного массива оправдано.
Предположим, мы обрабатываем данные о ежемесячных объемах
96 Глава 3
продаж для трех агентов по продажам, и одна из задач заключается в нахождении самых высоких уровней ежемесячных продаж у любого агента. Имея все данные в одном массиве 3
*
12, мы можем обработать весь этот массив за один раз, используя вложенные циклы: const int NUM_AGENTS = 3;
const int NUM_MONTHS = 12;
X int sales[NUM_AGENTS][NUM_MONTHS] = {
{1856, 498, 30924, 87478, 328, 2653, 387, 3754, 387587, 2873, 276, 32},
{5865, 5456, 3983, 6464, 9957, 4785, 3875, 3838, 4959, 1122, 7766, 2534},
{23, 55, 67, 99, 265, 376, 232, 223, 4546, 564, 4544, 3434}
};
Y int highestSales = sales[0][0];
for (
Zint agent = 0; agent < NUM_AGENTS; agent++) {
for (
[int month = 0; month < NUM_MONTHS; month++) {
if (sales[agent][month] > highestSales)
highestSales = sales[agent][month];
}
}
Несмотря на то, что это простая адаптация базового кода для на- хождения наибольшего числа, здесь есть несколько нюансов. Ког- да мы объявляем двумерный массив, обратите внимание, что ини- циализатор организован по агентам, то есть в виде 3 групп по 12, а не 12 групп по 3
X
. Как вы увидите в следующей задаче, это реше- ние может иметь определенные последствия. Мы инициализируем highestSales первым элементом массива, как обычно
Y
. Вы можете осознать, что при первом прохождении вложенных циклов значе- ния обоих счетчиков циклов будут равны 0, поэтому мы будем срав- нивать это начальное значение highestSales с самим собой. Это не влияет на результат, однако иногда начинающие программисты мо- гут попытаться обойти эту небольшую проблему путем добавления второй инструкции if в тело внутреннего цикла: if (agent != 0 || month != 0)
if (sales[agent][month] > highestSales)
highestSales = sales[agent][month];
Однако это гораздо менее эффективно, чем предыдущая версия, поскольку нам придется выполнять 50 дополнительных сравнений, избегая при этом только одного.
Также обратите внимание на то, что я использовал для пере- менных цикла выразительные имена: agent для внешнего цикла
Z
и month для внутреннего
[
. В одном цикле, который обрабатывает одномерный массив, описательный идентификатор мало что дает.
Однако в двойном цикле, который обрабатывает двумерный массив, выразительные идентификаторы помогают мне поддерживать по- рядок в измерениях и индексах, поскольку я могу посмотреть и уви- деть, что я использую agent в том же измерении, в котором я исполь- зовал NUM_AGENTS при объявлении массива.
Даже при наличии многомерного массива иногда лучше всего иметь дело только с одним измерением за раз. Предположим, ис-
Решение задач с массивами 97
пользуя тот же массив sales, что и в предыдущем коде, мы захотели бы отобразить наивысшее среднемесячное значение объема про- даж. Мы могли бы сделать это, используя двойной цикл, как было показано ранее, однако код был бы более понятным для чтения и простым для написания, если бы мы обращались со всем массивом как с тремя отдельными массивами и обрабатывали их по отдель- ности.
Помните код, который мы неоднократно использовали для вы- числения среднего значения в массиве целых чисел? Давайте пере- делаем его в функцию: double arrayAverage(int intArray[], int ARRAY_SIZE) {
double sum = 0;
for (int i = 0; i < ARRAY_SIZE; i++) {
sum += intArray[i];
}
double average = sum / ARRAY_SIZE; return average;
}
С помощью этой функции мы можем снова изменить базовый код для нахождения наибольшего числа, чтобы отыскать агента с са- мым высоким среднемесячным объемом продаж: double highestAverage =
XarrayAverage(sales[0], 12);
for (int agent = 1; agent < NUM_AGENTS; agent++) {
double agentAverage =
YarrayAverage(sales[agent], 12);
if (agentAverage > highestAverage)
highestAverage = agentAverage;
}
cout << "Highest monthly average: " << highestAverage << "\n";
Изменение здесь заключается в двух вызовах функции arrayAverage
. Первым параметром, принятым этой функцией, яв- ляется одномерный массив типа int. В первом вызове мы передаем sales[0]
в качестве первого аргумента
X
, а во втором вызове пере- даем sales[agent]
Y
. Поэтому в обоих случаях мы указываем индекс для первого измерения двумерного массива sales, но не для второ- го измерения. Из-за прямой взаимосвязи между массивами и адреса- ми в C++ эта ссылка указывает адрес первого элемента конкретной строки, который затем может использоваться нашей функцией в ка- честве базового адреса одномерного массива, состоящего только из этой строки.
Если вы запутались, посмотрите еще раз на объявление масси- ва sales, в частности, на инициализатор. Значения в инициализа- торе перечислены в том же порядке, в котором они будут сохране- ны в памяти при выполнении программы. Таким образом, значение sales[0][0]
, которое равно 1856, будет первым, за ним последует значение sales[0][1] 498 и так далее до последнего значения для первого агента sales[0][11], равного 32. Затем будут перечисле- ны значения для второго агента, начиная со значения sales[1][0],
98 Глава 3
равного 5865. Поэтому несмотря на то, что концептуально массив представляет собой 3 строки по 12 значений, в памяти он сохранен как одна большая последовательность из 36 значений.
Важно отметить, что эта техника работает из-за порядка, в кото- ром мы поместили данные в массив. Если бы массив был организован вдоль другой оси, то есть по месяцам, а не по агентам, мы не смогли бы сделать то, что сделали. Хорошая новость заключается в том, что есть простой способ убедиться в правильности настройки массива — для этого достаточно проверить инициализатор. Если данные, которые требуется обработать индивидуально, не являются непрерывными в инициализаторе массива, это значит, что вы организовали данные не- правильно.
Последнее, что следует отметить в этом коде, — это использова- ние временной переменной agentAverage. Поскольку на значение среднемесячного объема продаж для текущего агента мы потенциаль- но ссылаемся дважды, один раз в условном выражении в инструкции if и затем снова в инструкции присваивания в теле, эта временная пе- ременная исключает возможность того, что функция arrayAverage бу- дет вызвана дважды для одних и тех же данных агента.
Этот метод рассмотрения многомерного массива в качестве мас- сива массивов непосредственно вытекает из основного принци- па разбиения задачи на более простые компоненты и значительно упрощает концептуализацию задачи с многомерными массивами.
Тем не менее эта техника может показаться вам несколько сложной, и если вы относитесь к большинству начинающих программистов на C++, то, вероятно, немного побаиваетесь адресов и стоящей за ними арифметики. Думаю, что лучший способ справиться с этим — это максимально разграничить измерения, поместив один уровень массива внутри структуры struct или класса class. Предположим, что мы создали структуру agentStruct: struct agentStruct {
int monthlySales[12];
};
Взяв на себя труд по созданию структуры struct, мы могли бы подумать о добавлении других данных, вроде идентификационно- го номера агента, однако это и так упростит ход наших размышле- ний. После добавления структуры struct вместо создания двумерно- го массива с данными о продажах мы создаем одномерный массив с данными об агентах: agentStruct agents[3];
Теперь, когда мы вызываем нашу функцию, возвращающую сред- нее значение элементов в массиве, мы не используем специальный прием C++, а просто передаем одномерный массив. Например: int highestAverage = arrayAverage(agents[1].monthlySales, 12);
Решение задач с массивами 99
В каких случаях использовать массивы
Массив — это всего лишь инструмент. Как и с любым другим инстру- ментом, важная часть процесса освоения заключается в понимании, когда его следует использовать, а когда — нет. Обсуждавшиеся до сих пор примеры задач в самих описаниях предполагали использование массивов. Тем не менее в большинстве случаев никто вам этого не подскажет, и вам придется самим принять решение относительно использования массива. Самые распространенные ситуации, в кото- рых может потребоваться принять это решение, — это те, в которых даны агрегированные данные, но не указано, как они должны хра- ниться. Например, в задаче определения моды задание «Напишите
код для обработки массива данных опроса... звучало бы так: «Напишите
код для обработки набора данных опроса... В данном случае выбор отно- сительно использования массива будет за вами. Как вы его сделаете?
Помните, что мы не можем изменить размер массива после его создания. Если бы у нас закончилось свободное пространство, в на- шей программе произошел бы сбой. Таким образом, первое, о чем нужно подумать, — это будем ли мы знать в том месте нашей програм- мы, где потребуется структура агрегированных данных, сколько зна- чений мы будем хранить или, по крайней мере, каково их примерное максимальное количество. Это не значит, что при написании про- граммы мы должны знать размер массива. C++, как и большинство других языков, позволяет создать массив, размер которого опреде- ляется во время выполнения программы. Предположим, что задача определения моды была изменена таким образом, что мы заранее не знаем, сколько у нас есть ответов на опрос, а вместо этого данное значение поступает в программу в виде пользовательского ввода.
В этом случае мы могли бы объявить динамический массив для хра- нения данных опроса. int ARRAY_SIZE;
cout << "Number of survey responses: ";
cin >> ARRAY_SIZE;
Xint *surveyData = new int[ARRAY_SIZE];
for(int i = 0; i < ARRAY_SIZE; i++) {
cout << "Survey response " << i + 1 << ": ";
Ycin >> surveyData[i];
}
Мы объявляем массив, используя нотацию указателей, инициа- лизируя его через вызов оператора new
X
. Из-за связи между указа- телем и типами массивов в языке C++ доступ к этим элементам мож- но получить, используя массивную нотацию
Y
, несмотря на то, что surveyData объявлен как указатель. Обратите внимание, что, по- скольку память для данного массива выделяется динамически, в кон- це программы, когда массив нам больше не нужен, мы должны осво- бодить память: delete[] surveyData;
100 Глава 3
Для массивов используется оператор delete[], а не обычный оператор delete. Хотя в случае с массивом целых чисел это не име- ет никакой разницы, при создании массива объектов оператор delete[]
гарантирует то, что отдельные объекты в массиве будут удалены до удаления самого массива. Поэтому вам следует вырабо- тать привычку всегда использовать оператор delete[] с динамиче- скими массивами.
Необходимость очищать динамическую память — это проклятие для программиста, работающего с C++, однако если вы программи- руете на данном языке, вам этого не избежать. Начинающие про- граммисты часто уклоняются от этой ответственности, поскольку их программы настолько малы и выполняются в такие короткие сроки, что они никогда не замечают вредных последствий от утечек памяти
(когда память, которая больше не используется программой, не ос- вобождается и, следовательно, остается недоступной для остальной системы). Не развивайте эту дурную привычку.
Обратите внимание на то, что мы можем использовать динами- ческий массив только в том случае, если пользователь заранее сооб- щит нам количество ответов на опрос. Рассмотрим другой вариант, когда пользователь начинает вводить ответы опроса, не сообщая нам их количество и указывая на отсутствие дальнейших ответов пу- тем ввода –1 (метод записи данных, известный как значение-метка).
Можем ли мы использовать массив для решения этой задачи?
Это «серая зона». Мы могли бы использовать массив, если бы точно знали максимальное количество ответов. В этом случае мы могли бы объявить массив конкретного размера и предположить, что код в безопасности. Тем не менее в долгосрочной перспективе у нас все равно могли бы возникнуть проблемы. Что, если в будущем количество участников исследования увеличится? Что, если мы за- хотим использовать ту же программу с другим участником? В общем, зачем создавать программу с известным ограничением, если этого можно избежать?
Тогда лучше использовать набор данных нефиксированного раз- мера. Как говорилось ранее, класс векторов из стандартной библио- теки шаблонов C++ действует как массив, но увеличивается по мере необходимости. После объявления и инициализации вектор может обрабатываться точно так же, как и массив. Мы можем присвоить вектору значение или извлечь значение, используя стандартную мас- сивную нотацию. Если вектор заполнил свой изначальный размер и нам нужно добавить дополнительный элемент, мы можем сделать это, используя метод push_back. Решение модифицированной зада- чи с помощью вектора выглядит следующим образом:
X vector
Y surveyData.reserve(30);
int surveyResponse;
cout << "Enter next survey response or -1 to end: ";
Z cin >> surveyResponse;