17

Министерство образования и науки рф

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Тульский государственный университет

Кафедра прикладной математики и информатики

Базы данных и экспертные системы

Методические указания по выполнению лабораторных работ

для студентов направления 010500 «Прикладная математика и информатика»

специальности 010501 «Прикладная математика и информатика» очной формы обучения

Тула 2011

Лабораторная работа № 1

ИНФОРМАЦИОННЫЕ СТРУКТУРЫ

 Цель работы

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

 Задание по вариантам

1. Разработать программу получения обратной польской записи арифметических выражений, составленных из однобуквенных идентификаторов, открывающей и закрывающей скобок и операций: +, –, /, *, ^ (возведение в степень).

Алгоритм перевода, предложенный Э. Дейкстрой, основывается на использовании стека с приоритетами. Все символы операций и скобки имеют определенный приоритет. Для построения польской записи продвигаются вдоль выражения слева направо. Операнды переписываются в выходную строку, а операции запоминаются в стек. Если приоритет помещаемой в стек операции меньше приоритета операции, находящейся в вершине стека, то происходит выталкивание операций из стека по одной до тех пор, пока в вершине не окажется операция с меньшим приоритетом или стек не окажется пустым. Закрывающая скобка вызывает выталкивание всех символов до открывающей скобки (скобки в выходное выражение не переписываются). Операции имеют следующие приоритеты:

Операция	(	+, –	*, /	^
Приоритет	0	1	2	3

2. Разработать программу включения и исключения элементов в очередь с последовательным распределением. Предусмотреть обработку ситуаций «ПЕРЕПОЛНЕНИЕ» и «НЕХВАТКА».

3. Разработать программу включения и исключения элементов в очередь со связным распределением. Предусмотреть обработку ситуаций «ПЕРЕПОЛНЕНИЕ» и «НЕХВАТКА».

4. Разработать программу обращения связного списка с произвольным числом узлов (после выполнения обращения элементы списка должны располагаться в обратном порядке).

5. Разработать программу обращения циклического списка с произвольным числом узлов (после выполнения обращения элементы списка должны располагаться в обратном порядке).

6. Разработать программу сложения двух многочленов Р(х,у) и Q(х,y), представленных в виде циклических списков. Узел описка имеет вид

M

a

b

link

и соответствует одночлену Мx^ay^b.

7. Имеется стек, элементы которого также являются стеками. Разработать программу включения и исключения стеков и отдельных элементов из верхнего стека.

8. Разработать программу получения циклического списка по многочлену Р(x,у) (cм. вариант № 6).

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

10. Разработать программу построения бинарного дерева по обратное польской записи (см. вариант № 1).

11. Прямой порядок прохождения дерева состоит в следующем: 1) попасть в корень; 2) пройти левое поддерево; 3) пройти правое поддерево. Разработать программу, дающую узел дерева, следующий за данным в прямом порядке.

12. Обратный порядок прохождения дерева состоит в следующем: 1) пройти левое поддерево; 2) попасть в корень; 3) пройти правое поддерево. Разработать программу, дающую узел дереве, следующий за данным в обратном порядке.

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

14. Разработать программу получения обратной польской записи по бинарному дереву.

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

16. Разработать программу удаления узла из бинарного дерева.

17. Имеется бинарное дерево, каждый узел которого представляет собой связный список некоторых элементов. Разработать программу поиска элемента в таком дереве.

18. Разработать программу умножения выражений вида axⁿ + b, представленных в виде бинарного дерева.

19. Разработать программу дифференцирования полинома Р(х) = a₀xⁿ + a₁x^n-1 + … + a_n-1x + а_n, представленного в виде бинарного дерева.

20. Разработать программу интегрирования полинома Р(х) = a₀xⁿ + a₁x^n-1 + … + a_n-1x + а_n, представленного в виде бинарного дерева.

21. Разработать программу заполнения таблицы идентификаторов языка Паскаль. В качестве хеш-функция использовать функцию h(K) = K mod M, где К — числовая характеристика идентификатора, М — размер таблицы в строках. Для разрешения коллизий использовать схему линейного опробования, согласно которой, если строчка h(K) занята другим идентификатором, то поиск свободной строчки производится в отроках h(K) – 1, h(K) – 2, …, 0, M – 1, M – 2, …, h(K) + 1, (h(K) < M). Обратите внимание на выбор значения М.

22. Выполнить задание варианта № 21 для идентификаторов языка Си.

23. Разработать программу заполнения таблицы идентификаторов языка Ассемблера. В качестве хеш-функции использовать функцию из варианта № 21. Для разрешения коллизий использовать метод цепочек.

24. Выполнить задание варианта № 23, взяв в качестве хеш-функции функцию, сопоставляющую идентификатору номер его первой буквы по алфавиту.

25. Пусть Т₁ и Т₂ — два бинарных дерева. Т₁ = Т₂, если деревья имеют одинаковую структуру и содержимое соответствующих узлов равно. Т₁ < Т₂, если Т₁ содержится в Т₂ качестве поддерева, Т₁ > Т₂, если Т₂ является поддеревом Т₁. Разработать программу, сравнивающую два дерева Т₁ и Т₂.