Реферат: Линейные списки. Стек. Дек. Очередь

Реферат: Линейные списки. Стек. Дек. Очередь

Содержание

Введение 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 Списки. Очередь. Стек. Дек.

Список (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), если исключается верхний элемент. Эта терминология берет свое начало от "стеков" закусок, которые можно встретить в кафетериях, или по аналогии с колодами карт в некоторых перфораторных устройствах. Краткость слов "опустить" и "поднять" имеет свое преимущество, но эти термины ошибочно предполагают движение всего списка в памяти машины. Физически, однако, ничего не опускается; элементы просто добавляются сверху, как при стоговании сена или при укладке кипы коробок. В применении к очередям мы говорим о начале и конце очереди; объекты встают в конец очереди и удаляются в момент, когда наконец достигают ее начала. Говоря о деках, мы указываем левый и правый концы. Понятие верха, низа, начала и конца применимо иногда и к декам, если они используются как стеки или очереди. Не существует, однако, каких-либо стандартных соглашений отно­сительно того, где должен быть верх, начало и конец: слева или справа. Таким образом, мы находим, что в наших алгоритмах применимо богатое разнообразие описательных слов: "сверху — вниз" — для стеков, "слева — направо" — для деков и "ожидание в очереди" — для очередей.

Однонаправленный и двунаправленный список – это линейный список, в котором все исключения и добавления происходят в любом месте списка.

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

Очередь — тип данных, при котором новые данные располагаются следом за существующими в порядке поступления; поступившие первыми данные при этом обрабатываются первыми.

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

Другими словами, у очереди есть голова (head) и хвост (tail). Элемент, добавляемый в очередь, оказывается в её хвосте, как только что подошедший покупатель; элемент, удаляемый из очереди, находится в её голове, как тот покупатель, что отстоял дольше всех.

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

Стек  — часть памяти ОЗУ компьютера, которая предназначается для временного хранения байтов, используемых микропроцессором; при этом используется порядок запоминания байтов «последним вошел – первым вышел», поскольку такие ввод и вывод организовывать проще всего, также операции осуществляются очень быстро. Действия со стеком производится при помощи регистра указателя стека. Любое повреждение этой части памяти приводит к фатальному сбою.

Стек в виде списка (pushdown list) – стек, организованный таким образом, что последний вводимый в область памяти элемент размещается на вершине списка.

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

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

Представьте себе, что четыре железнодорожных вагона находятся на входной стороне пути (рис. 1) и перенумерованы соответственно 1, 2, 3 и 4. Предположим, что мы выполняем следующую последовательность операций (которые согласуются с направлением стрелок на рисунке и не требуют, чтобы вагоны "перепрыгивали" друг через друга). Отправьте:

В результате этих операций первоначальный порядок вагонов, 1234, изменился на 2431. Цель этого упражнения состоит в том, чтобы исследовать, какие перестановки можно получить, используя стеки, очереди и деки.

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

Иногда аналогия с переключением железнодорожных путей, предложенная Э. Дейкстрой, помогает понять механизм стека. На рис. 2. Изображен дек в виде железнодорожного разъезда.

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

В деке все исключения и добавления происходят на обоих его концах. Дек по сути двунаправленный список.

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

Если каждый стоящий в очереди запомнит, кто за ним стоит, после чего все в беспорядке рассядутся на лавочке, получится односторонне связанный список; если он запомнит ещё и впереди стоящего, будет двусторонне связанный список.

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

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

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

Здесь А, В, С, D и Е— произвольные ячейки в памяти, а Л — пустая связь. Программа, в которой используется такая таблица, имела бы, в случае последовательного распределения, дополнительную переменную или константу, значение которой по­казывает, что таблица состоит из пяти элементов; эту же информа­цию можно задать с помощью признака конца ("пограничника"), снабдив им элемент 5 или следующую ячейку, В случае связанного распределения в программе имеется переменная связи или константа, которая указывает на А, а отправляясь от А, можно найти все другие элементы списка.

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

