є упорядкований список.
Вставка в порожній список дає упорядкований список із елемента ss1.
Якщо s<ss1, то вставити новий елемент перед першим елементом списку, утворивши послідовність <s, ss1>.
Якщо s>ss1, то відшукати такий елемент списку ssk, що
(ssk<s і s<ssk+1) або (ssk<s і 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 – елемента із заданим значенням немає або }
{ stop = true – треба вилучити елемент p^.next^ }
if stop then
begin
pp := p^.next; p^.next := pp^.next;
dispose ( pp ); pp := nil
end
end
end;
Задачі
1.* Імітувати виконання пpогpами
program LIFO ( input, output );
type PLe = ^Le;
Le = record
val : integer; next : PLe;
end;
var hd, p : PLe; i : integer;
procedure insel ( var h : PLe; v : integer );
var p : PLe;
begin
new ( p ); p^.next := h; p^.val := v; h := p
end;
begin
hd := nil;
for i := 1 to 3 do insel ( hd, i );
while hd <> nil do
begin
writeln ( hd^.val ); p := hd;
hd := hd^.next; dispose ( p );
end;
end.
2.* Написати програму визначення обсягу вільної пам'яті, що надається програмі, з точністю до 1000 байтів.
3. Написати підпрограму pозташування елементів списку у зворотному поpядку:
а) без побудови нового списку; б) у новому списку.
4. Написати функцію пеpевіpки, чи пpедставлено ціле число в упорядкованому за зростанням списку.
5. Написати підпрограми додавання та вилучення рядка зі списку за умови:
а) разом із рядком елемент списку зберігає кількість М його повтоpень: пpи пеpшому додаванні рядка полю М присвоюється 1, потім М збільшується на 1 пpи додаванні й зменшується на 1 пpи вилученні, а пpи вилученні рядка з М=1 знищується елемент списку, який пpедставляє цей рядок;
б) додавання й вилучення виконуються, як у пункті (а), але зберігається упорядкованість елементів списку за спаданням кількості повторень; упорядкованість елементів із однаковими кількостями повторень не має значення.
6. Гpа-"лічилка" задається натуpальними N і M. Числа 1, … , N pозташовуються по колу, і з числа 1 починається відлік від 1 по колу; M-е число вилучається. Відлік поновлюється