Посилання та покажчики

Мета: вивчення фундаментальної абстрактної структури – зв'язкових списків.

На сьогоднішньому занятті ми розглянемо фундаментальну абстрактну структуру пов'язаного списку.

Пов'язаний список – це набір послідовно організованих даних. Зв'язкові списки визначені як примітиви в деяких мовах програмування (зокрема, у Ліспі, Delphi), але не в Паскалі. Однак Паскаль надає деякі базові примітивні операції, що дозволяють легко використовувати зв'язані списки.

Головна перевага пов'язаних списків перед масивами у тому, що можуть зменшувати чи збільшувати свої розміри під час виконання програми. Зокрема ми не повинні заздалегідь знати його максимальний розмір.

Друга перевага полягає в тому, що вони забезпечують гнучкість під час переорганізації їх елементів. Така гнучкість виходить за рахунок втрати швидкості доступу до довільного елементу списку. Це стане більш очевидним нижче, після того, як ми ознайомимося з деякими основними властивостями пов'язаних списків та базовими операціями, визначеними над ними.

Список можна подати у вигляді ланок ланцюга.

У масиві послідовна організація забезпечується безпосередньо (згідно з індексом).

Для пов'язаного списку використовується спеціальний спосіб організації даних, згідно з яким його елемент міститься в "вузлі" містить дані, а також "посилання" на наступний "вузол".

Вузол та посилання можна описати так:

Type Link = ^Node; Node = record Data: integer; Next: Link; End;

Для опису списку ми будемо використовувати додатково два допоміжні вузли head та z. Вузол head вказуватиме на перший елемент списку, а z - останній елемент списку. Head інодіназивають "голова" списку, а z - "хвіст".

Тоді список можна буде подати у такому вигляді.

Таке представлення даних дозволяє проводити деякі операції набагато ефективнішими методами, ніж масивами. Наприклад, якщо ми хочемо пересунути елемент 1 з кінця на початок, то для проведення такої операції в масиві нам потрібно було пересунути всі його елементи, щоб звільнити місце. У зв'язаному списку ми тільки змінюємо посилання. Обидва варіанти малюнка еквівалентні; вони лише по-різному намальовані. Ми просто встановлюємо заново посилання вузла, що містить 1, на вузол містить 2, а посилання порожнього вузла head на вузол містить 1. Навіть якби список був дуже великий, то нам все одно знадобилося б тільки три перестановки посилань для подібного обміну.

Що важливіше, тепер ми можемо говорити про "вставку" елемента у зв'язаний список (що збільшує його довжину на один елемент) - операції, яка настільки неприродна і незручна на масивах. На малюнку показано, як вставити в список новий вузол. Потрібно спочатку додати цей вузол, потім створити посилання q на вузол, а потім змінити посилання вузла p на новий вузол. Для цього потрібно змінити лише два посилання незалежно від довжини списку.

Аналогічно ми можемо вести мову про "видалення" елемента зі списку (що зменшує його розмір на один елемент). Потрібно просто переставити посилання на вузол, який слідує за вузлом q і після цього вузол, що містить q, повинен бути знищений.

Паскаль надає нам деякі примітивні операції, які дозволяють нам безпосередньо створювати зв'язані списки. Наступний фрагмент коду – це приклад реалізації основних функцій,які ми щойно обговорювали.

Type Link = ^Node; Node = record Data: integer; Next: Link; End;

Var Head, z: link;

procedure list_initialize; begin new(head); new(z); head^.next := z; z^.next := nil; end;

procedure insert_after( v : integer; t : link ); var x: link; begin new(x); x^.data := v; x^.next := t^.next; t^.next := x; end;

procedure delete_next (t: link); var del:link; begin del := t^.next; t^.next := t^.next^.next; dispose(del); end;

Давайте розглянемо їх докладніше.

Link = ^Node; - тут створюється новий тип Link, який є типізованим покажчиком на тип Node. Тип Node наведено нижче.

Давайте детальніше розберемо це визначення.

Пам'ять комп'ютера можна у наступному вигляді. Вона розбита на блоки, кожен такий блок називається сегментом. У Dos номер кожного сегмента може містити максимум 16 біт (число $FFFF, коли всі біти дорівнюють

1) (символ $ - це символ шістнадцяткової системи обчислення), тобто. будь-який сегмент може мати номер [0; $FFFF]. Припустимо, що ми розглядаємо ділянку пам'яті із сегментами $592B, $592C, $592D. Щоб знайти конкретну комірку пам'яті всередині кожного сегмента є так зване усунення, яке теж може мати номер [0; $FFFF]. Наприклад нехай зміщення всередині сегмента $592C буде $B401, тоді покажчик на цю комірку пам'яті матиме значення $592CB401.

