Содержание
- 2. СТРУКТУРЫ ДАННЫХ Статические структуры представляют собой структурированное множество базовых структур; они отличаются отсутствием изменчивости. Массивы –
- 3. МАССИВЫ МАССИВ – это структура данных, представляющая собой конечную совокупность элементов одного типа, которая определяется одним
- 4. МАССИВЫ Принципы обработки и типовые алгоритмы Элементы массива располагаются в последовательных ячейках памяти и обозначаются именем
- 5. МАССИВЫ Принципы обработки и типовые алгоритмы Структура данных Массив позволят выполнять операции как со всем массивом
- 6. МАССИВЫ Инициализация элементов массива Прежде чем выполнять какие либо действия с массивом, необходимо занести начальные данные
- 7. МАССИВЫ Инициализация элементов массива Загрузка в массив начальных значений извне Если значения элементов массива в ходе
- 8. МАССИВЫ Алгоритм заполнения массива с клавиатуры: Приращение счётчика итераций цикла – индекса массива (на 1) И+ПРГ
- 9. МАССИВЫ Инициализация элементов массива Загрузка начальных значений в массив непостоянного размера Если требуется массив непостоянного размера
- 10. МАССИВЫ Алгоритм заполнения массива непостоянного размера: И+ПРГ
- 11. Элементы ЯПВУ C Массивы (определяемый программистом составной тип данных) Pascal МАССИВ – это структура данных, представляющая
- 12. Примеры int d[3] = {3,5}; // d[0]=3, d[1]=5, d[2]=0 float mask[12][5]; int mass[3][2]={{1,1},{0,2},{1,0}}; или int mass[3][2]={1,1,0,2,1,0};
- 13. ЗАДАНИЕ. Нарисовать блок-схему алгоритма: ввести с клавиатуры одномерный массив из 5 элементов и вывести количество ненулевых
- 14. ЗАДАНИЕ: ввести с клавиатуры одномерный массив из 5 элементов и вывести количество ненулевых элементов в этом
- 15. МАССИВЫ Двумерные массивы Когда для решения задач не хватает вектора – одномерного массива, тогда возникает необходимость
- 16. МАССИВЫ Алгоритм заполнения двумерного массива с клавиатуры: Загрузка начальных значений в массив с клавиатуры реализуется обычно
- 17. Двумерные массивы. Загрузка содержимого массива с клавиатуры // Заполнение двумерного массива #include // Количество строк матрицы
- 18. Двумерные массивы. Загрузка содержимого массива с клавиатуры И+ПРГ Program Matrica; Const N=2; (*Количество строк матрицы *)
- 20. Скачать презентацию
СТРУКТУРЫ ДАННЫХ
Статические структуры представляют собой структурированное множество базовых структур; они отличаются
СТРУКТУРЫ ДАННЫХ
Статические структуры представляют собой структурированное множество базовых структур; они отличаются
Массивы – структура данных, которая характеризуется:
фиксированным набором элементов одного и того же типа;
каждый элемент имеет уникальный набор значений индексов;
количество индексов определяют мерность массива, например, три индекса - трехмерный массив, один индекс - одномерный массив или вектор;
обращение к элементу массива выполняется по имени массива и значениям индексов для данного элемента.
Иначе: массив – это вектор, каждый элемент которого скаляр или вектор.
Записи – конечное упорядоченное множество полей, характеризующихся различным типом данных (базовыми, статическими и др.).
Полустатические структуры данных характеризуются следующими признаками: (1) они имеют переменную длину и простые процедуры ее изменения; (2) изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения. Доступ к элементу может осуществляться по его порядковому номеру, но с некоторыми ограничениями.
Строки – это линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемому алфавитом. Их важные свойства:
длина, как правило, переменна, хотя алфавит фиксирован;
обычно обращение к символам строки идет с какого-нибудь одного конца последовательности, т.е. важна упорядоченность этой последовательности, а не ее индексация; в связи с этим свойством строки часто называют также цепочками;
чаще всего целью доступа к строке является не отдельный ее элемент (хотя это тоже не исключается), а некоторая цепочка символов в строке.
Основные понятия
И+ПРГ
МАССИВЫ
МАССИВ – это структура данных, представляющая собой конечную совокупность элементов одного
МАССИВЫ
МАССИВ – это структура данных, представляющая собой конечную совокупность элементов одного
Массив – это внутренняя структура данных алгоритма, т.е. массивы используются только во время выполнения алгоритма, в котором они определены. Во внешнем представлении задачи массивы могут быть (см. рисунки):
- Линейной последовательностью значений однотипных элементов -- вектором или одномерной матрицей,
- Совокупностью двух векторов – таблицей или двумерной матрицей,
- Совокупностью трёх векторов – трёхмерной матрицей,
и т.д.
Принципы обработки и типовые алгоритмы
Количество векторов в массиве называется измерением массива, количество элементов в измерении называется размерностью данного измерения. Измерение и размерность массива данных фиксируется при создании массива и остаются неизменными при выполнении различных операций над массивами данных.
Размерность массива определяет количество элементов массива и вычисляется как произведение размерностей всех измерений массива.
Размерность измерения массива задаётся или через именованную константу, или напрямую – числом.
И+ПРГ
МАССИВЫ
Принципы обработки и типовые алгоритмы
Элементы массива располагаются в последовательных ячейках памяти
МАССИВЫ
Принципы обработки и типовые алгоритмы
Элементы массива располагаются в последовательных ячейках памяти
Элементы массива нумеруются от 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 – размерность массива.
И+ПРГ
МАССИВЫ
Алгоритм заполнения массива с клавиатуры:
Приращение счётчика итераций цикла – индекса
МАССИВЫ
Алгоритм заполнения массива с клавиатуры:
Приращение счётчика итераций цикла – индекса
И+ПРГ
МАССИВЫ
Инициализация элементов массива
Загрузка начальных значений в массив непостоянного размера
Если требуется массив
МАССИВЫ
Инициализация элементов массива
Загрузка начальных значений в массив непостоянного размера
Если требуется массив
Во время начального ввода элементов массива сигнальная метка укажет конец входных записей (завершение ввода), а во время последующей обработки массива будет указывать последний элемент массива. Если массив содержит символьные элементы, то и сигнальная метка должна быть символьная (например, точка).
Если сигнальную метку записывать в последний элемент массива, то по ней можно определять завершение содержательной части массива.
Если надо записать в массив заранее известное количество элементов (и оно меньше размера массива), то рационально использовать цикл с параметром ДЛЯ.
При заполнении элементов массива данными из файла не требуется использовать сигнальную метку – специальное значение, обозначающее окончание вводимых данных (в приведенном алгоритме – это 9999). Работая с файлом, можно проверять специальный символ окончания файла – eof (end of file).
И+ПРГ
МАССИВЫ
Алгоритм заполнения массива непостоянного размера:
И+ПРГ
МАССИВЫ
Алгоритм заполнения массива непостоянного размера:
И+ПРГ
Элементы ЯПВУ
C
Массивы
(определяемый программистом составной тип данных)
Pascal
МАССИВ – это структура данных, представляющая
Элементы ЯПВУ
C
Массивы
(определяемый программистом составной тип данных)
Pascal
МАССИВ – это структура данных, представляющая
Объявление массива
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 d[3] = {3,5}; // d[0]=3, d[1]=5, d[2]=0
float mask[12][5];
int mass[3][2]={{1,1},{0,2},{1,0}};
или
Примеры
int d[3] = {3,5}; // d[0]=3, d[1]=5, d[2]=0
float mask[12][5];
int mass[3][2]={{1,1},{0,2},{1,0}};
или
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
ЗАДАНИЕ. Нарисовать блок-схему алгоритма:
ввести с клавиатуры одномерный массив из 5
МАССИВЫ
И+ПРГ
ЗАДАНИЕ: ввести с клавиатуры одномерный массив из 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) смещается по столбцам – выбира-ет в текущей строке ячейку, соответствующую столбцу массива (таблицы).
Затем управление возвращается внешнему циклу, происходит переход к следующей строке массива. И так пока не заполниться весь массив.
И+ПРГ
Двумерные массивы. Загрузка содержимого массива с клавиатуры
// Заполнение двумерного массива
#include
// Количество
Двумерные массивы. Загрузка содержимого массива с клавиатуры
// Заполнение двумерного массива
#include
// Количество
#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
printf ("a[%i][%i] = ",i,j);
scanf ("%i",&a[i][j]);
}
}
}
Двумерные массивы. Загрузка содержимого массива с клавиатуры
И+ПРГ
Program Matrica;
Const
N=2;
Двумерные массивы. Загрузка содержимого массива с клавиатуры
И+ПРГ
Program Matrica;
Const
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.