Дипломная работа по предмету "Программирование, программное обеспечение, СУБД"

Узнать цену дипломной по вашей теме


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

Содержание Введение 3 Глава 1. Динамические типы данных 6 1. 1 Списки. Очередь. Стек. Дек. 6 1. 2 Динамические информационные структуры 22
Глава 2. Разработка факультативного курса “Динамические типы данных” 29 2. 1 Методические рекомендации по введению факультативного курса в школе 29 2. 2 Разработка программного средства по теме “Динамические типы данных” 38 Заключение 42 Литература 44 Приложение 1. (Листинг программы) 45 Введение
Сегодня человек живет в мире, где информация имеет огромное значение. Жизненно важно научиться правильно с ней работать и использовать различные инструменты для этой работы. Одним из таких инструментов является компьютер, который стал универсальным помощником человеку в различных сферах деятельности. В вычислительной машине программы обычно оперируют с таблицами информации. В большинстве случаев это не просто аморфные массы числовых величин: в таблицах присутствуют важные структурные отношения между элементами данных. Чтобы правильно использовать машину, важно добиться хорошего понимания структурных отношений, существующих между данными, способов представления таковых в машине и методов работы с ними. Изучить наиболее важные факты, касающиеся информационных структур: их статические и динамические свойства; средства распределения памяти и представления данных; эффективные алгоритмы для создания, изменения, разрушения структурной информации и доступа к ней. В простейшей форме таблица может быть линейным списком элементов. Тогда присущие ей структурные свойства содержат в себе ответы на такие вопросы, как: "Какой элемент является первым в списке? какой — последним? какой элемент предшествует данному или следует за данным? " Можно много говорить о структуре даже в этом совершенно очевидном случае. В более сложных ситуациях таблица может быть двумерным массивом (т. е. матрицей, иногда называемой сеткой, имеющей структуру строк и столбцов), либо может быть n-мерным массивом при весьма больших значениях n, либо она может иметь структуру дерева, представляющего отношения иерархии или ветвления, либо это может быть сложная многосвязанная структура с огромным множеством взаимных соединений, такая, например, которую можно найти в человеческом мозгу. Системы обработки списков полезны в очень многих случаях, однако при их использовании программист нередко сталкивается с излишними ограничениями. Теперь целесообразно определить несколько терминов и понятий, которыми мы будем часто пользоваться в дальнейшем. Информация в таблице представлена множеством узлов (некоторые авторы называют их "записями", "бусинами", "объектами"); мы иногда вместо "узел" будем говорить "элемент". Каждый узел состоит из одного или нескольких последовательных слов в памяти машины, разделенных на именуемые части, называемые полями. В простейшем случае узел — это просто одно слово памяти, он имеет только одно поле, включающее все слово. В связи с этим цель нашей работы: Знакомство с теоретическим положением, касающиеся информационных структур и разработка программного средства “Динамические структуры данных”. Этой целью определяется следующая гипотеза: если при изучении данной темы будет использоваться компьютер, то усвоение темы будет более успешным, так как усиливает мотивацию, и влияет на конечный результат. Предмет исследования: Изучение динамических информационных структур. Объект исследования: Знакомство учащихся с основами программирования. Достижением цели и согласно поставленной гипотезы определяются следующие задачи: Изучить литературу по теме динамические информационные структуры, педагогическую и методическую по теме исследования; Проанализировать виды динамических информационных структур; Разработать факультатив по теме исследования; Разработать программный продукт по теме исследования. Глава 1. Динамические типы данных 1. 1 Списки. Очередь. Стек. Дек.
Список (list) – набор элементов, расположенных в определенном порядке. Таким набором быть может ряд знаков в слове, слов в предложений в книге. Этот термин может также относиться к набору элементов на диске. Использование при обработке информации списков в качестве типов данных привело к появлению в языках программирования средств обработки списков. Список очередности (pushup list) – список, в котором последний поступающий элемент добавляется к нижней части списка. Список с использованием указателей (linked list) – список, в котором каждый элемент содержит указатель на следующий элемент списка. Линейный список (linear list) — это множество, состоящее из узлов , структурные свойства которого по сути ограничиваются лишь линейным (одномерным) относительным положением узлов, т. е. теми условиями, что если , то является первым узлом; если , то k-му узлу предшествует и за ним следует ; является последним узлом. Операции, которые мы имеем право выполнять с линейными списками, включают, например, следующие: Получить доступ к k-му узлу списка, чтобы проанализировать и/или изменить содержимое его полей. Включить новый узел непосредственно перед k-ым узлом. Исключить k-й узел. Объединить два (или более) линейных списка в один список. Разбить линейный список на два (или более) списка. Сделать копию линейного списка. Определить количество узлов в списке.
Выполнить сортировку узлов списка в возрастающем порядке по некоторым полям в узлах. Найти в списке узел с заданным значением в некотором поле.
Специальные случаи 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. Изображен дек в виде железнодорожного разъезда.


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

Доработать Узнать цену работы по вашей теме
Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем дипломную работу самостоятельно:
! Как писать дипломную работу Инструкция и советы по написанию качественной дипломной работы.
! Структура дипломной работы Сколько глав должно быть в работе, что должен содержать каждый из разделов.
! Оформление дипломных работ Требования к оформлению дипломных работ по ГОСТ. Основные методические указания.
! Источники для написания Что можно использовать в качестве источника для дипломной работы, а от чего лучше отказаться.
! Скачивание бесплатных работ Подводные камни и проблемы возникающие при сдаче бесплатно скачанной и не переработанной работы.
! Особенности дипломных проектов Чем отличается дипломный проект от дипломной работы. Описание особенностей.

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

Виды дипломных работ:
выпускная работа бакалавра Требование к выпускной работе бакалавра. Как правило сдается на 4 курсе института.
магистерская диссертация Требования к магистерским диссертациям. Как правило сдается на 5,6 курсе обучения.

Другие популярные дипломные работы:

Сейчас смотрят :

Дипломная работа Повышение эффективности производственно-хозяйственной деятельности на предприятии (на примере ОАО "Смолевичский молочный завод")
Дипломная работа Анализ кредитоспособности заемщика
Дипломная работа Сделки с недвижимостью
Дипломная работа Судебное разбирательство
Дипломная работа Амнистия и помилование
Дипломная работа Кредитование коммерческими банками юридических лиц (на материалах ОАО "Белпромстройбанк")
Дипломная работа Совершенствование управления пассивами банка на примере ОАО Банк Москвы
Дипломная работа Совершенствование финансового планирования на предприятии (на примере ООО "Техноавиа")
Дипломная работа Повышение рентабельности предприятия (на примере Ростовского областного консультативно-диагностического центра)
Дипломная работа Формы и виды систем оплаты труда
Дипломная работа Институт реабилитации в уголовном судопроизводстве
Дипломная работа Проблема сбытовой деятельности организации
Дипломная работа Синхронный перевод
Дипломная работа Пути стимулирования познавательной деятельности студентов на учебном занятии
Дипломная работа Коллективный договор