1

Dynamiczna alokacja pamięci,
biblioteka

stdlib.h

Funkcja

malloc

void* malloc (size_t size);

Przydziela pamięć o wielkości

size

bajtów. Obszar nie jest

inicjowany. Zwraca wskaźnik do nowo przydzielonego

bloku pamięci.

W przypadku niepowodzenia (np. nie ma wystarczająco

dużo miejsca w pamięci lub

size=0

) zwraca NULL oraz

do zmiennej

errno

wpisany jest kod błędu.

Przykład:

#include <stdlib.h>

int r = 10;
float* tab;

tab = malloc ( r * sizeof(float) );
tab[5] = 9;

lub
tab = malloc ( r * sizeof *tab );

2

Kontrola typów

Powyższy przykład jest poprawny dla języka C, nie jest
jednak poprawny dla języka C++

W C++ w stosunku do C została zaostrzona kontrola typów,
co wymaga stosowania jawnego rzutowania. Konwersja z

void*

na inne typy wskaźnikowe nie jest domyślna.

Język ten oferuje nowe sposoby alokacji pamięci (

new

,

delete

).

Kod poprawny dla C+++:

tab = (float*) malloc( r*sizeof(float) );

3

Funkcja

calloc

void *calloc (size_t n, size_t size);

Przydziela pamięć dla

n

elementów o rozmiarze

size

bajtów każdy i zeruje przydzieloną pamięć.

Jeżeli przydzielanie pamięci się powiodło, zwraca wskaźnik

do nowo przydzielonego bloku pamięci, w przeciwnym

przypadku zwraca NULL (i w zmiennej

errno

zapisuje

kod błędu).

Przykład:

#include <stdlib.h>

int r = 10;

float *tab;

tab=calloc(r, sizeof *tablica);

Uwaga: Podstawową różnicą pomiędzy funkcjami

malloc

i

calloc

jest to, że ta druga zeruje wartość przydzielonej

pamięci (do wszystkich bajtów wpisuje wartość 0).

4

Przykład: tablica wskaźników

int **tab = calloc(100,sizeof *tab);

Pomimo wyzerowania bajtów, nie możemy założyć, że

wszystkiego wskaźniki tablicy

tab

mają wartość NULL.

Nie możemy bowiem założyć, że w reprezentacji wskaźnika

NULL występują same zera, a tak nie musi być.

Bezpiecznie zainicjowana dynamiczna tablica wskaźników:

int **tab = malloc(100* sizeof *tab);

int i = 0;

while (i<100) tab [i++] = NULL;

5

Definicje makra NULL

stddef.h, locale.h, stdio.h, stdlib.h, string.h, time.h

#define NULL 0

#define NULL 0L

#define NULL ((void *) 0)

6

Funkcja

realloc

void *realloc(void *wsk, size_t size);

Zmienia rozmiar przydzielonego wcześniej bloku pamięci

wskazywanego przez

wsk

na

size

bajtów.

Dodatkowy obszar pamięci nie jest inicjowany.

Funkcja zwraca wskaźnik na nowy przydzielonego bloku

pamięci. Może to być wartość inna niż

wsk

.

Jeśli żądamy zwiększenia rozmiaru, a za zaalokowanym

aktualnie obszarem nie ma wystarczająco dużo wolnego

miejsca, funkcja znajdzie nowe miejsce i przekopiuje tam

starą zawartość. Wywołanie tej funkcji może więc

kosztować dużo czasu.

Przykład:

tab = realloc (tab, 2*r*sizeof *tab);

Jeżeli

tab

było równa NULL, funkcja zachowuje się tak

samo jako

malloc

.

Jeśli działanie funkcji nie powiedzie się, zwracany jest

NULL i w

errno

jest kod błędu

7

Funkcja

free

void free (void* wsk);

Zwalnia blok pamięci wskazywany przez

wsk

przydzielony

przez

malloc

,

calloc

lub

realloc (

a także

strdup

z biblioteki

string.h)

.

Jeżeli

wsk

ma wartość NULL funkcja nie robi nic.

Uwaga 1

Należy pamiętać o zwalnianiu pamięci - inaczej dojdzie do

tzw. wycieku pamięci - program będzie rezerwował nową

pamięć, ale nie zwracał jej z powrotem i w końcu pamięci

może mu zabraknąć.

Uwaga 2

Po wywołaniu

free

wskaźnik nie zmienia wartości

(pamięta wskazywany adres). Ale nie należy już się do niej

odwoływać. Dla bezpieczeństwa warto po wywołaniu

funkcji

free

przypisać wskaźnikowi wartość NULL.

Uwaga 3

Nie należy dwa razy zwalniać tego samego miejsca.

8

Przykład: Odczyt liczb

int size = 64;

int num = 0;

float *tab, tmp;

tab = malloc(size * sizeof *tab);

if (tab!=NULL) {perror("malloc");return 1;}

while (scanf("%f", &tmp)==1)

