Структурированные данные и алгоритмы их обработки

Для повышения производительности и качества работы необхо­димо иметь данные, максимально приближенные к реальным анало­гам. Тип данных, позволяющий хранить вместе под одним именем несколько переменных, называется структурированным. Каждый язык программирования имеет свои структурированные типы. Рас­смотрим структуру, объединяющую элементы одного типа данных – массив.

Массивом называется упорядоченная совокупность однотипных величин, имеющих общее имя, элементы которой адресуются (раз­личаются) порядковыми номерами (индексами). В качестве иллюст­рации можно представить шкаф, содержащий множество пронуме­рованных ящиков (совокупность – «Ящик № 1», «Ящик № 2», «Ящик № 3» и т.д.; «Ящик» – общее имя всех ее элементов). Доступ к со­держимому конкретного ящика (элементу массива) осуществляется после выбора ящика по его номеру (индексу). Элементы массива в памяти компьютера хранятся по соседству, одиночные элементы про­стого типа такого расположения данных в памяти не предполагают. Массивы различаются количеством индексов, определяющих их эле­менты.

Одномерный массив (шкаф ящиков в один ряд) предполагает на­личие у каждого элемента только одного индекса. Примерами одно­мерных массивов служат арифметическая (а_i) и геометрическая (b_i) последовательности, определяющие конечные ряды чисел. Количе­ство элементов массива называют размерностью. При определении одномерного массива его размерность записывается в круглых скоб­ках, рядом с его именем. Например, если сказано: «задан массив А(10)», это означает, что даны элементы: a₁, a₂, ... , а₁₀. Рассмотрим алгоритмы обработки элементов одномерных массивов.

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

Рассмотрим двумерныймассив (шкаф с множеством ящиков, положение которых определяется двумя коорди­натами – по горизонтали и по вертикали). В математике двумерный массив (таблица чисел) называется матрицей. Каждый ее элемент имеет два индекса а_ij, первый индекс i определяет номер строки, в которой на­ходится элемент (координата по горизонтали), а второй, j – номер столбца (координата по вертикали). Двумерный массив характеризу­ется двумя размерностями N и М, определяющими число строк и столбцов соответственно.

Ввод элементов двумерного массива осуществляется построчно, в свою очередь, ввод каждой строки производится поэлементно, тем самым определяется циклическая конструкция, реализующая вложение циклов. Внешний цикл определяет номер вводимой строки (i), внутренний – номер элемента по столбцу (j). На рис. Представлен алгоритм ввода матрицы A(N на М).

Разберем примеры алгоритма на псевдокоде:

Дан массив целых чисел {A_i}, где i=1,2,3,…,M. Пусть M равно 15. Программа вычисляет произведение сумм некоторых элементов этого массива. В программе введены следующие константы: G=1; W=12; T=8; L=15.

ПРОГРАММА 15;
ФУНКЦИЯ SUMMA(I1,I2);
НАЧАТЬ ФУНКЦИЮ
||S:=0;
||НЦ ДЛЯ I:=I1 ДО I2
|S:=S + A[I]
||КЦ;
||SUMMA:=S
КОНЕЦ ФУНКЦИИ;
НАЧАТЬ ПРОГРАММУ
||ПИСАТЬ ('ВВЕДИТЕ ЗНАЧЕНИЯ МАССИВА A:' );
||НЦ ДЛЯ J:=1 ДО M
|ЧИТАТЬ (A[J]);
||КЦ;
||P:=SUMMA (G, W)*SUMMA(T, L);
||ПИСАТЬ ('ПРОИЗВЕДЕНИЕ РАВНО:', P:6)
КОНЕЦ ПРОГРАММЫ.

Для удобства дальнейших пояснений, перепишем псевдокод с номерами строк:

