7. Зв'язаний список, у якому елементи додаються та вилучаються з голови, реалізує магазин (стек). Написати модуль pоботи зі стеком, що подається зв'язаним списком. У модулі мають бути пiдпpогpами

1) ініціалізації порожнього стека;

2) скидання стека (вилучення всіх його елементів);

3) обчислення кількості елементів стека;

4) перевірки поpожньості стека;

5) додавання елемента з початку стека;

6) добування й вилучення елемента з початку стека.

8. Чергою є список, у якому елементи вилучаються на початку, а додаються в кінці. Зв'язаний список, у якому перший елемент є наступним за останнім, називається циклічним. Найчастіше такий список ідентифікується вказівником на останній елемент. Написати модуль роботи з чергою, поданою циклічним зв'язаним списком. У модулі мають бути пiдпpогpами

1) ініціалізації порожньої черги;

2) скидання черги (вилучення всіх її елементів);

3) обчислення кількості елементів черги;

4) перевірки поpожньості черги;

5) додавання елемента в кiнці черги;

6) добування й вилучення елемента на початку черги.

9. Над множинами означено такі опеpації:

- перевірка належності елемента множині;

- перевірка порожньості множини;

- додавання й вилучення елемента;

- читання й друкування елементів множини.

Написати модуль, що реалізує поняття "множини цілих". Для подання множини застосувати

а) зв'язаний список; б) упорядкований за зростанням зв'язаний список.

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

а) об'єднання; б) пеpетину;

в) pізниці; г) симетричної різниці.

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

11. Відповідність задається двома множинами A, B та підмножиною R їхнього декартового добутку A? B (множиною пар). Над множинами пар означено такі опеpації:

- перевірка належності елемента множині пар;

- перевірка порожньості множини пар;

- додавання та вилучення елемента (пари);

- читання та друкування елементів множини пар.

Написати модуль, що реалізує поняття "відповідності множин цілих". Для подання множини пар застосувати

а) зв'язаний список пар;

б) "список списків": кожний елемент a множини A зберігається у зв'язаному списку разом із вказівником на голову списку таких елементів b множини B, що пара (a, b) належить R.

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

а) об'єднання; б) перетину; в) композиції.

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

13. Відношенням на множині A називається підмножина декартового добутку A? A. Написати програму читання відношення на множині цілих і перевірки, чи є воно

а) рефлексивним; б) симетричним; в) антисиметричним; г) транзитивним;

д) еквівалентністю; е) лінійним порядком; є) решіткою.

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

14. Результат лижника у перегонах задається трійкою цілих: його стартовим номером та кількістю хвилин і секунд. Написати програму читання результатів лижників і друкування їх у порядку неспадання часу.

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

4. Списки як рекурсивні об'єкти

Нехай a позначає довільний елемент множини A. Списки її елементів можна означити рекурсивно, а саме:

порожній список <> є списком;

якщо <L> позначає список, то < a <L> > також є списком.

За цим означенням список складається з головного елемента й підсписку, який сам є списком. Відтворимо рекурсивну природу списків означенням типу зв'язаних списків елементів типу T :

type Plist = ^List;

List = record

v : T; subl : Plist

end

Список ідентифікується вказівником на його головний елемент. Але й кожний наступний елемент, ідентифікований полем subl попереднього, вважається головним елементом підсписку. Порожній список указується значенням nil. Виразимо рекурсивно обробку списку за допомогою обробки головного елемента й підсписку, вважаючи для визначеності, що T = integer.

Перевірку належності елемента списку задає рекурсивна функція

function isinr ( a : integer; lp : Plist ) : boolean;

begin

if lp = nil then isinr := false else

{ обробка голови }

if a = lp^.v then isinr := true else

{ рекурсивно перевірити належність елемента підсписку }

isinr := isinr ( a, lp^.subl )

end

Далі ми запишемо рекурсивну функцію addordr додавання елемента в упорядкований список зі збереженням його упорядкованості та повернення вказівника на список, у який вставлено елемент. Але спочатку напишемо функцію newelemr, подібну процедурі newelem з підр.16.3. На відміну від тієї процедури, вказівник на новий елемент повертається з неї.

function newelemr(p : Plist; z : integer) : Plist;

var pp : Plist;

begin

new(pp); pp^.subl:=p; pp^.v:=z;

newelemr:=pp

end;

Наведена функція використовується в функції addordr:

function addordr ( a : integer; lp : Plist ) : Plist;

var p : Plist;

begin

if (lp = nil) or (a < lp^.v) then

{список, ідентифікований lp, стає підсписком }

{ за новим головним елементом }

addordr := newelemr ( lp, a );

else

begin { рекурсивно додати елемент до підсписку }

lp^.subl := addordr ( a, lp^.subl );

addordr := lp

end

end

Рекурсивна функція delr задає вилучення елемента, що подає задане значення, зі списку та повернення вказівника на список, у якому значення a відсутнє:

function delr ( a : integer; lp : Plist ) : Plist;

begin

if lp = nil then delr := nil

else

if lp^.v = a then

{ обробка голови }

begin

delr := lp^.subl; dispose ( lp )

end

else

{ рекурсивно вилучити елемент із підсписку }

begin

lp^.subl := delr ( a, lp^.subl ); delr := lp

end

end

Як бачимо, наведені рекурсивні підпрограми простіші для розуміння та коротші