Function Empty: Boolean;
If I = 0 then Empty: = True Else Empty: = False;
При виконанні операції вибірки з стека спочатку необхідно здійснити перевірку на порожнечу стека. Якщо він порожній, то Empty повертає значення True. Якщо Empty повертає False, то це означає, що стік не порожній і з нього ще можна вибирати елементи.
Procedure StackTop (var I: Integer; S: Stack);
2.4.2 Черга
Поняття черги всім добре відомо з повсякденного життя. Елементами черзі в загальному випадку є замовлення на ту чи іншу обслуговування.
У програмуванні є структура даних, яка називається чергою. Ця структура даних використовується, наприклад, для моделювання реальних черг з метою визначення їх характеристик при даному законі надходження замовлень і дисципліни їх обслуговування. За своєю суттю чергу є полустатіческой структурою - з плином часу і довжина черги, і склад можуть змінюватися.
На ріс.пріведена чергу, містить чотири елементи - А, В, С і D. Елемент А розташований на початку черги, а елемент D - в її кінці. Елементи можуть віддалятися тільки з початку черги, тобто перший поміщається в чергу об'єкт був видалений першим. З цієї причини чергу часто називають списком, організованим за принципом «перший розміщений першим видаляється» на противагу принципу стековой організації - «останній розміщений першим видаляється».
Дисципліну обслуговування, в якій замовлення, що надійшло в чергу першим, вибирається першим для обслуговування (і видаляється з черги), називається FIFO (First In First Out - Першим прийшов, першим пішов). Черга відкрита з обох сторін.
Таким чином, вилучення компонент відбувається з початку черги, а запис - в кінець. У цьому випадку вводять два покажчика: один - на початок черги, другий - на її кінець.
Реальна чергу створюється в пам'яті ЕОМ у вигляді одновимірного масиву з кінцевим числом елементів, при цьому необхідно вказати тип елементів черги, а також необхідна змінна в роботі з чергою.
Фізично чергу займає суцільну область пам'яті і елементи слідують один за одним, як в послідовному списку.
Операції, вироблені над чергою:
Для черзі визначені три примітивні операції. Операція insert (q, x) поміщає елемент х в кінець черги q. Операція remove (q) видаляє елемент з початку черги q і привласнює його значення змінної х. Третя операція, empty (q), повертає значення true або false залежно від того, чи є дана чергу порожній чи ні. Крім того. З огляду на те, що полустатіческая чергу реалізується на одновимірному масиві, необхідно стежити за можливістю його переповнення. Сетой метою вводиться опнрація full (q).
Операція insert може бути виконана завжди, оскільки на кількість елементів, які може містити чергу, ніяких обмежень не накладається. Операція remove, однак, може бути застосована тільки до непорожній черги, оскільки неможливо видалити елемент з черги, яка не містить елементів. Результатом спроби видалити елемент з порожньою черзі є виникнення виняткової ситуації втрата значущості. Операція empty, зрозуміло, здійсненна завжди.
Приклад реалізації черги у вигляді одновимірного масиву на Паскалі:
Queue = Array [1..MaxQ] of E;
Прибираємо елементи A і B з черги.
На жаль, при подібному представленні черзі, можливе виникнення абсурдної ситуації, при якій чергу є марною, однак новий елемент розмістити в ній не можна (розгляньте послідовність операцій видалення і вставки, що приводить до такої ситуації). Ясно, що реалізація черзі за допомогою масиву є неприйнятною.
Одним з рішень проблеми, що виникла може бути модифікація операції remove таким чином, що при видаленні чергового елемента вся чергу зміщується до початку масиву. Операція remove (q) може бути в цьому випадку реалізована в такий спосіб.
Мінлива F більше не потрібно, оскільки перший елемент масиву завжди є початком черзі. Порожня чергу представлена чергою, для якої значення R дорівнює нулю.
Однак цей метод досить непродуктивна. Кожне уда-ня вимагає переміщення всіх, хто лишився в черзі елементів. Якщо чергу містить 500 або 1000 елементів, то очевидно, що це дуже неефективний спосіб. Далі, операція видалення елемента з черги логічно передбачає маніпулювання тільки з одним елементом, т. Е. З тим, який розташований на початку черги. Реалізація даної операції повинна відображати саме цей факт, не роблячи при цьому безлічі додаткових дій.
Інший спосіб передбачає розглядати масив, який містить чергу у вигляді замкнутого кільця, а не лінійної послідовності, що має початок і кінець. Це означає, що перший елемент черги слід відразу ж за останнім. Це означає, що навіть у тому випадку, якщо останній елемент зайнятий, нове значення може бути розміщено відразу ж за ним на місці першого елемента, якщо цей перший елемент порожній.
Організація кільцевої черзі.
Розглянемо приклад. Припустимо, що черга містить три елементи - в позиціях 3, 4 і 5 пятіелементного масиву. Цей випадок, показаний на рис. 2.17. Хоча масив і не заповнений, останній елемент черги зайнятий.
Якщо тепер робиться спроба помістити в чергу елемент G, то він буде записаний в першу позицію масиву, як це показано на рис. 2.17. Перший елемент черги є Q (3), за яким слідують елементи Q (4), Q (5) і Q (l).
На жаль, при такому поданні досить важко визначити, коли черга порожня. Умова R Одним із способів вирішення цієї проблеми є введення угоди, при якому значення Fесть індекс елемента масиву, негайно передує першому елементу черги. а не індексу самого першого елемента. В цьому випадку, оскільки R містить індекс останнього елемента черги, умова F = R має на увазі, що черга порожня. Відзначимо, що перед початком роботи з чергою, в F і R встановлюється значення останнього індексу масиву, а не 0 і 1, оскільки при такому поданні черги останній елемент масиву негайно-но передує першому елементу. Оскільки R = F, то чергу спочатку порожня. Основні операції з кільцевої чергою: 1. Вставка елемента q в чергу x. 2. Витяг елемента з черги x. 3. Перевірка черзі на порожнечу. 19. Як організовується кільцева чергу? 20. Яка особливість деков? До сих пір ми розглядали тільки статичні програмні об'єкти. Однак використання при програмуванні тільки статичних об'єктів може викликати певні труднощі, особливо з точки зору отримання ефективної машинної програми. Справа в тому, що іноді ми заздалегідь не знаємо не тільки розміру значення того чи іншого програмного об'єкта, але також і того, чи буде існувати цей об'єкт чи ні. Такого роду програмні об'єкти, які виникають уже в процесі виконання програми або розмір значень яких визначається при виконанні програми, називаються динамічними об'єктами. Динамічні структури даних мають 2 особливості: 1) Заздалегідь не визначене кількість елементів в структурі. 2) Елементи динамічних структур не мають жорсткої лінійної впорядкованості. Вони можуть бути розкидані по пам'яті. Щоб зв'язати елементи динамічних структур між собою до складу елементів крім інформаційних полів входять поля покажчиків (рис. 3.1) (зв'язок з іншими елементами структури). Найбільш поширеними динамічними структурами є зв'язані списки. З точки зору логічного представлення розрізняють лінійні і нелінійні списки. До лінійним списками відносяться одинзв'язні і двусвязного списки. До нелінійним - багатозв'язкові. Приклад в загальному випадку являє собою поле записи і одного або декількох покажчиків. Елемент однозв'язного списку містить два поля (рис. 3.2): інформаційне поле (INFO) і поле покажчика (PTR). Доступ до елемента списку здійснюється тільки від його початку, тобто зворотного зв'язку в цьому списку немає. Кільцевій однозв'язний список виходить зі звичайного однозв'язного списку шляхом привласнення вказівником останнього елемента списку значення покажчика початку списку (рис 3.3). Найпростіші операції, вироблені над однозв'язного списками 1) Вставка в початок однозв'язного списку. Треба вставити в початок однозв'язного списку елемент з інформаційним полем D. Для цього необхідно згенерувати порожній елемент (P = GetNode). Інформаційного поля цього елемента привласнити значення D (INFO (P) = D), значенням покажчика на цей елемент привласнити значення покажчика на початок списку (Ptr (P) = Lst), значенням покажчика початку списку привласнити значення покажчика P (Lst = P). Реалізація на Паскалі: Вставка в початок 2) Видалення елемента з початку однозв'язного списку. Треба видалити перший елемент списку, але запам'ятати інформацію, що міститься в поле Info цього елемента. Для цього введемо покажчик P, який буде вказувати на видаляється елемент (P = Lst). У змінну X занесемо значення інформаційного поля Info видаляється елемента (X = Info (P)). Значенням покажчика на початок списку дамо значення покажчика наступного за видаляється елемента (Lst = Ptr (P)). Видалимо елемент (FreeNode (P)). Реалізація на Паскалі: Видалення з початку Використання односпрямованих списків при вирішенні ряду завдань може викликати певні труднощі. Справа в тому, що по односпрямованому списку можна рухатися тільки в одному напрямку, від заголовного ланки до останнього ланці списку. Тим часом нерідко виникає необхідність зробити яку-небудь обробку елементів, що передують елементу із заданою властивістю. Однак після перебування елемента з цією властивістю в однозв'язного списку у нас немає можливості отримати досить зручний і швидкий доступ до попередніх елементів - для досягнення цієї мети доведеться ускладнити алгоритм, що незручно і нераціонально. Двусвязний список характеризується тим, що у будь-якого елементу є два покажчика. Один вказує на попередній елемент (зворотний), інший вказує на наступний елемент (прямий) (рис. 3.4). Фактично двусвязний список це два однозв''язних списку з однаковими елементами, записаних в протилежної послідовності. Операції над двусвязного списками: - cоздание елемента списку; - пошук елемента в списку; - вставка елемента в вказане місце списку; - видалення зі списку заданого елемента. Будь однозв'язний список може розглядатися у вигляді стека. Однак список в порівнянні зі стеком у вигляді одновимірного масиву має перевагу, так як заздалегідь не заданий його розмір. Стекові операції, застосовні до списків 1). Щоб додати елемент в стек, треба в алгоритмі замінити покажчик Lst на покажчик Stack (операція Push (S, X)). 2) Перевірка стека на порожнечу (Empty (S)) If Stack = Nil then Print "Стек порожній" 3) Вибірка елементу з стека (POP (S)) Для більш ефективного використання пам'яті комп'ютера (для виключення сміття. Тобто невикористовуваних елементів) при роботі його зі списками створюється вільний список, який має той же формат полів, що і у функціональних списків. Якщо у функціональних списків різний формат, то треба створювати вільний список кожного функціонального списку. Кількість елементів у вільному списку повинно бути визначено завданням, яке вирішує програма. Як правило, вільний список створюється в пам'яті машини як стек. При цьому створення (GetNode) нового елемента еквівалентно вибірці елемента вільного стека, а операція FreeNode - додаванню в вільний стік звільнився елемента. Нехай нам необхідно створити порожній список за типом стека (рис. 3.6) з покажчиком початку списку - AVAIL. Розробимо процедури, які дозволять нам створювати порожній елемент списку і звільняти елемент зі списку. Розробимо процедуру, яка буде створювати порожній елемент списку з покажчиком Р. Для реалізації операції GetNode необхідно вказівником згенерованого елемента привласнити значення покажчика початку вільного списку, а покажчик початку перенести до наступного елементу. Перед цим треба перевірити, чи є елементи в списку. Порожнеча вільного списку (Avail = Nil), еквівалентна переповнення функціонального списку. If Avail = Nil then Print "Переповнення" Stop При звільненні елемента Nod (P) з функціонального списку операцією FreeNode (P), він заноситься в вільний список. Стандартні операції повернення звільнився елемента списку в пул вільних елементів не завжди дають ефект, якщо використовуються нелінійні багатозв'язкові списки. Перший спосіб утилізації - метод лічильників. У кожен елемент багатозв'язного списку вставляється поле лічильника, який рахує кількість посилань на даний елемент. Коли лічильник елемента виявляється в нульовому стані, а поля покажчиків елемента знаходяться в стані nil, цей елемент може бути повернутий в пул вільних елементів. Другий спосіб - метод збирання сміття (метод маркера). Якщо з якихось елементом встановлено зв'язок, то однобітових поле елемента (маркер) встановлюється в "1", інакше - в "0". За сигналом переповнення шукаються елементи, у яких маркер встановлено в нуль, т. Е. Включається програма збірки сміття, яка переглядає всю відведену пам'ять і повертає в список вільних елементів, усі вони, чи не помічені маркером. Необхідно вставити в існуючий масив елемент X між 5 і 6 елементами. Для проведення даної операції в масиві потрібно "опустити" всі елементи, починаючи з X6 - збільшити їх індекси на одиницю. В результаті вставки отримуємо наступний масив (рис. 3.7, 3.8): Дана процедура може займати дуже значний час. На противагу цьому, в пов'язаному списку операція вставки полягає в зміні значення 2-х покажчиків і генерації вільного елементу. Причому час, витрачений на виконання цієї операції, є постійним і не залежить від кількості елементів в списку. Визначаємо елемент, після якого необхідно вставити елемент в список. Вставка проводиться за допомогою процедури InsAfter (Q, X), а видалення - DelAfter (Q, X). При цьому робочий покажчик P буде вказувати на елемент, після якого необхідно провести вставку або видалення (рис 29). Нехай необхідно вставити новий елемент з інформаційним полем X після елемента, на який вказує робочий покажчик P. 1) Необхідно згенерувати новий елемент. 2) Інформаційному полю цього елемента привласнити значення X. 3) Вставити отриманий елемент. Це і є процедура InsAfter (Q, X). Нехай необхідно видалити елемент списку, який слід після елемента, на який вказує робочий покажчик P. 1) Надаємо Q значення покажчика на видаляється елемент. 2) В змінну X зберігаємо значення інформаційного поля видаляється елемента. 3) Міняємо значення покажчика на видаляється елемент на значення покажчика на наступний елемент і виробляємо видалення. Це і є процедура DelAfter (P, X). Мовою Паскаль вищеописані процедури будуть виглядати наступним чином: procedure InsAfter (var Q: PNode; X: Integer); procedure DelAfter (var Q: PNode; var X: Integer); Позначимо P - робочий покажчик, на початку процедури P = Lst. Введемо також покажчик Q, який відстає на один елемент від P. Коли покажчик P знайде елемент, останній буде видалений щодо покажчика Q як наступний елемент. While P <> Nil do If Info (P) = 4 then Дан упорядкований по зростанню Info - полів список. Необхідно вставити в цей список елемент зі значенням X, не порушивши впорядкованості списку. Нехай X = 16. Початкова умова: Q = Nil, P = Lst. Вставка елемента повинна відбутися між 3 і 4 елементом (рис.3.10). While (P <> Nil) and (X> Info (P)) do Для створення переліку з заголовком в початок списку вводиться додатковий елемент, який може містити інформацію про список (рис. 3.11). У заголовок списку часто поміщають динамічну змінну, що містить кількість елементів у списку (не рахуючи самого заголовка). Якщо список порожній, то залишається тільки заголовок списку (рис. 3.12). Також зручно занести в інформаційне поле заголовка значення покажчика кінця списку. Тоді, якщо список використовується як черга, то Fr = Lst, а Re = Info (Lst). З через великий обсяг цей матеріал розміщений на декількох сторінках: 3.1 Зв'язні списки
3.1.1 однозв'язного списки
3.1.2 Кільцевій однозв'язний список
3.1.3 двусвязного список
3.1.4 Кільцевій двусвязний список
3.2 Реалізація стеків за допомогою однозв''язних списків
3.3 Організація операцій Getnode, Freenode і утилізація звільнилися елементів
3.3.1 Операція GetNode
3.3.2 Операція FreeNode
3.3.3 Утилізація звільнилися елементів в багатозв'язних списках
3.4 однозв'язного список, як самостійна структура даних
3.4.1 Вставляння та виймання елементів зі списку
3.4.2 Приклади типових операцій над списками
3.4.3 Елементи заголовків в списках
1 2 3 4 5 6 7 8Схожі статті