WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Використання вільної пам'яті - Реферат

Використання вільної пам'яті - Реферат

ssk.
Нехай результат лексикографічного порівняння рядків s1 і s2 обчислюється при виконанні виклику функції lt(s1, s2) - див. задачу 12.9.
Скористаємося процедурою створення нового елемента списку Newelem. Аргументами в її виклику є вказівник типу Tple та вираз типу str. За виконання її виклику створюється новий елемент списку, в його поля записуються значення аргументів, після чого аргумент-вказівник установлюється на цей елемент:
procedure newelem(var p : Tple; z : str);
var pp : Tple;
begin
new(pp); pp^.next:=p; pp^.v:=z; p:=pp
end;
З використанням цієї процедури наведений алгоритм уточнюється такою процедурою:
procedure addord ( s : str; var h : TPle );
var p, pp : TPle; stop : boolean;
begin
if h = nil then {Список порожній - створюється новий елемент }
newelem ( h, s ); {і стає головним}
else
if lt ( s, h^.v ) then { Вставка перед першим елементом - }
newelem ( h, s ) {новий елемент стає головним}
else
begin { Пошуки місця для вставки }
stop := false; p := h;
while ( p^.next nil ) and not stop do
if lt(s, p^.next^.v) then stop := true
else p := p^.next;
{ Вставка після елемента p^ за умови, }
{ що s не дорівнює p^.v }
if p^.v s then newelem ( p^.next, s );
end
end
Нехай ця процедура разом із допоміжними до неї міститься в модулі strlist. Як бачимо, вона задає вставку елемента після перевірки його відсутності в списку. Тоді в наступній програмі розв'язання задачі з умовою (2) функція isin не потрібна:
program namlist2(input, output);
uses strlist;
var pss : Tple; s : str;
begin
pss := nil; readln ( s );
while s '' do
begin
addord ( s, pss );
readln ( s )
end;
writelst ( pss )
end.
Упорядкований список можна створити іншим шляхом. Можна при читанні додавати елементи просто з голови списку, і лише після цього починати йогопереупорядкування. У розділі 17 ми розглянемо упорядкування послідовності за допомогою так званого злиття її упорядкованих частин в більші за довжиною упорядковані. Якщо доводиться читати багато значень і створювати довгий список, то такий спосіб вимагає в підсумку суттєво менше роботи, ніж наведене додавання зі збереженням упорядкованості.
3.4. Вилучення елемента зі списку
На прикладі списків рядків типу str розглянемо операцію вилучення елемента, який зберігає задане значення. Реалізуємо її згідно з алгоритмом:
1)Порожній список залишається без змін.
2)Якщо значення зберігається в голові списку, то достатньо перемістити вказівник із неї на наступний елемент і звільнити пам'ять, зайняту нею. Але внаслідок переміщення голова стає недоступною, тому спочатку треба встановити на неї допоміжний вказівник.
3)Якщо значення не зберігається в першому елементі, то треба переміститися по зв'язках списку до елемента A, наступний за яким B зберігає задане значення. Потім треба наступний за B елемент "прив'язати" до A та звільнити пам'ять, зайняту B. Якщо елемента із заданим значенням немає, то список не змінюється. Аналогічно п.2 перед розривом зв'язку з елементом B треба встановити на нього допоміжний вказівник.
Наведений алгоритм уточнюється процедурою del:
procedure del ( s : str; var h : TPle );
var p, pp : TPle; stop : boolean;
begin
if h nil then
if h^.v = s then
begin
pp := h; h := h^.next;
dispose ( pp ); pp := nil
end
else
begin
p := h; stop := false;
while ( p^.next nil ) and not stop do
if p^.next^.v = s then stop := true
else p := p^.next;
{ p^.next = nil - елемента із заданим значенням немає або }
{ stop = true - треба вилучити елемент p^.next^ }
if stop then
begin
pp := p^.next; p^.next := pp^.next;
dispose ( pp ); pp := nil
end
end
end;
4. Списки як рекурсивні об'єкти
Нехай a позначає довільний елемент множини A. Списки її елементів можна означити рекурсивно, а саме:
порожній список є списком;
якщо позначає список, то < a > також є списком.
За цим означенням список складається з головного елемента й підсписку, який сам є списком. Відтворимо рекурсивну природу списків означенням типу зв'язаних списків елементів типу 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 glob-1-8) then
begin
write(k:8, parl(p[k div num])^[k mod num]:8);
cnt:=cnt+1;
end;
if cnt=4 then begin writeln; cnt:=0 end;
end;
writeln;
writeln('вільна пам''ять : ', memavail,
'; найбільша ділянка : ', maxavail);
readln;
end.
Loading...

 
 

Цікаве