Изучение принципов работы стека для организации вычислений на примере теоретико-множественных операций над множествами. Применение стека для организации хранения данных и для реализации алгоритмических структур. Алгоритм вычисления для стековой машины.
Наиболее часто в программах используются массивы, структуры и их сочетания, например, массивы структур, полями которых являются массивы и структуры. Цель описания типов данных, состоит в том, чтобы зафиксировать на время выполнения программы размер значений, которые присваиваются этим переменным и, соответственно, фиксировать размер выделяемой области памяти для них. Память под данные выделяется либо на этапе компиляции , либо во время выполнения программы с помощью операций выделения и очистки памяти .В обоих случаях выделяется непрерывный участок памяти. Такой способ распределения памяти называется динамическим, а соответствующий способ организации данных называется динамическими структурами данных, поскольку их размер изменяется во время выполнения программы. Из динамических структур в программах чаще всего используются линейные списки, стеки, деки, очереди и бинарные деревья.Стек - частный случай линейного односвязного списка, для которого разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной стека. Наиболее простой из них является стек, представляющий собой последовательность объектов данных, связанных между собой с помощью указателей. Особенность работы со стеком заключается в том, что новый объект всегда добавляется в начало списка. Запись возможна только в верхнюю ячейку стека, при этом вся хранящаяся в стеке информация предварительно проталкивается на одну позицию вниз. Подобные фрагменты программисты используют настолько часто, что, начиная с процессора Intel 80286, к системе команд записи в стек была добавлена инструкция PUSHA (от push all), сохраняющая в стеке сразу все регистры процессора.Если на вход подан операнд, он помещается на вершину стека. Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлеченных из стека, взятых в порядке добавления. После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека. Обратная польская запись совершенно унифицирована - она принципиально одинаково записывает унарные, бинарные, тернарные и любые другие операции, а также обращения к функциям, что позволяет не усложнять конструкцию вычислительных устройств при расширении набора поддерживаемых операций. Если предположить, что польская запись поступает в стек поэлементно и каждое поступившее число просто заталкивается в стек, а каждая операция снимает со стека два числа, выполняет с ними свое действие и кладет в стек результат, то в конце стек будет содержать только искомый результат.Развитие вычислительной техники и программирования сопровождалось эволюцией представлений о роли данных, взглядов на их организацию. Информация, подлежащая обработке, в некотором смысле представляет абстракцию некоторого фрагмента реального мира. Какие-то данные алгоритм (программа) может использовать как промежуточные. Естественно, что представление и организация данных имеет при разработке алгоритма первостепенное значение. С развитием вычислительной техники и программирования средства и возможности представления данных получили большое развитие и теперь позволяют использовать как простейшие неструктурированные данные, так и данные более сложных типов, которые обладают некоторой организацией.
План
Содержание
Введение
ГЛАВА 1. Принципы работы стека
ГЛАВА 2. Использование стека для организации работы с множествами
Заключение
Список литературы
Приложение
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы