Лекція № 18
Тема: Списки як динамічна структура даних
План заняття:
Динамічна структура даних
Вставлення елемента в список
Вилучення елемента зі списку
Шукання елемента списку
Динамічна структура даних
Розглянуті рядки символів, зображені у вигляді ланцюгів, тобто як динамічна структура, є частковим випадком такої структури - лінійного однонапрямленого списку. Різниця полягає в тому, що коли для рядків інформаційними елементами можуть бути тільки значення типу char, то в загальному випадку списків елементами можуть бути значення довільного типу - як прості, так і складені. Однак з метою уніфікації під час опрацювання списку вважатимемо, що всі елементи є значеннями одного типу.
Схематично однонаправлений список показаний на рис. 1.
……
Рис. 1. Однонаправлений список.
За аналогією з динамічними рядками тут визначено вказівник Sp, який вказує на весь список як на єдину структуру, а також нульову ланку, у якій вказівник вказує на перший елемент.
Недоліком однонапрямлених списків є те, що рухатись по такому списку можна тільки в одному напрямі - від початку до кінця. Немає змоги природним способом, без значного ускладнення алгоритму, перебирати елементи у зворотному напрямі.
Тому введемо нову динамічну структуру - двонаправлений список. Для цього в кожній ланці списку додамо ще по одному полю. Значенням цього поля буде вказівник на попередню ланку списку. Оскільки кожна ланка зображена як запис, то в цей запис відповідно додамо ще одне поле. Тоді структуру ланки опишемо таким списком типу:
type
TypeElm=Char;
Link=^Lanka;
Lanka=record
Elem: Char;
Next: Link;
Predd: Link;
end;
Така структура схематично зображена на рис. 2.
Sp
……….
Рис. 2.Двонаправлений список.
Як видно з рис. 2, у полі Predd нульової ланки, як і в полі Next останньої ланки, вказівник має значення nil, що відповідає ситуації, коли нульова ланка не має попередньої, а остання - наступної.
Варіантом двонапрямлених є кільцеві списки, їх утворюють на базі двонапрямлених, якщо вказівній змінній у полі Next останньої ланки присвоїти значення вказівника, що вказує на початок, тобто на нульову ланку, а в полі Predd нульової ланки - значення вказівника, що вказує на останню ланку. Тобто одержимо кільцеву структуру (рис. 3).
Над списками визначені ті ж самі операції, що й над динамічними рядками, тобто пошук елемента в списку, Вставка елемента у визначене місце і вилучення зі списку.
Sp
……..
Рис. 3. Кільцевий список.
Вставка елемента в список
Вставка елемента в список виконують за алгоритмом, що подібний до вставки символу в рядок. Процедура вставки має два формальні параметри: перший - елемент, який вставляють, і другий - вказівку на ланку, після якої вставляють елемент:
program Form5;
type
TypeElm=Char;
Link=^Lanka;
Lanka=record
Elem: Char;
Next: Link;
Predd: Link;
end;
procedure lnList(Elm: TypeElm; LanLst: Link);
var Rb: Link;
begin
New(Rb);
Rb^.EIem:=Elm;
Rb^.Next:=LanLst^.Next;
Rb^.Predd:=LanLst^.Next^.Predd;
LanLst^.Next:=Rb;
LanLst^.Next^.Predd:= Rb;
end;
begin
end.
Тут Elm- елемент, який вставляють, LanLst- вказівник на ланку, після якої виконують вставку.
Вилучення елемента зі списку
Для цього треба змінити вказівку в полі Next попередньої ланки і в полі Predd наступної після тої, яку вилучають. Доцільно ланку, елемент якої вилучають, знищити:
program Form6;
type
TypeElm=Char;
Link=^Lanka;
Lanka=record Elem: Char; Next: Link; Predd: Link;
end;
procedure OutList(LanLst:Link);
begin
LanLst^.Next^.Predd:=LanLst^.Predd;
LanLst^.Predd^.Next:=LanLst^.Next;
Dispose(LanLst);
end;
begin
end.
Тут значення LanLst вказує на ланку, яку вилучають.