Структурні типи даних. Записи. Опис записів, поля. Обробка даних у записах.
Структурні типи даних визначають впорядковану сукупність скалярних змінних і характеризуються типом своїх компонентів. В мові Pascal допускаються наступні структуровані типи даних: рядки, масиви, множини, записи, файли і покажчики.
Масиви, рядки, множини давали складені структури даних, елементи яких були одного і того ж типу. Кількість елементів в них могла б бути різною. В масивах фіксованою, в рядках і множинах могла б змінюватися, але тип був би спільним. Часто виникає проблема у формування структур даних, елементи яких мають різний тип.
Запис – це структурований тип даних, які складається із фіксованого числа компонентів різного типу.
Оголошуються записи за допомогою слова record. Після нього слідує перелік окремих елементів запису. Елементи описуються через ідентифікатор і тип, що розділюється двокрапкою. В кінці запис закривається службовим словом end.
TYPE
<ім’я типу запису> = RECORD
<ідентифікатор1>: <тип поля>; <ідентифікатор2>: <тип поля>; ... END;
Наприклад
Type Student = record Name: string; Yy, mm, dd: word;
Pol: (female, male); Educ: (state, pay); Usp:real; End;
Ідентифікатор поля повинен бути унікальним тільки в межах запису, однак в силу уникнення помилок краще робити його унікальним в межах усієї програми.
Під величини в пам’яті відводиться, розмір якого дорівнює сумі розмірів кожного поля.
Оскільки записи є комбінаціями різних полів, то доступ до окремого поля повинен здійснюватися при допомозі складеної ідентифікації, кожне поле має своє ім’я.
Якщо весь запис позначається деяким ідентифікатором деякої змінної, то кожне ім’я поля має вигляд
<ідентифікатор запису>.<ідентифікатор поля запису>
Наприклад a.name , a.year, a.pol, a.educ
Враховуючи, що запис є комбінацією різних типів, можна будувати записи із записів.
Складені імена a.name можна використовувати скрізь, де допускається застосування типу поля.
До них можна застосовувати оператор присвоювання, складені імена можна використовувати в в операторах вводу-виводу. Допускається застосування оператора присвоєння до записів вцілому, якщо вони мають один і той же тип. Часто зручно користуватись масивом записів. Вказавши один раз оператор with, можна працювати з іменами полів, як зі звичайними змінними, тобто без вказання перед ідентифікатором поля імені змінної, яка визначає запис.
With <змінна типу запис>do <оператор>;
Записи зазвичай використовуються при роботі з динамічними структурами і для організації файлів на магнітних дисках. Записи також можуть слугувати для опису комплексних чисел, оскільки в мові Pascal немає для цього спеціальних засобів. В цьому випадку дійсна і уявна частини комплексного числа є полями запису.
Поняття рекурсії. Ітеративні та рекурсивні програми. Види рекурсії. Рекурсивні процедури та функції. Найпростіші схеми рекурсивних програм.
Під повторенням розуміють виконання деякої послідовності команд у визначеному порядку більше, ніж 1 раз. Повторення, у свою чергу, ділиться на 2 види: ітерація; рекурсія.
Під ітерацією розуміють виконання деякої послідовності дій із зміною так званого параметра ітерації або із перевіркою умови ітерації. У програмуванні це відповідно оператори циклу з параметром та оператори циклу з перед- або післяумовою.
Другий спосіб реалізації повторення, що називається рекурсією, передбачає використання в алгоритмі чи програмі звертання до самого себе. Це приводить до виконання такого алгоритму від початку до нового самозвертання. Рекурсію ще можна описати висловом «виконувати те ж саме, що й минулий раз, від початку до даного місця».
Рекурсія та ітерація – абсолютно еквівалентні способи реалізації повторень. Будь-який ітераційний алгоритм легко перетворити на рекурсивний і навпаки.
Приклад:
– ітерація;
– рекурсія.
Рекурсія як повторення реалізується у програмуванні через рекурсивні підпрограми – процедури і функції. Підпрограма, яка викликає сама себе, називається рекурсивною підпрограмою. Можна виділити явний і неявний спосіб організації рекурсії.
Під час явного рекурсивного виклику підпрограма звертається сама до себе, тобто в тілі цієї підпрограми є оператор виклику цієї ж підпрограми.
Під час неявного способу організації рекурсії підпрограма звертається до другої підпрограми, яка, у свою чергу, містить виклик першої підпрограми.
Таким чином, рекурсивна підпрограма повинна містити такі елементи:
опис кроку рекурсії (опис тих дій, які повинні повторюватись);
серед описаних дій повинен бути виклик тієї ж самої підпрограми.
Під час прямого ходу рекурсії будується ланцюжок викликів рекурсивної підпрограми. В ході таких викликів у пам’яті виділяється певна кількість байт для збереження стану процесора в момент виклику підпрограми. Також виділяється пам’ять для збереження локальних даних. Оскільки об’єм пам’яті ЕОМ обмежений, то, очевидно, що нескінченного рекурсивного ланцюжка побудувати не можна;
потрібно передбачити умову зупинки рекурсії.
Логіка багатьох задач вимагає того, щоб у потрібний момент зупинити побудову рекурсивного ланцюжка (це потрібно для побудови результативних рекурсивних підпрограм). Отже, виникає потреба у описі умови зупинки рекурсії (таку умову називають опорною умовою рекурсії). Якщо умова зупинки рекурсії виконується, то при цьому починається процес, який називають зворотнім ходом рекурсії, під час якого відбувається підстановка проміжних результатів у точку виклику рекурсивної підпрограми.