Podstawy
programowania II

Wykład 5: Dynamiczne struktury danych

Zachodniopomorska Szkoła Biznesu

Podstawy programowania II - Dynamiczne struktury

danych

Struktury danych



Dane - model rzeczywistości



Złożoność i wielość danych opisujących dany problem



Potrzeba organizacji danych w logiczne całości zwane
strukturami danych



grupowanie danych w sposób odzwierciedlający
rzeczywiste związki pomiędzy danymi



opis podobnych obiektów za pomocą jednakowych
zestawów danych



Korzyści płynące z budowy struktur danych



ułatwienie projektowania oprogramowania



możliwość automatyzacji przetwarzania danych



efektywniejsze zarządzanie pamięcią

Podstawy programowania II - Dynamiczne struktury

danych

Statyczne struktury danych



W przypadku problemów prostych i ograniczonych pod
względem liczby przetwarzanych danych stosuje się
struktury statyczne, których rozmiary i organizacja są
niezależne od samych danych i liczby obiektów



Typowe dane statyczne:



dane proste



tablice statyczne danych prostych



rekord



tablica statyczna rekordów

Podstawy programowania II - Dynamiczne struktury

danych

Dynamiczne struktury danych



Jeżeli problem jest złożony lub dane bardzo liczne, użycie
statycznych struktur powoduje:



niemożność efektywnego zarządzania pamięcią



niemożność odzwierciedlenia związków pomiędzy
poszczególnymi obiektami wśród przetwarzanych danych



Rozwiązaniem jest tworzenie dynamicznych struktur
danych, których organizacja w pewnym stopniu budowana
jest już na etapie wykonania programu. Wymaga to:



dynamicznego zarządzania pamięcią



organizacji danych w struktury zawierające m.in.
powiązania pomiędzy obiektami



Pozwala to na odzwierciedlenie związków pomiędzy
obiektami, co umożliwia znacznie efektywniejsze
przetwarzanie
danych (np. wyszukiwanie, sortowanie itp.)

Podstawy programowania II - Dynamiczne struktury

danych

Tworzenie struktur
dynamicznych



Elementarną strukturą danych w tym ujęciu jest rekord,
który stanowi opis pojedynczego obiektu za pomocą
pewnej liczby prostych danych (lub niewielkich struktur
statycznych)



Element, który jest charakterystyczny dla struktur
dynamicznych to wprowadzenie do każdego rekordu
jednego lub kilku powiązań z innymi obiektami
(podobnego lub innego typu)



W przypadku języka C++:



rekordy mają postać struktur (lub klas)



powiązania mają postać wskaźników



poszczególne obiekty tworzone są za pomocą
dynamicznej alokacji pamięci

Podstawy programowania II - Dynamiczne struktury

danych

Typowe struktury dynamiczne



Lista



jednokierunkowa



dwukierunkowa



cykliczna



Drzewo



drzewo binarne



Kolejka (zastosowanie listy)



FIFO



LIFO (Stos)

Podstawy programowania II - Dynamiczne struktury

danych

Lista jednokierunkowa



Model:



Deklaracja w C++:

struct Rekord

{

// zestaw danych ma temat jakiegoś obiektu,np.

float dana;

Rekord *next; // wskaźnik na następny rekord

};

Rekord *begin=NULL; // wskaźnik na początek listy

// NULL oznacza ostatni rekord

// na początku lista jest pusta

...

Dane 1

begin

Dane 2

Dane n

Podstawy programowania II - Dynamiczne struktury

danych

Przeglądanie listy



Służy do tego wskaźnik, który początkowo wskazuje na

początek listy, a następnie cyklicznie przesuwa się na

element następny aż do napotkania wartości

NULL

;



void PokazListe()

{

if (begin==NULL)

cout << "Lista pusta!\n";

else

{

Rekord *r=begin;

while (r!=NULL)

{

cout << r->dana<< endl;

r=r->next;

}

}

}

Podstawy programowania II - Dynamiczne struktury

danych

Pusta lista i dodawanie obiektów

Lista pusta:

begin

Dodanie elementu do listy:

begin

Dane 1

Dodanie drugiego elementu (na koniec
listy):

Dane 1

begin

Dane 2

Dane 1

begin

Dane 2

Dodanie trzeciego elementu (na początek listy):

Dane 3

Dodanie czwartego elementu (w środek listy):

