Сегодня мы с вами наконец-то начинаем новую тему - одномерные массивы .
Одномерные массивы. Определение.
Одномерный массив - это фиксированное количество элементов одного и того же типа, объединенных одним именем, где каждый элемент имеет свой номер. Обращение к элементам массива осуществляется с помощью указания имени массива и номеров элементов.
Var a: array of integer; //или type arr = array of integer; var a: arr;
Между именем типа и именем переменной ставится знак «двоеточие». Array - служебное слово (в переводе с английского означает «массив», «набор»); - в квадратных скобках указывается номер первого элемента, затем, после двух точек, номер последнего элемента массива; of - служебное слово (в переводе с английского «из»); integer - тип элементов массива.
Индексом могут быть не только натуральные числа: мы можем написать так: , [-29..45], [‘a’..’z’], - то есть нам подходят любые символы и числа - главное соблюсти следующее условие: левая часть меньше правой. Для того чтобы определить, что меньше - восклицательный знак(‘!’) или точка(‘.’) используем таблицу ASCII и функции
Как же производится ввод одномерного массива?
Для того чтобы ввести или вывести значения элементов такого массива, используем цикл с параметром(или с постусловием, или с предусловием - в общем, любой цикл.).
For i:= 1 to N do read(a[i]); //где a[i] -- элемент одномерного массива a с индексом (порядковым номером) i.
Как видите, ничего страшного в массивах нет. Массивы применяют в тех случаях, когда нельзя обойтись одной-двумя переменными (примеры таких задач мы рассматривали в решении задач из блока ). В случаях, когда после ввода последовательности целиком пользователю необходимо обратиться к переменным в середине последовательности, в начале, поменять их значения местами, отсортировать.
Раз уж мы затронули тему задач из блока Series, давайте решим пару задачек оттуда с помощью массивов, а не тем увечным способом, которым нам приходилось пользоваться.
Одномерные массивы. Решение задач.
Series8 . Дано целое число N и набор из N целых чисел. Вывести в том же порядке все четные числа из данного набора и количество K таких чисел.
Модифицированное решение:
Var a: array of integer; {мы не знаем заранее N, поэтому берем с запасом.} k, N, i: integer; begin write("N = "); readln(N); write("Введите ", N, " целых чисел: "); for i:= 1 to N do read(a[i]); {заполняем масссив} {Начинаем выбирать чётные числа} write("Чётные числа: "); for i:= 1 to N do begin if a[i] mod 2 = 0 then begin Inc(k); write(a[i], " "); end; end; writeln(); writeln("Количество четных чисел - ", k); end.
Series28 . Дано целое число N и набор из N вещественных чисел: A 1 , A 2 , …, A N . Вывести следующие числа:
(A 1) N , (A 2) N−1 , …, (A N−1) 2 , A N .
Более подробно про возведение числа в степень мы говорили в решении задачи
Модифицированное решение:
Var a: array of integer; N, i, j, n_pow: integer; d, r: real; begin write("N = "); readln(N); write("Введите ", N, " целых чисел: "); for i:= 1 to N do read(a[i]); {Возводим элементы массива в степень} for i:= 1 to N do begin n_pow:= N + 1 - i; d:= a[i]; if n_pow mod 2 <> 0 then r:= d else r:= 1; //в r будет записываться результат while n_pow > 1 do begin n_pow:= n_pow div 2; d:= d * d; if n_pow mod 2 <> 0 then r:= r * d; end; writeln(a[i], " в степени ", N + 1 - i, " равно ", r); end; end.
Ну и напоследок давайте разберём веселенькую задачу на длинную арифметику.
Задача. Найти факториал числа.
Научимся вычислять факториал натурального числа N. Факториал числа - это произведение чисел 1*2*3*…*(N-1)*N (обозначается как N!). Сложность задачи в том, что уже 8!=40320, а 13!=6227020800. Типы данных Integer, Longlnt применимы весьма в ограниченном диапазоне натуральных чисел. Для представления факториала договоримся использовать массив. Пример:
| A | A | A | A | A | A | A | A | A |
| 8 | 0 | 0 | 8 | 6 | 1 | 9 | 9 | 3 |
В массиве записано значение 11!=39916800. Каким образом? В А фиксируется число занятых элементов массива, в А - цифра единиц результата, в А - цифра десятков результата, в А - цифра сотен результата и т. д. Почему так, а не наоборот? Такая запись позволяет исключить сдвиг элементов массива при переносе значений в старший разряд. А сейчас наберите, как обычно, текст программы, выполните компиляцию и, выполните ее в пошаговом режиме, отслеживая изменение значений переменных при не очень большом значении N. Добейтесь полного понимания логики работы программы.
Для того чтобы выполнить программу в пошаговом режиме, нажмите «шаг без входа в подпрограмму» и перейдите в «локальные переменные».
Const MaxN = 300; var A: array of integer; i, j, r, w, N: integer; begin Write("Введите число, факториал которого необходимо подсчитать: "); Read(N); A := 1; A := 1; j:= 2; {Начальные присвоения, начинаем вычислять 2! } while (j <= N) and (A < MaxN) Do {Второе условие позволяет избежать выхода из границ диапазона, если количество цифр в факториале превзойдет 300.} begin r:= 0; i:= 1; {r - перенос из разряда в разряд при выполнении умножения числа j на очередную цифру A[i] предыдущего результата.} while (i <= A) or (r <> 0) Do begin {Пока не «прошли» все цифры предыдущего результата или есть перенос цифры в старший разряд} w:= A[i] * j + r;{Умножаем очередную цифру и прибавляем цифру переноса из предыдущего разряда} A[i] := w mod 10; {Оставляем остаток от деления на 10} r:= w div 10;{Вычисляем значение переноса} if A <> 0 then Inc(A);{Изменяем количество элементов, если их количество увеличилось.} Inc(i); end; Inc(j); end; write("Факториал: "); for i:= A downto 1 Do Write(A[i]);{Вывод результата} end.
Подведем итоги:
Одномерный массив - это конечное упорядоченное множество элементов. За первым элементом идет второй, за вторым - третий и т. д. Индекс может быть чем угодно - и целым числом, и символом. Но чаще мы всё-таки будем пользоваться следующим диапазоном: .
На сегодня все! Если у вас еще остались вопросы о том, как работает программа выше, оставляйте их в комментариях. И очень скоро мы начнем решать задачи на массивы из .
Описание многомерного массива позволяет использовать в программе любой из его элементов как индексированную переменную.
Индексированная переменная (индексное выражение) – обозначение ячейки для хранения конкретного элемента массивауказанием идентификатора массива и индексов элемента по каждому измерению.
В массивах Си/Си++ индексы элементов на единицу меньше заданных математически. Это обстоятельство должно учитываться в программе, особенно при формировании условия повторения (выхода из) цикла.
Особенность работы с массивами в Си/Си++ – любой двумерный массив можно представить в виде одномерного при условии укрупнения единицы хранения (элемента).
Например, если в качестве элементов выбрать строки (столбцы), то двумерный массив превратится в одномерный массив строк (столбцов).
Хранение двумерного массива, например X(m n), реализуется схемой распределения оперативной памяти (рис. 9.4).
Для хранения трехмерного массива, например S(k m n), схема распределения оперативной памяти представлена на рис 9.5 (первая и последняя страницы).
 | x 00 | x 01 | . | . | . | x 0j | . | . | . | x 0 n-1 |
| s 0i0 | s 0i1 | . | . | . | s 0ij | . | . | . | s 0i n-1 |
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
| s 0m-1 0 | s 0 m-1 1 | . | . | . | s 0 m-1 j | . | . | . | s 0 m-1 n-1 |
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
| s k-100 | s k-101 | . | . | . | s k-10j | . | . | . | s k-10 n-1 |
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
| s k-1i0 | s k-1i1 | . | . | . | s k-1ij | . | . | . | s k-1i n-1 |
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
| s k-1m-10 | s k-1 m-1 1 | . | . | . | s k-1 m-1 j | . | . | . | s k-1 m-1 n-1 |
Рис. 9.5. Хранение элементов трехмерного массива
Анализ схем показывает, что все элементы многомерного массива располагаются в оперативной памяти линейно (непрерывно и последовательно). При этом двумерный массив представляется последовательностью строк, трехмерный – последовательностью страниц, каждая из которых в свою очередь является последовательностью строк.
Изменение индексов происходит последовательно – справа налево . Например, для трёхмерного массива вначале полностью перебирается крайний правый индекс (столбцов), затем средний (строк) и последним – левый (страниц).
Длина ячейки хранения каждого элемента определяется типом массива.
Таким образом, любой трехмерный массив представляется в виде одномерного массива двумерных матриц (страниц), каждая из которых, в свою очередь, рассматривается как одномерный массив строк (столбцов).
Следовательно, n-мерный массив в Си/Си++ интерпретируется как совокупность массивов (n-1) размерности, которые также могут быть представлены совокупностью массивов еще меньшей размерности.
Структура обозначения индексированной переменной многомерного массива:
где имя – идентификатор массива;
индекс_i – целая константа, задающая номер элемента по i-му измерению;
– ограничители индекса элемента по каждому измерению.
Так, в описанном ранее массиве D(20 30) элемент, расположенный в первом столбце первой строки, обозначается индексным выражением d, во втором столбце той же строки – d, в первом столбце второй строки – d, текущий – d[i][j], элемент последнего столбца, последней строки – d.
Рассмотренный пример идентификации элементов массива D применим к любому из двумерных массивов, указанных в соответствующем описателе.
Для трехмерных массивов обозначение элементов выполняется аналогично. Например, в массиве S(10 5 15) (описан ранее) элемент первой страницы на пересечении первой строки и первого столбца обозначается индексным выражением s, элемент второго столбца первой строки той же страницы – s, второго столбца второй строки первой страницы – s, текущий – s[k][i][j], а элемент последнего столбца, последней строки, последней страницы – s.
Индекс, при необходимости, может задаваться арифметическим выражением. Например, d, d[i], s, s[i].
ü Внимание! Индекс на момент использования переменной должен быть определен (рассчитан) и укладываться в заданный описателем диапазон.
Рассмотренные формы представления индексированных переменных позволяют осуществить программную реализацию элементов алгоритма с использованием многомерных массивов.
Непрерывное и последовательное расположение элементов многомерного массива в оперативной памяти позволяет адрес каждого элемента представить зависимостью:
а = а1 + смещение,
где а – адрес некоторого текущего элемента массива;
а1 – адрес первого элемента массива;
смещение – номер текущего элемента относительно первого.
Смещение рассчитывается для массивов различной размерности по аналогичным методикам.
Так для двумерного массива
т.е. произведение номера текущей строки на ее размер (число столбцов) плюс номер текущего столбца. Первое слагаемое определяет число элементов в вышерасположенных строках, второе – число элементов в текущей строке от ее начала до искомого включительно.
Для трехмерного массива
смещение = индекс_1*(разм_2* разм_3) +
Первое слагаемое определяет число элементов в ранее расположенных страницах, второе – в предыдущих строках текущей страницы, третье – число элементов в текущей строке текущей страницы.
ü Внимание! Для любого массива размер первого измерения (разм_1) в расчете смещения не используется.
В качестве сомножителей (разм_i) используются значения, указанные в описателях массивов.
Описатели массивов определяют максимально возможные значения (размеры) каждого измерения. Это позволяет использовать зарезервированное пространство оперативной памяти полностью, либо частично, обеспечивая универсальность размеров в сторону уменьшения. Для двумерного массива это утверждение поясняется схемой (рис. 9.6):
| Размер, заданный в описателе (максимальное число столбцов n max) | ||||||||||||
| Размер, используемый в расчетах (n) | ||||||||||||
| Размер, использу-емый в расчетах (m) | Размер, заданный в описателе (максимальное число строк m max) | |||||||||||
Рис. 9.6. Соответствие реальных размеров описанным
Размеры, указанные в описателе определяют количество зарезервированных в оперативной памяти ячеек. При этом ячейки создаваемого двумерного массива располагаются последовательно и линейно (построчно). Если в расчетах зарезервированное пространство используется частично (с меньшим числом строк и/или столбцов), то участки с хранимыми значениями будут чередоваться с неиспользуемыми, количество которых должно быть учтено при указании длины каждой строки в индексном выражении. Суммарное количество элементов каждой строки задано в описателе массива. Поэтому адреса любой ячейки определяется индексным выражением, использующим в качестве одного из параметров указанный в описателе размер.
Так, если двумерный массив z описан как z, а в задаче используется с размерами m=7, n=12, то адрес текущего элемента &z[i][j] = z + i * 20 + j, а не &z[i][j] = z + i * n + j.
Исходя из изложенного, адрес i-го, j-го элемента массива D(20х30) вычисляется по формуле
&(d[i][j]) = d + i * 30 + j,
а адрес k-го, i-го, j-го элемента массива S(10х5х15) вычисляется как
&(s[k][i][j]) = s + k * (5 * 15) + i * 15 + j
Таким образом, индексное выражение полностью определяет адрес конкретной ячейки для хранения соответствующего элемента через параметры описателя, а не укороченные, реально заданные.
С учетом изложенного идентификация переменных алгоритма и создаваемой программы представлена в табл. 9.1.
Таблица 9.1
На основании схемы алгоритма и таблицы идентификации составим программу решения задачи.
Классический вариант программирования задачи
#include
#include
#include
#define M 10 /* увеличенные */
#define N 12 /* размеры массивов */
main() /* заголовок головной функции */
char buf; /*описание символьного массива*/
CharToOem(" Введите m (m<= ",buf); /* запрос */
printf("\n %s %d):",buf,M); /* и */
scanf("%d", &m); /* ввод */
CharToOem(" Введите n (n<= ",buf); /* фактических */
printf("\n %s %d):",buf,N); /* размеров */
scanf("%d", &n); /* массивов */
printf("\n n=%d m=%d ", n, m); /*вывод размеров массивов*/
for(i = 0; i < m; i++) /*заголовок внешнего цикла ввода x[i][j]*/
for(j = 0; j < n; j++) /*заголовок внутр. цикла ввода x[i][j]*/
CharToOem(" Введите значение ",buf); /* ввод */
printf("\n %s x[%d][%d]:",buf,i+1, j+1); /* элементов */
scanf("%f", & x[i][j]); /*массива Х*/
CharToOem(" Массив X",buf); /* вывод */
for(i = 0; i < m; i++)/* заголовок внешн. цикла вывода x[i][j]*/
for(j=0; j < n; j++)/*заголовок внутр. цикла вывода x[i][j]*/
printf(" %5.2f", x[i][j]);
for(i = 0; i < m ; i++ /*заголовок внешн. цикла расчета y[i][j]*/
for(j = 0; j < n; j++)/*заголовок внутр. цикла расчета y[i][j]*/
CharToOem(" Массив Y",buf); /* вывод */
printf("\n %s \n",buf); /*заголовка*/
for(i = 0 ; i < m ; i++)/*заголовок внешн. цикла вывода y[i][j]*/
for(j = 0; j < n; j++) /*заголовок внутр. цикла вывода y[i][j]*/
printf(" %5.2f", y[i][j]);
2 3 – размеры массива;
Результаты решения представлены в приложении 9.1.
Программирование задачи с графическим интерфейсом
Программирование задачи при использовании графического интерфейса предварим его разработкой.
|
|
Для ввода количества столбцов и строк массива планируем однострочные поля редактирования (EditN, EditМ). Для ввода элементов массива Х – многострочное поле редактирования (EditХ). Вывод элементов массивов X и Y реализуем в поля-списки (ListBoxXi, ListBoxYi).
Управление процессом решения реализуем двумя командными кнопками, расположенными в нижней части окна. Назначение каждой определяется ее названием.
Использование графического интерфейса для вывода числовых элементов двумерных массивов в виде таблицы требует:
· представления каждого числового данного соответствующей символьной строкой;
· формирования общей символьной строки (из полученных для каждого элемента строк), соответствующей числовой строке массива;
· размещение сформированной общей символьной строки в окне вывода.
Представление числовых данных символьными строками комментариев не требует.
Формирование элементов выводимой строки в единое целое выполняется функцией «склеивания» строк strcat.
Функция «склеивания» символьных строк strcat()
Функция предназначена для получения результирующей строки из двух исходных строк. Структура функции:
strcat(buf1, buf2)
где strcat – обозначение функции;
buf1 – имя исходной (результирующей) символьной строки;
buf2 – имя добавляемой символьной строки;
() – ограничители аргумента.
Функция располагается в библиотеке string.h.
Правила записи и использования
1. Операнды buf1 и buf2 – символьные строки. Строка buf1 увеличивает свое значение после выполнения функции на величину buf2.
2. Обязательное условие формирования строк buf1 и buf2 – окончание каждой символом «\0».
3. Пробелы, при необходимости, формируются структурой соответствующей строки (включением в нее).
4. Однократное использование функции – чтение строки buf1, добавление к ней строки buf2 и занесение результата в buf1. Поэтому размер buf1 в описателе создается увеличенным (на величину добавляемых компонентов).
5. Многократное использование функции – последовательное добавление второго операнда (buf2) к предварительно полученной строке buf1.
6. Повторное использование функции для создания новой результирующей строки требует предварительной очистки первого аргумента функции. Один из вариантов – присваивание строке buf1 пустой строки: sprintf(buf1,"%s","");
7. Проверка результирующей строки на переполнение не выполняется.
8. Функция используется как операнд арифметического выражения (присваивания) или самостоятельный оператор.
Общий вид фрагмента программы «склеивания» символьных строк str и buf:
#include
char str, buf; /*описатель символьных строк*/
EditStr->
EditBuf->GetText(buf, 10); /*ввод buf из поля EditBuf*/
Описатель типа определяет массивы str и buf как символьные максимальной длины 25 и 10 символов. Пятая и шестая строки предписывает ввод строк str и buf из полей EditStr и EditBuf соответственно. Оператор strcat(str, buf); формирует «склеенную» строку и хранит ее под именем str .
Многократное использование функции позволяет создать результирующую строку с любым количеством компонентов в пределах, предусмотренных размером buf1.
Вариант 1: последовательное соединение нескольких строк
#include
char str, buf1, buf2;/*описатель символьных строк*/
EditStr->GetText(str, 10); /*ввод строки str из поля EditStr*/
EditBuf1->GetText(buf1, 10); /*ввод buf1 из поля EditBuf1*/
EditBuf2->GetText(buf2, 10); /*ввод buf2 из поля EditBuf2*/
strcat(str, buf1); /*формирование результирующей строки str «склеиванием» исходных строк str и buf1*/
strcat(str, buf2); /*формирование результирующей строки str «склеиванием» полученных str и buf2*/
Описатель типа определяет массивы str, buf1 и buf2 как символьные, максимальной длины 25, 10 и 5 символов, соответственно. Пятая, шестая и седьмая строки предписывает ввод str, buf1 и buf2 из полей EditStr, EditBuf1 и EditBuf2 соответственно. Операторы strcat(str, buf1); и strcat(str, buf2); последовательно формируют «склеенную» строку из str, buf1 и buf2. Полученная строка имеет имя str .
Вариант 2: использование функции в теле цикла.
#include
char str = “ ”, buf;/*описание и инициализация
символьных строк*/
for(j = 0 ; j < 5 ; j++) /* заголовок цикла ввода buf и формирования str*/
EditBuf->GetLine(buf, 10, j); /* ввод buf */
strcat(str, buf); /*формирование результирующей строки str «склеиванием» исходных строк str и buf*/
Описатель типа определяет массивы str и buf как символьные максимальной длины 50 и 10 символов соответственно и инициализирует str пустой строкой. Оператор EditBuf->GetLine (buf, 10, j); предписывает ввод buf из j-й строки многострочного поля EditBuf. Оператор strcat(str, buf); формирует в теле цикла, из последовательно вводимых строк buf, «склеенную» строку и хранит ее под именем str .
С учетом планируемого интерфейса выполним программирование задачи.
#include
#include
#include
void TSumprDlgClient::Ok()
// INSERT>> Your code here.
float x[M][N], y[M][N]; /* описатели массивов */
char buf,buf1=" "; /*описание символьного массива*/
ListBoxYi->
ListBoxXi->ClearList(); /*очистка поля вывода*/
EditN->
n = atoi(buf); /* столбцов массива*/
EditM->GetText(buf, 10); /*ввод количества*/
m = atoi(buf); /* строк массива*/
for(i = 0 ; i < m ; i++) /* заголовок внешн. цикла ввода x[i][j] */
for(j = 0 ; j < n ; j++) /* заголовок внутр. цикла ввода x[i][j] */
EditX->GetLine(buf, 30, i*n+j); /* ввод элементов */
x[i][j]=atof(buf); /* массива Х*/
for(i = 0; i < m; i++) /*заголовок внешн. цикла вывода x[i][j]*/
for(j = 0; j < n; j++)/*заголовок внутр. цикла вывода x[i][j]*/
sprintf(buf,"%11.3f",x[i][j]); /* вывод текущих*/
ListBoxXi->AddString(buf1); /*значений xi*/
sprintf(buf1,"%s","");
for(i = 0; i < m; i++)/*заголовок внешн. цикла расчета y[i][j]*/
for(j = 0; j < n; j++) /*заголовок внутр. цикла расчета y[i][j]*/
y[ i ][ j ] = x[ i ][ j ] / 2.;
for(i = 0 ; i < m ; i++)/*заголовок внешн. цикла вывода y[i][j]*/
for(j = 0; j < n; j++)/*заголовок внутр. цикла вывода y[i][j]*/
sprintf(buf,"%11.6f",y[i][j]); /* вывод текущих*/
strcat(buf1, buf); /*склеенных*/
ListBoxYi->AddString(buf1); /*значений yi*/
sprintf(buf1,"%s","");
3 2 – размеры массива;
10. 20. 30. – элементы первой строки;
100. 200. 300. – элементы второй строки.
Под закрывающей скобкой приведены исходные данные для решения задачи.
Результаты решения представлены в приложении 9.2.
Похожая информация.
До сих пор мы работали с простыми типами данных – логический (boolean), целый (integer , word , byte , longint), вещественный (real), символьный (char). Любой алгоритм можно запрограммировать с помощью этих четырех базовых типов. Но для обработки информации о многообразном реальном мире требуются данные, имеющие более сложное строение. Такие сложные конструкции, основанные на простейших скалярных типах, называются структурами. Структура – некоторый составной тип данных, составленный из базовых скалярных. Если структура не изменяет своего строения на протяжении всего выполнения программы, в которой она описана, то такую структуру называют статической.
Массив – однородная совокупность элементов
Самой распространенной структурой, реализованной практически во всех языках программирования, является массив.
Массивы состоят из ограниченного числа компонент, причем все компоненты массива имеют один и тот же тип, называемый базовым. Структура массива всегда однородна. Массив может состоять из элементов типа integer , real или char , либо других однотипных элементов. Из этого, правда, не следует делать вывод, что компоненты массива могут иметь только скалярный тип.
Другая особенность массива состоит в том, что к любой его компоненте можно обращаться произвольным образом. Что это значит? Программа может сразу получить нужный ей элемент по его порядковому номеру (индексу).
Индекс массива
Номер элемента массива называется индексом . Индекс – это значение порядкового типа, определенного, как тип индекса данного массива. Очень часто это целочисленный тип (integer , word или byte), но может быть и логический и символьный.
Описание массива в Паскале. В языке Паскаль тип массива задается с использованием специального слова array (англ. – массив), и его объявление в программе выглядит следующим образом:
Type < имя _ типа >= array [ I ] of T;
где I – тип индекса массива, T – тип его элементов.
Можно описывать сразу переменные типа массив, т.е. в разделе описания переменных:
Var a,b: array [ I ] of T;
Обычно тип индекса характеризуется некоторым диапазоном значений любого порядкового типа: I 1 .. I n . Например, индексы могут изменяться в диапазоне 1..20 или " a ".." n ".
При этом длину массива Паскаля характеризует выражение:
ord (I n)- ord (I 1)+1.
Вот, например, объявление двух типов: vector в виде массива Паскаля из 10 целых чисел и stroka в виде массива из 256 символов:
Type
Vector=array of integer;
Stroka=array of char;
С помощью индекса массива можно обращаться к отдельным элементам любого массива, как к обычной переменной: можно получать значение этого элемента, отдельно присваивать ему значение, использовать его в выражениях.
Опишем переменные типа vector и stroka:
Вычисление индекса массива Паскаля
Индекс массива в Паскале не обязательно задавать в явном виде. В качестве индекса массива можно использовать переменную или выражение, соответствующее индексному типу. Иначе говоря, индексы можно вычислять.
Этот механизм – весьма мощное средство программирования. Но он порождает распространенную ошибку: результат вычислений может оказаться за пределами интервала допустимых значений индекса, то есть будет произведена попытка обратиться к элементу, которого не существует. Эта типичная ошибка называется «выход за пределы массива».
Пример программы с ошибкой массива ПаскаляProgram primer _ error ;
Type
vector=array of word;
var
n: integer;
a: vector;
begin
n:=45;
a:=25;
end .
Хотя данная программа полностью соответствует синтаксису языка, и транслятор «пропустит» ее, на стадии выполнения произойдет ошибка выхода за пределы массива Паскаля. При n =45 выражение n *2=90, компьютер сделает попытку обратиться к элементу массива a , но такого элемента нет, поскольку описан массив размерностью 80.
Будем считать, что хорошая программа должна выдавать предупреждающее сообщение в случае попытки обращения к несуществующим элементам массива. Не лишним будет проверять возможный выход как за правую, так и за левую границы массива, ведь не исключено, что в результате вычисления значения выражения получится число, находящееся левее границы массива Паскаля.
Из всего этого следует сделать вывод: программисту надо быть очень аккуратным при работе с индексами массива.
Основные действия с массивами Паскаля
Как известно, определение типа данных означает ограничение области допустимых значений, внутреннее представление в ЭВМ, а также набор допустимых операций над данными этого типа. Мы определили тип данных как массив Паскаля. Какие же операции определены над этим типом данных? Единственное действие, которое можно выполнять над массивами целиком, причем только при условии, что массивы однотипны, – это присваивание. Если в программе описаны две переменные одного типа, например,
Var
a , b: array of real ;
то можно переменной a присвоить значение переменной b (a:= b). При этом каждому элементу массива a будет присвоено соответствующее значение из массива b . Все остальные действия над массивами Паскаля производятся поэлементно (это важно!) .
Ввод массива Паскаля
Для того чтобы ввести значения элементов массива, необходимо последовательно изменять значение индекса, начиная с первого до последнего, и вводить соответствующий элемент. Для реализации этих действий удобно использовать цикл с заданным числом повторений, т.е. простой арифметический цикл, где параметром цикла будет выступать переменная – индекс массива Паскаля. Значения элементов могут быть введены с клавиатуры или определены с помощью оператора присваивания.
Пример фрагмента программы ввода массива ПаскаляVar
A: array of integer ;
Begin
For i:=1 to 10 do
Readln (a[i]); { ввод i- го элемента производится с клавиатуры }
Рассмотрим теперь случай, когда массив Паскаля заполняется автоматически случайными числами, для этого будем использовать функцию random (N).
Пример фрагмента программы заполнения массива Паскаля случайными числамиVar
I: byte ; {переменная I вводится как индекс массива}
Begin
For i:=1 to 10 do
A [ i ]:= random (10); { i -му элементу массива присваивается «случайное» целое число в диапазоне от 0 до 10}
Вывод массива Паскаля
Вывод массива в Паскале осуществляется также поэлементно, в цикле, где параметром выступает индекс массива, принимая последовательно все значения от первого до последнего.
Пример фрагмента программы вывода массива ПаскаляVar
A: array of integer;
I: byte ; {переменная I вводится как индекс массива}
Begin
For i:=1 to 10 do
Write (a [ i ]," "); {вывод массива осуществляется в строку, после каждого элемента печатается пробел}
Вывод можно осуществить и в столбик с указанием соответствующего индекса. Но в таком случае нужно учитывать, что при большой размерности массива все элементы могут не поместиться на экране и будет происходить скроллинг, т.е. при заполнении всех строк экрана будет печататься очередной элемент, а верхний смещаться за пределы экрана.
Пример программы вывода массива Паскаля в столбикVar
A: array of integer;
I: byte ; {переменная I вводится как индекс массива}
Begin
For i:=1 to 10 do
Writeln ("a[", i,"]=", a[i]); { вывод элементов массива в столбик }
На экране мы увидим, к примеру, следующие значения:
a =2
a =4
a =1 и т.д.
Пример решения задачи с использованием массивов Паскаля
Задача: даны два n -мерных вектора. Найти сумму этих векторов.
Решение задачи:
- Входными данными в этой задаче будут являться два одномерных массива. Размер этих массивов может быть произвольным, но определенным. Т.е. мы можем описать заведомо большой массив, а в программе определить, сколько элементов реально будет использоваться. Элементы этих массивов могут быть целочисленными. Тогда описание будет выглядеть следующим образом:
var a , b: array of integer ;
- Выходными данными будут элементы результирующего массива, назовем его c . Тип результирующего массива также должен быть целочисленным.
- Кроме трех массивов нам потребуется переменная – параметр цикла и индекс массива, назовем ее i , а также переменная n для определения количества элементов в каждом массиве.
Ход решения задачи:
- определим количество элементов (размерность) массивов, введем значение n ;
- введем массив a ;
- введем массив b ;
- в цикле, перебирая значения индекса i от 1 до n , вычислим последовательно значения элементов массива c по формуле:
c [ i ]= a [ i ]+ b [ i ];
- выведем на экран полученный массив.
Текст программы:
Пример программы суммирования векторовProgram summa;
Var
a, b, c: array of integer;
I, n: byte;
Begin
Write ("введите размерность массивов:");
Readln(n);
For i:=1 to n do
Readln (a[i]); { ввод массива a}
For i:=1 to n do
Readln (b[i]); { ввод массива b}
For i:=1 to n do
C[i]:=a[i]+b[i]; { вычисление суммы массивов }
For i:=1 to n do
write (c[i]," "); { вывод массива с }
end.
Массив
| Эту страницу предлагается переименовать в Массив (информатика).
Пояснение причин и обсуждение - на странице Википедия:К переименованию/4 ноября 2012
. Не снимайте пометку о выставлении на переименование до окончания обсуждения. |
Размерность массива - количество индексов, необходимое для однозначного доступа к элементу массива .
Форма или структура массива - количество размерностей и размер (протяжённость) массива для каждой размерности , может быть представлен одномерным массивом .
В ряде языков программирования, например, Лисп , JavaScript , PHP , Ruby применяются также ассоциативные массивы (или хэш-массивы), в которых элементы не обязательно являются однотипными, а доступ к ним не обязательно осуществляется по индексу.
Общее описание
Массив - упорядоченный набор данных, для хранения данных одного типа, идентифицируемых с помощью одного или нескольких индексов . В простейшем случае массив имеет постоянную длину и хранит единицы данных одного и того же типа.
Количество используемых индексов массива может быть различным. Массивы с одним индексом называют одномерными , с двумя - двумерными и т. д. Одномерный массив нестрого соответствует вектору в математике, двумерный - матрице. Чаще всего применяются массивы с одним или двумя индексами, реже - с тремя, ещё большее количество индексов встречается крайне редко.
Пример статического массива на языке Паскаль
{Одномерный массив целых чисел. Нумерация элементов от 1 до 15} a: array [ 1 .. 15 ] of Integer ; {Двумерный массив символов. Нумерация по столбцам по типу Byte (от 0 до 255) по строкам от 1 до 5} multiArray : array [ Byte , 1 .. 5 ] of Char ; {Одномерный массив из строк. Нумерация по типу word (от 0 до 65536)} rangeArray : array [ Word ] of String ;
Пример статического массива на С/С++
Int Array[ 10 ] ; // Одномерный массив целых чисел размера 10 // Нумерация элементов от 0 до 9 double Array[ 12 ] [ 15 ] ; // Двумерный массив вещественных чисел двойной точности // размера 12 на 15. // Нумерация по столбцам от 0 то 11, по строкам от 0 до 14
Поддержка индексных массивов (свой синтаксис объявления, функции для работы с элементами и т. д.) есть в большинстве высокоуровневых языков программирования . Максимально допустимая размерность массива, типы и диапазоны значений индексов, ограничения на типы элементов определяются языком программирования и/или конкретным транслятором.
В языках программирования, допускающих объявления программистом собственных типов , как правило, существует возможность создания типа «массив». В определении такого типа может указываться размер, тип элемента, диапазон значений и типы индексов. В дальнейшем возможно определение переменных созданного типа. Все такие переменные-массивы имеют одну структуру. Некоторые языки поддерживают для переменных-массивов операции присваивания (когда одной операцией всем элементам массива присваиваются значения соответствующих элементов другого массива).
Объявление типа «массив» в языке Паскаль
Type TArrayType = array [ 0 .. 9 ] of Integer ; (* Объявления типа "массив" *) var arr1, arr2, arr3: TArrayType; (* Объявление трёх переменных-массивов одного типа *)
Специфические типы массивов
Динамические массивы
Динамическим называется массив, размер которого может меняться во время исполнения программы. Для изменения размера динамического массива язык программирования , поддерживающий такие массивы, должен предоставлять встроенную функцию или оператор. Динамические массивы дают возможность более гибкой работы с данными, так как позволяют не прогнозировать хранимые объёмы данных, а регулировать размер массива в соответствии с реально необходимыми объёмами. Обычные, не динамические массивы называют ещё статическими .
Пример динамического массива на Delphi
ByteArray : Array of Byte ; // Одномерный массив multiArray : Array of Array of string ; // Многомерный массив
Пример динамического массива на Си
Float * array1; // Одномерный массив int ** array2; // Двумерный массив array1 = (float * ) malloc (10 * sizeof (float ) ) ; // выделение 10 блоков по sizeof(float) байт каждый array2 = (int ** ) malloc (16 * sizeof (int * ) ) ; // выделение 16 блоков по sizeof(int*) байт каждый. Сюда будут записаны указатели на одномерные массивы-строки for (i = 0 ; i < 16 ; i++ ) array2[ i] = (int * ) malloc (8 * sizeof (int ) ) ; // выделение 8 блоков по sizeof(int) байт каждый. Это одномерные массивы - строки матрицы. // Обращение к массиву array1[ i] = 5.0 ; * (array1+ i) = 5.0 ; array2[ i] [ j] = 6 ; // Записи эквивалентны. Первая с использованием индекса, * (* (array2+ i) + j) = 6 ; // вторая с операцией разыменования.
Пример динамического массива на С++
Float * array1; // Одномерный массив int ** array2; // Многомерный массив array1 = new float [ 10 ] ; // выделение 10 блоков размером типа float array2 = new int * [ 16 ] ; // выделение 16 блоков размером типа указателя на int for (int i = 0 ; i < 16 ; i++ ) { array2[ i] = new int [ 8 ] ; }
Гетерогенные массивы
Гетерогенным называется массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным типам данных . Массив, хранящий указатели на значения различных типов, не является гетерогенным, так как собственно хранящиеся в массиве данные относятся к единственному типу - типу «указатель». Гетерогенные массивы удобны как универсальная структура для хранения наборов данных произвольных типов. Отсутствие их поддержки в языке программирования приводит к необходимости реализации более сложных схем хранения данных. С другой стороны, реализация гетерогенности требует усложнения механизма поддержки массивов в трансляторе языка. Гетерогенный массив как встроенный тип данных присутствует в языках PHP и 1С .
Реализация
Одним из способом реализации статических массивов с одним типом элементов является следующий (в Фортране порядок индексов противоположен таковому в Си ):
- Под массив выделяется непрерывный блок памяти объёмом S*m 1 *m 2 *m 3 …m n , где S - размер одного элемента, а m 1 …m n - размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс).
- При обращении к элементу массива A адрес соответствующего элемента вычисляется как B+S*((…(i 1p *m 1 +i 2p)*m 2 +…+i (n-1)p)*m n-1 +i np), где B - база (адрес начала блока памяти массива), i kp - значение k-го индекса, приведённое к целому с нулевым начальным смещением.
Таким образом, адрес элемента с заданным набором индексов вычисляется так, что время доступа ко всем элементам массива одинаково.
Первый элемент массива, в зависимости от языка программирования , может иметь различный индекс. Различают три основных разновидности массивов: с отсчетом от нуля (zero-based), с отсчетом от единицы (one-based) и с отсчетом от специфического значения заданного программистом (n-based). Отсчет индекса элемента массивов с нуля более характерен для низкоуровневых языков программирования , однако этот метод был использован в языках более высокого уровня языком программирования Си.
Более сложные типы массивов - динамические и гетерогенные - реализуются сложнее.
Достоинства
- лёгкость вычисления адреса элемента по его индексу (поскольку элементы массива располагаются один за другим)
- одинаковое время доступа ко всем элементам
- малый размер элементов: они состоят только из информационного поля
Недостатки
- для статического массива - отсутствие динамики, невозможность удаления или добавления элемента без сдвига других
- для динамического и/или гетерогенного массива - более низкое (по сравнению с обычным статическим) быстродействие и дополнительные накладные расходы на поддержку динамических свойств и/или гетерогенности.
- при работе с массивом в стиле C (с указателями) и при отсутствии дополнительных средств контроля - угроза выхода за границы массива и повреждения данных
См. также
Литература
- Вирт Н. Алгоритмы и структуры данных = Algoritms and data structure. - М .: Мир, 1989. - 360 с. - ISBN 5-03-001045-9
- Хювёнен Э., Сеппянен Й. Мир Лиспа. Введение в язык ЛИСП и функциональное программирование. В 2-х т. = Lisp-maailma: Johdatus kieleen ja ohjelmointiin / Пер. с финск. - М .: Мир, 1990. - ISBN 5-03-001935-9
- Магариу Н. А. Язык программирования АПЛ. - М .: «Радио и связь», 1983. - 96 с.
- Бартеньев О. В. Современный Фортран. - 3-е изд., доп. и перераб.. - М .: ДИАЛОГ-МИФИ, 2000. - 449 с.
Примечания
Массив это структура данных, представленная в виде группы ячеек одного типа, объединенных под одним единым именем. Массивы используются для обработки большого количества однотипных данных. Имя массива является , что такое указатели расскажу немного позже. Отдельная ячейка данных массива называется элементом массива. Элементами массива могут быть данные любого типа. Массивы могут иметь как одно, так и более одного измерений. В зависимости от количества измерений массивы делятся на одномерные массивы, двумерные массивы, трёхмерные массивы и так далее до n-мерного массива. Чаще всего в программировании используются одномерные и двумерные массивы, поэтому мы рассмотрим только эти массивы.
Одномерные массивы в С++
Одномерный массив — массив, с одним параметром, характеризующим количество элементов одномерного массива. Фактически одномерный массив — это массив, у которого может быть только одна строка, и n-е количество столбцов. Столбцы в одномерном массиве — это элементы массива. На рисунке 1 показана структура целочисленного одномерного массива a . Размер этого массива — 16 ячеек.
Рисунок 1 — Массивы в С++
Заметьте, что максимальный индекс одномерного массива a равен 15, но размер массива 16 ячеек, потому что нумерация ячеек массива всегда начинается с 0. Индекс ячейки – это целое неотрицательное число, по которому можно обращаться к каждой ячейке массива и выполнять какие-либо действия над ней (ячейкой).
//синтаксис объявления одномерного массива в С++: /*тип данных*/ /*имя одномерного массива*/; //пример объявления одномерного массива, изображенного на рисунке 1: int a;
где, int —целочисленный ;
А — имя одномерного массива;
16 — размер одномерного массива, 16 ячеек.
Всегда сразу после имени массива идут квадратные скобочки, в которых задаётся размер одномерного массива, этим массив и отличается от всех остальных переменных.
//ещё один способ объявления одномерных массивов int mas, a;
Объявлены два одномерных массива mas и а размерами 10 и 16 соответственно. Причём в таком способе объявления все массивы будут иметь одинаковый тип данных, в нашем случае — int .
// массивы могут быть инициализированы при объявлении: int a = { 5, -12, -12, 9, 10, 0, -9, -12, -1, 23, 65, 64, 11, 43, 39, -15 }; // инициализация одномерного массива
Инициализация одномерного массива выполняется в фигурных скобках после знака равно , каждый элемент массива отделяется от предыдущего запятой.
Int a={5,-12,-12,9,10,0,-9,-12,-1,23,65,64,11,43,39,-15}; // инициализации массива без определения его размера.
В данном случае компилятор сам определит размер одномерного массива. Размер массива можно не указывать только при его инициализации, при обычном объявлении массива обязательно нужно указывать размер массива. Разработаем простую программу на обработку одномерного массива.
// array.cpp: определяет точку входа для консольного приложения.
#include "stdafx.h"
#include
// код Code::Blocks
// код Dev-C++
// array.cpp: определяет точку входа для консольного приложения.
#include
В строках 10 — 11 объявлен и проинициализирован целочисленный одномерный массив с именем array1 , размер которого равен 16 ячейкам, то есть такой массив может хранить 16 чисел. Любая обработка массива осуществима только совместно с циклами. Какой цикл выбрать для обработки массива — это вам решать. Но лучше всего для этой задачи подходит . Переменную-счётчик counter будем использовать для обращения к элементам одномерного массива array1 . В условии продолжения цикла for стоит строгий знак неравенства, так как шестнадцатого индекса в одномерном массиве array1 нет. А так как нумерация ячеек начинается с нуля, то элементов в массиве 16. В теле цикла for оператор cout печатает элементы одномерного массива (см. Рисунок 2).
Obrabotka massiva indeks element massiva array1 5 array1 -12 array1 -12 array1 9 array1 10 array1 0 array1 -9 array1 -12 array1 -1 array1 23 array1 65 array1 64 array1 11 array1 43 array1 39 array1 -15 Для продолжения нажмите любую клавишу. . .
Рисунок 2 — Массивы в С++
Разработаем ещё одну программу на обработку одномерного массива в С++. Программа должна последовательно считывать десять введённых чисел с клавиатуры. Все введённые числа просуммировать, результат вывести на экран.
// array_sum.cpp: определяет точку входа для консольного приложения.
#include "stdafx.h"
#include
// код Code::Blocks
// код Dev-C++
// array_sum.cpp: определяет точку входа для консольного приложения.
#include
Перед тем как выполнять обработку массива его необходимо объявить, причём размер одномерного массива равен 10, так как это оговорено условием задачи. В переменной sum будем накапливать сумму элементов одномерного массива. Первый цикл for заполняет объявленный одномерный массив, введёнными с клавиатуры числами, строки 12 — 13 . Переменная счётчик counter используется для последовательного доступа к элементам одномерного массива array1 , начиная с индекса 0 и до 9-го включительно. Второй цикл for выводит на экран элементы массива, строки 15 — 16 . Третий цикл for последовательно считывает элементы одномерного массива и суммирует их, сумма накапливается в переменной sum , строки 17 — 18 . Результат работы программы смотреть на рисунке 3.
Enter elementi massiva: 0 1 2 3 4 5 6 7 8 9 array1 = {0 1 2 3 4 5 6 7 8 9 } sum = 45 Для продолжения нажмите любую клавишу. . .
Рисунок 3 — Массивы в С++
Сначала последовательно были введены все 10 чисел, после чего отобразился одномерный массив, и напечаталась сумма чисел массива.
Двумерные массивы в С++
До этого момента мы рассматривали одномерные массивы, которыми не всегда можно ограничиться. Допустим, необходимо обработать некоторые данные из таблицы. В таблице есть две характеристики: количество строк и количество столбцов. Также и в двумерном массиве, кроме количества элементов массива, есть такие характеристики как, количество строк и количество столбцов двумерного массива. То есть, визуально, двумерный массив — это обычная таблица, со строками и столбцами. Фактически двумерный массив — это одномерный массив одномерных массивов. Структура двумерного массива, с именем a , размером m на n показана ниже (см. Рисунок 4).
Рисунок 4 — Массивы в С++
где, m — количество строк двумерного массива;
n — количество столбцов двумерного массива;
m * n — количество элементов массива.
// синтаксис объявления двумерного массива /*тип данных*/ /*имя массива*/;
В объявлении двумерного массива, также как и в объявлении одномерного массива, первым делом, нужно указать:
- тип данных;
- имя массива.
После чего, в первых квадратных скобочках указывается количество строк двумерного массива, во вторых квадратных скобочках — количество столбцов двумерного массива. Двумерный массив визуально отличается от одномерного второй парой квадратных скобочек. Рассмотрим пример объявления двумерного массива. Допустим нам необходимо объявить двумерный массив, с количеством элементов, равным 15. В таком случае двумерный массив может иметь три строки и пять столбцов или пять строк и три столбца.
// пример объявление двумерного массива: int a;
- a — имя целочисленного массива
- число в первых квадратных скобках указывает количество строк двумерного массива, в данном случае их 5;
- число во вторых квадратных скобках указывает количество столбцов двумерного массива, в данном случае их 3.
// инициализация двумерного массива: int a = { {4, 7, 8}, {9, 66, -1}, {5, -5, 0}, {3, -3, 30}, {1, 1, 1} };
В данном массиве 5 строк, 3 столбца. после знака присвоить ставятся общие фигурные скобочки, внутри которых ставится столько пар фигурных скобочек, сколько должно быть строк в двумерном массиве, причём эти скобочки разделяются запятыми. В каждой паре фигурных скобочек записывать через запятую элементы двумерного массива. Во всех фигурных скобочках количество элементов должно совпадать. Так как в массиве пять строк, то и внутренних пар скобочек тоже пять. Во внутренних скобочках записаны по три элемента, так как количество столбцов — три. Графически наш массив будет выглядеть, как двумерная таблица (см. Рисунок 5).
Рисунок 5 — Массивы в С++
В каждой ячейке двумерного массива a показано значение, в нижнем правом углу показан адрес данной ячейки. Адресом ячейки двумерного массива является имя массива, номер строки и номер столбца.
Разработаем несложную программу, на обработку двумерного массива, которая называется «Лабиринт». Лабиринт должен быть построен на основе двумерного массива. Размер лабиринта выберем на свое усмотрение.
// array2.cpp: определяет точку входа для консольного приложения.
#include "stdafx.h"
#include
// код Code::Blocks
// код Dev-C++
// array2.cpp: определяет точку входа для консольного приложения.
#include
Правильный и ложный пути можно было бы обозначать одной и той же цифрой, например, нулём, но для наглядности правильный путь обозначен цифрой 2. Инициализация массива выполнялась вручную, только для того, что бы упростить программу. Так как в программе выполняется обработка двумерного массива, нужны два цикла, для переключения между элементами двумерного массива. Первый цикл for выполняет переключение между строками двумерного массива. Так как строк в двумерном массиве 33, то и переменная-счетчик i инкрементируется от 0 до 33, строка 46 . Внутри первого цикла стоит цикл for , который переключается между элементами строки двумерного массива. В теле второго цикла for внутри выполняетcя унарная операция преобразования типа данных — static_cast<>() , которая печатает символ , под номером 176. операция преобразования типов данных дублируется для увеличения ширины лабиринта. Результат работы программы (см. Рисунок 6).
Рисунок 6 — Массивы в С++
