Динамичке структуре података

Динамичке структуре података представљају такве врсте структура података које могу да настају, мијењају капацитет и нестају и у току самог извршења програма. Динамичке структуре података су у врло широкој употреби у модерном програмирању.

Динамичке структуре се најчешће користе у ситуацијама када није унапријед задата горња граница количине потребног простора за складиштење података. Остварују се користећи алоцирање меморије у току рада програма и показиваче као везивно ткиво између основних јединица динамичке структуре. Динамичке структуре се најчешће реализују у облику стека, листе и дрвета, али су често коришћени и редови, обични низови и графови.

Реализација

Динамичка структура се реализује као коначан скуп јединица динамичке структуре, које су најчешће слогови (у програмском језику C struct, у Паскалу record итд.) због њихове могућности да садрже више елемената различитих типова, али се може реализовати и као обични низ, чија се величина мијења у току рада програма.

Реализација путем слогова

Слогови по својој природи могу садржати више елемената различитих типова, те се у њих може смјестити одређени број показивача који по својој декларацији могу показивати на слогове истог или сродног типа као и онај којем припадају, а преостали елементи да представљају релевантне податке које структура носи. На овај начин, организује се одређени скуп слогова, сваки од њих посједујући показиваче ка другим слоговима.

Слиједи низ примјера структура података реализованих путем слогова:

• Стабло се може реализовати као динамичка структура чији сваки слог посједује по два или више показивача (бинарно или вишеструко стабло), чији слогови са показивачима једнаким нули представљају листове стабла, а слог на који ниједан показивач из преосталих слогова не показује а који показује на бар један слог из преосталог скупа представља врх односно коријен стабла.
• Листа се може реализовати као динамичка структура чији сваки слог посједује по тачно један показивач који показује на сљедећи слог, а тачно један слог посједује показивач једнак нули, што представља крај листе.
• Стек се реализује на исти начин као и листа, само што се употреба стека разликује од употребе листе.
• Граф се може реализовати као динамичка структура чији сваки слог посједује неодређен број показивача (нпр. низ показивача) који показују на друге елементе листе.

Реализација путем обичног низа

Ако имамо низ n1 дужине N, и желимо да га проширимо на дужину N+K, проширивање се врши на сљедећи начин:

• алоцирамо нови низ n2 дужине N+K (користећи динамичко алоцирање)
• препишемо сав садржај низа n1 на почетак низа n2
• обришемо низ n1 (користећи динамичко ослобађање меморије)
• низу n2 промијенимо име у n1 (изједначавајући вриједност показивача n1 са вриједношћу n2

Динамичка структура реализована преко обичног низа се најчешће назива вектор.

Види још

• Структура података
• Стек
• Листа
• Ред
• Дрво
• Низ
• Граф (структура података)