Simple Data Structures

В тази секция ще разгледаме какво е структура данни и най-основните от тях: префиксен масив, динамичен масив (също наричан "vector"), стек, опашка, свързан списък, и приоритетна опашка. В повечето случаи няма да се налага да си ги пишете сами (тъй като са имплементирани в стандартните библиотеки на повечето езици). Все пак е хубаво да знаете как те са имплементирани и работят, както и какви са сложностите на операциите им, от една страна да не ги ползвате като "черна кутия", а от друга - защото в някои задачи се ползва само част от идеята им. Префиксният масив е значително по-рядко срещан в практическото програмиране, в следствие на което не е включен в стандартната библиотека. За сметка на това, както ще видим, има доста състезателни задачи, в които се ползва. Повечето от тези структури ще ползваме като част от алгоритми, които ще разгледаме по-нататък (например опашка при търсене в ширина и приоритетна опашка в алгиритъма на Дейкстра).

Подходящи теми, които можете да видите, са Структури данни, Префиксен масив, Динамичен масив, Списък, Опашка, Стек, Приоритетна опашка. Разбира се, за да не се налага да ги пишете всеки път, ще ви е полезно и да знаете как да ги ползвате от стандартната библиотека.

Задачите в секцията са такива, че да не можете да ползвате наготово вградените в STL имплементации. В повечето се ползва само идея от някоя от структурите, или операция, която стандартно не се поддържа. В задачата Sum of Primes ще можете да упражните Решето на Ератостен, което трябва да сте разгледали в предходната тема. В задачата Road Signs пък трябва да ползвате няколко масива, в които да пазите различна информация, така че да можете достатъчно ефективно да пресмятате отговора.