Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 1
Одномерные массивы и указатели
В случае простых переменных каждой области памяти для хранения одной вели чины соответствует свое имя. Если требуется работать с группой величин одного типа, их располагают в памяти последовательно и дают им общее имя, а различают по порядковому номеру. Такая последовательность однотипных величин называ ется массивом. Чтобы лучше себе это представить, простые переменные можно упо добить гражданскому населению, а массивы — обитателям мест лишения свободы.
Массивы, как и любые другие объекты, можно размещать либо с помощью опера торов описания в сегментах данных или стека, либо в динамической области памя ти с помощью операций выделения памяти.
При описании массива после имени в квадратных скобках задается количество его элементов (размерность), например int а[10]. Массив располагается в зависимо сти от места его описания либо в сегменте данных, либо в сегменте стека, и все инструкции по выделению памяти формирует компилятор до выполнения про граммы. Вследствие этого размерность массива может быть задана только констан той или константным выражением.
При описании массив можно инициализировать, то есть присвоить его элементам начальные значения, например:
int а[10] = {1. 1. 2. 2. 5. 100}:
Если инициализирующих значений меньше, чем элементов в массиве, остаток мас сива обнуляется, если больше — лишние значения не используются.
ВНИМАНИЕ
Элементы массивов нумеруются с нуля, поэтому максимальный номер элемента всегда на единицу меньше размерности. Автоматический контроль выхода индекса за границы мас сива не производится, поэтому программист должен следить за этим самостоятельно.
Для данного массива элементы имеют номера от 0 до 9. Номер элемента указыва ется после его имени в квадратных скобках, например, а[0]. а[3]
Задача 1. Количество элементов между минимумом и максимумом
Написать программу, которая для целочисленного массива из 100 элементов опре деляет, сколько положительных элементов располагается между его максималь ным и минимальным элементами. Предполагается, что все элементы массива различны.
Запишем алгоритм в самом общем виде.
1. Определить, где в массиве расположены его максимальный и минимальный эле менты, то есть найти их индексы.
2. Просмотреть все элементы, расположенные между ними. Если элемент масси ва больше нуля, увеличить счетчик элементов на единицу.
Перед написанием программы полезно составить тестовый пример, чтобы более наглядно представить себе алгоритм решения задачи. Ниже представлен пример массива из 10 чисел и обозначены искомые величины:
Ясно, что порядок расположения элементов в массиве заранее не известен, и сна чала может следовать как максимальный, так и минимальный элемент. Поэтому прежде чем просматривать массив в поисках ко личества положительных элементов, требуется определить, какой из этих индек сов больше. Запишем уточненный алгоритм:
3. Обнулить счетчик положительных элементов. Просмотреть массив в указан ном диапазоне. Если очередной элемент больше нуля, увеличить счетчик на единицу
Для экономии времени при отладке значения элементов массива задаются путем инициализации.
В программе использована управляющая последовательность \t, которая задает отступ при выводе на следующую позицию табуляции.
СОВЕТ
После нахождения каждой величины вставлена отладочная печать. Мы рекомендуем ни когда не пренебрегать этим способом отладки и не жалеть времени, стараясь сделать эту печать хорошо читаемой, то есть содержащей необходимые пояснения и хорошо отформа тированной. Это экономит много времени при отладке программы.
Массив просматривается, начиная с элемента, следующего за максимальным (мини мальным), до элемента, предшествующего минимальному (максимальному). Ин дексы границ просмотра хранятся в переменных ibeg и lend. В приведенной выше программе для определения их значений используется тернарная условная опера ция. Можно поступить и по-другому: просматривать массив всегда от максимума к минимуму, а индекс при просмотре увеличивать или уменьшать в зависимости от их взаимного расположения.
В приведенной ниже программе направление просмотра, то есть приращение ин декса, хранится в переменной d. Если массив просматривается «слева направо», она равна 1, иначе -1. Обратите внимание и на изменившееся условие продолже ния этого цикла.
Ввод массива в этом варианте программы осуществляется с клавиатуры. Напоми наем, что в этом случае желательно для проверки вывести введенные значения на печать.
Тестовых примеров для этой задачи должно быть по крайней мере два для случа ев, когда:
1) a[imin] расположен левее a[imax];
2) a[imin] расположен правее a[imax];
Желательно также проверить, как работает программа, если a[imin] и a[imax] расположены рядом, а также в начале и в конце массива (граничные случаи). Элементы массива нужно задавать как положительные, так и отрицательные.
Разница между приведенными способами решения несущественна, но первый ва риант более «прозрачен», поэтому он, на наш взгляд, предпочтительнее. Измените приведенную выше программу так, чтобы она вычисляла произведение отрицательных элементов, расположенных между минимальным и максимальным по модулю элементами массива.
Часто бывает, что точное количество элементов в исходном массиве не задано, но известно, что оно не может превышать некое конкретное значение. В этом случае память под массив выделяется «по максимуму», а затем заполняется только часть этой памяти. Память можно выделить либо с помощью оператора описания в сте ке или сегменте данных, либо в динамической области. Фактическое количество введенных элементов запоминается в переменной, которая затем участвует в орга низации циклов по массиву, задавая его верхнюю границу. Этот подход является весьма распространенным, поэтому мы приводим ниже небольшую, но полезную программу, в которой выполняется только считывание элементов массивах кла виатуры и их вывод на экран:
Несмотря на то, что значение константы n определяется «с запасом», надо обяза тельно проверять, не запрашивается ли большее количество элементов, чем воз можно. Привычка к проверке подобных, казалось бы, маловероятных случаев по зволит вам создавать более надежные программы, а нет ничего более важного для программы, чем надежность. Впрочем, и для человека это качество совсем не лишнее.
Динамические массивы
Если до начала работы программы неизвестно, сколько в массиве элементов, в про грамме следует использовать динамические массивы. Память под них выделяется с помощью операции new или функции mal1ос в динамической области памяти во время выполнения программы. Адрес начала массива хранится в переменной, на зываемой указателем. Например:
Во второй строке описан указатель на целую величину, которому присваивается адрес начала непрерывной области динамической памяти, выделенной с помощью операции new. Выделяется столько памяти, сколько необходимо для хранения n величин типа int. Величина n может быть переменной.
В третьей строке для выделения памяти под n элементов типа doubl е используется функция malloc, унаследованная из библиотеки С. Этот способ устарел, поэтому мы им пользоваться не будем.
ВНИМАНИЕ
Обнуления памяти при ее выделении не происходит. Инициализировать динамический массив нельзя.
Обращение к элементу динамического массива осуществляется так же, как и к эле менту обычного — например а[3]. Можно обратиться к элементу массива и другим способом — *(а + 3). В этом случае мы явно задаем те же действия, что выполня ются при обращении к элементу массива обычным образом. Рассмотрим их подробнее
В переменной-указателе а хранится адрес начала массива (имя статического массива также является указателем на его первый элемент, только константным, то есть ему нельзя присвоить новое значение). Для получения адреса третьего элемента к этому адресу прибавляется смещение 3. Операция сло жения с константой для указателей учитывает размер адресуемых элементов, то есть на самом деле индекс умножается на длину элемента массива: а + 3 * sizeof(int). Затем с помощью операции * (разадресации) выполняется выборка значения из указанной области памяти.
Если динамический массив в какой-то момент работы программы перестает быть нужным и мы собираемся впоследствии использовать эту память повторно, необ ходимо освободить ее с помощью операции de1ete[], например: delete [] а:
Размерность массива при этом не указывается.
ВНИМАНИЕ -
Квадратные скобки в операции delete [] при освобождении памяти из-под массива обяза тельны. Их отсутствие может привести к неопределенному поведению программы. Память, выделенную с помощью mal loc, следует освобождать посредством функции free.
Таким образом, время жизни динамического массива, как и любой динамической переменной, — с момента выделения памяти до момента ее освобождения. Область действия зависит от места описания указателя, через который производится рабо та с массивом. Область действия и время жизни указателей подчиняются общим правилам, рассмотренным лекции. Как вы помните, локальная пере менная при выходе из блока, в котором она описана, «теряется». Если эта перемен ная является указателем и в ней хранится адрес выделенной динамической памя ти, при выходе из блока эта память перестает быть доступной, однако не помечается как свободная, поэтому не может быть использована в дальнейшем. Это называет ся утечкой памяти и является распространенной ошибкой:
Задача 2. Сумма элементов правее последнего отрицательного
Написать программу, которая для вещественного массива из п элементов определяет сумму его элементов, расположенных правее последнего отрицательного элемента.
В этой задаче размерность массива задана переменной величиной. Предполагает ся, что она будет нам известна на этапе выполнения программы до того, как мы будем вводить сами элементы. В этом случае мы сможем выделить в динамиче ской памяти непрерывный участок нужного размера, а потом заполнять его вводимыми
значениями. Если же стоит задача вводить заранее неизвестное количество чисел до тех пор, пока не будет введен какой-либо признак окончания ввода, то заранее выделить достаточное количество памяти не удастся и придется восполь зоваться так называемыми динамическими структурами данных, например спис ком. Мы рассмотрим эти структуры позже, а пока остановимся на первом предположении — что количество элементов массива вводится с клавиату ры до начала ввода самих элементов.
По аналогии с предыдущей задачей нам может прийти в голову такой алгоритм решения этой задачи: просматривая массив с начала до конца, найти номер по следнего отрицательного элемента, а затем организовать цикл суммирования всех элементов, расположенных правее него. Вот как выглядит построенная по этому алгоритму программа (сразу же признаемся, что она далеко не так хороша, как может показаться с первого взгляда):
Поскольку количество элементов заранее не задано, память под массив выделяет ся в операторе 1 на этапе выполнения программы с помощью операции new. Выде ляется столько памяти, сколько необходимо для хранения n элементов веществен ного типа, и адрес начала этого участка заносится в указатель а.
Номер последнего отрицательного элемента массива формируется в переменной ineg. При просмотре массива с помощью оператора 3 в эту переменную последова тельно записываются номера всех отрицательных элементов массива, таким обра зом, после выхода из цикла в ней остается номер самого последнего.
С целью оптимизации программы может возникнуть мысль объединить цикл на хождения этого номера с циклами ввода и контрольного вывода элементов масси ва, но мы не советуем так делать, потому что ввод данных, их вывод и анализ — разные по смыслу действия, и смешивание их в одном цикле не прибавит програм ме ясности. После отладки программы контрольный вывод (оператор 2) можно удалить или закомментировать. В последующих примерах мы для экономии места будем позволять себе его опускать, но это не значит, что вы должны поступать так же!
Теперь перейдем к самому интересному — к критическому анализу нашей первой попытки решения задачи. Для массивов, содержащих отрицательные элементы, эта программа работает верно, но при их отсутствии, как правило, завершается
аварийно. Это связано с тем, что если в массиве нет ни одного отрицательного эле мента, переменной i neg значение не присваивается. Поэтому в операторе for (опе ратор 4) будет использовано значение ineg, ниспосланное Богом. Обычно всевыш ний таких ошибок не прощает, и программа незамедлительно «вылетает». Поэтому в программу необходимо внести проверку, есть ли в массиве хотя бы один отрица тельный элемент. Для этого переменной ineg присваивается начальное значение, не входящее в множество допустимых индексов массива (например, -1). После цикла поиска номера отрицательного элемента выполняется проверка, сохрани лось ли начальное значение ineg неизменным. Если это так, это означает, что усло вие a[i ] < 0 в операторе 3 не выполнилось ни разу, и отрицательных элементов в массиве нет:
Если не останавливаться на достигнутом и подумать, можно предложить и более рациональное решение этой задачи: просматривать массив в обратном порядке, суммируя его элементы, и завершить цикл, как только встретится отрицательный элемент:
В этой программе каждый элемент массива анализируется не более одного раза, а ненужные элементы не просматриваются вообще. Для больших массивов это иг рает роль, поэтому последний вариант программы предпочтительнее, хотя на вид он отличается от предыдущего незначительно.
Для исчерпывающего тестирования этой программы необходимо ввести по край ней мере три варианта исходных данных — когда массив содержит один, несколь ко или ни одного отрицательного элемента.
Измените приведенную выше программу так, чтобы она вычисляла сумму элемен тов, расположенных после самого левого отрицательного элемента.