Оператор вводу інформації.

Оператор вводу даних призначений для вводу даних з клавіатури та присвоювання їх змінним. Є два оператори вводу даних: read та readln. Оператор read має такий вид:

read(<список змінних>); readln(<список змінних>);

де <список> задає ті змінні, значення яких необхідно ввести з клавіатури. Можна вводити з клавіатури значення всіх стандартних типів даних, крім boolean. При виконанні оператора очікується введення даних вказаного типу. Значення повинні вводитись у строгій відповідності з синтаксисом мови Паскаль. При цьому ніякого додаткового повідомлення про очікування вводу даних на екрані не виводиться. Дані можна вводити списком, розділяючи їх символом "пробіл", або по одному. Введення закінчується натискуванням клавіші Enter. Оператор вводу readln має аналогічний формат. Для скалярних типів при вводі даних з клавіатури обидва оператори працюють аналогічно. Типовими помилками використання оператора є:

 розбіжність типу змінної і типу значення, що вводиться;

 введення виразів, а не значень.

Для наочності рекомендується перед оператором вводу використовувати оператор виводу з підказкою про тип та кількість значень, що вводяться.

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

Цикл – це процес виконання певного набору команд деяку кількість разів.

Є три види команд циклів: з параметром, з передумовою та з післяумовою.

Розглянемо цикли з передумовою та з післяумовою.

Команда циклу з передумовою (while) має вигляд

While <логічний вираз> do <команда1>;

Дія команди. Доки значення логічного виразу істинне, виконується команда1. Істинний логічний вираз описує умову продовження процесу виконання команди циклу.

Оператор, який стоїть після do називається тілом циклу.

Умова – це логічний вираз.

У якості тіла циклу найчастіше використовують складений оператор. Оператор циклу While найчастіше використовується у тому випадку, коли кількість проходів по циклу не відома (наперед). Приклад

Кожний член натурального ряду від 7 до 30 зменшити в три рази. Обчислити добуток. Program Natriad;

Var A:integer;M:real;

Begin

M:=1; A:=7;

While A<30 do begin

WriteLn (' A/3=', A/3:5:2); M:=M*A/3;

WriteLn (' M=',M:5:2); A:=A+1; End;

Readln; End.

Команда циклу з післяумовою (repeat) має вигляд

Repeat <команди> until <логічний вираз>;

Дія команди. Команди виконуються в циклі, доки значення логічного виразу не стане істинним. Істинний логічний вираз задає умову виходу з циклу.

Тілом циклу є послідовність, яка записана між словами repeat і until.

Вказівка повторення з параметром призначена для організації багатократного виконання тіла циклу для значень параметра циклу з деякої впорядкованої дискретної множини.

Вказівку повторення з параметром використовують у тих випадках, коли наперед можна визначити кількість повторень виконання вказівок циклу.

Вказівка повторення з параметром записується у вигляді: for <параметр:=вираз1> to <вираз2> do begin

<вказівка1>;

<вказівка2>;……….;........

<вказівка N>; end;

for <параметр:=вираз1> downto <вираз2> do begin

<вказівка1>;

<вказівка2>;…….;........

<вказівка N>;end;

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

Вираз1 (початковий параметр вказівки) — це деяка константа такого ж самого типу, що й параметр вказівки.

Вираз2 (кінцевий параметр вказівки) — це деяка константа такого ж самого типу, що й параметр вказівки.

Якщо в тілі вказівки повторення з параметром необхідно виконати тільки одну вказівку, то складеної вказівки begin.. end використовувати не потрібно.

for <параметр:=вираз1> to <вираз2> do <вказівка1>;

6. Структурні типи даних. Масиви. Опис масивів. Обробка даних у масивах.

Структурні типи даних визначають впорядковану сукупність скалярних змінних і характеризуються типом своїх компонентів. В мові Pascal допускаються наступні структуровані типи даних: рядки, масиви, множини, записи, файли і покажчики.

Регулярнітипи – масиви Це означає, що елементи таких структур даних будуть однотипні значення (цілі числа, символи, перелічувальні типи). На відмінну від масивів, де кількість елементів є фіксованою і незміною, множини можуть змінювати свій склад, проте кількість елементів не може перевищувати деякого фіксованого значення. І масиви, і рядки можуть мати декілька однакових елементів, у множині всі елементи різні.

