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

  1. С++
    1. Выделение, освобождение памяти: int *a = new int[n];, delete[] a;
    2. Неинициализированные переменные: -Wall, -Wextra, -Wshadow
    3. RangeCheckError: int a[10], x; a[10]; // иногда undefined behavior
    4. RangeCheckError fix: vector<int> a; a.at(10); #define _GLIBCXX_DEBUG
    5. Структуры: struct T { int a, b; }; T x; x.a;
    6. Указатели: int *a = &b;
  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. Простейшие структуры данных
    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.
    4. Односвязный список
      1. struct node { node *next; int data; }; node *head = 0;
      2. Версия на массиве: struct node { int data, next; } a[n]; int head = -1;
      3. Пишем код добавления в начало.
− Перерыв −
  1. Расширяющийся массив (вектор)
    1. int size, an, a[size];
    2. get(i), set(i, x), pop_back() − O(1)
    3. push_back() − O(1) в среднем, доказательство
  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. Сравнение двусвязного списка и очереди.
  3. Очередь и стек с минимумом
    1. Стек с минимумом: частичные минимумы
    2. Очередь с минимумом через два стека: Q = <S, S>, push = O(1), pop = O(1) + reverse iff need
  4. Время работы: определяем амортизированное время. Пример: вектор.