Algorytmy i struktury danych

Wykład 3

Podstawy struktur danych

Liniowe struktury danych (listy)

Rodzaje struktur liniowych

Implementacja list

Podstawowe operacje na listach jednokierunkowych

2

Algorytmy i struktury danych

Definicja struktury danych

Definicja

Struktur

ą

danych nazywamy trójk

ę

uporz

ą

dkowan

ą

S = (D, R, e)

,

gdzie:

D

– oznacza zbiór danych elementarnych

R={r

we

, N}

– jest zbiorem dwóch relacji okre

ś

lonych na strukturze danych:

– relacja wej

ś

cia do struktury danych S,

– relacja nast

ę

pstwa (porz

ą

dkuj

ą

ca) struktur

ę

S,

e

– jest elementem wej

ś

ciowym do struktury danych S

(nie jest to element danych struktury danych S).

D

e

r

we

×

⊂

D

D

N

×

⊂

3

Algorytmy i struktury danych

Zbiór danych elementarnych

D



Zbiór danych elementarnych jest sko

ń

czony i dla wygody operowania

oznaczeniami jego elementów poszczególne dane s

ą

indeksowane od

warto

ś

ci 1 w kierunku warto

ś

ci wi

ę

kszych.



Przykład:



Liczno

ść

powy

ż

szego zbioru danych elementarnych wynosi 5, czyli

{

}

5

4

3

2

1

d

,

d

,

d

,

d

,

d

=

D

5

D

=

4

Algorytmy i struktury danych

Dane elementarne - zmienne programowe



Dane elementarna

d

i

s

ą

poj

ę

ciem abstrakcyjnym, rozumianym jako tzw.

„nazwana warto

ść

”. Jest ona okre

ś

lana jako uporz

ą

dkowana dwójka

elementów:

, gdzie:



n

i

– nazwa danej,



w

i

– aktualna warto

ść

danej z okre

ś

lonej dziedziny warto

ś

ci.



Zmienna programowa jest poj

ę

ciem zwi

ą

zanym z realizacj

ą

danej

w konkretnym

ś

rodowisku programistycznym. Posiada zdefiniowan

ą

nazw

ę

, wraz z okre

ś

leniem dziedziny warto

ś

ci, któr

ą

mo

ż

e przyjmowa

ć

i

i

i

w

n

d

,

=

5

Algorytmy i struktury danych

Relacja

r

we

– wskazanie korzenia struktury S



Relacja , jest opisywana poprzez zbiór (jedno- lub
wieloelementowy) par uporz

ą

dkowanych elementów, z których pierwszym

jest zawsze element wej

ś

ciowy

e

, natomiast drugim elementem jest jedna

z danych elementarnych ze zbioru

D

.



Element

d

i

„uczestnicz

ą

cy” w relacji

r

WE

nazywamy korzeniem struktury

danych S.



Struktura musi mie

ć

zdefiniowany co najmniej jeden korze

ń

.



Przykład:

Je

ś

li struktura S posiada dwa korzenie: d

2

oraz d

5

, to

{

}

d

,

e

,

d

,

e

r

5

2

we

=

D

e

r

we

×

⊂

6

Algorytmy i struktury danych

Relacja

N

– ustalenie porządku struktury S



Relacja nast

ę

pstwa N opisuje wzajemne uporz

ą

dkowanie elementów

w strukturze danych S. Porz

ą

dek struktury opisujemy w postaci zestawów

par uporz

ą

dkowanych elementów.



Przykładowy porz

ą

dek pi

ę

cioelementowej struktury danych S:

{

}

3

5

4

3

4

1

3

1

1

2

d

,

d

,

d

,

d

,

d

,

d

,

d

,

d

,

d

,

d

N

=

poprzednik

następnik

7

Algorytmy i struktury danych

Model grafowy struktury danych



Aby łatwiej zobrazowa

ć

struktur

ę

