Структуры данных - Массивы

образом организованная совокупность данных, состоящая из данных простых типов или

других структур данных.
Напомним, что данные – это информационные объекты, над которыми выполняются действия (операции) алгоритмов для получения требующего результата. Тип данных определяет объём памяти для хранения данных, диапазон значений данных и допустимые операции (действия) над данными.
Структуры данных – это сложные (составные) типы данных.

К сложным структурам данных относят статические, полустатические, динамические и файловые структуры данных.
Основой для построения Сложных структур данных служат Базовые структуры данных (примитивные, простые структуры). В языках программирования простые структуры описываются простыми (базовыми) типами. К основным базовым типам данных относятся: числовые, логические, символьные.
Числовые данные – с помощью целых чисел может быть представлено количество объектов, являющихся дискретными по своей природе (т.е. счетное число объектов); значение вещественных чисел определяется лишь с некоторой конечной точностью, зависящей от внутримашинного формата вещественного числа и от разрядности процессора ЭВМ.
Логические – данные в виде одной из констант false (ложь) или true (истина).
Символьные – символы из некоторого предопределенного множества. В большинстве современных ПЭВМ этим множеством является ASCII (American Standard Code for Information Interchange – американский стандартный код для обмена информацией).

Основные понятия

И+ПРГ

отличаются отсутствием изменчивости.
Массивы – структура данных, которая характеризуется:

фиксированным набором элементов одного и того же типа;
каждый элемент имеет уникальный набор значений индексов;
количество индексов определяют мерность массива, например, три индекса - трехмерный массив, один индекс - одномерный массив или вектор;
обращение к элементу массива выполняется по имени массива и значениям индексов для данного элемента.
Иначе: массив – это вектор, каждый элемент которого скаляр или вектор.
Записи – конечное упорядоченное множество полей, характеризующихся различным типом данных (базовыми, статическими и др.).
Полустатические структуры данных характеризуются следующими признаками: (1) они имеют переменную длину и простые процедуры ее изменения; (2) изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения. Доступ к элементу может осуществляться по его порядковому номеру, но с некоторыми ограничениями.
Строки – это линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемому алфавитом. Их важные свойства:
длина, как правило, переменна, хотя алфавит фиксирован;
обычно обращение к символам строки идет с какого-нибудь одного конца последовательности, т.е. важна упорядоченность этой последовательности, а не ее индексация; в связи с этим свойством строки часто называют также цепочками;
чаще всего целью доступа к строке является не отдельный ее элемент (хотя это тоже не исключается), а некоторая цепочка символов в строке.

Основные понятия

И+ПРГ

одного типа, которая определяется одним именем, например Mas.
Массив – это

внутренняя структура данных алгоритма, т.е. массивы используются только во время выполнения алгоритма, в котором они определены. Во внешнем представлении задачи массивы могут быть (см. рисунки):
- Линейной последовательностью значений однотипных элементов -- вектором или одномерной матрицей,
- Совокупностью двух векторов – таблицей или двумерной матрицей,
- Совокупностью трёх векторов – трёхмерной матрицей,
и т.д.

Принципы обработки и типовые алгоритмы

Количество векторов в массиве называется измерением массива, количество элементов в измерении называется размерностью данного измерения. Измерение и размерность массива данных фиксируется при создании массива и остаются неизменными при выполнении различных операций над массивами данных.
Размерность массива определяет количество элементов массива и вычисляется как произведение размерностей всех измерений массива.
Размерность измерения массива задаётся или через именованную константу, или напрямую – числом.

И+ПРГ

памяти и обозначаются именем массива и индексом.
Элементы массива нумеруются

от 1 до N (например, в Pascal) или от 0 до N-1 (в С/С++), номер элемента массива называется индексом.
Для обозначения отдельных элементов массива используются переменные представленные именем массива с индексом(-ами):
М[3], FR[3,6], S[K+1].

Пример: одномерный массив M из пяти элементов, содержащий пять нечётных чисел (ряд арифметической прогрессии с шагом 2):

При обращении к элементам массива необходимо контролировать выход индекса элемента за объявленные границы (размерность) массива и избегать такой ситуации, так это обычно приводит к ошибкам при выполнении алгоритма.

И+ПРГ

как со всем массивом в целом, так и с отдельным

