Przejdź do zawartości

C/Typy złożone

Z Wikibooks, biblioteki wolnych podręczników.
< C

typedef

[edytuj]

Jest to słowo kluczowe, które służy do definiowania typów pochodnych np.:

 typedef stara_nazwa  nowa_nazwa;
 typedef int mojInt;
 typedef int* WskNaInt;

od tej pory można używać typów mojInt i WskNaInt.

Często używa się typedef w jednej instrukcji razem z definicją typu

Typ wyliczeniowy

[edytuj]

Służy do tworzenia zmiennych, które mogą przyjmować tylko pewne z góry ustalone wartości:

 enum Nazwa {WARTOSC_1, WARTOSC_2, WARTOSC_N };

Na przykład można w ten sposób stworzyć zmienną przechowującą kierunek:

 enum Kierunek {W_GORE, W_DOL, W_LEWO, W_PRAWO};
   
 enum Kierunek ruch = W_GORE;

Gdzie "Kierunek" to typ zmiennej, wcześniej określony, a "ruch" nazwa zmiennej, o takim typie. Zmienną tę można teraz wykorzystać na przykład w instrukcji switch

 switch(ruch)
 {
   case W_GORE:
     printf("w górę\n");
     break;
   case W_DOL:
     printf("w dół\n");
     break;
   default:
     printf("gdzieś w bok\n");
 }

Tradycyjnie przechowywane wielkości zapisuje się wielkimi literami (W_GORE, W_DOL).

Tak naprawdę C przechowuje wartości typu wyliczeniowego jako liczby całkowite (zakres typu signed int), o czym można się łatwo przekonać:

 ruch = W_DOL;
 printf("%i\n", ruch); /* wypisze 1 */

Kolejne wartości to po prostu liczby całkowite: domyślnie pierwsza to zero, druga jeden itp. Możemy przy deklarowaniu typu wyliczeniowego zmienić domyślne przyporządkowanie:

 enum Kierunek { W_GORE, W_DOL = 8, W_LEWO, W_PRAWO };
 printf("%i %i\n", W_DOL, W_LEWO); /* wypisze 8 9 */

Co więcej liczby mogą się powtarzać i wcale nie muszą być ustawione w kolejności rosnącej:

 enum Kierunek { W_GORE = 5, W_DOL = 5, W_LEWO = 2, W_PRAWO = -1 };
 printf("%i %i\n", W_DOL, W_LEWO); /* wypisze 5 2 */

Traktowanie przez kompilator typu wyliczeniowego jako liczby pozwala na wydajną ich obsługę, ale stwarza niebezpieczeństwa:

Można przypisywać pod typ wyliczeniowy liczby, nawet nie mające odpowiednika w wartościach, a kompilator może o tym nawet nie ostrzec:

 ruch = 40;

Lub przypisać pod typ wyliczeniowy, np. liczby:

 enum Kierunek { W_GORE, W_DOL, W_LEWO = -1, W_PRAWO };

Co spowoduje nadanie tej samej wartości 0 dla elementów W_GORE i W_PRAWO, a to może skutkować błędem kompilacji, np. w przytoczonym powyżej użyciu instrukcji switch.

Struktury

[edytuj]

Struktury to specjalny typ danych mogący przechowywać wiele wartości w jednej zmiennej. Od tablic jednakże różni się tym, iż te wartości mogą być różnych typów.

Struktury definiuje się w następujący sposób:

 struct Struktura {
   int pole1;
   int pole2;
   char pole3;
 };

gdzie "Struktura" to nazwa tworzonej struktury.
Nazewnictwo, ilość i typ pól definiuje programista według własnego uznania.

Zmienną posiadającą strukturę tworzy się podając jako jej typ nazwę struktury.

 struct Struktura zmiennaS;


Dostęp do poszczególnych pól uzyskuje się przy pomocy operatora wyboru składnika: kropki ('.').

 zmiennaS.pole1 = 60;   /* przypisanie liczb do pól */
 zmiennaS.pole2 = 2;
 zmiennaS.pole3 = 'a';  /* a teraz znaku */



typedef struct

[edytuj]

Deklaracja typu strukturalnego

