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

Массивы являются структурированным типом. Структурированные типы данных отличаются от обычных типов тем, что переменные таких типов, имеют более одного значения, т.е. состоят из нескольких компонентов. Структурированные типы характеризуются методом структурирования и типами своих компонентов. Если тип компонента является структурированным, то получаемый в результате структурированный тип имеет более одного уровня структурирования.

Одномерные массивы

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

 

var

<имя переменной>:array[<тип индекса>] of <тип элемента>;

 

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

Приведем пример переменной типа массив:

 

var

A: array[1..100] of Real

 

Если тип элемента в типе массив также является массивом, то результат можно рассматривать как массив массивов или как один многомерный массив. Например,

 

array[boolean] of array[1..100] of Real

 

интерпретируется компилятором точно так же, как массив:

 

array[boolean,1..10] of Real

 

Конкретный элемент массива обозначается с помощью ссылки на переменную массива, за которой указывается индекс, определяющий данный элемент.

 

A[5]:=3.4;

For i:=1 to 100 do

Begin

writeln(‘Введите элемент A[‘,I,’]:’);

Readln(A[i]);

End;

 

При объявлении массивов удобно пользоваться константами, задающими количество элементов в массиве. Объявление констант:

 

Const

<имя конст.>=<значение>;

 

Примеры

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

Сумма элементов массива

 

Const N=10;

Var a:array[1..N] of real;

i:word;

sum:real;

Begin

sum:=0;

for i:=1 to N do

sum:=sum+a[i];

writeln(‘Сумма=‘,sum:10:5);

end.

 

Произведение элементов массива

 

Const N=10;

Var a:array[1..N] of real;

i:word;

p:real;

Begin

p:=1;

for i:=1 to N do

p:=p*a[i];

writeln(‘Произведение=‘,p:10:5);

end.

 

Заполнение массива псевдослучайными числами:

 

randomize;

for i:=1 to N do

a[i]:=x1+random*(x2-x1);

 

Заполнение массива числами Фибоначчи:

 

b[1]:=1;

b[2]:=1;

for i:=3 to N do

b[i]:=b[i-1]+b[i-2];

 

Возведение в квадрат четных элементов массива (элементов с четными значениями):

 

for i:=1 to N do

if b[i] mod 2=0 then

b[i]:=sqr(b[i]);

 

Возведение в квадрат элементов массива с четным индексом:

 

i:=2;

while i<=N do

begin

a[i]:=sqr(a[i]);

Inc(I,2);

End;

 

 

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

program rand1;

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);

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 и знак "+" меняется на знак "*".

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

program sum;

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

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 значение индекса максимального из перебранных элементов.

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

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

program sort1;

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

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. Это происходит в том случае, если ни одну пару элементов не удается переставить, что указывает на то, что все элементы стоят на своих местах.

Многомерные массивы

Если тип элемента в типе массив также является массивом, то результат можно рассматривать как массив массивов или как один многомерный массив. Например,

array[boolean] of array[1..10] of Real;

интерпретируется компилятором точно так же, как массив:

array[boolean,1..10] of Real;

В случае многомерного массива можно использовать несколько индексов или несколько выражений в индексе. Например:

 

Matrix[I][J]

 

что тождественно записи:

 

Matrix[I,J]

 

Примеры

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

Ввод элементов двумерного массива

For i:=1 to N do

for j:=1 to M do

begin

writeln(‘Введите элемент a2[‘,I,’,’,j,’]: ‘);

readln(a2[I,j]);

end;

 

Вывод на экран:

For i:=1 to N do

begin

for j:=1 to M do

write(a2[I,j]:8);

writeln;

end;

 

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

program rand2;

const n1=10; {максимальнoе количество стpок массива}

m1=10; { максимальное количество столбцов массива}

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

var a: mas;

i, { текущий номеp строки }

j, { текущий номеp столбца }

n,s,m: integer;

begin

writeln('Введите число стpок и столбцов массива:');

read(n,m);

randomize;

for i:=1 to n do

for j:=1 to m do

a[i,j]:=random(10);

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

for i:=1 to n do

begin

for j:=1 to m do

write (a[i,j]:5);

writeln;

end;

s:=0;

for i:=1 to n do

for j:=1 to m do

s:=s+a[i,j];

writeln('s=',s);

end.

Анализируя предложенную программу, можно заметить, что для ввода, вывода и нахождения суммы элементов массива используются три раза вложенные циклы. Так как массив располагается в непрерывной области памяти построчно, более рационально будет и обрабатывать элементы построчно. В программе во вложенных циклах для каждого значения индекса i индекс j изменяется от 1 до m, т.е. индекс j изменяется чаще. Таким образом, обрабатываются элементы массива построчно. Хотелось бы обратить внимание на вывод элементов массива на экран. Здесь для каждого значения i в теле цикла выполняются два оператора: первый оператор цикла выводит на экран в строчку элементы одной строки, а второй оператор вывода переводит курсор на новую строку, что как раз и обеспечивает вывод матрицы в виде прямоугольника.

Следующий пример иллюстрирует работу с диагоналями матрицы. Дана квадратная матрица. Заменить отрицательные элементы побочной диагонали на сумму элементов главной диагонали матрицы. При изучении поставленной задачи следует напомнить, что главная диагональ проходит из правого верхнего в левый нижний угол. Так как мы работаем с квадратной матрицей, то только на главной диагонали будут лежать элементы, индексы строк и столбцов которых одинаковы. Именно этот факт и используется при решении задачи. Мы не будем перебирать все элементы массива и смотреть, совпали ли индексы, а сразу задаем оба индекса с помощью одного идентификатора i. Побочная диагональ проходит из правого верхнего в левый нижний угол матрицы. Нетрудно заметить, что при движении по побочной диагонали номер строки возрастает от 1 до n, номер столбца убывает от n до 1. Таким образом, только на побочной диагонали лежат элементы, у которых номер столбца определяется по формуле j=n-i+1.

program diag;

const n1=10; {максимальнoе количество стpок массива}

type

mas = array[1..n1,1..n1] of integer;{квадpатная матpица}

var a:mas;

i, { текущий номеp стpоки }

j, { текущий номеp столбца }

n,s:integer;

begin

writeln('Введите число стpок и столбцов массива:');

read(n);

for i:=1 to n do

for j:=1 to n do

begin

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

read(a[i,j]);

end;

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

for i:=1 to n do

begin

for j:=1 to n do

write (a[i,j]:5);

writeln;

end;

s:=0;

for i:=1 to n do {Сумма элементов главной диагонали }

s:=s+a[i,i];

writeln('s=',s);

for i:=1 to n do{Замена элементов побочной диагонали}

begin

j:=n-i+1;

if a[i,j]<0 then a[i,j]:=s;

end;

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

for i:=1 to n do

begin

for j:=1 to n do

write (a[i,j]:5);

writeln;

end;

end.

Фрагмент программы для транспонирования матрицы относительно побочной диагонали:

 

For i:=1 to N-1 do

for j:=1 to N-i do

begin

tmp:=c2[I,j];

c2[I,j]:=c2[N-j+1,N-i+1];

c2[N-j+1,N-i+1]:=tmp;

end;

 

И последний пример на обработку двумерных массивов. Дана прямоугольная матрица. Отсортировать столбцы матрицы в порядке неубывания максимальных элементов столбцов.

Решение задачи сводится к формированию одномерного массива из максимальных элементов столбцов, а уж затем сортируется этот одномерный массив и параллельно – столбцы матрицы. Чтобы не запутать читателя, в этой задаче используем знакомый метод сортировки "пузырьком". Исходный массив имеет идентификатор a, а промежуточный одномерный массив – b.

program sort2;

const n1=10; {максимальнoе количество стpок массива}

m1=10; {максимальнoе количество столбцов массива}

type

mas = array[1..n1,1..m1] of integer;{квадpатная матpица}

var

a:mas;

b:array[1..m1] of integer;

{массив из максимальных элементов столбцов}

i, { текущий номеp стpоки }

j, { текущий номеp столбца }

n,m,d:integer;

fl:boolean;

begin

writeln('Введите число стpок и столбцов массива:');

read(n,m);

for i:=1 to n do

for j:=1 to m do

begin

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

read(a[i,j]);

end;

 

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

for i:=1 to n do

begin

for j:=1 to m do

write (a[i,j]:5);

writeln;

end;

{Фоpмиpование одномеpного массива из максимальных

элементов столбцов}

for j:=1 to m do {Пеpебиpаем все столбцы}

begin

b[j]:=a[1,j];{Пpинимаем пеpвый элемент в столбце за максимальный }

for i:=2 to n do{Пеpебиpаем все элементы в столбце}

if a[i,j]>b[j] then b[j]:=a[i,j];

end;

end;

{Сортировка одномерного и двумерного массива}

repeat

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

for j:=1 to m-1 do {Перебрать элементы одномерного

массива}

if b[j]>b[j+1] then { Проверить нужна ли перестановка }

begin

fl:=false;{опустить флаг}

{Переставить элементы одномерного массива и}

d:=b[j];

b[j]:=b[j+1];

b[j+1]:=d;

{столбцы двумерного массива}

for i:=1 to n do

begin

d:=a[i,j];

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

a[i,j+1]:=d;

end;

end;

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

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

for i:=1 to n do

begin

for j:=1 to m do

write (a[i,j]:5);

writeln;

end;

end.

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

Тип данных String

Тип STRING (строка) в Турбо Паскале широко используется для обработки текстов. Он во многом похож на одномерный массив символов ARRAY [O..N] OF CHAR, однако, в отличие от последнего, количество символов в строке-переменной может меняться от 0 до N, где N - макси­мальное количество символов в строке. Значение N определяется объяв­лением типа STRING[N] и может быть любой константой порядкового типа, но не больше 255. Турбо Паскаль разрешает не указывать N, в этом случае длина строки принимается максимально возможной, а именно N-255.

Строка в Турбо Паскале трактуется как цепочка символов. К любому символу в строке можно обратиться точно так же, как к элементу одномер­ного массива ARRAY [O..N] OF CHAR, например:

 

var

st: string;

if st[5] - 'A' then...

 

Самый первый байт в строке имеет индекс 0 и содержит текущую длину строки. Первый значащий символ строки занимает второй байт и имеет индекс 1. Над длиной строки можно осуществлять необходимые действия и таким способом изменять длину. Например, удалить из строки все ведомые пробелы можно следующим образом:

 

var

st: strlng[10];

i: word;

i:= 10;

while (st[l]=' ') and (i<>0) do begin dec(i):

st[0]:= chr(i) end;

 

Значение ORD(st[0]), т.е. текущую длину строки, можно получить и с помощью функции LENGTH(st), например:

 

while (Iength(st)<>0) and (st[ length(st)]-' ') do

s[0]:= chr(length(st)-1)

 

К строкам можно применять операцию «+» - сцепление, например:

 

st:= 'а' + 'b':

st:= st + 'с'; {st содержит 'abc'}

 

Если длина сцепленной строки превысит максимально допустимую длину N, то «лишние» символы отбрасываются. Следующая программа,

например, напечатает символ 1:

var

st:string[1];

begin

st:='123';

writeln(st)

end.

 

Все остальные действия над строками и символами реализуются с помощью встроенных процедур и функций.

CONCAT(S1 [,S2,...,SN]) - функция типа STRING; возвращает строку, представляющую собой сцепление строк-параметров SI, S2,...,SN.

COPY(ST, INDEX, COUNT) - функция типа STRING; копирует из строки ST COUNT символов, начиная с символа с номером INDEX.

DELETE(ST, INDEX, COUNT) - процедура; удаляет COUNT сим­волов из строки ST, начиная с символа с номером INDEX.

INSERT(SUBST, ST, INDEX) - процедура; вставляет подстроку SUBST в строку ST, начиная с символа с номером INDEX.

LENGTH(ST) - функция типа INTEGER; возвращает длину строки ST.

POS(SUBST, ST) - функция типа INTEGER: отыскивает в строке ST первое вхождение подстроки SUBST и возвращает номер позиции, с которой она начинается; если подстрока не найдена, возвращается ноль.

STR(X [:WIDTH [:DECIMALS]], ST) - процедура; преобразует число Х любого вещественного или целого типов в строку символов ST так, как это делает процедура WRITELN перед выводом; параметры WIDTH и DECIMALS, если они присутствуют, задают формат преобразования:

WIDTH определяет общую ширину поля, выделенного под соответствующее символьное представление вещественного или целого числа X, а DECIMALS - количество символов в дробной части (имеет смысл только в том случае, когда Х - вещественное число).

VAL(ST, X, CODE) - процедура; преобразует строку символов ST во внутреннее представление целой или вещественной переменной X, которое определяется типом этой переменной; параметр CODE содержит ноль, если преобразование прошло успешно, и тогда в Х помещается результат преобразования, в противном случае он содержит номер позиции в строке ST. где обнаружен ошибочный символ, и в этом случае содержимое Х не меняется; ведущие пробелы в строке ST должны отсутствовать.

UPCASE(CH) - функция типа CHAR; возвращает для символьного выражения CH, которое должно представлять собой строчную латинскую букву, соответствующую заглавную букву; если значением CH является любой другой символ, функция возвращает его без преобразований.

Примеры:

 

var

х: real;

у: Integer:

st,st1: string;

st:=concat('12','345'); {строка st содержит 12345}

st1:=copy(st,3,length(st)-2); {st1 содержит 345}

insert('-',st1,2); {строка st1 содержит 3-45}

delete(st,pos{'2',st),3); {строка st содержит 12}

str(pi:6:2,st); {строка st содержит 3.14)

st1:='3,1415':

 

Сравнение строк:

 

'Turbo' < 'Turbo Pascal'

'Паскаль' > 'Turbo Pascal'