элементом массива.
С отдельными элементами массива можно работать как в режиме последовательного доступа, переходя от элемента с индексом i к элементу с индексом i+1 (или i-1), так и в режиме прямого доступа, обращаясь прямо к элементу с нужным индексом.
Последовательная обработка массивов реализуется в цикле (ДЛЯ, ПОКА, ПОВТОРЯТЬ-ПОКА).
Элементам массива присваиваются некоторые значения, при этом в общем случае количество элементов массива, которым заданы какие-либо значения, может быть меньше размерности массива.

И+ПРГ

необходимо занести начальные данные в элементы массива – такая операция

называется инициализацией элементов массива.
Начальные значения элементов могут быть заданы как константы или считаны извне (с клавиатуры и из файла).

Инициализация массива константами

Такая инициализация обычно выполняется в том случае, когда данные массива не планируется изменять.
Пример: Массив, хранящий названия месяцев
Это двумерный массив символьных элементов – month-mas, его размерностью 12х8, 12 – количество месяцев, 8 – максимальное количество символов в названии месяца (сентябрь).

И+ПРГ

массива в ходе выполнения алгоритма изменяются, то инициализировать их константами

нельзя.
Начальные значения элементов массива необходимо получить извне – ввести с клавиатуры или прочитать из файла.
Стандартный способ ввода начальных значений элементов массива – организовать цикл ПОКА (ПОВТОРЯТЬ-ПОКА) или ДЛЯ, в каждой итерации цикла получить очередное значение и записать его в очередной элемент массива.

Инициализируем одномерный массив.
Используем переменные:
- M – имя массива,
- i – индекс массива,
- Max – размерность массива.

И+ПРГ

индекса массива (на 1)
И+ПРГ

массив непостоянного размера (динамический), в котором количество элементов меняется в

ходе выполнения алгоритма, то задаётся массив заведомо большего размера, а для маркировки последнего элемента массива используется сигнальная метка (например, 9999).
Во время начального ввода элементов массива сигнальная метка укажет конец входных записей (завершение ввода), а во время последующей обработки массива будет указывать последний элемент массива. Если массив содержит символьные элементы, то и сигнальная метка должна быть символьная (например, точка).
Если сигнальную метку записывать в последний элемент массива, то по ней можно определять завершение содержательной части массива.
Если надо записать в массив заранее известное количество элементов (и оно меньше размера массива), то рационально использовать цикл с параметром ДЛЯ.

При заполнении элементов массива данными из файла не требуется использовать сигнальную метку – специальное значение, обозначающее окончание вводимых данных (в приведенном алгоритме – это 9999). Работая с файлом, можно проверять специальный символ окончания файла – eof (end of file).

И+ПРГ

представляющая собой совокупность элементов одного типа, которая определяется одним именем,

например M. Для обозначения отдельных элементов массива используются пременные с индексом(-ами) типа М[3], FR[3,6] – в Pascal и FR[3][6] – в С, S[K+1].
Объявление массива

Type
NameM = array [F1_Ind..L1_Ind [,…Fn_Ind..Ln_Ind]] of TypeM;
где - NameM – имя типа массива, -TypeM – тип элементов массива,
Fx_Ind..Lx_Ind – начальный и конечный индексы массива (интервальный тип данных).
Var ID1, ID2 : NameM; где – ID1 и ID2 – идентификаторы объявляемых массивов.

TypeM NameM [E1] [[E2]…] = [{]{Init_11,Init_12,...}[,Init_21,Init_22,…},…][}];
где - TypeM – тип элементов массива, - NameM – имя массива,
En – к-во элементов по измерению массива – размерность массива,
Init_n – инициализаторы (нач.значен.) каждого элемента массива. Если инициализаторов меньше, чем элементов, то начальное значение остальных элементов равно 0.

Элементы массива нумеруются от 1 до N в Pascal и от 0 до N-1 в С; номер элемента массива называется индексом.

И+ПРГ

или
int mass[3][2]={1,1,0,2,1,0};
Type
MS = array[1..100] of Real;
Var
t1, Z,

De : MS;
Можно описывать массивы прямо в разделе Var:
Var
t1, Z, De : array[1..100] of Real;
Описание двумерного массива:
n: array [1..12, 1..14] of Integer;
или
Type
а = array [1..6] of integer;
b = array [1..12] of a;
Var
m : b;

Размерность массива разумно задавать в виде именованных констант:
const int n = 12;
int mark[n] = {3,3,4,5,4,4};
Или через директиву препроцессора define:
#define SIZE 5 // размерность массива

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

