AiSD W3

Algorytmy i struktury danych

Definicja struktury danych

Definicja

Struktur

danych nazywamy trójk

uporz

dkowan

S = (D, R, e)

gdzie:

– oznacza zbiór danych elementarnych

R={r

, 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

– jest elementem wej

ciowym do struktury danych S

(nie jest to element danych struktury danych S).

⊂

Algorytmy i struktury danych

Zbiór danych elementarnych

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

{

}

Algorytmy i struktury danych

Dane elementarne - zmienne programowe

Dane elementarna

poj

ciem abstrakcyjnym, rozumianym jako tzw.

„nazwana warto

ść

”. Jest ona okre

lana jako uporz

dkowana dwójka

elementów:

, gdzie:

– nazwa danej,

– 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

e przyjmowa

Algorytmy i struktury danych

Relacja

– 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

, natomiast drugim elementem jest jedna

z danych elementarnych ze zbioru

Element

„uczestnicz

cy” w relacji

nazywamy korzeniem struktury

danych S.

Struktura musi mie

zdefiniowany co najmniej jeden korze

Przykład:

li struktura S posiada dwa korzenie: d

oraz d

, to

{

}

⊂

Algorytmy i struktury danych

Relacja

– 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:

{

}

poprzednik

następnik

Algorytmy i struktury danych

Model grafowy struktury danych

Aby łatwiej zobrazowa

struktur

danych i w ten sposób lepiej j

zrozumie

na zbudowa

dla niej model grafowy. W modelu tym:

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:

{

}

{

}

{

}

liść

korzeń

Algorytmy i struktury danych

Podstawowe operacje na listach

Wyszukiwanie elementu na li

cie

Doł

czanie elementu do listy

Usuwanie elementu z listy

Przestawianie elementów na li

cie

Porz

dkowanie (sortowanie) listy

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)

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));

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

Algorytmy i struktury danych

Dynamiczne realizacje struktur listowych

Przykład:

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

startPtr

currPtr

prevPtr

newPtr

NULL

startPtr

currPtr

Warto

ść

szukana: C

currPtr: startPtr

currPtr -> dane: A

Algorytmy i struktury danych

startPtr

currPtr

prevPtr

newPtr

NULL

startPtr

Dynamiczne realizacje struktur listowych

Przykład (cd):

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

currPtr

Nazwa szukana: C

currPtr: currPtr -> next

currPtr -> dane: B

Algorytmy i struktury danych

startPtr

currPtr

prevPtr

newPtr

NULL

startPtr

Dynamiczne realizacje struktur listowych

Przykład (cd.)

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

currPtr

Nazwa szukana: C

currPtr: currPtr -> next

currPtr -> dane: C

Algorytmy i struktury danych

Algorytm dołączania elementu do uporządkowanej listy

jednokierunkowej

Cel:

Dodanie nowego elementu (z warto

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

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;

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

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

NULL

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

NULL

startPtr

newPtr

prevPtr

currPtr

NULL

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;

}

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;

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.

Algorytmy i struktury danych

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej

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);

}

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;

}

Algorytmy i struktury danych

Algorytm usuwania elementu z uporządkowanej listy jednokierunkowej

...

Znajd

element do usuni

cia na li

cie (cd.):

eli nie znaleziono elementu, zwró

kod bł

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;

}

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;

}

Algorytmy i struktury danych

Dołączanie elementu do uporządkowanej listy dwukierunkowej

Uwagi:

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;

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?

Algorytmy i struktury danych

Dołączanie elementu do uporządkowanej listy

jednokierunkowej cyklicznej

Uwagi:

brak dowi

wskazuj

cych na NULL;

w li

cie jednoelementowej dowi

zania wskazuj

na ten sam

element;

aby unikn

ąć

tli niesko

czonej podczas przegl

dania listy,

na zastosowa

wartownika – dowi

zanie do pierwszego

elementu (umownego);

Czy potrafisz dostosowa

zaprezentowane algorytmy

dla list cyklicznych?