Definicja nienazwanego typu strukturalnego:[1]

typedef struct {
    int x;
    int y;
} TypPunktowy;

TypPunktowy to jest

  • alias do typu
  • krótka nazwa typu ( pełna nazwa to: struct TypPunktowy)


W obrębie struktury nie można odwoływać się do siebie za pomocą krótkiej nazwy.


Struktury jako argumenty funkcji mogą być użyte na 2 sposoby:[2]

  • przekazywanie wartości bez możliwości ich zmiany ( ang. pass by value)
  • przekazywanie wartości z możliwością ich zmiany ( ang. pass by reference)


/*
https://en.cppreference.com/w/c/language/struct_initialization

gcc s.c -Wall -Wextra
./a.out

*/
#include <stdio.h>


// definicja typu
typedef struct {   
    char name[20];
    char sex; 
    int age; 
} person_t;


// zmienna
person_t p = {"Tom", 'M', 19};


int main(void)
{

	 printf("person name = %s, sex = %d age = %d \n", p.name, p.sex, p.age);


	return 0;
}

Unie

[edytuj]

Unie to kolejny sposób prezentacji danych w pamięci. Na pierwszy rzut oka wyglądają bardzo podobnie do struktur:

 union Nazwa {
   typ1 nazwa1;
   typ2 nazwa2;
   /* ... */
 };

Na przykład:

 union LiczbaLubZnak {
   int calkowita;
   char znak;
   double rzeczywista;
 };

Pola w unii nakładają się na siebie w ten sposób, że w danej chwili można w niej przechowywać wartość tylko jednego typu. Unia zajmuje w pamięci tyle miejsca, ile zajmuje największa z jej składowych. W powyższym przypadku unia będzie miała prawdopodobnie rozmiar typu double czyli często 64 bity, a całkowita i znak będą wskazywały odpowiednio na pierwsze cztery bajty lub na pierwszy bajt unii (choć nie musi tak być zawsze). Dlaczego tak? Taka forma często przydaje się np. do konwersji pomiędzy różnymi typami danych. Możemy dzięki unii podzielić zmienną 32-bitową na cztery składowe zmienne o długości 8 bitów każda.

Do konkretnych wartości pól unii odwołujemy się, podobnie jak w przypadku struktur, za pomocą kropki:

 union LiczbaLubZnak liczba;
 liczba.calkowita = 10;
 printf("%d\n", liczba.calkowita);

Zazwyczaj użycie unii ma na celu zmniejszenie zapotrzebowania na pamięć, gdy naraz będzie wykorzystywane tylko jedno pole i jest często łączone z użyciem struktur.

Przyjrzyjmy się teraz przykładowi, który powinien dobitnie zademonstrować działanie unii:

 #include <stdio.h>
 
 struct adres_bajtowy {
  __uint8_t a;
  __uint8_t b;
  __uint8_t c;
  __uint8_t d;
  };
 
 union adres {
   __uint32_t ip;
   struct adres_bajtowy badres;
   };
 
 int main ()
 {
    union adres addr;
    addr.badres.a = 192;
    addr.badres.b = 168;
    addr.badres.c = 1;
    addr.badres.d = 1;
    printf ("Adres IP w postaci 32-bitowej zmiennej: %08x\n",addr.ip);
    return 0;
 }

Zauważyłeś pewien ciekawy efekt? Jeśli uruchomiłeś ten program na typowym komputerze domowym (rodzina i386) na ekranie zapewne pojawił Ci się taki oto napis:

Adres IP w postaci 32-bitowej zmiennej: 0101a8c0

Dlaczego jedynki są na początku zmiennej, skoro w programie były to dwa ostatnie bajty (pola c i d struktury)? Jest to problem kolejności bajtów. Aby dowiedzieć się o nim więcej przeczytaj rozdział przenośność programów. Zauważyłeś zatem, że za pomocą tego programu w prosty sposób zamieniliśmy cztery zmienne jednobajtowe w jedną czterobajtową. Jest to tylko jedno z możliwych zastosowań unii.

Inicjacja struktur i unii

[edytuj]

