Линейные списки.
Стік. Груд.
Очередь

РефератДопомога в написанніДізнатися вартістьмоєї роботи

Линейные списки. Стік. Груд. Очередь (реферат, курсова, диплом, контрольна)

Запровадження 3.

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

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

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

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

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

2.2 Розробка програмного кошти на тему «Динамічні типи даних» 38.

Заключение

42.

Література 44.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1 Списки. Черга. Стік. Дек.

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

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

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

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

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

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

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

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

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

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

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

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

На малюнку видно як додається і видаляється елемент з двунаправленного списку. При додаванні нового елемента (вказано N) між елементами 2 і трьох. Зв’язок від 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. Зображено груд як залізничного разъезда.

[pic].

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

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

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

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

Інакше кажучи, елемент двусторонне пов’язаного списку (doubly linked list) — це запис, яка містить три поля: key (ключ) і двоє покажчика — next (наступний) і prev (від previous—предыдущий). До того ж, елементи списку можуть утримувати додаткові дані. Якщо x — елемент списку, то next свідчить про наступний елемент списку, а prev — на попередній. Якщо prev{х}=nil, те в елемента x немає попереднього: це голова (head) списку. Якщо next{х}= nil, то x — останній елемент списку чи, кажуть, його хвіст (tail).

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

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

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

Тут А, У, З, D та О— довільні осередки у пам’яті, а Л — порожня зв’язок. Програма, у якій використовується така таблиця, було б, у разі послідовного розподілу, додаткову зміну чи константу, значення показує, що таблиця складається з п’ятьох елементів; цю інформацію можна поставити з допомогою ознаки кінця («прикордонника »), забезпечивши їм елемент 5 чи таку осередок, Що стосується пов’язаного розподілу є у програмі є змінна зв’язку чи константа, яка визначає на А, а вирушаючи від А, можна знайти інші елементи списка.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[pic] на [pic], що дає в итоге.

[pic].

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

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

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

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

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

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

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

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

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

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

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

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

Проте, дізнатися адресу динамічної перемінної з допомогою процедури writeln (і) нельзя.

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

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

Якщо у процесі виконання програми певний динамічний об'єкт р^, створений результаті виконання оператора 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 і := 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); Видаляє елемент під номером Position begin q := ListBegin; Присвоюється посилання перший елемент if q nil then Якщо список не порожній, то begin if Position = 0 then Якщо позиція = 0, то видаляємо перший елемент begin.

ListBegin := q^. Next; if q nil then Dispose (q); end else begin і := 0; while (і < Position — 1) and (q nil) do.

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

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

Глава 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. На аркуші формату А4, опишіть хід виконану работы.

Скажіть на поставлені вопросы:

1) Як видаляється й додають елементи в очереди?

2) У чому відмінність і подібність черзі й односпрямованого списка?

3) Як мовиться головою хвостом очереди?

4) Як розташовуються елементи у черзі? ________________________________________________________________ Завдання для самостійного рішення: 1) Нехай вже й побудована чергу Q, що містить цілі числа. Обчислити суму і твір елементів, що у черги. 2) Нехай вже й побудована чергу Q, що містить цілі числа. Сформувати нову чергу P, що складається з елементів черги Q, кратних числу 3. 3) Нехай вже й побудована чергу Q, що містить цілі числа. Обчислити кількість простих чисел, що у очереди.

Тема: «Стек».

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

Лабораторна робота № 5 на тему «Стек».

1. Натиснімо кнопку «Теорія «для стека.

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

Кнопки «> «служать для переміщення курсору в стеці. а) Переміститеся вправо до запланованих 4 елемента; б) Переміститеся вліво (див. комментарии);

Кнопка «Додати «служить для додавання елемента у стек.

Додайте 1, 3, 5 елементами число 22;

Кнопка «Видалити «служить видалення елемента із стека.

Приберіть 1, 3, 5, останній елементи; 3. На аркуші формату А4, опишіть хід виконану работы.

Скажіть на поставлені вопросы:

1) Як видаляється й додають елементи в стек?

2) Приведи приклади стека практично? ________________________________________________________________ Завдання для самостійного рішення: 1) Припустимо, що вони побудований стік, елементами якого є цілі числа. Написати програму, яка має суму елементів, що у стеці. 2) Припустимо, що вони побудований стік, елементами якого є цілі числа. Написати програму, яка додає насамкінець стека P. S елемент, що у вершині. 3) Припустимо, що вони побудований стік, елементами якого є цілі числа. Написати програму, яка видаляє з стека все елементи, кратні 4 (використовуватиме проміжного зберігання елементів стека односпрямований список з заглавным звеном).

Тема: «Тест».

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

Лабораторна робота № 7 на тему «Тест».

1. Повторіть весь теоретичний матеріал. 2. Попрацюйте з демонстраційної програмою. 3. Запустіть тест (сервистест чи Ctrl + T). 4. Скажіть на ці запитання тесту. 5. Результати тесту повідомити преподавателю.

2.2 Розробка програмного кошти на тему «Динамічні типи данных».

Після завантаження демонстраційної програми перед вами з’явиться ось таке окно.

[pic].

Це головне форма демонстраційної програми. Щоб сформувати списків натиснімо кнопку «Обновить».

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

[pic] [pic].

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

При натисканні на кнопку теорія (для черги) відкривається вікно «Черга», якому викладено теорія і дано примеры.

[pic] Аналогічно інших списков.

Для зручною роботи з учнями у програмі передбачені лабораторні роботи (Ctrl + L чи Сервіс Лабораторні роботи). Якщо ви хоч виберете усе те відкриється вікно «Лабораторні роботи», у якому дано відразу всі роботи і завдання. Перед вами 4 лабораторна робота на список «Очередь».

[pic].

Якщо ви вибирати кожну окремо вони будуть відображатись коментарів на головною форме.

Допомога можна викликати (СправкаПомощь чи F1).

[pic].

Після завершення всіх лабораторних робіт учням пропонується запитання тесту, протягом якого вони мають оцінку. Після запуску тесту (СервисТест чи Ctrl + T) відкривається вікно «Тест».

[pic].

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

Закрити програму можна натисканням на кнопку «Закрити» чи F10.

Заключение

У кваліфікаційної роботі намагалися розкрити повніше і наочно поняття лінійного списку, односпрямованого і двунаправленного списків, стека, дека і першої черги. Сформувати і закріпити пізнавальний інтерес до теми у учнів. Виявляти і розвивати творчі здібності використання отриманого досвіду при программировании.

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

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

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

1. Айен Сінклер «Великий тлумачний словник комп’ютерних термінів», М.: 1998 р. 2. Архангельський А. Я. «Програмування в Delphi 4», М.: 1999 р. 3. Архангельський А. Я. «Програмування в Delphi 5», М.: 2000 р. 4. Вірт М. «Алгоритми і структури даних», Москва Вид. Світ, 1989 р. 5. Гудмэн Д. «Управління пам’яттю всім», Київ 1995 р. 6. Зубов У. З. «Довідник програміста», М.: 1999 р. 7. Батіг Д. «Мистецтво програмування для ЕОМ», т.1 Основні алгоритмы,.

Вид. Світ М.: 1976 р. 8. Кормен Т. та інші «Алгоритми побудови і аналіз», М.: 2000 р. 9. Подласый І. П. Підручник для студентів вищих педагогічних навчальних закладів, М.: Просвітництво 1996 р. 10. Усова А. У. «Формування школярі понять у процесі обучения»,.

М.: Педагогіка, 1986 г.

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

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

unit Unit1; // Интерфейс.

interface.

uses.

Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, ExtCtrls, StdCtrls, ComCtrls, Unit2, Unit3, Unit4, Unit5, Unit6, Unit7, Unit8, Unit9, Menus, Unit11, Unit12, Unit13, Unit14, Unit15, Unit16, Unit17;

type TForm1 = class (TForm).

Panel1: TPanel;

Edit1: TEdit;

Label1: TLabel;

Button1: TButton;

Button2: TButton;

Button3: TButton;

Button4: TButton;

Panel2: TPanel;

Label2: TLabel;

Edit2: TEdit;

Button5: TButton;

Button6: TButton;

Button7: TButton;

Button8: TButton;

Panel3: TPanel;

Label3: TLabel;

Edit3: TEdit;

Button9: TButton;

Button10: TButton;

Button11: TButton;

Button12: TButton;

Panel4: TPanel;

Label4: TLabel;

Edit4: TEdit;

Button13: TButton;

Button14: TButton;

Button15: TButton;

Button16: TButton;

Panel5: TPanel;

Label5: TLabel;

Edit5: TEdit;

Button17: TButton;

Button18: TButton;

Button19: TButton;

Button20: TButton;

Panel6: TPanel;

Edit6: TEdit;

Label6: TLabel;

Button21: TButton;

StatusBar1: TStatusBar;

Image1: TImage;

Image2: TImage;

Image3: TImage;

Image4: TImage;

Image5: TImage;

Button22: TButton;

Memo1: TMemo;

Label7: TLabel;

Image6: TImage;

Bevel1: TBevel;

Panel7: TPanel;

Button23: TButton;

Button24: TButton;

Button25: TButton;

Button26: TButton;

Edit7: TEdit;

Image7: TImage;

Label8: TLabel;

Panel8: TPanel;

Image8: TImage;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

Button27: TButton;

Button28: TButton;

Button30: TButton;

Button29: TButton;

Button31: TButton;

Button32: TButton;

N6: TMenuItem;

N7: TMenuItem;

N8: TMenuItem;

N11: TMenuItem;

N21: TMenuItem;

N31: TMenuItem;

N41: TMenuItem;

N51: TMenuItem;

N61: TMenuItem;

N71: TMenuItem;

Button33: TButton;

N9: TMenuItem; procedure Button12Click (Sender: TObject); procedure Button11Click (Sender: TObject); procedure Button22Click (Sender: TObject); procedure Button21Click (Sender: TObject); procedure Button1Click (Sender: TObject); procedure Button3Click (Sender: TObject); procedure Button4Click (Sender: TObject); procedure Button7Click (Sender: TObject); procedure Button8Click (Sender: TObject); procedure FormClose (Sender: TObject; var Action: TCloseAction); procedure Button15Click (Sender: TObject); procedure Button16Click (Sender: TObject); procedure Button20Click (Sender: TObject); procedure FormCreate (Sender: TObject); procedure Button19Click (Sender: TObject); procedure Button5Click (Sender: TObject); procedure Button2Click (Sender: TObject); procedure Button6Click (Sender: TObject); procedure Button10Click (Sender: TObject); procedure Button9Click (Sender: TObject); procedure Button14Click (Sender: TObject); procedure Button13Click (Sender: TObject); procedure Button17Click (Sender: TObject); procedure Button18Click (Sender: TObject); procedure Button26Click (Sender: TObject); procedure Button25Click (Sender: TObject); procedure Button23Click (Sender: TObject); procedure Button24Click (Sender: TObject); procedure N2Click (Sender: TObject); procedure N5Click (Sender: TObject); procedure N4Click (Sender: TObject); procedure Button27Click (Sender: TObject); procedure Button30Click (Sender: TObject); procedure Button29Click (Sender: TObject); procedure Button31Click (Sender: TObject); procedure Button32Click (Sender: TObject); procedure N8Click (Sender: TObject); procedure N11Click (Sender: TObject); procedure Button33Click (Sender: TObject); procedure N21Click (Sender: TObject); procedure N31Click (Sender: TObject); procedure N41Click (Sender: TObject); procedure N51Click (Sender: TObject); procedure N61Click (Sender: TObject); procedure N71Click (Sender: TObject); procedure N9Click (Sender: TObject); private public end;

procedure DoNewEditList; procedure DoNewEditListTwo; procedure DoNewEditRoundList;

var Form1: TForm1; ListBegin: List; //покажчик на однонапр. список ListPos: Integer; //позиція в однонапр. списку ListTwoBegin: ListTwo; //покажчик на двунапр. список ListTwoPos: Integer; //позиція в двунапр. списку QueueBegin: List; //покажчик на чергу QueuePos: Integer; // «позиція у черзі «(містить у символів в Edit до першого елемента) Stack: List; //покажчик на стік StackPos: Integer; // «позиція в стеці «(містить у символів в Edit до першого елемента) DeckBegin, DeckEnd: ListTwo; //покажчики початку і поклала край дека DeckBeginPos, DeckEndPos: Integer; // «позиції з деці «(DeckEndPos містить у символів в Edit від DeckEndPosition аж до останнього елемента) DeckEndPosition: Integer; //позиція останнього елемента у деці (містить початкове у символів в Edit аж до останнього елемента) RoundList: List; //покажчик в циклічний списку RoundListPos: Integer; // «позиція в циклічному списку «.

implementation.

uses O_programm, Help, Un18_Lab;

{$R *.DFM}.

procedure DoNewEditList; var q: List; begin q := ListBegin; Form1. Edit1.Text := «»; while q nil do begin.

Form1.Edit1.Text := Form1. Edit1.Text + «» + IntToStr (q^.Info); q := q^.Next; end; end;

procedure DoNewEditListTwo; var q: ListTwo; begin q := ListTwoBegin; Form1. Edit2.Text := «»; while q nil do begin.

Form1.Edit2.Text := Form1. Edit2.Text + «» + IntToStr (q^.Info); q := q^.Next; end; end;

procedure DoNewEditRoundList; var q: List; begin q := RoundList^.Next; Form1. Edit7.Text := «» + IntToStr (RoundList^.Info); while q RoundList do begin.

Form1.Edit7.Text := Form1. Edit7.Text + «» + IntToStr (q^.Info); q := q^.Next; end; end;

procedure TForm1. Button12Click (Sender: TObject); var і, j: Integer; p. s: string; begin StatusBar1. Panels[0]. Text := «»; GetQueue (QueueBegin); if QueueBegin nil then begin while Edit3. Text[QueuePos] «» do Inc (QueuePos);

Inc (QueuePos); p. s := Edit3. Text; for і := 1 to QueuePos — 1 do if s[i] «» then s[i] := «» ;

Edit3.Text := p. s; end else begin.

ShowMessage («Черга порожня »);

Edit3.Text := «» ;

Image3.Hide;

Button10.Enabled := False;

Button11.Enabled := False;

Button12.Enabled := False;

StatusBar1.Panels[1]. Text := «Черга порожня »; end; Image3. Left := Round (QueuePos * 7); end;

procedure TForm1. Button11Click (Sender: TObject); begin StatusBar1Panels[0]. Text := «Не можна !!! »; Memo1.Lines.Add («У очерди не можна повертатися на початок т.к. покажчик вказує відразу початку; «); end;

procedure TForm1. Button22Click (Sender: TObject); begin Application. Terminate; end;

procedure TForm1. Button21Click (Sender: TObject); var q: List; qTwo: ListTwo; qQueue, rQueue: List; Info: Integer; FlagList: Boolean; qStack: List; qDeckBegin, qDeckEnd: ListTwo; qRoundList: List; // початок циклич. списка.

begin Button1. Enabled := True; Button2. Enabled := True; Button3. Enabled := True; Button4. Enabled := True; Button5. Enabled := True; Button6. Enabled := True; Button7. Enabled := True; Button8. Enabled := True; Button9. Enabled := True; Button10. Enabled := True; Button11. Enabled := True; Button12. Enabled := True; Button13. Enabled := True; Button14. Enabled := True; Button15. Enabled := True; Button16. Enabled := True; Button17. Enabled := True; Button18. Enabled := True; Button19. Enabled := True; Button20. Enabled := True; Button23. Enabled := True; Button24. Enabled := True; Button25. Enabled := True; Button26. Enabled := True; Image1. Visible := True; Image2. Visible := True; Image3. Visible := True; Image4. Visible := True; Image5. Visible := True; Image6. Visible := True; Image7. Visible := True; Edit1. Text := «»; Edit2. Text := «»; Edit3. Text := «»; Edit4. Text := «»; Edit5. Text := «»; Edit7. Text := «»; StatusBar1. Panels[0]. Text := «»; StatusBar1. Panels[1]. Text := «»; CreateLists; q := ListBegin; qTwo := ListTwoBegin; while q nil do begin.

Edit1.Text := Edit1. Text + «» + IntToStr (q^.Info); q := q^.Next; end; Image1. Left := 9; ListPos := 0; while qTwo nil do begin.

Edit2.Text := Edit2. Text + «» + IntToStr (qTwo^.Info); qTwo := qTwo^.Next; end; Image2. Left := 9; ListTwoPos := 0; FlagList := True; while QueueBegin nil do begin.

Info := GetQueue (QueueBegin);

Edit3.Text := Edit3. Text + «» + IntToStr (Info);

AddToQueue (Info, qQueue); if FlagList then begin.

FlagList := False; rQueue := qQueue; end; end; QueueBegin := rQueue; QueuePos := 2; Image3. Left := 9; while Stack nil do begin.

Info := GetStack (Stack);

Edit4.Text := Edit4. Text + «» + IntToStr (Info);

AddToStack (Info, qStack); end; Stack := qStack; Memo1.Lines.Add («У стеці числа роблять оборот т.к. елементи зчитуються з кінця стека. »); StackPos := 2; Image4. Left := 9; while DeckEnd nil do begin.

Info := GetDeckEnd (DeckEnd);

Edit5.Text := Edit5. Text + «» + IntToStr (Info);

AddToDeck (Info, qDeckBegin, qDeckEnd, 0); end; DeckBegin := qDeckBegin; DeckEnd := qDeckEnd; DeckBeginPos := 2; Image5. Left := 9; Memo1.Lines.Add («Груд прочитувався початку, тому елементи записалися усе своєю чергою. »); DeckEndPosition := 1; while Edit5. Text[DeckEndPosition] «» do Inc (DeckEndPosition); Image6. Left := Round (9 + DeckEndPosition * 6.2); Dec (DeckEndPosition); DeckEndPos := DeckEndPosition; qRoundList := RoundList^.Next; Edit7. Text := «» + IntToStr (RoundList^.Info); while qRoundList RoundList do begin.

Edit7.Text := Edit7. Text + «» + IntToStr (qRoundList^.Info); qRoundList := qRoundList^.Next; end; Image7. Left := 9; RoundListPos := 0; end;

procedure TForm1. Button1Click (Sender: TObject); begin Form3. Show; end;

procedure TForm1. Button3Click (Sender: TObject); begin StatusBar1. Panels[0]. Text := «Не можна !!! »; Memo1.Lines.Add («У однонаправленном списку не можна переміщатися тому, т.к. зв’язок існує тілки до однієї бік; «); end;

procedure TForm1. Button4Click (Sender: TObject); var qList: List; і, j: Integer; begin StatusBar1. Panels[0]. Text := «»; qList := ListBegin; і := 0; while і ListPos do begin qList := qList^.Next;

Inc (i); end; if qList nil then begin if qList^.Next nil then Inc (ListPos); і := 0; j := 0; while і < ListPos do begin.

Inc (j); if Edit1. Text[j] = «» then Inc (i); end;

Image1.Left := Round (9 + (j + 1) * 7.5); end; end;

procedure TForm1. Button7Click (Sender: TObject); var qListTwo: ListTwo; і, j: Integer; begin StatusBar1. Panels[0]. Text := «»; qListTwo := ListTwoBegin; і := 0; if ListTwoPos 0 then dec (ListTwoPos); і := 0; j := 0; while і < ListTwoPos do begin.

Inc (j); if Edit2. Text[j] = «» then Inc (i); end; if ListTwoPos = 0 then Image2. Left := 9 else Image2. Left := Round (9 + (j + 1) * 7.5); end;

procedure TForm1. Button8Click (Sender: TObject); var qListTwo: ListTwo; і, j: Integer; begin StatusBar1. Panels[0]. Text := «»; qListTwo := ListTwoBegin; і := 0; while і ListTwoPos do begin qListTwo := qListTwo^.Next;

Inc (i); end; if qListTwo nil then begin if qListTwo^.Next nil then Inc (ListTwoPos); і := 0; j := 0; while і < ListTwoPos do begin.

Inc (j); if Edit2. Text[j] = «» then Inc (i); end;

Image2.Left := Round (9 + (j + 1) * 7.5); end; end;

procedure TForm1. FormClose (Sender: TObject; var Action: TCloseAction); begin DestroyList (ListBegin); DestroyListTwo (ListTwoBegin); DestroyList (QueueBegin); DestroyList (Stack); DestroyListTwo (DeckBegin); Application. Terminate; end;

procedure TForm1. Button15Click (Sender: TObject); begin StatusBar1. Panels[0]. Text := «Не можна !!! »; Memo1.Lines.Add («У стеці не можна повертатися на початок т.к. покажчик вказує відразу початку; «); end;

procedure TForm1. Button16Click (Sender: TObject); var і: Integer; p. s: string; begin StatusBar1. Panels[0]. Text := «»; GetStack (Stack); if Stack nil then begin while Edit4. Text[StackPos] «» do Inc (StackPos);

Inc (StackPos); p. s := Edit4. Text; for і := 1 to StackPos — 1 do if s[i] «» then s[i] := «» ;

Edit4.Text := p. s; end else begin.

ShowMessage («Стік порожній »);

Edit4.Text := «» ;

Image4.Hide;

Button14.Enabled := False;

Button15.Enabled := False;

Button16.Enabled := False;

StatusBar1.Panels[1]. Text := «Стік порожній »; end; Image4. Left := Round (StackPos * 7); end;

procedure TForm1. Button20Click (Sender: TObject); var і: Integer; p. s: string; begin StatusBar1. Panels[0]. Text := «»; GetDeckBegin (DeckBegin); if DeckBegin nil then begin while Edit5. Text[DeckBeginPos] «» do Inc (DeckBeginPos);

Inc (DeckBeginPos); p. s := Edit5. Text; for і := 1 to DeckBeginPos — 1 do if s[i] «» then s[i] := «» ;

Edit5.Text := p. s; end; if (DeckBegin = nil) and (DeckBegin = DeckEnd) then begin.

ShowMessage («Груд порожній »);

Edit5.Text := «» ;

Image5.Hide;

Image6.Hide;

Button18.Enabled := False;

Button19.Enabled := False;

Button20.Enabled := False;

StatusBar1.Panels[1]. Text := «Груд порожній »; end; Image5. Left := Round (DeckBeginPos * 7); end;

procedure TForm1. FormCreate (Sender: TObject); begin Windows. SetFocus (Button21.Handle); end;

procedure TForm1. Button19Click (Sender: TObject); var і, a: Integer; p. s: string; begin StatusBar1. Panels[0]. Text := «»; GetDeckEnd (DeckEnd); if DeckEnd nil then begin while Edit5. Text[DeckEndPos] «» do Dec (DeckEndPos);

Dec (DeckEndPos); p. s := Edit5. Text; for і := DeckEndPosition downto DeckEndPos + 1 do if s[i] «» then s[i] := «» ;

Edit5.Text := s;

//видаляємо все прогалини кінці рядки p. s := «»; і := Length (Edit5.Text) — 1; while Edit5. Text[i] = «» do Dec (i); for a := 1 to і do p. s := p. s + Edit5. Text[a];

Edit5.Text := p. s; end; if (DeckEnd = nil) and (DeckBegin = DeckEnd) then begin.

ShowMessage («Груд порожній »);

Edit5.Text := «» ;

Image5.Hide;

Image6.Hide;

Button19.Enabled := False;

Button20.Enabled := False;

StatusBar1.Panels[1]. Text := «Груд порожній »; end; Image6. Left := Round (DeckEndPos * 7 — 9); end;

procedure TForm1. Button5Click (Sender: TObject); begin.

Form5.Show; end;

procedure TForm1. Button2Click (Sender: TObject); begin DeleteFromList (ListPos); DoNewEditList; end;

procedure TForm1. Button6Click (Sender: TObject); begin DeleteFromListTwo (ListTwoPos); DoNewEditListTwo; end;

procedure TForm1. Button10Click (Sender: TObject); var і, a: Integer; s1, s2: string; begin GetQueue (QueueBegin); if QueueBegin nil then begin і := QueuePos; while (Edit3.Text[i] «») and (і «служать для переміщення курсору по списку. »); Memo1.Lines.Add («а) Переміститеся вліво до 3, 5 й останнього елемента; «); Memo1.Lines.Add («б) Переміститеся вправо до першого елемента (див. коментарии); «); Memo1.Lines.Add («Кнопка «Додати «служить для додавання елемента у список. »); Memo1.Lines.Add («а) Додайте після 3, 5, 7 елемента цифру 33 в обох списках; «); Memo1.Lines.Add («б) Добавте 1-му і 3-му елементом цифру 55 в двунаправленном списку; «); Memo1.Lines.Add («Кнопка «Видалити «служить видалення елемента із списку. »); Memo1.Lines.Add («а) Приберіть 3, 5, 7 елементи в однонаправленном списку; «); Memo1.Lines.Add («б) Приберіть останній, 1 і трьох елементи в двунаправленном; «); Memo1.Lines.Add («»); Memo1.Lines.Add («3. На аркуші формату А4, опишіть хід виконану роботи. »); Memo1.Lines.Add («Скажіть на ці запитання: »); Memo1.Lines.Add («1) Зверніть увагу як переміщається курсор? »); Memo1.Lines.Add («2) Чим КиМу різниться односпрямований і двунаправленный списки? »); Memo1.Lines.Add («3) Чи можна додати елемент у будь-яку довільну місце списку? »); Memo1.Lines.Add («4) Чи можна видалити будь-який елемент зі списку? »); end;

procedure TForm1. N31Click (Sender: TObject); begin Memo1. Clear; Memo1.Lines.Add («Лабораторна робота № 3. »); Memo1.Lines.Add («» Циклічний список «»);

Memo1.Lines.Add («___________________________________________________________ ___ «); Memo1.Lines.Add («1. Натиснімо кнопку «Теорія «для циклічного списку? »); Memo1.Lines.Add («Уважно вивчите теоретичний матеріал. »); Memo1.Lines.Add («»); Memo1.Lines.Add («2. Натисніть кнопку «Обновити «на формування списків. »); Memo1.Lines.Add («Кнопки «> «служать для переміщення курсору по списку. »); Memo1.Lines.Add («а) Переміститеся вправо до 3, 5, останнього, першого елемента; «); Memo1.Lines.Add («б) Переміститеся вліво (див. коментарии); «); Memo1.Lines.Add («Кнопко «Додати «служить для додавання елемента у список. »); Memo1.Lines.Add («а) Додайте 3, 5, 1-му елементами число 44; «); Memo1.Lines.Add («б) Додайте після 2, 4, 1-го елемента число 0; «); Memo1.Lines.Add («Кнопко «Видалити «служить видалення елемента із списку. »); Memo1.Lines.Add («Приберіть 3, 5, 1, 4 елементи; «); Memo1.Lines.Add («»); Memo1.Lines.Add («3. На аркуші формату А4, опишіть хід виконану роботи. »); Memo1.Lines.Add («Скажіть на ці запитання: »); Memo1.Lines.Add («1) Зверніть увагу як переміщається курсор? »); Memo1.Lines.Add («2) Яку заслання має останній елемент циклічного списку? »); Memo1.Lines.Add («3) Як мовиться головою хвостом списку? »);

end;

procedure TForm1. N41Click (Sender: TObject); begin Memo1. Clear; Memo1.Lines.Add («Лабораторна робота № 4. »); Memo1.Lines.Add («» Черга «»);

Memo1.Lines.Add («___________________________________________________________ ___ «); Memo1.Lines.Add («1. Натиснімо кнопку «Теорія «для черги. »); Memo1.Lines.Add («Уважно вивчите теоретичний матеріал. »); Memo1.Lines.Add («»); Memo1.Lines.Add («2. Натиснімо кнопку «Обновити «на формування списків. »); Memo1.Lines.Add («Кнопки «> «служать для переміщення курсору по черги. »); Memo1.Lines.Add («а) Переміститеся вправо до 3 елемента; «); Memo1.Lines.Add («б) Переміститеся вліво (див. коментарии); «); Memo1.Lines.Add («Кнопко «Додати «служить для додавання елемента у чергу. »); Memo1.Lines.Add («а) Додайте 1, 4, 5-му елементами число 99; «); Memo1.Lines.Add («б) Додайте останнім число 999; «); Memo1.Lines.Add («Кнопко «Видалити «служить видалення елемента із черги. »); Memo1.Lines.Add («Приберіть 1, 2, 3 елементи; «); Memo1.Lines.Add («»); Memo1.Lines.Add («3. На аркуші формату А4, опишіть хід виконану роботи. »); Memo1.Lines.Add («Скажіть на ці запитання: »); Memo1.Lines.Add («1) Як видаляється й додають елементи у черзі? »); Memo1.Lines.Add («2) У чому відмінність і подібність черзі й односпрямованого списку? »); Memo1.Lines.Add («3) Як мовиться головою хвостом черги? »); Memo1.Lines.Add («4) Як розташовуються елементи у черзі? »); end;

