Содержание Введение 3 Глава 1. Динамические типы данных 1.1 Списки. Очередь. Стек. Дек. 1.2 Динамические информационные структуры 22 Глава 2. Разработка факультативного курса Динамические типы данных 2.1 Методические рекомендации по введению факультативного курса в школе 2.2 Разработка программного средства по теме Динамические типы данных 38
Заключение 42 Литература 44 Приложение 1. Листинг программы 45 Введение Сегодня человек живет в мире, где информация имеет огромное значение. Жизненно важно научиться правильно с ней работать и использовать различные инструменты для этой работы. Одним из таких инструментов является компьютер, который стал универсальным помощником человеку в различных сферах деятельности. В вычислительной машине программы обычно оперируют с таблицами информации.
В большинстве случаев это не просто аморфные массы числовых величин в таблицах присутствуют важные структурные отношения между элементами данных. Чтобы правильно использовать машину, важно добиться хорошего понимания структурных отношений, существующих между данными, способов представления таковых в машине и методов работы с ними. Изучить наиболее важные факты, касающиеся информационных структур их статические и динамические свойства средства распределения памяти и представления данных эффективные алгоритмы для
создания, изменения, разрушения структурной информации и доступа к ней. В простейшей форме таблица может быть линейным списком элементов. Тогда присущие ей структурные свойства содержат в себе ответы на такие вопросы, как Какой элемент является первым в списке? какой - последним? какой элемент предшествует данному или следует за данным? Можно много говорить о структуре даже в этом совершенно очевидном случае.
В более сложных ситуациях таблица может быть двумерным массивом т. е. матрицей, иногда называемой сеткой, имеющей структуру строк и столбцов , либо может быть n-мерным массивом при весьма больших значениях n, либо она может иметь структуру дерева, представляющего отношения иерархии или ветвления, либо это может быть сложная многосвязанная структура с огромным множеством взаимных соединений, такая, например, которую можно найти в человеческом мозгу. Системы обработки списков полезны в очень многих случаях,
однако при их использовании программист нередко сталкивается с излишними ограничениями. Теперь целесообразно определить несколько терминов и понятий, которыми мы будем часто пользоваться в дальнейшем. Информация в таблице представлена множеством узлов некоторые авторы называют их записями , бусинами , объектами мы иногда вместо узел будем говорить элемент . Каждый узел состоит из одного или нескольких последовательных слов в памяти машины, разделенных на
именуемые части, называемые полями. В простейшем случае узел - это просто одно слово памяти, он имеет только одно поле, включающее все слово. В связи с этим цель нашей работы Знакомство с теоретическим положением, касающиеся информационных структур и разработка программного средства Динамические структуры данных. Этой целью определяется следующая гипотеза если при изучении данной темы будет использоваться компьютер, то усвоение темы будет более успешным, так как усиливает
мотивацию, и влияет на конечный результат. Предмет исследования Изучение динамических информационных структур. Объект исследования Знакомство учащихся с основами программирования. Достижением цели и согласно поставленной гипотезы определяются следующие задачи 1. Изучить литературу по теме динамические информационные структуры, педагогическую и методическую по теме исследования 2. Проанализировать виды динамических информационных структур 3.
Разработать факультатив по теме исследования 4. Разработать программный продукт по теме исследования. Глава 1. Динамические типы данных1.1 Списки. Очередь. Стек. Дек.Список list - набор элементов, расположенных в определенном порядке. Таким набором быть может ряд знаков в слове, слов в предложений в книге. Этот термин может также относиться к набору элементов на диске.
Использование при обработке информации списков в качестве типов данных привело к появлению в языках программирования средств обработки списков. Список очередности pushup list - список, в котором последний поступающий элемент добавляется к нижней части списка. Список с использованием указателей linked list - список, в котором каждый элемент содержит указатель на следующий элемент списка. Линейный список linear list - это множество, состоящее из узлов , структурные
свойства которого по сути ограничиваются лишь линейным одномерным относительным положением узлов, т. е. теми условиями, что если , то является первым узлом если , то k-му узлу предшествует и за ним следует является последним узлом. Операции, которые мы имеем право выполнять с линейными списками, включают, например, следующие 1. Получить доступ к k-му узлу списка, чтобы проанализировать и или изменить содержимое его полей. 2. Включить новый узел непосредственно перед k-ым узлом.
3. Исключить k-й узел. 4. Объединить два или более линейных списка в один список. 5. Разбить линейный список на два или более списка. 6. Сделать копию линейного списка. 7. Определить количество узлов в списке. 8. Выполнить сортировку узлов списка в возрастающем порядке по некоторым полям в узлах. 9. Найти в списке узел с заданным значением в некотором поле.
Специальные случаи k 1 и k n в операциях 1 , 2 и 3 особо выделяются, поскольку в линейном списке проще получить доступ к первому и последнему элементам, чем к произвольному элементу. В машинных приложениях редко требуются все девять из перечисленных выше операций в самом общем виде. Мы увидим, что имеется много способов представления линейных списков в зависимости от класса операций, которые необходимо выполнять наиболее часто. По-видимому, трудно спроектировать единственный метод
представления для линейных списков, при котором все эти операции выполняются эффективно например, сравнительно трудно эффективно реализовать доступ к k-му узлу в длинном списке для произвольного k, если в то же время мы включаем и исключаем элементы в середине списка. Следовательно, мы будем различать типы линейных списков по главным операциям, которые с ними выполняются. Очень часто встречаются линейные списки, в которых включение, исключение или доступ к значениям почти
всегда производятся в первом или последнем узлах, и мы дадим им специальные названия Многие люди поняли важность стеков и очередей и дали другие названия этим структурам стек называли пуш-даун push-down списком, реверсивной памятью, гнездовой памятью, магазином, списком типа LIFO last-in-first-out - последним включается - первым исключается и даже употребляется такой термин, как список йо-йо! Очередь иногда называют - циклической памятью или списком типа
FIFO first-in-first-out - первым включается - первым исключается . В течение многих лет бухгалтеры использовали термины LIFO и FIFO как названия методов при составлении прейскурантов. Еще один термин архив применялся к декам с ограниченным выходом, а деки с ограниченным входом называли перечнями , или реестрами . Такое разнообразие названий интересно само по себе,
Поскольку оно свидетельствует о важности этих понятий. Слова стек и очередь постепенно становятся стандартными терминами из всех других словосочетаний, перечисленных выше, лишь пуш-даун список остается еще довольно распространенным, особенно в теории автоматов. При описании алгоритмов, использующих такие структуры, принята специальная терминология так, мы помещаем элемент на верх стека или снимаем верхний элемент.
Внизу стека находится наименее доступный элемент, и он не удаляется до тех пор, пока не будут исключены все другие элементы. Часто говорят, что элемент опускается push down в стек или что стек поднимается pop up , если исключается верхний элемент. Эта терминология берет свое начало от стеков закусок, которые можно встретить в кафетериях, или по аналогии с колодами карт в некоторых перфораторных устройствах. Краткость слов опустить и поднять имеет свое преимущество, но эти термины ошибочно предполагают движение
всего списка в памяти машины. Физически, однако, ничего не опускается элементы просто добавляются сверху, как при стоговании сена или при укладке кипы коробок. В применении к очередям мы говорим о начале и конце очереди объекты встают в конец очереди и удаляются в момент, когда наконец достигают ее начала. Говоря о деках, мы указываем левый и правый концы. Понятие верха, низа, начала и конца применимо иногда и к декам, если они используются как стеки или
очереди. Не существует, однако, каких-либо стандартных соглашений относительно того, где должен быть верх, начало и конец слева или справа. Таким образом, мы находим, что в наших алгоритмах применимо богатое разнообразие описательных слов сверху - вниз - для стеков, слева - направо - для деков и ожидание в очереди - для очередей. Однонаправленный и двунаправленный список - это линейный список, в котором все исключения и добавления происходят в любом месте списка.
Однонаправленный список отличается от двунаправленного списка только связью. То есть в однонаправленном списке можно перемещаться только в одном направлении из начала в конец , а двунаправленном - в любом. Из рисунка это видно сверху однонаправленный список, а снизу двунаправленный На рисунке видно как добавляется и удаляется элемент из двунаправленного списка. При добавлении нового элемента обозначен N между элементами 2 и 3.
Связь от 3 идет к N, а от N к 4, а связь между 3 и 4 удаляется. В однонаправленном списке структура добавления и удаления такая же только связь между элементами односторонняя. Очередь queue - линейный список, в котором все включения производятся на одном конце списка, а все исключения и обычно всякий доступ делаются на другом его конце. Очередь - тип данных, при котором новые данные располагаются следом за существующими в порядке поступления
поступившие первыми данные при этом обрабатываются первыми. В некоторых разделах математики слово очередь используют в более широком смысле, обозначая любой сорт списка, в котором производятся включения и исключения указанные выше специальные случаи называются тогда очередями с различными дисциплинами . Однако здесь термин очередь используется лишь в узком смысле, аналогичном упорядоченным очередям людей, ожидающим обслуживания.
Правило здесь такое же, как в живой очереди первым пришёл-первым обслужен. Пришел новый покупатель, встал добавился в конец очереди, а который уже отоварился ушел удалился из начала очереди. То есть первым пришел, первым ушел. Другими словами, у очереди есть голова head и хвост tail . Элемент, добавляемый в очередь, оказывается в её хвосте, как только что подошедший покупатель элемент,
удаляемый из очереди, находится в её голове, как тот покупатель, что отстоял дольше всех. В очереди новый элемент добавляется только с одного конца. Удаление элемента происходит на другом конце. В данном случае это может быть только 4 элемент. Очередь по сути однонаправленный список, только добавление и исключение элементов происходит на концах списка. Стек stack - линейный список, в котором все включения и исключения и обычно всякий доступ делаются
в одном конце списка. Стек - часть памяти ОЗУ компьютера, которая предназначается для временного хранения байтов, используемых микропроцессором при этом используется порядок запоминания байтов последним вошел - первым вышел, поскольку такие ввод и вывод организовывать проще всего, также операции осуществляются очень быстро. Действия со стеком производится при помощи регистра указателя стека. Любое повреждение этой части памяти приводит к фатальному сбою.
Стек в виде списка pushdown list - стек, организованный таким образом, что последний вводимый в область памяти элемент размещается на вершине списка. Из стека мы всегда исключаем младший элемент из имеющихся в списке, т. е. тот, который был включен позже других. Для очереди справедливо в точности противоположное правило исключается всегда самый старший элемент узлы покидают список в том порядке, в котором они в него вошли.
Стеки очень часто встречаются в практике. Простым примером может служить ситуация, когда мы просматриваем множество данных и составляем список особых состояний или объектов, которые должны обрабатываться позднее когда первоначальное множество обработано, мы возвращаемся к этому списку и выполняем последующую обработку, удаляя элементы из списка, пока список не станет пустым. Для этой цели пригодны как стек, так и очередь, но стек, как правило, удобнее.
При решении задач наш мозг ведет себя как стек одна проблема приводит к другой, а та в свою очередь к следующей мы накапливаем в стеке эти задачи и подзадачи и удаляем их по мере того, как они решаются. Аналогично процесс входов в подпрограммы и выходов из них при выполнении машинной программы подобен процессу функционирования стека. Стеки особенно полезны при обработке языков, имеющих структуру вложений. К ним относятся языки программирования, арифметические выражения и немецкие
Schachtelsatze буквально вложенные предложения . Вообще, стеки чаще всего возникают в связи с алгоритмами, имеющими явно или неявно рекурсивный характер. Представьте себе, что четыре железнодорожных вагона находятся на входной стороне пути рис. 1 и перенумерованы соответственно 1, 2, 3 и 4. Предположим, что мы выполняем следующую последовательность операций которые согласуются с направлением стрелок на рисунке и не требуют, чтобы вагоны перепрыгивали друг через друга .
Отправьте а вагон 1 в стек b вагон 2 в стек с вагон 2 на выход d вагон 3 в стек е вагон 4 в стек f вагон 4 на выход g вагон 3 на выход h вагон 1 на выход. В результате этих операций первоначальный порядок вагонов, 1234, изменился на 2431. Цель этого упражнения состоит в том, чтобы исследовать, какие перестановки можно получить, используя стеки, очереди и деки. В стеке элемент добавляется и удаляется только с одного
конца. На рисунке это элемент N. То есть если он добавился, то удаляется может сначала только он, а уж потом все остальные. Стек можно представить себе как коробку, в которую складывают какие-нибудь предметы, чтобы достать самый нижний нужно предварительно вытащить остальные. Стек можно уподобить стопке тарелок, из которой можно взять верхнюю и на которую можно положить новую тарелку. Другое название стека в русской литературе - магазин - понятно всякому, кто разбирал автомат
Калашникова . Дек deck стек с двумя концами - линейный список, в котором все включения и исключения и обычно всякий доступ делаются на обоих концах списка. Иногда аналогия с переключением железнодорожных путей, предложенная Э. Дейкстрой, помогает понять механизм стека. На рис. 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 с целыми коэффициентами. Существует много задач, в которых математик предпочитает работать с многочленами, а не просто с числами речь идет об операциях, подобных умножению EMBED Equation.3 на EMBED Equation.3 , дающему в итоге EMBED Equation.3 .
Связанное распределение - естественный инструмент для этой цели, поскольку количество слагаемых в многочлене может расти и их число нельзя заранее предсказать кроме того, может потребоваться, чтобы в памяти одновременно присутствовало несколько многочленов. 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. Разработка факультативного курса Динамические типы данных2.1 Методические рекомендации по введению факультативного курса в школеВ системе школьных факультативов необходимо изучение информатики с большей полнотой. Это требует в свою очередь особенно тщательного отбора материала который может быть хорошо усвоен учащимися за ограниченное количество часов. Разработанный нами факультатив рассчитан на 14 часов.
Задачи факультатива 1 Ввести понятие линейного списка, однонаправленного и двунаправленного списка, циклического списка, стека, дека и очереди 2 Сформировать познавательный интерес у учащихся к информатике 3 Развить у учащихся творческие способности. Цель первого урока - дать учащимся на качественном уровне необходимый подготовительный материал, который включает в себя 1 Определение линейного списка. 2 Операции со списками.
3 Виды списков. 4 Связанное распределение. 5 Динамические переменные. На 2 - 6 уроках учащиеся знакомятся со списками более глубже. Седьмой урок итоговый. Учащимся предлагается тестовая программа, в которой они отвечают на вопросы и оценивают результаты полученных знаний. В целом же факультатив рассчитан на семь двух часовых занятий. Общая структура факультатива такова урока Тема Кол-во часов 1.
Списки 2 2. Однонаправленный и двунаправленный список 2 3. Циклический список 2 4. Очередь 2 5. Стек 2 6. Дек 2 7. Тест 2 Конспекты уроков Тема Очередь Цели 1. Раскрыть понятие линейного списка Очередь. 2. Научиться использовать Очередь на практике при решении задач. 3. Сформировать у учащихся познавательный интерес к информатике.
Этап урока Время мин. 1. Организационный момент 2 2. Подготовка к лабораторной работе 10 3. Выполнение лабораторной работы 20 4. Закрепление 8 Лабораторная работа 4 по теме Очередь. 1. Нажмите кнопку Теория для очереди. Внимательно изучите теоретический материал. 2. Нажмите кнопку Обновить для формирования списков.
Кнопки и служат для перемещения курсора по очереди. а Переместитесь вправо до 3 элемента б Переместитесь влево см. коментарии Кнопка Добавить служит для добавления элемента в очередь. а Добавьте 1, 4, 5-м элементами число 99 б Добавьте последним число 999 Кнопка Удалить служит для удаления элемента из очереди.
Удалите 1, 2, 3 элементы 3. На листе формата А4, опишите ход проделанной работы. Ответьте на поставленные вопросы 1 Как удаляется и добавляется элементы в очереди? 2 В чем различие и сходство очереди и однонаправленного списка? 3 Что называется головой и хвостом очереди? 4 Как располагаются элементы в очереди? Задачи для самостоятельного решения 1 Пусть уже построена очередь
Q, содержащая целые числа. Вычислить сумму и произведение элементов, находящихся в очереди. 2 Пусть уже построена очередь Q, содержащая целые числа. Сформировать новую очередь P, состоящую из элементов очереди Q, кратных числу 3. 3 Пусть уже построена очередь Q, содержащая целые числа. Вычислить количество простых чисел, находящихся в очереди.
Учитель Ученик ПК Тетрадь 2 этап - Подготовка к лабораторной работе Запускаем демонстрационную программу. Нажмите кнопку теория. Перед вами появилось окно с теоретическим материалом. Внимательно ознакомьтесь с новым материалом. Обратите внимание на примеры создания очереди и получения элемента из очереди. Провести аналогию между очередью и однонаправленным списком.
Знакомится с новым материалом. Теоретический материал по теме очередь. Определение очереди. Порядок расположения данных. Примеры создания очереди и получения элемента из очереди. 3 этап - Выполнение лабораторной работы Открываем лабораторную работу 4. Внимательно читаем задание и начинаем выполнять. Выполняет лабораторную работу.
Лабораторная работа 4. После выполнения заданий ответьте на поставленные вопросы. Отвечает на вопросы. Ответы на вопросы. Попробуйте выполнить практические задания. Решает задачи. Delphi или Pascal. Листинг задачи. 4 этап - Закрепление лабораторной работы Итак, давайте подведем итоги сегодняшней работы. Что называется очередью? Очередь - линейный список, в котором все включения производятся на одном конце
списка, а все исключения на другом конце. Как располагаются данные в очереди? Очередь - тип данных, при котором новые данные располагаются следом за существующим в порядке поступления Какие данные в очереди обрабатываются первыми? Данные поступившие первыми обрабатываются первыми. Что такое голова, хвост очереди? Элемент, добавляемый в очередь, оказывается в её хвосте. Элемент, удаляемый из очереди, находится в её голове.
В чем схожи очередь и однонаправленный список? Очередь, по сути, однонаправленный список, только добавление и исключение элементов происходит на концах списка. Тема Стек Цели 1. Раскрыть понятие линейного списка Стек. 2. Научиться использовать Стек на практике при решении задач. 3. Сформировать у учащихся познавательный интерес к информатике.
Этап урока Время мин. 1. Организационный момент 2 2. Подготовка к лабораторной работе 10 3. Выполнение лабораторной работы 20 4. Закрепление 8 Лабораторная работа 5 по теме Стек. 1. Нажмите кнопку Теория для стека. Внимательно изучите теоретический материал. 2. Нажмите кнопку Обновить для формирования списков.
Кнопки и служат для перемещения курсора в стеке. а Переместитесь вправо до 4 элемента б Переместитесь влево см. комментарии Кнопка Добавить служит для добавления элемента в стек. Добавьте 1, 3, 5 элементами число 22 Кнопка Удалить служит для удаления элемента из стека. Удалите 1, 3, 5, последний элементы 3. На листе формата
А4, опишите ход проделанной работы. Ответьте на поставленные вопросы 1 Как удаляется и добавляется элементы в стек? 2 Приведи примеры стека на практике? Задачи для самостоятельного решения 1 Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая находит сумму элементов, находящихся в стеке. 2 Предположим, что уже построен стек, элементами которого являются целые числа.
Написать программу, которая добавляет в конец стека S элемент, находящийся в его вершине. 3 Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая удаляет из стека все элементы, кратные 4 использовать для промежуточного хранения элементов стека однонаправленный список с заглавным звеном . Учитель Ученик ПК Тетрадь 2 этап - Подготовка к лабораторной работе
Запускаем демонстрационную программу. Нажмите кнопку теория. Перед вами появилось окно с теоретическим материалом. Внимательно ознакомьтесь с новым материалом. Обратите внимание на примеры создания стека и получения элемента из стека. Провести аналогию между очередью и стеком. Знакомится с новым материалом. Теоретический материал по теме стек.
Определение стека. Порядок расположения данных. Примеры создания стека и получения элемента из стека. 3 этап - Выполнение лабораторной работы Открываем лабораторную работу 5. Внимательно читаем задание и начинаем выполнять. Выполняет лабораторную работу. Лабораторная работа 5. После выполнения заданий ответьте на поставленные вопросы. Отвечает на вопросы. Ответы на вопросы. Попробуйте выполнить практические задания.
Решает задачи. Delphi или Pascal. Листинг задачи. 4 этап - Закрепление лабораторной работы Итак, давайте подведем итоги сегодняшней работы. Что называется стеком? Стек - линейный список, в котором все включения и исключения делаются в одном конце списка. Как располагаются данные в стеке? Стек, организован таким образом, что последний вводимый в область памяти элемент размещается на вершине списка.
Различия между очередью и стеком? Из стека мы всегда исключаем младший элемент из имеющихся в списке, т. е. тот, который был включен позже других. Для очереди справедливо в точности противоположное правило исключается всегда самый старший элемент узлы покидают список в том порядке, в котором они в него вошли. Тема Тест Цели 1. Закрепить полученные знания по пройденному курсу. 2. Выяснить результативность полученных знаний с помощью теста.
3. Сформировать у учащихся познавательный интерес к информатике. Этап урока Время мин. 1. Организационный момент 2 2. Подготовка к тесту 10 3. Тест 20 4. Подведение итогов 8 Лабораторная работа 7 по теме Тест. 1. Повторите весь теоретический материал. 2. Поработайте с демонстрационной программой. 3. Запустите тест сервис тест или
Ctrl T . 4. Ответьте на поставленные вопросы теста. 5. Результаты теста сообщить преподавателю. Учитель Ученик ПК Тетрадь 2 этап - Подготовка к тесту Запускаем демонстрационную программу. Внимательно просмотрите теоретический материал по пройденному курсу. Обратите внимание на определения списков, на то как добавляется и исключаются элементы из списков,
на общее и различия списков. Повторяет пройденный материал. Теоретический материал по пройденному курсу. Определения списков. Включение и исключение элементов из списков. Общее и различия между списками. 3 этап - Тест Запускаем тест. Меню Сервис Тест . Перед вами появилось окно Тест. В верхнем левом поле предлагается вопрос, ниже под полем предлагаются на выбор несколько вариантов
ответов. Правой клавишей мыши щелкаете на правильный по вашему мнению ответ. После выбора ответа, кнопка Далее становится активной, нажимаете ее. После нажатия на кнопку Далее, появится следующий вопрос. Продолжаете далее, пока не появится оценка за тест. Тестируется. Тест. Результат сообщите учителю. Оценка за тест.
Если результат оказывается неудовлетворительный, ученику предлагается повторить пройденный материал, и проверить свои знания на следующем уроке. После проведения теста, вызов теста блокируется. 4 этап - Подведение итогов Итак, мы с вами изучили линейные списки. Подведем итоги. Вы ознакомились с такими списками как однонаправленный и двунаправленный списки, стек, дек, очередь и циклический список. Вы узнали, что такое связанное распределение и динамические информационные
структуры. Научились использовать полученные знания на практике при решении задач. При помощи теста оценили результаты полученных знаний. Если кого, что-то заинтересовало или кто-то полностью не усвоил пройденный материал, то он может подойти к учителю и получить интересующие его сведения. Сообщаются оценки за тест, и за факультатив в общем. 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 г. Приложение 1. Листинг программы В листинге приведены только три основных модуля. В первом модуле описан интерфейс программы, обработка всех событий. Второй модуль, отвечай за формирование списков и выполнения всех операций со списками.
У второго модуля нет формы. Третий модуль - это тест, служит для проверки и оценивания учащихся. В остальных, не приведенных модулях, описаны формы для добавления элемента в список, лабораторные работы, теоретический материал с примерами, помощь и информация о программе. unit Unit1 Интерфейс interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, ExtCtrls,
StdCtrls, ComCtrls, Unit2, Unit3, Unit4, Unit5, Unit6, Unit7, Unit8, Unit9, Menus, Unit11, Unit12, Unit13, Unit14, Unit15, Unit16, Unit17 type TForm1 class TForm Panel1 TPanel Edit1 TEdit Label1 TLabel Button1 TButton Button2 TButton Button3 TButton Button4 TButton Panel2
TPanel Label2 TLabel Edit2 TEdit Button5 TButton Button6 TButton Button7 TButton Button8 TButton Panel3 TPanel Label3 TLabel Edit3 TEdit Button9 TButton Button10 TButton Button11 TButton Button12 TButton Panel4 TPanel Label4 TLabel Edit4 TEdit Button13 TButton Button14
TButton Button15 TButton Button16 TButton Panel5 TPanel Label5 TLabel Edit5 TEdit Button17 TButton Button18 TButton Button19 TButton Button20 TButton Panel6 TPanel Edit6 TEdit Label6 TLabel Button21 TButton StatusBar1 TStatusBar Image1 TImage Image2 TImage Image3 TImage
Image4 TImage Image5 TImage Button22 TButton Memo1 TMemo Label7 TLabel Image6 TImage Bevel1 TBevel Panel7 TPanel Button23 TButton Button24 TButton Button25 TButton Button26 TButton Edit7 TEdit Image7 TImage Label8 TLabel Panel8 TPanel Image8 TImage MainMenu1 TMainMenu N1
TMenuItem N2 TMenuItem N3 TMenuItem N4 TMenuItem N5 TMenuItem Button27 TButton Button28 TButton Button30 TButton Button29 TButton Button31 TButton Button32 TButton N6 TMenuItem N7 TMenuItem N8 TMenuItem N11 TMenuItem N21 TMenuItem N31 TMenuItem N41 TMenuItem
N51 TMenuItem N61 TMenuItem N71 TMenuItem Button33 TButton N9 TMenuItem procedure Button12Click Sender TObject procedure Button11Click Sender TObject procedure Button22Click Sender TObject procedure Button21Click Sender TObject procedure Button1Click Sender TObject procedure
Button3Click Sender TObject procedure Button4Click Sender TObject procedure Button7Click Sender TObject procedure Button8Click Sender TObject procedure FormClose Sender TObject var Action TCloseAction procedure Button15Click Sender TObject procedure Button16Click Sender TObject procedure
Button20Click Sender TObject procedure FormCreate Sender TObject procedure Button19Click Sender TObject procedure Button5Click Sender TObject procedure Button2Click Sender TObject procedure Button6Click Sender TObject procedure Button10Click Sender TObject procedure Button9Click
Sender TObject procedure Button14Click Sender TObject procedure Button13Click Sender TObject procedure Button17Click Sender TObject procedure Button18Click Sender TObject procedure Button26Click Sender TObject procedure Button25Click Sender TObject procedure Button23Click Sender TObject procedure
Button24Click Sender TObject procedure N2Click Sender TObject procedure N5Click Sender TObject procedure N4Click Sender TObject procedure Button27Click Sender TObject procedure Button30Click Sender TObject procedure Button29Click Sender TObject procedure Button31Click
Sender TObject procedure Button32Click Sender TObject procedure N8Click Sender TObject procedure N11Click Sender TObject procedure Button33Click Sender TObject procedure N21Click Sender TObject procedure N31Click Sender TObject procedure N41Click Sender TObject procedure N51Click Sender TObject procedure
N61Click Sender TObject procedure N71Click Sender TObject procedure N9Click Sender TObject private public end procedure DoNewEditList procedure DoNewEditListTwo procedure DoNewEditRoundList var Form1 TForm1 ListBegin List указатель на однонапр. список ListPos Integer позиция в однонапр. списке ListTwoBegin
ListTwo указатель на двунапр. список ListTwoPos Integer позиция в двунапр. списке QueueBegin List указатель на очередь QueuePos Integer позиция в очереди содержит кол-во символов в Edit до первого элемента Stack List указатель на стек StackPos Integer позиция в стеке содержит кол-во символов в Edit до первого элемента DeckBegin, DeckEnd ListTwo указатели на начало и конец дека
DeckBeginPos, DeckEndPos Integer позиции в деке DeckEndPos содержит кол-во символов в Edit от DeckEndPosition до последнего элемента DeckEndPosition Integer позиция последнего элемента в деке содержит первоначальное кол-во символов в Edit до последнего элемента RoundList List указатель в циклическом списке RoundListPos Integer позиция в циклическом списке implementation uses
O programm, Help, Un18 Lab R .DFM procedure DoNewEditList var q List begin q ListBegin Form1.Edit1.Text while q nil do begin Form1.Edit1.Text Form1.Edit1.Text IntToStr q .Info q q .Next end end procedure DoNewEditListTwo var q ListTwo begin q ListTwoBegin Form1.Edit2.Text while q nil do begin
Form1.Edit2.Text Form1.Edit2.Text IntToStr q .Info q q .Next end end procedure DoNewEditRoundList var q List begin q RoundList .Next Form1.Edit7.Text IntToStr RoundList .Info while q RoundList do begin Form1.Edit7.Text Form1.Edit7.Text IntToStr q .Info q q .Next end end procedure TForm1.Button12Click
Sender TObject var 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.
| ! |
Как писать рефераты Практические рекомендации по написанию студенческих рефератов. |
| ! | План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом. |
| ! | Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач. |
| ! | Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты. |
| ! | Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ. |
| → | Виды рефератов Какими бывают рефераты по своему назначению и структуре. |