Структури данни

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 и изпратете Вашето предложение.
предишна тема
версия за печат
следваща тема
Страницата е посетена 9359 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: