Podstawy
programowania II
Wykład 5: Dynamiczne struktury danych
Zachodniopomorska Szkoła Biznesu
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