Programowanie strukturalne
- Wykład 12

Złożone typy danych

typedef

typedef to słowo kluczowe w języku C, które pozwala na definiowanie aliasów dla typów danych. W kontekście struktur, typedef jest często używane w celu uproszczenia deklaracji zmiennych strukturalnych i funkcji.

Wariant 1 - Użycie typedef podczas definiowania struktury:

#include <stdio.h>

typedef struct {
    float x;
    float y;
} Punkt2D;

int main() {
    Punkt2D punkt = {3.0, 4.0};
    printf("Punkt: (%.1f, %.1f)\n", punkt.x, punkt.y);
    return 0;
}

Wariant 2 - Użycie typedef po definiowaniu struktury:

#include <stdio.h>

struct Punkt {
    float x;
    float y;
};

typedef struct Punkt Punkt2D;

int main() {
    Punkt2D punkt = {3.0, 4.0};
    printf("Punkt: (%.1f, %.1f)\n", punkt.x, punkt.y);
    return 0;
}

Wariant 3 - Użycie typedef w kombinacji ze wskaźnikami na strukturę:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    float x;
    float y;
} Punkt2D;

int main() {
    Punkt2D *punkt = (Punkt2D *)malloc(sizeof(Punkt2D));
    punkt->x = 3.0;
    punkt->y = 4.0;
    printf("Punkt: (%.1f, %.1f)\n", punkt->x, punkt->y);
    free(punkt);
    return 0;
}

Wariant 4 - Użycie typedef w funkcjach przyjmujących struktury jako argumenty:

#include <stdio.h>

typedef struct {
    float x;
    float y;
} Punkt2D;

void wypisz_punkt(Punkt2D p) {
    printf("Punkt: (%.1f, %.1f)\n", p.x, p.y);
}

int main() {
    Punkt2D punkt = {3.0, 4.0};
    wypisz_punkt(punkt);
    return 0;
}

Przekazywanie struktur do funkcji

  1. Przekazywanie struktury przez wartość:
#include <stdio.h>

struct Punkt2D {
    float x;
    float y;
};

void wypisz_punkt(struct Punkt2D p) {
    printf("Punkt: (%.1f, %.1f)\n", p.x, p.y);
}

int main() {
    struct Punkt2D punkt = {3.0, 4.0};
    wypisz_punkt(punkt); // przekazanie struktury przez wartość
    return 0;
}
  1. Przekazywanie struktury przez wskaźnik:
#include <stdio.h>

struct Punkt2D {
    float x;
    float y;
};

void przesun_punkt(struct Punkt2D *p, float dx, float dy) {
    p->x += dx;
    p->y += dy;
}

int main() {
    struct Punkt2D punkt = {3.0, 4.0};
    printf("Punkt przed przesunieciem: (%.1f, %.1f)\n", punkt.x, punkt.y);
    przesun_punkt(&punkt, 2.0, 3.0); // przekazanie struktury przez wskaźnik
    printf("Punkt po przesunieciu: (%.1f, %.1f)\n", punkt.x, punkt.y);
    return 0;
}

Zwracanie przez funkcję struktury

Przykład zwracania struktury jako zwykłej zmiennej:

#include <stdio.h>

struct Point {
  int x;
  int y;
};

struct Point add_points(struct Point p1, struct Point p2) {
  struct Point result;
  result.x = p1.x + p2.x;
  result.y = p1.y + p2.y;
  return result;
}

int main() {
  struct Point p1 = {1, 2};
  struct Point p2 = {3, 4};
  struct Point sum = add_points(p1, p2);
  printf("sum: (%d, %d)\n", sum.x, sum.y);
  return 0;
}

Przykład zwracania struktury przez wskaźnik przekazany jako argument:

#include <stdio.h>

struct Point {
  int x;
  int y;
};

void add_points(struct Point p1, struct Point p2, struct Point *result) {
  result->x = p1.x + p2.x;
  result->y = p1.y + p2.y;
}

int main() {
  struct Point p1 = {1, 2};
  struct Point p2 = {3, 4};
  struct Point sum;
  add_points(p1, p2, &sum);
  printf("sum: (%d, %d)\n", sum.x, sum.y);
  return 0;
}

Przykład zwracania struktury przez wskaźnik przekazany (bezpośrednio):