1 ПРОГРАММА 15;
2 ФУНКЦИЯ SUMMA(I1,I2);
3 НАЧАТЬ ФУНКЦИЮ
4 ||S:=0;
5 ||НЦ ДЛЯ I:=I1 ДО I2
6 |S:=S + A[I]
7 ||КЦ;
8 ||SUMMA:=S
9 КОНЕЦ ФУНКЦИИ;
10 НАЧАТЬ ПРОГРАММУ
11 ||ПИСАТЬ ('ВВЕДИТЕ ЗНАЧЕНИЯ МАССИВА A:' );
12 ||НЦ ДЛЯ J:=1 ДО M
13 |ЧИТАТЬ (A[J]);
14 ||КЦ;
15 ||P:=SUMMA (G, W)*SUMMA(T, L);
16 ||ПИСАТЬ ('ПРОИЗВЕДЕНИЕ РАВНО:', P)
17 КОНЕЦ ПРОГРАММЫ.

В строке 1 записано название программы – «Программа 15».

В строке 2 описан заголовок функции Summa. Как видно из заголовка в функцию передается 2 формальных параметра – I1 и I2. Само тело функции записано в строках с 3 по 9. Проанализируем тело функции.

В строке 4 переменной S присваивается начальное значение равное 0.

В строках с 5 по 7 записан цикл. Количество повторений цикла известно – оно равно I2-I1. В теле цикла (строка 6) производится прибавление к прежнему значению переменной S элемента под номером I массива из A.

После цикла, в строке 8 записан результат, который будет выдавать функция (это называется – возвращать результат) – результат равен значению переменной S.

Например, если I1=1, I2=1, A[1]=1, A[2]=2, A[3]=4, то выполнение тела функции будет происходить следующим образом:

Шаг 1: 4 ||S:=0;

Шаг 2: 5 ||НЦ ДЛЯ I:=1 ДО 3

Шаг 3: 6 |S:=0 + A[1]=0+1=1

Шаг 4: увеличение счетчика цикла: I=I+1=1+1=2

Шаг 5: возврат на начало цикла (строка 5)
Шаг 6: 6 |S:=1 + A[2]=1+2=3

Шаг 7: увеличение счетчика цикла: I=I+1=2+1=3

Шаг 8: возврат на начало цикла (строка 5)
Шаг 9: 6 |S:=3 + A[3]=3+3=6

Шаг 10: увеличение счетчика цикла: I=I+1=3+1=4

Шаг 11: возврат на начало цикла (строка 5)

Шаг 12: поскольку значение счетчика цикла больше чем заданный предел (I2=3) то происходит выход из цикла и переход на сроку за циклом

Шаг 13: 8 ||SUMMA:=S=6
Шаг 14: завершение функции

Итак, функция производит суммирование всех элементов массива A, начиная с элемента с номером I1 и заканчивая номером I2. Математически, это записывается:

В строке 10 начинается выполнение программы.

В строке 11 на экран выводится надпись «ВВЕДИТЕ ЗНАЧЕНИЯ МАССИВА A:».

В строках с 12 по 14 записан цикл, в котором последовательно вводятся элементы массива A.

В строке 15 вызывается функция SUMMA с фактическими параметрами G и W и еще раз с фактическими параметрами T и L. Результат перемножается и присваивается переменной P.

В строке 16 на экран выводится надпись «ПРОИЗВЕДЕНИЕ РАВНО» и после нее значение переменной P.

Итак, программа выполняется следующим образом:

Шаг 1: на экран пишется «ВВЕДИТЕ ЗНАЧЕНИЯ МАССИВА A:» (строка 10)

Шаг 2: в цикле вводятся элементы массива A (строки 12-14, количество повторений цикла М-1)

Шаг 3: выполняется вызов функции SUMMA (строка 15)

Шаг 4: выполняется тело функции SUMMA (строки 2-9. При

этом вместо I1 подставляется G, а вместо I2 подставляется W. Результат: )

Шаг 5: выполняется тело функции SUMMA (строки 2-9. При

этом вместо I1 подставляется T, а вместо I2 подставляется L. Результат: )

Шаг 6: переменной P присваивается произведение результатов вызовов функций SUMMA (строка 15. Результат: )

Шаг 7: на экран выводится «ПРОИЗВЕДЕНИЕ РАВНО:» (строка 16)

Шаг 8: на экран выводится значение переменной P (строка 16)

Шаг 9: выполнение программы завершается (строка 17)