Lista
dwukierunkowa
PODSTAWOWE INFORMACJE, INTERPRETACJA
GRAFICZNA, PODSTAWOWE OPERACJE, IMPLEMENTACJA
W JĘZYKU C ORAZ NAJCZĘŚCIEJ WYSTĘPUJĄCE ZADANIA
ZWIĄZANE Z LISTĄ DWUKIERUNKOWĄ
Łukasz Krupa,
2014
1
Lista
dwukierunkowa
PODSTAWOWE INFORMACJE, INTERPRETACJA
GRAFICZNA, PODSTAWOWE OPERACJE, IMPLEMENTACJA
W JĘZYKU C ORAZ NAJCZĘŚCIEJ WYSTĘPUJĄCE ZADANIA
ZWIĄZANE Z LISTĄ DWUKIERUNKOWĄ
Łukasz Krupa,
2014
1
2
Podstawowe informacje
Niezbędne informacje, związane z listą, były przedstawione w pierwszej prezentacji pod tytułem „Lista
jednokierunkowa”.
Lista dwukierunkowa jest rozszerzeniem listy jednokierunkowej. W liście jednokierunkowej każdy element
listy zawierał dwa pola – klucz oraz adres_nast. Widzimy więc, że możemy poruszać się tylko w jedną stronę,
ponieważ nie mamy adresu elementu, występującego przed elementem n-tym. W związku z tym należało
cały czas przechowywać adres głowy listy, ponieważ w przypadku przesunięcia głowy o n elementów,
nieodwracalnie gubimy adresy n wcześniejszych elementów.
Lista dwukierunkowa, prócz pól klucz oraz adres_nast, zawierała będzie jeszcze jedno pole – adres_poprz.
Pozwoli to poruszać się po liście w dowolnym kierunku, a do początku listy będziemy mogli dojść z każdego
elementu listy (co w przypadku listy jednokierunkowej było niemożliwe).
Zgodnie z tym, co zostało powiedziane przy okazji omawiania listy jednokierunkowej, zmienna wskaźnikowa,
wskazująca na adres elementu następnego, zajmuje w pamięci 4b miejsca. Wzrasta zatem koszt pamięciowy
utrzymania listy dwukierunkowej – z 8 bajtów (lista jednokierunkowa) do 12 bajtów (lista dwukierunkowa).
Łukasz Krupa,
2014
3
Łukasz Krupa,
2014
Interpretacja graficzna
Sposobów interpretacji graficznej listy dwukierunkowej jest taki sam, jak listy jednokierunkowej, z małym
rozszerzeniem o adres elementu poprzedniego.
Niech nasza lista przechowuje liczby całkowite (int). Zgodnie z tym, co zostało powiedziane w
wiadomościach wstępnych, lista zawiera daną, adres kolejnego elementu listy oraz adres wcześniejszego
elementu listy.
Niech pojedynczym elementem listy będzie kontener, zawierający trzy kieszenie – liczba, adres_nast oraz
adres_poprz:
Jak będzie wyglądać lista złożona z trzech elementów (kolejno) 3, 8, 15 ?
0xFB12
0
x
FA
4
1
Kolumna po lewo w każdym „kontenerze” to adres w pamięci, pod którym zapisany jest dany „kontener”.
3
NULL
0
x
FB
1
2
8
NULL
0
xF
F8
8
0xFF88
15
NULL
liczba
adres_nas
t
adres_pop
rz
NULL
NULL
NULL
0x
FA41
0xFB12
głowa
listy
ogon
listy
4
Łukasz Krupa,
2014
Podstawowe operacje –
dodawanie
Podstawowe operacje, związane z listą, ograniczają się do trzech – dodawania elementu do listy, usuwania
elementu z listy oraz wyszukiwania danego elementu w liście. Zajmijmy się pierwszą – dodawaniem.
Podczas dodawania należy rozpatrzyć dwa przypadki:
•
lista, do której dodajemy, jest pusta
•
lista zawiera przynajmniej jeden element
Umownie dodawać będziemy na początek listy, który stanowi ostatni dodany do listy element.
PRZYPADEK 1: lista nie istnieje (nie zawiera ani jednego elementu)
Dodajemy do pustej listy element o kluczu równym 5
0
x
9
6
C
4
5
NULL
Nowa głowa
listy
Adres nowego
elementu listy w
pamięci (przydzielany
dynamicznie)
Adres następnego
elementu listy
(NULL, bo lista była
pusta)
NULL
Adres poprzedniego
elementu listy
(NULL, bo lista była
pusta)
5
Łukasz Krupa,
2014
Podstawowe operacje –
dodawanie
PRZYPADEK 2: lista istnieje (zawiera przynajmniej jeden element)
Dodajemy na początek poniższej listy element o kluczu równym 9
0
x
9
6
C
4
5
0xA812
Głowa listy
0
xA
8
1
2
7
0
x
A
A
7
6
2
0xAA7
6
NULL
0
x1
3
3
D
9
0x96C4
nowa głowa
listy
Nową głową listy jest nowododany „kontener” z kluczem równym 9
Podczas implementacji funkcji dodawania do listy można połączyć oba przypadki w jeden – przy
odpowiednim przypisaniu adresu elementu poprzedniego oraz następnego w liście.
NULL
NULL
NULL
NULL
0xA812
0x96C4
0x133
D
NULL
6
Łukasz Krupa,
2014
Podstawowe operacje –
usuwanie
Usuwanie z listy, podobnie jak dodawanie, jest podstawową operacją dla list. Mówiliśmy już o
tym przy okazji przerabiania listy jednokierunkowej. Wartym zaznaczenia jest fakt, że
podstawowa operacja usuwania usuwa pierwszy napotkany element, zgodny z podanym
kluczem przeznaczonym do usunięcia.
Podczas usuwania należy rozpatrzyć trzy przypadki:
• lista, z której usuwamy, jest pusta
• lista zawiera element przeznaczony do usunięcia
• lista nie zawiera elementu przeznaczonego do usunięcia
PRZYPADEK 1: lista, z której usuwamy, nie istnieje (nie zawiera ani jednego elementu – jest
pusta)
W tym przypadku nie robimy nic. Wskaźnik na głowę listy jest pusty, czyli wynosi NULL.
7
Łukasz Krupa,
2014
Podstawowe operacje –
usuwanie
PRZYPADEK 2: lista zawiera element przeznaczony do usunięcia
W tym przypadku należy rozważyć, teoretycznie, trzy inne przypadki:
•
usuwany element jest głową listy
•
usuwany element znajduje się w środku listy
•
usuwany element jest ogonem listy
Dlaczego „teoretycznie” trzy? Otóż przypadek 2 i 3 przy odpowiedniej implementacji listy pokrywają się, tj. mogą zostać
obsłużone bez konieczności wyodrębniania obu przypadków. Dla zainteresowanych – przypadek 1 również można połączyć z 2 i
3, lecz na potrzeby lepszego zrozumienia algorytmów będziemy skupiać się na funkcji usuwania, rozróżniającej przypadek 1 od
2 i 3.
PRZYPADEK 2.1: element przeznaczony do usunięcia jest głową listy
Usuwany z poniższej listy element o kluczu 9
Głowa listy
Nowa głowa listy
Po usunięciu z listy elementu, który był jej głową, nową głową jest element, na którego adres wskazywał wskaźnik na następny element listy usuwanego elementu.
0
x
9
6
C
4
5
0xA812
0
x
A
8
1
2
7
0
x
A
A
7
6
2
0xAA7
6
NULL
0
x
1
3
3
D
9
0x96C4
NULL
NULL
NULL
NULL
0xA812
0x96C4
0x133
D
8
Łukasz Krupa,
2014
Podstawowe operacje –
usuwanie
PRZYPADEK 2.2: element usuwany znajduje się w środku listy
Usuwany z poniższej listy element o kluczu 7
Głowa listy
Po usunięciu z listy elementu, który był jej głową, nową głową jest element, na którego adres wskazywał wskaźnik na następny element
listy usuwanego elementu.
Tymczasowa głowa listy
9 != 7
5 != 7
7 == 7
Usuwany z poniższej listy element o kluczu 2
Głowa listy
PRZYPADEK 2.3: element przeznaczony do usunięcia znajduje się na końcu listy (jest ogonem)
Tymczasowa głowa listy
9 != 2
5 != 2
7 != 22 == 2
Po usunięciu elementu, który był ogonem listy, nowym ogonem staje się element poprzedzający elementu usunięty – jego pole adresu,
Wskazujące na kolejny element listy, zamieniane jest na NULL.
0
x
9
6
C
4
5
0xA812
0
xA
8
1
2
7
0
x
A
A
7
6
2
0xAA7
6
NULL
0
x
1
3
3
D
9
0x96C4
NULL
NULL
NULL
NULL
0xA812
0x96C4
0x133
D
0xAA7
6
0x96C4
0
x9
6
C
4
5
0xA812
0
x
A
8
1
2
7
0
x
A
A
7
6
2
0xAA7
6
NULL
0
x
1
3
3
D
9
0x96C4
NULL
NULL
NULL
NULL
0xA812
0x96C4
0x133
D
NULL
9
Łukasz Krupa,
2014
Podstawowe operacje –
usuwanie
PRZYPADEK 3: lista nie zawiera elementu przeznaczonego do usunięcia
Przypadek ten najczęściej łączony jest z przypadkiem 2. W przypadku listy nieposortowanej,
aby sprawdzić, czy lista nie zawiera żądanego elementu, należy każdorazowo przeszukać całą
listę.
W przypadku listy posortowanej, w pewnych przypadkach, nie ma potrzeby przechodzenia całej
listy by stwierdzić, że żądany element nie zawiera się w liście. Oczywiście, jest gro przypadków,
w których bez względu na to, czy lista jest posortowana, czy też nie – algorytm usuwania
przejdzie ją całą.
Usuwany z poniższej listy element o kluczu 10 (nie należącym do listy)
Głowa listy
Tymczasowa głowa
listy
9 != 10
5 != 10
7 != 10
2 != 10
Brak kolejnego
elementu
listy
KONIEC PRACY
ALGORYTMU
Lista nie zostanie zmodyfikowana, ponieważ żądany do usunięcia element nie zawierał się w
podanej liście.
0
x9
6
C
4
5
0xA812
0
x
A
8
1
2
7
0
x
A
A
7
6
2
0xAA7
6
NULL
0
x
1
3
3
D
9
0x96C4
NULL
NULL
NULL
NULL
0xA812
0x96C4
0x133
D
10
Łukasz Krupa,
2014
Podstawowe operacje –
wyszukiwanie
Ostatnią operacją podstawową, którą omówimy, będzie wyszukiwanie elementu w liście. Z
operacji wyszukiwania korzystaliśmy niejawnie podczas usuwania elementu z listy.
Wartym zaznaczenia jest fakt, że podstawowa operacja wyszukiwania zwraca adres
pierwszego napotkanego elementu, zgodny z podanym kluczem do wyszukania.
Podczas usuwania należy rozpatrzyć trzy przypadki:
• lista, którą przeszukujemy, jest pusta
• lista zawiera element szukany
• lista nie zawiera elementu szukanego
Ponieważ operację wyszukiwania wykorzystywaliśmy podczas operacji usuwania, nie będzie
ona omawiana osobno – wystarczy zapoznać się ze wspomnianą funkcją usuwania.
11
Łukasz Krupa,
2014
Implementacja w języku C
W tej części skupimy się już na programowaniu tego, o czym do tej pory mówiliśmy i co
rozważaliśmy.
Zaimplementowane zostaną funkcje:
• Dodaj do listy
• Usuń z listy
• Wyszukaj w liście
Ponieważ operować możemy na pojedynczym lub podwójnym wskaźniku, wszystkie wyżej
podane funkcje będą zaimplementowane w obu wersjach – z pojedynczym oraz z podwójnym
wskaźnikiem.
Funkcje implementowane będą w języku angielskim – wynika to z faktu, że większość kodów
dostępnych w internecie posługuje się anglojęzycznymi nazwami zmiennych i funkcji.
12
Łukasz Krupa,
2014
Implementacja w języku C -
dodawanie
Zdefiniujmy najpierw strukturę listy dwukierunkowej oraz zadeklarujmy alias dla naszej listy:
struct
list
{
int
key
;
struct
list
*
prev
,
*
next
;
};
typedef
struct
list list
;
Teraz możemy zaimplementować funkcję dodającą do listy, w oparciu o powyższą strukturę.
list
*
add
(
list
*
head
,
int
key
)
{
list
*
newHead
=
(
list
*)
malloc
(
sizeof
(
list
));
newHead
->
key
=
key
;
newHead
->
prev
=
NULL
;
newHead
->
next
=
head
;
if
(
head
)
head
->
prev
=
newHead
;
return
newHead
;
}
void
add
(
list
**
head
,
int
key
)
{
list
*
newHead
=
(
list
*)
malloc
(
sizeof
(
list
));
newHead
->
key
=
key
;
newHead
->
prev
=
NULL
;
newHead
->
next
=
*
head
;
if
(*
head
)
(*
head
)->
prev
=
newHead
;
*
head
=
newHead
;
}
dodaj przy użyciu pojedynczego wskaźnika:
dodaj przy użyciu podwójnego wskaźnika:
13
Łukasz Krupa,
2014
Implementacja w języku C -
usuwanie
Funkcja usuwająca element listy zwraca:
• W przypadku usunięcia elementu, który jest głową – przesunięcie głowy na kolejny element listy i
zwrócenie adresu nowej głowy
• W przypadku, gdy usuwamy element, będący jedynym elementem listy – NULL
• W przeciwnym przypadku – ten sam adres, który przekazywaliśmy do funkcji jako argument
Argumentami funkcji są: adres głowy listy oraz konkretna wartość, która ma zostać usunięta z listy.
Ponieważ funkcja usuwania zajmuje więcej linii niż dodawanie czy wyszukiwanie, została ona umieszczona
na osobnym slajdzie.
Zanim przejdziemy do części z kodem funkcji, sprawdźmy, jak wywoływać funkcję na pojedynczym i
podwójnym wskaźniku.
head
=
remove
(
head
,
10
);
list
**
phead
=
&
head
;
.
.
.
remove
(
phead
,
10
);
list
*
phead
=
NULL
;
.
.
.
remove
(&
head
,
10
);
wywołanie funkcji opartej o wskaźnik pojedynczy:
wywołanie funkcji opartej o wskaźnik podwójny:
14
Łukasz Krupa,
2014
Implementacja w języku C -
usuwanie
list
*
remove
(
list
*
head
,
int
key
)
{
if
(
head
)
{
list
*
tmpHead
=
head
;
while
(
tmpHead
&&
tmpHead
->
key
!=
key
)
tmpHead
=
tmpHead
->
next
;
if
(
tmpHead
)
{
if
(
tmpHead
==
head
)
head
=
head
->
next
;
list
*
trash
=
tmpHead
;
if
(
tmpHead
->
next
)
tmpHead
->
next
->
prev
=
tmpHead
->
prev
;
if
(
tmpHead
->
prev
)
tmpHead
->
prev
->
next
=
tmpHead
->
next
;
free
(
trash
);
}
}
return
head
;
}
void
remove
(
list
**
head
,
int
key
)
{
if
(*
head
)
{
list
*
tmpHead
=
*
head
;
while
(
tmpHead
&&
tmpHead
->
key
!=
key
)
tmpHead
=
tmpHead
->
next
;
if
(
tmpHead
)
{
if
(
tmpHead
==
*
head
)
*
head
=
(*
head
)->
next
;
list
*
trash
=
tmpHead
;
if
(
tmpHead
->
next
)
tmpHead
->
next
->
prev
=
tmpHead
->
prev
;
if
(
tmpHead
->
prev
)
tmpHead
->
prev
->
next
=
tmpHead
->
next
;
free
(
trash
);
}
}
}
usuń przy użyciu pojedynczego wskaźnika:
usuń przy użyciu podwójnego wskaźnika:
15
Łukasz Krupa,
2014
Implementacja w języku C -
przeszukanie
Funkcja przeszukująca listę zwraca:
• W przypadku znalezienia szukanego elementu – adres do pamięci, zawierający ten element
• NULL w przeciwnym wypadku
Argumentami funkcji są: adres głowy listy oraz konkretna wartość, którą ma zawierać zwracany adres do
komórki pamięci.
list
*
find
(
list
*
head
,
int
key
)
{
while
(
head
&&
head
->
key
!=
key
)
head
=
head
->
next
;
return
head
;
}
void
find
(
list
**
itemAddress
,
int
key
)
{
while
(*
itemAddress
&&
(*
itemAddress
)->
key
!=
key
)
*
itemAddress
=
(*
itemAddress
)->
next
;
}
wyszukaj przy użyciu pojedynczego wskaźnika:
wyszukaj przy użyciu podwójnego wskaźnika:
Skupmy się na chwilę na funkcji zbudowanej w oparciu o podwójny wskaźnik.
Przed jej wywołaniem w programie, należy zadeklarować stosowny wskaźnik oraz przypisać do wskaźnika wartość zmiennej
head, lub adres tej zmiennej (w zależności od tego, czy zechcemy działać od razu na podwójnym wskaźniku). Oto przykładowe
wywołania (funkcji zbudowanej w oparciu o podwójny wsk.):
list
**
itemAddress
=
&
head
;
find
(
itemAddress
,
10
);
list
*
itemAddress
=
head
;
find
(&
itemAddress
,
10
);
W obu przypadkach „10” jest elementem, który chcemy wyszukać w liście, a head jest zmienną wskaźnikową, przechowującą
adres bieżącej głowy listy.
16
Łukasz Krupa,
2014
Przykładowe zadania – zadanie 1
Przedstawione zostały do tej pory trzy funkcje, które tworzą niezbędne minimum, by móc posługiwać się
listą dwukierunkową.
Teraz skupimy się na zadaniach, które mogą pojawić się na kolokwiach czy egzaminach, a które ściśle
związane są z tematem list dwukierunkowych.
Zadanie 1
*
Dana jest posortowana lista dwukierunkowa określona przez poniższą strukturę. Napisz funkcję void removeDuplicates(struct list* head),
która usunie z listy wszystkie duplikaty. Na bazie napisanej funkcji napisz funkcję void removeDuplicates (struct list** head).
Przykład:
1 1 3 4 4 4 6 6 8 9 9
po usunięciu wszystkich duplikatów:
1 3 4 6 8 9
struct list
{
int key;
struct list *prev, *next;
};
Najpierw stwórzmy alias dla naszej listy, ponieważ dość irytujące jest ciągłe wpisywanie struct lista w
funkcje.
typedef
struct
list list
;
Rozwiązanie zadania zamieszczone na kolejnym slajdzie.
17
Łukasz Krupa,
2014
Przykładowe zadania – zadanie 1
void
removeDuplicates
(
list
*
head
)
{
if
(
head
)
{
list
*
tmpHead
=
head
;
while
(
tmpHead
)
{
list
*
tmp
=
tmpHead
->
next
;
while
(
tmp
&&
tmp
->
key
==
tmpHead
->
key
)
{
list
*
trash
=
tmp
;
tmp
->
prev
->
next
=
tmp
->
next
;
if
(
tmp
->
next
)
tmp
->
next
->
prev
=
tmp
->
prev
;
tmp
=
tmp
->
next
;
free
(
trash
);
}
tmpHead
=
tmpHead
->
next
;
}
}
}
void
removeDuplicates
(
list
**
head
)
{
if
(*
head
)
{
list
*
tmpHead
=
*
head
;
while
(
tmpHead
)
{
list
*
tmp
=
tmpHead
->
next
;
while
(
tmp
&&
tmp
->
key
==
tmpHead
->
key
)
{
list
*
trash
=
tmp
;
tmp
->
prev
->
next
=
tmp
->
next
;
if
(
tmp
->
next
)
tmp
->
next
->
prev
=
tmp
->
prev
;
tmp
=
tmp
->
next
;
free
(
trash
);
}
tmpHead
=
tmpHead
->
next
;
}
}
}
removeDuplicates przy użyciu pojedynczego
wskaźnika:
removeDuplicates przy użyciu podwójnego
wskaźnika:
18
Łukasz Krupa,
2014
Przykładowe zadania – zadanie 2
Zadanie 2
Dana jest lista dwukierunkowa określona przez poniższą strukturę. Napisz funkcję struct list* rotateRight(list* head, int position), dokona
obrotu logicznego listy o position miejsc w prawo. Na postawie napisanej funkcji napisz funkcję void rotateRight(list** head, int
position), przy użyciu podwójnego wskaźnika.
Przykład:
2 8 9 6 1 4
obrót o 2 pozycje:
1 4 2 8 9 6
struct list
{
int key;
struct list *prev, *next;
};
Ponieważ rozwiązanie zadania jest złożone, zatem najpierw zostanie przedstawione na przykładzie.
Niech dana będzie lista jak poniżej, a wartość position wynosi 2.
0
x
9
6
C
4
5
0xA812
0
xA
8
1
2
7
0
xA
A
7
6
2
0xAA7
6
NULL
0
x1
3
3
D
9
0x96C4
NULL
NULL
NULL
NULL
0xA812
0x96C4
0x133
D
NULL
Głowa listy
Tymczasowa głowa
listy
Licznik
elementów = 0
Licznik
elementów = 1
Licznik
elementów = 2
Licznik
elementów = 3
Licznik
elementów = 4
0x133
D
0xAA7
6
Powstała lista
cykliczna
Position = 2
STOP!
Position = 1
Position = 0
STO
P!
NULL
NULL
Nowa głowa
listy
Po wykonaniu funkcji, lista będzie rozpoczynała się elementem 7, a kończyła 5. Będzie miała kolejność: 7 2 9
5.
19
Łukasz Krupa,
2014
Przykładowe zadania – zadanie 2
list
*
rotateRight
(
list
*
head
,
int
position
)
{
if
(
head
&&
position
>
0
)
{
int
lengthOfList
=
0
,
guard
=
1
;
list
*
tmpHead
=
head
;
while
(
guard
)
{
if
(!
tmpHead
->
next
)
{
tmpHead
->
next
=
head
;
head
->
prev
=
tmpHead
;
guard
=
0
;
}
lengthOfList
++;
tmpHead = tmpHead
->
next
;
}
int
rotNumber
=
position
%
lengthOfList
;
while
(
rotNumber
--)
head
=
head
->
prev
;
head
->
prev
->
next
=
NULL
;
head
->
prev
=
NULL
;
}
return
head
;
}
void
rotateRight
(
list
**
head
,
int
position
)
{
if
(*
head
&&
position
>
0
)
{
int
lengthOfList
=
0
,
guard
=
1
;
list
*
tmpHead
=
*
head
;
while
(
guard
)
{
if
(!
tmpHead
->
next
)
{
tmpHead
->
next
=
*
head
;
(*
head
)->
prev
=
tmpHead
;
guard
=
0
;
}
lengthOfList
++;
tmpHead
=
tmpHead
->
next
;
}
int
rotNumber
=
position
%
lengthOfList
;
while
(
rotNumber
--)
*
head
=
(*
head
)->
prev
;
(*
head
)->
prev
->
next
=
NULL
;
(*
head
)->
prev
=
NULL
;
}
}
rotateRight przy użyciu pojedynczego wskaźnika:
rotateRight przy użyciu podwójnego wskaźnika:
20
Łukasz Krupa,
2014
Przykładowe zadania – zadanie 3
Zadanie 3
Dana jest lista dwukierunkowa określona przez poniższą strukturę. Napisz funkcję int showList(struct list* head), która wyświetli wszystkie
elementy listy i zwróci jej długość. Na podstawowie napisanej funkcji, napisz funkcję int showList(list** head).
Przykład:
2 8 9
Po wykonaniu funkcji showList:
2 8 9, dlugosc: 3
struct list
{
int key;
struct list *prev, *next;
};
typedef
struct
list list
;
Najpierw stwórzmy alias dla naszej listy, ponieważ dość irytujące jest ciągłe wpisywanie struct lista w
funkcje.
int
showList
(
list
*
head
,
int
key
)
{
int
counter
=
0
;
while
(
head
)
{
printf
(
”
%d
”
,
head
->
key
);
head
=
head
->
next
;
counter
++;
}
return
counter
;
}
int
showList
(
list
**
head
,
int
key
)
{
int
counter
=
0
;
list
*
tmpHead
=
*
head
;
while
(
tmpHead
)
{
printf
(
”
%d
”
,
tmpHead
->
key
);
tmpHead
=
tmpHead
->
next
;
counter
++;
}
return
counter
;
}
showList przy użyciu pojedynczego wskaźnika:
wyszukaj przy użyciu podwójnego wskaźnika:
21
Podsumowanie
Materiał o listach jednokierunkowych, jak i dwukierunkowych, został przedstawiony w dwóch
dotychczasowych prezentacjach.
Dzięki znajomości przedstawionych zagadnień można bez problemu zabrać się za, np. Implementację
grafów, algorytmy ich przeszukiwań czy algorytm przechodzenia drzewa w porządku in level. Wszędzie tam
wykorzystywane są listy, zarówno jedno-, jak i dwukierunkowe.
Dalsze omawiane tematy będą w bardzo dużym stopniu korzystać z materiału już omówionego, zatem jeżeli
czujesz, że nie do końca przyswoiłeś wszystko, co zostało do tej pory przedstawione, cofnij się do
krytycznego momentu i prześledź przedstawione Ci materiały jeszcze raz. Zrozumienie list (pełne
zrozumienie, a nie wyuczenie się gotowych funkcji na pamięć) to klucz do zrozumienia np. implementacji
grafów, ponieważ bazuje ona na liście jedno- i dwukierunkowej (jako, odpowiednio – lista krawędzi danego
wierzchołka i lista wierzchołków grafu).
Również tablice z hashowaniem będą realizowane nie tylko na tablicy (alokowanej dynamicznie rzecz jasna),
ale także będą realizowane przy użyciu list.
Łukasz Krupa,
2014
22
Autor: Łukasz Krupa
lukasz_krupa@gazeta.pl
Łukasz Krupa,
2014
Autor zezwala na kopiowanie i rozpowszechnianie powyższej
pracy, pod warunkiem zachowania informacji o oryginalnym
autorze niniejszej prezentacji.