#include <stdio.h>
#include <stdlib.h>

struct Person {
    char *name;
    int age;
};

struct Person *create_person(char *name, int age) {
    struct Person *new_person = malloc(sizeof(struct Person));
    new_person->name = name;
    new_person->age = age;
    return new_person;
}

int main() {
    struct Person *person1 = create_person("John Doe", 30);
    printf("Name: %s, Age: %d\n", person1->name, person1->age);
    free(person1);
    return 0;
}

“Wartościowość struktur”

#include <stdio.h>
#include <stdlib.h>

struct Punkt3D
{
    int x,y,z;
};

void przepisz(struct Punkt3D tab1[], struct Punkt3D tab2[], int n)
{
    for(int i = 0; i < n; i++)
    {
        tab2[i] = tab1[i];
    }
}

void wyswietl(struct Punkt3D tab[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("[%d]: %d %d %d\n", i, tab[i].x, tab[i].y, tab[i].z);
    }
    printf("---\n");
}

int main()
{
    struct Punkt3D p1 = {1,2,3};
    struct Punkt3D p2 = {4,5,6};
    struct Punkt3D p3 = {7,8,9};
    struct Punkt3D tab1[] = {p1,p2,p3};
    struct Punkt3D tab2[] =
    {
            {0,0,0},
            {0,0,0},
            {0,0,0}
    };
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    przepisz(tab1, tab2, 3);
    printf("Po przepisaniu:\n");
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    tab1[0].x = 10;
    printf("Po zmianie:\n");
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    return 0;
}

Dziwny warning?

#include <stdio.h>
#include <stdlib.h>

struct Punkt3D
{
    int tab[3];
};

void przepisz(struct Punkt3D tab1[], struct Punkt3D tab2[], int n)
{
    for(int i = 0; i < n; i++)
    {
        tab2[i] = tab1[i];
    }
}

void wyswietl(struct Punkt3D tab[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("[%d]: ", i);
        for(int j = 0; j < 3; j++)
        {
            printf("%d ", tab[i].tab[j]);
        }
        printf("\n");
    }
    printf("---\n");
}

int main()
{
    struct Punkt3D p1 = {1,2,3};
    struct Punkt3D p2 = {4,5,6};
    struct Punkt3D p3 = {7,8,9};
    struct Punkt3D tab1[] = {p1,p2,p3};
    struct Punkt3D tab2[] =
    {
            {0,0,0},
            {0,0,0},
            {0,0,0}
    };
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    przepisz(tab1, tab2, 3);
    printf("Po przepisaniu:\n");
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    tab1[0].tab[2] = 22;
    printf("Po zmianie:\n");
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    return 0;
}

Wersja poprawiona

#include <stdio.h>
#include <stdlib.h>

struct Punkt3D
{
    int wspolrzedne[3];
};

void przepisz(struct Punkt3D tab1[], struct Punkt3D tab2[], int n)
{
    for(int i = 0; i < n; i++)
    {
        tab2[i] = tab1[i];
    }
}

void wyswietl(struct Punkt3D tab[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("[%d]: ", i);
        for(int j = 0; j < 3; j++)
        {
            printf("%d ", tab[i].wspolrzedne[j]);
        }
        printf("\n");
    }
    printf("---\n");
}

int main()
{
    struct Punkt3D p1 = {.wspolrzedne={1, 2, 3}};
    struct Punkt3D p2 = {{4,5,6}};
    struct Punkt3D p3 = {{7,8,9}};
    struct Punkt3D tab1[] = {p1,p2,p3};
    struct Punkt3D tab2[] =
    {
            {{0,0,0}},
            {{0,0,0}},
            {{0,0,0}}
    };
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    przepisz(tab1, tab2, 3);
    printf("Po przepisaniu:\n");
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    tab1[0].wspolrzedne[2] = 22;
    printf("Po zmianie:\n");
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    return 0;
}

A gdy mamy wskaźnik?

#include <stdio.h>
#include <stdlib.h>

struct Punkt3D
{
    int * wspolrzedne;
};

void przepisz(struct Punkt3D tab1[], struct Punkt3D tab2[], int n)
{
    for(int i = 0; i < n; i++)
    {
        tab2[i] = tab1[i];
    }
}

