Быстрый поиск

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

Содержание

Введение 3

Глава 1. Динамические типы данных_ 6

1.1 Списки. Очередь. Стек. Дек. 6

1.2 Динамические информационные структуры_ 22

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

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

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

Заключение 42

Литература_ 44

Приложение 1. (Листинг программы) 45

Введение

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

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

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

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

В простейшей форме таблица может быть линейным списком элементов. Тогда присущие ей структурные свойства содержат в себе ответы на такие вопросы, как: "Какой элемент является первым в списке? какой — последним? какой элемент предшествует данному или следует за данным?" Можно много говорить о структуре даже в этом совершенно очевидном случае.

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

Системы обработки списков полезны в очень многих случаях, однако при их использовании программист нередко сталкивается с излишними ограничениями.

Теперь целесообразно определить несколько терминов и понятий, которыми мы будем часто пользоваться в дальнейшем. Информация в таблице представлена множеством узлов (некоторые авторы называют их "записями", "бусинами", "объектами"); мы иногда вместо "узел" будем говорить "элемент". Каждый узел состоит из одного или нескольких последовательных слов в памяти машины, разделенных на именуемые части, называемые полями. В простейшем случае узел — это просто одно слово памяти, он имеет только одно поле, включающее все слово.

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

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

Предмет исследования: Изучение динамических информационных структур.

Объект исследования: Знакомство учащихся с основами программирования.

Достижением цели и согласно поставленной гипотезы определяются следующие задачи:

1. Изучить литературу по теме динамические информационные структуры, педагогическую и методическую по теме исследования;

2. Проанализировать виды динамических информационных структур;

3. Разработать факультатив по теме исследования;

4. Разработать программный продукт по теме исследования.

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

1.1 Списки. Очередь. Стек. Дек.

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

Список очередности (pushup list) – список, в котором последний поступающий элемент добавляется к нижней части списка.

Список с использованием указателей (linked list) – список, в котором каждый элемент содержит указатель на следующий элемент списка.

Линейный список (linear list) — это множество, состоящее из узлов , структурные свойства которого по сути ограничиваются лишь линейным (одномерным) относительным положением узлов, т. е. теми условиями, что если , то является первым узлом; если , то 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 как названия методов при составлении прейскурантов. Еще один термин "архив" применялся к декам с ограниченным выходом, а деки с ограниченным входом называли "перечнями", или "реестрами". Такое разнообразие названий интересно само по себе, Поскольку оно свидетельствует о важности этих понятий. Слова "стек" и "очередь" постепенно становятся стандартными терминами; из всех других словосочетаний, перечисленных выше, лишь "пуш-даун список" остается еще довольно распространенным, особенно в теории автоматов.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13