Лабораторна робота № 4. Масиви. Алгоритми сортування та пошуку.
Мета: Складні типи даних. Тип даних масиви. Лінійний та бінарний пошук елемента в масиві. Задачі сортування. Прості алгоритми сортування.
Короткі теоретичні відомості.
1. Складні (складені) типи.
У мові Pascal реалізований механізм визначення складних (складених) типів даних. Новий тип даних визначається як структурована сукупність даних-компонент стандартних або раніше визначених типів. Оскільки типи компонент можуть також складеними, можна будувати складні ієрархії типів. Методи структурування даних у мові дозволяють будувати масиви, записи, множини і файли. Ці методи називають статичними, оскільки їх опис здійснюється попередньо. Більш складні структури можна створити динамічно - у процесі виконання програми - за допомогою посилання. При вивченні складних типів основна увага приділяється способам конструювання даного і способам доступу до компонентів даного.
2. Регулярний тип. Масиви.
Прикладом складного (регулярного) типу являються масиви. Масив - це найбільш поширена структура даних. Масив - це послідовність однотипних даних, що об’єднана загальним іменем, елементи (компоненти) якої відрізняються (ідентифіцируються) індексами. Індекс елемента вказує місце (номер) елемента в масиві. Кількість елементів масиву фіксовано і визначено в його описі. Доступ до елемента масиву здійснюється обчисленням значення його індексу. Тому масиви - це структури даних з прямим (випадковим) доступом. Всі компоненти масиву є однаково доступними. При визначенні регулярного типу задається і тип компонент, і тип індексів. Саме визначення має вид:
<ім’я типу > = Array [< тип індексу >] of <тип компоненти >;
м
асив
Приклади:
а) Type LinearTable = Array [0..100] of Integer;
б) type Word = Array [1..20] of Letter;
Letter = ‘a’..’z’;
Order = Array [Letter] of Integer;
в) type Matrix = array [1..N] of array [1..M] of Real;
г) Tenzor = array [-10..10] of array [0..20] of array [0..3] of Real;
У прикладі в) М і N - константи цілого типу. Зверніть увагу на те, що значення типу Matrix - M*N матриці - визначаються як масиви, компонентами яких, в свою чергу, є масиви з дійсних чисел.
Регулярний тип, значеннями якого є багатомірні масиви (наприклад, в) і г)), можна визначати в скороченому виді:
Type <ім’я> = Array [<Tип> {,<Tип>} ] of <тип компоненти>;
Наприклад:
а) Type matrica = array [1..N,1..M] of real;
б) Type Index1 = -10..10;
Index2 = 0..20;
Index3 = 0..3;
Tenzor = Array [Index1, Index2, Index3] of Real;
в) Type Labyrinth = array [1..100,1..100] of Boolean;
Типи Real і Integer не можуть бути типами індексів!
Компонента змінної регулярного типу - компонента масиву явно позначається іменем змінної, за яким у квадратних дужках слідують індекси; індекси являються виразами типу індексу. Наприклад, Table[1, i+j ], T[2*i+1, (j*j) mod i], S[Monday, Friday]. Зверніть увагу на те, що на відміну від індексних виразів, межі індексів у змінних - масивах повинні бути константами. Значення індексних виразів повинні бути значеннями типу індексу, тобто знаходитись в межах, що визначені межами індексів.
Розглянемо приклад:
Приклад 1. Програма обчислює скалярний добуток вектора V і вектора V`, отриманого з V перестановкою координат у зворотному порядку.
Program ScalarMult;
Const n = 10;
Type Vector = array[1..n] of Real;
Var V : Vector; Summa : Real; i : Integer;
Begin
For i := 1 to n do begin { блок читання вихідного вектора }
Write(‘Введіть координату вектора : ‘); Readln(V[i]);
end;
Summa := 0; { блок обчислень}
For i := 1 to n do
Summa := Summa + V[i]*V[n-i+1];
write(‘ Результат : ‘, Summa)
End.
Блок обчислень можна оптимізувати за часом. Зазначимо, що Summa обчислюється за формулою: : Summa = V[1]*V[n] + V[2]*V[n-1] +...+ V[2]*V[n-1] + V[1]*V[n]. Отже, її доданки, рівновіддалені від кінців, рівні. Тому кількість повторень циклу можна зменшити вдвоє. При цьому необхідно враховувати парність числа n:
{Program ScalarMult1;}
For i := 1 to n div 2 do Summa := Summa + V[i]*V[n-i+1];
If Odd(n)
then Summa := 2*Summa
else Summa := 2*(Summa + V[n div 2 + 1];