Б С Бусигін - Прикладна інформатика - страница 50

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83 

8.27.10. Логічна структура черги FIFO

Чергою FIFO (First In - First Out - "першим прийшов - першим виключається") називається такий послідовний список зі змінною довжиною, у якому включення елементів виконується тільки з однієї сторони списку (цю сторону часто називають кінцем чи хвостом черги), а виключення - з іншої сторони (називаної початком чи головою черги). Ті самі черги, що виникають до прилавків і кас, є типовим побутовим прикладом черги FIFO.

Основні операції над чергою - це включення і виключення елементів, визначення розміру черги, очищення, не руйнуюче читання.

Черги будуються на базі лінійних списків. Представлення черги за допомогою лінійного списку дозволяє досить просто забезпечити будь-які бажані операції обслуговування черги. Особливо це зручно, коли число елементів у черзі важко передбачити. Лінійні списки також знаходять широке застосування в додатках, де непередбачені вимоги до розміру пам'яті, необхідної для збереження даних; мається велике число складних операцій над даними, особливо включень і виключень.

8.27.11. Зв'язні лінійні списки

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

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

На рис. 8.96 приведена спрощена структура однозв'язного списку. На ньому поле INF - інформаційне поле, яке може включати різноманітні дані, як вбудованих, так і користувацьких типів Турбо Паскалю дані, NEXT - указник на наступний елемент списку. Кожен список повинний мати особливий елемент, називаний указником початку списку чи головою списку, що звичайно по форматі відмінний від інших елементів. У поле указника останнього елемента списку знаходиться спеціальна ознака nil, що свідчить про кінець списку.

8.27.12. Реалізація операцій над зв'язними лінійними списками

Для розгляду програмних прикладів визначимо наступні типи даних:

Type

data = { Будь-яка структура інформаційної частини списку }

Type { Елемент однозв'язного списку (sll - single linked list):}

Рис 8.96. Логічна структура однозв'язного списку

sllptr = Aslltype;  І указник в однозв'язному списку } slltype = record І елемент однозв'язного списку }

inf : data;   І інформаційна частина } next  :  sllptr; І указник на наступний елемент } end;

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

Словесні описи алгоритмів дані у виді коментарів до програмних прикладів.

8.27.13. Перебір елементів списку.

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

І Перебір І -зв'язного списку }

Procedure LookSll   (head  : sllptr); { head - указник на початок списку }

Var

cur :  sllptr; І адреса поточного елемента }

Begin

cur:=head; { 1-й елемент списку призначається поточним } while cur <> nil do begin

< обробка curA.inf> Іобробляється інформаційна частина того елементу, на який указує cur. Обробка може включати: друк вмісту інформаційної частини; модифікацію полів інформаційних частин; порівняння полів інформаційних частин зі зразком при пошуку по ключу; підрахунки ітерацій циклу при пошуку по номеру і т.д.}

cur:=curA.next; Із поточного елементу вибирається указник на наступний елемент і для наступної ітерації наступний елемент стає поточним; якщо поточний елемент був останнім, то його поле NEXT містить порожній указник і тому у cur запишеться nil, що приведе до виходу з циклу при перевірці умови while} end; {while} End; { Proc LookSll}

8.27.14. Вставка елемента у список.

Вставка елемента у середину однозв'язного списку показана у прикладі нижче та на рис.8.97.

І Вставка елемента у середину однозв'язного списку }

Procedure InsertSll(prev :  sllptr;  inf  : data); {prev - адреса попереднього елементу; inf - дані нового елементу}

Var

cur :  sllptr; ІАдреса нового елементу}

Begin

New(cur);  ІВиділення пам'яті для нового елементу} curA.inf:=inf;  ІЗапис у інформаційну частину елементу} curA.next   := prevA.next; ІЕлемент, який йшов за попереднім

тепер буде йти за новим} prevA.next  := cur; І Новий елемент йде за попереднім} End; {Proc InsertSll}

INF

NEXT

4

INF

NEXT

К

INF

NEXT

•••

Ф

INF

NEXT

©

Рис. 8.97. Вставка елемента у середину списку

Ви повинні добре себе уявляти, що писля того, як Ви за допомогою процедури New отримали адресу нового елементу списку cur (current -поточний) та заповнили його інформаційну частину inf, Ви повинні на першому кроці Ф (рис. 86) перенести у його поле NEXT адресу з попереднього елементу. Тоді він буде указувати на наступний елемент (крок ©). Після цього Ви повинні занести адресу cur нового елемента у поле NEXT попереднього елементу (крок ®). Тоді, після цього, попередній елемент буде указувати на новий елемент (крок ©).

У такий спосіб Ви можете зробити вставку у середину списку, але не зможете зробити вставку у його початок. При цьому повинний модифікуватися указник на початок списку, як показано на рис. 8.98.

©

HEAD

і

-> INF

NEXT

к

INF

NEXT

•••

Ф

INF

NEXT

©

Рис. 8.98. Вставка елемента у голову списку

Як Ви бачите, операція дуже схожа на попередню (рис. 86), але тонкощі полягають у засобі зберігання указника HEAD. Тому, давайте розробимо процедуру, яка буде виконувати вставку елемента в будь-яке місце однозв'язного списку:

І Вставка елемента в будь-яке місце однозв'язного списку }

Procedure  InsertSll   (Var head  :   sllptr;   { Указник на початок

списку, що може змінитися у процедурі. Якщо head=nil - список порожній }

prev  :   sllptr;   {Указник на елемент, після якого робиться вставка. Якщо prev=nil - вставка перед першим елементом } inf : data;  ІДані нового елементу } Var cur :  sllptr) ІАдреса нового елементу }

Begin

New(cur);    ІВиділення пам'яті для нового елемента й запис у його

інформаційну частину} curA.inf:=inf; if prev <> nil then

begin ІЯкщо є попередній елемент - вставка у середину списку, див. рис.87}

curA.next:=prevA.next; prevA.next:=cur;

end else

begin ІВставка у початок списку }

curA.next:=head; ІНовий елемент указує на колишній 1-й елемент

списку; якщо head=nil, то новий елемент буде й останнім елементом списку} head:=cur; І Новий елемент стає 1-им у списку, указник на початок тепер указує на нього}

end {if} End;  {Proc InsertSll}

8.27.15. Видалення елемента зі списку.

Порядок видалення елемента з однозв'язного списку з середини списку та з початку декілька відрізняється. Тому, давайте почнемо з видалення елемента з середини списку (рис. 8.99).

Ф

INF

NEXT

©

INF

NEXT

і >

INF

NEXT

•••

Видаляємо

D

Рис. 8.99. Видалення елементу з середини списку

Тут, спершу Ви повинні указник на наступний елемент з елементу, який видаляється, перенести в попередній (крок Ф), тоді на кроці © указник обминає елемент, який видаляється. І на третьому кроці D Ви повинні видалити сам елемент, щоб звільнити від нього пам'ять.

У випадку видалення елементу з голови списку Ви повинні указник HEAD переадресувати на наступний елемент (рис. 8.100).

Ф

А''

HEAD

і 

INF

NEXT

і -4

INF

NEXT

•••

Видаляємо] D ©

Рисунок 8.100. Видалення елементу з голови списку

Тут, спершу Ви повинні указник на наступний елемент з елементу, який видаляється, перенести в указник HEAD (крок Ф), тоді на кроці © указник HEAD обминає елемент, який видаляється. А на третьому кроці D Ви повинні видалити сам елемент, щоб звільнити від нього пам'ять.

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

{Видалення елемента з будь-якого місця однозв'язного списку}

Procedure   DeleteSll(var   head   :   sllptr;  {Указник на початок

списку, може змінитися в процедурі}

del    :    sllptr   {Указник на елемент, який

видаляється} ); var prev :  sllptr; {Адреса попереднього елементу } Begin

if head=nil then

begin  {Спроба видалення з порожнього списку розцінюється як помилка (у наступних прикладах цей випадок враховуватися на

буде)}

Writeln('Помилка!');

Halt;

end;

if  del=head  then {Якщо елемент, що видаляється, 1 -й у списку, то

наступний за ним стає першим }

head:=delA.next

else

begin { При видаленні із середини списку приходиться шукати елемент, що передує тому, що видаляється; пошук робиться перебором списку із самого його початку, поки не буде знайдено елемент, поле next якого збігається з адресою елемента, що видаляється} prev:=headA.next;

while   (prevA.next<>del)   and  (prevA.next<>nil) do prev:=prevA.next; if prevA.next=nil then

begin {Це випадок, коли перебраний весь список, але елемент не знайдений, він відсутній у списку; це розцінюється як помилка (у наступних прикладах цей випадок враховуватися на буде)} Writeln('Помилка!');

Halt;

end;

prevA.next :=delA.next; {Попередній елемент тепер указує на

наступний за тим, що видаляється}

end;

Dispose(del);  {Елемент виключений зі списку - тепер можна звільнити

займану їм пам'ять} End;  {Proc DeleteSll}

8.27.16. Перестановка елементів списку.

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

Давайте спробуємо зробити перестановку двох сусідніх елементів списку. Однак, по-перше спробуємо розібратись, як проходить цей процес (рис. 8.101).

•••

INF

NEXTl

Ф

©

INF

і

©

INF

і

•••

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83 


Похожие статьи

Б С Бусигін - Прикладна інформатика