Масив - це структурний тип даних, що складається з фіксованого числа елементів, що мають один і той же тип. Можна використовувати і будь-який інший раніше описаний тип, тому цілком правомірно існування масивів записів, масивів покажчиків, масивів рядків, масивів масивів і т.д. Елементами масиву можуть бути дані будь-кого, але тільки одного типу, включаючи структуровані. Тип елементів масиву називається базовим. Число елементів масиву фіксується при описі і в процесі виконання програми не міняється.

Доступ до кожного окремого елемента здійснюється шляхом індексації елементів масиву. Індекси є виразами будь-якого скалярного типу, окрім дійсного. Тип індексу визначає межі зміни значень індексу. Для опису масиву призначено словосполучення array (масив з...).

Формат: Туре <имя типа> = аггау[тип індексу] of <тип компонента>

Var <идентификатор>: <имя типа>;

Якщо в такій формі опису масиву заданий один індекс, масив називається одновимірним, якщо два індекси - двомірним, якщо n індексів, n-вимірним. Розмірність обмежена тільки об'ємом пам'яті.

Дії над масивами. Для роботи з масивом як єдиним цілим використовується ідентифікатор масиву без вказівки індексу в квадратних дужках. Масив може брати участь тільки в операціях відношення "рівно", не "рівно" і в операторі присвоєння. Масиви, що беруть участь в цих діях, повинні бути ідентичні по структурі, тобто мати однакові типи індексів і однакові типи компонентів.

Ініціалізація масиву полягає в присвоєнні кожному елементу масиву одного і того ж значення, відповідного базовому типу.

Для ініціалізації двомірного масиву звичайно використовується вкладений оператор for.

Копіюванням масивів називається присвоєння значень всіх елементів одного масиву всім відповідним елементам іншого масиву. Копіювання можна виконати одним оператором присвоєння, наприклад А: = D; або за допомогою оператора for:

Перестановка значень елементів масиву здійснюється за допомогою додаткової змінної того ж типу, що і базовий тип масиву.

В мові Pascal допускається опис багатовимірних масивів. Такий опис виконується за правилами: - двохвимірні масиви

1.) TYPE m1=array [1..10] of real;

Var m2: array [1..3]of ml;

Ml - це ім'я типу, елементи якого є одновимірні масиви (або вектори).

М2 - це ім'я змінної, яка є масивом з 3-х елементів, кожен такий елемент є вектором. В результаті отримуємо об'єднання, яке називається матрицею.

2.) Var m2:array[1..3,1..10] of real;

m2 - ім'я змінної, яка є двовимірним масивом дійсних чисел.

7. Структурні типи даних. Рядки. Опис рядків. Обробка даних у рядках.

Структурні типи даних визначають впорядковану сукупність скалярних змінних і характеризуються типом своїх компонентів. В мові Паскаль допускаються наступні структурні типи даних: рядки, масиви, множини, записи, файли, покажчики.

Рядок - це послідовність символів. При використовуванні у виразах рядок обов'язково береться в апострофи. Кількість символів в рядку (довжина рядка) може динамічно змінюватися від 0 до 255. Для визначення даних рядкового типу використовується ідентифікатор string, за яким слідує укладене в квадратні дужки значення максимально допустимої довжини рядка даного типу. Рядкові дані можуть використовуватися в програмі також як константи. Визначення рядкового типу встановлює максимальну кількість символів, яку може містити рядок.

Формат:

Туре <ім'я типу> = string [максимальна довжина рядка];

Var <ідентификатор...>: <ім'я типу>;

Вирази, в яких операндами служать рядкові дані, називаються рядковими виразами, вони складаються з рядкових констант, змінних, покажчиків функцій і знаків операцій. Над рядковими даними допустима операція зчеплення і операції відношення.

Операція зчеплення (+) застосовується для зчеплення декількох рядків в один результуючий рядок. Вираз "Е'+'С'+' 18'+*40'. Результат 'ЕС 1840". Довжина результуючого рядка не повинна перевищувати 255.

Операції відношення (=, < >, <, >=, <=) проводять порівняння двох рядкових операндів і мають пріоритет більш низький, ніж операція зчеплення, тобто спочатку завжди виконуються всі операції зчеплення, якщо вони присутні, і лише потім реалізуються операції відношення. Порівняння рядків проводиться зліва направо до першого неспівпадаючого символу, і той рядок вважається більшим, в якому перший неспівпадаючий символ має більший номер в стандартній таблиці символів. Результат виконання операцій відношення над рядковими операндами завжди має булевий тип і приймає значення True, якщо вираз істинний і False, якщо вираз помилковий.

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

Якщо значення змінної після виконання оператора присвоєння перевищує по довжині максимально допустиму при описі величину, всі зайві символи справа відкидаються.

До окремих символів рядка можна звернутися по номеру (індексу) даного символу в рядку. Індекс визначається виразом цілочисельного типу, який записується в квадратних дужках відразу за ідентифікатором рядкової змінної або константи.

8. Структурні типи даних. Множини. Опис множин. Операції над множинами.

Структурні типи даних визначають впорядковану сукупність скалярних змінних і характеризуються типом своїх компонентів. В мові Pascal допускаються наступні структуровані типи даних: рядки, масиви, множини, записи, файли і покажчики.

Множина – це структурований тип даних, який являє собою набір вибраних по якій-небудь ознаці або групі ознак об’єктів, які можна розглядати як єдине ціле. Елементи множини не впорядковані. Для опису множини використовується зарезервоване слово set (множина).

Регулярнийтип – множини. Це означає, що елементи таких структур даних будуть однотипні значення (цілі числа, символи, перелічувальні типи). На відмінну від масивів, де кількість елементів є фіксованою і незмінною, множини можуть змінювати свій склад, проте кількість елементів не може перевищувати деякого фіксованого значення. І масиви, і рядки можуть мати декілька однакових елементів, у множині всі елементи різні.

Оголошення множини, при доповненні стандартних слів set of, після яких вказується ідентифікатор елементів множини. В якості базових типів можуть бути лише порядкові типи і кількістю елементів до 256. Це цілі byte, shorting, символи char, логічні boolean.

Значення множинних величин задається в парі квадратних дужок, переліком через кому або інтервалом. Наприклад

A:=[109,100,0,5..50]; B:=[100,0..99]; C:=[‘A’,’Z’]; D:=[red];

Множини можуть бути порожніми [ ].

В пам’яті множини представляються у вигляді чисел достатньо великого розміру. Кожне із цих чисел в своєму подвійному записі матиме одиничний біт у позиції, що відповідає присутньому елементу. Таким чином множини займають у пам’яті 256 бітів і до 32 байт.

Якщо базовий тип є перелічувальний або інтервальний із меншою, ніж 256 елементів, то і відповідне поле в пам’яті буде менше. Задання перелічувальних типів визначає порядок бітів, що відповідають кожному елементу.

Над множинами можуть виконуватися наступні дії:

Обєднання (додавання). Виконується над множинами одного базового типу.

Наприклад. A:=[1,2,3] B:=[3,4,8] C:=A+B { C=[1,2,3,4,8] }

Виконання операції додавання фактично є побітовою операцією диз’юнкції.

Перетин (множеннямножин). Результатом є спільна частина двох множин.

Наприклад. [1,2,3]*[3,4,8] =[3] [1,2,3]*[ ]= [ ]

Виконання операції множення фактично є побітовою кон’юнкцією.

Віднімання. Результат віднімання деякої множини В від множини А будуть всі елементи А, яких немає в множині В.

Наприклад. [1,2,3]-[3,4,8]=[1,2]

Це побітова операція виключення або одиничними бітами у зменшуваному.

Операція належності

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

Наприклад. [1] in [3,4,8] = false..........[1] in [1,2,3]=true

Формування множини безпосередньо з клавіатури і вивід їх на екран неможливо, оскільки стандартні процедури вводу-виводу не допускають параметрів множини так як і перелічувального. Але ці дії легко реалізувати за рахунок операції об’єднання та перевірки належності in для виводу.

9. Структурні типи даних. Записи. Опис записів, поля. Обробка даних у записах.

