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

  1. С++
    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. Структуры: struct T { int a, b; }; T x; x.a; T y = {2, 3}; T z = T {2, 3};
    5. Указатели: int b, *a = &b;. Они же массивы: int *a = new int[n]; a[1] = 3;

  2. Неасимптотические оптимизации
    1. cmath: sqrt, sin, cos, atan, ...
    2. Вызов функции (если оптимизатор не уберёт его). Пример с рекурсией.
    3. Ввод, вывод (scanf/printf, cin/cout)
    4. Операции с памятью: new, delete. Работают не за O(1).
    5. Случайный, а не последовательный доступ к памяти. Пример с проходом по матрице (умножение матриц).
    6. Деление и взятие по модулю: a /= b; a %= b;. Пример с (a+b)%m.

  3. Быстрый операции: memcpy, strcmp

  4. Простейшие структуры данных
    1. Сумма на отрезке. Частичные суммы.
    2. Массив фиксированного размера
      1. int a[n];
      2. Интерфейс: get(i), set(i,x) − O(1)
      3. Минусы: удаление и добавление в середину за O(n), поиск за O(n)
    3. Двусвязный список
      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;
    4. Односвязный список
      1. struct node { node *next; int data; }; node *head = 0;
      2. Версия на массиве: struct node { int next, data; } a[n]; int head = -1;
      3. Пишем код добавления в начало для обеих версий: head = new Node {head, x};
− Перерыв −
  1. Расширяющийся массив (вектор)
    1. int size, an, a[size];
    2. get(i), set(i, x), del_back() − O(1)
    3. add_back() − O(1) в среднем, доказательство
    4. C++: vector<int> a; a.push_back(x), a.pop_back(x)

  2. Стек, очередь, дек
    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. Сравнение двусвязного списка и очереди.

  3. Очередь и стек с минимумом
    1. Стек с минимумом: частичные минимумы
    2. Очередь с минимумом через два стека: Q = <S, S>, push = O(1), pop = O(1) + reverse iff need

  4. Амортизированное время работы
    1. Определение через потенциальную функцию: ai = ti + Δφ (пример: вектор)
    2. Определение через монетки: есть операции, которые накапливают средства (Δφ > 0), а есть те, что тратят (Δφ < 0). (пример: вектор)