Понятие массива. Одномерные массивы

Массивы являются представителями структурированных типов данных, то есть таких, переменные которых составлены из более простых элементов согласно определённому порядку. Для массивов характерно то, что они являются совокупностью некоторого числа одинаковых элементов. В простейшем случае эти элементы могут быть занумерованы натуральными числами из некоторого диапазона. Рассмотрим пример такой переменной в Турбо Паскале:

var a: array [1..10] of real;

Переменная a состоит из десяти ячеек типа real, можно записывать и извлекать значения из них, пользуясь записью a[< номер ячейки >].

Пример 1. Поиск наибольшего числа среди элементов массива.

program FindMaximumInArray;

var a: array [1..10] of real;

i,max: integer;

Begin

for i:=1 to 10 do begin

write('Введите элемент номер ',i,' -> ');

readln(a[i]);

end;

max:=a[1];

for i:=2 to 10 do

if a[i]>max then max:=a[i];

writeln('Максимум равен ',max);

readln;

end.

 

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

Нумеровать элементы массивов можно не только от единицы, но и от любого целого числа. Вообще для индексов массивов подходит любой порядковый тип, то есть такой, который в памяти машины представляется целым числом. Единственное ограничение состоит в том, что размер массива не должен превышать 64 Кб. Рассмотрим некоторые примеры объявления массивов.

var Numbers: array [0..1000] of integer;

Names: array [1..10] of string;

Crit: array [sh or tint] of boolean;

CountAll: array [char] of integer;

Count: array ['a'..'z'] of integer;

В следующем примере показано для чего может понадобиться последний тип.

Пример 2. Подсчет количества различных букв в строке.

program CountLetters;

var s: string;

count: array ['a'..'z'] of byte;

ch: char;

i: byte;

Begin

write('Введите строку > ');

readln(s);

for i:=1 to length(s) do

if (s[i]>='a') and (s[i]<='z') then inc(count[s[i]]);

writeln('Количество различных букв в строке: ');

for ch:='a' to 'z' do

if count[ch]<>0 then

writeln(ch,': ',count[ch]);

readln;

end.

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

При необходимости можно нумеровать массивы не одним индексом а двумя и более. Двумерному массиву соответствует матрица в математике, то есть прямоугольная таблица.

Примеры описаний многомерных массивов:

var Matrix: array [1..4,1..3] of real;

Cube3D: array [1..5,1..5,1..5] of integer;

Рассмотрим пример использования двумерного массива.

Пример 3. Построить календарь на следующий год, то есть при вводе номера месяца и числа выдавать день недели.

program Calendar;

type tWeekDay = (Mon,Tue,Wed,Thu,Fri,Sat,Sun,NoDay);

           {NoDay - нет дня (например, 30.02)}

tCalendar = array [1..12,1..31] of tWeekDay;

var CL: tCalendar;

m,d: byte; {месяц и число}

wd: tWeekDay; {день недели}

 

Begin

   {Строим массив:}

{1. Заполним весь календарь значениями "нет дня":}

for m:=1 to 12 do

for d:=1 to 31 do CL[m,d]:=NoDay;

  {2. Строим массив-календарь:}

m:=1; d:=1;

wd:=Mon;

Repeat

CL[m,d]:=wd;

case m of

4,6,9,11:   if d=30 then begin m:=m+1; d:=1; end else d:=d+1;

1,3,5,7,8,10,12: if d=31 then begin m:=m+1; d:=1; end else d:=d+1;

2:          if d=28 then begin m:=m+1; d:=1; end else d:=d+1;

end;

wd:=tWeekDay((ord(wd)+1) mod 7);

until m=13;

{Выводим на экран:}

repeat

write('Номер месяца > '); readln(m);

write('Число > '); readln(d);

case CL[m,d] of

Mon: writeln('Понедельник');

Tue: writeln('Вторник');

Wed: writeln('Среда');

Thu: writeln('Четверг');

Fri: writeln('Пятница');

Sat: writeln('Суббота');

Sun: writeln('Воскресенье');

NoDay: writeln('Такого дня нет в календаре');

end;

until false;

end.

Сортировка и поиск

В прикладных программах широко распространены два типа операций, связанных с массивами:

1. Упорядочивание элементов массива по возрастанию или убыванию (сортировка)

2. Поиск элемента в массиве.

 

Рассмотрим простейший вариант сортировки массива (сортировка выбором). Пусть есть массив из n элементов; сначала найдём в нём самый маленький среди элементов с номерами 2,3,...n и поменяем местами с первым элементом, затем среди элементов с номерами 3,4,...n найдём наименьший и обменяем со вторым, и т. д. В результате наш массив окажется отсортированным по возрастанию.

program SelectSort;

const n = 10;

var a: array [1..n] of integer;

i,j,jmin,buf: integer;

