Практика языка C (МФТИ, 2023-2024). Семинар 4.1. Односвязные списки.

Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.

На этом занятии мы начнём знакомство с динамическими структурами данных и рассмотрим односвязные списки. С прошлым семинаром этот связан через идею корзинной сортировки, но это не единственный алгоритм, который мы рассмотрим.

Семинарист: Константин Владимиров.
Дата: 24 ноября 2023 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.

Timeline
00:00 Идея односвязного списка
08:55 Корзинная сортировка
20:45 Петли в списках
30:25 Разворот списка
36:20 Время решать задачи
39:40 Разбор problem AL
01:03:00 Разбор итеративного разворота
01:10:15 Ревью одной интересной ошибки

Errata:
* Пока пусто

[kotanvich]

Лучшие лекции по си, а позитив и увлеченность преподавателя передаются через экран и заражают!

[MichaelSolovyev-ly]

Благодаря этому семинару общественность узнала, как выглядят занятия физкультурой на физтехе

[napalm]

14:17

А диапазоны под бакеты может должны быть такими: [0, 83] [84, 167] [168, 251] [252, 335] [336, 419] [420, 503] [504, 670]

[АлександрКондратьев-ое]

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

[stanislavstanislavius]

Константин, может быть у вас уже спрашивали - могут ли домашки отсылать нестуденты?

[kruassanorkiwi]

1:11:50
Если мы в данной реализации вставим проверку на равенство после первого шага, то на первой же итерации получим true (или false, но если сначала проверим на NULL и сразу на него попадем, но все еще оба указателя будут NULL). Или я что-то не так понимаю?

[sibedir]

31:35
А почему для разворота списка, если есть требование "не использовать О(n) памяти", нам подходит рекурсия?

[SeriousMan]

1:10:35 Утверждается, что тут ошибка у студента из-за того, что заяц перепрыгнет иногда черепаху и лишний круг сделает. Я не согласен и вот почему.

Пусть t_0 -- длина маршрута до цикла, t -- длина цикла.
Следующие две интуиции обосновываются ниже:
1. Новый if добавит нам примерно t_0 + t проверок.
2. Ситуация, когда заяц перепрыгнет черепаху лишь иногда уменьшит лишние t итераций и это не то чтобы частая ситуация.
Док-во:

Рассмотрим сперва ситуацию, когда черепаха только зашла на цикл спустя t_0 и заяц сделал два шага. Пусть расстояние заяца по циклу до нее -- m.

При существующем алгоритме:
1. За каждую итерацию расстояние сокращается на 1 (= -2 + 1) и происходит проверка, что позиции совпали.
2. Таким образом m итераций.
3. Новый if тут ничего не изменит -- проверки и так есть на каждом уменьшении расстояния m на 1.

Новый if только убыстрит в ситуации, если черепаха зашла на цикл, а заяц проскочил в этот момент черепаху. Т.е. когда m = 1 или 0 сразу после захода черепахи на цикл.
1. Без доп if мы имеем примерно лишние t итераций только для данной ситуации.
2. Но с новым if мы всегда имеем лишние t_0 + t проверок и иногда в ситуации выше меньше итераций на t.

То есть даже когда эта ситуация прозошла все равно будет лишние t_0 проверок против t лишний итераций прежнего цикла. Цикл не выглядит очень сложным -- пара проверок, присваиваний. А в остальных случаях всегда будет t_0 + t лишних проверок. Оптимизация тут как-то сомнительна или требует доп мотивации со стороны уже скорости конкретных инструкций и только при странных распределениях t_0, t когда вероятность m = 1 и 0 в момент когда черепаха зашла на цикл -- весома.

[dmitriy]

Вопрос по оформлению кода. Как лучше подходить к написанию функций. Лучше возвращать флаг успешной операции или кидать аборд? Ну например написать функцию чтения из файла, и если файла нет, возвращать из функции код 1 например и не кидать аборд. А в мейне уже обрабатывать этот флаг?

[alexhitch]

Подскажите литературу хорошую литературу по структурам данных.. Можно и на английском

[Aidar]

где можно взять старта на эти семинары, я просто чайник в этом. Хочется у вас учится, понятным языком объясняете)) только только устанавливаю линукс убунту
Спасибо за семинары!