{

if (num==size)

{ /* trzeba zwi

ę

kszy

ć

tablice*/

float *wsk = realloc (tab,

(size *= 2) * sizeof *wsk);

if (wsk!=NULL) {

free (tab);

perror("realloc"); return 1;

}

tab = wsk;

}

tab[num++] = tmp;

}

while (num) printf ("%f\n", tab[--num]);

/* Zwolnienie pamieci */

free (tab);

9

Dynamiczne tablice wielowymiarowe

Tablica dwuwymiarowa — tablica wskaźników do tablic

Przykład – tabliczka mnożenia

int n;
int i, j;
int** tab;

printf("Podaj rozmiar: ");
scanf("%i", &n);

tab = malloc (n * sizeof *tab);

for (i=0; i<n; ++i)
tab [i] = malloc(n* sizeof **tab);

for (i=0; i<n; ++i)
for (j=0; j<n; ++j)
tab[i][j] = (i+1)*(j+1);

. . .

for (i = 0; i<n; ++i) free(tab[i]);

free(tab);

10

Możemy

alokować

inne

tablice

niż

normalne,

"kwadratowe", np.

Tablica trójkątna:

0123456789

…

0123

012

01

0

int** tab = malloc(10*sizeof *tab);

for (i = 9; i>=0; ++i)

tab [i] = malloc (i*sizeof **tab);

...

for (i = 0; i<10; ++i) free(tab[i]);

free(tab);

11

Tablica o dowolnym rozkładzie długości wierszy

const int wymiary[10] =

{ 2, 4, 6, 8, 1, 3, 5, 7, 9 };

int i;

int **tab = malloc(10*sizeof *tab);

for (i = 0; i<10; ++i)

tab [i] =

malloc (wymiary[i] * sizeof **tab);

12

Na tablicach dynamicznych można wykonywać różne

operacje, np. zamiana wierszy miejscami:

Przykład: Zamiana wierszy miejscami
Tablica:

int** tab

0123456789
…
012
01
0

int i = 0
int j = 9;
int* temp;

while (i<j)
{
temp = tab [i];
tab [i] = tab [j];
tab [j] = tab [i];
i++; j--;
}

Tablica:

0
01
012
…
0123456789

13

Tablice wielowymiarowe

- analogicznie, zwiększa się tylko liczba poziomów,

Przykład:

Tablica trójwymiarowa

int X = 100, Y = 10, Z = 10;

int x, y;

int ***tab;

tab = (int***)malloc(X*sizeof(int**));

for (x = 0; x < X ; ++x)

{

tab[x]=(int**)malloc (Y * sizeof(int*));

for (y = 0; y < Y; ++y)

tab[x][y]=(int*) malloc(Z*sizeof(int));

}

/* u

ż

ycie - jak tablicy trójwymiarowej */

tab[5][6][1] = 1;

int b = tab [5][6][1];

/* czyszczenie pami

ę

ci: */

for (x = 0; x < X; ++x)

{

for(y = 0; y < Y; ++y) free(tab[x][y]);

free(tab [x]);

}

free(tab);

14

Inne funkcje związane z pamięcią

Funkcja

memset,

plik

string.h

void* memset(void* tab, int c,size_t n);

Funkcja wypełnia kolejne

n

bajtów pamięci o adresie

tab

ustaloną wartością

c

. Zwraca wskaźnik na

tab

. Zasadniczo

stosowana dla napisów.

Przykład 1

#include <string.h>

int main()
{
char napis[10] ;
memset(napis, 'a', 5);
memset(napis+5, '-', 1);
memset(napis+6, 'b', 5);

puts(napis);
return 0;
}

Wynik działania:

aaaaa-bbbb

15

Przykład 2:

Nie możemy stosować tej funkcji dla tablicy liczb, chyba, że
chcemy ta tablicę wyzerować.

#include <stdio.h>
#include <string.h>

int main()
{
int i;
int t[5] ;

memset( t, 2 ,5*sizeof(int) );
for (i=0;i<5;i++) printf(“%d ”,t[i]);
printf(“\n”);

memset( t, 0 ,5*sizeof(int) );
for (i=0;i<5;i++) printf(“%d ”,t[i]);
printf(“\n”);

return 0;
}

Wynik działania:

33686018 33686018 33686018 33686018 33686018

0 0 0 0 0

16

Funkcja

memcpy,

plik

string.h

void *memcpy
(void* to, const void* from, size_t s);

Funkcja kopiuje

s

bajtów z pamięci o adresie

from

do

pamięci o adresie

to

. Zwraca wskaźnik do

to

Uwaga: Pod adresem to powinno być zaalokowane
dostatecznie dużo pamięci, co najmniej s bajtów.

Przykład

int t1[] = {1,2,3,4,5,6,7,8,9,10};

int* t2 = malloc(10 * sizeof(int));

memcpy ( t2, t1, 10*sizeof(int) );

for (i=0;i<10;i++) printf("%d ", t2[i]);

printf("\n");

Wynik:

1 2 3 4 5 6 7 8 9 10

17

Funkcja

memmove,

plik

string.h

void *memmove
(void* to, const void* from, size_t s);

Funkcja kopiuje

s

bajtów z pamięci o adresie

from

do

pamięci o adresie

to

. Zwraca wskaźnik do

to.

Różni się

od

memcpy

tym, że obszar odpowiadające adresom

from

oraz

to

mogą się częściowo pokrywać

.

Przykład

int t[] = {1,2,3,4,5,6,7,8,9,10};

memcpy ( t+4, t, 6*sizeof(int) );

Wynik:

1 2 3 4 1 2 3 4 1 2

memmove ( t+4, t, 6*sizeof(int) );

Wynik:

1 2 3 4 1 2 3 4 5 6

18

Pamięć

Dwa rodzaje pamięci: stos i sterta.

Stos (ang. stack)

1. Przechowuje zmienne programu:

•

rezerwacja pamięci dokonywana jest, gdy program

wchodzi

do

bloku,

w

którym

zmienne

są

zadeklarowane, a

•

zwalnianie pamięci dokonywane jest, kiedy program

opuszcza blok

•

dla zmiennych globalnych w momencie uruchomienia i

zakończenia programu.

2. Przechowuje informacje o wywoływanych funkcjach

(parametry, zmienne, wartość zwracana)

Każde wywołanie rekurencyjne funkcji wymaga pamiętania

na stosie:

•

Adresu powrotu,

•

parametry przekazane do funkcji

•

wartości zmiennych lokalnych

19

Przykład

int f(int n)
{
int b = 1;
if (n==1) return 1;
b = f(n-1)*n; /* adres 2 */
return b;
}

int main()
{
int n =4;
int a = f(n); /* adres 1 */
}

b=1

1

Wywołanie

f(1)

adres 2

Adres powrotu do funkcji f

b=1

2

Wywołanie

f(2)

adres 2

Adres powrotu do funkcji f

b=1

3

Wywołanie

f(3)

adres 2

Adres powrotu do funkcji f

b=1

4

Parametr dla funkcji f, Wywołanie

f(4)

adres 1

Adres powrotu do funkcji

main

a

n=4

Stos dla wywołań funkcji f

20

Rozmiar stosu

Zależy od kompilatora i systemu.

Pod linuxem można to sprawdzić (albo ustawić) za

pomocą:

ulimit –s

ulimit –s 65536

Błąd

przepełnienia stosu ( ang

.

stack overflow ).

Występuje zwykle wtedy, gdy pamięć stosu jest pełna a

chcemy zaalokować nowy obszar, np.

•

próba alokacji dużej tablicy statycznej

•

nastąpiło zbyt wiele wywołań funkcji (na ogół zbyt

głęboka

rekursja

lub

nieskończone

wywołania

rekurencyjne).

21

Sterta (ang. heap)

Obszar pamięci udostępniany przez system operacyjny

wykonującym się procesom.

Przechowywane są w nim zmienne „dynamiczne”, ich czas

ż

ycia nie jest związany z poszczególnymi blokami.

Programista sam rezerwuje dla nich miejsce i to miejsce

zwalnia.

Uwaga:

Rezerwowanie i zwalnianie pamięci na stercie zajmuje

więcej czasu niż analogiczne działania na stosie.

Sterta utrzymuje specjalną strukturę, w której trzymane są

wolne partie (może to być np. lista).

22

Błąd przepełnienia sterty

(ang. heap overflow)

Pojawia się przy próbie alokacji zmiennej dynamicznej, dla

której na stercie nie ma już miejsca (najczęściej z powodu

wycieku pamięci albo nieoptymalnego wykorzystania

pamięci przez program)

Wyciek pamięci

(ang. memory leak)

Pojawia się najczęściej, gdy program nie zwalnia

przydzielonej pamięci, przestaje o niej „pamiętać” i

rezerwuje nową.

Program z wyciekiem pamięci zajmuje coraz więcej

pamięci, ale nie jest w stanie jej wykorzystać ani zwolnić.

Przykład 1

int cos1()

{

int* wsk = malloc( sizeof int );

*wsk = 20;

return *wsk; //zamiast return wsk;

}

23

Przykład 2

void cos2 (struct osoba* os1)

{

struct osoba* os2 =

malloc(sizeof (struct osoba));

os2 = os1;

/* albo: os2 = NULL; */

return;

}

Przykład 3

int* cos3(int *a, int n)

{

int *b = malloc ( 10* sizeof int);

for (i=0; i<n; i++) b[i]=a[i]*a[i];

return b;

}

int *a = malloc(10*sizeof(int));

a = cos3(a, 10)

24

Popularne błędy

1.

Próba wykonania operacji na wskaźniku NULL.

2.

Brak sprawdzania, czy dany wskaźnik nie ma wartości

NULL.

3.

Odwołania się do obszaru pamięci po jego zwolnieniu. Po

wykonaniu funkcji

free

nie możemy już wykonywać

ż

adnych odwołań do zwolnionego obszaru. Warto wpisać

tam NULL.

4.

Odwołania do adresów pamięci, które są poza

przydzielonym obszarem

.

5.

Wyciek pamięci, czyli nie zwalnianie całej, przydzielonej

