Как показала практика, у начинающих кодеров возникает множество вопросов при решении задач по теме «Массивы». В данной статье затронуты вопросы, относящиеся только к массивам в классическом понимании. Работа с контейнерами STL — это отдельная тема.
Как правило, задачи сводятся к следующему: заполнить массив, произвести некие операции с элементами массива, распечатать результат. Уже в постановке задачи угадываются логические блоки её решения. Далее я постараюсь показать типовые «кирпичики», из которых можно сложить решение задачи — т. е. программу.
- Организация массива
- Использование автоматических массивов
- Использование массивов с динамическим выделением памяти
- Заполнение массива случайными числами
- Заполнение массива числами, введёнными пользователем
- Поиск максимального/максимального значения в массиве
- Поиск определённого значения в массиве
- Сумма/произведение отрицательных элементов массива
- Сумма элементов массива с чётными/нечётными индексами
Организация массива
Память под массив может выделяться автоматически или динамически.
Ввод и вывод массива | Фрагмент лекции JavaRush — университета
Автоматическое выделение памяти используют, когда размер массива известен на этапе компиляции (т. е. при написании кода).
Динамическое выделение памяти используют, когда размер массива неизвестен на этапе компиляции (допустим, запрашивается у пользователя).
Оба типа массивов могут быть как глобальными (определёнными вне функций), так и локальными (определёнными внутри функции или блока). Здесь для автоматических массивов существует одна тонкость. Память для локального автоматического массива выделяется в стеке. Поэтому размер такого массива должен быть небольшим.
В противном случае можно получить переполнение стека и, как следствие, аварийное завершение программы. Переполнение стека также можно получить и при небольших размерах локального автоматического массива, при многократных рекурсивных вызовах функции. Поэтому, когда вы определяете в функции автоматический массив, вы должны точно знать, что делаете.
Глобальные автоматические массивы в плане переполнения стека безопасны. Но они будут видны во всём коде, лексикографически расположенному после объявления массивов, что может спровоцировать их использование напрямую, минуя их передачу в функции через параметры. Это приведёт к возникновению побочных эффектов работы функций, что затрудняет отладку и делает программы менее надёжными. Такого использования глобальных массивов следует избегать.
Для массивов, использующих динамическое выделение памяти, память распределяется из «кучи» (heap). Куча — это память, выделяемая программе операционной системой, для использования этой программой. Размер кучи, как правило, значительно больше размера стека, а для ОС, поддерживающих парадигму виртуальной памяти, размер кучи теоретически может ограничиваться только разрядностью приложения.
Массивы. Описание, ввод и вывод элементов массива
Использование автоматических массивов
Автоматические массивы используют, когда размер массива известен на этапе компиляции.
Размер массива в коде настоятельно рекомендуется указывать с помощью именованной константы. Это полезно по нескольким соображениям:
- имя константы должно указывать на область её применения — самодокументирование кода;
- при необходимости изменить в коде размер массива потребуется внести правку только в одном месте;
- размер массива, как правило, используется в циклах прохода по массиву, проверки границы и пр., поэтому использование символического имени избавит от необходимости тщательной проверки и правки всего кода при изменении размера массива.
Тип константного выражения для определения размера (количество элементов) автоматического массива должен быть целочисленный: char , int , unsigned int , long , etc.
Память, отведённая под автоматические массивы, освобождается при выходе из области видимости переменной-массива. Для локальных массивов это функция или блок. Глобальные массивы уничтожаются при выходе из программы.
Пример определения глобального автоматического массива длиной 10 элементов типа int :
Пример определения локального автоматического массива длиной 10 элементов типа int :
Использование массивов с динамическим выделением памяти
Массивы с динамическим выделением памяти используют, когда размер массива не известен на этапе компиляции. Реальный размер массива может вычисляться в программе или вводиться пользователем — неважно.
Память для массива выделяется оператором new в форме new тип[количество_элементов] .
Тип выражения, определяющего размер (количество элементов) массива должен быть целочисленным. Также это выражение может быть и константным.
Когда работа с массивом закончена, память, выделенную под массив необходимо освободить. Это делается с помощью оператора delete в форме delete [] имя_переменной . После того, как память освобождена, работать с массивом нельзя.
Пример использования массива с динамическим выделением памяти:
Заполнение массива значениями
При решении учебных задач, обычно предлагается заполнить массив значениями либо введёнными с клавиатуры, либо случайными значениями из определённого диапазона. Начнём со второго случая, как более простого (Парадокс? Нет, правда жизни).
Заполнение массива случайными числами
Для начала необходим генератор случайных чисел. Ниже приведён код одной из простейших реализаций:
using namespace std; // функция генерации случайного числа из диапазона от range_min до range_max включительно int rrand(int range_min, int range_max)
Однако без дополнительных телодвижений стандартная функция rand() будет при каждом запуске программы генерировать одинаковую последовательность случайных чисел (кстати, это очень удобно при отладке!). Для того, что бы при каждом запуске программы получать уникальную последовательность случайных чисел, функцию rand() надо «разогнать» начальным случайным значением. Это делается с помощью функций srand() и time() .
Заполнение массива значениями, естественно, делаем в цикле. Помним, что элементы массива в C/C++ нумеруются с 0. Следовательно последний элемент массива имеет индекс на единицу меньший, чем размер массива.
В примере показано заполнение глобального автоматического массива из 10 элементов типа int случайными значения из диапазона от −100 до 100 включительно:
#include using namespace std; // функция генерации случайного числа из диапазона от range_min до range_max включительно int rrand(int range_min, int range_max) < return rand() % (range_max — range_min + 1) + range_min; >const unsigned int ARRSIZE = 10; const int ABSLIMIT = 100; int ary[ARRSIZE]; int main(void) < srand(static_cast(time(NULL))); // инициализация массива случайными значениями из диапазона -ABSLIMIT..ABSLIMIT for (unsigned int i = 0; i < ARRSIZE; i++) < ary[i] = rrand(-ABSLIMIT, ABSLIMIT); >return 0; >
Обратите внимание на включение заголовочных файлов!
Заполнение массива числами, введёнными пользователем
Как ни странно, это более сложный случай. Дело в том, что во-первых, наличие человека всегда может приводить к некорректному вводу данных (ошибкам), во-вторых, для человека необходимо обеспечить какой-никакой интерфейс, а в-третьих, система потокового ввода-вывода STL имеет свои неприятные особенности.
Итак, пользуясь предыдущим примером, попробуем написать фрагмент, отвечающий за ввод значений массива с клавиатуры. Добавим в начало кода заголовочный файл #include , а вместо инициализации массива случайными значениями напишем что-то типа:
> ary[i]; >
Оно как бы работает, но если вы попытаетесь в качестве числа (конечно случайно!) ввести 1111111111111111111111111111111111 или 11q, то, в зависимости от компилятора, сможете наблюдать некоторые интересные эффекты работы вашей программы.
Поэтому приходится писать более сложный код:
> ary[i]; if (cin.fail()) < cout cin.clear(); cin.ignore(); > while (fail); >
Подробный разбор данного фрагмента выходит за рамки данной статьи. Но интересующиеся могут его разобрать, вооружившись, например, известной книгой Г. Шилдта.
Вывод на консоль значений из массива
Вывод значений массива на консоль реализуется элементарно. В свете уже вышесказанного даже нечего добавить:
(time(NULL))); // инициализация массива случайными значениями из диапазона -ABSLIMIT..ABSLIMIT for (unsigned int i = 0; i < ARRSIZE; i++) < ary[i] = rrand(-ABSLIMIT, ABSLIMIT); >// вывод в cout значений элементов массива for (unsigned int i = 0; i < ARRSIZE; i++) < cout // поиск максимального значения в массиве и его индекса // при наличии нескольких минимальных значений находится первое int min_val = ary[0]; unsigned int min_idx = 0; for (unsigned int i = 1; i < ARRSIZE; i++) < if (min_val >ary[i]) < min_val = ary[i]; min_idx = i; >> cout
Ввод и вывод массивов
Ввод, вывод и обработка массива осуществляются поэлементно. Одномерный массив вводится и выводится в цикле, цикл организуется по порядковому номеру элемента в массиве (индексу элемента).
Ввод одномерного массива можно осуществить, например, так:
for i:=1 to n do read (x[i]); или
for i:=1 to n do readln (x[i]);
где n – количество элементов в массиве; x – имя массива;
i –порядковый номер элемента в массиве;- i–й элемент массива х.
Пример вывода одномерного массива :
for i:=1 to n do write (x[i],’ ‘);или
for i:=1 to n do writeln (x[i]);
Ввод и вывод элементов двумерного массива осуществляется с помощью двух вложенных циклов. Двумерный массив вводится либо по строкам, либо по столбцам. Если двумерный массив вводится по строкам, то внешний цикл организуется по номеру строки, а внутренний — по номеру столбца. Если массив вводится по столбцам, то внешний цикл организуется по номеру столбца, а внутренний – по номеру строки. Вывод двумерного массива, как правило, осуществляется построчно.
Ввод двумерного массива a размерности n×m:
for i:=1 to n do
for j:=1 to m do read(a[i,j]);
где n –количество строк в массиве; m – количество столбцов в массиве;
i –номер строки массива; j –номер столбца массива; a –имя массива;
a[i,j] — элемент массива a, находящийся в i –й строке, j –ом столбце.
Вывод двумерного массива a размерности n×m в виде прямоугольной матрицы (каждая строка матрицы начинается с новой экранной строки):
for i:=1 to n do
for j:=1 to m do write(a[i,j],’ ‘);
Описание и использование данных строкового типа
Строка – это последовательность произвольных символов алфавита. Длиной строки называется количество символов в последовательности. Длина строки не может превышать 255. Для работы со строками в языке Pascal предусмотрен строковый тип данных.
Значением величины строкового типа является строка. Константы строкового типа записываются в апострофах. Например: ’задача’, ’57+38’, ’а’, ’’ (пустая строка).
Описание строковых типов данных:
typeимя типа =string;илиимя типа =string[n];
var имя строки: имя типа ;
var имя строки: string; или имя строки: string[n];
где n – длина строки.
Если длина строки не указана, по умолчанию она принимается равной 255.
Примеры: var a: string; x: string[10];
К любому символу строки можно обратиться непосредственно, указав за именем строки в квадратных скобках номер позиции этого символа.
Например: s[i] –i- й символ строки s.
Операции над строками
К строкам применимы операции склеивания (конкатенации) и сравнения. Операция склеивания обозначается с помощью символа “+”, а операции сравнения – символами “=”,“<>”,“>”,“>=”,“
Операция склеивания добавляет к первой строке вторую.
Сравнение осуществляется слева направо в соответствии с кодами соответствующих символов. Если длина одной строки меньше другой, то недостающие символы короткой строки заменяются значениями #0.
‘9’>‘123’ результат – true
‘ab’>‘a’ результат – true
Для формирования значения строковой переменной существуют два способа.
- Ввод значения с клавиатуры.
- Использование оператора присваивания. В левой части оператора присваивания при этом должно быть имя строки, а не ее символ. Посимвольное заполнение строки (подобно заполнению массива) в языке Pascal запрещено. Значение отдельных символов строки можно изменять лишь после того, как строка сформирована.
Источник: studfile.net
Использование языка Free Pascal для обработки массивов
Для работы с массивом как с единым целым надо использовать имя массива (без указания индекса в квадратных скобках). Для доступа к элементу массива необходимо указать имя массива и в квадратных скобках порядковый номер элемента массива, например x[1], y[5], c[25], А[8] .
В языке Free Pascal определена операция присваивания для массивов, идентичных по структуре (с одинаковыми типами индексов и компонентов).
Например, если массивы C и D описаны как
var C,D: array [ 0.. 30 ] of real;
то можно записать оператор
Такая операция сразу всем элементам массива C присвоит значения соответствующих им по номерам элементов массива D .
Выполнение любой другой операции над массивом надо организовывать поэлементно, для чего необходимо организовать цикл, в котором последовательно обрабатывать элементы массива; сначала обрабатываем первый элемент массива, затем второй, третий. -й (см. рис. 5.1—5.2). Для обработки элементов массива удобно использовать цикл for..do .
5.4 Ввод-вывод элементов массива
Язык Free Pascal не имеет специальных средств ввода-вывода всего массива, поэтому данную операцию следует организовывать поэлементно. При вводе массива необходимо последовательно вводить 1-й, 2-й и 3-й и т. д. элементы массива, аналогичным образом поступить и при выводе. Следовательно, как для ввода, так и для вывода необходимо организовать стандартный цикл обработки массива (см. рис. 5.3—5.4). Для обращения к элементу массива необходимо указать имя массива и в квадратных скобках номер элемента, например X[5], b[2] и т. д.
Рис. 5.1. Блок-схема обработки элементов массива с использованием цикла с предусловием
Рис. 5.2. Блок-схема обработки элементов массива с использованием цикла for
Рис. 5.3. Алгоритм ввода массива X с использованием цикла с предусловием
Рис. 5.4. Алгоритм ввода массива X с использованием блока модификации
5.4.1 Организация ввода-вывода в консольных приложениях
Рассмотрим реализацию этих алгоритмов в консольных приложениях.
//Ввод элементов массива X с помощью цикла while. var x : array [ 1.. 100 ] of real; i, n : integer; begin writeln ( ’введите размер массива ’ ); readln (N); i : = 1; while ( i <=N) do begin write ( ’ x ( ’, i, ’ )= ’ ); readln ( x [ i ] ); i := i +1 end; end; //Ввод элементов массива X с помощью цикла for. var x : array [ 1.. 1 0 0 ] of real; i, n : integer; begin readln (N); for i :=1 to N do begin write ( ’ x ( ’, i, ’ )= ’ ); readln ( x [ i ] ) >end; end.
Цикл for..do удобнее использовать для обработки всего массива, и в дальнейшем при выполнении подобных операций с массивами мы будем применять именно его.
Вывод массива организуется аналогично вводу, только вместо блока ввода элемента массива будет блок вывода.
Предлагаем читателю рассмотреть несколько вариантов вывода массива вещественных чисел a=(1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8) , самостоятельно разобраться, чем они отличаются друг от друга, и решить, какой из вариантов удобнее в конкретной задаче.
//Вариант 1 for i : = 1 to n do write ( a [ i ] : 3 : 1 );
Результат первого варианта вывода массива на экран представлен на рисунке 5.5. Обратите внимание, что между числами в данном варианте отсутствует пробел.
Рис. 5.5. Результат первого варианта вывода массива
Рис. 5.6. Результат второго варианта вывода массива
Рис. 5.7. Результат третьего варианта вывода массива
//Вариант 2 for i : = 1 to n do write ( a [ i ] : 6 : 2 );
Результат второго варианта вывода массива на экран представлен на рисунке 5.6.
//Вариант 3 for i : = 1 to n do write ( a [ i ] : 3 : 1, ’ ’ );
Результат третьего варианта вывода массива на экран представлен на рисунке 5.7.
//Вариант 4 writeln ( ’массив A ’ ); for i :=1 to n do writeln ( a [ i ] : 6 : 2 );
Результат четвёртого варианта вывода массива на экран представлен на рисунке 5.8.
//Вариант 5 for i :=1 to n do write ( ’ a ( ’, i, ’ )= ’, a [ i ] : 3 : 1, ’ ’ ); >
Результат пятого варианта вывода массива на экран представлен на рисунке 5.9.
Рис. 5.8. Результат четвёртого варианта вывода массива
Рис. 5.9. Результат пятого варианта вывода массива
Рис. 5.10. Результат шестого варианта вывода массива
//Вариант 6 for i :=1 to n do writeln ( ’ a ( ’, i, ’ )= ’, a [ i ] : 6 : 2 );
Результат шестого варианта вывода массива на экран представлен на рисунке 5.10.
увеличить изображение
Рис. 5.11. Форма для задачи вывода массива вещественных чисел
| Name1 | Text | Height | Left | Top | Width | ReadOnly |
| Edit1 | ’ ’ | 23 | 103 | 184 | 492 | True |
| Name1 | Caption | Height | Left | Top | Width |
| label1 | Button1 | 25 | 177 | 392 | 239 |
5.4.2 Организация ввода-вывода в визуальных приложениях
Рассмотрим возможности организации ввода-вывода массивов в визуальных приложениях, для вывода массивов можно использовать стандартный компонент типа TEdit .
Рассмотрим эти возможности на примере стандартной задачи вывода массива вещественных чисел a=(1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8) .
Расположим на форме кнопку (компонент типа TButton ) и компонент типа TEdit (см. рис. 5.11).
В табл. 5.4—5.5 приведены свойства компонентов типа TButton и TEdit .
Наше приложение по щелчку по кнопке Вывод массива будет выводить массив a в поле ввода Edit1 . Алгоритм вывода массива заключается в следующем: каждое число переводится в строку с помощью функции FloatToStr , после чего полученная строка добавляется к полю вывода. Текст обработчика события Button1Click с комментариями приведен ниже.
procedure TForm1. Button1Click ( Sender : TObject ); var //Исходный массив a. a : array [ 1.. 8 ] of real = ( 1. 1, 2. 2, 3. 3, 4. 4, 5. 5, 6. 6, 7. 7, 8. 8 ); i : integer; //В переменной n хранится количество элементов в массиве //вещественных чисел. n : integer =8; S : string= ’ ’; begin Edit1. Text := ’ ’; //Цикл for для последовательной обработки всех элементов //массива a. for i :=1 to n do //Добавление в поле ввода Edit1 строки, которая получена из //элемента массива a[i]. Edit1.
Text := Edit1. Text+FloatToStr ( a [ i ])+ ’ ’; end;
После щелчка по кнопке Вывод массива окно приложения станет подобным тому, которое представлено на рис. 5.12.
Для ввода массивов в Lazarus в простейшем случае можно воспользоваться функцией InputBox . В качестве примера рассмотрим проект, в котором будет осуществляться ввод массива при щелчке по кнопке. На форме расположим единственную кнопку. Текст обработчик события Button1Click с комментариями приведен ниже.
procedure TForm1. Button1Click ( Sender : TObject ); var i, n : byte; X: array [ 1.. 20 ] of real; begin //Количество элементов массива. n:= StrToInt ( InputBox ( ’Ввод элементов массива ’, ’ n= ’, ’ 7 ’ ) ); for i := 1 to n do //Поэлементный ввод. //Ввод очередного элемента массива. X[ i ] : = StrToFloat ( InputBox ( ’Ввод элементов массива ’, ’Введите ’+IntToStr ( i )+ ’элемент ’, ’ 0,00 ’ ) ); end;
увеличить изображение
Рис. 5.12. Вывод массива в поле ввода
Рис. 5.13. Ввод размера массива
Рис. 5.14. Ввод второго элемента массива
При щелчке по кнопке на экране появится окно для ввода размера массива (см. рис. 5.13).
После корректного ввода размера массива, последовательно будут появляться диалоговые окна для ввода очередного элемента, подобные представленному на рис. 5.14.
Для вывода массива с помощью диалогового окна можно применить функцию MessageDlg :
for i := 1 to n do MessageDlg ( ’X[ ’+IntToStr ( i )+ ’ ]= ’+FloatToStr (X[ i ] ), MtInformation, [mbOk], 0 )
которая будет открывать отдельное окно для каждого элемента (см. рис. 5.15).
Рис. 5.15. Вывод третьего элемента массива
Чтобы у пользователя была возможность просматривать элементы массива одновременно, можно сформировать из них строку, а затем вывести её, например, на форму в виде метки или в окне сообщения:
var i, n : byte; X: array [ 1.. 2 0 ] of real; S : string; begin //В переменную строкового типа записывается пустая строка. S:= ’ ’; for i :=1 to n do //Выполняется слияние элементов массива, преобразованных в //строки, и символов пробела; результат — строка, в которой //элементы массива перечислены через пробел. S:=S+FloatToStrF (X[ i ], ffFixed,5,2)+ ’ ’; //Полученную строку можно вывести в виде метки Label2.
Caption :=S; //Вывод строки на форму в виде метки. //Аналогично строку можно вывести в виде сообщения, используя //функцию MessageDlg(S,MtInformation,[mbOk],0);
Наиболее универсальным способом ввода-вывода как одномерных, так и двумерных массивов является компонент типа TStringGrid («таблица строк»). Ознакомимся с этим компонентом подробнее.
На рис. 5.16 представлен проект формы, на которой расположен компонент типа TStringGrid 1 Компонент типа TStringGrid расположен на странице Additional . (таблица строк). Ячейки таблицы строк предназначены для чтения или редактирования данных. Этот компонент может служить как для ввода, так и для вывода массива.
Основные свойства этого компонента представлены в таблице 5.6.
увеличить изображение
Рис. 5.16. Форма с компонентом «таблица»
- ssNone — отсутствие полос прокрутки (в этом случае пользователь может перемещаться по таблице только с помощью курсора);
- ssHorizontal, ssVertical или ssBoth — наличие горизонтальной, вертикальной или обеих полос прокрутки;
- ssAutoHorizontal, ssAutoVertical или ssAutoBoth — появление горизонтальной, вертикальной или обеих полос прокрутки по мере необходимости
Рассмотрим использование компонента для ввода-вывода массивов на примере программы, с помощью которой можно осуществить ввод массива из восьми вещественных чисел, а затем вывести его в обратном порядке.
Разместим на форме две метки, два компонента типа TStringGrid и одну кнопку. Свойства компонентов StringGrid1 и StringGrid2 можно задать такими же, как показано в табл. 5.7.
| ColCount | 8 | 8 | Количество столбцов таблицы |
| RowCount | 1 | 1 | Количество строк таблицы |
| FixedCols | Количество зафиксированных слева столбцов таблицы | ||
| FixedRows | Количество зафиксированных сверху строк таблицы | ||
| Options.goEditing | True | False | Логическая переменная, которая определяет возможность редактирования содержимого ячеек таблицы пользователем |
| Left | 186 | 186 | Расстояние от таблицы до левой границы формы |
| Top | 72 | 216 | Расстояние от таблицы до верхней границы формы |
| Height | 24 | 24 | Высота компонента |
| Width | 518 | 518 | Ширина компонента |
Окно формы приложения ввода-вывода массива будет подобно представленному на рис. 5.17.
В первую таблицу будем вводить элементы массива, во вторую — преобразованный массив. Щелчок по кнопке Выполнить вызовет следующую подпрограмму:
procedure TForm1. Button1Click ( Sender : TObject ); var n, i : integer; a : array [ 0.. 7 ] of real; begin for i :=0 to 7 do //Ввод массива. //Из поля таблицы считывается элемент, //преобразовывается в число и присваивается элементу массива. a [ i ] : = StrToFloat ( StringGrid1.Cells [ i, 0 ] ); for i :=0 to 7 do //Вывод массива. //Элемент массива преобразовывается в строку и помещается в //поле таблицы. StringGrid2.Cells [ i, 0 ] : = FloatToStrF ( a[7 — i ], ffFixed, 5, 2 ); end;
увеличить изображение
Рис. 5.17. Окно формы задачи ввода-вывода массива
увеличить изображение
Рис. 5.18. Окно программы ввода-вывода массива
При запуске программы на выполнение появляется окно приложения, подобное представленному на рис. 5.17, пользователь вводит исходный массив, щёлкает по кнопке Выполнить, после чего окно приложения принимает вид, как на рис. 5.18.
В параграфе 5.4 были рассмотрены различные способы ввода-вывода как в консольных, так и в визуальных приложениях. В дальнейшем мы будем использовать те из них, которые удобнее при решении конкретной задачи.
Теперь перейдём к рассмотрению основных алгоритмов обработки одномерных массивов, многие из которых аналогичны соответствующим алгоритмам обработки последовательностей (вычисление суммы, произведения, поиск элементов по определённому признаку, выборки и т. д.). Отличие заключается в том, что в массиве одновременно доступны все его компоненты, поэтому с массивами становятся возможны более сложные действия (например сортировка элементов массива, удаление и вставка элементов и т. д.).
Источник: intuit.ru