И+ПРГ

массив из 5 элементов и вывести количество ненулевых элементов в

этом массиве.

МАССИВЫ

И+ПРГ

вывести количество ненулевых элементов в этом массиве.

Program MASSIV;
Const SIZE

= 5; (* Размер массива*)
Var a:arry[1..Size] of integer;
n: integer; i: integer;
Begin
WriteLn('Введите 5 элементов массива');
Write('После ввода числа');
WriteLn('нажимайте Enter');
n:=0;
For i:=1 To SIZE do
Begin
Write('a[',i,'] -> ');
ReadLn(a[i]);
If a[i] <> 0 Then n:=n+1;
End;
WriteLn('В массиве',n,' ненулевых элементов.');
ReadLn;
End.

#include
#define SIZE 5 // размер массива
void main ()
{
int a[SIZE]; // массив
int n = 0, i; //ненулевые элементы, индекс
printf("\nВведите элементы массива\n");
Printf ("После ввода числа – Enter\n");
for (i=0; i {
printf("a[%i] ->", i);
scanf("%i",&a[i]);
if (a[i] != 0) n++;
}
printf("В массиве %i ненулевых элемента \n", n);
}

И+ПРГ

массива, тогда возникает необходимость увеличить количество измерений массива.
Рассмотрим некоторые особенности

работы с двумерными массивами.
Двухмерный массив – это фактически массив одномерных массивов.
Объявление двухмерного массива d, состоящего из 10 строк и 20 столбцов:
int d[10][20]; – в ЯП С/С++ и d: array [1..10, 1..20] of Integer; – в ЯП Pascal .
Осторожно! В Pascal размерности векторов массива отделяются запятыми, в C/C++ размерность каждого вектора массива заключена в квадратные скобки.
Двумерный массив хранится в виде матрицы, в которой первый индекс задает номер строки, а второй – номер столбца. Принято, что при обходе элементов в порядке их размещения в памяти правый (второй) индекс изменяется быстрее, чем левый.

Графическая схема размещения двухмерного массива int Mas[4][3] в памяти:

И+ПРГ

массив с клавиатуры
реализуется обычно с использованием циклов (ДЛЯ, ПОКА, ПОВТОРЯТЬ-ПОКА)

начиная с первого элемента до конца массива. Первый индекс (i) определяет номер строки, второй индекс (j) – номер столбца. Max_i – количество строк массива, Max_j – количество столбцов.
Для смещения по каждому индексу массива выделяется отдельный цикл. Циклы вложены один в другой.
Внешний цикл (по индексу - i) смещается по строкам (выбирает строку) и передает управление внутреннему циклу.
Внутренний цикл (по индексу - j) смещается по столбцам – выбира-ет в текущей строке ячейку, соответствующую столбцу массива (таблицы).
Затем управление возвращается внешнему циклу, происходит переход к следующей строке массива. И так пока не заполниться весь массив.

И+ПРГ

Количество строк матрицы
#define SIZE_i 5
// Количество столбцов матрицы
#define

SIZE_j 5

void main ()
{
int a[SIZE_i][SIZE_j]; // Двумерный массив
int i, j; // индексы массива
printf("\nВведите элементы массива\n");


см. продолжение

Продолжение
// Ввод элементов массива с клавиатуры

printf("После ввода числа - Enter\n");
for (i=0; i for (j=0; j {
printf ("a[%i][%i] = ",i,j);
scanf ("%i",&a[i][j]);
}

}
}

И+ПРГ

N=2; (*Количество строк матрицы *)
M=2; (*Количество столбцов матрицы*)
K=2;

(* Размерность массива *)
Type
(* Тип данных – двумерный массив *)
Matr=array [1..N,1..M] of integer;
Var
(* массив двумерных матриц*)
x : array [1..K]of Matr;
i,j,p : integer; (* индексы массивов *)
см. продолжение

продолжение
Begin
(* Загрузка данных *)
writeln ( 'Ввод данных в
массив двумерных матриц ');
for i:=1 to K do
for j:=1 to N do
for p:=1 to M do
write ('X[', i,',', j,',‘,p'] = ');
readln (x[i,j,p]);

readln;
end.

С.
Задание на дом:

решить задачи обработки массивов данных:
2-а

индивидуальные задания.

И+ПРГ