Jeśli tworzymy nową strukturę lub unię możemy zaraz po jej deklaracji wypełnić ją określonymi danymi. Rozważmy tutaj przykład:

 struct moja_struct {
    int a;
    char b;
    } moja = {1,'c'};

W zasadzie taka deklaracja nie różni się niczym od wypełnienia np. tablicy danymi. Jednak standard C99 wprowadza pewne udogodnienie zarówno przy deklaracji struktur, jak i unii. Polega ono na tym, że w nawiasie klamrowym możemy podać nazwy pól struktury lub unii którym przypisujemy wartość, np.:

 struct moja_struct {
    int a;
    char b;
    } moja = {.b = 'c'}; /* pozostawiamy pole a niewypełnione żadną konkretną wartością */

Wspólne własności typów wyliczeniowych, unii i struktur

[edytuj]

Warto zwrócić uwagę, że język C++ przy deklaracji zmiennych typów wyliczeniowych, unii lub struktur nie wymaga przed nazwą typu słowa kluczowego typedef. Na przykład poniższy kod jest poprawnym programem C++:

 enum   Enum   { A, B, C };
 union  Union  { int a; float b; };
 struct Struct { int a; float b; };
 int main() {
   Enum   e;
   Union  u;
   Struct s;
   e = A;
   u.a = 0;
   s.a = 0;
   return e + u.a + s.a;
 }

Nie jest to jednak poprawny kod C i należy o tym pamiętać szczególnie jeżeli uczysz się języka C korzystając z kompilatora C++.

Częstym idiomem w C jest użycie typedef od razu z definicją typu, by uniknąć pisania enum, union czy struct przy deklaracji zmiennych danego typu.[3]

 typedef struct struktura {
   int pole;
 } Struktura;

 
 Struktura s1;
 struct struktura s2;

W tym przypadku zmienne s1 i s2 są tego samego typu, który ma 2 nazwy: pełną:

struct struktura

i skróconą:

Struktura  



Możemy też zrezygnować z pełnej nazwy struktury i pozostawić tylko skróconą:

 typedef struct {
   int pole;
 } Struktura;

 Struktura s1;

Jeśli chcemy utworzyć strukturę rekurencyjną to wewnątrz struktury możemy użyć tylko nazwy długiej, nie krótkiej:

 typedef struct Wezel {// długa nazwa typu 
  double re;
  double im;
  int level;
  struct Wezel *poprzedni; /* poprzedni węzeł */     
} TWezel; // krótka nazwa typu

Należy również pamiętać, że po klamrze zamykającej definicje musi następować średnik. Brak tego średnika jest częstym błędem powodującym czasami niezrozumiałe komunikaty błędów. Jedynym wyjątkiem jest natychmiastowa definicja zmiennych danego typu, na przykład:

 struct Struktura {
   int pole;
 } s1, s2, s3;

lub też definicja nowego typu, jak w poprzednim bloku kodowym (TWezel).

Definicja typów wyliczeniowych, unii i struktur jest lokalna do bloku. To znaczy, możemy zdefiniować strukturę wewnątrz jednej z funkcji (czy wręcz wewnątrz jakiegoś bloku funkcji) i tylko tam będzie można używać tego typu.

Wskaźnik na unię i strukturę

[edytuj]

Podobnie, jak na każdą inną zmienna, wskaźnik może wskazywać także na unię lub strukturę. Oto przykład:

 typedef struct {
   int p1, p2;
 } Struktura;

 int main ()
 {
   Struktura s = { 0, 0 };
   Struktura *wsk = &s;
   wsk->p1 = 2;
   wsk->p2 = 3;
   return 0;
 }

Zapis wsk->p1 jest (z definicji) równoważny (*wsk).p1, ale bardziej przejrzysty i powszechnie stosowany. Wyrażenie wsk.p1 spowoduje błąd kompilacji (strukturą jest *wsk a nie wsk).


Zobacz też

[edytuj]

Pola bitowe

[edytuj]

Struktury mają pewne dodatkowe możliwości w stosunku do zmiennych. Mowa tutaj o rozmiarze elementu struktury. W przeciwieństwie do zmiennej może on mieć nawet 1 bit!. Aby móc zdefiniować taką zmienną musimy użyć tzw. pola bitowego. Wygląda ono tak:

 struct moja {
   unsigned int a1:4, /* 4 bity */
                a2:8, /* 8 bitów (często 1 bajt) */ 
                a3:1, /* 1 bit */
                a4:3; /* 3 bity */
 };

Wszystkie pola tej struktury mają w sumie rozmiar 16 bitów, jednak możemy odwoływać się do nich w taki sam sposób, jak do innych elementów struktury. W ten sposób efektywniej wykorzystujemy pamięć, jednak istnieją pewne zjawiska, których musimy być świadomi przy stosowaniu pól bitowych. Więcej na ten temat w rozdziale przenośność programów.

Pola bitowe znalazły zastosowanie głównie w implementacjach protokołów sieciowych.

Listy

[edytuj]

rodzaje list:

  • lista jednokierunkowa – w każdym elemencie listy jest przechowywane odniesienie tylko do jednego sąsiada (następnika lub poprzednika)
  • lista dwukierunkowa – w każdym elemencie listy jest przechowywane odniesienie zarówno do następnika, jak i poprzednika elementu w liście. Taka reprezentacja umożliwia swobodne przemieszczanie się po liście w obie strony
  • lista cykliczna – następnikiem ostatniego elementu jest pierwszy element. Po liście można więc przemieszczać się cyklicznie. Nie ma w takiej liście charakterystycznego ogona (ani głowy), często rozpoznawanego po tym, że jego następnik jest pusty (NULL)
  • lista z wartownikiem – lista z wyróżnionym elementem zwanym wartownikiem. Jest to specjalnie oznaczony element niewidoczny dla programisty wykorzystującego listę. Pusta lista zawiera wtedy tylko wartownika. Zastosowanie wartownika znacznie upraszcza implementację operacji na listach.


Studium przypadku: lista jednokierunkowa

[edytuj]

Rozważmy teraz coś, co każdy z nas może spotkać w codziennym życiu. Każdy z nas widział kiedyś jakiś przykład listy (czy to zakupów, czy też listę wierzycieli). Język C też oferuje listy, jednak w programowaniu listy będą służyły do czegoś innego. Wyobraźmy sobie sytuację, w której jesteśmy autorami genialnego programu, który znajduje kolejne liczby pierwsze. Oczywiście każdą kolejną liczbę pierwszą może wyświetlać na ekran, jednak z matematyki wiemy, że dana liczba jest liczbą pierwszą, jeśli nie dzieli się przez żadną liczbę pierwszą ją poprzedzającą, mniejszą od pierwiastka z badanej liczby. Mniej więcej chodzi o to, że moglibyśmy wykorzystać znalezione wcześniej liczby do przyspieszenia działania naszego programu. Jednak nasze liczby trzeba jakoś mądrze przechować w pamięci. Tablice mają ograniczenie - musimy z góry znać ich rozmiar. Jeśli zapełnilibyśmy tablicę, to przy znalezieniu każdej kolejnej liczby musielibyśmy:

  1. przydzielać nowy obszar pamięci o rozmiarze poprzedniego rozmiaru + rozmiar zmiennej, przechowującej nowo znalezioną liczbę
  2. kopiować zawartość starego obszaru do nowego
  3. zwalniać stary, nieużywany obszar pamięci
  4. w ostatnim elemencie nowej tablicy zapisać znalezioną liczbę.

Cóż, trochę tutaj roboty jest, a kopiowanie całej zawartości jednego obszaru w drugi jest czasochłonne. W takim przypadku możemy użyć listy. Tworząc listę możemy w prosty sposób przechować nowo znalezione liczby. Przy użyciu listy nasze postępowanie ograniczy się do:

  1. przydzielenia obszaru pamięci, aby przechować wartość obliczeń
  2. dodać do listy nowy element

Prawda, że proste? Dodatkowo, lista zajmuje w pamięci tylko tyle pamięci, ile potrzeba na aktualną liczbę elementów. Pusta tablica zajmuje natomiast tyle samo miejsca co pełna tablica.

Implementacja listy

[edytuj]

W języku C aby stworzyć listę musimy użyć struktur. Dlaczego? Ponieważ musimy przechować co najmniej dwie wartości:

  1. pewną zmienną (np. liczbę pierwszą z przykładu)
  2. wskaźnik na kolejny element listy

Przyjmijmy, że szukając liczb pierwszych nie przekroczymy możliwości typu unsigned long:

 typedef struct element {
   struct element *next; /* wskaźnik na kolejny element listy */
   unsigned long val; /* przechowywana wartość */
 } el_listy;

Zacznijmy zatem pisać nasz eksperymentalny program, do wyszukiwania liczb pierwszych. Pierwszą liczbą pierwszą jest liczba 2 Pierwszym elementem naszej listy będzie zatem struktura, która będzie przechowywała liczbę 2. Na co będzie wskazywało pole next? Ponieważ na początku działania programu będziemy mieć tylko jeden element listy, pole next powinno wskazywać na NULL. Umówmy się zatem, że pole next ostatniego elementu listy będzie wskazywało NULL - po tym poznamy, że lista się skończyła.

 #include <stdio.h>
 #include <stdlib.h>
 typedef struct element {
   struct element *next;
   unsigned long val;
 } el_listy;
 
 el_listy *first; /* pierwszy element listy */
  
 int main ()
 {
   unsigned long i = 3; /* szukamy liczb pierwszych w zakresie od 3 do 1000 */
   const unsigned long END = 1000;
   first = malloc (sizeof(el_listy));
   first->val = 2;
   first->next = NULL;
   for (;i<=END;++i) {
     /* tutaj powinien znajdować się kod, który sprawdza podzielność sprawdzanej liczby przez
        poprzednio znalezione liczby pierwsze oraz dodaje liczbę do listy w przypadku stwierdzenia,
        że jest ona liczbą pierwszą. */
     }
   wypisz_liste(first);
  return 0;
 }

Na początek zajmiemy się wypisywaniem listy. W tym celu będziemy musieli "odwiedzić" każdy element listy. Elementy listy są połączone polem next, aby przejrzeć listę użyjemy następującego algorytmu:

  1. Ustaw wskaźnik roboczy na pierwszym elemencie listy
  2. Jeśli wskaźnik ma wartość NULL, przerwij
  3. Wypisz element wskazywany przez wskaźnik
  4. Przesuń wskaźnik na element, który jest wskazywany przez pole next
  5. Wróć do punktu 2
 void wypisz_liste(el_listy *lista)
 {
   el_listy *wsk=lista;          /* 1 */
   while( wsk != NULL )          /* 2 */
     {
     printf ("%lu\n", wsk->val); /* 3 */
     wsk = wsk->next;            /* 4 */
     }                           /* 5 */
 }

Zastanówmy się teraz, jak powinien wyglądać kod, który dodaje do listy następny element. Taka funkcja powinna:

  1. znaleźć ostatni element (tj. element, którego pole next == NULL)
  2. przydzielić odpowiedni obszar pamięci
  3. skopiować w pole val w nowo przydzielonym obszarze znalezioną liczbę pierwszą
  4. nadać polu next ostatniego elementu listy wartość NULL
  5. w pole next ostatniego elementu listy wpisać adres nowo przydzielonego obszaru

Napiszmy zatem odpowiednią funkcję:

 void dodaj_do_listy (el_listy *lista, unsigned long liczba)
 {
   el_listy *wsk, *nowy;
   wsk = lista;
   while (wsk->next != NULL)          /* 1 */
     { 
     wsk = wsk->next; /* przesuwamy wsk aż znajdziemy ostatni element */
     }
   nowy = malloc (sizeof(el_listy));  /* 2 */
   nowy->val = liczba;                /* 3 */
   nowy->next = NULL;                 /* 4 */
   wsk->next = nowy;                  /* 5 */
 }

