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

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

ГоловнаІнформатика, Компютерні науки → Адреси та вказівники - Реферат

Адреси та вказівники - Реферат

вказівники будь-якого типу мають той самий розмір.
Отже, означимо спочатку тип Tple вказівників, а потім тип елементів Tle зв'язаного списку рядків. Нехай str є ім'ям типу рядків у таких означеннях:
type TPle = ^Tle;
Tle = record
v : str; next : TPle
end
Якщо вказівник p типу TPle установлений на деякий елемент списку, то його можна позначити p^. Вирази p^.v і p^.next задають відповідно змінні типів str та Tple - їх значеннями є рядок, що зберігається в елементі списку, і адреса наступного елемента.
3.2. Найпростіші операції над списками
За допомогою введених означень почнемо уточнювати алгоритм (16.1). Подамо послідовність ss зв'язаним списком рядків. Для його ідентифікації означимо вказівник pss типу TPle.
Присвоювання ss := можна записати як pss := nil.
Опишемо додавання рядка s до послідовності ss. Найпростіший спосіб - додавати елемент з голови списку, тобто рядок ніби записується перед послідовністю. Для цього треба одержати ділянку вільної пам'яті під новий елемент списку, записати в нього новий рядок, "прив'язати" голову списку до нового елемента і зробити цей елемент головою:
procedure add ( s : str; var h : TPle );
var p : TPle;
begin
new ( p ); p^.v := s; p^.next := h; h := p
end
В результаті виконання процедури add у списку з'являється новий перший елемент, і вказівник h на голову списку змінюється. Тому він обов'язково повинен бути параметром-змінною. Оскільки послідовність представлено вказівником pss, саме він повинен бути аргументом у викликах цієї процедури: add ( s, pss ).
Для визначення належності s до ss треба рухатися по елементах списку від його початку доти, поки не натрапимо на елемент із рядком s або не дістанемось останнього елемента. Нехай h^ - черговий елемент списку. Умову переходу до наступного елемента в пошуках s можна виразити так:
( h^.next nil ) { черговий елемент не є останнім }
and
( h^.v s ) { і зберігає рядок, не рівний s }
Перехід до наступного елемента задає оператор h:=h^.next. Якщо послідовність порожня, то відповідь одержується тривіально. Отже, визначення належності s до ss задається функцією isin:
function isin ( s: str; h: TPle ) : boolean;
begin
if h = nil then isin := false
else
begin
while ( h^.next nil ) and ( h^.v s ) do
h := h^.next;
{ ( h^.next = nil ) or ( h^.v = s ) }
isin := ( h^.v = s )
end
end
Оскільки список починається елементом pss^, то виклик функції має вигляд isin(s, pss). Зміна вказівника h при виконанні процедури не міняє значення pss і не веде до втрати зв'язку з головою списку, оскільки h є параметром-значенням.
Рядки, представлені в списку, друкуються з його початку просуванням по елементах до кінця:
procedure writelst ( h : TPle );
begin
while h nil do
begin writeln ( h^.v ); h := h^.next end
end
Зберемо означення типів str, TPle, Tle та наведені підпрограми в модуль strlist, і запишемо розв'язання задачі (1) у вигляді програми namlist1:
program namlist1(input, output);
uses strlist;
var pss : TPle; s : str;
begin
pss := nil; readln ( s );
while s '' do
begin
if not isin ( s, pss ) then add ( s, pss );
readln ( s )
end;
writelst ( pss )
end.
3.3. Додавання до упорядкованого списку
Розглянемо тепер задачу про друкування прізвищ із умовою (2), тобто в лексикографічному порядку. Нехай знак 1 і aiРозглянемо таке додавання нового рядка s до упорядкованого списку ss, що його результатом є упорядкований список.
Вставка в порожній список дає упорядкований список із елемента ss1.
Якщо sЯкщо s>ss1, то відшукати такий елемент списку ssk, що
(sskВ обох цих випадках s вставляється після елемента 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 - елемента із
Loading...

 
 

Цікаве