2277150868

1, Dynamiczne struktury danych

Opracowanie: Ania Zawrzykraj

Dynamiczne struktury danych są to struktury, dla których pamięć jest przydzielana w momencie procesu obliczeniowego (dynamicznie) w przeciwieństwie do struktur statycznych, których zakres wartości i wzorzec pamięciowy jest ustalony raz na zawrze w momencie definiowania struktury (najczęściej w deklaracjach zmiennych na początku kodu programu). Dla zmiennych dynamicznych pamięć przydzielana jest w chwili powoływania ich do życia, a nie podczas translacji, dlatego mogą one zmieniać swoje rozmiary.

Zdefiniowanie takiej struktury odbywa się przez zastosowanie wskaźników. Przydzielenie pamięci dla zmiennej wskaźnikowej realizow ane jest w dwóch etapach:

•    w momencie deklaracji zmiennej przy dzielana jest pamięć dla adresu składowej struktur)',

•    przydzielenie pamięci dla samej składowej realizow ane jest poprzez wywołanie odpowiedniej funkcji.

Wskaźnik to zmienna przechowująca adres innej zmiennej (mówi nam, gdzie znajduje się zmienna, a nie co się w' niej znajduje)

Przy kład wskaźnika i jego wykorzystania (w języku C):

int *p    - zdefiniowanie wskaźnika, który będzie wskazywał na zmienną typu int

int z    - zdefiniowanie zmiennej z

p=&z    - wskaźnik wskazuje na zmienną p

(przechowuje adres zmiennej p, a nie jej wartość)

Struktury te zawierają odwołania do samych siebie np. elementy listy są listami.

Elementy struktury nie są umieszczone w pamięci bezpośrednio za sobą, każdy element struktury wyposażony jest w tzw. dowiązanie, które wskazuje na położenie następnego elementu struktury.

Do struktur dynamicznych możemy zaliczyć:

•    listy,

•    stosy,

•    kolejki,

•    drzewa,

•    grafy.

Strona 2 z 41