Здесь 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);

Удаляет элемент под номером 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

        i := 0;

        while (i < 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(r);

            end

  end;

end

end;

2.1 Методические рекомендации по введению факультативного курса в школе

В системе школьных факультативов необходимо изучение информатики с большей полнотой. Это требует в свою очередь особенно тщательного отбора материала который может быть хорошо усвоен учащимися за ограниченное количество часов.

Разработанный нами факультатив рассчитан на 14 часов.

Задачи факультатива:

1)  Ввести понятие линейного списка, однонаправленного и двунаправленного списка, циклического списка, стека, дека и очереди;

2)  Сформировать познавательный интерес у учащихся к информатике;

3)  Развить у учащихся творческие способности.

Цель первого урока – дать учащимся на качественном уровне необходимый подготовительный материал, который включает в себя:

1)  Определение линейного списка.

2)  Операции со списками.

3)  Виды списков.

4)  Связанное распределение.

5)  Динамические переменные.

На  2 – 6 уроках учащиеся знакомятся со списками более глубже. Седьмой урок итоговый. Учащимся предлагается тестовая программа, в которой они отвечают на вопросы и  оценивают результаты полученных знаний. В целом же факультатив рассчитан на семь двух часовых занятий.

Общая структура факультатива такова:

Конспекты уроков

Тема: «Очередь»

Цели:

1.   Раскрыть понятие линейного списка «Очередь».

2.   Научиться использовать «Очередь» на практике при решении задач.

3.   Сформировать у учащихся познавательный интерес к информатике.

Лабораторная работа №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.   Сформировать у учащихся познавательный интерес к информатике.

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

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

     Внимательно изучите теоретический материал.

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

Кнопки "<< и >>" служат для перемещения курсора в стеке.

а) Переместитесь вправо до 4 элемента;

б) Переместитесь влево (см. комментарии);

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

Добавьте 1, 3, 5 элементами число 22;

Кнопка "Удалить" служит для удаления элемента из стека.

Удалите 1, 3, 5, последний элементы;

3.   На листе формата А4, опишите ход проделанной работы.

Ответьте на поставленные вопросы:

1)   Как удаляется и добавляется элементы в стек?

2)   Приведи примеры стека на практике?

________________________________________________________________

Задачи для самостоятельного решения:

1)   Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая находит сумму элементов, находящихся в стеке.

2)   Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая добавляет в конец стека S элемент, находящийся в его вершине.

3)   Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая удаляет из стека все элементы, кратные 4 (использовать для промежуточного хранения элементов стека однонаправленный список с заглавным звеном).

Тема: «Тест»

Цели:

1.   Закрепить полученные знания по пройденному курсу.

2.   Выяснить результативность полученных знаний с помощью теста.

3.   Сформировать у учащихся познавательный интерес к информатике.

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

1.   Повторите весь теоретический материал.

2.   Поработайте с демонстрационной программой.

3.   Запустите тест (сервис\тест или Ctrl + T).

4.   Ответьте на поставленные вопросы теста.

5.   Результаты теста сообщить преподавателю.

2.2 Разработка программного средства по теме «Динамические типы данных»

После загрузки демонстрационной программы перед вами появится вот такое окно.

Это главная форма демонстрационной программы. Для формирования списков нажмите кнопку «Обновить». 

Теперь списки сформированы и готовы к работе. Списки содержат целые положительные числа. Указатели указывают на начало списка. С помощью кнопок «<<» «>>» можно перемещать указатель по списку. С помощью кнопки «Добавить» вы можете добавить элемент в список. При нажатии на кнопку «Добавить» всплывает окно «Добавление нового элемента», в котором вы указываете какой элемент хотите добавить и нажимаете кнопку «Ok».

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

При нажатии на кнопку теория (для очереди) открывается окно «Очередь», котором изложена теория и даны примеры.

Аналогично для остальных списков.

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

Если вы будете выбирать каждую в отдельности то они будут отображаться в комментариях на главной форме.

