Элементарные структуры данных (2 октября 2013)

1. Какие есть структуры
1. Stack, Queue, Dequeue
2. Список, двусвязный список
3. BST, хеш-таблица, куча
4. set, map
2. Реализации через массив
1. Стек: все просто [код]
2. Пример: скобочные последовательности из 5 типов скобок [код]
3. Очередь, дек: все просто, получили бонусы относительно стандартной реализации --- random access, цикличность [код]
4. Если размер заранее не известен --- пишем через список (и стек, и очередь, и дек)
5. Реализация списка, стека через список [код] [код]
6. Удаление за O(1) из двусвязного списка (обратные ссылки)
3. Тестирование скорости работы
1. Очередь на C++ : queue<int> (просто медленная) [код]
2. Очередь на Java 1.6 : LinkedList<Integer> (очень медленная, да еще кушает много памяти) [код]
3. Реализация на массиве. Заметно быстрее. [cpp] [java]
4. Хеш-таблица [код]
1. Реализавали открытую адресацию
2. Реализавали удаление для открытой адресации
5. С++ : vector [код]
1. Размер удвавивается
2. clear() и resize(0) не освобождают память
3. Реализован внутри также, как это делали мы
4. Есть обращение a[i], есть безопасное обращение a.at(i), а еще можно определить struct myVector : vector