Урок 01                                                                                                Інформатика 11 (АП)

Структури даних:

проста змінна, масив, стек.

Мета.

Навчальна. Ввести поняття структури данних, поняття проста змінна, масив, стек.

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

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

Тип уроку. Засвоєння нових знань і навичок.

Матеріали для роботи з учнями:

Інформатика: Методи побудови алгоритмів та їх аналіз. Необчисл. алгоритми: Навч. посіб. для 9-10 кл із поглибл. вивч. інформатики. - К.: Генеза, 2007.

Мультимедійне обладнання.

План

• Організація класу.
• Введення в тему.
• Мотивація навчальної діяльност.
• Структури даних: проста змінна, масив, стек.
• Практичні завдання.
• Типові запитання до уроку.
• Домашнє завдання.

Пам’ятка для учня!

• Пригадайте правила техніки безпеки при роботі з ПК.
• Через кожні 15 хв. виконуйте вправи для очей та для зняття м’язової втоми.

Хід уроку

1. Організаційний момент.

2. Актуалізація опорних знань.

1. Що таке інформація?
2. Як можна представляти інформацію?
3. Навіщо потрібний алгоритм?

3. Мотивація навчальної діяльності.

Основним завданням будь-якого алгоритму є обробка інформації. Яким чином представити інформацію? Адже від зручно­го способу її представлення залежить і зручність обробки.

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

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

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

4. Структури даних: проста змінна, масив, стек.

Структура даних - це спосіб представлення інформації.

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

Деякі структури даних визначаються безпосередньо в мовах програмування, які ми використовуємо для реалізації алгорит­мів. Наприклад, ви вже знайомі з простими змінними, масива­ми. А деякі організовуються самими розробниками алгорит­мів. Саме з ними ми маємо ознайомитися в цьому розділі.

Можна сказати, що структури даних є одним з інструментів розробки алгоритмів. Багато відомих методів алгоритмів ба­зуються на тих чи інших структурах.

Ознайомлюючись із структурами даних, ми, в першу чергу, будемо виділяти два такі важливі моменти:

• відображення структури даних на пам’ять комп’ютера;
• обробка інформації в даній структурі.

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

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

Якщо до будь-якого елемента заданої структури можна дістатися, не переглядаючи всі, то такий доступ називають пря­мим. У протилежному випадку - послідовним.

ПРОСТА ЗМІННА

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

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

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

При виконанні дій, робота яких пов’язана із записом зна­чення змінної у відповідну область пам’яті, тобто стандартних процедур read, readln та оператора присвоювання змінній деякого значення, відбувається визначення адреси, що відпові­дне розміщенню значення даної змінної в пам’яті комп’ютера і напис указаного двійкового значення за цією адресою.

Виконання операції читання значення простої змінної від­бувається при використанні стандартних процедур write, writeln та обчислення значень виразів, у яких використовують­ся ідентифікатори цих змінних. При цьому система «знає» ндресу розміщення в пам’яті значення цієї змінної і «читає» його за цією адресою. Далі відбувається процес декодування двійкового зображення інформації, що відповідає правилу її кодування згідно з указаним для цієї змінної типом.

Можна зробити висновок, що прості змінні є структурою прямого доступу.

МАСИВ

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

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

Спершу нагадаємо, що пам’ять комп’ютера є дискретною і мас лінійну структуру. Тобто, всі комірки пам’яті мають абсо­лютні адреси, що починаються з 0. Для зручності адреси комі рок пам’яті комп’ютера представляють шістнадцятковими числами: 0, 1, 2, ..., 9, А, В, С, D, Е, F, 10, ..., FF, ... .

Саме тому відображення елементів одновимірного масиву на пам’ять комп’ютера уявити собі зовсім нескладно: вони запи­сані в пам’ять підряд, починаючи з деякого визначеного місця.

При розташуванні масиву а1, а2, ..., аn у пам’яті комп’ютера визначається адреса його початку, тобто першого елемента масиву а1, і далі розміщуються всі елементи, займаючи кож­ний стільки байтів, скільки визначено вказаним типом. Тобто, система «знає» адресу першого елемента масиву, скільки байтів займає кожний елемент і загальну кількість елементів масиву.

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

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

Можемо також зробити висновок, що структура даних «масив» є, як і проста змінна, структурою прямого доступу.

Розташування елементів двовимірного масиву аij, де і = 1, 2, ..., n; j = 1, 2,,..., m  у пам’яті комп’ютера відбувається так:

cпочатку розміщуються елементи першого рядка, потім друго­го і т. д.

Tак само як і для одновимірного масиву, при визначенні міс­ця розташування елементів двовимірного стає відомою адреса першого елемента. Адреса будь-якого іншого елемента аij цього масиву визначається за алгоритмом:

<адреса аij> = <адреса а11> + ((і - 1) •mт + j - 1) •<скількість байтів указаного типу>.

Тобто для визначення адреси поточного елемента двови­мірного масиву потрібно до адреси першого елемента додати кількість байтів, яку займає один елемент указаного типу, по­множену на кількість елементів двовимірного масиву (і - 1) • m + j — 1, що розміщені в пам’яті комп’ютера від першого еле­мента до даного аij.

