Зміст

Вступ 3

Глава 1. Динамічні типи даних 6

1.1 Списки. Черга. Стек. Груд. 6

1.2 Динамічні інформаційні структури 22

Глава 2. Розробка факультативного курсу «Динамічні типи даних» 29

2.1 Методичні рекомендації щодо впровадження факультативного курсу в школі 29

2.2 Розробка програмного засобу за темою «Динамічні типи даних» 38 < p> Висновок 42

Література 44

Додаток 1. (Лістинг програми) 45

Введення

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

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

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

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

У простій формі таблиця може бути лінійним списком елементів.
Тоді властиві їй структурні властивості містять у собі відповіді на такіпитання, як: "Який елемент є першим в списку? який - останнім?який елемент передує даному або слідує за даними? "Можна багатоговорити про структуру навіть у цьому випадку абсолютно очевидний.

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

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

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

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

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

Предмет дослідження: Вивчення динамічних інформаційних структур.

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

Досягненням цілі і відповідно до поставленої гіпотези визначаютьсянаступні завдання:
1. Вивчити літературу по темі динамічні інформаційні структури, педагогічну і методичну за темою дослідження;
2. Проаналізувати види динамічних інформаційних структур;
3. Розробити факультатив за темою дослідження;
4. Розробити програмний продукт за темою дослідження.

Глава 1. Динамічні типи даних

1.1 Списки. Черга. Стек. Груд.

Список (list) - набір елементів, розташованих у певному порядку.
Таким набором може бути ряд знаків у слові, слів у пропозицій у книзі.
Цей термін може також відноситися до набору елементів на диску.
Використання при обробці інформації списків як типів данихпризвело до появи в мовах програмування засобів обробки списків.

Список черговості (pushup list) - список, у якому останнійвступник елемент додається до нижньої частини списку.

Список з використанням покажчиків (linked list) - список, у якомукожен елемент містить вказівник на наступний елемент списку.

Лінійний список (linear list) - це безліч, що складається звузлів, структурні властивості якого по суті обмежуються лишелінійним (одновимірним) відносним становищем вузлів, тобто тими умовами,що якщо, то є перший вузлом; якщо, то k-му вузлу
 передує і за ним слід; є останнімвузлом.

Операції, які ми маємо право виконувати з лінійними списками,включають, наприклад, такі:
1. Отримати доступ до k-го вузла списку, щоб проаналізувати та/або змінити вміст його полів.
2. Включити новий вузол безпосередньо перед k-м вузлом.
3. Виключити k-й вузол.
4. Об'єднати два (або більше) лінійних списку в один список.
5. Розбити лінійний список на два (або більше) списку.
6. Зробити копію лінійного списку.
7. Визначити кількість вузлів у списку.
8. Виконати сортування вузлів списку у зростаючому порядку за деякими полях у вузлах.
9. Знайти в списку вузол із заданим значенням в деякому полі.

Спеціальні випадки k = 1 та k = n в операціях (1), (2) і (3) особливовиділяються, оскільки в лінійному списку простіше отримати доступ до першого іостанньому елементів, ніж до довільного елементу.

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

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

Багато людей зрозуміли важливість стеків і черг і дали інші назвицим структурам; стек називали пуш-даун (push-down) списком, реверсивноїпам'яттю, гніздовий пам'яттю, магазином, списком типу LIFO ( "last-in-first -out "-" останнім включається - перший виключається ") і навіть вживаєтьсятакий термін, як список йо-йо! Черга іноді називають - циклічноїпам'яттю або списком типу FIFO ( "first-in-first-out" - "перший включається --перший виключається "). Протягом багатьох років бухгалтери використовували терміни
LIFO і FIFO як назви методів при складанні прейскурантів. Ще одинтермін "архів" застосовувався до декам з обмеженим виходом, а деки зобмеженим входом називали "переліками", або "реєстрами". Такерізноманітність назв цікаво само по собі, Оскільки воно свідчитьпро важливість цих понять. Слова "стек" і "черга" поступово стаютьстандартними термінами; з усіх інших словосполучень, перерахованих вище,лише "пуш-даун список" залишається ще досить поширеним, особливо втеорії автоматів.

