Сторінка
3
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 Як бачимо, наведені рекурсивні підпрограми простіші для розуміння та коротші від їх нерекурсивних аналогів з попереднього підрозділу. Проте вони виконуються практично вдвічі довше за рахунок заглиблення в рекурсію та повернення з неї. Крім того, для виконання кожного рекурсивного виклику потрібна нова ділянка автоматичної пам'яті. Але ця пам'ять обмежена, а її "переповнення" веде до аварійного завершення виконання програми. Таким чином, може статися, що максимальна глибина рекурсії залежить зовсім не від довжини списку, а від розмірів автоматичної пам'яті. Отже, наведені алгоритми мають скоріше теоретичний, ніж практичний інтерес. Принаймні, ми не можемо рекомендувати їх до практичного застосування.
5. Великі масиви у вільній пам'яті Подання послідовностей даних списками є досить гнучким. Особливо зручним воно є у випадках, коли дані додаються та вилучаються в процесі виконання програми. Але воно призводить до неефективного використання пам'яті, особливо коли дані, записані в елементах списку, невеликі за розміром. Справді, кожний елемент послідовності потребує додатково 4 байти під вказівник, або навіть 8, коли список двозв'язаний. Крім того, доступність елемента залежить від його розташування в списку. Відсутність прямого доступу до елементів створює незручності програмування і в багатьох випадках веде до того, що при виконанні програми пошук елемента стає занадто довгим. Існує багато задач, в яких вимагається швидкий пошук значень і не потрібна гнучкість спискового подання. Прикладами є задачі наступних розділів. Там, як правило, не треба додавати чи вилучати довільні елементи з послідовності. Використання масивів там набагато зручніше. Система Турбо Паскаль має обмеження на розміри як статичної, так і автоматичної пам'яті, що надається програмі. Тому у випадках, коли потрібні масиви розміром, наприклад, у сотні тисяч байтів, слід зберігати їх у вільній пам'яті, адже її обсяг залежить головним чином від обсягу наявної оперативної пам'яті комп'ютера. Розглянемо засоби системи Турбо Паскаль, за допомогою яких зручно задавати обробку масивів у вільній пам'яті. По-перше, корисними є функції MEMAVAIL і MAXAVAIL, з яких повертається загальний розмір незайнятої частини купи та найбільший розмір суцільної незайнятої ділянки (у байтах, типу Longint). Масив у купі повинен ідентифікуватися вказівником, установленим на його перший елемент. В означенні типу масиву головне – задати індекс і тип його першого елемента. Наприклад, type Arl=array[0 0]of longint. Далі означимо тип вказівника на такий масив: Parl=^Arl. Вказівник, який встановлюється на масив у купі, означається як безтиповий– він може мати значеннями адреси даних будь-яких типів і розмірів. Для цього в Турбо Паскаль є тип з іменем Pointer. "Захоплення" ділянки вільної пам'яті заданого розміру та встановлення безтипового вказівника на її перший байт задається процедурою GETMEM. Першим аргументом у її виклику є ім'я вказівника, другим – вираз типу Longint, що задає довжину ділянки в байтах. Наприклад, якщо var p : Pointer; num : word = 16383; то за виконання виклику
getmem(p, num*sizeof(Longint)) вказівник p встановлюється на ділянку вільної пам'яті розміром у
Завантажити реферат