Структурні типи даних визначають впорядковану сукупність скалярних змінних і характеризуються типом своїх компонентів. В мові 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 немає для цього спеціальних засобів. В цьому випадку дійсна і уявна частини комплексного числа є полями запису.

10. Поняття підпрограми. Класифікація підпрограм. Процедури та функції. Локальні та глобальні дані. Обмін даними між підпрограмами та основними програмами. Формальні та фактичні параметри. Класифікація параметрів.

Підпрограми призначені для реалізації алгоритмів опрацювання окремих частин деякої складної задачі. Вони дають змогу реалізувати концепцію структурного програмування, суть якого полягає в розкладанні складної задачі на послідовність простих підзадач і в складанні для алгоритмів розв’язування кожної під задачі відповідних підпрограмам. Розрізняють два види підпрограм: підпрограми-процедури і підпрограми-функції.

Підпрограми поділяються на стандартні та підпрограми користувача.

Стандартні підпрограми створювати не потрібно – вони містяться у стандартних модулях System, Crt, Graph, тощо. Підпрограма користувача – це пойменована група команд, яку створюють і описують в основній програмі в розділах Procedure або Function і до якого звертаються з будь-якого місця програми потрібну кількість разів.

Процедури

Загальний опис процедури:

Procedure <назва> (<список формальних параметрів>);

<розділи описів і оголошень процедури>;

Begin

<розділ команд процедури>

End;

У списку формальних параметрів перераховують змінні разом із зазначенням їхніх типів. Розрізняють параметри-аргументи (параметри-значення) – вхідні дані для процедури, і параметри-результати (параметри-змінні), через які можна повертати результати роботи процедури в основну програму. Перед списками параметрів-змінних кожного типу записують слово Var.

Процедуру викликають за допомогою команди виклику:

<назва процедури> <список фактичних параметрів>

Фактичними параметрами-значеннями можуть бути сталі, змінні, вирази, а параметрами-змінними – лише змінні. Між фактичними і формальними параметрами має бути відповідність за кількістю й типами. Відповідні фактичні параметри можуть мати різні імена. Команда виклику функціонує так: значення фактичних параметрів присвоюються відповідним формальним параметрам процедури, виконується процедура, визначаються параметри-змінні, значення яких надаються (повертаються) відповідним фактичним параметрам у команді виклику.

Змінні, описані в розділі описів основної програми, називаються глобальними. Вони діють у всіх підпрограмах, з яких складається програма. Змінні, описані в розділі конкретної процедури, називаються локальними. Вони діють тільки в межах даної процедури. Процедури можуть отримувати й повертати значення не тільки через параметри-змінні, але й через глобальні змінні. Тому списків параметрів у процедурі може й не бути.

Функції

Функція, на відміну від процедури, може повертати в місце виклику лише один результат простого стандартного типу.

Загальний опис функції:

Function <назва> (<список формальних параметрів>): <тип функції>;

<розділи описів і оголошень функції>;

Begin

<розділ команд функції, де має бути така команда: назва:=вираз>

End;

У розділі команд функцій має бути команда присвоєння призначення виразу назві функції. Результат функції повертається в основну програму через її назву. Виклик функції здійснюється лише з виразів так:

<назва функції> (<список фактичних параметрів>).

Існують рекурсивні підпрограми. Рекурсією називається алгоритмічна конструкція, де підпрограма викликає сама себе.

11. Динамічні змінні. Покажчики. Найпростіші динамічні структури даних. Використання динамічних структур даних.

Розрізняють звичайну (статичну) та динамічну організації пам’яті комп’ютера.

В оперативній пам’яті можна розмістити обмежену кількість даних, зокрема, змінних. Коли змінні оголошують у розділі var, система надає їм певний обсяг пам’яті, навіть якщо не всі змінні будуть використані у програмі. Пам’ять, надана змінним, вивільняється лише після виконання програми. Однак є задачі, де заздалегідь невідомо, скільки змінних потрібно для їхнього розв’язування, а отже, який обсяг пам’яті слід зарезервувати. У цьому випадку, а також, якщо заздалегідь знають, що даних буде багато, застосовують динамічну організацію пам’яті.

Принцип динамічної організації пам’яті полягає в тому, що змінні займають пам’ять за необхідністю, опрацьовуються і в потрібний момент вивільняють пам’ять – це так звані динамічні змінні. Вони характеризуються тим, що пам’ять для них виділяється протягом виконання програми і об’єм виділеної пам’яті може змінюватись під час виконання програми.

Для роботи з динамічними змінними використовують тип даних вказівник (покажчик) – це елемент даних програми, значенням якого є адреса. Якщо ім’я статичної змінної задає адресу даного в оперативній пам’яті, то вказівник на динамічну змінну – лише тип даного, а не його розташування в пам’яті. Тип даних вказівник описують за допомогою символу ^ у розділі type так:

type <назва типу> = ^ <базовий тип>;

Конкретні вказівники на динамічні змінні оголошують, як звичайно, у розділі var:

var <список вказівників на змінні>: <назва типу>;

Пам’ять для даних, про можливість появи яких попереджає вказівник, буде надана на етапі виконання програми за допомогою процедури new:

new (<вказівник на змінну>);

Тільки тепер утворилася динамічна змінна, ім’я якої має такий вигляд:

<вказівник на змінну> ^.

Розрізняють операції над вказівником на динамічну змінну та операції над самою динамічною змінною. З динамічною змінною можна виконувати операції, визначені для даних відповідного базового типу. Над вказівниками визначені дві основні операції: операція взяття адреси та операція розіменування покажчика (вказівника).

Після опрацювання динамічної змінної пам’ять можна вивільнити за допомогою процедури dispose:

dispose (<вказівник на динамічну змінну>);

Найпростіші динамічні структури даних є такі:

1) однозв’язний (однонапрямлений) лінійний список – це динамічна структура даних, кожен елемент якої містить вказівник на наступний елемент;

2) двозв’язний (двонапрямлений) лінійний список – це динамічна структура даних, кожен елемент якої містить вказівник на наступний і попередній елементи.

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

 стеку – це структура даних, у якій елемент, записаний останнім, зчитують (він є доступний до опрацювання) першим; принцип „останній прийшов – перший пішов”;

черги – це структура даних, у якій елемент, записаний першим, зчитують першим; принцип „перший прийшов – перший пішов”.

12. Списки. Стеки. Черги. Деревоподібні структури даних.

СТЕК в інформатиці та програмуванні -- різновид лінійного списку, структура даних, яка працює за принципом "останнім прийшов -- першим пішов". Всі операції (наприклад, видалення елементу) в стеку можна проводити тільки з одним елементом, який знаходиться на верхівці стеку та був введений в стек останнім. Стек можна розглядати як певну аналогію до стопки тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку.

Операції зі стеком

push ("заштовхнути елемент"): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміра стека граничної величини, відбувається переповнення стека (stack overflow)

pop ("виштовхнути елемент"): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні "виштовхнути" елемент з вже пустого стеку, відбувається ситуація "незаповнення" стеку (stack underflow)

Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стеку.

Додаткові операції (присутні не у всіх реалізаціях стеку):

isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли в стеку немає елементів.

isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе.

clear: звільнити стек (видалити усі елементи).

top: отримати верхній елемент (без виштовхування).

size: отримати розмір (кількість елементів) стека.

swap: поміняти два верхніх елементи місцями.

Організація в пам'яті комп'ютера

Стек може бути організований як масив або множина комірок в певній області комп'ютера з додатковим зберіганням ще й вказівника на верхівку стека. Заштовхування першого елемента в стек збільшує адресу вказівника, виштовхування елементу зменшує її. Таким чином, адреса вказівника завжди відповідає комірці масиву, в якій зараз знаходиться верхівка стеку. Багато процесорів ЕОМ мають спеціалізовані регістри, які використовуються як вказівники на верхівку стеку, або використовують деякі з регістрів загального вжитку для цієї спеціальної функції в певних режимах адресації пам'яті.

Приклади застосування

Калькулятори, які використовують зворотню польську нотацію, використовують стек для збереження даних обчислень.

Існує велика кількість "стеко-орієнтованих" мов програмування (Forth, PostScript), які використовують стек як базову структуру даних при виконанні багатьох операцій (арифметичних, логічних, вводу-виводу тощо).

