Динамічні структури даних. 1. Засвоєння принципів роботи з динамічними структурами даних

Мета роботи:

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;

Розробка програми завершена і її можна запустити на виконання.