Dane 1

begin

Dane 2

Dane 3

Dane 4

Podstawy programowania II - Dynamiczne struktury

danych

Dodanie obiektu do listy (C++)



Dodanie nowego obiektu na koniec listy:

Rekord *el=new Rekord;

// pominiemy tu kontrolę błędów alokacji

cin >> el->dana;

el->next=NULL;

// nowy obiekt będzie ostatni

Rekord *wsk=begin;

if (wsk==NULL)

// lista jest pusta

begin=el;

else

{

while (wsk->next!=NULL)

// znalezienie końca

wsk=wsk->next;

wsk=el;
}



Dodanie nowego obiektu na początek listy:

Rekord *el=new Rekord;

cin >> el->dana;

el->next=begin;

// dawny pierwszy element

begin=el;

Podstawy programowania II - Dynamiczne struktury

danych

Usuwanie obiektu z listy

Dane 1

begin

Dane 2

Dane 3

Dane 2

begin

Dane 1

Dane 3

Dane 2

begin

Dane 1

Dane 3

• Usunięcie obiektu w środku listy

• Usunięcie obiektu na początku listy

• Usunięcie obiektu na końcu listy

Podstawy programowania II - Dynamiczne struktury

danych

Usuwanie obiektu (C++)



Usunięcie pierwszego obiektu listy:

if (wsk!=NULL)

// lista nie jest pusta

{

Rekord *pierwszy=begin;

begin=begin->next;

delete pierwszy;

}



Usunięcie ostatniego obiektu z listy:

if (wsk!=NULL)

// lista nie jest pusta

{

Rekord *rek=begin;

while ((rek->next)->next!=NULL)

// przedost.

rek=rek->next;

delete rek->next;

rek->next=NULL;

}

Podstawy programowania II - Dynamiczne struktury

danych

Przykład listy jednokierunkowej



Program

LISTA.CPP

Podstawy programowania II - Dynamiczne struktury

danych

Wskaźnik na koniec listy



Często występuje konieczność wykonania operacji na
końcu listy (np. dopisanie nowego rekordu)



W takich wypadkach konieczne jest przeglądniecie całej
listy po kolei aby dojść do końca



Przydatne może być zapamiętanie wskaźnika na ostatni
rekord listy (wskaźnik ten będzie się zmieniał przy
dodaniu elementu na koniec lub usunięciu ostatniego
elementu)



Model:

...

Dane 1

begin

Dane n

end

Podstawy programowania II - Dynamiczne struktury

danych

Lista cykliczna jednokierunkowa



Model:



Ponieważ nie ma tu elementu ostatniego, podczas
przeglądania listy należy pamiętać albo liczbę elementów albo
sprawdzać czy adres elementu następnego jest równy

begin

.



Wskaźnik

begin

może być przestawiony na dowolny z

elementów listy (można przestawić jej początek)



Zastosowanie: zapamiętywanie danych zawierających cykl,
np. dane związane z kolejnymi miesiącami roku.



Struktura rekordu identyczna jak dla zwykłej listy
jednokierunkowej

Dane 1

begin

Dane 2

Dane n

Podstawy programowania II - Dynamiczne struktury

danych



Model:



Deklaracja w C++:

struct Rekord
{
float dana;

// przykładowe dane właściwe

Rekord *prev;

// wskaźnik na poprzedni rekord

Rekord *next;

// wskaźnik na następny rekord

};
Rekord *begin=NULL;
Rekord *end=NULL;

// nie zawsze jest tworzony

Lista dwukierunkowa

...

begin

Dane 1

Dane 2

Dane n

end

Podstawy programowania II - Dynamiczne struktury

danych



Model:



Ponieważ nie ma tu w zasadzie elementu pierwszego ani
ostatniego, podczas przeglądania listy należy pamiętać albo
liczbę elementów albo sprawdzać czy adres elementu
następnego jest równy

begin

.



Wskaźnik

begin

może być przestawiony na dowolny z elementów

listy (można przestawić jej umowny początek)



Zastosowanie: zapamiętywanie danych zawierających cykl,
np. dane związane z kolejnymi miesiącami roku.



Struktura rekordu identyczna jak dlazwykłej listy dwukierunkowej

Lista cykliczna dwukierunkowa

...

begin

Dane 1

Dane 2

Dane n

Podstawy programowania II - Dynamiczne struktury

