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