procedure list_initialize;

head ^.

procedureinsert_after( v : integer; t : link );

procedure delete_next(t:link);

Чому використання порожніх вузлів таке корисне?

По-перше, якби ми домовилися тримати покажчик початку списку замість того, щоб тримати вузол head, то процедурі вставки знадобилася б спеціальна перевірка для вставки початку списку.

По-друге, угода порожнього вузла z оберігає процедуру видалення від зайвої перевірки видалення з порожнього списку.

А ці перевірки суттєво впливають на час роботи програми.

Вираз типуhead^.next^.key дає нам перший елемент списку, аhead^. Next^.next^.key - другий.

Давайте створимо програму, яка обробляє інформацію про автомобілі.

program car; uses crt; type namestr = string[20]; Link = ^Node; Node = record name: namestr; speed: integer; next: link; end; var head, z:link; namfind: namestr; v: 0..4; endmenu: boolean;

procedure list_initialize; begin new(head); new(z); head^.next:=z; z^.next:=nil; end;

procedure list_destroy; begin dispose(head); dispose(z); end;

procedure insert_after(name1: namestr; speed1: integer; t: link); var x: link; begin new(x); x^.name: = name1; x^.speed:= speed1; x^.next := t^.next; t^.next := x; end;

procedure delete_next(t: link); var del:link; begin del := t^.next; t^.next := t^.next^.next; dispose(del); end;

procedure InpAuto; var nam: namestr; sp: integer; begin write('Введіть марку автомобіля:'); readln(nam); write('Максимальна швидкість:'); readln(sp); insert_after(nam, sp, head); end;

procedure Mylist; var Curr: Link; begin Curr:=head^.next; While Curr^.next <> nil do begin writeln('Марка: ', Curr^.name, ' Швидкість: ', Curr^.Speed); curr:=curr^.next; end; write('Виведення списку закінчено натисніть Enter.'); readln; end;

function findname(fn:namestr): link; var Curr: Link; begin Curr:=head; While Curr<Nil do якщо Curr^.name=fn then begin findname:=curr; exit; end else curr:=curr^.next; findName:=Nil; end;

begin list_initialize; endmenu:=false; repeat clrscr; writeln('Вкажіть вид роботи:'); writeln('1. Запис першим до списку'); writeln('2. Видалення першого об'єкта зі списку'); writeln('3. Перегляд всього списку'); writeln('4. Видалення об'єкта, наступного у списку за вказаним'); writeln('0. Закінчення роботи'); readln(v); case v of 1: inpauto; 2: delete_next(head); 3: mylist; 4: begin writeln('Введіть марку автомобіля, за яким слід видаляється зі списку'); readln(NamFind); delete_next(FindName(namfind)); end; else endmenu:=true; end; until endmenu; list_destroy; end.

Наступний вид списків – це циклічні списки. Циклічний список - це останній елемент, якого вказує на перший. Цей список дозволяє програмі знову і знову переглядати список по колу, поки в цьому є необхідність.

Як приклад, ми розглянемо так звану "проблему Джозефа". Вона полягає в наступному: уявіть собі, що N людина вирішили вчинити масове самогубство, вибудовуючи себе в коло і вбиваючи кожну М людину і поступово звужуючи коло. Треба знайти людину, яка помре останньою (хоча можливо під кінець вона змінить свою думку з цього питання), або, по-іншому, знайтипорядок смерті цих людей. Наприклад, якщо N=9 та М=5, то люди будуть убиті в наступному порядку: 5 1 7 4 3 6 9 2 8. Ця програма читає значення N та M, а потім роздруковує цей порядок.

Ця програма використовує циклічний пов'язаний список для прямого симулювання порядку самогубств. Спочатку створюється список з ключами від 1 до N: змінна head вказує на початок списку в процесі його створення, а потім програма робить, щоб останній елемент у списку вказував на head. Потім програма проходить за цим циклічним списком, пропускаючи M-1 елементом і знищуючи наступний після них вузол до тих пір, поки в списку не залишиться один єдиний елемент (який вказує на себе).

Type link=^node; node=record data:word; next:link; end; Var N, M:word; head:link; Procedure Init; Var q,l:link; i:word; Begin Write('Enter N: '); Readln(N); New(head); l:=head; Head^.data:=1; Head^.next:=head; For i:=2 to n do begin New(q); q^.data:=i; l^.next:=q; q^.next:=head; l:=q; end; End; Procedure Del; Var i,k:word; q,p:link; Begin Write('Enter M: '); Readln(M); k:=0; i:=1; q:=head; While k

Отже, на сьогоднішньому занятті ми розглянули посилання та покажчики, лінійні та циклічні списки

---