Линейные списки. Стек. Дек. Очередь
Категория реферата: Рефераты по информатике, программированию
Теги реферата: реферати, сочинение 5 класс
Добавил(а) на сайт: Губанов.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Глава 1. Динамические типы данных
1.1 Списки. Очередь. Стек. Дек.
Список (list) – набор элементов, расположенных в определенном порядке.
Таким набором быть может ряд знаков в слове, слов в предложений в книге.
Этот термин может также относиться к набору элементов на диске.
Использование при обработке информации списков в качестве типов данных
привело к появлению в языках программирования средств обработки списков.
Список очередности (pushup list) – список, в котором последний поступающий элемент добавляется к нижней части списка.
Список с использованием указателей (linked list) – список, в котором каждый элемент содержит указатель на следующий элемент списка.
Линейный список (linear list) — это множество, состоящее из [pic]
узлов [pic], структурные свойства которого по сути ограничиваются лишь
линейным (одномерным) относительным положением узлов, т. е. теми условиями, что если [pic], то [pic] является первым узлом; если [pic], то k-му узлу
[pic] предшествует [pic] и за ним следует [pic]; [pic] является последним
узлом.
Операции, которые мы имеем право выполнять с линейными списками, включают, например, следующие:
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) – стек, организованный таким образом, что последний вводимый в область памяти элемент размещается на вершине списка.
Рекомендуем скачать другие рефераты по теме: гигиена реферат, курсовик.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата