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

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

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

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

)
end;
надрукувати елементи ss.
Умова задачі не обмежує кількість елементів у послідовності ss, тому для її зберігання масив непридатний. Скористаємося лінійним зв'язаним списком рядків у вільній пам'яті. Елементами списку є структури вигляду
Рядок Вказівник на наступний рядок
Вони утворюють послідовність, показану на рис.16.1.
Перший елемент називається головою списку. Поле-вказівник кожного (крім останнього) елемента списку ідентифікує наступний елемент, тобто "прив'язує" його до попереднього.
Якщо розірвати цей зв'язок, змінивши значення вказівника, то наступний елемент списку і всі за ним стають неідентифікованими і перетворюються на "сміття" у вільній пам'яті.
Наприклад, якщо вказівник у першому елементі списку встановити не на другий елемент, а на якусь іншу ділянку пам'яті (пунктирна стрілка на рис.16.1), то на другий елемент (і всі за ним) вже немає посилань. А якщо на щось немає посилань, то його ніби й немає.
За останнім елементомсписку немає наступного, тому його вказівник установлений на "ніщо".
Для ідентифікації першого елемента (і списку як структури в цілому) потрібен окремий вказівник, означений у програмі й розташований у її статичній або автоматичній пам'яті. Його називають вказівником на голову списку.
Розглянемо означення та операції, за допомогою яких створюється та обробляється лінійний список. По-перше, нам потрібен тип для елементів лінійного списку. Очевидно, вони являють собою структури, одне з полів яких є вказівником на значення цього самого типу структур. Таким чином, незрозуміло, який же тип слід означити спочатку - тип структур чи вказівників на них? Вихід із цього "замкненого кола" дає така властивість мови Паскаль:
означення типу ^T вказівників дозволяється записувати вище від означення самого типу T.
Ця властивість мови грунтується на тім, що вказівники будь-якого типу мають той самий розмір.
Отже, означимо спочатку тип Tple вказівників, а потім тип елементів Tle зв'язаного списку рядків. Нехай str є ім'ям типу рядків у таких означеннях:
type TPle = ^Tle;
Tle = record
v : str; next : TPle
end
Якщо вказівник p типу TPle установлений на деякий елемент списку, то його можна позначити p^. Вирази p^.v і p^.next задають відповідно змінні типів str та Tple - їх значеннями є рядок, що зберігається в елементі списку, і адреса наступного елемента.
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 вставляється після елемента
Loading...

 
 

Цікаве