Компілятори мов програмування використовують стек для передавання параметрів в процесі виклику підпрограм, процедур та функцій. Спеціалізований стек використовується також для збереження адрес повернення з підпрограм.

Черга в програмуванні — динамічна структура даних, що працює за принципом "перший прийшов - перший пішов". У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові. Така черга повністю аналогічна звичній "базарній" черзі, в якій хто перший встав в неї, той першим буде обслуженим (але, на відміну від реальної черги, імовірність пройти поза чергою виключена)

Основні операції з чергою

англ. enqueue — "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (англ. queue overflow).

англ. dequeue — "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповнення" (англ. queue underflow).

В програмуванні та комп'ютерних науках структури даних -- це способи організації даних в комп'ютерах. Часто разом зі структурою даних пов'язується і специфічний перелік операцій, які можуть бути виконаними над даними, організованими в таку структуру.

Правильний підбір структур даних є надзвичайно важливим для ефективного функціонування відповідних алгоритмів їх обробки. Добре побудовані структури даних дозволяють оптимізувати використання машинного часу та пам'яті комп'ютера для виконання найбільш критичних операцій.

Відома формула "Програма = Алгоритми + Структури даних" дуже точно виражає необхідність відповідального ставлення до такого підбору. Тому іноді навіть не обраний алгоритм для обробки масиву даних визначає вибір тої чи іншої структури даних для їх збереження, і навпаки.