void wyswietl(struct Punkt3D tab[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("[%d]: ", i);
        for(int j = 0; j < 3; j++)
        {
            printf("%d ", tab[i].wspolrzedne[j]);
        }
        printf("\n");
    }
    printf("---\n");
}

int main()
{
    struct Punkt3D p1 = {.wspolrzedne=malloc(3*sizeof(int))};
    p1.wspolrzedne[0] = 1;
    p1.wspolrzedne[1] = 2;
    p1.wspolrzedne[2] = 3;
    struct Punkt3D p2 = {(int[]){4,5,6}};
    struct Punkt3D p3 = {(int[]){7,8,9}};
    struct Punkt3D tab1[] = {p1,p2,p3};
    struct Punkt3D tab2[] =
    {
            {(int[]){0,0,0}},
            {(int[]){0,0,0}},
            {(int[]){0,0,0}}
    };
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    przepisz(tab1, tab2, 3);
    printf("Po przepisaniu:\n");
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    tab1[0].wspolrzedne[2] = 22;
    printf("Po zmianie:\n");
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    return 0;
}

Trzeba zrobić “głębokie kopiowanie”:

#include <stdio.h>
#include <stdlib.h>

struct Punkt3D
{
    int * wspolrzedne;
};

void przepisz(struct Punkt3D tab1[], struct Punkt3D tab2[], int n)
{
    for(int i = 0; i < n; i++)
    {
        tab2[i].wspolrzedne[0] = tab1[i].wspolrzedne[0];
        tab2[i].wspolrzedne[1] = tab1[i].wspolrzedne[1];
        tab2[i].wspolrzedne[2] = tab1[i].wspolrzedne[2];
    }
}

void wyswietl(struct Punkt3D tab[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("[%d]: ", i);
        for(int j = 0; j < 3; j++)
        {
            printf("%d ", tab[i].wspolrzedne[j]);
        }
        printf("\n");
    }
    printf("---\n");
}

int main()
{
    struct Punkt3D p1 = {.wspolrzedne=malloc(3*sizeof(int))};
    p1.wspolrzedne[0] = 1;
    p1.wspolrzedne[1] = 2;
    p1.wspolrzedne[2] = 3;
    struct Punkt3D p2 = {(int[]){4,5,6}};
    struct Punkt3D p3 = {(int[]){7,8,9}};
    struct Punkt3D tab1[] = {p1,p2,p3};
    struct Punkt3D tab2[] =
    {
            {(int[]){0,0,0}},
            {(int[]){0,0,0}},
            {(int[]){0,0,0}}
    };
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    przepisz(tab1, tab2, 3);
    printf("Po przepisaniu:\n");
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    tab1[0].wspolrzedne[2] = 22;
    printf("Po zmianie:\n");
    wyswietl(tab1, 3);
    wyswietl(tab2, 3);
    return 0;
}

Unie

Unia (ang. union) jest typem, który pozwala przechowywać różne rodzaje danych w tym samym obszarze pamięci (jednak nie równocześnie).

 union Nazwa {
   typ1 nazwa1;
   typ2 nazwa2;
   /* ... */
 };
#include <stdio.h>
#include <stdlib.h>

union Unia {
   int pole1;
   char pole2;
 };

int main()
{
    union Unia zm;
    zm.pole1=67;
    printf("%c\n",zm.pole1);
    printf("%d\n",zm.pole1);
    printf("%c\n",zm.pole2);
    printf("%d\n",zm.pole2);
    return 0;
}
#include <stdio.h>

union Number {
    int i;
    float f;
    double d;
};

int main() {
    union Number num;
    num.i = 10;
    printf("int: %d\n", num.i);
    num.f = 3.14;
    printf("float: %f\n", num.f);
    num.d = 2.718;
    printf("double: %lf\n", num.d);
    printf("int: %d\n", num.i);
    return 0;
}
#include <stdio.h>
#include <stdlib.h>
union Liczba
{
    int a;
    float b;
};
struct Dane
{
    int tp;
    union Liczba zaw;
};
struct Dane wczytaj()
{
    struct Dane temp;
    printf("Jesli chcesz wpisac liczbe calk to wpisz 0,a jesli wymierna to wpisz 1\n");
    scanf("%d", &temp.tp);
    if (temp.tp ==0)
    {
        scanf("%d", &temp.zaw.a);
    }
    else
    {
        scanf("%f", &temp.zaw.b);
    }
    return temp;
};
void wyswietl(struct Dane arg)
{
    if (arg.tp ==0)
    {
        printf("%d\n", arg.zaw.a);
    }
    else
    {
        printf("%f\n", arg.zaw.b);
    }
}
int main()
{
    union Liczba zm;
    zm.a =5;
    printf("%d\n", zm.a);
    printf("%f\n", zm.b);
    zm.b=3.4;
    printf("%d\n", zm.a);
    printf("%f\n", zm.b);
    struct Dane dane1;
    dane1= wczytaj();
    wyswietl(dane1);
    return 0;
}

Typ wyliczeniowy

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 };
#include <stdio.h>
#include <stdlib.h>

enum miasta {OLSZTYN, GDANSK, KRAKOW, WARSZAWA, BYDGOSZCZ};

int main()
{
    enum miasta m1 = OLSZTYN;
    printf("%s\n",m1);
    printf("%d\n",m1);
    printf("%u\n",m1);
    return 0;
}

Struktury - prekursor do obiektowości?

#include <stdio.h>
#include <string.h>

struct Laptop {
    char model[30];
    float cena;
};

struct Laptop initLaptop(char* model, float cena) {
    struct Laptop nowyLaptop;
    strncpy(nowyLaptop.model, model, sizeof(nowyLaptop.model) - 1);
    nowyLaptop.model[sizeof(nowyLaptop.model) - 1] = '\0';
    nowyLaptop.cena = cena;
    return nowyLaptop;
}

void pokazLaptop(struct Laptop laptop) {
    printf("Model: %s\n", laptop.model);
    printf("Cena: %.2f\n", laptop.cena);
}

void zmniejszCene(struct Laptop* laptop) {
    laptop->cena *= 0.95;
}

int main() {
    struct Laptop mojLaptop = initLaptop("Dell XPS 15", 5000.0);
    pokazLaptop(mojLaptop);
    zmniejszCene(&mojLaptop);
    printf("Po obnizce ceny:\n");
    pokazLaptop(mojLaptop);
    return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Ksiazka {
    char tytul[50];
    int liczba_stron;
} Ksiazka;

Ksiazka* initKsiazka(const char *tytul, int liczba_stron) {
    if(strlen(tytul) < 5 || liczba_stron <= 50)
        return NULL;

    Ksiazka* nowa_ksiazka = (Ksiazka*)malloc(sizeof(Ksiazka));
    strcpy(nowa_ksiazka->tytul, tytul);
    nowa_ksiazka->liczba_stron = liczba_stron;

    return nowa_ksiazka;
}

void pokazKsiazka(Ksiazka ksiazka) {
    printf("Tytul: %s, Liczba stron: %d\n", ksiazka.tytul, ksiazka.liczba_stron);
}

void dodajStrony(Ksiazka *ksiazka) {
    ksiazka->liczba_stron += 10;
}

int main() {
    Ksiazka* ksiazka1 = initKsiazka("Wojna i pokoj", 1200);

    if(ksiazka1 != NULL) {
        pokazKsiazka(*ksiazka1);
        dodajStrony(ksiazka1);
        pokazKsiazka(*ksiazka1);
    } else {
        printf("Nie udalo sie utworzyc ksiazki.\n");
    }

    free(ksiazka1);

    return 0;
}

Listy jednokierunkowe

Listy jednokierunkowe - “opowieść”

Listy jednokierunkowe – jest to pewna złożona konstrukcja, która w sposób elastyczny pozwala nam trzymać elementy określonego typu. W odróżnieniu od tablic nie określamy z góry jego rozmiaru, więc z punktu widzenia programisty konstrukcja jest bardziej bezpieczna.

Inspiracja: Jaś i Małgosia

Idea implementacji w języku C polega na stworzeniu struktury elementy o składni:

struct element
{
    int i;
    struct element * next;
};

Pole i to wartość konkretngo elementu. Pole next to wskaźnik na następnik. Przy tak elastycznej konstrukcji nie mamy zawsze pewności, w której „miejsce” w pamięci trafi kolejny element. Standardowo też powinniśmy na każdy elementy zarezerwować pamięć (poprzez funkcję malloc). Usuwając element możemy to wykonać zwalniając pamięć metodą free.

Mamy podstawowe dwa rodzaj list: bez głowy i z głową. W przypadku listy z głową tworzymy pusty element „głowę” tak, aby wykonując operację na liście zawsze mieć stały „adres”/wskaźnik na początek listy (tak jak w przypadku tablic wskaźnik na listę to inaczej wskaźnik na pierwszy element). Co zyskujemy? Warto rozważyć sobie sytuację, kiedy mamy jakąś listę i chcemy dodać element na początek.

Rozważmy listę:

Lista bez głowy mogłaby by wyglądać tak:

Kod:

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element *next;
};

int main()
{
    // stwórz listę bez głowy o elementach 5,7,-4
    struct element * lista = malloc(sizeof(struct element));
    lista->i = 5;
    lista->next = malloc(sizeof(struct element));
    lista->next->i = 7;
    lista->next->next = malloc(sizeof(struct element));
    lista->next->next->i = -4;
    lista->next->next->next = NULL;
    //wyswietl listę
    struct element * wsk = lista;
    while(wsk != NULL)
    {
        printf("%d\n", wsk->i);
        wsk = wsk->next;
    }
    return 0;
}

Rozważmy teraz przypadek listy z głową

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element *next;
};

int main()
{
    // stwórz listę z głową o elementach 5,7,-4
    struct element * lista = malloc(sizeof(struct element));
    lista->next = malloc(sizeof(struct element));
    lista->next->i = 5;
    lista->next->next = malloc(sizeof(struct element));
    lista->next->next->i = 7;
    lista->next->next->next = malloc(sizeof(struct element));
    lista->next->next->next->i = -4;
    lista->next->next->next->next = NULL;
    //wyswietl listę
    struct element * wsk = lista->next;
    while(wsk != NULL)
    {
        printf("%d\n", wsk->i);
        wsk = wsk->next;
    }
    return 0;
}

Porównanie

  1. Lista z głową (Headed List): Lista z głową ma dodatkowy element, zwykle nazywany “głową” lub “dummy node”, który nie przechowuje żadnych danych, ale służy jako punkt odniesienia do początku listy. Głowa listy wskazuje na pierwszy element listy zawierający rzeczywiste dane. Przy korzystaniu z listy z głową, operacje takie jak dodawanie elementu na początek listy lub usuwanie elementu z początku listy stają się prostsze, ponieważ nie musimy martwić się o specjalne przypadki, kiedy lista jest pusta.

  2. Lista bez głowy (Headless List): W liście bez głowy, pierwszy element listy przechowuje rzeczywiste dane. W przeciwieństwie do listy z głową, nie ma dodatkowego elementu wskazującego na początek listy. W tym przypadku, musimy zwracać szczególną uwagę na specjalne przypadki, takie jak dodawanie lub usuwanie elementu z początku listy, szczególnie kiedy lista jest pusta.

Pusta lista bez głowy

Konwencja:

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element *next;
};

int main()
{
    struct element * lista = NULL;
    return 0;
}

Pusta lista z głową

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element *next;
};

int main()
{
    struct element * lista = malloc(sizeof(struct element));
    lista->next = NULL;
    return 0;
}

Dodanie na początek - lista bez głowy

Dodanie na początek wymaga zatem wykonania następujących operacji (bez uwzględnienia sytuacji kiedy bazowa lista jest pusta):

  1. Rezerwacja pamięci na nowy element
  2. Ustawienia wartości pola i na nowym elemencie z punktu 1
  3. Pole next nowego elementu z punktu 1 jest ustawiane jako adres pierwszej elementu początkowej listy
  4. Należy zmienić wskaźnik całej „listy” wskazując jako adres „nowy” element z punktu 1.

Kod w main z kolejnym dodawaniem elementów

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element * next;
};

int main()
{
     struct element * lista = NULL; //tworzymy "pustą listę"
     //dodajemy pierwszy element na listę (tu pojęcie koniec czy początek nie ma większego sensu)
     struct element * wsk = malloc(sizeof(struct element)); // rezerwujemy miejsce w pamięci na jeden z elementów
     wsk->i=-4;
     wsk->next=NULL; //bo nic więcej nie ma na liście
     lista=wsk; // ustawiamy wskaznik początku listy
     // dodajemy nowy element na początek
     struct element * wsk2 = malloc(sizeof(struct element)); // rezerwujemy miejsce w pamięci na jeden z elementów
     wsk2->i=7;
     wsk2->next=lista; // następnik nowego elementu to bieżacy wskaznik listy
     lista=wsk2;  // ustawiamy wskaznik nowego elementy jako początek listy
     // dodajemy jeszcze jeden nowy element na początek
     struct element * wsk3 = malloc(sizeof(struct element)); // rezerwujemy miejsce w pamięci na jeden z elementów
     wsk3->i=5;
     wsk3->next=lista; // następnik nowego elementu to bieżacy wskaznik listy
     lista=wsk3;  // ustawiamy wskaznik nowego elementy jako początek listy
     //tu już mamy listę jak na rysunku - pierwszy eleemnt yo 5, drugi to 7, trzeci to i 4
     // teraz dodajemy 11 na początek
     struct element * wsk4 = malloc(sizeof(struct element)); // rezerwujemy miejsce w pamięci na jeden z elementów
     wsk4->i=11;
     wsk4->next=lista; // następnik nowego elementu to bieżacy wskaznik listy
     lista=wsk4;  // ustawiamy wskaznik nowego elementy jako początek listy
     return 0;
}

Prostsze rozwiązanie gdy lista jest już stworzona:

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element * next;
};

int main()
{
    struct element * lista = malloc(sizeof (struct element));
    lista->i = 5;
    lista->next = malloc(sizeof (struct element));
    lista->next->i = 7;
    lista->next->next = malloc(sizeof (struct element));
    lista->next->next->i = -4;
    lista->next->next->next = NULL;
    struct element * temp = lista;
    while (temp != NULL)
    {
        printf("%d\n", temp->i);
        temp = temp->next;
    }
    printf("dodanie\n");
    struct element * wsk = malloc(sizeof (struct element));
    wsk->i = 11;
    wsk->next = lista;
    lista = wsk;
    temp = lista;
    while (temp != NULL)
    {
        printf("%d\n", temp->i);
        temp = temp->next;
    }
    return 0;
}

Kod w funkcji

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element * next;
};

struct element* dodaj(struct element*Lista, int a)
{
    struct element * wsk = malloc(sizeof(struct element));
    wsk->i=a;
    wsk->next=Lista;
    return wsk;
}

struct element * utworz()
{
    return NULL;
}

int main()
{
    struct element* l1 = utworz();
    l1 = dodaj(l1,2);
    l1 = dodaj(l1,4);
    l1 = dodaj(l1,7);
    l1 = dodaj(l1,-2);
    struct element * wsk = l1;
    while(wsk!=NULL)
    {
        printf("%d\n",wsk->i);
        wsk=wsk->next;
    }
    return 0;
}

Kod w funkcji - argument podwójny wskaźnik

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element * next;
};

void dodaj(struct element**Lista, int a)
{
    struct element * wsk = malloc(sizeof(struct element));
    wsk->i=a;
    wsk->next=*Lista;
    *Lista= wsk;
}

struct element * utworz()
{
    return NULL;
}

int main()
{
    struct element* l1 = utworz();
    dodaj(&l1,2);
    dodaj(&l1,4);
    dodaj(&l1,7);
    dodaj(&l1,-2);
    struct element * wsk = l1;
    while(wsk!=NULL)
    {
        printf("%d\n",wsk->i);
        wsk=wsk->next;
    }
    return 0;
}

Dodanie na początek - lista z głową

Dodanie na początek (przy założeniu że bieżąca lista nie jest pusta) polega na wykonaniu operacji:

  1. Rezerwujemy pamięć na nowy element
  2. Ustawiamy wartość jako pole i
  3. Pole next ustawiamy jako to co znajduje się w „głowie” w polu next
  4. Modyfikujemy pole next w „głowie” ustawiając je jako wskaźnik na nowy element z punktu 1

Ważne: nie możemy zmienić kolejności punktu 3 i 4 bo zmieni to sens.

Kod w main:

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element * next;
};

int main()
{
     //tworzymy głowę
     struct element * lista = malloc(sizeof(struct element));
     //pola i glowy nie ustawiamy
     lista->next= NULL; //następnik glowy jest na NULL, mamy zatem w tym miejscu pustą listę z głową
     //dodajemy pierwszy element na listę - w liscie z głową musimy go postawić po głowie
     struct element * wsk = malloc(sizeof(struct element)); // rezerwujemy miejsce w pamięci na jeden z elementów
     wsk->i=-4;
     wsk->next=lista->next; //tutaj teoretycznie można ustawić na NULL, ale zgodnie z konwencją trzeba ustawić pole next głowy
     lista->next=wsk; // ustawiamy nastepnik glowy jako wskaznik na nowy element
     // dodajemy nowy element na początek
     struct element * wsk2 = malloc(sizeof(struct element)); // rezerwujemy miejsce w pamięci na jeden z elementów
     wsk2->i=7;
     wsk2->next=lista->next; // następnik nowego elementu to nastepnik "głowy"
     lista->next=wsk2;  // ustawiamy następnik głowy jako wskaźnik na nowy element
     // dodajemy jeszcze jeden nowy element na początek
     struct element * wsk3 = malloc(sizeof(struct element)); // rezerwujemy miejsce w pamięci na jeden z elementów
     wsk3->i=5;
     wsk3->next=lista->next; // następnik nowego elementu to nastepnik "głowy"
     lista->next=wsk3;  // ustawiamy następnik głowy jako wskaźnik na nowy element
     //tu już mamy listę jak na rysunku - "głowa", pierwszy eleemnt to 5, drugi to 7, trzeci to i 4
     // teraz dodajemy 11 na początek
     struct element * wsk4 = malloc(sizeof(struct element)); // rezerwujemy miejsce w pamięci na jeden z elementów
     wsk4->i=11;
     wsk4->next=lista->next; // następnik nowego elementu to nastepnik "głowy"
     lista->next=wsk4;  // ustawiamy następnik głowy jako wskaźnik na nowy element
     return 0;
}

Prostsze rozwiązanie gdy lista jest już stworzona:

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element * next;
};

int main()
{
    struct element * lista = malloc(sizeof(struct element));
    lista->next = malloc(sizeof(struct element));
    lista->next->i = 5;
    lista->next->next = malloc(sizeof(struct element));
    lista->next->next->i = 7;
    lista->next->next->next = malloc(sizeof(struct element));
    lista->next->next->next->i = -4;
    lista->next->next->next->next = NULL;
    struct element * temp = lista->next;
    while(temp != NULL)
    {
        printf("%d\n", temp->i);
        temp = temp->next;
    }
    printf("Dodanie\n");
    struct element * wsk = malloc(sizeof(struct element));
    wsk->i = 11;
    wsk->next = lista->next;
    lista->next = wsk;
    temp = lista->next;
    while(temp != NULL)
    {
        printf("%d\n", temp->i);
        temp = temp->next;
    }
    return 0;
}

Kod przez funkcje:

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element * next;
};

struct element * utworz()
{
    struct element * wskaznik = malloc(sizeof(struct element));
    wskaznik->next=NULL;
    return wskaznik;
}

void dodaj(struct element*Lista, int a)
{
    struct element * wsk = malloc(sizeof(struct element));
    wsk->i=a;
    wsk->next=Lista->next;
    Lista->next=wsk;
}

int main()
{
    struct element* l1 = utworz();
    dodaj(l1,2);
    dodaj(l1,4);
    dodaj(l1,-8);
    dodaj(l1,-22);
    struct element * wsk = l1;
    while(wsk->next!=NULL)
    {
        wsk=wsk->next;
        printf("%d\n",wsk->i);
    }
    return 0;
}

Co zyskujemy? To zależy od kontekstu w którym używamy i jakie operacje mamy. W wielu sytuacjach zmiana wskaźnika „początku” przy liście bez głowy jest operacją, która zwiększa tzw. złożoność obliczeniową.

Na dziś można sobie myśleć, że jest to „szybsze” (to też zależy od języka programowania).

Dodanie na koniec - lista bez głowy

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element * next;
};

struct element * dodaj_na_koniec(struct element * Lista, int a)
{
    struct element * wsk;
    wsk = Lista;
    if (Lista == NULL)
    {
        Lista = malloc(sizeof(struct element));
        Lista->i = a;
        Lista->next = NULL;
    }
    else
    {
        while (wsk->next != NULL)
        {
            wsk = wsk->next;
        }
        wsk->next = malloc(sizeof(struct element));
        wsk->next->i = a;
        wsk->next->next = NULL;
    }
    return Lista;
}

void wyswietl(struct element * Lista)
{
    struct element * wsk;
    wsk = Lista;
    if (wsk == NULL)
    {
        printf("Lista jest pusta\n");
        return;
    }
        while (wsk != NULL)
    {
        printf("%d\n", wsk->i);
        wsk = wsk->next;
    }
    printf("---\n");
}

int main()
{
    // przypadek pusty
    struct element * Lista = NULL;
    wyswietl(Lista);
    Lista = dodaj_na_koniec(Lista, 5);
    wyswietl(Lista);
    // przypadek listy dwuelementowej
    struct element * lista2 = malloc(sizeof(struct element));
    lista2->i = 12;
    lista2->next = malloc(sizeof(struct element));
    lista2->next->i = -8;
    lista2->next->next = NULL;
    wyswietl(lista2);
    lista2 = dodaj_na_koniec(lista2, 3);
    wyswietl(lista2);
    return 0;
}

Podwójny wskaźnik

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element * next;
};

void dodaj_na_koniec(struct element ** Lista, int a)
{
    struct element * wsk;
    wsk = *Lista;
    if (wsk == NULL)
    {
        wsk = malloc(sizeof(struct element));
        wsk->i = a;
        wsk->next = NULL;
        *Lista = wsk;
        return;
    }
    while (wsk->next != NULL)
    {
        wsk = wsk->next;
    }
    wsk->next = malloc(sizeof(struct element));
    wsk->next->i = a;
    wsk->next->next = NULL;
}

void wyswietl(struct element * Lista)
{
    struct element * wsk;
    wsk = Lista;
    if (wsk == NULL)
    {
        printf("Lista jest pusta\n");
        return;
    }
        while (wsk != NULL)
    {
        printf("%d\n", wsk->i);
        wsk = wsk->next;
    }
    printf("---\n");
}

int main()
{
    // przypadek pusty
    struct element * Lista = NULL;
    wyswietl(Lista);
    dodaj_na_koniec(&Lista, 5);
    wyswietl(Lista);
    // przypadek listy dwuelementowej
    struct element * lista2 = malloc(sizeof(struct element));
    lista2->i = 12;
    lista2->next = malloc(sizeof(struct element));
    lista2->next->i = -8;
    lista2->next->next = NULL;
    wyswietl(lista2);
    dodaj_na_koniec(&lista2, 3);
    wyswietl(lista2);
    return 0;
}

Dodanie na koniec - lista z głową

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int i;
    struct element * next;
};

void dodaj_na_koniec(struct element * Lista, int a)
{
    struct element * wsk;
    wsk = Lista;
    while (wsk->next != NULL)
    {
        wsk = wsk->next;
    }
    wsk->next = malloc(sizeof(struct element));
    wsk->next->i = a;
    wsk->next->next = NULL;
}

void wyswietl(struct element * Lista)
{
    struct element * wsk;
    wsk = Lista->next;
    if (wsk == NULL)
    {
        printf("Lista jest pusta\n");
        return;
    }
        while (wsk != NULL)
    {
        printf("%d\n", wsk->i);
        wsk = wsk->next;
    }
    printf("---\n");
}

int main()
{
    // przypadek pusty
    struct element * Lista1 = malloc(sizeof(struct element));
    Lista1->next = NULL;
    wyswietl(Lista1);
    dodaj_na_koniec(Lista1, 5);
    wyswietl(Lista1);
    // przypadek dwuelementowy
    struct element * Lista2 = malloc(sizeof(struct element));
    Lista2->next = malloc(sizeof(struct element));
    Lista2->next->i = 12;
    Lista2->next->next = malloc(sizeof(struct element));
    Lista2->next->next->i = -8;
    Lista2->next->next->next = NULL;
    wyswietl(Lista2);
    dodaj_na_koniec(Lista2, 3);
    wyswietl(Lista2);
    return 0;
}

Bibliografia