{ jmin - номер наименьшего элемента,

buf используется при обмене значений двух элементов}

Begin

for i:=1 to 10 do begin

write('Введите элемент номер ',i,' -> ');

readln(a[i]);

end;

 

for i:=1 to n-1 do begin

jmin:=i;

for j:=i+1 to n do

if a[j]<jmin then jmin:=j;

buf:=a[i];

a[i]:=a[jmin];

a[jmin]:=buf;

end;

 

write('Результат: ');

for i:=1 to 10 do write(a[i],' ');

readln;

end.

Другой способ — пузырьковая сортировка, он работает чуть быстрее, чем предыдущий. На первом этапе двигаемся от n-го элемента до 2-го и для каждого из них проверяем, не меньше ли он предыдущего; если меньше, то меняем местами текущий и предыдущий. В итоге первый элемент будет наименьшим в массиве. На втором этапе также проходим элементы от n-го до 3-го, на третьем — от n-го до 4-го, и т. д. В итоге массив будет отсортирован по возрастанию.

program BubbleSort;

...

var i,j: integer;

buf: integer;

Begin

...

for i:=2 to n do

for j:=n downto i do

if a[j]<a[j-1] then begin

   buf:=a[j];

   a[j]:=a[j-1];

   a[j-1]:=buf;

end;

end.

 

Лекция 8. Тип запись

Тип запись, также как и массив, является структурированным типом данных, то есть таким, переменные которого составлены из нескольких частей. В Турбо-Паскале существует возможность объединить в одну переменную данные разных типов (тогда как в массиве все элементы имеют одинаковый тип). Приведём пример такого типа. Пусть в переменной требуется хранить сведения о некотором человеке: ФИО, пол, адрес, телефон. Тогда для хранения этих данных будет удобен такой тип:

type tPerson = record

   Name,Surname,SecondName: string [30];

   Male: boolean;

   Address: string;

   Phone: longint;

end;

 

Объявление переменной типа запись выполняется стандартно, с помощью var. Части записи (в нашем случае: Name, Surname, SecondName, Male, Address, Phone) называются полями. Обращение к полю записи в программе производится с помощью знака ‘.’ (точка). Пример обращения к полям:

 

var p: tPerson;

...

Begin

...

p.Surname:=’Иванов’;

p.Name:=’Иван’;

p.SecondName:=’Иванович’;

...

if (p.Phone<0) or (p.Phone>999999)

then writeln(‘Ошибка’);

...

end.

 

Заметим, что в этом примере постоянно приходится обращаться к полям одной и той же переменной типа запись, и, следовательно, постоянно писать её имя. Есть возможность избавиться от этого неудобства. В Турбо Паскале есть оператор присоединения (with), который позволяет один раз указать, какой записью мы пользуемся и в дальнейшем писать только имена полей. Обычно этот оператор выглядит так:

with <имя_записи> do <оператор>;

Чаще всего в качестве оператора используется составной оператор.

Пример:

with p do begin   

Surname:=’ Иванов’;

Name:=’Иван’;

...

end;

 

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

 

const N = 30;

type tStaff = array [1..N] of tPerson;

 

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

 

type tPoint = record

    x,y: integer;

end;

 

tRectangle = record

    LeftTop: tPoint;

    Width, Height: integer;

    Color: integer;

end;

 

Для такой записи можно применять ещё одну форму оператора with, которая может «присоединять» несколько имён записей, например:

 

var rect: tRect;

with rect, LeftTop do begin

x:=100;

y:=150;

Color:=11;

...

end;

 

Без использования with появились бы выражения вида rect.Color, rect.LeftTop.x, rect.LeftTop.y и т. п.

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

 

const MaxVertex = 200;

 

type tPolygon = record

    size: integer;

    V: array [1..MaxVertex] of tPoint;

    Color: tColor;

end;

 

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

type tFKind = (fCir,fRect,fSqr);

tFigure = record

    Color: integer;

    case kind: tFKind of

      fCir: (Center: tPoint; r: integer);

      fRect: (LeftTop,RightBottom: tPoint);

      fSqr: (LT: tPoint; size: integer);

end;

В этой записи имеется одно обычное поле (Color), а остальные 6 и представляют собой вариантную часть. Для окружности в ней имеются поля Center и r, для прямоугольника — LeftTop и RightBottom, для квадрата — LT и size. Фраза kind: tFKind не является обязательной, она служит для понимания того, какие поля к каким фигурам относятся. Можно написать просто case integer of... и нумеровать варианты целыми числами. Заметим также, что в объявлении нашей записи нет слова end, относящегося к case.

Мы можем обращаться к любому полю вариантной части, однако следует помнить, что при записи данных в поле для одной фигуры поля для других фигур могут измениться. Чтобы понять, почему так происходит, достаточно рассмотреть способ хранения переменной типа tFigure:

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