АиСД (практика)

1.

АиСД (практика)
Бондаренко Богдан
Евгеньевич

2.

3.

Общие требования
• Все ЛР связаны и заканчиваются на курсовой
• Студенты не должны использовать стандартные
библиотеки
• Каждая ЛР должна быть самописной и использовать
только результаты предыдущих ЛР
• Все ЛР должны работать корректно (используйте
несколько вариантов исходных данных)
• Отчёт: что делали, как работает, примеры
• По деталям всегда спрашивайте (про GitHub позже)

4.

Лабораторная работа №1
• Списочные структуры.
• Реализовать следующие структуры: односвязный список,
динамический массив и стек. Стек можно реализовать как
на базе списка, так и отдельно.
• Алгоритм сортировочной станции.
• Использовать стек для реализации алгоритма
сортировочной станции. Разрешённые символы в исходном
выражении: +, -, *, /, ^, sin, cos, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Для упрощения разбиения входной строки на токены
разрешается отделять каждый символ пробелом.

5.

Динамический массив
Динамическим называется
массив, размер которого может
изменяться во время исполнения
программы
Доступ
O(1)
Поиск
O(n)
Вставка
O(n)
Удаление O(n)

6.

Односвязный список
Доступ
Поиск
Вставка
Удаление
O(n)
O(n)
O(1)
O(1)

7.

Стек

8.

Алгоритм сортировочной станции

9.

Дедлайны и материалы
• ЛР 1 - 8 октября
• ЛР 2 - 29 октября
• ЛР 3 - 19 ноября
• Курсовая - приблизительно за две недели до зачетной
недели
• https://markoutte.me/students/#algostr
• https://www.bigocheatsheet.com/
• https://gist.github.com/PurpleBooth/109311bb0361f32d87a2