Лабораторная работа № 10 Работа с указателями. Динамическое выделение памяти Задание 1.
Программа по созданию двухсвязного списка студентов содержащего следующую информацию о них:
Фамилия;
Стипендия;
Группа;
Номер зачетной книжки;
Разработать следующие функции:
Функция создания списка;
Функция вставки узла после текущего;
Функция удаления текущего узла (учесть, что текущий узел может совпадать с головой списка, с хвостом списка, быть единственным элементом в списке);
Функция обхода и вывода списка на экран;
Функция добавления узла в голову списка, в хвост, перед текущим узлом;
Функция поиска данных в списке по фамилии, стипендии, группе, номеру зачетной книжки (учесть возможность поиска по стипендии с условиями >, <, =).
Организовать текстовое меню, позволяющее пользователю осуществлять любые из указанных выше действий.
Задание 2.
Используя записи и указатели, а также функции динамического распределения памяти, реализовать программу для алгоритма Дейкстра. Обязательно учесть ошибки ввода.
Алгоритм Дейкстра – алгоритм перевода выражения в обратную польскую запись. Обратная польская запись представляет собой промежуточную форму выражения, которая используется в компиляторах и интерпретаторах для вычисления значения выражения. В обратной польской записи отсутствуют скобки, а операции всегда следуют за операндами, а не между ними.
Алгоритм Дейкстра
В стек (стек – это структура данных, хранящая совокупность однотипных элементов, которые поступают в стек и выходят из него по правилу «последний вошел - первый вышел») будут помещаться только символы операций.
Символы операндов из входной строки поступают сразу в выходную строку.
Символы операций сначала поступают в стек и при определенных условиях выталкиваются в выходную строку.
Открывающаяся скобка всегда попадает в стек.
Закрывающаяся скобка ни в стек, ни в выходную строку не попадает.
Когда встречается в выходной строке закрывающаяся скобка, из стека выталкиваются все символы до первой встречной открывающейся скобки включительно. Причем знаки операций выталкиваются в выходную строку, а открывающаяся скобка пропадает.
Необходимо использовать приоритеты операций:
( 0
+, - 1
*, / 2
Чем больше значение приоритета, тем сильнее операция связывает операнды.
Если во входной строке текущий символ – знак операции, то сравниваются приоритеты операций из строки и верхушки стека.
Если приоритет операции из входной строки больше приоритета операции из верхушки стека, то операция из входной строки стека перемещается в стек. В противном случае из стека выталкиваются все операции с приоритетами большими либо равными приоритетам операций из входной строки. После чего операция из входной строки помещается в стек.
При встрече конца входной строки содержимое стека выталкивается в выходную строку.
Пример: Входная строка: (a+b*c)*(a-b)/(d-(a+b*d))
Стек:
|
( |
+ |
* |
* |
( |
- |
* |
/ |
( |
- |
( |
+ |
* |
- |
/ |
|
|
( |
+ |
|
* |
( |
|
|
/ |
( |
- |
( |
+ |
( |
|
|
|
|
( |
|
|
* |
|
|
|
/ |
( |
- |
( |
/ |
|
|
|
|
|
|
|
|
|
|
|
|
/ |
( |
- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
/ |
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
/ |
|
|
Выходная строка: abc*+ab-*dabd*+-/
Рекомендации.
Стек можно рассматривать как случай списка. Для стека обязательно наличие указателя на вершину.
Если стек пуст, то указатель на вершину пустой (NIL).
Для данного примера данные в структуре списка это символы и числа (приоритеты).
Для работы со стеком необходимы как минимум две процедуры: push(втолкнуть) и pop(вытолкнуть). Для процедуры push необходимы два параметра (символ и приоритет); для процедуры pop в общем случае параметры не нужны, но в нашем примере необходим один параметр типа bool (true – выталкивать в выходную строку; false –выталкивать, но не в выходную строку).
Желательно написать функцию, которая бы по входному параметру-символу выдавала его приоритет.