Зразок діалогової програми

Лабораторна робота №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;

If j>0 then

for k:=1 to j do

write(a[j],' ')

else write('Queue is empty' );

End;

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

Хід роботи

1. Завантажте середовище програмування. Відкрийте новий файл та збережіть його з назвою quele_(буква вашого класу(англ.)).

2. Розробити діалогову меню-орієнтовану програму роботи з елементами черги за такими пунктами:

1) Записати елемент у чергу

2) Прочитати елемент з черги;

3) Показати вміст черги;

4) Показати вміст масиву

5) Завершити роботу з чергою.

Зразок діалогової програми додається. Наберіть її та доповніть потрібними процедурами.

3. Протестуйте програму для n=6 та 10 за такими пунктами:

Ø Заповніть чергу двома-трьома елементами;

Ø Спорожніть чергу;

Ø Заповніть чергу трьома елементами;

Ø Виведіть вміст черги на екран;

Ø Виведіть вміст масиву на екран.

Ø Заповніть чергу шістьма елементами;

Ø Вичитайте з черги шість елементів;

Ø Прочитайте сьомий елемент черги.

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

4. Код програми перепишіть в зошит та доповніть потрібними коментаріями.

5. Дайте відповіді на контрольні запитання.

Зразок діалогової програми

uses cRT;

const n=6;

var ch:char;

i,j:word;

a:array[1..20] of integer;

Procedure read_from_queue;

Begin

…

End;

Procedure write_from_queue;

Begin

…

End;

Procedure print_quele;

Var k:word;

Begin

…

End;

procedure print_mas;

var k:word;

Begin

for k:=1 to n do write(a[k], ' ');

end;

{-----------Golovna programa--------}

Begin

clrscr;

ch:='0';i:=0; j:=0;

While ch<>'5' do

Begin

writeln('1. Zapus elementa y queue');

writeln('2. Prohutatu element z queue');

writeln('3. Pokazatu vmist queue');

writeln('4. Pokazatu vmist masuvy');

writeln('5. zaverchutu poboty si queue');

writeln;

write('Vvedite N menu - '); readln(ch);

Case ch of

'1':write_from_queue;

'2':begin read_from_queue;; writeln('ENTER');readln(ch); end;

'3':begin print_quele;;writeln('ENTER');readln(ch); end;

'4':begin print_mas;writeln('ENTER');readln(ch) end;

'5': exit;

end;

end;

End.

Контрольні запитання

1. Яка структура називається чергою?

2. Як структура даних «черга» відображається на пам’ять комп’ютера?

3. Який елемент називають «головою» черги?

4. Який елемент називають «хвостом черги?

5. Як відбувається читання елементів черги? Запишіть алгоритм читання елемента черги.

6. Як відбувається запис елементів у чергу? Запишіть алгоритм запису елемента в чергу.

7. Зобразіть схематично роботу з елементами черги.

8. Запишіть процедуру перегляду елементів черги.

9. Який принцип доступу здійснюється до значень елементів черги при їх обробці? Обґрунтуйте свою відповідь.