7

Лабораторная работа 2 Структуры данных типа "Стек"

1.Общие понятия

Стеком называется линейно-упорядоченная последовательность Е(1), Е(2), Е(n), где n>0, причем каждый элемент характеризуется одним и тем же набором полей. В общем случае "n" не является const. Это обстоятельство позволяет назвать стек полустатической структурой. В стеке реализуется принцип

LIFO (последний пришел- первый ушел), или по-другому принцип "мешка"- то, что положено в последнюю очередь, вынимается в первую. Этот принцип оказывается очень удобным при решении некоторых специальных задач, связанных, например, с использованием рекурсии или анализом арифметических выражений. Он поддерживается обращением к стеку через указатель, указывающий на верхний занятый слот (значение этого указателя изменяется в пределах, определённых при описании стека). При этом можно говорить об обычной модели стека, если все операции производятся только над верхними элементами стека, и о расширенной модели стека, в которой могут производиться операции и над элементами, лежащими в глубине стека. Нужно помнить, что стек считается одной из самых "быстродействующих структур". Поэтому при использовании расширенной модели стека число операций с верхними элементами должно быть существенно больше, чем с глубинными, так как в противном случае стек теряет свои "скоростные" качества и его применение становиться нецелесообразным.

2. Цель работы

Целью работы является изучение и отработка приемов и навыков использования стеков в организации алгоритмических структур. Машинная реализация этих структур планируется на языке Турбо Паскаль или С++.

3. Варианты заданий на выполнение работы

При выполнении заданий следует задействовать все стандартные операции работы со стеком, каждая из которых должна быть оформлена в виде отдельной процедуры или функции.

1. Используя стек, сравнить символьный запрос с набором шаблонов.

2. Используя стек, разработать механизм вычисления арифметических выражений, записанных в постфиксной форме.

3. В режиме мультистека (не менее 4-х простых стеков) организовать сравнение элементов простых стеков, находящихся на одинаковом расстоянии от вершины стека с последующим выводом одинаковых элементов на экран.

4. Используя стек, разработать процедуру изъятия некорректных скобок и интервалов в арифметических выражениях, записанных в инфиксной х форме.

5. Используя стек, преобразовать инфиксную форму в постфиксную.

6. Используя стек, создать простейшую БД, содержащую сведения о студентах.

7. Используя стек, вывести из экзаменационной ведомости список студентов, получивших одинаковые оценки.

8. Используя стек, сосчитать вероятность появления в тексте букв: а, б, в.

9. Используя стек, определить символ, наиболее часто появляющийся в случайно выбранном тексте.

10. Используя стек, разработать процедуру изъятия лишних скобок.

11. Разработать комплекс процедур, позволяющих организовать работу двух стеков, которые занимают одну область памяти.

12. Используя стек, построенный в динамической памяти, введенную последовательность символов прочитать в обратном порядке, устранив повторяющие символы.

13. Объединить два стека в один таким образом, чтобы элементы в нем следовали в алфавитном порядке.

14. Для стека, организованного в динамической памяти, построить все стандартные операции со стеками.

15. Организовать обмен данных между двумя стеками, один из которых построен на статической памяти, а другой на динамической.

16. Перевести выражение, представленное в постфиксной форме, в инфиксную.

17. Организовать с помощью стека передачу локальных параметров в подпрограмму при встроенном ассемблере.

18. Использование стека для вывода числа в 4 байтном формате на ассемблере.

19. Перевести префиксное выражение в инфиксное.

20. Используя стек, вычислить выражение в префиксной форме.

21. Перевести инфиксное выражение в префиксное.

22. Построить стек на основе элементов, расположенных в центральной вертикали таблицы.

23. Построить стек на основе элементов, расположенных в центральной горизонтали таблицы

24. Построить стек на основе элементов, расположенных в таблицы со смещением

25. Построить стек на основе элементов, расположенных в смещенной вертикали таблицы.

26. Построить стек на основе элементов, расположенных в нижней горизонтали таблицы