Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Стек. Функциональная спецификацияСодержание книги
Поиск на нашем сайте
Стек — это структура с единственной читающей-записывающей головкой, последовательным доступом и неразрушающей записью. Чтение из стека, как и у очереди, разрушающее (удаление!). Более строго, стеком называется множество некоторого переменного (возможно, нулевого) числа данных, на котором выполняются следующие операции: Пополнение стека новыми данными; Проверка, определяющая пуст ли стек; Просмотр верхнего(самого нового) элемента, если он существует; Уничтожение последнего добавленного, но еще не уничтоженного элемента, если он есть. 1) Тип sT или стек объектов типа т, характеризуется операциями: 2) Последовательность действий: 0 -> ST ST -> {true, false} ST -> N ST x T -> ST ST->ST ST -> ST ST ->0 Заносящая во вновь созданный пустой стек сначала элемент t1, а затем эл. t2, а затем извлекающая из нее два элемента инвертирует их порядок. Стек. Логическое описание. Самый свежий элемент стека, т. е. последний введенный и еще не уничтоженный играет особую роль; именно его можно рассмотреть или уничтожить. Этот элемент называется верхушкой стека. Оставшуюся часть можно назвать телом стека и оно само является, но существу, стеком; если снять со стека верхушку, то тело превращается в сток. Таким образом, стек, как и очередь, является рекурсивной структурой данных и может быть описан рекурсивно как конкатенация элемента типа Т и некоторого стека s типа SТ.Для обеспечения эффективной вычислимости необходим терминатор, ограничивающий глубину рекурсии описания, роль которого, как в файлах и очередях, играет пустой стек: type СТЕК-Т = (ПУСТО | НЕПУСТОЙСТЕК) type НЕПУСТОЙСТЕК = (верхушка: Т; тело: СТЕК-Т) const int POOL_SIZE-100 Заметим, что рекурсивность описания может быть не только по глубине стека, но и по сложности типа его компонент Т: этот тип может быть произвольным, в том числе и рекурсивным, и даже стеком... 13 Стек. Физическое представление (массив). Идеальной структурой представления для стека должен быть файл. Действительно, добавление элементов происходит только в конец файла, однако при удалении последнего элемента придется два раза переписывать весь файл, причем с подсчетом элементов. Это главный недостаток файла – для удаления компоненты требуется слишком много действий. С другой стороны время удаления элементов из файла не зависит ни от положения этого элемента в файле, ни от количества удаляемых элементов – это плюс! Реализация стека с помощью массива позволяет уравнять время выполнения действий по добавлению и удалению элемента. Нужно всего лишь хранить в отдельной переменной длину последовательности и увеличивать ее или уменьшать соответственно при добавлении и удалении. Единственный недостаток такого представления – недостаток самого массива – ограниченный размер, приводящий к переполнению стека Использование динамических структур полностью решает эту проблему. В этом случае при добавлении и удалении элемента модифицируется только ссылка на начало цепочки динамических объектов, что снижает до минимума количество используемых для действия операторов. При этом размер стека почти неограничен. Начало последовательности называется дном стека, конец последовательности, в который производится добавление элементов и их исключение - вершиной стека. Переменная, которая указывает на последний элемент последовательности в вершине стека - указатель стека. Операция добавления нового элемента (запись в стек) имеет общепринятое название Push (погрузить), операция исключения - Pop (звук выстрела). Операции Push и Pop являются безадресными в том смысле, что для их выполнения никакой дополнительной информации о месте размещения элементов не требуется (для этого достаточно указателя стека)
15 Линейный список. Функциональная спецификация. Линейный список — это представление в ЭВМ конечного упорядоченного динамического множества элементов типа Т. Точнее, это не множество, а мультимножество, т. к. в последовательности могут находиться элементы с одинаковыми значениями. Элементы этого множества линейно упорядочены, но порядок определяется не номерами (индексами), как в массиве, а относительным расположением элементов. Отношений порядка па этом множестве может быть не одно, а два, и тогда мы имеем дело с двусвязными (двусторонними или симметричными) списками. Для закольцевания списка необходимо доопределить в качестве следующего за. последним первый элемент списка, а в качестве предыдущего первому элементу — последний (голова указывает на хвост, а хвост на голову). Таким образом отношения порядка (предыдущий и /или следующий) становятся определенными для всех смежных (с точностью до закольцевания) пар элементов списка. Список обозначается простым перечислением элементов в заданном порядке в круглых скобках через запятую. Например, список l из пяти элементов типа T выглядит так: l = (t1, t2, t3, t4, t5) Полная функциональная спецификация двусвязного линейного списка LT объектов типа T достаточно длинна: СОЗДАТЬ: 0 -> LT ПУСТО: LT -> boolean ДЛИНА: LT ->N ПЕРВЫЙ: LT -> T ПОСЛЕДНИЙ: LT -> T СЛЕДУЮЩИЙ: LT x T -> T ПРЕДЫДУЩИЙ: LT x T -> T ВСТАВКА: LT x T x T -> LT УДАЛЕНИЕ: LT x T -> LT УНИЧТОЖИТЬ: LT -> 0.
Свойства: ПУСТО (СОЗДАТЬ) - true ПУСТО (ВСТАВКА (l, t, t) — false ПРЕДЫДУЩИЙ(СЛЕДУЮЩИЙ(t)) = t СЛЕДУЮЩИЙ(11РЕДЫДУЩИЙ(t)) = t l:— СОЗДАТЬ l:— ВСТАВКА (l, t2, t2) l: ВСТАВКА(l, t2, t1) ПЕРВЫЙ (l) = t1 ПОСЛЕДНИЙ (l) = t2 В левой части спецификации операции ВСТАВКА находится декартово произведение трех множеств: всевозможных списков, в которые должна быть проведена вставка, всех элементовПЕРЕДкоторыми необходимо ее произвести и различных вставляемых элементов. 16 Линейный список. Логическое описание. В отличие от очередей и стеков списковые структуры, хотя и не входят в стандартные языки программирования, но хорошо реализованы в альтернативных достаточно распространенных языках Лисп и Пролог. Более того, в языке Лисп это основная структура. Рассмотрим сначала как списки реализованы в Прологе. По определению, пустой список является списком, он обозначается символом [ ]. Функтор «.» (точка) образует новый список путем добавления нового элемента в начало исходного списка. Так список (t1, t2, t3, t4, t5) может быть записан на Прологе как: .(t1,.(t2,.(t3,.(t4,.(t5, []))))) Логическое описание списков на Прологе базируется на встроенном предикате отделения головы списка «|» и реализованных на самом Прологе предикатах (программных единицах этого языка), более или менее соответствующих вышеприведенной функциональной спецификации: проверка членства элемента или подсписка в заданном списке, вычисление длины, конкатенация, генерация перестановок элементов списка. Остальное может быть легко дописано на Прологе. Примеры: [Tl, Т2, T3 | Tail] * Отделение от списка трех первых элементов. В результате переменные Tl, Т2 и ТЗ получают значения, первых трех элементов списка, а 'Tail становится, остатком списка */ % Определение длин ы производится, рекурсивно length([], О). length([_| Tail ], N):- length(Tail, N1), N is N1 + 1.
|
||||
Последнее изменение этой страницы: 2016-08-14; просмотров: 635; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.140.195.142 (0.009 с.) |