Елементи масивів більшої вимірності розміщуються в па­м'яті комп’ютера аналогічно.

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

СТЕК

Стеком називається структура даних, що організована за принципом «останнім прийшов — першим пішов».

З поняттям стека ми вже зустрічалися при ознайомленні і алгоритмом роботи рекурсії.

Ми домовилися розглядати структури даних у відображенні на пам’ять комп’ютера. Тому в першу чергу треба визначи­тися, яким чином елементи даної структури зберігаються в пам’яті.

Оскільки організація одновимірного масиву аналогічна лінійній структурі пам’яті комп’ютера, то логічним буде представлення стека саме у вигляді одновимірного масиву (мал. 5).

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

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

Обробляючи елементи масиву, ми вводимо поняття поточно­го порядкового номера елемента масиву і. В даному випадку нас цікавитиме лише останній елемент: ми його або зчитуємо (), або після нього записуємо новий елемент ().

Індекс останнього елемента стека називається вершиною. Це означає, що для обробки елементів стека нам достатньо знати значення лише однієї величини і вершини стека. Схематично стек можна зобразити так (мал. 6):

Подвійною стрілкою () ми позначили елемент вершини стека, який доступний як для читання, так і для запису, а сі­рим кольором - ті елементи масиву, які належать стеку. Нижня стрілка() показує зміну розміру стека в межах визначеного масиву.

Алгоритм запису нового елемента х у стек виглядатиме так:

i:=i+1;

ai:= х.

Tобто ми спочатку збільшуємо значення вершини стека на 1, a потім елементу масиву з індексом і присвоюємо значення х.

Алгоритм читання чергового елемента стека буде таким:

x:= аi;

i:=i-1.

Пояснимо цей алгоритм: спочатку значення елемента стека, що знаходиться на його вершині і, читаємо в х, а потім змен­шуємо значення вершини стека на 1.

Тепер, коли ми визначили операції для роботи з елементами і ті-ка, обов’язково треба зауважити таке.

Для швидкодії роботи зі стеком не витрачається час на «знищення» елементів стека, які вже «вичитано». Доступ до цих елементів утрачається лише за рахунок зміни значення вершини стека (і - 1). Таким чином, у масиві лишається «сміття». При наступному «попаданні» на ці елементи в масиві під час виконання операції запису туди будуть записані нові зна­чення.

Розглянемо тепер реалізацію цих алгоритмів мовою Pascal. Перш за все треба обговорити критичні ситуації, які можуть виникнути при читанні та записі інформації. А саме: при чи­танні може виникнути ситуація, коли вже читати немає чого, тобто стек порожній, а при записі — стек переповнений, тобто досягнуто останнього елемента масиву, оскільки, описуючи масив у програмі, ми повинні вказати межі зміни його індексу. Процедура читання зі стека:

procedure read_from_stack;

begin

if і = 0 then writeln(’Стек пустий’)

else

    begin

writeln(a[i]);

dec(i)

    end

end;

Логічним є твердження, що на початку роботи програми з обробки елементів стека вершина стека повинна мати значен­ня 0, оскільки в початковому стані дозволена лише операція запису в стек.

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

procedure writetostack;

begin

if і > = n then writeln(’Стек повний’)

else

     begin

inc(i)

readln(a[i]);

     end

end;

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

procedure print_stack;

var k: word;

begin

for k := 1 to і do

write(a[k], ”);

        writeln

end;

Корисною також є інформація про вміст усього масиву, від­веденого для організації стека, під час обробки елементів стека. Саме при виконанні цієї процедури можна спостерігати за появою «сміття» в масиві та заміною його на нові значення при виконанні операції запису в стек.

procedure printmas;

var і: word;

begin

for і := 1 to n do

write(a[i], ’ ’);

         writeln

                    end;

Нам залишилося ще визначитися з принципом доступу до елементів даної структури. Робота зі стеком зводиться до об­робки вершинного елемента, який доступний завжди, а решта елементів - ні. Щоб зробити доступним деякий елемент ак (k < і), треба спочатку вичитати зі стека всі елементи, що зна­ходяться вище від нього, зробивши таким чином даний еле­мент вершиною стека.

Тому можна зробити висновок: структу­ра даних «стек» є структурою послідовного доступу.

5. Типові питання до уроку 

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. Який принцип доступу здійснюється до значень елементів стека при їх обробці? Обґрунтуйте свою відповідь.

6. Розв’язування задач.

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

1)      записати елемент у стек;

2)      прочитати елемент зі стека;

3)      показати вміст стека;

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

5)      завершити роботу зі стеком.

2.      Протестувати програму завдання 1 для масиву розмірністю п 5, спостерігаючи за вмістом стека та масиву, за такою схемою:

-заповнити повністю стек;

-спорожнити стек;

-заповнити стек до половини;

-вичитати один елемент;

-записати два елементи.

3.      Зробити письмовий аналіз виконання завдань 1,2.

7. Підсумки уроку.

7. Домашнє завдання.

1. Вивчити конспект.

2. Підготуватися до тестування.

3. Виконати завдання 1.