При описі алгоритмів, що використовують такі структури, прийнятаспеціальна термінологія; так, ми розміщуємо елемент на верх стека абознімаємо верхній елемент. Внизу стека знаходиться найменш доступний елемент,і він не видаляється до тих пір, поки не будуть виключені всі інші елементи.
Часто кажуть, що елемент опускається (push down) в стек або що стекпіднімається (pop up), якщо виключається верхній елемент. Ця термінологіябере свій початок від "стеків" закусок, які можна зустріти вкафетеріях, або за аналогією з колодами карт в деяких перфораторнихпристроях. Стислість слів "опустити" і "підняти" має свою перевагу,але ці терміни помилково припускають рух всього списку в пам'яті машини.
Фізично, однак, нічого не опускається; елементи просто додаютьсязверху, як при стогованіі сіна або при укладанні стоси коробок. У застосуваннідо черг ми говоримо про початок і кінець черги; об'єкти стають в кінецьчерги і віддаляються в момент, коли нарешті досягають її початку. Говорячи продеках, ми вказуємо лівий і правий кінці. Поняття верху, низу, початку ікінця застосовується іноді й до декам, якщо вони використовуються як стеки абочерги. Не існує, однак, будь-яких стандартних угодщодо того, де має бути верх, початок і кінець: ліворуч або праворуч.
Таким чином, ми знаходимо, що в наших алгоритмах застосовується багатерізноманітність описових слів: "зверху - вниз" - для стеков, "зліва --направо "- для деков і" очікування в черзі "- для черг.

Однонаправлений і двонаправлений список - це лінійний список, вякому всі винятки і додавання відбуваються в будь-якому місці списку.

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

На малюнку видно як додається і віддаляється елемент здвонаправленого списку. При додаванні нового елементу (позначений N) міжелементами 2 і 3. Зв'язок від 3 йде до N, а від N до 4, а зв'язок між 3 і 4видаляється.

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

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

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

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

Правило тут таке ж, як в живій черзі: перший прийшов-першеобслужений. Прийшов новий покупець, встав (додався) в кінець черги, аякий вже отоварився пішов (вийшов) з початку черги. Тобто першаприйшов, перший пішов.

Іншими словами, у черги є голова (head) та хвіст (tail). Елемент,додається до черги, опиняється в її хвості, як тільки що підійшовпокупець; елемент, що видаляється з черги, знаходиться в її голові, як тойпокупець, що відстояв довше за всіх.

У черзі новий елемент додається тільки з одного кінця. Видаленняелемента відбувається на іншому кінці. У даному випадку це може бути тільки
4 елемент. Черга по суті односпрямований список, тільки додавання івиключення елементів відбувається на кінцях списку.

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

Стек - частина пам'яті ОЗП комп'ютера, яка призначається длятимчасового зберігання байтів, що використовуються мікропроцесором; при цьомувикористовується порядок запам'ятовування байтів «останнім увійшов - першим вийшов»,оскільки такі введення і виведення організовувати простіше за все, також операціїздійснюються дуже швидко. Дії зі стеком проводиться за допомогоюрегістра покажчика стека. Будь-яке ушкодження цій частині пам'яті призводить дофатального збою.

Стек у вигляді списку (pushdown list) - стік, організований такимчином, що останній вводиться в область пам'яті елемент розміщується навершині списку.

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

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

Уявіть собі, що чотири залізничні вагони знаходяться навхідній стороні колії (рис. 1) і перенумеровані відповідно 1, 2, 3 і 4.
Припустимо, що ми виконуємо наступну послідовність операцій
(які узгоджуються з напрямом стрілок на малюнку і не вимагають, щобвагони "перестрибували" один через одного). Відішліть:
| (а) вагон 1 в стек; | (е) вагон 4 в стек; |
| (b) вагон 2 в стек; | (f) вагон 4 на вихід; |
| (с) вагон 2 на вихід; | (g) вагон 3 на вихід; |
| (d) вагон 3 в стек; | (h) вагон 1 на вихід. |

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

У стеку елемент додається і видаляється тільки з одного кінця. Намалюнку це елемент N. Тобто якщо він додався, то віддаляється можеспочатку тільки він, а вже потім всі інші.