Помощь можно вызвать (Справка\Помощь или F1).

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

Сверху вопрос, ниже варианты ответов. После выбора ответа кнопка «Далее» становится активной, нажав на нее появляется следующий вопрос. После выполнения теста выдается оценка, если неудовлетворительная то открывается окно «Лабораторные работы».

Примечание: после того как тест запустился вызов теста становится неактивным т.е. второй раз учащийся запустить тест не сможет.

Закрыть программу можно нажатием на кнопку «Закрыть» или 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 г.

В листинге приведены только три основных модуля. В первом модуле описан интерфейс программы, обработка всех событий. Второй модуль, отвечай за формирование списков и выполнения всех операций со списками. У второго модуля нет формы. Третий модуль – это тест, служит для проверки и оценивания учащихся. В остальных, не приведенных модулях, описаны: формы для добавления элемента в список, лабораторные работы, теоретический материал с примерами, помощь и информация о программе.

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

  i, j: Integer;

  s: string;

begin

  StatusBar1.Panels[0].Text := '';

  GetQueue(QueueBegin);

  if QueueBegin <> nil then

    begin

      while Edit3.Text[QueuePos] <> ' ' do Inc(QueuePos);

      Inc(QueuePos);

      s := Edit3.Text;

      for i := 1 to QueuePos - 1 do

        if s[i] <> ' ' then s[i] := ' ';

      Edit3.Text := 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;

  i, j: Integer;

begin

  StatusBar1.Panels[0].Text := '';

  qList := ListBegin;

  i := 0;

  while i <> ListPos do

    begin

      qList := qList^.Next;

      Inc(i);

    end;

  if qList <> nil then

    begin

      if qList^.Next <> nil then Inc(ListPos);

      i := 0;

      j := 0;

      while i < 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;

  i, j: Integer;

begin

  StatusBar1.Panels[0].Text := '';

  qListTwo := ListTwoBegin;

  i := 0;

  if ListTwoPos <> 0 then dec(ListTwoPos);

  i := 0;

  j := 0;

  while i < 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;

  i, j: Integer;

begin

  StatusBar1.Panels[0].Text := '';

  qListTwo := ListTwoBegin;

  i := 0;

  while i <> ListTwoPos do

    begin

      qListTwo := qListTwo^.Next;

      Inc(i);

    end;

  if qListTwo <> nil then

    begin

      if qListTwo^.Next <> nil then Inc(ListTwoPos);

      i := 0;

      j := 0;

      while i < 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

  i: Integer;

  s: string;

begin

  StatusBar1.Panels[0].Text := '';

  GetStack(Stack);

  if Stack <> nil then

    begin

      while Edit4.Text[StackPos] <> ' ' do Inc(StackPos);

      Inc(StackPos);

      s := Edit4.Text;

      for i := 1 to StackPos - 1 do

        if s[i] <> ' ' then s[i] := ' ';

      Edit4.Text := 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

  i: Integer;

  s: string;

begin

  StatusBar1.Panels[0].Text := '';

  GetDeckBegin(DeckBegin);

  if DeckBegin <> nil then

    begin

      while Edit5.Text[DeckBeginPos] <> ' ' do Inc(DeckBeginPos);

      Inc(DeckBeginPos);

      s := Edit5.Text;

      for i := 1 to DeckBeginPos - 1 do

        if s[i] <> ' ' then s[i] := ' ';

      Edit5.Text := 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

  i, a: Integer;

  s: string;

begin

  StatusBar1.Panels[0].Text := '';

  GetDeckEnd(DeckEnd);

  if DeckEnd <> nil then

    begin

      while Edit5.Text[DeckEndPos] <> ' ' do Dec(DeckEndPos);

      Dec(DeckEndPos);

      s := Edit5.Text;

      for i := DeckEndPosition downto DeckEndPos + 1 do

        if s[i] <> ' ' then s[i] := ' ';

      Edit5.Text := s;

      //удаляем все пробелы конце строки

      s := '';

      i := Length(Edit5.Text) - 1;

      while Edit5.Text[i] = ' ' do Dec(i);

      for a := 1 to i do s := s + Edit5.Text[a];

      Edit5.Text := 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

  i, a: Integer;

  s1, s2: string;

