Informatyka Stosowana, Wydział Inżynierii Metali i Informatyki Przemysłowej, Akademia Górniczo -Hutniczej im. Stanisława Staszica w Krakowie

Algorytmy i struktury danych, Barbara Barabasz – notatki z ćwiczeo – Wioletta Makuch

1
4

W

IZUALIZACJA LISTY

L – oznaczenie listy
a – pierwszy element listy, w tym wypadku 13
b – ostatni element listy, w tym wypadku 65
element: x – wartość danego danej pozycji np. dla pozycji 3, wartość wynosi 34
pozycja: p – pozycja danego elementu np. dla wartości 48, pozycja wynosi 4

W

IZUALNE DODAWANIE I USUWANIE ELEMENTÓW Z LISTY

U

SUWANIE ELEMENTU Z LISTY

1) Z listy usuwamy element 3

(p=3 , x=3)

2) Element 4

(p=4, x =4)

przesuwamy na puste mi ejsce 3

(p=3, x=0)

3) Teraz nasza lista ma tylko 3 elementy

(b=b-1)

D

ODAWANIE ELEMENTU DO LISTY

1) Mamy listę 3-elementową. Chc emy za 1 wstawić 5.
2) Przesuwamy od kooca wszystkie elementy o jedno miejsce tj. 4 na

miejsce za listą, 2 na miejsce 4.

3) W puste miejsce wkładamy 5.

I

MPLEMENTACJA TABLICOWA

Dla implementacji tablicowej pozycja



indeks/p, a element



tablica[indeks]/tablica[p].

(For array implementation position



i , element



array[i])

WSKAŹNIKI

ALGORYTM

Delete(p)

p



null;

q  p

q  p

Delete (p)

EFEKT ALGIRYTMU

p 

__ ______

p 

?

………….

p 

_ _

q

p 

_ _

q

p 

?

q

……….

KOMEN TARZ

Us uni ęcie wskaźnika powoduje usuni ęcie

elementu, który znajduje się pod danym

adresem. Sam ws kaźni k nadal istnieje.

Możemy zdefiniowa ć dwa zna czni ki

odwołujące si ę do tego samego miejs ca .

Us uwa jąc wska źnik p usuwamy element,

który zna jduje się pod tym adresem.

Ws kaźniki , które wskazywa ły na ten element

pozosta ją wtedy zupełnie pus te.

13

21

34

48

59

65

1

2

3

4

5

6

1)

1

2

3

4

2)

1

2

4

4

3)

1

2

4

1)

1

2

4

2)

1

2

2

4

4

3)

1

5

2

4

3

3

3

3

3

3

3

3

Informatyka Stosowana, Wydział Inżynierii Metali i Informatyki Przemysłowej, Akademia Górniczo -Hutniczej im. Stanisława Staszica w Krakowie

Algorytmy i struktury danych, Barbara Barabasz – notatki z ćwiczeo – Wioletta Makuch

2
4

WIZUALIZACJA

WSKAŹNIKÓW

TWORZENIE P USTEJ L ISTY

new (p)
p



null

Informatyka Stosowana, Wydział Inżynierii Metali i Informatyki Przemysłowej, Akademia Górniczo -Hutniczej im. Stanisława Staszica w Krakowie

Algorytmy i struktury danych, Barbara Barabasz – notatki z ćwiczeo – Wioletta Makuch

3
4

F

UNKCJE PODSTAWOWE

I

NSERT

(

ELEMENT

:

X

,

POZYCJA

:

P

,

L

ISTA

:

L)

–

WSTAWIANIE ELEMENTU X NA POZYCJĘ P W LIŚCIE

L

L ISTA

Insert (element: x, pozycja: p, Lista: L)
a



First (L);

while (a ≠ p) a



Next (a, L);

insert x;

TA BLICA

Insert (element: x, pozycja: p, Lista: L)
y



Endl(L)

while (y ≠

Next (p)

) {

L[y]



L[y-1];

y



Previous(y)

; }

L[p]



x;

b



b +1;

P

OZYCJA

:

L

OCATE

(

ELEMENT

:

X

;

L

ISTA

:

L)

–

POZYCJA ELEMENTU X NA LIŚCIE

L

L ISTA

Pozycja: Locate (element: x; Lista: L)
a



First (L)

while (

Retrieve(a, L)

≠ x) a



Next (a , L);

return a;

TA BLICA

Pozycja: Locate (element: x; Lista: L)
a



First (L)

while (L[i] ≠ x) i



Next (i, L);

return i;

E

LEMENT

:

R

ETRIEVE

(

POZYCJA

:

P

,

L

ISTA

:

L)

–

WARTOŚĆ ELEMENTU NA POZYCJI P W LIŚCIE

L

L ISTA

No code.

TA BLICA

Pozycja: Retrieve (pozycja: p, Lista: L)
return L[p];

D

ELETE

(

POZYCJA

:

P

,

L

ISTA

:

L)

–

USUWANIE ELEMENTU Z POZYCJI P NA LIŚCIE

L

L ISTA

No code.

TA BLICA

Delete (Pozycja: p, Lista: L)
while (p ≠ b) {

L[p]



L[p+1];

P



Next (p, L);

}

b=b-1;

P

OZYCJA

:

N

EXT

(

POZYCJA

:

P

,

L

ISTA

:

L)

–

NASTĘPNY ELEMENT PO POZYCJI P W LIŚCIE

L

L ISTA

No code.

TA BLICA

Pozycja: Nex t (pozycja: p, Lista: L)
return p+1;

P

OZYCJA

:

P

ERVIOUS

(

POZYCJA

:

P

,

L

ISTA

:

L)

–

POPRZEDNI ELEMENT PRZED POZYCJĄ P W LIŚCIE

L

L ISTA

Pozycja: Pervious (pozycja: p, Lista: L)
a



First (L)

while (

Next(a,L)

≠p) a



Next (a , L)

return a;

TA BLICA

Pozycja: Pervious (pozycja: p, Lista: L)
return p-1;

P

OZYCJA

:

F

IRST

(L

ISTA

:

L)

–

PIERWSZY ELEMENT NA LIŚCIE

L

L ISTA

Pozycja: First (Lista: L)
return a;

TA BLICA

No code.

P

OZYCJA

:

E

NDL

(L

ISTA

:

L)

–

ELEMENT ZA OSTATNIM ELEMENTEM W LIŚCIE

L

L ISTA

Pozycja: Endl (Lista: L)
return b+1;

TA BLICA

No code.

I

NIT

(L

ISTA

:

L)

–

INICJALIZACJA LISTY

L

L ISTA

Init (Lista: L)
a



0;

b



-1;

Informatyka Stosowana, Wydział Inżynierii Metali i Informatyki Przemysłowej, Akademia Górniczo -Hutniczej im. Stanisława Staszica w Krakowie

Algorytmy i struktury danych, Barbara Barabasz – notatki z ćwiczeo – Wioletta Makuch

4
4