danych

Cechy list



Łatwość wstawiania i usuwania elementów



Możliwość całkowitej zmiany kolejności elementów
(np. sortowanie)



Dostęp sekwencyjny do poszczególnych elementów
(konieczność przeszukiwania listy w celu dostępu do
elementu o określonym numerze)



W przypadku listy jednokierunkowej przeszukiwanie
odbywa się zawsze od elementu pierwszego w stronę
ostatniego



Lista dwukierunkowa umożliwia przeszukiwanie
elementów w obu kierunkach, a nawet wielokrotną
zmianę kierunku przeglądania.

Podstawy programowania II - Dynamiczne struktury

danych

Lista z atrapą (1)



W wielu rodzajach list tworzy się zawsze jeden rekord
zwany atrapą



Jedynymi danymi, jakie są wypełnione w atrapie są
powiązania (brak danych właściwych )



Celem tworzenia atrapy jest zapewnienie aby lista nigdy
nie była pusta, a wskaźniki

begin

i

end

nigdy nie miały

wartości NULL.



Ułatwia to opracowywanie algorytmów
przetwarzających listę



usunięcie warunku czy lista jest pusta



ułatwienie dopisania pierwszego lub ostatniego
elementu



W przypadku listy dwukierunkowej, atrapa może
występować zarówno na początku, jak i na końcu listy

Podstawy programowania II - Dynamiczne struktury

danych

Lista z atrapą (2)

Atrapa

begin

Dane n

• Lista jednokierunkowa z atrapą

...

Atrapa

Dane n

begin

end

• Lista dwukierunkowa z atrapą

...

Atrapa

begin

Dane n

• Lista cykliczna jednokierunkowa z atrapą

...

• Lista cykliczna dwukierunkowa z
atrapą

Atrapa

Dane n

begin

...

Podstawy programowania II - Dynamiczne struktury

danych

Kolejka FIFO (First In First Out)



Dopuszczalne operacje:



dopisanie elementu na początek listy



odczyt elementu z końca listy wraz z jego usunięciem



Realizacja może opierać się o listę jednokierunkową



Przykład realizacji: program

FIFO.CPP

Podstawy programowania II - Dynamiczne struktury

danych

Stos (kolejka LIFO - Last In First
Out)



Dopuszczalne operacje:



dopisanie elementu na początek listy



odczyt pierwszego elementu z listy wraz z jego
usunięciem



Realizacja może opierać się o listę jednokierunkową



Przykład realizacji: program

LIFO.CPP

Podstawy programowania II - Dynamiczne struktury

danych

Drzewa (1)



Drzewo to struktura dynamiczna o budowie
hierarchicznej



Każdy element posiada jednego rodzica i może mieć
kilka elementów potomnych



Model

Dane 1

Dane 11

Dane 12

Dane 13

Dane 121

Dane 122

Dane 123

Dane 131

Dane 132

Dane 1321

korzeń

liście

węzły

Podstawy programowania II - Dynamiczne struktury

danych

Drzewa (2)



Drzewo daje możliwość odzwierciedlenia hierarchii
obiektów występującej w rzeczywistości



przykład: zapis drzewa genealogicznego



Inną możliwością zastosowania drzewa jest
optymalizacja przeszukiwania dużych zbiorów obiektów.
Celem jest umożliwienie dojścia do szukanego obiektu
jak najkrótszą drogą



Warunkiem jest odpowiednie uporządkowanie obiektów
już na etapie ich dodawania do drzewa



Algorytm przeglądania drzewa nie jest jednoznaczny,
np.



przeglądanie poziomami od korzenia do liści



przeglądanie od gałęzi lewej do prawej

Podstawy programowania II - Dynamiczne struktury

danych

Drzewa binarne



Drzewo binarne to drzewo, w którym każdy węzeł
posiada dokładnie dwa powiązania z węzłami
potomnymi



Model:

Dane 1

Dane 11

Dane 12

Dane 121

Dane 122

Dane 111

Dane 112

Dane 1121

Dane 1122

Dane 1211

Podstawy programowania II - Dynamiczne struktury

danych

Drzewa binarne (C++)



Deklaracja:

struct Rekord
{
float dana;

// przykładowe dane właściwe

Rekord *child1, *child2;

// obiekty potomne

};
Rekord *root=NULL;

// korzeń

NULL