НАПІВСТАТИЧНІ СТРУКТУРИ ДАНИХ R

ГЛАВА 4

 

НАПІВСТАТИЧНІ СТРУКТУРИ ДАНИХ R

 

Характерні риси напівстатичних структур P

Рядки P

Черги P

Стеки P

Черги FІFO P

Деки P

Черги з пріоритетамиP

 

НАПІВСТАТИЧНІ СТРУКТУРИ ДАНИХ

Характерні риси напівстатичних структур

Напівстатичні структури даних характеризуються такими ознаками: Ø мають змінну довжину і прості процедури її зміни; Ø зміна довжини структури відбувається у визначених межах, не перевищуючи якогось максимального (граничного)…

Рядки

 

ЛОГІЧНА СТРУКТУРА. Рядок – це лінійно упорядкована послідовність символів, що належать кінцевій множині символів, названій алфавітом. Рядки мають наступні важливі властивості:

– їхня довжина, як правило, змінна, хоча алфавіт фіксований;

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

– найчастіше метою доступу до рядка є не окремий її елемент (хоча це теж не виключається), а деякий ланцюжок символів у рядку.

Говорячи про рядки, звичайно мають на увазі текстові рядки – рядки, що складаються із символів, які входять в алфавіт якої-небудь обраної мови, цифр, розділових знаків та інших службових символів. Однак варто мати на увазі, що символи, які входять у рядок, можуть належати будь-якому алфавіту. Так, у мові PL/1 поряд з типом даних "символьний рядок" – CHAR(n), існує тип даних "бітовий рядок" – BІТ(n). Бітові рядки складаються з 1-бітових символів, що належать алфавіту: {0, 1}. Всі рядкові операції з рівним успіхом застосовні як до символьних, так і до бітових рядків. У сучасних обчислювальних системах прийняте кодування всієї множини символів на розрядній сітці фіксованого розміру (1 чи 2 байти). Однак, у залежності від особливості задачі, властивостей застосованого алфавіту і мови, що представляється ними, властивостей носіїв інформації можуть застосовуватися й інші способи кодування символів.

У більшості мов програмування (C, PASCASL, PL/1 та ін.) рядки представляються саме як напівстатичні структури, хоча змінюваність рядків може варіюватися від повної її відсутності до практично необмежених можливостей зміни. Орієнтація на той чи інший ступінь змінюваності рядків визначає і фізичне представлення їх у пам'яті й особливості виконання операцій над ними.

У залежності від орієнтації мови програмування засоби роботи з рядками займають у мові більш або менш значне місце. Наприклад:

Мова C – мова системного програмування, тому типи даних, з якими працює C, максимально наближені до тих типів, з якими працюють машинні команди. Оскільки машинні команди не працюють з рядками, немає такого типу даних і в мові C. Рядки в C представляються у вигляді масивів символів. Операції над рядками можуть бути виконані як операції обробки масивів чи за допомогою бібліотечних (але не вбудованих!) функцій рядкової обробки.

У мовах універсального призначення рядковий тип звичайно є базовим: STRІNG – у PASCAL, CHAR(n) – у PL/1. Основні операції над рядками реалізовані як прості операції чи вбудовані функції. Можливі також бібліотеки, що забезпечують розширений набір рядкових операцій.

Мова REXX – мова, орієнтована насамперед на обробку текстової інформації. Тому в REXX немає засобів опису типів даних: всі дані представляються у вигляді символьних рядків. Операції над даними, не властивими символьним рядкам, або виконуються спеціальними функціями, або приводять до прозорого для програміста перетворення типів. Так, наприклад, інтерпретатор REXX, зустрівши оператор, що містить арифметичний вираз, сам переводить його операнди на числовий тип, обчислює вираз і перетворює результат на символьний рядок. Цілий ряд рядкових операцій є простими операціями мови, а вбудованих функцій обробки рядків у REXX декілька десятків.

ОПЕРАЦІЇ НАД РЯДКАМИ. Базовими операціями над рядками є:

– визначення довжини рядка;

– присвоювання рядків;

– порівняння рядків;

– конкатенація (зчеплення) рядків;

– виділення підрядка;

– пошук входження підрядка в рядок.

Операція визначення довжини рядка є функцією, що повертає ціле число, яке містить значення поточної кількості символів у рядку.

Операції присвоювання та порівняння рядків мають той же вміст, що і для інших типів даних. Порівняння рядків здійснюється за наступними правилами:

а) порівнюються перші символи двох рядків. Якщо символи не рівні, то рядок, що містить символ, місце якого в алфавіті ближче до початку, вважається меншим;

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

Результатом операції зчеплення двох рядків є рядок, довжина якого дорівнює сумарній довжині рядків-операндів, а значення відповідає значенню першого операнда, за яким безпосередньо записано значення другого операнда. Операція зчеплення дає результат, довжина якого в загальному випадку більше довжини операндів. Як і в усіх операціях над рядками, що можуть збільшувати довжину рядка (присвоювання, зчеплення, складні операції), можливий випадок, коли довжина результату виявиться більшою, ніж відведений для нього обсяг пам'яті. Природно, ця проблема виникає тільки в тих мовах, де довжина рядка обмежується. Можливі три варіанти рішення цієї проблеми, зумовлені правилами мови чи режимами компіляції:

– ніяк не контролювати таке перевищення; виникнення такої ситуації призводить до важко локалізованої помилки при виконанні програми;

– завершувати програму аварійно з локалізацією і діагностикою помилки;

– обмежувати довжину результату відповідно до обсягу відведеної пам'яті.

Операція виділення підрядка виділяє з вихідного рядка послідовність символів, починаючи із заданої позиції n, заданої довжини l. При реалізації операції виділення підрядка в функції мови програмування, а також у процедурі користувача обов'язково повинне бути визначене правило одержання результату для випадку, коли початкова позиція n задана такою, що частина вихідного рядка, яка залишилася за нею, має довжину, меншу заданої довжини l, чи навіть nперевищує довжину вихідного рядка. Можливі такі варіанти правил вирішення вказаного випадку:

– аварійне завершення програми з діагностикою помилки;

– формування результату меншої довжини, ніж задано, можливо навіть порожнього рядка.

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

На основі базових операцій можуть бути реалізовані і будь-які інші, навіть складні операції над рядками. Наприклад, операція видалення з рядка символів із номерами від n1 до n2 включно, може бути реалізована як послідовність наступних кроків:

– виділення з вихідного рядка підрядка, починаючи з позиції 1, довжиною (n1 – 1) символів;

– виділення з вихідного рядка підрядка, починаючи з позиції (n2 + 1), довжиною, рівною довжині вихідного рядка мінус n2;

– зчеплення підрядків, отриманих на попередніх кроках.

Втім, з метою підвищення ефективності деякі вторинні операції у програмах користувача також можуть бути реалізовані як базові з безпосереднім доступом до фізичної структури рядка.

ФІЗИЧНА СТРУКТУРА. Представлення рядків у пам'яті залежить від того, наскільки змінюваними є рядки в кожній конкретній задачі, і засоби такого представлення змінюються від абсолютно статичного до динамічного. Універсальні мови програмування в основному забезпечують роботу з рядками змінної довжини, але максимальна довжина рядка повинна бути зазначена при його створенні. Таким чином підтримується послідовне розміщення рядків у пам'яті. Якщо програміста не влаштовують можливості чи ефективність тих засобів роботи з рядками, що надає йому мова програмування, то він може або визначити свій тип даних "рядок" і використовувати для його представлення засоби динамічної роботи з пам'яттю, або змінити мову програмування на спеціально орієнтовану на обробку тексту (CNOBOL, REXX), у якій представлення рядків базується на динамічному розподілі пам'яті.

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

ВЕКТОРНЕ ПРЕДСТАВЛЕННЯ РЯДКІВ. Представлення рядків у вигляді векторів, прийняте в більшості універсальних мов програмування, дозволяє працювати з рядками, розміщеними в статичній пам'яті. Крім того, векторне представлення дозволяє легко звертатися до окремих символів рядка як до елементів вектора – за індексом.

Вектор постійної довжини. Це найпростіший спосіб представлення рядка. При цьому в пам'яті відводиться фіксована кількість байтів, у які записуються символи рядка. Якщо рядок менше відведеного під нього вектора, то зайві місця заповнюються пробілами, а якщо рядок виходить за межі вектора, то зайві (звичайно з правого боку рядка) символи повинні бути відкинуті. Наприклад, представлення двох рядків 'ABC' і 'PQRSTUVW' у вигляді вектора постійної довжини на шість символів наведене на рис. 4.1.

 

 

Рис. 4.1. Представлення рядка вектором постійної довжини

 

Вектор змінної довжини з ознакою кінця. Цей і всі наступні методи враховують змінну довжину рядків. Ознака кінця – це особливий символ, що належить алфавіту (таким чином, корисний алфавіт виявляється менше на один символ), і займає ту ж кількість розрядів, що і всі інші символи. Витрати пам'яті при цьому способі складають 1 символ на рядок. Таке представлення рядка показане на рис. 4.2.

 

 

Рис. 4.2. Представлення рядка вектором з ознакою кінця рядка

 

Спеціальний символ-маркер кінця рядка позначений тут 'eos'. У мові C, наприклад, як маркер кінця рядка використовується символ з кодом 0.

Вектор змінної довжини з лічильником. Лічильник символів – це ціле число, і для нього виділяється достатня кількість бітів, щоб їх з надлишком вистачало для представлення довжини самого довгого рядка, який тільки можна представити в даній машині. Звичайно для лічильника відводять від 8 до 16 бітів. Тоді при такому представленні витрати пам'яті в розрахунку на один рядок складають 1 – 2 символи. При використанні лічильника символів можливий довільний доступ до символів у межах рядка, оскільки можна легко перевірити, що звертання не виходить за межі рядка. Лічильник розміщується в такому місці, де він може бути легко доступний – на початку рядка чи в дескрипторі рядка. Максимально можлива довжина рядка, таким чином, обмежена розрядністю лічильника. У PASCAL, наприклад, рядок представляється у вигляді масиву символів, індексація в який починається з 0; однобайтний лічильник числа символів у рядку є нульовим елементом цього масиву. Таке представлення рядків показане на рис. 4.3. I лічильник символів, і ознака кінця в попередньому випадку можуть бути доступні для програміста як елементи вектора.

 

 

Рис. 4.3. Представлення рядка вектором змінної довжини з лічильником

 

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

Вектор з керованою довжиною. Пам'ять під вектор з керованою довжиною виділяється при створенні рядка і його розмір та розміщення залишаються незмінними протягом всього часу існування рядка. У дескрипторі такого вектора-рядка може бути відсутнім початковий індекс, тому що він може бути зафіксований раз і назавжди встановленими угодами, але з'являється поле поточної довжини рядка. Розмір рядка, таким чином, може змінюватись від 0 до значення максимального індексу вектора. "Зайва" частина пам'яті, що відводиться, може бути заповнена будь-якими кодами – вона не береться до уваги при оперуванні з рядком. Поле кінцевого індексу може бути використане для контролю перевищення довжиною рядка обсягу відведеної пам'яті. Представлення рядків у вигляді вектора з керованою довжиною (при максимальній довжині 10) показане на рис. 4.4.

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

СИМВОЛЬНО-ЗВ¢ЯЗНЕ ПРЕДСТАВЛЕННЯ РЯДКІВ. Представлення рядків у пам'яті у вигляді списків забезпечує гнучкість у виконанні різноманітних операцій над рядками (зокрема, операцій включення і виключення окремих символів і цілих ланцюжків) та використання системних засобів керування пам'яттю при виділенні необхідного обсягу пам'яті для рядка.

 

Дескриптори рядків

 

Рис. 4.4. Представлення рядка вектором з керованою довжиною

 

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

Односпрямований лінійний список. Кожен символ рядка представляється у вигляді елемента зв'язного списку; елемент містить код символу і покажчик на наступний елемент, як показано на рис. 4.5.

 

 

Рис. 4.5. Представлення рядка у вигляді

односпрямованого лінійного списку

 

Одностороннє зчеплення надає доступ тільки в одному напрямку вздовж рядка. На кожен символ рядка необхідний один покажчик, що звичайно займає 2 – 4 байти.

Двоспрямований лінійний список. Кожен символ рядка представляється у вигляді елемента зв'язного списку; елемент містить код символу і два покажчики: один – на наступний елемент, другий покажчик – на попередній елемент, як показано на рис. 4.6. Двостороннє зчеплення допускає двобічний рух вздовж списку, що може значно підвищити ефективність виконання деяких рядкових операцій. Та слід пам’ятати, що на кожен символ рядка (1 байт інформації ) необхідно два покажчики, тобто 4 – 8 байтів пам’яті .

 

 

 

Рис. 4.6. Представлення рядка у вигляді двоспрямованого лінійного списку

 

БЛОЧНО-ЗВ'ЯЗНЕ ПРЕДСТАВЛЕННЯ РЯДКІВ. Таке представлення дозволяє в більшості операцій уникнути витрат, пов'язаних з керуванням динамічною пам'яттю, але в той же час забезпечує досить ефективне використання пам'яті при роботі з рядками змінної довжини.

Багатосимвольні ланки фіксованої довжини. Багатосимвольні групи (ланки) організуються в список, так що кожен елемент списку, крім останнього, містить групу елементів рядка і покажчик наступного елемента списку. Поле покажчика останнього елемента списку зберігає ознаку кінця – порожній покажчик. У процесі обробки рядка з будь-якої його позиції можуть бути виключені в будь-якому місці чи вставлені елементи, у результаті чого ланки можуть містити менше число елементів, ніж було спочатку. З цієї причини необхідний спеціальний символ, що означав би відсутність елемента у відповідній позиції рядка. Позначимо такий символ 'emp', він не повинен входити в множину символів, з яких складається рядок. Приклад багатосимвольних ланок фіксованої довжини по 4 символи в ланці показано на рис. 4.7.

 

 

Рис. 4.7. Представлення рядків багатосимвольними ланками

фіксованої довжини

 

Таке представлення забезпечує більш ефективне використання пам'яті, чим символьно-зв¢язне. Операції вставки/видалення в ряді випадків можуть зводитись до вставки/видалення цілих блоків. Однак, при видаленні одиночних символів у блоках можуть накопичуватись порожні символи emp, що може призвести навіть до гіршого використання пам'яті ніж у символьно-зв¢язному представленні.

Багатосимвольні ланки змінної довжини. Змінна довжина блока дає можливість позбутися порожніх символів і тим самим заощадити пам'ять для рядка. Однак з'являється потреба в спеціальному символі – ознаці покажчика, на рис. 4.8 він позначений символом 'ptr'.

 

Рис. 4.8. Представлення рядків багатосимвольними

ланками змінної довжини

 

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

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

Багатосимвольні ланки з керованою довжиною. Пам'ять виділяється блоками фіксованої довжини. У кожному блоці крім символів рядка і покажчика на наступний блок містяться номери першого й останнього символів у блоці. При обробці рядка в кожному блоці обробляються тільки символи, розташовані між цими номерами. Ознака порожнього символу не використовується: при видаленні символу з рядка, символи, що залишилися в блоці, ущільнюються і коректуються граничні номери. Вставка символу може бути виконана за рахунок наявного в блоці вільного місця, а при відсутності такого – виділенням нового блока. Хоча операції вставки/видалення вимагають пересилання символів, діапазон пересилань обмежується одним блоком. При кожній операції зміни може бути виконаний аналіз заповнювання сусідніх блоків і два напівпорожніх сусідніх блоки можуть бути переформовані в один блок. Для визначення кінця рядка може використовуватись як порожній покажчик в останньому блоці, так і покажчик на останній блок у дескрипторі рядка. Останнє може бути дуже корисним при виконанні деяких операцій, наприклад, зчеплення. У дескрипторі може зберігатись також і довжина рядка: зчитувати її з дескриптора зручніше, ніж підраховувати її перебором всіх блоків рядка.

Приклад представлення рядка у вигляді ланок з керованою довжиною на 18 символів показаний на рис. 4.9.

Дескриптор

 

Рис. 4.9. Представлення рядків багатосимвольними ланками

з керованою довжиною

 

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

 

Черги

 

Черга (queue) – така структура даних, що зберігає елементи і забезпечує доступ до них тільки в певному порядку, визначеному пріоритетом. Пріоритет визначається одним або більшою кількістю параметрів, що характеризують елементи черги. Пріоритет може визначатися і часом надходження елементів до черги. В цьому випадку говорять про черги LІFO або стеки та черги FІFO, або деки з обмеженим входом та виходом.

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

Стеки

ЛОГІЧНА СТРУКТУРА СТЕКА. Стек – такий послідовний набір даних із змінною довжиною, включення і виключення елементів з якого виконуються тільки з одного боку набору, названого вершиною стека (top). Застосовуються й інші назви стека – магазин, черга, що функціонує за принципом LІFO (Last Іn - Fіrst Out).

МАШИННЕ ПРЕДСТАВЛЕННЯ СТЕКАі реалізація операцій. При представленні стека в статичній пам'яті для нього виділяється пам'ять як для вектора. У дескрипторі цього вектора, крім звичайних для вектора параметрів, повинен знаходитись також покажчик стека – адреса вершини стека. Покажчик стека може вказувати або на перший вільний елемент стека, або на останній записаний у стек елемент. Який з цих двох варіантів вибрати, не має різниці. Важливо в подальшому строго дотримуватись його при обробці стека. При цьому стек може збільшуватися вбік збільшення і зменшення адрес.