wcześniej pamięci

25

Przykłady struktur dynamicznych

Zbiór osób:

typedef struct {
char *imie;
char *nazwisko;
int wiek, zarobki;
} osoba;

int size = 5000;
osoba *tab;

tab =malloc(size * sizeof *tab);

w razie potrzeby:

wsk = realloc(tab,
(size *= 2) * sizeof *tab);

Problemy:

1. Zwiększanie rozmiaru jest czasochłonne – może

wymagać kopiowania…

2. Jak usuwać osoby ze środka tablicy?

3. Jak dodawać osoby do środka tablicy posortowanej?

26

Lista -

Abstrakcyjna struktura danych, w której

elementy uporządkowane są w sposób liniowy oraz na

której mogą być wykonywane różne operacje, tj. dodawanie

elementów w dowolne miejsce listy, usuwanie z dowolnego

miejsca, wyszukiwanie, itp.

Typowe operacje wykonywane na liście:

dodaj (element, gdzie, lista) - wstawia element na odpowiednia

pozycję w liście

usun (pozycja, lista) - kasuje element z określonej pozycji.

szukaj (element, lista) - znajduje element w liście i zwraca jego

pozycję

pierwszy (lista) - zwraca pozycję pierwszego elementu na

liście

ostatni (lista) - zwraca pozycję za ostatnim elementem w liście

poprzedni (pozycja, lista) - zwraca pozycję elementu

poprzedniego

nastepny (pozycja, lista) - zwraca pozycję elementu

następnego

czysc (lista) - czyści listę

27

Implementacje:

1.

Przykładem listy jest zwykła tablica. Porządek elementów

wyznaczają wówczas indeksy.

2.

Wskaźnikowa pojedynczo wiązana (jednokierunkowa)

3.

Wskaźnikowa podwójnie wiązana (dwukierunkowa)

4.

Kursorowa

Lista wskaźnikowa jednokierunkowa

Struktura składająca się ze struktur, w której porządek

wyznaczają

wskaźniki(adresy)

związane

z

każdym

elementem listy, inaczej mówiąc każdy element listy „zna”

adres swojego następnika.

Po liście możemy poruszać się w kierunku od pierwszego

do ostatniego.

Na takiej liście można „łatwo” dodawać/usuwać elementy.

Lista jest wskaźnikiem na swój pierwszy element.

28

Struktury odwołujące się do samych siebie

typedef struct os

{

char *imie;

char *nazwisko;

int wiek, zarobki;

struct os *nast;

} osoba;

osoba *lista;

Inicjowanie listy pustej

osoba *lista = NULL;

Ala
Kowalska
30
3000

Józek
Malinowski
35
3000

Genowefa
Wiśniewska
50
3500

lista

NULL

29

Tworzenie listy:

osoba *lista = malloc(sizeof osoba);

lista->imie = ”Ala”;
/* równowa

ż

nie (*lista).imie = ”Ala” */

lista->nazwisko = ”Kowalska”;
lista->wiek = 30;
lista->pensja = 3000;

osoba *temp = malloc(sizeof osoba);

temp->imie = ”Józek”;
temp->nazwisko = ”Malinowski”;
temp->wiek = 35;
temp->pensja = 3000;

lista->nast = temp;

temp = malloc(sizeof osoba);

temp->imie = ”Genowefa”;
temp->nazwisko = ”Wisniewska”;
temp->wiek = 50;
temp->pensja = 3500;
temp->nast = NULL;

lista->nast->nast = temp;

30

Przeglądanie listy:

/* ustawiamy si

ę

na pocz

ą

tku listy */

osoba *p = lista;

while (p != NULL)

{

/*jaka

ś

operacja na elemencie listy*/

visit(p)

/* przej

ś

cie do kolejnego elementu */

p = p->nast;

}

/* teraz p == NULL */

31

Wyszukiwanie elementu na liście

– wersja iteracyjna

osoba *szukaj(osoba *lista, int wiek)

{

osoba *p = lista;

while ((p != NULL) && (p->wiek !=wiek))

p = p->nast;

return p;

}

Jeśli

p == NULL

elementu szukanego nie ma,

Jeśli

p!=NULL

to wskazuje na szukany element.

Wyszukiwanie elementu na liście

– wersja rekurencyjna

osoba *szukaj(osoba *lista, int wiek)

{

if (lista == NULL) return NULL;

if (lista->wiek == wiek) return lista;

return szukaj(lista->nast, wiek );

}

32

Dodawanie elementu na początek listy:

void dodaj_p (osoba **lista, char *imie,
char *nazwisko, int wiek, int pensja)
{
osoba *temp = malloc(sizeof osoba);
temp->imie = strdup(imie);
temp->nazwisko = strdup(nazwisko);
temp->wiek = wiek;
temp->pensja = pensja;
temp->nast = *lista;

*lista = temp;
}

Ala
Kowalska
30
3000

Józek
Malinowski
35
3000

Genowefa
Wiśniewska
50
3500

lista

NULL

Marek
Nowakowski
45
3200

33

Dodawanie elementu w środek listy:

Ala
Kowalska
30
3000

Józek
Malinowski
35
3000

Genowefa
Wiśniewska
50
3500

lista

NULL

Marek
Nowakowski
45
3200

34

void dodaj (osoba *poprzednik,

char *imie, char *nazwisko,

int wiek, int pensja)

/* dodaj nowy element za struktur

ą

wskazywan

ą

przez poprzednik */

{

osoba *temp = malloc(sizeof osoba);

temp->imie = strdup(imie);

temp->nazwisko = strdup(nazwisko);

temp->wiek = wiek;

temp->pensja = pensja;

temp->nast = poprzednik->nast;

poprzednik->nast = temp;

}

Uwaga:

Kolejność instrukcji jest istotna. Poniższy fragment jest

błędny:

poprzednik->nast = temp;

temp->nast = poprzednik->nast;

35

Usuwanie elementy ze środka listy:

void usun (osoba *poprzednik)

{

/* usu

ń

element za struktur

ą

wskazywan

ą

przez poprzednik */

poprzednik->nast=poprzednik->nast->nast;

}

Ala
Kowalska
30
3000

Józek
Malinowski
35
3000

Genowefa
Wiśniewska
50
3500

lista

NULL

36

Funkcja

usun

jest niepoprawna, powoduje wyciek pamięci.

void usun2 (osoba *poprzednik)

{

/* usun element za struktur

ą

wskazywan

ą

przez poprzednik */

osoba *temp = poprzednik->nast;

poprzednik->nast = temp->nast;

free(temp);

}

Nadal jest wyciek pamięci…

void usun3 (osoba *poprzednik)

{

/* usun element za struktur

ą

wskazywan

ą

przez poprzednik */

osoba *temp = poprzednik->nast;

poprzednik->nast = temp->nast;

free(temp->imie);

free(temp->nazwisko);

free(temp);

}

Jak usunąć element, jeśli nie znamy jego poprzednika?

Należy go najpierw wyszukać – przebiec całą listę…

37

Lista wskaźnikowa dwukierunkowa

Lista wskaźnikowa, w której jest możliwość poruszania się

w obu kierunkach. Oznacza to, że każdy element listy

posiada wskaźnik do swojego poprzednika i wskaźnik do

swojego następnika.

typedef struct os

{

char *imie;

char *nazwisko;

int wiek, zarobki;

struct os *nast;

struct os *poprz;

} osoba;

Ala
Kowalska
30
3000

Józek
Malinowski
35
3000

Genowefa
Wiśniewska
50
3500

lista.
first

NULL

NULL

lista.
last

38

Lista jest pamiętana jako 2 wskaźniki:

adres elementu pierwszego i adres elementu ostatniego

Lista jest strukturą.

typedef struct

{

first *osoba

last *osoba

} Tlista;

Tlista lista;

Inicjowanie listy pustej

lista.first = NULL;

lista.last = NULL;

39

Dodawanie elementu na początek listy:

void dodaj_p (Tlista *lista, char *imie,
char *nazwisko, int wiek, int pensja)
{
osoba* temp = malloc(sizeof osoba);
temp->nazwisko = strdup(nazwisko);
temp->imie = strdup(imie);
temp->wiek = wiek;
temp->pensja = pensja;

temp->nast = lista->first;
temp->poprz = NULL;
lista->first = temp;
}

Ala
Kowalska
30
3000

Józek
Malinows
ki
35
3000

Genowefa
Wiśniewsk
a
50
3500

lista.
first

NULL

Marek
Nowakows
ki
45
3200

lista.
last

NULL

NULL

40

Poprawiona funkcja

dodaj

:

void dodaj_p (Tlista *lista, char *imie,

char *nazwisko, int wiek, int pensja)

{

osoba *temp = malloc(sizeof osoba);

temp->nazwisko = strdup(nazwisko);

temp->imie = strdup(imie);

temp->wiek = wiek;

temp->pensja = pensja;

temp->nast = lista->first;

temp->poprz = NULL;

if (lista->first != NULL)

lista->first->poprz = temp;

else lista->last = temp;

lista->first = temp;

}

41

Dodawanie elementu w środek listy:

Ala
Kowalska
30
3000

Józek
Malinowski
35
3000

Genowefa
Wiśniewska
50
3500

lista.
first

NULL

Marek
Nowakowski
45
3200

lista.
last

NULL

42

Usuwanie elementy ze środka listy:

void usun (Tlista *lista, osoba *wsk)

/* usun element wskazywany przez wsk */

{

osoba *temp = wsk->poprz;

if (temp!=NULL) temp->nast=wsk->nast;

else lista->first = wsk->nast;

temp = wsk->nast;

if (temp!=NULL) temp->poprz=wsk->poprz;

else lista->last = wsk->poprz;

free(temp->imie);

free(temp->nazwisko);

free(temp);

}

lista
.last

Ala
Kowalska
30
3000

Józek
Malinowski
35
3000

Genowefa
Wiśniewska
50
3500

lista.
first

NULL

wsk

43

Lista kursorowa –

symulacja wskaźników w tablicy

lista

4

-1

9

2

5

7

struct

{

char* nazwisko;

int wiek

int next;

} tab[100];

int lista; //indeks komórki

pierwszego elementu listy

Lista jest indeksem.

Ostatni element listy ma „wskaźnik”/kursor

next

ustawiony na

-1

.

44

Lista elementów wolnych

Wszystkie wolne komórki tablicy – nienależące do listy są

powiązane w listę elementów wolnych.

int wolne; //indeks wolnej komórki

lista = 1

3

4

-1

6

9

2

8

5

-1

7

wolne = 0

Przygotowanie

Inicjalizacja_tablicy (),

Funkcja wiąże wszystkie elementy w listę elementów
wolnych oraz ustawia zmienną

wolne

na 0.

Funkcję należy wykonać na początku działania programu.

Inicjalizacja listy

lista = -1;

45

Operacje

Algorytmy operacji są analogiczne jak te dla list

wskaźnikowych, tyle, że

•

zamiast pracować na wskaźnikach operujemy na

indeksach (kursorach)

•

wskaźnik pusty (NULL) identyfikowany jest przez -1

•

podczas dodawania do listy nowego elementu –

usuwamy pierwszy element z listy elementów wolnych,

o ile to możliwe. W przeciwnym przypadku dodawania

nie można wykonać.

•

podczas usuwania elementu z listy – dodajemy usunięty

element do na początek listy elementów wolnych

W jednej tablicy można przechowywać jednocześnie wiele

różnych list kursorowych.

46

Przykład 1: Wyszukiwanie

int szukaj(int lista, int wiek)

{

int p = lista;

while ((p != -1) && (p.wiek !=wiek))

p = p.nast;

return p;

}

Jeśli

p == -1

elementu szukanego nie ma, w przeciwnym

razie

p>-1 i

wskazuje na szukany element.

Przykład 2: Dodawanie na początek

int dodaj_p (int lista, char *nazwisko,

int wiek){

if (wolne == -1) return 0;

temp = wolne;
wolne = tab[wolne].next;

tab[temp].nazwisko = strdup(nazwisko);
tab[temp].wiek = wiek;
tab[temp].nast = lista;
lista = temp;
}

47

Lista kursorowa dwukierunkowa

Analogiczna do listy wskaźnikowej dwukierunkowej.

Każda komórka tablicy przechowuje dodatkowo dwa

indeksy – indeks poprzednika oraz indeks następnika.

struct

{

char* nazwisko;

int wiek

int next;

int prev;

} tab[100];

lista = 1

3

4

-1

6

9

2

8

5

-1

7

-1

5

1

7

9

4

wolne = 0

48

Przygotowanie

Inicjalizacja_tablicy ()

Przygotowanie jest takie samo jak w przypadku listy

kursorowej jednokierunkowej.

Funkcja wiąże wszystkie elementy w listę elementów

wolnych oraz ustawia zmienną

wolne

na 0.

Lista elementów wolnych może być listą jednokierunkową:

dodawanie do niej i usuwanie zawsze odbywa się dla

pierwszego elementu.

Definicja listy

typedef struct

{

int first;

int last;

} Tlista;

Tlista lista;

Inicjalizacja listy:

lista.first = -1;
lista.last = -1;

49

Drzewo

Struktura danych, w której na elementy narzucona jest

pewna drzewiasta struktura, na której wykonywane są

operacje:

•

dodawania,

•

usuwania,

•

przeszukiwania,

•

czasem łączenie

Drzewa nieukorzenione

Drzewa ukorzenione

Drzewa wielodzietne (wieloarne)

Drzewa binarne

Implementacja wskaźnikowa

Implementacja kursorowa

Implementacja „left-child, right-sibling”

50

Graf

– struktura danych, składająca się ze zbioru

wierzchołków V i zbioru krawędzi E, czyli połączeń między

wierzchołkami.

Jeśli krawędzie mają określony kierunek graf nazywamy

skierowanym, w przeciwnym wypadku mówimy że jest ona

nieskierowany

Ś

cieżka - czyli ciąg wierzchołków, między którym

przechodzimy za pomocą krawędzi, np. abzx

Cykl –ścieżka, której pierwszy wierzchołek jest zarazem

wierzchołkiem ostatnim, np. abcxd

Graf spójny – graf, w którym między każdymi dwom

wierzchołkami istnieje ścieżka.

x

z

a

b

c

y

d

51

Drzewo nieukorzenione

Nieskierowany grafy spójny nie zawierający cykli

Wierzchołki drzewa często nazywamy węzłami.

Drzewo ukorzenione

Drzewo, w którym jeden z wierzchołków został wyróżniony

i nazywany jest korzeniem oraz krawędzie zostają

skierowane w taki sposób, że każdy węzeł, z wyjątkiem

korzenia ma dokładnie jedna krawędź wchodząca.

x

z

a

b

c

y

d

52

Przykład:

Pojęcia:

węzeł drzewa – element drzewa

ojciec (rodzic) węzła y – węzeł x, który wskazuje na
element y, np.

x->left

== y lub

x->right ==y

korzeń drzewa – węzeł, który nie ma ojca

syn (dziecko) węzła y – element wskazywany przez y

brat elementu y – węzeł, który ma z

y

wspólnego ojca

liść – węzeł który nie posiada dzieci (jego wskaźniki

left

i

right

mają wartość NULL)

poddrzewo o korzeniu y – fragment drzewa zawierający

węzeł

y

, jego dzieci, dzieci, itd.

x

z

NULL

NULL

a

b

NULL

NULL

NULL

NULL

c

NULL

y

53

Rodzaje drzew

Drzewo binarne – drzewo ukorzenione, w którym każdy

węzeł ma co najwyżej dwoje dzieci.

Drzewo binarne regularne – drzewo binarne, w którym

każdy węzeł ma albo dwoje albo zero dzieci.

x

z

a

d

f

y

b

c

e

54

Drzewo trzyarne – drzewo ukorzenione, w którym każdy

węzeł ma co najwyżej troje dzieci

Drzewo wielodzietne – drzewo ukorzenione, w którym

każdy węzeł ma dowolną liczbę dzieci

Drzewo binarne (trzyarne) pełne – drzewo binarne

(trzyarne) regularne, którego wszystkie liście znajdują się na

tym samym poziomie (tzn. dla wszystkich liści w drzewie,

długość ich najkrótszej ścieżki od korzenia jest taka sama)

x

a

y

b

a

y

b

55

Przeglądanie drzewa binarnego (inorder)

1. przeglądnij lewe poddrzewo węzła

x

(rekurencyjnie)

2. wypisz wartość węzła x (albo wykonaj inną akcje na
węźle x)

3.· przeglądnij prawe poddrzewo węzła

x

(rekurencyjnie)

Wynik przeglądania:

2, 16, 6, 17, 9, 1, 12, 15, 20, 5, 3

1

17

15

16

5

9

6

2

3

12

20

56

Przeglądanie drzewa binarnego (preorder)

1. wypisz wartość węzła x (albo wykonaj inną akcje na
węźle x)

2. przeglądnij lewe poddrzewo węzła

x

(rekurencyjnie)

3.· przeglądnij prawe poddrzewo węzła

x

(rekurencyjnie)

Wynik przeglądania:

1, 17, 16, 2, 6, 9, 15, 12, 5, 20, 3

1

17

15

16

5

9

6

2

3

12

20

57

Przeglądanie drzewa binarnego (postorder)

1. przeglądnij lewe poddrzewo węzła

x

(rekurencyjnie)

2.· przeglądnij prawe poddrzewo węzła

x

(rekurencyjnie)

3. wypisz wartość węzła x (albo wykonaj inną akcje na
węźle x)

Wynik przeglądania:

2, 6, 16, 9, 17, 12, 20,3, 5, 15, 1

1

17

15

16

5

9

6

2

3

12

20

58

Przeglądanie drzewa binarnego poziomami

1.

Dla każdego poziomu wypisz kolejno węzły na tym

poziomie. Wypisywanie rozpocznij od poziomu na

którym znajduje się korzeń

Wynik przeglądania:

1, 17, 15, 16, 9, 12, 5, 2, 6, 20, 3

1

17

15

16

5

9

6

2

3

12

20

59

Drzewo binarne – implementacja wskaźnikowa

typedef struct os

{

int liczba;

struct os *lewy;

struct os *prawy;

} osoba;

osoba *korzen;

Inicjowanie drzewa pustego

osoba *korzen = NULL;

Czasem drzewo jest wzbogacone o wskaźnik do „rodzica”

typedef struct os

{

int liczba;

struct os *lewy;

struct os *prawy;

struct os *ojciec;

} osoba;

60

Drzewo binarne – implementacja kursorowa

struct os

{

int liczba;

int lewy;

int prawy;

} tab[100];

Drzewo wzbogacone o kursor do „rodzica”

struct os

{

int liczba;

int lewy;

int prawy;

int ojciec;

}tab[100];

61

Przygotowanie

Inicjalizacja_tablicy (),

Przygotowanie jest takie samo jak w przypadku list

kursorowych.

Łączymy

w

listę

(jednokierunkową)

wszystkie elementy tablicy

Inicjowanie drzewa pustego

int korzen = -1;

W jednej tablicy może być kilka struktur kursorowych,

zarówno list (jedno i dwukierunkowych) jak i kilka drzew.

62

Drzewo poszukiwań binarnych

Drzewo BST (binary search tree),

Drzewo BST to drzewo binarne, dla którego wartość
przechowywana w węźle jest większa od wartości
przechowywanej w lewym synu i mniejsza od wartości
przechowywanej w prawym synu
(relacja może być odwrócona).

Fakt.

Dla dowolnych węzłów drzewa x, y zachodzi:

jeśli x jest w lewym poddrzewie o korzeniu y, to x<y

jeśli x jest w prawym poddrzewie o korzeniu y, to x>y

10

7

15

5

25

