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 встановлюється на ділянку вільної пам'яті розміром у
num*sizeof(Longint) = 16383*4 = 65532
|
Скачати "Реферат на тему Використання вільної пам'яті"