I... to już właściwie koniec naszej funkcji (warto zwrócić uwagę, że funkcja w tej wersji zakłada, że na liście jest już przynajmniej jeden element). Wstaw ją do kodu przed funkcją main. Został nam jeszcze jeden problem: w pętli for musimy dodać kod, który odpowiednio będzie "badał" liczby oraz w przypadku stwierdzenia pierwszeństwa liczby, będzie dodawał ją do listy. Ten kod powinien wyglądać mniej więcej tak:

 int jest_pierwsza(el_listy *lista, int liczba)
 {
   el_listy *wsk;
   wsk = lista;
   while (wsk != NULL) {
     if ((liczba % wsk->val)==0) return 0;  /* jeśli reszta z dzielenia liczby
                                               przez którąkolwiek z poprzednio
                                               znalezionych liczb pierwszych
                                               jest równa zero, to znaczy, że liczba
                                               ta nie jest liczbą pierwszą */
     wsk = wsk->next;
     }
   /* natomiast jeśli sprawdzimy wszystkie poprzednio znalezione liczby
      i żadna z nich nie będzie dzieliła liczby i,
      możemy liczbę i dodać do listy liczb pierwszych */
   return 1;
 }
 ...
 for (;i<=END;++i) {
   if (jest_pierwsza(first, i))
     dodaj_do_listy (first,i);
     }

Kod

[edytuj]

Podsumujmy teraz efekty naszej pracy. Oto cały kod naszego programu:

 #include <stdio.h>
 #include <stdlib.h>
 
 typedef struct element {
   struct element *next;
   unsigned long val;
 } el_listy;
 
 el_listy *first;
 
 void dodaj_do_listy (el_listy *lista, unsigned long liczba)
 {
   el_listy *wsk, *nowy;
   wsk = lista;
   while (wsk->next != NULL)
     { 
     wsk = wsk->next; /* przesuwamy wsk aż znajdziemy ostatni element */
     }
   nowy =(el_listy*) malloc (sizeof(el_listy));
   nowy->val = liczba;
   nowy->next = NULL;
   wsk->next = nowy; /* podczepiamy nowy element do ostatniego z listy */
 }
 
 void wypisz_liste(el_listy *lista)
 {
   el_listy *wsk=lista;
   while( wsk != NULL )
     {
     printf ("%lu\n", wsk->val);
     wsk = wsk->next;
     }
 }
 
 int jest_pierwsza(el_listy *lista, int liczba)
 {
   el_listy *wsk;
   wsk = lista;
   while (wsk != NULL) {
     if ((liczba%wsk->val)==0) return 0;
        wsk = wsk->next;
     }
     return 1;
 }
 
 int main ()
 {
   unsigned long i = 3; /* szukamy liczb pierwszych w zakresie od 3 do 1000 */
   const unsigned long END = 1000;
   first =(el_listy*) malloc (sizeof(el_listy));
   first->val = 2;
   first->next = NULL;
   for (;i!=END;++i) {
     if (jest_pierwsza(first, i))
       dodaj_do_listy (first, i);
       }
   wypisz_liste(first);
   return 0;
 }

Możemy jeszcze pomyśleć, jak można by wykonać usuwanie elementu z listy. Najprościej byłoby zrobić:

wsk->next = wsk->next->next

ale wtedy element, na który wskazywał wcześniej wsk->next przestaje być dostępny i zaśmieca pamięć. Trzeba go usunąć. Zauważmy, że aby usunąć element potrzebujemy wskaźnika do elementu go poprzedzającego (po to, by nie rozerwać listy). Popatrzmy na poniższą funkcję:

 void usun_z_listy(el_listy *lista, int element)
 {
   el_listy *wsk=lista;
   while (wsk->next != NULL)
   {
     if (wsk->next->val == element) /* musimy mieć wskaźnik do elementu poprzedzającego */
     {
       el_listy *usuwany=wsk->next; /* zapamiętujemy usuwany element */
       wsk->next = usuwany->next;   /* przestawiamy wskaźnik next by omijał usuwany element */
       free(usuwany);               /* usuwamy z pamięci */
     } 
     else 
     {
       wsk = wsk->next;             /* idziemy dalej tylko wtedy kiedy nie usuwaliśmy */
     }                              /* bo nie chcemy zostawić duplikatów */
   }
 }

Funkcja ta jest tak napisana, by usuwała z listy wszystkie wystąpienia danego elementu (w naszym programie nie ma to miejsca, ale lista jest zrobiona tak, że może trzymać dowolne liczby). Zauważmy, że wskaźnik wsk jest przesuwany tylko wtedy, gdy nie kasowaliśmy. Gdybyśmy zawsze go przesuwali, przegapilibyśmy element gdyby występował kilka razy pod rząd.

