Практика языка C (МФТИ, 2023-2024). Семинар 4.2. Обходы деревьев.
Вставка
- Опубліковано 13 чер 2024
- Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.
На этом занятии мы познакомимся с деревьями и с бинарными деревьями. В основном мы будем заниматься их обходами и решать соответствующие задачи. Но также нас ждёт немного интересной теории относительно представлений деревьев.
Семинарист: Константин Владимиров.
Дата: 1 декабря 2023 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.
Предыдущий семинар: • Практика языка C (МФТИ...
Следующий семинар: • Практика языка C (МФТИ...
Слайды к занятиям: cs.mipt.ru/wp/?page_id=7775
Примеры кода: github.com/tilir/c-graduate
Задачник: olymp1.vdi.mipt.ru/
Timeline
00:00 Что такое дерево
07:00 Обходы
22:20 Итеративные обходы и стек
33:30 Поисковость
39:35 Время решать задачи
43:45 Больше про деревья и леса
55:45 Представление топологии деревьев
01:03:10 Ревью кода и завершение
Errata:
* Пока пусто
это самая сногсшибательная лекция. 1:01:01 - особое спасибо.
Как будто проснулся и не можешь заснуть)
Огромная Вам благодарность за семинар.
Спасибо за лекцию.
Осталось понять как сохранять топологию k-ичных деревьев, т.к. не всякое дерево имеет семантический смысл в бинарном представлении и думать о нем именно как о k-ичном значительно удобнее.
Добрый день/ночь. Поскажите пожалуйста, есть ли принципиальная разница для условий, когда первым словом идёт проверка на NULL или nullptr?
if (NULL == top) или if (nullptr == ptr) по идее писать if (!top) проще или тут есть подводные камни?
Это язык C здесь нет nullptr ))
Никаких подводных камней. Записи:
if (top == NULL) do();
if (top == 0) do();
if (!top) do();
Либо трижды сработают либо трижды не сработают в зависимости от значения top.
Добрый день! Вопрос Константину, как понял из ваших лекций Вы любите интересные примеры. Вот один из таких, правда не по этой теме а в продолжение одной из предыдущих, где упоминалось размещение данных в секциях памяти. Столкнулся с неожиданным поведением компилятора IAR при размещении не инициализируемых переменных, хотелось бы услышать Ваш комментарий по приведенному ниже случаю: это баг компилятора или же есть объяснение в стандарте.
static int arr[2][500];
int val = 3;
#if CASE==1 // компилятор IAR положит arr в секцию .data (GCC положит в .bss)
int main(void){
arr[0][0] = arr[1][0] = val;
return 0;
}
#endif
#if CASE==2 // компилятор IAR положит arr в секцию .bss
int main(void){
arr[0][0] = val;
return 0;
}
#endif
Стандарт нигде не регламентирует раскладку по секциям. Это просто особенности реализации.
Как оказалось лечится определенными флагами компилятора.
P.S. Совет: Если собираете проект на новом для вас компиляторе всегда полезно посмотреть какие его родная система сборки устанавливает флаги по умолчанию из GUI в режиме автобилд. Не всегда всё сразу очевидно, а подсмотрев можно немного времени сэкономить.
Почему у обходов такие имена 'inorder', 'postorder', 'preorder' ? И как это связать с методами обхода LVR, LRV, VLR чтобы запомнить кто есть кто ?
V это visit, L это left, R это right. Если visit в начале то это преордер и т.д.
Спасибо. Очень интересно. Одного не понял - зачем в описании топологии дерева в 57:27 ноль в конце нужен? Выглядит лишним.
Почему просто единицей последовательность не заканчивать, а остальные листья считать заведомо отсутствующими, если всё равно финальный в уме держим уже, что мешает ещё один додумать ?
Рассматривайте единицы как открывающие скобки а нули как закрывающие. Тогда последние нули очевидно полезны для баланса. Но в общем да, для компактности хранения их можно удалить, это может даже быть неплохой оптимизацией при работе с миллионами таких представлений.
Направленный граф без циклов?
ненаправленный
А как бы выглядел брат-ребенок в многомерном случае?
А что такое многомерный случай?
@@tilir AST абстрактное синтаксическое дерево - это, условно, бинарная сбалансированная строка(топология дерева). По этой логике, это просто целое число. Не всякое число это программа, но всякая программа - это целое число. Теперь допустим у нас есть параллельное исполнение программ операционной системой. По идее, это лес, который дорисовкой вершины превращается в дерево. Но как будет выглядеть в этом срезе планировщик задач в операционной системе? Как решается этот вопрос частичного порядка и синхронизации, в гипотетическом планировщике оперирующим с числами-топологиями АСТ ?