9

6

2

30

12

20

63

Przeglądanie drzewa (inorder)

1. przeglądnij lewe poddrzewo węzła

x

(rekurencyjnie)

2. wypisz wartość węzła x
3.· przeglądnij prawe poddrzewo węzła

x

(rekurencyjnie)

Wynik przeglądania:

2, 5, 6, 7, 9, 10, 12, 15, 20, 25, 30

Fakt.

Drzewo binarne jest drzewem BST wtedy i tylko wtedy gdy

lista jego węzłów w porządku inorder jest ciągiem

rosnącym.

10

7

15

5

25

9

6

2

30

12

20

64

Wyszukiwanie w drzewie

Szukamy w drzewie węzła o wartości

x

:

Porównujemy wartość

x

z wartością aktualnego węzła

k

x == k

– cieszymy się, że znaleźliśmy

x < k

– szukamy w lewym poddrzewie

x > k

– szukamy w prawym poddrzewie

typedef struct os
{
int liczba;
struct os *lewy;
struct os *prawy;
} osoba;

osoba *szukaj (osoba *korzen, int k)
{
osoba *temp = korzen;
while (temp!=NULL && temp->liczba!=k)
{

if (temp->liczba<k) temp=temp->lewy;
else temp=temp->prawy;
}
return temp;
}

Jeśli dojdziemy w ten sposób do pustego drzewa
(

temp==NULL

) elementu nie ma w drzewie.

65

Dodawanie do drzewa:

Postępujemy jak przy wyszukiwaniu i nowy element

wstawiamy w liściach

10

7

15

5

25

9

6

2

30

12

20

11

66

Usuwanie całego drzewa

void usunDrzewo(osoba *korzen)

{

/* wersja rekurencyjna

if (korzen != NULL) {

usunDrzewo(korzen->lewy);

usunDrzewo(korzen->prawy);

free(korzen);

}

return;

}

usunDrzewo(korzen);

korzen = NULL:

67

Usuwanie jednego węzła w drzewie

10

7

15

5

25

9

6

2

30

12

20

11

23

18

19

10

7

18

5

25

9

6

2

30

12

20

11

23

19

68

Usuwanie jednego węzła w drzewie

1.

Znajdujemy węzeł

x

, który chcemy usunąć.

2.

Rozpatrujemy przypadki:

a.

jeśli

x

nie ma dzieci – usuwamy go

b.

jeśli

x

ma tylko jedno dziecko – zastępujemy go

własnym dzieckiem

c.

jeśli

x

ma dwoje dzieci:

•

znajdujemy następnik

y

(najbardziej lewy element w

prawym poddrzewie

x

)

•

zastępujemy zawartość węzła

x

przez zawartość

węzła

y

•

usuwamy węzeł

y

(syn

y

stanie się synem swojego

„dziadka”)

Możliwa wersja druga:

•

znajdujemy poprzednik

y

(najbardziej prawy

element lewego podrzewa)

•

dalej tak samo

69

Drzewo trzyarne

– implementacje analogiczne

do binarnych

typedef struct os

{

int liczba;

struct os *pierwszy;

struct os *drugi;

struct os *trzeci;

struct os *ojciec;

} osoba;

osoba* korzen = NULL;

struct os

{

int liczba;

int pierwszy;

int drugi;

int trzeci;

int ojciec;

} tab[100];

int korzen = -1;

70

Drzewo wielodzietne

1. Implementacja poprzez tablicę lub listę
dzieci

1. Drzewo jest wskaźnikiem (kursorem) na korzeń drzewa.

2.

Każdy węzeł „pamięta” wskaźnik na tablicę lub listę

zawierająca wskaźniki do swoich dzieci.

3.

Wszystkie węzły mogą być stablicowane. Wówczas

zamiast wskaźników mogą być pamiętane indeksy dzieci.

2. Implementacja poprzez wskaźnik na rodzica

1. Wszystkie węzły drzewa są stablicowane.

2. Każdy węzeł „pamięta” wskaźnik (albo kursor) na

swojego rodzica.

3.

Dodatkowo może być pamiętana lista (tablica) liści

drzewa.

4.

Przy tym podejściu chodzimy po drzewie „od dołu”.

71

3. Implementacja „left-child, right-sibling”

==

implementacja

za

pomocą

drzewa

binarnego

(wskaźnikowego lub kursorowego)

1. Drzewo jest wskaźnikiem na korzeń.

2. Każdy węzeł struktury „pamięta” dwa wskaźniki

•

wskaźnik na swoje pierwsze dziecko

•

wskaźnik na swojego brata

Przykład

korzen

a

c

e

h

n

b

f

d

i

o

g

m

l

k

j

p

q

r

72

Implementacja wskaźnikowa:

typedef struct os

{

int liczba;

struct os *first_child;

struct os *next_sibling;

struct os *parent;

//ewent.

} osoba;

osoba* korzen = NULL;

Implementacja kursorowa:

struct os

{

int liczba;

int first_child;

int next_sibling;

int parent; //ewent.

} tab[100];

int korzen =-1;