begin

  GetQueue(QueueBegin);

  if QueueBegin <> nil then

    begin

      i := QueuePos;

      while (Edit3.Text[i] <> ' ') and (i <= Length(Edit3.Text)) do Inc(i);

      Inc(i);

      s1 := '';

      s2 := '';

      for a := 1 to QueuePos - 1 do s1 := s1 + Edit3.Text[a];

      for a := i to Length(Edit3.Text) do s2 := s2 + Edit3.Text[a];

      Edit3.Text := s1 + s2;

    end;

end;

procedure TForm1.Button9Click(Sender: TObject);

begin

  Form4.Show;

end;

procedure TForm1.Button14Click(Sender: TObject);

var

  i, a: Integer;

  s1, s2: string;

begin

  GetStack(Stack);

  i := StackPos;

  while (Edit4.Text[i] <> ' ') and (i <= Length(Edit4.Text)) do Inc(i);

  Inc(i);

  s1 := '';

  s2 := '';

  for a := 1 to StackPos - 1 do s1 := s1 + Edit4.Text[a];

  for a := i to Length(Edit4.Text) do s2 := s2 + Edit4.Text[a];

  Edit4.Text := s1 + s2;

end;

procedure TForm1.Button13Click(Sender: TObject);

begin

  Form6.Show;

end;

procedure TForm1.Button17Click(Sender: TObject);

begin

  Form7.Show;

end;

procedure TForm1.Button18Click(Sender: TObject);

begin

  Form8.Show;

end;

procedure TForm1.Button26Click(Sender: TObject);

begin

  StatusBar1.Panels[0].Text := 'Нельзя !!!';

  Memo1.Lines.Add('В цикл. списке нельзя перемещаться назад, т.к. по сути цикл. список это однонаправ. список и следовательно связь существует только в одну сторону;');

end;

procedure TForm1.Button25Click(Sender: TObject);

var

  qRoundList: List;

  i, j: Integer;

  Count: Integer;

begin

  StatusBar1.Panels[0].Text := '';

  qRoundList := RoundList^.Next;

  // Подсчет кол-ва елементов в списке

  Count := 1;

  while qRoundList <> RoundList do

    begin

      Inc(Count);

      qRoundList := qRoundList^.Next;

    end;

  qRoundList := RoundList;

  i := 0;

  while i <> RoundListPos do

    begin

      qRoundList := qRoundList^.Next;

      Inc(i);

    end;

  if qRoundList <> nil then

    begin

      if qRoundList^.Next <> nil then Inc(RoundListPos);

      if RoundListPos > Count - 1 then RoundListPos := 0;

      i := 0;

      j := 0;

      while i < RoundListPos do

        begin

          Inc(j);

          if Edit7.Text[j] = ' ' then Inc(i);

        end;

      if RoundListPos = 0 then j := -1;

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

    end;

end;

procedure TForm1.Button23Click(Sender: TObject);

begin

  Form9.Show;

end;

procedure TForm1.Button24Click(Sender: TObject);

begin

  if RoundList <> nil then

    begin

      DeleteFromRoundList(RoundListPos);

      if RoundList <> nil then DoNewEditRoundList;

    end

  else

    begin

      Edit7.Text := '';

      ShowMessage('Циклический список пуст');

      Button24.Enabled := False;

      Button25.Enabled := False;

      Button26.Enabled := False;

      Image7.Hide;

    end;

end;

procedure TForm1.N2Click(Sender: TObject);

begin

  Close;

end;

procedure TForm1.N5Click(Sender: TObject);

begin

  AboutBox.Visible := True;

end;

procedure TForm1.N4Click(Sender: TObject);

begin

  Form10.Visible := True;

end;