danych i w ten sposób lepiej j

ą

zrozumie

ć

,

mo

ż

na zbudowa

ć

dla niej model grafowy. W modelu tym:



w

ę

zły (wierzchołki) oznaczaj

ą

poszczególne dane elementarne,



łuki (strzałki) słu

żą

do odwzorowania nast

ę

pstw poszczególnych danych

elementarnych w strukturze S.

Przykład: Model grafowy dla opisywanej struktury S:

{

}

5

4

3

2

1

,

,

,

,

d

d

d

d

d

D

=

{

}

5

2

,

,

,

d

e

d

e

r

we

=

{

}

3

5

4

3

4

1

3

1

1

2

,

,

,

,

,

,

,

,

,

d

d

d

d

d

d

d

d

d

d

N

=

e

d

2

d

5

d

1

d

3

d

4

liść

korzeń

korzeń

8

Algorytmy i struktury danych

Liniowe struktury danych

Wyró

ż

niamy cztery rodzaje list:

jednokierunkowe listy niecykliczne,

dwukierunkowe listy niecykliczne,

jednokierunkowe listy cykliczne (pier

ś

cienie jednokierunkowe),

dwukierunkowe listy cykliczne (pier

ś

cienie dwukierunkowe).

9

Algorytmy i struktury danych

Jednokierunkowe listy niecykliczne

Model grafowy listy jednokierunkowej:

e

d

1

d

2

d

3

d

n

10

Algorytmy i struktury danych

Dwukierunkowe listy niecykliczne

Model grafowy listy dwukierunkowej:

e

d

1

d

2

d

3

d

n

11

Algorytmy i struktury danych

Pierścień jednokierunkowy

Model grafowy pier

ś

cienia jednokierunkowego:

e

d

1

d

2

d

3

d

n

12

Algorytmy i struktury danych

Pierścienie dwukierunkowe

Model grafowy pier

ś

cienia dwukierunkowego:

e

d

1

d

2

d

3

d

n

13

Algorytmy i struktury danych

Podstawowe operacje na listach

1.

Wyszukiwanie elementu na li

ś

cie

2.

Doł

ą

czanie elementu do listy

3.

Usuwanie elementu z listy

4.

Przestawianie elementów na li

ś

cie

5.

Porz

ą

dkowanie (sortowanie) listy

14

Algorytmy i struktury danych

Dynamiczne realizacje struktur listowych

Element listy zawiera:



Dane elementarne,



Odwzorowanie relacji nast

ę

pstwa – informacja o dowi

ą

zaniu

do innych elementów;

dane

wska

ź

nik na nast

ę

pny element

startPtr

NULL

Ogon (tail)

Głowa (head)

15

Algorytmy i struktury danych

dane

elementarne

dowiązanie

do kolejnego

elementu

Dynamiczne realizacje struktur listowych

Deklaracja elementu listy:

struct Node {

char dane;
struct Node *next;

};

typedef struct Node *NodePtr;

/* definicja typu wska

ź

nikowego do struktury Node */

16

Algorytmy i struktury danych

Wyszukiwanie elementu na liście

Algorytm wyszukania elementu na li

ś

cie jednokierunkowej:



Cel:



Wyszukanie elementu na li

ś

cie;



Dane wej

ś

ciowe:



Wska

ź

nik na pierwszy element listy;



Kryterium poszukiwania, np. warto

ść

danej elementarnej;



Uwagi:



W skrajnym przypadku nale

ż

y przejrze

ć

wszystkie elementy

(zło

ż

ono

ść

:

Θ

(n));

17

Algorytmy i struktury danych

Algorytm wyszukiwania elementu na liście jednokierunkowej

1. Rozpocznij wyszukiwanie od pierwszego elementu listy;

2. Dopóki nie osi

ą

gni

ę

to ko

ń

ca listy oraz szukana warto

ść

jest

ró

ż

na od warto

ś

ci aktualnego elementu przejd

ź

do nast

ę

pnego

elementu listy;

3. Zwró

ć

wska

ź

nik na znaleziony (aktualny) element lub warto

ść

NULL (gdy szukanej warto

ś

ci nie znaleziono)

startPtr

D

A

C

B

18

Algorytmy i struktury danych

Algorytm wyszukiwania elementu na liście jednokierunkowej

struct Node {

char dane;
struct Node *next;

};

typedef struct Node *NodePtr;

Node *Find (Node *startPtr, char szukwart) {

NodePtr currPtr = startPtr;

/* adres na pierwszy element listy */

while ((currPtr != NULL) && (currPtr -> dane != szukwart))

currPtr = currPtr -> next;

return currPtr;

}

19

Algorytmy i struktury danych

Dynamiczne realizacje struktur listowych

Przykład:

Node *element = Find (startPtr, ‘C’);

startPtr

currPtr

prevPtr

newPtr

A

B

D

NULL

NULL

C

NULL

startPtr

D

A

B

C

currPtr

Warto

ść

szukana: C

currPtr: startPtr

currPtr -> dane: A

20

Algorytmy i struktury danych

startPtr

currPtr

prevPtr

newPtr

A

B

D

NULL

NULL

C

NULL

startPtr

D

A

B

C

Dynamiczne realizacje struktur listowych

Przykład (cd):

Node *element = Find (startPtr, ‘C’);

currPtr

Nazwa szukana: C

currPtr: currPtr -> next

currPtr -> dane: B

21

Algorytmy i struktury danych

startPtr

currPtr

prevPtr

newPtr

A

B

D

NULL

NULL

C

NULL

startPtr

D

A

B

C

Dynamiczne realizacje struktur listowych

Przykład (cd.)

Node *element = Find (startPtr, ‘C’);

currPtr

Nazwa szukana: C

currPtr: currPtr -> next

currPtr -> dane: C

22

Algorytmy i struktury danych

Algorytm dołączania elementu do uporządkowanej listy

jednokierunkowej



Cel:



Dodanie nowego elementu (z warto

ś

ci

ą

C) do listy uporz

ą

dkowanej

(we wła

ś

ciwe miejsce);



Dane wej

ś

ciowe:



Wska

ź

nik na pierwszy element listy;



Dane do wstawienia na list

ę

;

startPtr

A

B

D

C

23

Algorytmy i struktury danych

Algorytm dołączania elementu do uporządkowanej listy jednokierunkowej

1. Utwórz element i ustal dane elementarne

2. Znajd

ź

miejsce wstawienia elementu na list

ę



Zainicjuj currPtr na pocz

ą

tek listy a prevPtr na NULL;



Dopóki currPtr jest ró

ż

ny od NULL i warto

ść

wstawiana jest wi

ę

ksza

od currPtr->dane:

• Ustaw prevPtr na currPtr;

• Przesu

ń

currPtr na nast

ę

pny element listy;

3. Wstaw element na list

ę

:



wstaw element jako pierwszy na li

ś

cie:

• Ustaw pole next elementu wstawianego na pierwszy element

listy;

• Ustaw wska

ź

nik do listy na element wstawiony;



lub wstaw element w wyznaczone miejsce na li

ś

cie:

• Ustaw pole next elementu prevPtr na element wstawiany;

• Ustaw pole next elementu wstawianego na element currPtr;

24

Algorytmy i struktury danych

1. Utwórz element i ustal dane elementarne

struct Node {

char dane;
struct Node *next; };

typedef struct Node *NodePtr;

int insert (NodePtr *startPtr, char wstwart) {

struct Node *newPtr, *currPtr, *prevPtr;
int retcode;

/* Utwórz element Node */

newPtr = (struct Node*)malloc(sizeof(struct Node));

startPtr

currPtr

prevPtr

newPtr

A

B

D

25

Algorytmy i struktury danych

1. Utwórz element i ustal dane elementarne (cd.)

if (newPtr == NULL) /* weryfikacja przydzielonej pami

ę

ci*/

return 1;

else
{ /* Ustal dane elementarne w Node */

newPtr -> dane = wstwart;

newPtr -> next = NULL;
/* Zainicjowanie wska

ź

ników pomocniczych */

currPtr = startPtr; /* ustaw wska

ź

nik na głow

ę

listy */

prevPtr = NULL;

startPtr

currPtr

prevPtr

newPtr

A

B

D

NULL

C

26

Algorytmy i struktury danych

2. Znajdź miejsce wstawienia elementu na listę

/* Znajd

ź

miejsce wstawienia */

while ((currPtr != NULL) && (wstwart > currPtr->dane))
{

prevPtr = currPtr;
currPtr = currPtr -> next;

}

startPtr

currPtr

prevPtr

newPtr

A

B

D

C

27

Algorytmy i struktury danych

3. Wstaw element na listę

if (prevPtr == NULL)

/* Wstaw element jako pierwszy na li

ś

cie */

{

newPtr -> next = *startPtr;
*startPtr = newPtr;

}

startPtr

currPtr

prevPtr

newPtr

D

F

G

NULL

NULL

C

NULL

startPtr

newPtr

prevPtr

G

currPtr

C

D

F

NULL

28

Algorytmy i struktury danych

3. Wstaw element na listę (cd.)

/* Wstaw element w miejsce mi

ę

dzy prevPtr a currPtr */

else

{

newPtr->next = currPtr;
prevPtr->next = newPtr;

}

}

return 0;

}

startPtr

A

B

D

C

29

Algorytmy i struktury danych

Algorytm dołączania elementu do listy jednokierunkowej – pełny kod

int insert (NodePtr *startPtr, char wstwart) {

struct Node *newPtr, *currPtr, *prevPtr;

int retcode=1;
/* Utwórz element Node */
newPtr = (struct Node *)malloc(sizeof(Node));
if (newPtr == NULL) /* weryfikacja przydzielonej pami

ę

ci*/

return 1;

else

{ /* Ustal dane elementarne w Node */

newPtr -> dane = wstwart;
newPtr -> next = NULL;

/* Zainicjowanie wska

ź

ników pomocniczych */

currPtr = startPtr; /* ustaw wska

ź

nik na głow

ę

listy */

prevPtr = NULL;
while ((currPtr != NULL) && (wstwart > currPtr->dane)) {

prevPtr = currPtr;

currPtr = currPtr -> next;

}

if (prevPtr == NULL) { /* Wstaw element jako pierwszy w li

ś

cie */

newPtr -> next = *startPtr;

*startPtr = newPtr;

}

else { /* Wstaw element w miejsce mi

ę

dzy prevPtr a currPtr */

newPtr->next = currPtr;

prevPtr->next = newPtr;

}

}

return 0;

}

30

Algorytmy i struktury danych

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej



Cel:



Usuni

ę

cie elementu z listy;



Dane wej

ś

ciowe:



Wska

ź

nik na pierwszy element listy startPtr;



Opis usuwanego elementu, np. warto

ść

danej elementarnej;

31

Algorytmy i struktury danych

Idea algorytmu usuwania elementu z uporządkowanej listy jednokierunkowej

A

startPtr

B

C

Przed
usuni

ę

ciem

elementu B:

A

startPtr

B

C

Po usuni

ę

ciu:

32

Algorytmy i struktury danych

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej

1. Znajd

ź

element do usuni

ę

cia na li

ś

cie;

2. Je

ż

eli nie znaleziono elementu, zwró

ć

kod bł

ę

du;

3. Usu

ń

znaleziony element z listy.

33

Algorytmy i struktury danych

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej



Je

ż

eli dane s

ą

zgodne z danymi pierwszego elementu listy