procedure TForm1. N51Click (Sender: TObject); begin Memo1. Clear; Memo1.Lines.Add («Лабораторна робота № 5. »); Memo1.Lines.Add («» Стік «»);

Memo1.Lines.Add («___________________________________________________________ ___ «); Memo1.Lines.Add («1. Натисніть кнопку «Теорія «для стека. »); Memo1.Lines.Add («Уважно вивчите теоретичний матеріал. »); Memo1.Lines.Add («»); Memo1.Lines.Add («2. Натисніть кнопку «Обновити «на формування списків. »); Memo1.Lines.Add («Кнопки «> «служать для переміщення курсору в стеці. »); Memo1.Lines.Add («а) Переміститеся вправо до запланованих 4 елемента; «); Memo1.Lines.Add («б) Переміститеся вліво (див. коментарии); «); Memo1.Lines.Add («Кнопка «Додати «служить для додавання елемента у стік. »); Memo1.Lines.Add («Додайте 1, 3, 5 елементами число 22; «); Memo1.Lines.Add («Кнопко «Видалити «служить видалення елемента із стека. »); Memo1.Lines.Add («Приберіть 1, 3, 5, останній елементи; «); Memo1.Lines.Add («3. На аркуші формату А4, опишіть хід виконану роботи. »); Memo1.Lines.Add («Скажіть на ці запитання: »); Memo1.Lines.Add («1) Як видаляється й додають елементи в стік? »); Memo1.Lines.Add («2) Приведи приклади стека практично? »); end;

procedure TForm1. N61Click (Sender: TObject); begin Memo1. Clear; Memo1.Lines.Add («Лабораторна робота № 6. »); Memo1.Lines.Add («» Груд «»);

Memo1.Lines.Add («___________________________________________________________ ___ «); Memo1.Lines.Add («1. Натиснімо кнопку «Теорія «для дека. »); Memo1.Lines.Add («Уважно вивчите теоретичний матеріал. »); Memo1.Lines.Add («»); Memo1.Lines.Add («2. Натиснімо кнопку «Обновити «на формування списків. »); Memo1.Lines.Add («Кнопки «> «служать для переміщення курсору в деці. »); Memo1.Lines.Add («а) Переміститеся вліво на 2 елемента; «); Memo1.Lines.Add («б Переміститеся вправо на виборах 4 елемента; «); Memo1.Lines.Add («Кнопко «Додати «служить для додавання елемента у груд. »); Memo1.Lines.Add («а) Додайте 1, 3 елементом число 11; «); Memo1.Lines.Add («б) Додайте 5, 6 елементом число 88; «); Memo1.Lines.Add («Кнопко «Видалити «служить видалення елемента із дека. »); Memo1.Lines.Add («а) Приберіть 2, 4 елементи; «); Memo1.Lines.Add («б) Добавте 6, 7 елементи; «); Memo1.Lines.Add («»); Memo1.Lines.Add («3. На аркуші формату А4, опишіть хід виконану роботи. »); Memo1.Lines.Add («Скажіть на ці запитання: »); Memo1.Lines.Add («1) Як видаляється й додають елементи в груд? »); Memo1.Lines.Add («2) У чому схожі й різні груд, стік і двунаправленный список? »);

end;

procedure TForm1. N71Click (Sender: TObject); begin Memo1. Clear; Memo1.Lines.Add («Лабораторна робота № 7. »); Memo1.Lines.Add («» Тест «»);

Memo1.Lines.Add («___________________________________________________________ ___ «); Memo1.Lines.Add («1. Повторіть весь теоретичний матеріал. »); Memo1.Lines.Add («»); Memo1.Lines.Add («2. Попрацюйте з демонстраційної програмою. »); Memo1.Lines.Add («»); Memo1.Lines.Add («3. Запустіть тест (сервистест чи Ctrl + T). »); Memo1.Lines.Add («Скажіть на ці запитання тесту. »); Memo1.Lines.Add («»); Memo1.Lines.Add («4. Результати тесту повідомити викладачеві. »); end;

procedure TForm1. N9Click (Sender: TObject); begin Form18. Show; end;

end.

unit Unit2; //Формування списков.

interface.

uses SysUtils, Windows, Dialogs;

type.

List = ^Spisok; //Односпрямований Spisok = record.

Info: Integer;

Next: List; end;

ListTwo = ^SpisokTwo; //Двунаправленный SpisokTwo = record.

Info: Integer;

Next: ListTwo;

Prev: ListTwo; end;

procedure CreateLists; procedure AddToList (X: Integer; var PointerEndList: List); procedure AddToListAfterPos (X: Integer; Position: Integer); procedure DeleteFromList (Position: Integer); procedure AddToListTwo (X: Integer; var PointerEndListTwo: ListTwo); procedure AddToListTwoAfterPos (X: Integer; Position: Integer); procedure DeleteFromListTwo (Position: Integer); procedure AddToQueue (X: Integer; var PointerEndQueue: List); procedure AddToEndQueue (X: Integer); function GetQueue (var PointerBegin: List): Integer; procedure AddToStack (X: Integer; var PointerStack: List); function GetStack (var PointerStack: List): Integer; procedure AddToDeck (X: Integer; var PointerDeckBegin, PointerDeckEnd: ListTwo; Flag: Integer); function GetDeckBegin (var PointerDeckBegin: ListTwo): Integer; function GetDeckEnd (var PointerDeckEnd: ListTwo): Integer; procedure DestroyList (PointerBegin: List); procedure DestroyListTwo (PointerBegin: ListTwo); procedure AddToRoundList (X: Integer; var PointerRoundList: List); procedure DeleteFromRoundList (Position: Integer); procedure DestroyRoundList (var PointerRoundList: List);

implementation uses Unit1;

procedure DestroyList (PointerBegin: List); var q: List; begin while PointerBegin nil do begin q := PointerBegin;

PointerBegin := PointerBegin^.Next; if q nil then Dispose (q); end; end;

procedure DestroyListTwo (PointerBegin: ListTwo); var q: ListTwo; begin while PointerBegin nil do begin q := PointerBegin;

PointerBegin := PointerBegin^.Next; if q nil then Dispose (q); end; end;

procedure DestroyRoundList (var PointerRoundList: List); var q, t: List; begin q := PointerRoundList^.Next; PointerRoundList^.Next := nil; while q nil do begin t := q; q := q^.Next; if t nil then Dispose (t); end; PointerRoundList := nil; end;

procedure AddToList (X: Integer; var PointerEndList: List); //Додати елемент в.

//кінець списку (PointerEnd — покажчик на останній елемент списку) begin if PointerEndList = nil then // Якщо Сталін перший елемент що немає begin.

New (PointerEndList);

PointerEndList^.Info := X;

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

New (PointerEndList^.Next);

PointerEndList := PointerEndList^.Next;

PointerEndList^.Info := X;

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

procedure AddToListAfterPos (X: Integer; Position: Integer); var //Додати елемент до списку після Position і: Integer; q, qNew: List; begin if Position = 0 then // Якщо позиція = 0, то додаємо на початок begin.

New (qNew); qNew^.Info := X; qNew^.Next := ListBegin;

ListBegin := qNew; end else begin q := ListBegin; і := 0; while (і < Position) and (q nil) do // Шукаємо елемент після которого.

// потрібно вставити begin q := q^.Next;

Inc (i); end; if q nil then // Якщо елемент існує то вставляємо begin.

New (qNew); qNew^.Info := X; qNew^.Next := q^.Next; q^.Next := qNew; end else ShowMessage («Елемент, після якого хочете вставити, видалено »); end; end;

procedure AddToRoundList (X: Integer; var PointerRoundList: List); var qRound: List; begin if PointerRoundList = nil then begin.

New (PointerRoundList);

PointerRoundList^.Info := X;

PointerRoundList^.Next := PointerRoundList;

RoundList := PointerRoundList; end else begin.

New (qRound); qRound^.Info := X; qRound^.Next := PointerRoundList^.Next;

PointerRoundList^.Next := qRound; end; PointerRoundList := PointerRoundList^.Next; end;

procedure DeleteFromRoundList (Position: Integer); var q, h: List; і: Integer; begin if RoundList^.Next = RoundList then //один елемент у списку begin if RoundList nil then Dispose (RoundList);

RoundList := nil; end else // чимало елемент у списку begin і := 1; q := RoundList; while і < RoundListPos do begin.

Inc (i); q := q^.Next; end; if і 1 then begin h := q^.Next; q^.Next := h^.Next; if h nil then Dispose (h); end else begin q := RoundList^.Next; while q^.Next RoundList do q := q^.Next; h := q^.Next; q^.Next := h^.Next; if h nil then Dispose (h);

RoundList := q^.Next; end; end; if RoundList nil then begin q := RoundList^.Next; і := 1; while q RoundList do begin.

Inc (i); q := q^.Next; end; if і = RoundListPos then begin.

RoundListPos := 0;

Form1.Image7.Left := 9; end; end; end;

procedure DeleteFromList (Position: Integer); //Видаляє елемент под.

//номером Position var і: Integer; q, r: List; begin q := ListBegin; if q nil then // Якщо список не порожній, то begin if Position = 0 then //Якщо позиція = 0, то видаляємо перший елемент begin.

ListBegin := q^.Next; if q nil then Dispose (q); end else begin і := 0; while (і < Position — 1) and (q nil) do //Шукаємо елемент после.

//що потребує видалити begin q := q^.Next;

Inc (i); end; r := q^.Next; if r nil then //Якщо удаляемый елемент існує, то видаляємо його begin q^.Next := r^.Next; if r nil then Dispose®; end else ShowMessage («Елемент вже немає «); end; end else begin.

ShowMessage («Список порожній »);

Form1.Image1.Hide; end; end;

procedure AddToListTwo (X: Integer; var PointerEndListTwo: ListTwo); //Додати елемент в.

//кінець дв-списка (PointerEnd — покажчик на останній елемент списку) begin if PointerEndListTwo = nil then //Якщо список що немає чи пуст,.

//додаємо на початок begin.

New (PointerEndListTwo);

PointerEndListTwo^.Info := X;

PointerEndListTwo^.Next := nil;

PointerEndListTwo^.Prev := nil; end else begin.

New (PointerEndListTwo^.Next);

PointerEndListTwo := PointerEndListTwo^.Next;

PointerEndListTwo^.Info := X;

PointerEndListTwo^.Next := nil;

PointerEndListTwo^.Prev := nil; end; end;

procedure AddToListTwoAfterPos (X: Integer; Position: Integer); var //Додати елемент в двунап. список після Position і: Integer; q, qNew: ListTwo; begin if Position = 0 then //Якщо позиція = 0, вставляємо на початок begin.

New (qNew); qNew^.Info := X; qNew^.Next := ListTwoBegin;

ListTwoBegin := qNew; end else begin q := ListTwoBegin; і := 0; while (і < Position) and (q nil) do //Шукаємо елемент після которого.

//потрібно вставити begin q := q^.Next;

Inc (i); end; if q nil then // Якщо елемент існує то вставляємо begin.

New (qNew); qNew^.Info := X; qNew^.Next := q^.Next; qNew^.Prev := q;

q^.Next := qNew; end else ShowMessage («Елемент, після якого хочете вставити, видалено »); end; end;

procedure DeleteFromListTwo (Position: Integer); //Видаляє элемент.

//під номером Position var і: Integer; q, r: ListTwo; begin q := ListTwoBegin; if q nil then //Якщо удаляемый елемент існує, то begin if Position = 0 then //Якщо позиція = 0, то видаляємо перший елемент begin.

ListTwoBegin^.Prev := nil;

ListTwoBegin := q^.Next; if q nil then Dispose (q); end else begin і := 0; while (і < Position — 1) and (q nil) do //Шукаємо элемент.

// після що потребує видалити begin q := q^.Next;

Inc (i); end; r := q^.Next; if r nil then //Якщо він є, то видаляємо його begin if r^.Next nil then r^.Next^.Prev := q; q^.Next := r^.Next; if r nil then Dispose®; end else ShowMessage («Елемент вже немає «); end; end else begin.

ShowMessage («Список порожній »);

Form1.Image2.Hide; end; end;

procedure AddToQueue (X: Integer; var PointerEndQueue: List); //Додати элемент.

//насамкінець черги (PointerEnd — покажчик на останній елемент черги) begin if PointerEndQueue = nil then //Якщо чергу, ще немає чи пуста.

//додаємо на початок begin.

New (PointerEndQueue);

PointerEndQueue^.Info := X;

PointerEndQueue^.Next := nil; end else begin.

New (PointerEndQueue^.Next);

PointerEndQueue := PointerEndQueue^.Next;

PointerEndQueue^.Info := X;

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

function GetQueue (var PointerBegin: List): Integer; //ф-ия отримує елемент из.

// черзі й повертає покажчик початку черги var rQueue: List;

begin rQueue := PointerBegin; if rQueue nil then //Якщо черга порожня begin.

PointerBegin := PointerBegin^.Next;

Result := rQueue^.Info; if rQueue nil then Dispose (rQueue); end else begin.

ShowMessage («Черга порожня »);

Form1.Edit3.Text := «» ;

Form1.Button10.Enabled := False;

Form1.Button11.Enabled := False;

Form1.Button12.Enabled := False;

Form1.Image3.Hide; end;

end;

procedure AddToEndQueue (X: Integer);

var Info: Integer; rQueue, qQueue: List; FlagList: Boolean; begin FlagList := True; //Для виділення першого елемента qQueue := nil; rQueue := nil; while QueueBegin nil do //Шукаємо покажчик на останній елемент черги begin.

Info := GetQueue (QueueBegin);

AddToQueue (Info, rQueue); //Формуємо нову чергу з елементів старой.

//черги, ніж втратити if FlagList then ///////////////////////////////////// begin // // qQueue := rQueue; // формуємо покажчик на чергу //.

