Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Мета: Ознайомитися з роботою алгоритмів використання «черги».






Лабораторна робота №2

Тема: Робота з елементами черги.

Мета: Ознайомитися з роботою алгоритмів використання «черги».

Теоретичні відомості

Чергою називається структура даних, організована за принципом «першим прийшов – першим пішов»

Черга, так само як і стек, відображається на пам’ять комп’ютера у вигляді одновимірного масиву.

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

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

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

аі: = аі+1 для і=1, 2…

Зрозуміло, що така схема обробки операції читання забирає багато часу. Для його економії застосуємо ідею читання елементу зі стеку. Тобто після читання елемента не будемо намагатися знищити його значення, а просто перемістимо індекс початку черги на наступний елемент. Таким чином ми приходимо до ідеї існування двох індексів: і- початок черги, що носить назву «голова черги», та j – кінець черги, що називається «хвостом» черги.

Запишемо основні алгоритми роботи з елементами черги на Pascal. Врахуємо, що запис у чергу буде неможливий, тобто черга переповнена, коли «хвіст» досягне останнього елемента масиву, а читання стане неможливим, коли черга порожня, коли «голова» пережене «хвіст».

Процедура читання черги:

Procedure read_from_queue;

Begin

If j< =0 then writeln('Queue is empty')

Else

Begin

Writeln(a[1]);

for k: =1 to j-1 do

a[k]: =a[k+1];

a[j]: =0;

dec(j);

end;

End;

Процедура запису елементу в чергу:

Procedure write_from_queue;

Begin

If j=n then writeln('Queue is full')

Else

Begin

Inc(j);

Readln(a[j]);

End;

End;

Процедура перегляду елементів черги можна записати в такому вигляді:

Procedure print_quele;

Var k: word;


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал