Listy jednokierunkowe

-- Sebastian Pawlak, 2003.

Węzeł listy jest strukturą zawierającą informację oraz wskaźnik na następny węzeł listy.


typedef struct wezel {
    int wartosc;
    wezel *nastepny;
} wezel;

Lista jednokierunkowa

Przechowywanie danych w listach ma swoje zalety i wady. Zaletą list jest dynamiczne przydzielanie i zwalnianie pamięci na poszczególne węzły. Zatem w trakcie działania programu można zarezerwować tylko tyle pamięci ile potrzeba. Gdyby nieprzewidywalną ilość danych przechowywać w tablicy, której wielkość ustawia się "na sztywno" przed kompilacją, należałoby zadeklarować tablicę o zapewne dużym rozmiarze. Także operowanie na danych przechowywanych w liście jest na ogół mniej czasochłonne niż w przypadku tablic. Usuwanie i wstawianie z/do listy nie wymaga przenoszenia pozostałych elementów, jak ma to miejsce w przypadku tablic. Wadą list jest to, że każdy węzeł zawiera wskaźnik do następnego węzła, co pochłania pamięć operacyjną. Za pomocą listy nie można zaimplementować algorytmu wyszukiwania binarnego -- co nie jest problemem w przypadku tablic. Dostęp do poszczególnych elementów listy wymaga przejścia poprzednich elementów.

Wstawianie elementu na początek listy

Usuwanie elementu z początku listy

Usuwanie elementu ze środka bądź końca listy

Kod źródłowy pliku "lista.h":

/* lista.h: plik naglowkowy biblioteki z implementacja operacji na
 *          listach jednokierunkowych
 * Sebastian Pawlak, 2003-12-3
 */
#ifndef _LISTA_H_
#define _LISTA_H_

typedef struct wezel {
    int wartosc;
    struct wezel *nastepny;
} wezel;

enum {
    POPRAWNIE = 0,
    BRAK_PAMIECI = -1,
    BLAD_IO = -2,
    BLAD_POZYCJI = -3
};

int wstawPocz(wezel **L, int wartosc);
int wstaw(wezel **L, int p, int wartosc);
int usun(wezel **L, int p);
int zwroc(wezel *L, int p, int *wartosc);
int znajdz(wezel *L, int *p, int wartosc);
void wyczysc(wezel **L);
void wypisz(wezel *L);
int zapisz(wezel *L, char *nazwaPliku);
int wczytaj(wezel **L, char *nazwaPliku);

#endif

Kod źródłowy pliku "lista.c":

/* lista.c: biblioteka z implementacja operacji na
 *          listach jednokierunkowych
 * Sebastian Pawlak, 2003-12-3
 */
#include <stdio.h>
#include <stdlib.h>
#include "lista.h"

/* wstawPocz: tworzy i wstawia nowy element na poczatek listy */
int wstawPocz(wezel **L, int wartosc)
{
    wezel *Q;

    if ((Q = (wezel *)malloc(sizeof (wezel))) == NULL)
        return BRAK_PAMIECI;

    Q -> wartosc = wartosc;
    Q -> nastepny = *L;

    *L = Q;

    return POPRAWNIE;
}


/* wstaw: tworzy i wstawia nowy element na p-ta pozycje na liscie;
 *        pozycja liczona jest od 0
 */
int wstaw(wezel **L, int p, int wartosc)
{
    wezel *Q, *S = NULL, *T = *L;

    while (T && (p > 0)) {
        S = T;
        T = T -> nastepny;
        p--;
    }

    if (p != 0)
        return BLAD_POZYCJI;

    if ((Q = (wezel *)malloc(sizeof (wezel))) == NULL)
        return BRAK_PAMIECI;

    Q -> wartosc = wartosc;
    Q -> nastepny = T;

    if (S == NULL)
        *L = Q;
    else
        S -> nastepny = Q;

    return POPRAWNIE;
}


/* usun: usuwa element z p-tej pozycji na liscie;
 *       pozycja liczona jest od 0
 */
int usun(wezel **L, int p)
{
    wezel *S = NULL, *T = *L;

    while (T && (p > 0)) {
        S = T;
        T = T -> nastepny;
        p--;
    }

    if ((p != 0) || (T == NULL))
        return BLAD_POZYCJI;

    if (S == NULL)
        *L = T -> nastepny;
    else
        S -> nastepny = T -> nastepny;

    free(T);

    return POPRAWNIE;
}


/* zwroc: przypisuje zmiennej "wartosc" wartosc p-tego elementu z listy */
int zwroc(wezel *L, int p, int *wartosc)
{
    while (L && (p > 0)) {
        L = L -> nastepny;
        p--;
    }

    if ((p != 0) || (L == NULL))
        return BLAD_POZYCJI;

    *wartosc = L -> wartosc;

    return 0;
}


/* znajdz: przypisuje zmiennej "p" numer elementu listy, pod ktorym wystepuje
 *         "wartosc"
 */
int znajdz(wezel *L, int *p, int wartosc)
{
    *p = 0;

    while (L && (L -> wartosc != wartosc)) {
        (*p)++;
        L = L -> nastepny;
    }

    if (L == NULL)
        return BLAD_POZYCJI;

    return POPRAWNIE;
}


/* wyczysc: usuwa wszystkie elementy z listy */
void wyczysc(wezel **L)
{
    wezel *Q;

    while (*L) {
        Q = *L;
        *L = (*L) -> nastepny;

        free(Q);
    }
}


/* wypisz: wypisuje wszystkie elementy z listy */
void wypisz(wezel *L)
{
    while (L) {
        printf("%d\n", L -> wartosc);

        L = L -> nastepny;
    }
}


/* zapisz: zapisuje wszystkie elementy z listy do pliku tekstowego */
int zapisz(wezel *L, char *nazwaPliku)
{
    FILE *f;

    if ((f = fopen(nazwaPliku, "w")) == NULL)
	return BLAD_IO;

    while (L) {
        if (fprintf(f, "%d%c",
                    L -> wartosc, L -> nastepny ? ' ' : '\n') < 0)
            return BLAD_IO;

        L = L -> nastepny;
    }

    fclose(f);

    return POPRAWNIE;
}


/* wczytaj: wczytuje z pliku tekstowego elementy i wstawia je na liste 
 *          w odwrotnej kolejnosci
 */
int wczytaj(wezel **L, char *nazwaPliku)
{
    wezel *Q, *T = *L;
    FILE *f;
    int wartosc;

    if ((f = fopen(nazwaPliku, "r")) == NULL)
	return BLAD_IO;

    /* odnalezienie konca listy */
    while (T && (T -> nastepny))
        T = T -> nastepny;

    while (fscanf(f, "%d", &wartosc) != EOF) {
        if ((Q = (wezel *)malloc(sizeof (wezel))) == NULL)
            return BRAK_PAMIECI;

        Q -> wartosc = wartosc;
        Q -> nastepny = NULL;

        if (T == NULL)
            *L = T = Q;
        else {
            T -> nastepny = Q;   /* dopisywanie elementow do konca listy */
            T = T -> nastepny;
        }
    }

    fclose(f);

    return POPRAWNIE;
}

Kod źródłowy pliku "test.c":

/* test.c: ilustracja dzialania biblioteki lista.c
 * Sebastian Pawlak, 2003-12-3
 */
#include <stdio.h>
#include "lista.h"

int main(void)
{
    wezel *L = NULL;
    int p;

    wstawPocz(&L, 11);
    wstawPocz(&L, 33);
    wstaw(&L, 1, 22);
    wstaw(&L, 0, 78);
    usun(&L, 0);

    wypisz(L);

    return 0;
}