Лекция: Структуровані типи даних.

Масиви

Масив – це структурований тип даних, який складається із фіксованої кількості елементів одного і того ж типу.

Опис масиву в програмі має вигляд

<ім’я типу> array [<список індексних типів>] of <тип>;

де <ім’я типу> – ідентифікатор; array, of – зарезервовані слова (масив, із); <список індексних типів> – список з одного або декількох індексних типів (кількість вимірів масиву не обмежується), розділених комами; <тип> – тип елементів масиву, який може бути будь-яким крім файлового. Як індексний тип може використовуватися будь-який порядковий тип (найчастіше використовується тип-діапазон).

Масив можна описати в розділі Var безпосередньо або за допомогою раніше описаного ідентифікатора типу:

Type Tm= array[1..10] of integer;

Var a, b: array[1..100] of double;

r: array[1..100] of double;

s: array[1..100] of double;

c, d: Tm;

x: array[1..10, 1..10] of integer;

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

тут масиви a, b, r, s описані безпосередньо, масиви c, d описані за допомогою ідентифікатора типу, а двовимірні масиви x, y описані безпосередньо (вище наведені два можливі еквівалентні способи опису).

Для масивів допускається тільки операція присвоєння, якщо ідентифікатори цих масивів є в одному і тому ж спискові визначення типу. Тому оператор a:=b; є правильним і присвоїть елементам масиву a відповідні елементи масиву b. Оператор r:=s; – неправильний, оскільки ідентифікатори цих масивів визначені в різних списках.

Для доступу до окремого елемента масиву потрібно разом з іменем масиву вказати у квадратних дужках його індекс (місце розташування в масиві): a[5], x[3,4] або y[5][6]. З елементами масиву можна працювати як із простими змінними.

Масив вважається динамічним, якщо при описові такого масиву в програмі межі індексів не вказуються. Розподіл пам’яті і задання верхньої межі для кожного виміру динамічного масиву забезпечується під час виконання програми процедурою SetLength. Нижня межа кожного виміру дорівнює нулю. Для вивільнення пам’яті потрібно ідентифікаторові масиву присвоїти значення NIL або використати процедуру Finalize. Наприклад,

Var a: array of integer;

b: array of array of char;

c: array of array of array of double;

i, j: integer;

Begin

{Розподіл пам’яті}

SetLength(a,10);

{Довжина першого виміру (кількість рядків)}

SetLength(b,10);

{Довжина кожного рядка)}

for i:=0 to 9 do

SetLength(b[i], 20);

{Кубічний масив c[0..2, 0..2, 0..2]}

SetLength(c,3);

for i:=0 to 2 do

begin SetLength(c[i],3);

for j:=0 to 2 do

SetLength(c[i,j],3); end;

{Робота з масивами}

………………

{Вивільнення пам’яті}

a:=NIL;

Finalize(b);

Finalize(c);

End.

У наведеному прикладі: а – одновимірний масив цілих чисел, якому розподілена пам’ять для десяти елементів; b – двовимірний масив символів із 10 рядків по 20 символів у рядку; c – тривимірний масив дійсних чисел. Нижня межа індексів для кожного виміру динамічного масиву завжди дорівнює нулю. У багатовимірних масивах спочатку встановлюється довжина його першого виміру, потім другого, третього і т. д.

Алгоритми обробки масивів.До традиційних алгоритмів обробки даних належать: пошук максимального і мінімального елементів масиву, накопичення сум і обчислення добутків елементів масиву, циклічний зсув масиву, побудова об’єднання, перерізу, різниці масивів та інші.

Приклад 1.Опишемо алгоритм пошуку максимального елемента масиву. Виберемо один з елементів масиву (наприклад, перший) і порівнюватимемо його з рештою елементів масиву. Якщо зустрінеться більший елемент, то він запам’ятовується і порівняння продовжується. Після перегляду всіх елементів масиву буде знайдено найбільший елемент.

Для реалізації алгоритму командою File|New Application створимо новий проект. Присвоїмо формі заголовок Обчислення функції (властивість Caption). Командою File|Save All запишемо програмний модуль у файл з іменем ULAB3_1.pas, а проект – LAB3_1.dpr.

Рис.3.1 Форма Пошук максимального елемента