usu

ń

pierwszy element listy;

int delete (NodePtr *startPtr, char uswart)

{

Node *prevPtr, *currPtr, *tempPtr;

if (*startPtr == NULL)

/* Lista pusta */

return 1;

else
{

if (uswart == (*startPtr)->dane) /* Usu

ń

pierwszy element listy

*/

{

tempPtr = *startPtr;
*startPtr = (*startPtr)->next;
free (tempPtr);

}

34

Algorytmy i struktury danych

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej

...



Znajd

ź

element do usuni

ę

cia na li

ś

cie

:

…

else

{ /* znajd

ź

na li

ś

cie element do usuni

ę

cia */

prevPtr = *startPtr;

/* pocz

ą

tek listy */

currPtr = (*startPtr)->next;

/* drugi element*/

while (currPtr != NULL && currPtr -> dane != uswart)

{

prevPtr = currPtr;
currPtr = currPtr -> next;

}

35

Algorytmy i struktury danych

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej

...



Znajd

ź

element do usuni

ę

cia na li

ś

cie (cd.):



Je

ż

eli nie znaleziono elementu, zwró

ć

kod bł

ę

du



Usu

ń

znaleziony element;

…

if (currPtr == NULL)

return 1; /* element nie został znaleziony */

else

{ /* Usu

ń

znaleziony element */

tempPtr = currPtr;
prevPtr->next = currPtr->next;
free (tempPtr);
} } }

return 0;

}

36

Algorytmy i struktury danych

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej

int delete (NodePtr *startPtr, char uswart)

{ Node *prevPtr, *currPtr, *tempPtr;

if (*startPtr == NULL) /* Lista pusta */

return 1;

else {

if (uswart == (*startPtr)->dane) { /* Usu

ń

pierwszy element listy */

tempPtr = *startPtr;

*startPtr = (*startPtr)->next;

free (tempPtr);

}

else {/* znajd

ź

w li

ś

cie element do usuni

ę

cia */

prevPtr = *startPtr;

/* pocz

ą

tek listy */

currPtr = (*startPtr)->next;

/* drugi element*/

while (currPtr != NULL && currPtr -> dane != uswart) {

prevPtr = currPtr;

currPtr = currPtr -> next;

}
if (currPtr == NULL)

return 1; /* element nie został znaleziony */

else { /* Usu

ń

znaleziony element */

tempPtr = currPtr;

prevPtr->next = currPtr->next;

free (tempPtr);

}

}

}

return 0;

}

37

Algorytmy i struktury danych

Dołączanie elementu do uporządkowanej listy dwukierunkowej

Uwagi:



ka

ż

dy element posiada dodatkowe pole (wska

ź

nik) prev, który

dla pierwszego elementu listy jest równe NULL;



lista mo

ż

e by

ć

przegl

ą

dana w obydwu kierunkach;



cz

ę

sto pami

ę

ta si

ę

dowi

ą

zania do pierwszego i ostatniego

elementu;



nale

ż

y zawsze uaktualnia

ć

dowi

ą

zania w obydwu kierunkach;

Czy potrafisz dostosowa

ć

zaprezentowane algorytmy dla

list dwukierunkowych?

38

Algorytmy i struktury danych

Dołączanie elementu do uporządkowanej listy

jednokierunkowej cyklicznej

Uwagi:



brak dowi

ą

za

ń

wskazuj

ą

cych na NULL;



w li

ś

cie jednoelementowej dowi

ą

zania wskazuj

ą

na ten sam

element;



aby unikn

ąć

p

ę

tli niesko

ń

czonej podczas przegl

ą

dania listy,

mo

ż

na zastosowa

ć

wartownika – dowi

ą

zanie do pierwszego

elementu (umownego);

Czy potrafisz dostosowa

ć

zaprezentowane algorytmy

dla list cyklicznych?

39

Algorytmy i struktury danych