Witam Cię w pierwszej odsłonie cyklu wpisów dotyczących struktur danych. Założeniem serii jest wprowadzenie adeptów programowania w wszelkie hasła dotyczące struktur danych właśnie. Lista jednokierunkowa jest pierwszą strukturą do omówienia na mojej (nomen omen) liście :D. Przy okazji każdej struktury zaczynać będę od teoretycznego wprowadzenia, a kończąc na implementacji w języku C.
Czym jest struktura danych?
W możliwie największym uproszczeniu jest to rodzaj pojemnika na dane. Model przechowywania informacji. Jeśli planujesz zostać programistą, a na twojej liście rzeczy do nauczenia nie ma jeszcze struktur – dopisz je jak najprędzej 😉.
Dokonujemy podziału na struktury statyczne i dynamiczne. Główna różnica polega na sposobie przydzielania pamięci. Statyczne musza mieć z góry ustalony rozmiar. Natomiast przydział pamięci przy strukturach dynamicznych jest wykonywany w czasie realizacji programu. W pierwszej fazie serii zajmować będziemy się strukturami liniowymi, a pierwszą z nich będzie właśnie lista.
Struktura listy jednokierunkowej – koncepcja
Niejeden wczasowicz przed wyjazdem na urlop do Mielna tworzy spis niezbędnych mu nad morzem artefaktów – listę właśnie. Analogia nie jest przypadkowa. Po prostu powszechnie używane listy zakupów, rzeczy do zrobienia itd. to dobre przykłady do koncepcyjnego zrozumienia idei listy.
Podejrzewam, że każdy spośród moich czytelników zna pojęcie typu tablicowego. Jest to w równym stopniu struktura danych co lista, a skoro każdy potrafi posługiwać się tablicami to spróbujmy listę rzeczy do wzięcia na wakacje zapisać w tablicy.
Co nas ogranicza na samym początku? Ilość elementów. Przy deklarowaniu tablicy należy jawnie podać liczbę jej elementów, a nie zawsze ona jest z góry znana. Skąd mamy wiedzieć, ile rzeczy okaże się przydatnych na wakacjach? Można, by było zadeklarować na starcie dobrych 1000 elementów, ale nie dość, że to horrendalna strata pamięci to na dodatek nie mamy wcale gwarancji, że ktoś nie będzie chciał przekroczyć tej granicy. Więc zadeklarujmy tablicę o 5 elementach – tylu, ile potrzebujemy, aż tu nagle przypomniało nam się o czapce z daszkiem. Jak dodać czapkę do tablicy, skoro nie ma tam dla niej miejsca? A no właśnie! Nie da się tego zrobić w żaden znany mi efektywny sposób.
Kolejnym problemem jest kwestia usuwania elementów. Załóżmy, że jednak okazuje się, że w standardowym wyposażeniu pokoju w Mielnie znajdziemy czajnik. Super – nie musimy targać własnego i wykreślamy czajnik z naszej listy. No ale jeżeli element był w środku tablicy to przeszukując tablice po indeksach, bądź z wykorzystaniem wskaźników to próbując odwołać się do komórki pamięci z niegdysiejszym czajnikiem otrzymamy (w najlepszym przypadku) jakieś krzaki, a dodatkowo mamy nieużywaną pamięć.
Tablica okazuje się, więc wyjątkowo miernym rozwiązaniem. Skorzystamy z listy.
Lista jednokierunkowa – definicja i cechy
Lista jest strukturą danych, która wykorzystujemy, gdy mamy do czynienia z góry nieznaną ilością danych. Oczekuje się, że dane będą tego samego typu, ale wykorzystując unię można ograniczenie to pominąć. Każdy element listy – węzeł (ang. node) zawiera dwa pola. Jedno pole na daną i drugie zawierające wskaźnik na następny element, bez którego po prostu zgubilibyśmy następny element. Pierwszy element listy zwykło nazywać się głową (ang. head), a ostatni ogonem (ang. tail). Bystrzejszy czytelnik spyta: „na co wskazywać ma ogon listy, skoro nie ma po nim kolejnego elementu?”. Otóż wskaźnik ostatniego elementu wskazywać powinien na NULL.
Czym się charakteryzuje lista jednokierunkowa? W liście jednokierunkowej poruszamy się po elementach w (jak nazwa wskazuje) jednym kierunku. Od początku listy do jej końca. Co oznacza (i to jest dość istotna wada tego rozwiązania), że aby dostać się do przedostatniego elementu listy będziemy musieli przejść po kolei przez wszystkie węzły.
Lista jednokierunkowa – prosta implementacja w C
Obecnie w większości języków korzysta się z gotowych rozwiązań, dostarczających działające i udokumentowane struktury danych. Sam jestem zdania, że nie warto wymyślać koła od nowa i lepiej korzystać z gotowych i sprawdzonych bibliotek. Celem serii jest jednak pełne zrozumienie każdej struktury, aby móc w późniejszym czasie świadomie korzystać z ich dobrodziejstw. Nasza lista przechowywać będzie dane typu integer.
Zdefiniowanie struktury i stworzenie głowy
Każdy element listy przedstawiony będzie za pomocą typu strukturowego z dwoma polami. Pierwszym przechowującym daną i drugim wskazującym na kolejny element listy.
|
1 2 3 4 |
typedef struct ListElement { int data; struct ListElement * next; } ListElement_type; |
Stwórzmy na samym początku głowę listy, aby zilustrować jak działa alokowanie pamięci i jak dostać się do poszczególnych pól struktury.
|
1 2 3 |
ListElement_type *head; head = (ListElement_type *)malloc(sizeof(ListElement_type)); head=NULL; |
Lista jest dynamiczną strukturą danych, więc konieczne jest użycie wskaźników do skutecznego alokowania pamięci. W C w tym celu korzysta się z funkcji malloc(), której parametrem powinien być rozmiar jaki w pamięci komputera zajmuje jeden węzeł, a więc korzystamy z funkcji sizeof(), która zwróci rozmiar typu struktury podanej w argumencie.
Na samym początku lista powinna być pusta, więc head ustawimy na NULL. Równie dobrze moglibyśmy przypisać jakąś daną do głowy (np. 1). Chcąc dobrać się do pola w strukturze poprzez wskaźnik skorzystam z operatora strzałki „->” w sposób jaki widzimy poniżej.
|
1 2 |
head->data = 1; head->next = NULL; |
Dodawanie elementu na początku listy
Jak będziemy realizować to zagadnienie? Zaalokujemy pamięć dla nowego elementu, przypiszemy mu wartość, a jego pole next ustawimy na head. W końcu nowy węzeł będzie na liście przed głową. Argumentami funkcji będzie głowa oraz liczba, którą do listy będziemy chcieli dopisać.
|
1 2 3 4 5 6 7 8 9 10 11 |
void push_front(ListElement_type **head, int number) { ListElement_type *current; current=(ListElement_type *)malloc(sizeof(ListElement_type)); current->data=number; current->next=(*head); *head=current; } |
Ponieważ nowy element staje się automatycznie nową głową listy to musimy działać na oryginale heada. W tym celu skorzystam z podwójnego wskaźnika w argumencie.
Dodawanie elementy na końcu listy
Tutaj rozważymy dwa przypadki.
- Gdy head jest NULLem. Wtedy dodawany element będzie właściwie jedynym na naszej liście, a więc to head’a będziemy edytować.
- W przeciwnym razie tak jak poprzednio zaalokujemy pamięć, a następnie przejdziemy po całej liście, aby dostać się na jej koniec i tam dodać nasz element.
Tak jak wspominałem w liście jednokierunkowej musimy za każdym razem przechodzić od jej początku do końca. Problem ten rozwiewa lista dwukierunkowa, ale o niej opowiem wkrótce.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
void push_back(ListElement_type **head, int number) { if(*head==NULL) { *head = (ListElement_type *)malloc(sizeof(ListElement_type)); (*head)->data = number; (*head)->next = NULL; }else { ListElement_type *current=*head; while (current->next != NULL) { current = current->next; } current->next = (ListElement_type *)malloc(sizeof(ListElement_type)); current->next->data = number; current->next->next = NULL; } } |
Dostęp do elementów listy – na przykładzie wyświetlania zawartości i zliczania elementów
Wykorzystamy trik z poprzedniej funkcji. Funkcja będzie przechodzić po kolejnych elementach listy dopóki dany węzeł nie będzie wskazywać na NULL, czyli nie będzie to ostatni element – ogon.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
void show(ListElement_type *head) { printf("\n"); if(head==NULL) printf("List is empty"); else { ListElement_type *current=head; do { printf("%i", current->data); printf("\n"); current = current->next; }while (current != NULL); } } int list_size(ListElement_type *head) { int counter=0; if(head==NULL) return counter; else { ListElement_type *current=head; do { counter++; current = current->next; }while (current != NULL); } return counter; } |
Dodawanie elementu za pomocą indeksu
W tym momencie zaimplementowanie wymaganej funkcji może stanowić mały problem. Do rozpatrzenia mamy trzy przypadki:
- Gdy indeks wynosi 0 – wtedy skorzystamy z wcześniej zdefiniowanej przez nas funkcji push_front(),
- Gdy indeks równy jest liczbie elementów na liście – to tak jakbyśmy po prostu dodawali element na koniec listy. Użyjmy zatem push_back(),
- Gdy indeks znajduje się w środku listy. Wtedy, aby nie pogubić wskaźników skorzystać należy z dodatkowego elementu tymczasowego.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
void push_by_index(ListElement_type **head, int number, int position) { if(position==0) push_front(head, number); else { if(position==list_size(*head)) push_back(head, number); else { ListElement_type *current=*head; ListElement_type *tmp; int i=0; while (current->next != NULL && i<position-1) { current = current->next; i++; } tmp=current->next; current->next=(ListElement_type *)malloc(sizeof(ListElement_type)); current->next->data=number; current->next->next=tmp; } } } |
Usuwanie pierwszego elementu
Chcąc usunąć pierwszy element dokonujemy podmiany głowy. Element o indeksie zerowym – nasz head – zostanie usunięty, zwolnimy pamięć, którą zajmował, a element o dotychczasowym indeksie 1 zostanie nową głową listy.
|
1 2 3 4 5 6 7 8 9 10 11 |
void pop_front(ListElement_type **head) { ListElement_type * tmp=NULL; if (*head!=NULL) { tmp=(*head)->next; free(*head); *head=tmp; } } |
Usuwanie ostatniego elementu
Jeżeli lista jest jednoelementowa – mamy tylko głowę – to po prostu zwalniamy pamięć, którą zajmował head i lista jest pusta. W przeciwnym razie zwalniamy pamięć, którą zajmował ostatni element, a przedostatni od tego momentu powinien wskazywać na NULL. Staje się nowym ogonem.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
void pop_back(ListElement_type **head) { if((*head)->next==NULL) { *head=NULL; }else { ListElement_type *current=*head; while (current->next->next!= NULL) { current = current->next; } free(current->next); current->next=NULL; } } |
Usuwanie elementu o wybranym indeksie
W sytuacji, gdy będziemy chcieli usunąć element o indeksie skorzystam z funkcji pop_front(). W pozostałych przypadkach postępować będziemy według poniższej listy kroków:
- Poruszaj się po liście, aż do elementu poprzedzającego węzeł, który chcesz usunąć,
- Przechowaj element, który chcesz usunąć za pomocą tymczasowego elementu,
- Ustaw nastepnik elementu poprzedzającego węzeł, który chcesz usunąć, następnikiem tego elementu (z wykorzystaniem tymczasowego elementu),
- Zwolnij pamięć używająć tymczasowego elementu.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
void pop_by_index(ListElement_type **head, int position) { if(position==0) pop_front(head); else { ListElement_type *current=*head; ListElement_type *tmp; int i=0; while (current->next != NULL && i<position-1) { current=current->next; i++; } tmp = current->next; current->next = tmp->next; free(tmp); } } |
Podsumowanie
Z pewnością wkrótce na blogu pojawią się kolejne wpisy nawiązujące do tematyki struktur danych. Na liście jednokierunkowej się nie skończy, oj nie 😉 Temat dość łatwy do pojęcia, a w zawodzie nieoceniony.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 |
//Łukasz Kosiński - implementacja listy jednokierunkowej #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <windows.h> typedef struct ListElement { int data; struct ListElement * next; } ListElement_type; void show(ListElement_type *head); int list_size(ListElement_type *head); void push_front(ListElement_type **head, int number); void push_back(ListElement_type **head, int number); void push_by_index(ListElement_type **head, int number, int position); void pop_front(ListElement_type **head); void pop_back(ListElement_type **head); void pop_by_index(ListElement_type **head, int position); int main() { ListElement_type *head; head = (ListElement_type *)malloc(sizeof(ListElement_type)); head=NULL; int option=-1; int number=-1; int index=-1; while(option!=0) { system("cls"); printf("\nAktualny stan listy: "); show(head); printf("\n\nDrogi uzytkowniku! Co chcesz zrobic?\n"); printf("1. Dodac element na poczatek listy.\n"); printf("2. Dodac element na koniec listy.\n"); printf("3. Dodac element zgodnie z wybranym indeksem.\n"); printf("4. Usunac element z poczatku listy.\n"); printf("5. Usunac element z konca listy.\n"); printf("6. Usunac element o wybranym indeksie.\n"); printf("0. Zakonczyc program.\n"); scanf("%i", &option); switch (option) { case 0: return 0; break; case 1: printf("Wpisz liczbe jaka chcesz dodac: "); scanf("%i", &number); push_front(&head, number); break; case 2: printf("Wpisz liczbe jaka chcesz dodac: "); scanf("%i", &number); push_back(&head, number); break; case 3: printf("Wpisz liczbe jaka chcesz dodac: "); scanf("%i", &number); printf("Wpisz indeks: "); scanf("%i", &index); push_by_index(&head, number, index); break; case 4: pop_front(&head); break; case 5: pop_back(&head); break; case 6: printf("Wpisz indeks elementu, ktorego chcesz sie pozbyc raz na zawsze: "); scanf("%i", &index); pop_by_index(&head, index); break; default: printf("Podaj wlasciwa opcje."); Sleep(2000); break; } } return 0; } void push_front(ListElement_type **head, int number) { ListElement_type *current; current=(ListElement_type *)malloc(sizeof(ListElement_type)); current->data=number; current->next=(*head); *head=current; } void push_back(ListElement_type **head, int number) { if(*head==NULL) { *head = (ListElement_type *)malloc(sizeof(ListElement_type)); (*head)->data = number; (*head)->next = NULL; }else { ListElement_type *current=*head; while (current->next != NULL) { current = current->next; } current->next = (ListElement_type *)malloc(sizeof(ListElement_type)); current->next->data = number; current->next->next = NULL; } } void push_by_back(ListElement_type **head, int number, int position) { if(position==0) push_front(head, number); else { if(position==list_size(*head)) push_back(head, number); else { ListElement_type *current=*head; ListElement_type *tmp; int i=0; while (current->next != NULL && i<position-1) { current = current->next; i++; } tmp=current->next; current->next=(ListElement_type *)malloc(sizeof(ListElement_type)); current->next->data=number; current->next->next=tmp; } } } void pop_front(ListElement_type **head) { ListElement_type * tmp=NULL; if (*head!=NULL) { tmp=(*head)->next; free(*head); *head=tmp; } } void pop_back(ListElement_type **head) { if((*head)->next==NULL) { *head=NULL; }else { ListElement_type *current=*head; while (current->next->next!= NULL) { current = current->next; } free(current->next); current->next=NULL; } } void pop_by_index(ListElement_type **head, int position) { if(position==0) pop_front(head); else { ListElement_type *current=*head; ListElement_type *tmp; int i=0; while (current->next != NULL && i<position-1) { current=current->next; i++; } tmp = current->next; current->next = tmp->next; free(tmp); } } void show(ListElement_type *head) { printf("\n"); if(head==NULL) printf("List is empty"); else { ListElement_type *current=head; do { printf("%i", current->data); printf("\n"); current = current->next; }while (current != NULL);//może current->next??? } } int list_size(ListElement_type *head) { int counter=0; if(head==NULL) return counter; else { ListElement_type *current=head; do { counter++; current = current->next; }while (current != NULL); } return counter; } |
O wielu innych, równie ciekawych strukturach danych przeczytasz w tej książce:
Tynusz
says:A co jeśli chcemy mieć listę string’ów a nie int’ów?
admin
says:Widzę dwie opcje:
– zamieniasz typ składowej data w strukturze węzła listy na string i podobnie robisz z chociażby parametrami funkcji;
– korzystasz z szablonów. Jest to rozwiązanie o tyle dobre, że pozwala Ci napisać uniwersalną listę dla dowolnych typów danych. Listy dostępne w standardowej bibliotece języka zaimplementowane są właśnie z wykorzystaniem szablonów. Daj znać jeżeli chciałbyś przeczytać na binarnie.pl więcej na ten temat 🙂