Розробимо форму для введення початкових даних і виведення результату. Для введення кількості елементів масиву розмістимо на формі компонент Edit. Для введення елементів масиву використаємо багаторядковий редактор Memo. Розмістимо на формі компонент Memo і встановимо йому такі значення властивостей: Name= Memo1 (програмне ім’я); ScrolBars=ssBoth (горизонтальне і вертикальне прокручування), а властивість Lines очистимо. Для цього потрібно у полі значення властивості Lines двічі клацнути лівою клавішею мишки. Появиться вікно String list editor, в якому потрібно вилучити текст і натиснути кнопку OK. Пояснення до цих компонентів зробимо за допомогою компонента Label (властивість Caption).

Результат виводитимемо за допомогою компонента Edit.

Крім цього, розмістимо на формі дві керуючі кнопки (компонент Button) з написами Знайти та Вихід (властивість Caption). Загальний вигляд форми наведений на Рис.3.1.

Обробник кнопки Знайти міститься у програмному модулі ULAB3_1 і має вигляд:

{Обробник кнопки Знайти}

procedure TForm1.Button1Click(Sender: TObject);

Var n,i,max:integer;

A:array[0..299] of integer;

begin

if Edit1.Text='' then ShowMessage('Введіть n')

else begin

n:=StrToInt(Edit1.Text);

if (n<0) or (n>299) then ShowMessage('Недопустиме n')

else if Memo1.Lines.Count< n then

ShowMessage('Введіть всі елементи масиву')

else begin

for i:=0 to n-1 do

A[i]:=StrToInt(Memo1.Lines[i]);

max:=A[0];

for i:=1 to n-1 do

if max<A[i] then max:=A[i];

Edit2.Text:=IntToStr(max);

end;

При введенні початкових даних кількість елементів масиву розміщується у властивості Text компонента Edit1, а елементи масиву – у властивості Lines компонента Memo1, який є набором символьних рядків. Елементи масиву розміщується по одному в рядку починаючи з нульового номера. Кількість використаних рядків міститься у властивості Count набору Lines.

На початку програми здійснюються перевірки чи введено кількість елементів n, чи воно допустиме і чи введені всі елементи масиву. Якщо це не так, то виводяться відповідні повідомлення за допомогою функції ShowMessage.

Після введення початкових даних здійснюється пошук максимального елемента і його виведення. Результат виконання програми наведений на Рис. 3.1.

Приклад 2.Розглянемо алгоритм побудови перерізу двох масивів. Нехай задано два масиви цілих чисел,. Розробити програму, яка будує переріз масивів. Переріз масивів — це всі елементи масиву, які містяться у масиві і взяті по одному разу.

Очевидно, що переріз масивів матиме не більше 200 елементів. Помістимо їх у масив .

Для побудови перерізу кожний елемент масиву порівнюється з усіма елементами масиву. Якщо елемент масиву збіжиться з деяким елементом масиву, то цей елемент належатимиме перерізові. Якщо такого елемента ще немає в масиві, то він туди записується. Наведемо один з варіантів програми побудови перерізу двох масивів.

Розробимо форму для введення початкових даних і виведення результату.

Для введення кількості елементів масивів n і m розмістимо на формі два компоненти Edit. Для введення елементів масивів і використаємо багаторядковий редактор Memo. Розмістимо на формі два компоненти Memo і встановимо їм значення властивості ScrolBars=ssBoth (горизонтальне і вертикальне прокручування), а властивість Lines очистимо. Для цього потрібно у полі значення властивості Lines двічі клацнути лівою клавішею мишки. Появиться вікно String list editor, в якому потрібно вилучити текст і натиснути кнопку OK. Пояснення до цих компонентів зробимо за допомогою компонента Label (властивість Caption).

Рис.3.2 Форма Переріз масивів

Для виведення результату використаємо компонент Edit – кількість елементів перерізу, а елементи виведемо в Memo.

Крім цього, розмістимо на формі дві керуючі кнопки (компонент Button) з написами Знайти та Вихід (властивість Caption) і програмними іменами Button1, Button2 (властивість Name). Загальний вигляд форми наведений на Рис.3.2.

Обробники кнопок Знайти та Вихід містяться у програмному модулі ULAB3_2 і мають вигляд:

procedure TForm1.Button1Click(Sender: TObject);

VAR a, c: array[1..200] of integer;

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

n, m, k, i, j: integer;

f1, f2: boolean;

BEGIN

{Введення початкових даних}

n:=StrToInt(Edit1.Text);

for i:=1 to n do

a[i]:=StrToInt(Memo1.Lines[i-1]);

m:=StrToInt(Edit2.Text);