Мета роботи:
1. Засвоєння принципів роботи з динамічними структурами даних.
2. Практичні навички розроблення алгоритмів і програм для роботи зі списками, чергами, стеками і деревами.
Завдання:
1. Задано текст, в якому є круглі дужки. Розробити програму, яка перевіряє збалансованість дужок у заданому тексті. Якщо дужки збалансовані, то для кожної пари виводить їх номери позицій у тексті за зростанням номерів дужок, що закриваються. Якщо дужки не збалансовані, то виводить повідомлення про це.
2.Розробити програму, яка створює список 
, елементами якого є цілі числа. Розміщує в оберненому порядку всі елементи між першим і останнім входженням заданого елемента 
, якщо входить у не менше двох разів, інакше список залишається без змін. Виводить модифікований список.
3.Розробити програму, яка створює список , елементами якого є цілі числа. Вилучає із списку всі від’ємні елементи і розміщує їх у кінець списку в оберненому порядку до їх розміщення. Виводить модифікований список.
4.Розробити програму, яка створює бінарне дерево 
, елементами якого є цілі числа, знаходить і друкує всі його від’ємні елементи по рангах.
5. Розробити програму, яка створює списки 
і 
, елементами яких є слова із великих латинських літер. Знаходить всі слова списку , що не містяться у , і виводить їх, розділюючи пробілами, в оберненому порядку до їх розміщення.
6.Розробити програму, яка створює список , елементами якого є цілі числа і дописує в кінець цього списку всі елементи в оберненому порядку до їх розміщення в (тобто будується симетричний список, наприклад, 1,2,3,3,2,1). Виводить отриманий список.
7. Розробити програму, яка створює список , елементами якого є цілі числа. Для заданих чисел 
, 
виводить в порядку розміщення всі числа списку менші від , потім всі числа з діапазону 
і, нарешті, всі числа більші від . (Список переглядається тільки один раз).
8. Розробити програму, яка створює список , елементами якого є дійсні числа. Перетворює список так, щоб спочатку розміщувалися всі невід’ємні елементи зі збереженням порядку їх розміщення, а потім всі від’ємні в оберненому порядку. Виводить модифікований список.
9. Розробити програму, яка створює бінарне дерево , елементами якого є цілі числа і знаходить довжину (кількість віток) шляху від кореня до найближчої вершини з елементом .
10. Розробити програму, яка створює списки , , 
, елементами яких є цілі числа. Замінює перше входження списку в список (якщо таке є) на список . Виводить модифікований список .
11. Розробити програму, яка створює список , елементами якого є дійсні числа. Перетворює список за правилом: якщо числа упорядковані за неспаданням 
, то список залишається без зміни, інакше елементи у списку розміщуються в оберненому порядку 
. Виводить модифікований список.
12. Розробити програму, яка створює список , елементами якого є дійсні числа. Обчислює добуток 
і друкує значення добутку та всі елементи списку . (Для розв’язування задачі доцільно використати двозв’язний список).
13. Розробити програму, яка створює список , елементами якого є дійсні числа 
.Будує список, елементами якого є числа 
, . Виводить одержаний список.
14. Розробити програму, яка створює списки і , елементами яких є цілі числа (елементи у списку упорядковані за неспаданням, а у списку розміщені довільно). Вставляє елементи списку у так, щоб залишився упорядкованим. Виводить модифікований список .
15. Розробити програму, яка створює список , елементами якого є малі латинські літери. Виводить за алфавітним порядком всі літери, що входять у список по одному разу, по декілька разів і не входять жодного разу.
16. Розробити програму, яка створює бінарне дерево , елементами якого є дійсні числа, і обчислює добуток елементів цього дерева.
17.Задано текст, в якому є круглі дужки. Розробити програму, яка перевіряє збалансованість дужок у заданому тексті. Якщо дужки збалансовані, то для кожної пари виводить їх номери позицій у тексті за зростанням номерів дужок, що відкриваються. Якщо дужки не збалансовані, то виводить повідомлення про це.
18.Розробити програму, яка створює список , елементами якого є символи. Вилучає із списку всі повторні входження кожного символу. Виводить модифікований список.
19.По кругу розміщаються 
дітей. Відлік починається від першого і кожний 
-ий вилучається, а круг змикається. Розробити програму, яка визначає порядок вилучення дітей із круга.
20. Розробити програму, яка створює бінарне дерево , елементами якого є дійсні числа і знаходить найбільший та найменший елементи дерева .
21. Розробити програму, яка створює списки і , елементами яких є слова із великих латинських літер. Знаходить всі слова списку , що містяться в , і виводить, розділюючи їх пробілами, в оберненому порядку до їх розміщення.
22. Розробити програму, яка створює бінарне дерево , елементами якого є дійсні числа. Підраховує середнє арифметичне всіх елементів дерева і виводить це значення та значення його елементів.
23. Задана без помилок символьна формула виду: <формула>::=<цифра>| М(<формула>,<формула>)|m(<формула>,<формула>; <цифра>::=0|1|2|…|9, де М, m – функції обчислення максимуму і мінімуму відповідно. Розробити програму обчислення значення заданої формули (наприклад, М(5,m(6.8))–> 6).
24.Розробити програму, яка створює бінарне дерево , елементами якого є дійсні числа, і визначає його максимальну глибину, тобто кількість віток у найдовшому шляху від кореня до листків.
25. Розробити програму, яка створює список , елементами якого є слова із великих латинських літер, знаходить і друкує, розділюючи пробілами, всі слова, що входять у список по одному разу.
26. Розробити програму, яка створює список , елементами якого є цілі числа. Вставляє у список перед кожним входженням елемента 
елемент 
. Виводить модифікований список.
27. Розробити програму, яка створює список , елементами якого є цілі числа. Вилучає із списку після кожного входження елемента наступний елемент і розміщує всі вилучені елементи на початок списку в порядку їх розміщення. Виводить модифікований список.
28. Розробити програму, яка створює бінарне дерево 
, елементами якого є дійсні числа, будує і виводить його копію 
.
29. Розробити програму, яка створює списки і , елементами яких є слова. Знаходить і вилучає із списку всі слова, що також містяться у списку . Виводить модифікований список, розділюючи слова пробілами.
30.Розробити програму, яка створює список , елементами якого є цілі числа 
. Знаходить у списку і друкує найдовший ланцюжок чисел, що задовольняють умову: 
Файли
Файл –це іменована область зовнішньої пам’яті, в якій розміщена послідовність даних. Файл має три характерні особливості:
· файла має ім’я;
· компоненти файла мають однаковий тип, це може бути будь-який тип, крім файлового;
· довжина файла обмежується тільки ємністю пристрою, на якому він розміщений.
За способом організації і доступом до компонентів файли можуть бути з послідовним методом доступу і прямим методом доступу. Для доступу до деякого компонента у послідовному файлі необхідно переглянути всі компоненти, розміщені перед ним. У файлі з прямим методом доступу будь-який компонент доступний безпосередньо.
Object Pascal підтримує три види файлів: текстові, типізовані і нетипізовані. Програма працює з логічним файлом, який на етапі її виконання зв’язується з реальним фізичним файлом. Логічний файл або файлова змінна описуються у програмі одним із трьох способів:
<ім’я>: TextFile:
<ім’я>: File of <тип>;
<ім’я>: File;
.
де TextFile – стандартний ідентифікатор типу для текстових файлів; File, of – зарезервовані слова і <тип> – тип компонентів для типізованого файла; нетипізований файл описується зарезервованим словом File. Наприклад,
Type Tanketa = record
Pib: string{25];
Rn: word;
Pos: string{15];
Zp; currency;
End;
Text80 = File of string{80];
Var F1: File of Char;
F2: TextFile;
F3: File;
F4: Text80;
F5: File of Tanketa;
тут F1, F4, F5 – типізовані файли; F2 – текстовий файл; F3 – нетипізований файл.
В Object Pascal немає засобів контролю виду створених файлів, тому програміст сам повинен слідкувати за відповідністю виду файла і описаною файловою змінною. Однак, будь-який файл можна відкрити як нетипізований і працювати з ним.
Файл стає доступним програмі після виконання процедури його відкриття, яка зв’язує файлову змінну з фізичним файлом і відкриває його для читання або записування.
Процедури доступу до файлів:
· Procedure AssignFile(Var F; FileName: String); – зв’язує файлову змінну F з іменем файла FileName. FileName – символьний вираз, що містить ім’я файла або шлях до файла;
· Procedure Reset(Var F: File [; RecSize: Word]); – відкриває існуючий файл. RecSize має зміст тільки для нетипізованих файлів і вказує розмір блоку даних. Відкритий текстовий файл можна тільки читати, а типізований і нетипізований як читати, так і записувати. При відкритті неіснуючого файла фіксується помилка. З відкритим файлом зв’язується покажчик, який вказує на компонент з номером нуль. У процесі роботи з файлом покажчик завжди вказує на компонент, який буде наступним читатися або записуватися. Переміщення покажчика здійснюється автоматично;
· Procedure Rewrite(Var F: File [; RecSize: Word]); – створює новий файл. RecSize має зміст тільки для нетипізованих файлів і вказує розмір блоку даних. Відкритий текстовий файл можна тільки записувати, а типізований і нетипізований як читати, так і записувати. При відкритті існуючого файла всі дані, які зберігалися у файлі, знищуються. Повідомлень про це у програму не надходить.
· Procedure CloseFile(Var F); – закриває файл, а зв’язок файлової змінної з іменем файла, встановлений раніше процедурою AssignFile, зберігається. При створенні нового або розширенні старого файла процедура забезпечує збереження у файлі всіх нових записів і регістрацію файла в каталозі. Процедура CloseFile виконується автоматично стосовно до всіх відкритих файлів при нормальному завершенні програми. Оскільки зв’язок файлової змінної з іменем файла зберігається, то файл можна повторно відкрити без додаткового використання процедури AssignFile.
Тепер розглянемо особливості текстових, типізованих і не типізованих файлів.
Текстовий файл – це послідовність символьних рядків різної довжини. В кінці кожного рядка записується ознака кінця рядка EOLN (послідовність кодів #13 і #10). У кінці файла записується ознака кінця файла EOF (код #26). Текстові файли дозволяють працювати з окремими символами, символьними рядками і числами (якщо символи є послідовністю цифр).
Текстові файли допускають тільки послідовний метод доступу, тому файл, відкритий процедурою Reset, можна тільки читати, а відкритий процедурою Rewrite – тільки записувати.
Ознаки кінця рядка і кінця файла тестуються функціями Eoln, Eof, SeekEoln, SeekEof.
Обмін даними з текстовим файлом здійснюється процедурами Read, Readln, Write, Writeln.
Для того, щоб добавити записи у текстовий файл, його потрібно відкрити процедурою Append.
Типізований файл– це послідовність компонентів чітко визначеного типу (символ, число, масив, множина, запис та інше). Типізований файл – це файл прямого методу доступу, тобто доступ до компонента здійснюється за його порядковим номером.
Обмін даними з типізованим файлом здійснюється процедурами Read і Write.
Нетипізований файл– це послідовність компонентів невизначеного типу. Відсутність типу робить ці файли, з одного боку, сумісними з будь-якими іншими файлами, а з другого – дозволяє організувати швидкісний обмін даними між диском і пам’яттю. Нетипізовані файли є файлами з прямим методом доступу.
Обмін даними з нетипізованими файлами здійснюється процедурами BlockRead і BlockWrite.
При роботі з типізованими і нетипізованими файлами використовується процедура Seek, яка встановлює покажчик файла F на N-ий компонент (перший компонент файла має номер 0) і функції: FileSize – повертає кількість компонентів файла; FilePos –– повертає поточну позицію покажчика у файлі, тобто номер компонента, який буде оброблятися наступною операцією введення-виведення.
Типізовані і нетипізовані файли є файлами з прямим методом доступу і при їх відкритті покажчик вказує на компонент з нульовим номером. Після виконання кожної операції читання або запису покажчик буде вказувати на наступний запис. Переміщення покажчика здійснюється автоматично.
Докладно процедури і функції для роботи з файлами описані у додатку.
Приклад.Розробити програму, яка: а) створює текстовий файл TF_1 із символьних рядків різної довжини; б) читає вміст файла TF_1, формує рядки по 10 символів, вставляє перед кожним рядком п’ятизначний номер (1 ¸ 99999), відділяючи його пробілом і записує у файл TF_2; в) читає вміст файла TF_2 і друкує його по рядках.
Для розв’язання задачі командою File|New Application створимо новий проект. Присвоїмо формі заголовок Caption = Текстовий файл і програмне ім’я Name = FT. Командою File|Save All запишемо програмний модуль під іменем ULAB12_1.pas, а проект – LAB12_1.dpr.
Рис. 12.1. Форма Текстовий файл
На формі розмістимо два компоненти Memo (багаторядковий редактор). Один для введення початкових даних і другий для виведення результатів. Присвоїмо їм програмні імена Memo1, Memo2 (властивість Name) і значення властивості ScrolBars=ssBoth (горизонтальне і вертикальне прокручування ). Двічі клацнувши мишкою в полі значення властивості Lines цих компонентів, ввійдемо в редактор і очистимо значення цієї властивості.
Крім цього, розмістимо на формі дві кнопки керування (компонент Button) і встановимо їм значення властивостей Caption і Name. Першій – Caption = Виконати, Name = Button1, а другій – Caption = Вихід, Name = Button2 (Рис. 12.1).
Тепер напишемо обробники кнопок керування Виконати і Вихід.
В обробнику кнопки Виконати процедурою AssignFile файлові змінні f1, f2 зв’язуються з файлами TF_1 і TF_2. Процедурою Rewrite(f1) файл TF_1 відкривається для записування. Введені у вхідний набір Memo1.Lines символьні рядки переписуються у файл TF_1 і процедурою CloseFile (f1) він закривається. Потім файл TF_1 відкривається для читання, а файл TF_2 для записування. Читається вміст файла TF_1, формується рядок із номера і десяти чергових символів, який записується у файл TF_2. Потім вміст файл TF_2 виводиться у вихідний набір Memo2.Lines.
В обробнику кнопки Вихід виконується метод Close.
{Обробник кнопки Виконати}
procedure TFT.Button1Click(Sender: TObject);
var f1, f2: TextFile;
s: string;
c: char;
n, i, j: integer;
begin
{Зв’язування файлових змінних з файлами на диску}
AssignFile (f1, 'TF_1');
AssignFile (f2, 'TF_2');
{Відкриття файла TF_1 для запису}
Rewrite(f1);
{Створення файла TF_1 }
n:=Memo1.Lines.Count;
for i:=0 to n-1 do
begin
s:=Memo1.Lines[i];
writeln(f1, s);
end;
{Закриття файла TF_1 }
CloseFile (f1);
{Відкриття файла TF_1 для читання}
Reset (f1);
{Відкриття файла TF_2 для запису}
Rewrite (f2);
{Створення файла TF_2 }
i:=0;
while not eof(f1) do
begin
i:=i+1;
write(f2, i:5, ' ');
j:=1;
while (j<=10) and (not eof(f1)) do
if eoln(f1) then readln(f1)
else begin j:=j+1; read(f1, c); write(f2, c); end;
writeln(f2);
end;
{Закриття файлів }
CloseFile (f1);
CloseFile (f2);
{Відкриття файла TF_2 для читання}
Reset (f2);
{Виведення вмісту файла TF_2}
while not eof(f2) do
begin
readln(f2, s);
Memo2.Lines.Add(s);
end;
CloseFile (f2);
end;
{Обробник кнопки Вихід}
procedure TFT.Button2Click(Sender: TObject);
begin
Close;
end;
Розробка програми завершена і її можна запустити на виконання.
