Структуры данных (10 сентября 2024)

1. Забытое с прошлой лекции
   1. Формулировки: log^an = O(n^b), n^b = O(cⁿ)
   2. Примеры
      1. 5 циклов for, n⁵ / 5! (константа таки важна)
      2. Длинные числа, числа Фибоначчи на самом деле считаются за квадрат (договорённость, какие операции сколько работают)
      3. Для всех чисел от 1 до n сгенерить список делителей (nlogn, 2 цикла for, оцениваем сумму гармонического ряда).
   
   
2. С++
   1. Неинициализированные переменные, борьба с Warning-ами: -Wall, -Wextra, -Wshadow
   2. RangeCheckError: int a[10], x; a[10]; // undefined behavior
   3. RangeCheckError fix: vector<int> a; a.at(10); #define _GLIBCXX_DEBUG
   4. C++. Структуры: struct T { int a, b; }; T x; x.a; T y = {2, 3}; T z = T {2, 3};
   5. C++. Ссылки, передача параметров в функции (по значения, по ссылке).
   6. Указатели (рассказать уже в разделе про списки!): int b, *a = &b;. Они же массивы: int *a = new int[n]; a[1] = 3;
   
   
3. Неасимптотические оптимизации
   1. cmath: sqrt, sin, cos, atan, ...
   2. Вызов функции (если оптимизатор не уберёт его). Пример с рекурсией.
   3. Ввод, вывод (scanf/printf, cin/cout)
   4. Операции с памятью: new, delete. Работают не за O(1). Пример: vector<vector<int>>.
   5. Случайный, а не последовательный доступ к памяти. Пример с проходом по матрице (умножение матриц).
   6. Деление и взятие по модулю: a /= b; a %= b;. Пример с (a+b)%m.
   
   
4. Быстрые операции: memcpy, strcmp
   
   
5. Простейшие структуры данных (и интерфейсы)
   1. Немного про мышление. Важно не ломать себе мозг об мелочи, которых не понимаете: две плохие крайности вообще игнорировать, пытаться понять каждую запятую.
   2. Сумма на отрезке. Частичные суммы.
   3. Массив фиксированного размера
      1. int a[n];
      2. Интерфейс: get(i), set(i,x) − O(1)
      3. Минусы: удаление и добавление в середину за O(n), поиск за O(n)
   
   
   1. Двусвязный список
      1. struct node { node *l, *r; int data; };
      2. struct list { int length; node *head, *tail; }; // пустой список: head = tail = 0
      3. Интерфейс: add_front, add_back, del_front, del_back, add_after, del_node. Всё за O(1).
      4. Добавим ссылки внутрь: node* link[]; link[i] − node добавленный i-й операцией, тогда появляется del(i) за O(1)
      5. Поиск за O(n), обращение к i-му элементу за O(min(i, n-i))
      6. Пишем код поиска x: Node *p = head; while (p && p->x != x) p = p->next;

1. Односвязный список
   1. struct node { node *next; int data; }; node *head = 0;
      1. Версия на массиве: struct node { int next, data; } a[n]; int head = -1;
      2. Пишем код добавления в начало для обеих версий: head = new Node {head, x};
   
   
2. Расширяющийся массив (вектор)
   1. int size, an, a[size];
   2. get(i), set(i, x), del_back (pop_back) − O(1)
   3. add_back (push_back) − O(1) в среднем, доказательство
   4. C++: vector<int> a; a.push_back(x), a.pop_back(x)
   
   
3. Стек, очередь, дек
   1. Стек : add_back = push, del_back = pop за O(1), stack<int>
   2. Очередь : add_front = push, del_back = pop за O(1), queue<int>
   3. Дек : add_front, add_back, del_front, del_back за O(1), deque<int>
   4. Реализация на двусвязном списке
   5. Реализация стека, очереди, дека на динамическом массиве
   6. Реализация стека, очереди, дека на циклическом массиве
   7. Сравнение реализаций на двусвязном списке и на массиве.
   
   
4. Очередь и стек с минимумом
   1. Стек с минимумом: частичные минимумы
   2. Очередь с минимумом через два стека: Q = <S, S>, push = O(1), pop = O(1) + reverse iff need