FlagList := False; // // end; // ////////////////////////////////// end; AddToQueue (X, rQueue); if qQueue nil then QueueBegin := qQueue // визначаємо покажчик на чергу else QueueBegin := rQueue; //////////////////////////////////.

end;

procedure AddToStack (X: Integer; var PointerStack: List); //Додати елемент в.

//стік (PointerStack — покажчик на стік) var Stacks: List; begin if PointerStack = nil then //Якщо стік порожній, то формуємо його begin.

New (PointerStack);

PointerStack^.Info := X;

PointerStack^.Next := nil; end else //інакше додаємо елемент begin.

New (Stacks);

Stacks^.Info := X;

Stacks^.Next := PointerStack;

PointerStack := Stacks; end; end;

function GetStack (var PointerStack: List): Integer; //ф-ия отримує елемент из.

// стека і повертає покажчик на стік var rStack: List; begin rStack := PointerStack; if rStack nil then //Якщо стік ще порожній begin.

PointerStack := PointerStack^.Next;

Result := rStack^.Info; if rStack nil then Dispose (rStack); end else begin.

ShowMessage («Стік порожній »);

Form1.Button14.Enabled := False;

Form1.Image4.Hide; end; end;

procedure AddToDeck (X: Integer; var PointerDeckBegin, PointerDeckEnd: ListTwo;

Flag: Integer); //Додати елемент в дек.

//PointerDeckBegin — покажчик початку дека.

//PointerDeckEnd — покажчик наприкінці дека var Decks: ListTwo; begin if PointerDeckBegin = nil then //Якщо груд порожній, то формуємо його begin.

New (PointerDeckBegin);

PointerDeckBegin^.Info := X;

PointerDeckBegin^.Next := nil;

PointerDeckBegin^.Prev := nil;

PointerDeckEnd := PointerDeckBegin; end else //інакше додаємо елемент begin if Flag = 0 then //додаємо на початок begin.

New (Decks);

Decks^.Info := X;

Decks^.Next := PointerDeckBegin;

Decks^.Prev := nil;

PointerDeckBegin^.Prev := Decks;

PointerDeckBegin := Decks; end else //добавлям насамкінець begin.

New (Decks);

Decks^.Info := X;

Decks^.Next := nil;

Decks^.Prev := PointerDeckEnd;

PointerDeckEnd^.Next := Decks;

PointerDeckEnd := Decks; end; end; end;

function GetDeckBegin (var PointerDeckBegin: ListTwo): Integer;

//ф-ия отримує елемент з початку дека і повертає покажчик початку дека. var q: ListTwo; begin if PointerDeckBegin nil then //Якщо груд не порожній begin.

Result := PointerDeckBegin^.Info; q := PointerDeckBegin;

PointerDeckBegin := q^.Next; if PointerDeckBegin nil then PointerDeckBegin^.Prev := nil; if q nil then Dispose (q); end else begin.

ShowMessage («Груд порожній »);

Form1.Edit5.Text := «» ;

Form1.Button18.Enabled := False;

Form1.Button19.Enabled := False;

Form1.Button20.Enabled := False;

Form1.Image5.Hide;

Form1.Image6.Hide; end; end;

function GetDeckEnd (var PointerDeckEnd: ListTwo): Integer;

//ф-ия отримує елемент з кінця дека і повертає покажчик наприкінці дека. var q: ListTwo; begin if PointerDeckEnd nil then //Якщо груд не порожній begin.

Result := PointerDeckEnd^.Info; q := PointerDeckEnd;

PointerDeckEnd := q^.Prev; if PointerDeckEnd nil then PointerDeckEnd^.Next := nil; if q nil then Dispose (q); end else begin.

ShowMessage («Груд порожній »);

Form1.Edit5.Text := «» ;

Form1.Button18.Enabled := False;

Form1.Button19.Enabled := False;

Form1.Button20.Enabled := False;

Form1.Image5.Hide;

Form1.Image6.Hide; end; end;

procedure CreateLists; //процедура створення всіх списків var і: Integer; X: Integer; Uk, q: List; UkTwo, qTwo: ListTwo; UkQueue, qQueue: List; qStack: List; qDeckBegin, qDeckEnd: ListTwo; begin X := Random (101); //Визначаємо значення першого елемента Uk := nil; ////////////////////////// q := nil; // // UkTwo := nil; // ПОЧАТКОВІ УСТАНОВКИ: // qTwo := nil; // // UkQueue := nil; // все покажчики = nil // qQueue := nil; // // qStack := nil; // // qDeckBegin := nil; // // qDeckEnd := nil; //////////////////////////.

// Destroy for every lists if ListBegin nil then DestroyList (ListBegin); if ListTwoBegin nil then DestroyListTwo (ListTwoBegin); if QueueBegin nil then DestroyList (QueueBegin); if Stack nil then DestroyList (Stack); if DeckBegin nil then DestroyListTwo (DeckBegin); if RoundList nil then DestroyRoundList (RoundList);

AddToList (X, Uk); // AddToListTwo (X, UkTwo); // Додаємо Х в AddToQueue (X, UkQueue); // кожен список AddToStack (X, qStack); // AddToDeck (X, qDeckBegin, qDeckEnd, 0); // AddToRoundList (X, RoundList); /////////////////// Unit1. Form1.Edit6.Text := IntToStr (X); q := Uk; // [pic]qTwo := UkTwo; // Формуємо покажчики початку списків qQueue := UkQueue; // for і := to 9 do //Подальше формування списків begin.

X := Random (101);

AddToList (X, q);

AddToListTwo (X, qTwo);

AddToQueue (X, qQueue);

AddToStack (X, qStack);

AddToDeck (X, qDeckBegin, qDeckEnd, 0);

AddToRoundList (X, RoundList);

Unit1.Form1.Edit6.Text := Unit1. Form1.Edit6.Text + «» + IntToStr (X); end; ListBegin := Uk; ////////////////////////////////////// ListTwoBegin := UkTwo; // // QueueBegin := UkQueue; // // Stack := qStack; // Визначаємо покажчики все списки // DeckBegin := qDeckBegin; // // DeckEnd := qDeckEnd; // // RoundList := RoundList^.Next ////////////////////////////////// end;

end.

unit Unit16; //Тест.

interface.

uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ExtCtrls;

type TForm16 = class (TForm).

Memo1: TMemo;

Panel1: TPanel;

Button1: TButton;

RadioGroup1: TRadioGroup;

Button2: TButton; procedure RadioGroup1Click (Sender: TObject); procedure Button2Click (Sender: TObject); procedure Button1Click (Sender: TObject); procedure FormClose (Sender: TObject; var Action: TCloseAction); private.

{ Private declarations } public.

{ Public declarations } end;

var Form16: TForm16; NumberQuestion: Integer = 0; NumberTrueAnswer: Integer = 0; ff: Boolean = True;

implementation.

uses Unit1, Un18_Lab;

{$R *.DFM}.

procedure TForm16. RadioGroup1Click (Sender: TObject); begin Button1. Enabled := True; Button1. SetFocus; end;

procedure TForm16. Button2Click (Sender: TObject); begin Form16. Hide; Form1. Show; end;

procedure TForm16. Button1Click (Sender: TObject); begin Memo1.Lines.Clear; Button1. Enabled := False; Inc (NumberQuestion); case NumberQuestion of.

1: begin if RadioGroup1. ItemIndex = 0 then Inc (NumberTrueAnswer);

Memo1.Lines.Add («Односпрямований список — це … »);

RadioGroup1.Items.Clear;

RadioGroup1.Items.Add («Список, елементи якої мають зв’язок із наступним і попереднім елементом »);

RadioGroup1.Items.Add («Список, елементи якої мають зв’язок із наступним елементом »);

RadioGroup1.Items.Add («Список, елементи якої мають зв’язку »); end;

2: begin if RadioGroup1. ItemIndex = 1 then Inc (NumberTrueAnswer);

Memo1.Lines.Add («Якщо елемент містить посилання наступний і попередній елемент, це … »);

RadioGroup1.Items.Clear;

RadioGroup1.Items.Add («односпрямований список »);

RadioGroup1.Items.Add («двунаправленный список »);

RadioGroup1.Items.Add («чергу »);

RadioGroup1.Items.Add («стік »);

RadioGroup1.Items.Add («груд »);

RadioGroup1.Items.Add («циклічний список »); end;

3: begin if RadioGroup1. ItemIndex = 1 then Inc (NumberTrueAnswer);

Memo1.Lines.Add («Куди додається елемент в двунаправленный список? »);

RadioGroup1.Items.Clear;

RadioGroup1.Items.Add («У початок »);

RadioGroup1.Items.Add («У кінець »);

RadioGroup1.Items.Add («У будь-яке інше місце »); end;

4: begin if RadioGroup1. ItemIndex = 2 then Inc (NumberTrueAnswer);

Memo1.Lines.Add («Чим КиМу різниться односпрямований список від двунаправленного? »);

RadioGroup1.Items.Clear;

RadioGroup1.Items.Add («Існує зв’язку з попереднім елементом »);

RadioGroup1.Items.Add («Немає зв’язку з попереднім елементом »);

RadioGroup1.Items.Add («Не відрізняються »); end;

5: begin if RadioGroup1. ItemIndex = 1 then Inc (NumberTrueAnswer);

Memo1.Lines.Add («Який елемент зчитується з стека? »);

RadioGroup1.Items.Clear;

RadioGroup1.Items.Add («Останній »);

RadioGroup1.Items.Add («Будь-який »);

RadioGroup1.Items.Add («Перший »); end;

6: begin if RadioGroup1. ItemIndex = 0 then Inc (NumberTrueAnswer);

Memo1.Lines.Add («Чим КиМу різниться груд від стека? »);

RadioGroup1.Items.Clear;

RadioGroup1.Items.Add («Додавання у кожному місце. Видалення з початку »);

RadioGroup1.Items.Add («Додавання на початок. Видалення із будь-якої місця »);

RadioGroup1.Items.Add («Усі включення винятку відбуваються обох його кінцях »); end;

7: begin if RadioGroup1. ItemIndex = 2 then Inc (NumberTrueAnswer);

Memo1.Lines.Add («Звідки зчитується елемент з черги? »);

RadioGroup1.Items.Clear;

RadioGroup1.Items.Add («З кінця »);

RadioGroup1.Items.Add («З початку »);

RadioGroup1.Items.Add («З люього місця »); end;

8: begin if RadioGroup1. ItemIndex = 1 then Inc (NumberTrueAnswer);

Memo1.Lines.Add («Куди додається елемент в стік? »);

RadioGroup1.Items.Clear;

RadioGroup1.Items.Add («У кінець »);

RadioGroup1.Items.Add («У початок »);

RadioGroup1.Items.Add («У будь-яке місце »); end;

9: begin if RadioGroup1. ItemIndex = 0 then Inc (NumberTrueAnswer);

Memo1.Lines.Add («Яку заслання містить останній елемент циклічного списку? »);

RadioGroup1.Items.Clear;

RadioGroup1.Items.Add («На перший елемент »);

RadioGroup1.Items.Add («На попередній елемент »);

RadioGroup1.Items.Add («NIL »); end;

10: begin if RadioGroup1. ItemIndex = 0 then Inc (NumberTrueAnswer);

Memo1.Lines.Add («Якщо всі включення і виключення відбуваються з одного боку списку, це … »);

RadioGroup1.Items.Clear;

RadioGroup1.Items.Add («односпрямований список »);

RadioGroup1.Items.Add («двунаправленный список »);

RadioGroup1.Items.Add («чергу »);

RadioGroup1.Items.Add («стік »);

RadioGroup1.Items.Add («груд »);

RadioGroup1.Items.Add («циклічний список »); end;

11: begin if RadioGroup1. ItemIndex = 3 then Inc (NumberTrueAnswer);

Memo1.Lines.Add («Якщо останній елемент має посилання перший елемент, це … »);

RadioGroup1.Items.Clear;

RadioGroup1.Items.Add («односпрямований список »);

RadioGroup1.Items.Add («двунаправленный список »);

RadioGroup1.Items.Add («чергу »);

RadioGroup1.Items.Add («стік »);

RadioGroup1.Items.Add («груд »);

RadioGroup1.Items.Add («циклічний список »); end;

12: begin if RadioGroup1. ItemIndex = 5 then Inc (NumberTrueAnswer);

Button1.Hide; if NumberTrueAnswer >= 10 then ShowMessage («Ваша оцінка — ВІДМІННО! »); if (NumberTrueAnswer >= 8) and (NumberTrueAnswer < 10) then ShowMessage («Ваша оцінка — ДОБРЕ! »); if (NumberTrueAnswer >= 6) and (NumberTrueAnswer < 8) then ShowMessage («Ваша оцінка — ТРИ! »); if NumberTrueAnswer < 6 then begin.

ShowMessage («Тобі однозначно потрібно почитати теорію. Твоя оцінка — Два!!! »); ff := False; end;

Form16.Hide;

Form1.Show; if not ff then Form18. Show; end; end; end;

procedure TForm16. FormClose (Sender: TObject; var Action: TCloseAction); begin Form16. Hide; Form1. Show; if not ff then Form18. Show; end;

end.

———————————;

Включить.

Исключить.

Конец.

Третий.

Второй.

Включити чи исключить.

Новый.

Третій сверху.

Новый.

Конец.

Третий.

Второй.

Начало.

Низ.

Верх.

Включити чи исключить.

Другий сверху.

Рис. 1 Стік, поданий у вигляді залізничного разъезда.

Включити чи исключить.

Правий конец.

Другий справа.

Другий слева.

Лівий конец.

Р.

Указываемый объект.

Содержимое.

Адрес.

Пов’язане распределение.

Содержимое.

Адрес.

Послідовне распределение.

Л:

Л.

Елемент 1.

Елемент 2.

Елемент 3.

Елемент 4.

Елемент 5.

L0 + c:

L0 + 2c:

L0 + 3c:

L0 + 4c:

L0 + 5c:

Елемент 1.

Елемент 2.

Елемент 3.

Елемент 4.

Елемент 5.

FIRST.

Елемент 5.

Елемент 4.

Елемент 3.

Елемент 2.

Елемент 1.

Елемент [pic].

FIRST.

Елемент 5.

Елемент 4.

Елемент 3.

Елемент 2.

Елемент 1.

LINK.

INFO.

PTR.

Голова списка а.

а а.

а.

…

nil.

Начало.

??? ??? ???

Показати весь текст

Заповнити форму поточною роботою