Примеры обработки одномерных массивов

Раздел типов

Обработка одномерных массивов

Обработка массивов

Структурированные типы

В программировании используется такое определение массива: совокупность однотипных элементов данных.

Массив – это не простой тип данных, а структурированный, т.е. имеет более чем один компонент. Компоненты массива называют элементами. Все элементы массива имеют общее имя и обращение к конкретному элементу производится с помощью индекса. Важной отличительной чертой массива является однотипность элементов массива. В качестве типа можно использовать любой простой тип или структурированный (т.е. возможна вложенность типов). В Турбо-Паскале количество элементов в массиве фиксировано и определяется во время трансляции. Это является недостатком языка, поскольку не во всех задачах можно заранее определить количество элементов в массиве.

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

<имя массива>: array[<t1>] of <t2>;

Здесь array и of – ключевые слова, пер. с англ. массив, из;

<имя массива> – правильный идентификатор;

<t1> – тип индексов;

<t2> – тип элементов массива.

Для типа индексов обычно используют тип-диапазон, который определяет границы изменения индексов.

Ниже приведены примеры описания одномерных массивов:

var

f:array[1..10] of integer;

mas:array[0..100] of char;

b:array[-5..5] of real;

asd:array[1..20] of byte;

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

Обращение к элементам массива осуществляется по их индексам:

f[1]:=0;

mas[100]:='a';

b[-3]:=1.13;

Как и тип-диапазон, перечисляемый и структурированные типы можно, а иногда просто и необходимо объявлять в разделе описания типов (например, при описании формальных параметров в подпрограммах), который начинается с ключевого слова type:

type

massiv1 = array[1..10] of real;

massiv2 = array[0..50] of char;

var

a:massiv1;

b,c:massiv2;

............

a[3]:=ord(b[i])/10;

............

В разделе описания типов с типом сопоставляется некоторое имя и в дальнейшем вместо явного указания типа можно использовать введенный для данного типа идентификатор. Имя типа обозначается идентификатором, а сам тип описывается согласно определенным для него правилам. Символ "=" является требованием синтаксиса определения типов. Использование раздела типов считается хорошим стилем программирования: улучшается читаемость и структурированность программы.

При обработке массивов возникают такие задачи, как ввод элементов массива, нахождение суммы, произведения, среднего и т.д., поиск некоторого элемента в массиве, сортировка элементов массива, вывод элементов массива.

На рис.14 приведена схема алгоритма формирования элементов массива с помощью датчика случайных чисел, вывод элементов массива на экран, вычисление суммы всех элементов. Программа приведена в примере pr17.

program pr17;

const n1=100; {максимальный размер массива}

type mas = array[1..n1] of integer;

var a:mas;

i, {индекс элемента массива }

n,s:integer;

begin

writeln('Введите число элементов массива:');

read(n);

{ Формирование массива с помощью датчика случайных чисел}

randomize;{Инициализация датчика случайных чисел }

for i:=1 to n do

a[i]:=random(10);

Рис. 14

writeln('Полученный массив');

for i:=1 to n do

write (a[i]:5);

writeln;

s:=0; { Нахождение суммы }

for i:=1 to n do

s:=s+a[i];

writeln('s=',s);

end.

В приведенном примере в качестве исходных данных вводится размер массива. Хотелось бы обратить внимание на использование константы n1. Она сделает программу более универсальной, позволяя работать с целочисленными массивами, размерность которых может изменяться от 1 до 100. Если будет введено число, меньшее 1 и большее 100, то возникнет ошибка. Для формирования массива (да и во всех случаях, когда требуется перебор всех элементов массива) лучше всего подходит оператор цикла со счетчиком. В каждой итерации оператора цикла с датчика получаем псевдослучайное число и присваиваем его очередному элементу массива (индекс является переменной цикла). Результатом работы программы является сформированный массив и сумма элементов этого массива.

Аналогично решается задача нахождения произведения элементов массива, только начальное значение для произведения выбирается равным 1 и знак "+" меняется на знак "*".

На рис.15 приведена графическая схема алгоритма определения максимального элемента массива и суммы положительных элементов, а также замены максимального элемента массива суммой положительных элементов массива. Эта же задача решается в программе pr18.

program pr18;

const n1=100; {максимальный pазмеp массива}

type

mas = array[1..n1] of integer;

var

a:mas;

i, {индекс элемента массива}

n,s,

imax:integer;{индекс максимального элемента}

begin

writeln('Введите число элементов массива:');

read(n);

{Ввод массива}

for i:=1 to n do

begin

Рис. 15

write ('Введите ',i,'-й элемент:');

read(a[i])

end;

s:=0;

imax:=1;{пpедполагаем, что пеpвый

элемент максимальный}

for i:=1 to n do

begin

{если элемент положительный, то

прибавляем его к сумме}

if a[i]>0 then s:=s+a[i];

{если текущий элемент массива больше

максимального, то запоминаем его индекс}

if a[imax]<a[i] then imax:=i;

end;

writeln('максимальный элемент массива =',a[imax]);

a[imax]:=s;{ замена максимального элемента суммой }

writeln('s=',s);

writeln('Обpаботанный массив:');

for i:=1 to n do

writeln (a[i]);

end.

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

В приведенном примере массив вводится с клавиатуры. Для ввода массива используется оператор цикла со счетчиком. За начальное значение для индекса максимального элемента берем 1, т.е. предполагаем, что первый элемент максимальный. Далее в цикле перебираются все элементы массива и сравниваются c нулем для того, чтобы прибавлять или не прибавлять элемент к сумме. В этом же цикле каждый элемент сравнивается с a[imax] для выяснения, не встретился ли элемент, больший прежнего максимального, и если встретился, то запоминается его индекс, чтобы в следующий раз сравнивать текущий элемент с большим из перебранных. В условном операторе if a[i]>a[imax] ветвь else отсутствует; это означает, что в случае невыполнения условия imax остается без изменения, что и обеспечивает наличие в области памяти с идентификатором imax значение индекса максимального из перебранных элементов.

На рис.16 приведена графическая схема алгоритма сортировки элементов одномерного массива "методом пузырька" в порядке неубывания. Суть сортировки этим методом состоит в том, что сравниваются два соседних элемента и, если они расположены в порядке убывания, то меняются местами, и этот факт фиксируется в переменной fl.

После сравнения всех элементов массива принимается решение по состоянию fl об очередном прохождении по массиву. Решение этой задачи реализуется в программе pr20.

program pr20;

const n1=100; {максимальный pазмеp массива}

type

mas = array[1..n1] of real;

var

a:mas;

i, {индекс элемента массива}

n:integer;

fl:boolean;{флаг пеpестановок}

d:real;{дополнительная пеpеменная для пеpестановки

местами двух элементов массива}

begin

writeln('Введите число элементов массива:');

read(n);

{Ввод массива}

for i:=1 to n do

begin

write ('Введите ',i,'-й элемент:');

read(a[i])

end;

writeln('Исходный массив');

for i:=1 to n do

write (a[i]:5);

writeln;

{ Соpтиpовка }

repeat { повторить }

fl:=true;{ флаг поднять}

{ в очередной раз просматриваем элементы массива }

for i:=1 to n-1 do

Рис. 16

if a[i]>a[i+1] then {сравниваем два соседних элемента}

begin{ меняем местами соседние элементы}

d:=a[i];

a[i]:=a[i+1];

a[i+1]:=d;

fl:=false;{если был обмен,то флаг опускаем }

end;

until fl;{если флаг не опускался,то массив отсортирован }

writeln('Обpаботанный массив:');

for i:=1 to n do

write (a[i]:5:2);

writeln;

end.

Основной цикл repeat прекращает выполняться, когда значение логической переменной fl остается равной true после выполнения вложенного цикла for. Это происходит в том случае, если ни одну пару элементов не удается переставить, что указывает на то, что все элементы стоят на своих местах.

Дата добавления: 2014-11-18