Елементарні структури даних Масив,словник, лінійний список (Стек,черга,дек (двобічна черга), зв'язаний список)

Більш складні структури даних

Хеш-таблиця,Граф,Дерево (бінарне дерево, бінарне дерево пошуку, збалансоване дерево, B-дерево, AVL-дерево, Червоно-чорне дерево, Купа, Бінарна купа, Біномінальна купа, Фібоначчієва купа

13. Файлові типи. Операції з файлами. Файли прямого та послідовного доступу. Створення, читання та модифікація файлів.

Файлова структура служить для збереження у зовнішній пам 'яті різноманітної інформації і організації швидкого доступу до неї.

"Файл " — це сукупність байт, яка розміщена на диску (магнітному, оптичному...), має власне ім'я і приймається як єдине ціле."Ім 'я файла" складається з назви і типу файла.

"Назва файла" у Windows може мати до 255 англійських, російських і українських (крім і, є, ї, г) літер і арабських цифр, а також майже всі розділові і спеціальні знаки (_ 5 # & @ 1 % () {} ' ~ ^Л), крім / \: *? " о |.

За допомогою назви вказується призначення файла, за допомогою розширення встановлюється тип файла.

Серед типових розширень, наприклад, такі:

.txt — текстові файли;.doc—текстові документи Word;

.bat — командні файли;.xls — табличні документи Excel;

.com,.exe — програми;.bmp — графічні документи Paint;

Файлові змінні В програмі файли представляються спеціальними змінними – файловими. Ця змінна є свого роду буфером між конкретним файлом на диску, з яким вона зв’язана, і програмою. Одна і та ж змінна може бути зв’язана із різними файлами, але не одночасно.

В залежності від способу структурування даних в Pascal відрізняють три види файлів і файлових змінних: 1.Типізовані. 2. Текстові. 3. Безтипові.

Типізовані файли містять структури даних однакового типу: скалярні типи або складені. Наприклад Файл дійсних чисел є послідовністю елементів із шести байт, що відповідають дійсним числам.

Файл записів – послідовність структур, що відповідають певному комбінованому типу. Наприклад 321 байт.

Текстові файли можна вважати файлами ASCII-форматами. Елементами текстових файлів є рядки (послідовності символів: букв, цифр, знаків та пропусків). Такий файл можна створювати та редагувати за допомогою текстового редактора. Розмежовувачем між елементами файлу є пропуск. Уведення кожного рядка закінчується натисканням на клавішу вводу. Для перевірки чи є символи у рядку використовують функцію

eoln <ім’я файлу>, яка приймає значення TRUE, якщо знайдено кінець рядка.

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

Перед використанням операції над файлом, він повинен бути відкритим. Після завершення операції із файлом для звільнення для файлової змінної його потрібно закрити.

Для роботи із файлами використовуються наступні встановлюючі та завершальні процедури.

Процедура зв’язування певної файлової змінної із конкретним файлом на диску ASSIGN (<файлова змінна>,’<ім'я файла>’);

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

Тип фактичної файлової змінної, що використовується в процедурі assign означає вид і тип файлу.

Процедуравідкриттяфайлудлячитання RESET(<файлова змінна>);

Файлова змінна може бути будь-якого типу. При цьому, якщо файлу на диску ще нема, то виникає помилка програми. Відкрити для читання можна лише існуючий файл. При відкритті спеціальний файловий вказівник переміщується.

Процедуравідкриванняфайлудлязапису REWRITE(<файлова змінна>);

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

Процедуразакриванняфайлу CLOSE(<файлова змінна>);

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

Закриття файлу при запису призводить до фізичного запису файлу на диск.

Після закриття файлова змінна звільняється і може бути використана для зв’язування для інших файлів. Закритий файл можна знову відкрити в новому режимі.

Процедурапримусовогоочищеннявнутрішньогобуфераобміну

FLUSH (<файлова змінна>) Здійснює скидання у файл останніх записуваних даних, але не закриває файл. При використанні flush можна перевідкрити файл для читання без його закривання після режиму запису;

Процедура додавання даних APPEND(<файлова змінна>);

На відміну від звичайних файлів у текстовий файл можна додавати дані. Цю процедуру тоді використовують замість процедури REWRITE.

Для того, щоб знайти необхідний елемент файлу, необхідно послідовно переглянути всі попередні. Це називається послідовним доступом до файлу.

Окрім файлів послідовного доступу можна створювати і опрацьовувати файли прямого доступу. Відмінність така: перед використанням команд READ чи WRITE слід забезпечити доступ до k-го елемента файлу за допомогою команди: Seek (<назва файлу,k>).

14. Модульне програмування в системі ТР. Класифікація модулів. Загальна структура модуля користувача. Використання модулів.

Структурне програмування передбачає розділення алгоритмів на підалгоритми і програм на підпрограми. Такий поділ здійснюється не простим розділенням тексту програми на куски, а на логічно завершені цілісні компоненти. Об'єднання таких компонентів забезпечує об'єднання дій.

В Pascal модулі є окремими програмними одиницями, але не самостійно виконуваними. Окремі їх компоненти використовуються головними програмами або іншими зовнішніми модулями.

Всі модулі, що використовуються однією програмою або іншими модулями повинні бути оголошені USES <ім'я модуля>;

Як вже відмічалося модуль подібний до Pascal-програми, але є певні відмінності. В модулях виділяють чотири розділи:

1. Заголовок. UNIT <ім'я модуля>;

На відмінну від програм, заголовок модуля є обов’язковим. Ім'я модуля повинно співпадати з іменем відповідного *.pas-файлу, що містить текст модуля (8 букв).

2. Інтерфейсна частина. ІNTERFACE. В розділі інтерфейс оголошуються всі компоненти модуля, структура яких і самі вони мають бути „видимими” зовнішнім програмам, що використовують цей модуль.

В інтерфейсі можуть оголошуватися: uses- специфікація всіх модулів, що використовуються даним модулем; константи; типи; мітки; змінні; заголовки підпрограм. Всі перелічені компоненти будуть доступними, тобто „видимими” іншим програмам.

3. Розділ реалізації. В реалізації описуються всі компоненти мови, які мають бути невидимі зовні.

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

При описі реалізації підпрограм в цьому розділі може задаватися лише скорочений заголовок без списку формальних параметрів.

Модуль Crt містить ряд програм, які представляють можливість програмам, які працюють під DOS, ефективно управляти такими характеристиками персонального комп’ютера, як режим екрану, розширені коди клавіатури, кольору, вікна і звукові сигнали

Щоб використовувати модуль Crt, його ім'я потрібно вказати в операторі USES вашої програми: Uses CRT;

ЗМІННІ МОДУЛЯ CRT В модулі Crt визначений ряд констант і змінних, які призначені для управління екраном, клавіатурою, кольором та ін.

Модуль Dos містить ряд підпрограм для роботи з файлами і доступ до засобів операційної системи. Не одна з програм модуля Dos не визначена в стандартному Pascal, тому вони поміщені в окремий модуль.

Щоб використовувати підпрограми, які знаходяться в модулі Dos, його ім'я необхідно вказати в операторі USES на початку програми: USES Dos;

Процедури і функції модуля Dos можна уявно розбити на наступні групи: Функції управління операційним середовищем. Процедури управління процесами. Процедури обслуговування переривань. Процедури роботи з датою і часом. Процедури і функції перевірки стану диску. Процедури і функції роботи з файлами. Процедури і функції різного призначення.

ФУНКЦІЇ УПРАВЛІННЯ ОПЕРАЦІЙНИМ СЕРЕДОВИЩЕМ Програма, написана на мові Pascal 7.0 має можливість отримувати від MS-DOS інформацію про оточення (environment). Кожний опис в області оточення представляє собою рядок виду: Ім'я = Значення

Ім'я – це ім'я змінної, Значення – текстовий рядок.

Для того щоб встановити змінну оточення, використовується команда операційної системи SET, наприклад: SET COMSPEC=C:\DOS\COMMAND.COM;

ПРОЦЕДУРИ УПРАВЛІННЯ ПРОЦЕСАМИ

Використовуючи спеціальні засоби мови Pascal, можна організувати виклик з програми будь-якої іншої програми, яку називають програмою-нащадком. Виклик програми-нащадка відбувається за допомогою процедури Exec (Path, CmLine: STRING);

Параметр Path – це повний чи скорочений шлях до командного файлу і його ім'я, а CmLine – параметр, в якому можна передати викликаній програмі командний рядок.

ПРОЦЕДУРИ ОБСЛУГОВУВАННЯ ПЕРЕРИВАНЬ

Не дивлячись на те, що Турбо Паскаль має великий набір інструментальних засобів для використання можливостей MS-DOS, в багатьох випадках виникає необхідність прямого звертання до функцій MS-DOS для використання деяких специфічних засобів операційної системи, для організації обміну інформацією в оперативній пам'яті. Для більш повного використання можливостей MS-DOS в модулі DOS знаходиться дві процедури: Intr і MsDos.

В процедурі Intr (IntNo: BYTE; VAR Regs: REGISTERS); яка виконує задане програмне переривання, IntNo – номер програмного переривання; REGISTERS являється типом запису Процедура MsDos (VAR Regs: REGISTERS); виконує виклик функції DOS.

Процедури роботи з датою і часом. Для доступу до системної дати використовують процедури GetDate і SetDate.

15. Об’єктно-орієнтоване програмування як засіб створення складних програм. Поняття обєкта. Мова Object Pascal.

Об’єктно - орієнтоване програмування створене для опису складних програм.

Ідея об’єктно - орієнтованого програмування полягає в інкапсуляції (об’єднанні) даних і засобів їх опрацювання (методів) у тип, який називається класом. Конкретною змінною певного класу і є об’єкт.

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

Прикладами об’єктів можуть бути елементи керування у вікні: кнопки, списки, текстові поля тощо.

Мова програмування Object Pascal ґрунтується на використані наступних основних принципів:

v Інкапсуляції;

v Наслідування:

v Поліморфізму.

Інкапсуляція – це комбінування даних із процедурами та функціями, які ці дані використовують. У результаті такого об’єднання отримують нову структуру даних, яка називається об’єктом.

Наслідування – означає можливість побудови ієрархії об’єктів, в якій новий рівень ієрархії використовує можливості існуючих рівнів.

В побудованій ієрархічній структурі кожен породжений об’єкт має право доступу до об’єкта породжуючого.

Поліморфізм – визначає можливість визначення єдиної по імені дії (процедури чи функції), яку можна використати одночасно до всіх об’єктів у ієрархічному ланцюжку.

В мові Object Pascal для опису об’єкта використовується наступна синтаксична конструкція:

Type < ім’я типу > =object

< опис елемента даних >;

< опис заголовків підпрограм >;

End.

Структура опису об’єкта аналогічна структурі опису запису.

Елементи даних називають полями, а підпрограми називають методами.

Методи відображають властивості об’єкта.

Конкретну змінну об’єктного типу називають екземпляр типу (екземпляром класу).

Оголошується екземпляр типу за правилом:

Var <ім’я змінної >:<ім’я об. типу>