Стек можна уявити собі як коробку, в яку складають якісьнебудь предмети, щоб дістати самий нижній потрібно попередньо витягтиінші. Стек можна уподібнити стосі тарілок, з якої можна взятиверхню і на яку можна покласти нову тарілку. [Інша назва стека вросійській літературі - «магазин» - зрозуміло кожному, хто розбирав автомат
Калашнікова].

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

Іноді аналогія з перемиканням залізничних шляхів, запропонована Е.
Дейкстра, допомагає зрозуміти механізм стека. На рис. 2. Зображено грудня у виглядізалізничного роз'їзду.

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

У деки всі винятки і додавання відбуваються на обох його кінцях. Груденьпо суті двонаправлений список.

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

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

Іншими словами, елемент двосторонньо пов'язаного списку (doubly linkedlist) - це запис, що містить три поля: key (ключ) і два вказівника - next
(наступний) і prev (від previous-попередній). Крім цього, елементи спискуможуть містити додаткові дані. Якщо х - елемент списку, то nextвказує на наступний елемент списку, а prev - на попередній. Якщоprev (х) = nil, то в елемента х немає попереднього: це голова (head) списку.
Якщо next (х) =nil, то х - останній елемент списку або, як кажуть, йогохвіст (tail).

Перед тим, як рухатися за вказівниками, треба знати хоча б один елементсписку. У різних ситуаціях використовуються різні види списків. Уоднобічно зв'язаному (singly linked) списку відсутні поля prev. Уупорядкованому (sorted) списку елементи розташовані в порядку зростанняключів, так що у голови списку ключ найменший, а у хвоста списку --найбільший, на відміну від неупорядкованого (unsorted) списку. У кільцевомусписку (circular list) поле prev голови списку вказує на хвіст списку, аполе next хвоста списку вказує на голову списку.

Якщо інше не обумовлено, то під списком ми будемо розумітинеупорядкований двосторонньо пов'язаний список.

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

Тут А, В, С, D і Е-довільні комірки в пам'яті, а Л - порожнязв'язок. Програма, в якій використовується така таблиця, мала б, у випадкупослідовного розподілу, додаткову змінну або константу,значення якої показує, що таблиця складається з п'яти елементів; цю жінформацію можна задати за допомогою ознаки кінця ( "прикордонника"), забезпечившиїм елемент 5 або наступну комірку, У випадку пов'язаного розподілу впрограмі є мінлива зв'язку або константа, яка вказує на А, авирушаючи від А, можна знайти всі інші елементи списку.

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

Тут FIRST - мінлива зв'язку, яка вказує на перший вузол в списку.

Тепер ми можемо зіставити ці дві основні форми зберіганняінформації:

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

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

3) Якщо використовується пов'язана схема, то легко включити елемент усписок. Наприклад, щоб включити елемент у (1), необхідно змінитилише два зв'язку:

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

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

5) При використанні схеми зі зв'язками спрощується завдання об'єднаннядвох списків або розбиття списку на частини.

6) Схема зі зв'язками годиться для структур складніших, ніж простілінійні списки. У нас може бути змінна кількість списків, розміряких непостійний; будь-який вузол одного списку може бути початком іншогосписку; в один і той же час вузли можуть бути об'єднані в кількапослідовностей, що відповідають різним спискам, і т.д.

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

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

У наступних кількох прикладах ми будемо заради зручності припускати,що вузол - це одне слово і що воно розділене на два поля INFO і LINK:

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

Циклічний кільце або список (circular list або ring) - файл, уякого немає певного початку і кінця, кожен елемент файлу міститьвказівник на початок наступного елементу; при цьому «останній» елементвказує на «перший», так що до списку можна звернутися з будь-якого елемента.

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

Припустимо, у вузлах є два поля: INFO і LINK. Змінна зв'язку
PTR вказує на самий правий вузол списку, a LINK (PTR) є адресоюнайлівішого вузла.

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

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

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

При посиланні на списки замість вказівника на правий кінець спискувикористовується зазвичай голова списку, яка часто перебуває у фіксованійкомірці пам'яті.