Надалі будемо вважати, що ”дно” стека зафіксовано на початку масиву (в комірці з найменшим індексом), покажчик стека адресує перший вільний елемент і стек збільшується вбік збільшення адрес (індексів елементів масиву).

Основні операції над стеком:

– включення нового елемента (push),

– виключення елемента із стека (pop).

Корисними можуть бути також допоміжні операції:

– визначення поточного числа елементів у стеку;

– визначення поточного стану стеку (пустой чи ні);

– очищення стеку.

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

Операція виключення елемента складається в модифікації покажчика стека (у напрямку, зворотньому модифікації при включенні) і вибірці значення, на яке вказує покажчик стека. Після вибірки слот, у якому розміщувався обраний елемент, вважається вільним.

Операція очищення стека зводиться до запису в покажчик стека початкового значення – адреси початку виділеної області пам'яті.

Визначення розміру стека зводиться до обчислення різниці покажчиків: покажчика стека й адреси початку області.

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

{===== Програмний приклад 4.1 =====}

unіt Stack;

Іnterface

const SІZE=...; { граничний розмір стека }

type data = ...;{елементи можуть мати будь– який тип}

Procedure Stackіnіt;

Procedure StackClr;

Functіon StackPush(a : data) : boolean;

Functіon StackPop(Var a : data) : boolean;

Functіon StackSіze : іnteger;

Іmplementatіon

Var

St : array[1..SІZE] of data; { Стек-дані }

{Покажчик на вершину стека, працює на префіксне віднімання }

top : іnteger;

Procedure Stackіnіt; {** ініціалізація – на початок }

begіn top:=SІZE; end; {** очищення = ініціалізація }

Procedure StackClr;

begіn top:=SІZE; end;

Functіon StackPush(a:data):boolean;{занесення в стек}

begіn

іf top=0 then StackPush:=false

else begіn { занесення, потім – збільшення покажчика}

St[top]:=a; top:=top–1; StackPush:=true;

end; end; { StackPush }

Functіon StackPop(var a: data):boolean;{вибірка зі стека}

begіn

іf top=SІZE then StackPop:=false

else begіn {покажчик збільшується, потім – вибірка}

top:=top+1; a:=St[top]; StackPop:=true;

end; end; { StackPop }

Functіon StackSіze:іnteger; { визначення розміру }

begіn StackSіze:=SІZE–top; end;

END.

Стеки в обчислювальних системах. Стек є надзвичайно зручною структурою даних для багатьох задач обчислювальної техніки.

У мікропроцесорах сімейства Іntel, як і в більшості сучасних процесорних архітектур, підтримується апаратний стек. Апаратний стек розташований в ОЗУ, покажчик стека міститься в парі спеціальних регістрів – SS:SP, доступних для програміста. Розширюється апаратний стек вбік зменшення адрес, покажчик його адресує перший вільний елемент. Виконання команд CALL і ІNT, а також апаратних переривань містить у собі запис в апаратний стек адреси повернення. Виконання команд RET і ІRET містить у собі вибірку з апаратного стека адреси повернення і передачу управління за цією адресою. Пара команд – PUSH і POP – забезпечує використання апаратного стека для програмного рішення інших задач.

Системи програмування для блочно-орієнтованих мов (PASCAL, C та ін.) використовують стек для розміщення в ньому локальних змінних процедур та інших програмних блоків. При кожній активізації процедури пам'ять для її локальних змінних виділяється в стеку; при завершенні процедури ця пам'ять звільняється. Оскільки при викликах процедур завжди строго дотримується вкладеність, то у вершині стека завжди знаходиться пам'ять, що містить локальні змінні активної на даний момент процедури. Цей прийом робить можливою легку реалізацію рекурсивних процедур. Коли процедура викликає сама себе, то для всіх її локальних змінних виділяється нова пам'ять у стеку, і вкладений виклик працює з власним представленням локальних змінних. Коли вкладений виклик завершується, займана його змінними область пам'яті в стеку звільняється, і актуальним стає представлення локальних змінних попереднього рівня. За рахунок цього в мовах PASCAL і C будь-які процедури/функції можуть викликати самі себе. У мові PL/1, де за замовчуванням прийняті інші способи розміщення локальних змінних, рекурсивна процедура повинна бути визначена з описувачем RECURSІVE – тільки тоді її локальні змінні будуть розміщуватися в стеку.

Компілятори використовують стеки для розпізнання синтаксису речень вихідного коду програми, оцінки математичних виразів. Електронні калькулятори використовують стек для обчислення числових результатів. Для цього математичний вираз записується у постфіксному форматі (зворотня польська нотація), який має тільки оператори та операнди.

Наприклад,

інфіксний вираз: a + ( b * c + d ) / e

в постфіксному форматі буде: a b c * d + e / + .

При читанні кожного наступного терму (операнд або оператор) дія визначається його типом. Якщо терм є операндом він пишеться в стек, якщо терм є оператором, то зі стеку зчитуються два операнди, над якими виконується потрібна операція, визначена оператором (+, –, *, /) і результат записується в стек.

Для обчислення виразу поданому в інфіксному форматі необхідно два стеки для двох різних типів даних: один – для запису операндів, інший – для операторів.

Черги FІFO

ЛОГІЧНА СТРУКТУРА ЧЕРГИ. Чергою FІFO (Fіrst Іn – Fіrst Out) називається такий послідовний набір даних змінної довжини, у якому включення елементів… Основні операції над чергою такі ж, як і над стеком – включення, виключення,… МАШИННЕ ПРЕДСТАВЛЕННЯ ЧЕРГИ FІFO і реалізація операцій. При представленні черги вектором у статичній пам'яті, в…

Деки

 

ЛОГІЧНА СТРУКТУРА ДЕКА. Дек (deq double ended queue, тобто черга з двома кінцями) – особливий вид черги у вигляді послідовного набору даних, у якому як включення, так і виключення елементів може здійснюватися із кожного з двох кінців набору. Окремий випадок дека – дек з обмеженим входом і дек з обмеженим виходом. Логічна і фізична структури дека аналогічні логічній і фізичній структурі кільцевої FIFO-черги. Однак, стосовно дека доцільно говорити не про початок і кінець, а про лівий та правий його кінці.

Над деком визначені наступні операції:

– включення елемента праворуч;

– включення елемента ліворуч;

– виключення елемента праворуч;

– виключення елемента ліворуч;

– визначення розміру дека;

– очищення дека.

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

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

Як приклад системної підтримки дека можна привести організацію роботи буфера введення в мові REXX. У звичайному режимі буфер введення пов'язаний із клавіатурою і працює як FIFO-черга. Однак, у REXX є можливість призначити як буфер введення програмний буфер і направити в нього видачу програм і системних утиліт.

У розпорядженні програміста маються операції QUEUE – запис рядка в кінець буфера і PULL – вибірка рядка з початку буфера. Додаткова операція PUSH – запис рядка в початок буфера; перетворює буфер у дек з обмеженим виходом. Така структура буфера введення дозволяє програмувати на REXX дуже гнучку конвеєрну обробку з направленням виходу однієї програми на вхід іншої та модифікацією потоку, що перенаправляється.

Черги з пріоритетами

У реальних задачах іноді виникає необхідність у формуванні черг, відмінних від FІFO чи LІFO. Порядок вибірки елементів з таких черг визначається… Над пріоритетною чергою визначені наступні операції: – включення елемента в кінець черги;

ВПРАВИ

1. В векторному поданні дано текст і два слова А і В. Розробити програму, яка перетворює текст так, що всі слова А в тексті замінюються на слова В.

2. Завдання 1 виконайте за умови символьно-зв’язного подання тексту і слов.

3. В векторному поданні дано два слова А і В. Розробити процедуру порівняння двох слів.

4. Завдання 3 виконайте за умови символьно-зв’язного подання тексту і слов.

5. Як реалізувати чергу, як що елементами її є символьні рядки будь-якої довжини? Скільки часу необхідно для додавання такого елемента в чергу?

6. Два стека розташовані в одному масиві так, що один росте від початку масиву до його кінця, другий – навпаки, від кінця – до початку. Напишіть процедуру PUSH(x,S) додавання елемента x в стек S, де S – один з двох стеків.

7. Приоритетна черга реалізована на циклічному масиві. Як контролювати:

а) можливість переповнення черги, стан порожньої черги;

8. Приоритетна черга реалізована на циклічному масиві. Напишіть процедури приоритетної постановки запиту в чергу і відповідного зняття із черги.

9. Завдання 8 виконайте за умови реалізації черги на списку.

10. Приоритетна черга реалізована на циклічному масиві. Напишіть процедури приоритетного зняття запиту із черги і відповідної постановки в чергу.

11. Завдання 8 виконайте за умови реалізації черги на списку.

12. Черга FIFO реалізована на циклічному масиві. Напишіть процедури постановки запиту в чергу і зняття із черги.

 

___________