Структури данни
Data Structures
Какво е структура данни? За какво се ползват те? Примерна структура данни
Вече се запознахме с това, какво представляват техниките и алгоритмите. Другата основна част от програмирането са структурите данни.
Структура данни
Структура данни (data structure, на английски) е набор от променливи и функции, които съхраняват данни в удобен за програмиста начин. Често, освен, че е удобно да се добавят и/или премахват нови елементи, структурите данни имат специално свойство, като например бърз достъп до специален елемент (първия, последния, медианата, максималния и др.), или функция, която връща по-специфична информация за елементите (сума, минимум в интервал, брой елементи, по-малки от дадена стойност и т.н). Някои структури данни са ужасно разпространени, като най-простите от тях вече познавате (например, масив). С много други от тях ще се запознаем по-нататък. От най-основните (динамичен масив, лист, опашка, стек, префиксен масив) ще минем през по-сложни такива (двоично дърво за търсене, приоритетна опашка, disjoint set forest, индексно дърво), като накрая ще се сблъскаме и със значително по-сложни такива (интервално дърво, балансирано дърво, и много други).Употреба на структурите данни
Най-често структурите данни се ползват като част от алгоритъм - като в зависимост от избора на структура данни той е различно бърз. Някои състезателни задачи са създадени специално за интересна структура данни, като изискват само нейните свойства. Някои от структурите данни са особено мощни - например с приоритетна опашка можете да сортирате ЕГН-тата на всички българи по света за по-малко от секунда - задача, за която ни трябваха около седем часа, при ползване на някой от сортиращите алгоритми, които разгледахме по-рано.Пример
Като пример ще имплементираме структурата данниset
. Тя ще представлява множество от елементи, като ще можем да добавяме и премахваме числа, да питаме дали дадено число се съдържа в множеството, и да питаме колко елемента има в множеството. Като допълнителна функционалност към стандартния set
, нашата структура данни ще може да отговаря (много бързо) на въпроса "кой е k-тият по големина елемент".Имплементацията ни няма да е най-оптималната възможна, но за сметка на това ще е (сравнително) проста за писане. Ще поддържаме сортиран масив с числата, като на всяко добавяне или изтриване ще ги разместваме (относително бавно) по такъв начин, че отново да са сортирани.
Съхранение на данните
Първото нещо, което трябва да определим, е как да съхраняваме числата от множеството. Най-лесното и що-годе единственото нещо, което знаем за сега, е масив, така че ще ползваме именно това. Ще ни трябва и допълнителна променлива, която указва колко елемента имаме вече в множеството. Разчитаме, че потребителят няма да добави повече от един милион елемента.const int MAX_SIZE = 1048576;
int setSize;
int setValues[MAX_SIZE];
Вземане на размера
Тъй като пазим размера в отделна променлива, то трябва просто да върнем стойността ѝ на потребителя. Сложността еO(1)
.
int getSize() {
return setSize;
}
Намиране на k-ти по големина елемент
Това е учудващо просто - тъй като държим елементите сортирани, то просто връщаме този с индекс k, ако изобщо имаме такъв елемент. В противен случай връщаме -1. Сложността еO(1)
.
int getKth(int k) {
if (k >= 0 && k < setSize)
return setValues[k];
// Невалиден индекс
fprintf(stderr, "ERROR: Invalid index %d!\n", k);
return -1;
}
Търсене на елемент
Проверка дали даден елемент е в множеството става сравнително просто, тъй като винаги държим елементите сортирани. За бързина, можем да ползваме двоично търсене (да, възможно е да имаме алгоритми вътре в структурите данни) за това. Ще връщаме индекса, на който сме намерили елемента, или -1, ако той не се намира в множеството. Сложността еO(log(N))
.
int find(int val) {
int left = 0, right = setSize - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (setValues[mid] == val)
return mid;
if (setValues[mid] < val)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
Добавяне на елемент
Вече споменахме, че добавянето няма да е особено умно. Първо проверяваме дали елементът вече не е в множеството. Ако е, директно спираме (все пак пишем множество а не мултимножество, следователно всяка стойност може да имаме максимум веднъж). Ако такъв елемент не съществува, в началото го добавяме в края на масива, като после го "довлачваме" до правилното му място (както правихме и при Bubble Sort). Сложността еO(N)
.
void insert(int val) {
int idx = find(val);
// Ако елементът вече е в множеството сме готови
if (idx != -1)
return;
// В противен случай го добавяме накрая и го завлачваме до мястото му
setValues[setSize++] = val;
for (int i = setSize - 1; i > 0; i--) {
if (setValues[i - 1] < setValues[i])
break;
swap(setValues[i - 1], setValues[i]);
}
}
Изтриване на елемент
Също не особено умно, и доста подобно на добавянето на елемент, проверяваме дали елементът съществува, като ако това е така, го изтриваме, като местим останалите елементи. Сложността еO(N)
.
void erase(int val) {
int idx = find(val);
// Ако елементът не е в множеството сме готови
if (idx == -1)
return;
// В противен случай го изтриваме и донаместваме останалите елемнети
for (int i = idx; i < setSize - 1; i++)
setValues[i] = setValues[i + 1];
setSize--;
}
Готови сме!
Това беше! Вече потребителят може да ползва нашите функции (наричани интерфейс) за да извършва поддържаните дейности. Ето и целия код, съчетан в едно:#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_SIZE = 1048576;
int setSize;
int setValues[MAX_SIZE];
int getSize() {
return setSize;
}
int getKth(int k) {
if (k >= 0 && k < setSize)
return setValues[k];
// Невалиден индекс
return -1;
}
int find(int val) {
int left = 0, right = setSize - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (setValues[mid] == val)
return mid;
if (setValues[mid] < val)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
void insert(int val) {
int idx = find(val);
// Ако елементът вече е в множеството сме готови
if (idx != -1)
return;
// В противен случай го добавяме накрая и го завлачваме до мястото му
setValues[setSize++] = val;
for (int i = setSize - 1; i > 0; i--) {
if (setValues[i - 1] < setValues[i])
break;
swap(setValues[i - 1], setValues[i]);
}
}
void erase(int val) {
int idx = find(val);
// Ако елементът не е в множеството сме готови
if (idx == -1)
return;
// В противен случай го изтриваме и донаместваме останалите елемнети
for (int i = idx; i < setSize - 1; i++)
setValues[i] = setValues[i + 1];
setSize--;
}
int main(void) {
int a[8] = {42, 13, 42, 666, 1337, 17, 42, 69};
for (int i = 0; i < 8; i++)
insert(a[i]);
for (int i = -1; i <= 10; i++)
fprintf(stdout, "%dth element is: %d\n", i, getKth(i));
for (int i = 0; i < 20; i++)
fprintf(stdout, "Found number %d at position: %d\n", i, find(i));
return 0;
}
Заключение
Структурите данни са изключително важно нещо, както за състезателите по информатика, така и за професионалните програмисти. И докато в комерсиалното програмиране рядко се налага да се ползва нещо по-сложно от динамичен масив, стек или опашка, то в състезателното програмиране ще срещнете много по-красиви, екзотични и хитри структури данни. You're in for a treat!Много от често ползваните структури данни са имплементирани в стандартните библиотеки на повечето програмни езици, така че няма да се налага да ги пишете изобщо (за това ще говорим в темата за STL). Но все пак намираме за особено полезно да знаете как работят те и какво поддържат.
За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 9359 пъти.