Як приклад використання циклічних списків розглянемоарифметичні дії над многочленами від змінних х, у и z з цілимикоефіцієнтами. Існує багато задач, в яких математик за кращепрацювати з многочленами, а не просто з числами; мова йде про операції,подібних множенню

на,що дає в підсумку

.

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

1.2 Динамічні інформаційні структури

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

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

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

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

Значенням покажчика є адреса комірки, починаючи з якої будерозміщена в пам'яті відповідна динамічна величина.

На цій схемі р. - Ім'я покажчика; зірочкою зображено значенняпокажчика, а стрілка відображає той факт, що значенням вказівника єадреса об'єкта (посилання на об'єкт), за допомогою якого об'єкт і доступний впрограмі.

У деяких випадках виникає необхідність у якості значенняпокажчика прийняти «порожню» посилання, що не пов'язує з покажчикомніякого об'єкта. Таке значення в Паскалі задається службовим словом nil іналежить будь-якому посилальної типу. Результати виконання оператора p: = nilможна зобразити таким чином:

Процедура new (i) виконує дві функції:

1) резервує місце в пам'яті для розміщення динамічного об'єктавідповідного типу з ім'ям i;

2) вказівником i привласнює адресу динамічного об'єкта i.

Однак, дізнатися адресу динамічної змінної за допомогою процедуриwriteln (i) не можна.

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

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

Якщо в процесі виконання програми деякий динамічний об'єкт р ^,створений в результаті виконання оператора new (p), стає непотрібним, тойого можна знищити (очистити виділену йому місце в пам'яті) за допомогоюстандартної процедури dispose (p). В результаті виконання оператора видуdispose (p) динамічний об'єкт, на який вказує посилальна мінливар, припиняє своє існування, займане ним місце в пам'яті стаєвільним, а значення покажчика р стає невизначеним (але не рівнимnil).

Якщо до виклику процедури dispose (p) мав порожнє значення nil, то цепризведе до «зависання» програми.

Якщо ж до виклику цієї процедури покажчик р. не було визначено, то цеможе призвести до виходу з ладу операційної системи.

Значення одного покажчика можна присвоїти іншому вказівником того жтипу. Можна також покажчики однакового типу порівнювати один з одним,використовуючи відносини «=» або «о».

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

, пов'язані списки даних. Не дивлячись на багатий набір типів даних в
Паскалі, він не вичерпує всього практично необхідного для розробкибагатьох видів програм. Зокрема, з різноманітних пов'язаних структурданих в мові стандартизовані масиви та файли, а крім них можутьзнадобитися і схожі з ними, але інші структури. Для них характерні, взокрема, такі ознаки: а) невизначений заздалегідь число елементів; б) необхідність зберігання в оперативній пам'яті.

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

Інша подібна структура - стек. Його моделлю може служити трубка ззапаяним кінцем, до якої вкочували кульки. При цьому реалізується принцип
«Останнім увійшов - першим вийшов». Можлива кількість елементів в стеку НЕфіксовано.

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

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

(елементу, який прийшов першим, посилатися не на що, про щосвідчить «порожня посилання» nil).

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

Type

List = ^ Spisok; - Однонаправлений

Spisok = record

Info: Integer; - Інформаційне поле

Next: List; - Посилання на наступний елемент end;

ListTwo = ^ SpisokTwo; - Двонаправлений

SpisokTwo = record

Info: Integer; - Інформаційне поле

Next: ListTwo; - Посилання на наступний елемент

Prev: ListTwo; - Посилання на попередній елемент end;

Створення спискуprocedure CreateLists; - процедура створення спискуbegin

X: = Random (101); Визначаємо значення першого елемента

Uk: = nil; вказівниками присвоюємо nil. q: = nil;
AddToList (X, Uk); Додаємо елемент Х в список.q: = Uk; Формуємо покажчик на початок списку.for i: = 1 to 9 do Додаємо залишилися елементи до списку. begin

X: = Random (101);

AddToList (X, q); end;

ListBegin: = Uk; Визначаємо покажчик списку. end;

Знищення спискуprocedure DestroyList (PointerBegin: List); Процедура знищення списку
(PointerBegin - покажчик на початок списку).begin while PointerBegin nil do Якщо вказівник не nil, то begin q: = PointerBegin;

