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

Содержание
Введение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. Найти в списке узел с заданным значением в некотором поле.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию