Lista
jednokierunkowa
PODSTAWOWE INFORMACJE, LISTA A TABLICA, INTERPRETACJA
GRAFICZNA, PODSTAWOWE OPERACJE, IMPLEMENTACJA W
JĘZYKU C ORAZ NAJCZĘŚCIEJ WYSTĘPUJĄCE ZADANIA
ZWIĄZANE Z LISTĄ JEDNOKIERUNKOWĄ
Łukasz Krupa,
2014
1
2
Podstawowe informacje
LISTA - struktura danych służąca do reprezentacji zbiorów dynamicznych, w której
elementy ułożone są w liniowym porządku.
Stosuje się je do reprezentacji w pamięci komputera danych sekwencyjnych -
grafów, kolejek, stosów.
Implementacja listy zarządzanej dynamicznie opiera się o specjalny typ danych,
zwany strukturą, oraz dynamicznie alokowaną pamięć.
By swobodnie móc poruszać się w świecie nie tylko list, ale ogólnie rzecz ujmując
dynamicznych struktur danych, niezbędne jest opanowanie wskaźników
(pojedynczych, a w niektórych przypadkach – także podwójnych).
W pewnych przypadkach, alternatywą dla listy jest tablica.
Łukasz Krupa,
2014
3
Łukasz Krupa,
2014
Lista a tablica - porównanie
Podstawową wadą tablicy jest jej zapis w pamięci komputera – jako zwarty, n-elementowy blok danych. Co
to oznacza?
Załóżmy, że mamy tablicę liczb całkowitych (int) o rozmiarze n równym 1 000 000. Ponieważ pojedynczy int
zajmuje w pamięci dokładnie 4 bajty, tablica będzie zajmowała rozmiar 4 000 000 bajtów, co daje w
przybliżeniu 3906 kB, a to równa się (również w przybliżeniu) 3,82 MB. Aby tablica została zaalokowana,
program musi znaleźć w pamięci wolny blok o rozmiarze 3,82 MB. Jeżeli takiego bloku nie znajdzie, zwraca
komunikat o błędzie i kończy swoje działanie.
W dobie 4, 8 czy nawet 16 GB pamięci RAM wydaje się nie być to problemem, lecz jeszcze u progu XXI wieku
był to problem całkowicie realny.
Załóżmy, że chcemy zamiast tablicy użyć listy jednokierunkowej, również o rozmiarze n-elementowym
równym 1 000 000. Całkowity rozmiar listy będzie równał się w tym przypadku 8 000 000 bajty (ponieważ
każdy element listy będzie zajmował nie 4 bajty (sam int), lecz 8 bajtów (int – 4b - oraz wskaźnik na kolejny
element listy – kolejne 4b)). W pamięci komputera natomiast, zamiast zwartego bloku zajmującego ~ 7,64
MB, elementy listy będą po niej porozrzucane, zajmując kolejne wolne miejsca pamięci.
„Skoro będą porozrzucane po całej pamięci, to w jaki sposób będę mógł dostać się do konkretnego
elementu?”
Głowa listy zawsze wskazuje na jej pierwszy element – adres każdego kolejnego elementu zapisany jest w
odpowiednim polu (wskażniku) elementu poprzedniego. Pozwala to przechodzić całą listę, bez utraty
jakichkolwiek danych.
4
Łukasz Krupa,
2014
Lista a tablica - porównanie
Kolejną wadą tablicy jest sposób dodawania elementów do tablicy już zapełnionej. Załóżmy, że chcemy
dodać w środek tablicy jakąś wartość. Mamy dwa wyjścia:
• Realokować pamięć przy użyciu funkcji void *realloc(void *ptr, size_t size)
• Zaalokować pamięć o rozmiarze równym n+1 (funkcja void *malloc), przepisując starą tablicę z
uwzględnieniem nowego elementu
Oba są czasochłonne, co przy częstym wywoływaniu, może powodować zauważalne zmniejszenie szybkości
działania programu.
W przypadku listy, aby wstawić element w dowolne miejsce, należy przejść (przy pomocy adresów) do
elementu, za którym chcemy wstawić nowy element w listę, zaalokować pamięć równą rozmiarowi jednego
elementu listy i przypisać adres nowozaalokowanej pamięci do pola adresowego, wskazującego na element
następny w liście, elementu za którym wstawiamy nowy element listy. Wcześniej natomiast należy przypisać
do pola adresowego (wskazującego na następny element) elementu nowo dodawanego wartość zawartą w
tym samym polu elementu, za który wstawiamy nowy element – dzięki temu nie utracimy dalszej części
listy.
Brzmi skomplikowanie? Trochę tak, szczególnie dla osób, które nigdy wcześniej nie miały z tym styczności. W
dalszych slajdach zawarta jest animacja, przedstawiająca operację dodawania elementu w listę (na
początek, w środek i na koniec).
5
Łukasz Krupa,
2014
Lista a tablica - porównanie
Zaletą tablicy, a zarazem wadą listy jest czas dostępu do n-tego elementu.
W przypadku tablicy, dostęp do dowolnego elementu jest natychmiastowy – bez różnicy, czy
element jest elementem pierwszym, ostatnim czy środkowym. Dostęp do elementu tablicy o
nazwie tablica i indeksie n uzyskujemy poprzez tablica[n].
W przypadku listy, dostęp do elementu pierwszego jest również natychmiastowy. Nastomiast
dostęp do każdego kolejnego elementu jest sumą czasów dostępów do elementów poprzednich,
wg wzoru:
gdzie: – czas dostępu do n-tego elementu listy
6
Łukasz Krupa,
2014
Interpretacja graficzna
Sposobów interpretacji graficznej listy jest taki wiele, jak wiele jest sposobów na jej zrozumienie.
Poniżej przedstawiona jest ta najczęściej spotykaną – wydaje się być też najbardziej intuicyjna.
Niech nasza lista przechowuje liczby całkowite (int). Zgodnie z tym, co zostało powiedziane w
wiadomościach wstępnych, lista zawiera daną oraz adres kolejnego elementu listy.
Niech pojedynczym elementem listy będzie kontener, zawierający dwie kieszenie – liczba oraz adres_nast:
liczba
adres_na
st
Jak będzie wyglądać lista złożona z trzech elementów (kolejno) 3, 8, 15 ?
0xFB12
0
x
F
A
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
F
8
8
0xFF88
15
NULL
7
Ł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)
8
Ł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
x
A
8
1
2
7
0
x
A
A
7
6
2
0xAA7
6
NULL
0
x
1
3
3
D
9
0x
96C4
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 następnego w liście (będzie o tym mowa w części z
implementacją w C).
9
Łukasz Krupa,
2014
Podstawowe operacje –
usuwanie
Usuwanie z listy, podobnie jak dodawanie, jest podstawową operacją dla list. Jednak w
porównaniu do tej pierwszej, implementacja zajmuje trochę więcej czasu. 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.
10
Ł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.
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
0x
96C4
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.
11
Łukasz Krupa,
2014
Podstawowe operacje –
usuwanie
PRZYPADEK 2.2: element usuwany znajduje się w środku listy
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
0x
96C4
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
0xAA7
6
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
0x
96C4
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
NULL
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.
12
Ł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łą.
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
0x
96C4
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.
13
Ł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.
14
Ł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
• Wyświetl listę
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.
15
Łukasz Krupa,
2014
Implementacja w języku C -
dodawanie
Zdefiniujmy najpierw strukturę listy jednokierunkowej oraz zadeklarujmy alias dla naszej listy:
struct
list
{
int
key
;
struct
list
*
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
->
next
=
head
;
return
newHead
;
}
void
add
(
list
**
head
,
int
key
)
{
list
*
newHead
=
(
list
*)
malloc
(
sizeof
(
list
));
newHead
->
key
=
key
;
newHead
->
next
=
*
head
;
*
head
=
newHead
;
}
dodaj przy użyciu pojedynczego wskaźnika:
dodaj przy użyciu podwójnego wskaźnika:
16
Ł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
**
head
=
NULL
;
.
.
.
remove
(
head
,
10
);
list
*
head
=
NULL
;
.
.
.
remove
(&
head
,
10
);
wywołanie funkcji opartej o wskaźnik pojedynczy:
wywołanie funkcji opartej o wskaźnik podwójny:
17
Łukasz Krupa,
2014
Implementacja w języku C -
usuwanie
list
*
remove
(
list
*
head
,
int
key
)
{
if
(
head
)
{
if
(
head
->
key
==
key
)
{
list
*
trash
=
head
;
head
=
head
->
next
;
free
(
trash
);
}
else
{
list
*
tmpHead
=
head
;
while
(
tmpHead
->
next
&&
tmpHead
->
next
->
key
!=
key
)
tmpHead
=
tmpHead
->
next
;
if
(
tmpHead
->
next
)
{
list
*
trash
=
tmpHead
->
next
;
tmpHead
->
next
=
tmpHead
->
next
->
next
;
free
(
trash
);
}
}
}
return
head
;
}
void
remove
(
list
**
head
,
int
key
)
{
if
(*
head
)
{
if
((*
head
)->
key
==
key
)
{
list
*
trash
= *
head
;
*
head
=
(*
head
)->
next
;
free
(
trash
);
}
else
{
list
*
tmpHead
=
*
head
;
while
(
tmpHead
->
next
&&
tmpHead
->
next
->
key
!=
key
)
tmpHead
=
tmpHead
->
next
;
if
(
tmpHead
->
next
)
{
list
*
trash
=
tmpHead
->
next
;
tmpHead
->
next
=
tmpHead
->
next
->
next
;
free
(
trash
);
}
}
}
}
usuń przy użyciu pojedynczego wskaźnika:
usuń przy użyciu podwójnego wskaźnika:
18
Ł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.
19
Ł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 korzystać z listy
jednokierunkowej.
Teraz skupimy się na zadaniach, które mogą pojawić się na kolokwiach czy egzaminach, a które ściśle
związane są z listami jednokierunkowymi.
Zadanie 1
Dana jest lista jednokierunkowa określona przez poniższą strukturę. Napisz funkcję struct list* addTail(struct list* head, int key), która
dodaje element na koniec listy. Na bazie napisanej funkcji napisz funkcję void addTail(struct list** head, int key).
Przykład:
2 8 9
po dodaniu 1:
3 8 9 1
struct list
{
int key;
struct list *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.
20
Łukasz Krupa,
2014
Przykładowe zadania – zadanie 1
list
*
addTail
(
list
*
head
,
int
key
)
{
if
(
head
)
{
list
*
tmpHead
=
head
;
while
(
tmpHead
->
next
)
tmpHead
=
tmpHead
->
next
;
list
*
newTail
=
(
list
*)
malloc
(
sizeof
(
list
));
newTail-
>
key
=
key
;
newTail-
>
next
=
tmpHead-
>
next
;
tmpHead
->
next
=
newTail
;
}
else
{
list
*
newHead
=
(
list
*)
malloc
(
sizeof
(
list
));
newHead
->
key
=
key
;
newHead
->
next
=
head
;
head
=
newHead
;
}
return
head
;
}
void
addTail
(
list
**
head
,
int
key
)
{
if
(*
head
)
{
list
*
tmpHead
=
*
head
;
while
(
tmpHead
->
next
)
tmpHead
=
tmpHead
->
next
;
list
*
newTail
=
(
list
*)
malloc
(
sizeof
(
list
));
newTail-
>
key
=
key
;
newTail-
>
next
=
tmpHead-
>
next
;
tmpHead
->
next
=
newTail
;
}
else
{
list
*
newHead
=
(
list
*)
malloc
(
sizeof
(
list
));
newHead
->
key
=
key
;
newHead
->
next
=
*
head
;
*
head
=
newHead
;
}
}
addTail przy użyciu pojedynczego wskaźnika:
addTail przy użyciu podwójnego wskaźnika:
21
Łukasz Krupa,
2014
Przykładowe zadania – zadanie 2
Zadanie 2
Dana jest lista jednokierunkowa określona przez poniższą strukturę. Napisz funkcję int lengthOfList(struct list* head), która zwróci ilość
elementów w liście.
Przykład:
2 8 9 zwróci 3
struct list
{
int key;
struct list *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
;
int
lengthOfList
(
list
*
head
)
{
int
length
=
0
;
while
(
head
)
{
head
=
head
->
next
;
length
++;
}
return
length
;
}
int
lengthOfList
(
list
**
head
)
{
list
*
tmpHead
= *
head
;
int
length
=
0
;
while
(
tmpHead
)
{
tmpHead
=
tmpHead
->
next
;
length
++;
}
return
length
;
}
lengthOfList przy użyciu pojedynczego wskaźnika:
lengthOfList przy użyciu podwójnego wskaźnika:
22
Łukasz Krupa,
2014
Przykładowe zadania – zadanie 3
Zadanie 3
Dana jest posortowana niemalejąco lista jednokierunkowa określona przez poniższą strukturę. Napisz funkcję struct list*
addMissingElements(struct list** head), która będzie uzupełniała listę o brakujące elementy pomiędzy pierwszym a ostatnim elementem
listy. Na podstawowie napisanej funkcji, napisz funkcję void addMissingElements(struct list** head).
Przykład:
2 8 9
Po wykonaniu funkcji addMissingElements:
2 3 4 5 6 7 8 9
struct list
{
int key;
struct list *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.
Rozwiązanie zadania zamieszczone na kolejnym slajdzie.
UWAGA!
Funkcja, zaproponowana jako rozwiązanie, korzysta z funkcji podstawowej funkcji dodaj, która została
dokładnie omawiana w slajdach 15 oraz 16. Zamiast dodaj używana jest nazwa add.
23
Łukasz Krupa,
2014
Przykładowe zadania – zadanie 3
list
*
addMissingElements
(
list
*
head
)
{
list
*
tmpHead
=
head
;
int
counter
=
0
;
while
(
tmpHead
&&
tmpHead
->
next
)
{
list
*
nextItemAddress
=
tmpHead
->
next
;
counter
=
tmpHead
->
next
->
key
-
tmpHead
->
key
;
if
(
counter
>
1
)
{
while
(
counter
!=
1
)
{
tmpHead
->
next
=
add
(
tmpHead
->
next
,
tmpHead
->
key
+
counter
-
1
);
counter
--;
}
}
tmpHead
=
nextItemAddress
;
}
return
head
;
}
void
addMissingElements
(
list
**
head
)
{
list
*
tmpHead
=
*
head
;
int
counter
=
0
;
while
(
tmpHead
&&
tmpHead
->
next
)
{
list
*
nextItemAddress
=
tmpHead
->
next
;
counter
=
tmpHead
->
next
->
key
-
tmpHead
->
key
;
if
(
counter
>
1
)
{
while
(
counter
!=
1
)
{
tmpHead
->
next
=
add
(
tmpHead
->
next
,
tmpHead
->
key
+
counter
-
1
);
counter
--;
}
}
tmpHead
=
nextItemAddress
;
}
}
addMissingElements przy użyciu pojedynczego
wskaźnika:
addMissingElements przy użyciu podwójnego
wskaźnika:
24
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.
Document Outline
- Slide 1
- Slide 2
- Slide 3
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Slide 8
- Slide 9
- Slide 10
- Slide 11
- Slide 12
- Slide 13
- Slide 14
- Slide 15
- Slide 16
- Slide 17
- Slide 18
- Slide 19
- Slide 20
- Slide 21
- Slide 22
- Slide 23
- Slide 24
Wyszukiwarka
Podobne podstrony:
lista jednokierunkowa
lista jednokierunkowa
Lista jednokierunkowa zamiana kolejności
organizmy jednokomórkowe są różnorodne
Lista 2012 2
Polecenia lista 5
macierze i wyznaczniki lista nr Nieznany
Lista 14
Analiza matematyczna, lista analiza 2008 6 szeregi
Analiza III semestr lista nr 3 Nieznany (2)
lista produktow
podstawy automatyki ćwiczenia lista nr 4b
lista parafraz modu A
Lista watykańskich masonów
Lista czesci
eksploracja lab03, Lista sprawozdaniowych bazy danych
lista przed zabr id 270172 Nieznany
analiza sem 2 lista nr5 id 6134 Nieznany (2)
więcej podobnych podstron