PointerBegin: = PointerBegin ^. Next; Посилання на наступний. if q nil then Dispose (q); Знищення. end;end;

Додавання елемента до спискуprocedure AddToList (X: Integer; var PointerEndList: List);
Додати елемент в кінець списку
(PointerEndList - покажчик на останній елеменB? Списку)begin if PointerEndList = nil then
Якщо перший елемент ще не існує або список порожній, то begin

New (PointerEndList); Створюємо нову змінну

PointerEndList ^. Info: = X ; Інф. Частини присвоюємо елем. Х

PointerEndList ^. Next: = nil; посилання на такі - nil end else інакше додаємо до списку begin

New (PointerEndList ^. Next); Створюємо новую посилання

PointerEndList: = PointerEndList ^. Next;
Вказівником привласнити посилання на слід. елемент

PointerEndList ^. Info: = X;

PointerEndList ^. Next: = nil; end;end;

Видалення елемента зі списку.procedure DeleteFromList (Position: Integer);
Видаляє елемент під номером Positionbegin q: = ListBegin; Привласнюється посилання на перший елемент if q nil then Якщо список не порожній, тоbegin if Position = 0 then Якщо позиція = 0, то видаляємо перший елемент begin

ListBegin: = q ^. Next; if q nil then Dispose (q); endelse begin i: = 0; while (i

Шукаємо елемент після якого потрібно видалити begin q: = q ^. Next;

Inc (i); end; r: = q ^. Next; if r nil then Якщо видаляється елемент існує, товидаляємо його begin q ^. Next: = r ^. Next; if r nil then Dispose (r); end end;endend;

Глава 2. Розробка факультативного курсу «Динамічні типи даних»

2.1 Методичні рекомендації щодо впровадження факультативного курсу в школі

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

Розроблений нами факультатив розрахований на 14 годин.
Завдання факультативу:
1) Ввести поняття лінійного списку, однонаправленої і двонаправленого списку, циклічного списку, стека, дека і черги;
2) Сформувати пізнавальний інтерес в учнів до інформатики;
3) Розвинути в учнів творчі здібності .

Мета першого уроку - дати учням на якісному рівні необхіднупідготовчий матеріал, який включає в себе:
1) Визначення лінійного списку.
2) Операції зі списками.
3) Види списків.
4) Пов'язане розподіл.
5) Динамічні змінні.

На 2 - 6 уроках учні знайомляться зі списками більш глибше. Сьомийурок підсумковий. Учням пропонується тестова програма, в якій вонивідповідають на питання і оцінюють результати отриманих знань. У цілому жфакультатив розрахований на сім двох годинних занять.
Загальна структура факультативу така:
| № уроку | Тема | Кількість |
| | | Годин |
| № 1. | Списки | 2 |
| № 2. | Однонаправлений і двонаправлений список | 2 |
| № 3. | Циклічний список | 2 |
| № 4. | Черга | 2 |
| № 5. | Стек | 2 |
| № 6. | Грудень | 2 |
| № 7. | Тест | 2 |

Конспекти уроків

Тема: «Черга»

Цілі:
1. Розкрити поняття лінійного списку «Черга».
2. Навчитися використовувати «Черга» на практиці при розв'язанні задач.
3. Сформувати в учнів пізнавальний інтерес до інформатики.
| № | Етап уроку | Час (хв) |
| 1. | Організаційний момент | 2 |
| 2. | Підготовка до лабораторної роботи | 10 |
| 3. | Виконання лабораторної роботи | 20 |
| 4. | Закріплення | 8 |

Лабораторна робота № 4 за темою «Черга».

1. Натисніть кнопку "Теорія" для черги.

Уважно вивчіть теоретичний матеріал.
2. Натисніть кнопку "Обновити" для формування списків.

Кнопки ">" служать для переміщення курсору по черзі. а) переміститься вправо до 3 елементи; б) переміститеся вліво (див. коментарі);

Кнопка "Додати" служить для додавання елемента в чергу. а) Додайте 1, 4, 5-м елементами число 99; б) Додайте останнім число 999;

Кнопка "Видалити" служить для видалення елемента з черги.

Видаліть 1, 2 , 3 матеріалів;
3.