procedure TForm1.Button27Click(Sender: TObject);

begin

  Form11.Show;

end;

procedure TForm1.Button30Click(Sender: TObject);

begin

  Form12.Show;

end;

procedure TForm1.Button29Click(Sender: TObject);

begin

  Form13.Show;

end;

procedure TForm1.Button31Click(Sender: TObject);

begin

  Form14.Show;

end;

procedure TForm1.Button32Click(Sender: TObject);

begin

  Form15.Show;

end;

procedure TForm1.N8Click(Sender: TObject);

begin

  Form1.Hide;

  Form16.Show;

  N8.Enabled := False;

end;

procedure TForm1.N11Click(Sender: TObject);

begin

  Memo1.Clear;

  Memo1.Lines.Add('                      Лабораторная работа №1.');

  Memo1.Lines.Add('                               "Списки"');

  Memo1.Lines.Add('______________________________________________________________');

  Memo1.Lines.Add('1. Нажмите кнопку "Теория" для получения информации о списках.');

  Memo1.Lines.Add('   Внимательно изучите теоретический материал.');

  Memo1.Lines.Add('');

  Memo1.Lines.Add('2. На листе формата А4, опишите ход проделанной работы.');

  Memo1.Lines.Add('   Ответьте на поставленные вопросы.');

  Memo1.Lines.Add('   1) Что такое линейный список?');

  Memo1.Lines.Add('   2) Какие операции можно выполнить с линейным списком?');

  Memo1.Lines.Add('   3) Какие существую еще списки?');

  Memo1.Lines.Add('   4) Что представляет из себя связанное распределение?');

  Memo1.Lines.Add('   5) Чем отличается связанное распределение от последовательного?');

  Memo1.Lines.Add('   6) Что такое динамические переменные? Функции new и nil.');

end;

procedure TForm1.Button33Click(Sender: TObject);

begin

  Form17.Show;

end;

procedure TForm1.N21Click(Sender: TObject);

begin

  Memo1.Clear;

  Memo1.Lines.Add('                      Лабораторная работа №2.');

  Memo1.Lines.Add('       "Однонаправленный и двунаправленный список"');

  Memo1.Lines.Add('______________________________________________________________');

  Memo1.Lines.Add('1. Нажмите кнопку "Теория" для однонаправленного и ');

  Memo1.Lines.Add('   двунаправленного списка.');

  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, 7 элемента цифру 33 в обоих списках;');

  Memo1.Lines.Add('   б) Добавте 1-м и 3-м  элементом цифру 55 в двунаправленном списке;');

  Memo1.Lines.Add('   Кнопка "Удалить" служит для удаления элемента из списка.');

  Memo1.Lines.Add('   а) Удалите 3, 5, 7 элементы в однонаправленном списке;');

  Memo1.Lines.Add('   б) Удалите последний, 1 и 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.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

  i: 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;

      i := 0;

      while (i < 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;

  i: Integer;

begin

  if RoundList^.Next = RoundList then //один элемент в списке

    begin

      if RoundList <> nil then Dispose(RoundList);

      RoundList := nil;

    end

  else // не один элемент в списке

    begin

      i := 1;

      q := RoundList;

      while i < RoundListPos do

        begin

          Inc(i);

          q := q^.Next;

        end;

      if i <> 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;

      i := 1;

      while q <> RoundList do

        begin

          Inc(i);

          q := q^.Next;

        end;

      if i = RoundListPos then

        begin

          RoundListPos := 0;

          Form1.Image7.Left := 9;

        end;

    end;

end;

procedure DeleteFromList(Position: Integer); //Удаляет элемент под

                                             //номером Position

var

  i: 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

          i := 0;

          while (i < 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(r);

            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

  i: 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;

      i := 0;

      while (i < 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

  i: 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

          i := 0;

          while (i < 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(r);

            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

  i: 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;            //

  qTwo := UkTwo;      // Формируем указатели на начало списков

  qQueue := UkQueue;  //

  for i :=  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.