Funkcja ta działa poprawnie tylko wtedy, gdy nie chcemy usuwać pierwszego elementu. Można to poprawić - dodając instrukcję warunkową do funkcji lub dodając do listy "głowę" - pierwszy element nie przechowujący niczego, ale upraszczający operacje na liście. Zostawiamy to do samodzielnej pracy.


Cały powyższy przykład omawiał tylko jeden przypadek listy - listę jednokierunkową. Jednak istnieją jeszcze inne typy list, np. lista jednokierunkowa cykliczna, lista dwukierunkowa oraz dwukierunkowa cykliczna. Różnią się one od siebie tylko tym, że:

  • w przypadku list dwukierunkowych - w strukturze el_listy znajduje się jeszcze pole, które wskazuje na element poprzedni
  • w przypadku list cyklicznych - ostatni element wskazuje na pierwszy (nie rozróżnia się wtedy elementu pierwszego, ani ostatniego)

Lista dwukierunkowa

[edytuj]
//http://thradams.com/generator/linked_list.html
#include <stdlib.h>
#include <assert.h>
#include <errno.h>

struct book {
     char* title;
     struct book* next;
     struct book* prev;
};

void book_destroy(struct book* book) {
    /*remove if it is empty*/
     free(book->title);
}
 

struct books {
    struct book* head, *tail;
};

void books_insert_after(struct books* books, struct book* book, struct book* new_book)
{
    assert(books != NULL);
    assert(book != NULL);
    assert(new_book != NULL);
    assert(new_book->prev == NULL);
    assert(new_book->next == NULL);

    new_book->prev = book;

    if (book->next == NULL) {
        books->tail = new_book;
    }
    else {
        new_book->next = book->next;
        book->next->prev = new_book;
    }

    book->next = new_book;
}

void books_insert_before(struct books* books, struct book* book, struct book* new_book)
{
    assert(books != NULL);
    assert(book != NULL);
    assert(new_book != NULL);
    assert(new_book->prev == NULL);
    assert(new_book->next == NULL);

    new_book->next = book;
    if (book->prev == NULL) {
        books->head = new_book;
    }
    else {
        new_book->prev = book->prev;
        book->prev->next = new_book;
    }
    book->prev = new_book;

}
void books_remove(struct books* books, struct book* book)
{
    assert(books != NULL);
    assert(book != NULL);

    if (book->prev == NULL)
        books->head = book->next;
    else
        book->prev->next = book->next;

    if (book->next == NULL)
        books->tail = book->prev;
    else
        book->next->prev = book->prev;
    
    book_destroy(book);
    free(book);
}


void books_push_back(struct books* books, struct book* new_book)
{
   assert(books != NULL);
   assert(new_book != NULL);
   assert(new_book->prev == NULL);
   assert(new_book->next == NULL);

   if (books->tail == NULL) {
      books->head = new_book;
   }
   else {
      new_book->prev = books->tail;        
      books->tail->next = new_book;
   }
   books->tail = new_book;
}

void books_push_front(struct books* books, struct book* new_book)
{
    assert(books != NULL);
    assert(new_book != NULL);
     assert(new_book->prev == NULL);
    assert(new_book->next == NULL);

    if (books->head == NULL) {
        books->tail = new_book;
    }
    else {
        new_book->next = books->head;        
        books->head->prev = new_book;
    }
    books->head = new_book;
}

void books_destroy(struct books* books)
{
    //pre condition
    assert(books != NULL);

    struct book* it = books->head;
    while (it != NULL) {
        struct book* next = it->next;
        book_destroy(it);
        free(it);
        it = next;
    }
}

int main(int argc, char* argv[])
{
    struct books list = { 0 };
    struct book* b1 = calloc(1, sizeof(struct book));
    if (b1)
    {
        books_push_front(&list, b1);
    }
    books_destroy(&list);
}

Odnośniki

[edytuj]
  1. stackoverflow question: how-to-properly-use-typedef-for-structs-in-c
  2. stackoverflow questions : passing-struct-to-function
  3. [Difference between 'struct' and 'typedef struct' in C++? ]