Listy jednokierunkowe (wersja uniwersalna)

    -- Sebastian Pawlak, 2003.


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


typedef struct wezel {
    void *obj;
    wezel *nastepny;
} wezel;

Zaprezentowana wersja biblioteki umożliwia przechowywanie w węzłach listy dowolnych danych, o strukturze zdefiniowanej przez użytkownika. Wadą tego rozwiązania jest konieczność indywidualnego zaprogramowania kilku funkcji operujących na strukturze danych (patrz: test.c).


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

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

#include <stdarg.h>

typedef struct wezel {
    void *obj;
    struct wezel *nastepny;
} wezel;

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

int wstawPocz(wezel **L, void *obj);
int wstaw(wezel **L, int p, void *obj);
int usun(wezel **L, int p, void (*fn)(void *obj));
int zwroc(wezel *L, int p, void **obj);
int znajdz(wezel *L, int *p, int (*fn)(void *obj1, va_list *ap), ...);
void wyczysc(wezel **L, void (*fn)(void *obj));
void wypisz(wezel *L, void (*fn)(void *obj));
int zapisz(wezel *L, char *nazwaPliku, int (*fn)(FILE *f, void *obj));
int wczytaj(wezel **L, char *nazwaPliku, int (*fn)(FILE *f, void **obj));

#endif


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

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

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

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

    Q -> obj = obj;
    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, void *obj)
{
    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 -> obj = obj;
    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, void (*fn)(void *obj))
{
    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;

    (*fn)(T -> obj);  /* funkcja uzytkownika: kasuje pola "obj" */
    free(T -> obj);
    free(T);

    return POPRAWNIE;
}


/* zwroc: przypisuje wskaznikowi "obj" p-ty element z listy */
int zwroc(wezel *L, int p, void **obj)
{
    while (L && (p > 0)) {
        L = L -> nastepny;
        p--;
    }

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

    *obj = L -> obj;

    return 0;
}


/* znajdz: przypisuje zmiennej "p" numer elementu listy, dla ktorego 
 *         funkcja porownujaca "fn" zwroci wartosc 1;
 *         przeszukiwanie listy rozpoczyna sie od p-tego elementu
 */
int znajdz(wezel *L, int *p, int (*fn)(void *obj1, va_list *ap), ...)
{
    va_list ap;
    int i = *p;

    /* przesuniecie sie na p-ta pozycje, aby od tej pozycji rozpoczac
     * poszukiwanie
     */
    while (L && (i > 0)) {
        L = L -> nastepny;
        i--;
    }

    while (L) {
        va_start(ap, fn);  /* "fn" - ostatni nazwany argument */
        if ((*fn)(L -> obj, &ap)) /* funkcja uzytkownika: porownanie */
            return POPRAWNIE;
        va_end(ap);

        (*p)++;
        L = L -> nastepny;
    }

    return BLAD_POZYCJI;
}


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

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

        (*fn)(Q -> obj);  /* funkcja uzytkownika: kasuje pola "obj" */
        free(Q -> obj);
        free(Q);
    }
}


/* wypisz: wypisuje wszystkie elementy z listy;
 *         funkcji tej mozna uzyc takze do zaaplikowania danej operacji
 *         na wszystkich elementach listy
 */
void wypisz(wezel *L, void (*fn)(void *obj))
{
    while (L) {
        (*fn)(L -> obj);  /* funkcja uzytkownika: wypisanie */

        L = L -> nastepny;
    }
}


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

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

    while (L) {
        if ((*fn)(f, L -> obj) < 0)  /* funkcja uzytkownika: zapis */
            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, int (*fn)(FILE *f, void **obj))
{
    wezel *Q, *T = *L;
    FILE *f;
    void *obj;

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

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

    while ((*fn)(f, &obj) != EOF) {  /* funkcja uzytkownika: odczyt */
        if ((Q = (wezel *)malloc(sizeof (wezel))) == NULL)
            return BRAK_PAMIECI;

        Q -> obj = obj;
        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-11
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "lista.h"

/* struktura definiujaca element danych
 * umieszczany w wezle listy
 */
typedef struct dana {
    char *nazwisko;
    int wiek;
} dana;

void *nowy(char *nazwisko, int wiek);
void usunDana(void *obj);
int znajdzDana(void *obj1, va_list *ap);
void wypiszDana(void *obj);
int zapiszDana(FILE *f, void *obj);
int wczytajDana(FILE *f, void **obj);


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

    wstawPocz(&L, nowy("Kernighan", 55));
    wstawPocz(&L, nowy("Ritchie", 57));
    wstaw(&L, 1, nowy("Stroustrup", 61));
    wstawPocz(&L, nowy("Kernighan", 44));
    wstaw(&L, 2, nowy("Nikt", 10));
    usun(&L, 2, usunDana);
    wypisz(L, wypiszDana);
    printf("----------\n");

    zwroc(L, 1, (void *)&d);
    printf("> nazwisko: %s, wiek: %d\n", d -> nazwisko, d -> wiek);
    printf("----------\n");

    p = 0; 
    while (znajdz(L, &p, znajdzDana, "Kernighan") == POPRAWNIE)
        printf("znaleziono \"Kernighan\" pod numerem: %d\n", p++);

    printf("----------\n");

    zapisz(L, "lista", zapiszDana);
    wyczysc(&L, usunDana);
    wczytaj(&L, "lista", wczytajDana);
    wczytaj(&L, "lista", wczytajDana);
    wypisz(L, wypiszDana);

    return 0;
}


/* nowy: tworzy w pamieci nowy element danych */
void *nowy(char *nazwisko, int wiek)
{
    dana *d = NULL;

    if ((d = (dana *)malloc(sizeof (dana))) == NULL)
        perror("nowy: Brak pamieci 1!");

    if ((d -> nazwisko = (char *)malloc(strlen(nazwisko) + 1)) == NULL)
        perror("nowy: Brak pamieci 2!");

    strcpy(d -> nazwisko, nazwisko);

    d -> wiek = wiek;

    return (void *)d;
}


/* usunDana: usuwa z pamieci pola elementu danych */
void usunDana(void *obj)
{
    free(((dana *)obj) -> nazwisko);
    /* free(obj) przesunieta do lista.c */
}


/* znajdzDana: porownuje odpowiednie pola z "obj1" z podanymi jako
 *             argumenty;
 *             w niniejszej funkcji porównywane są nazwiska
 */
int znajdzDana(void *obj1, va_list *ap)
{
    char *nazwisko = va_arg(*ap, char *);

    if (!strcmp(((dana *)obj1) -> nazwisko, nazwisko))
        return 1;

    return 0;
}


/* wypiszDana: wypisuje odpowiednie pola elementu danych */
void wypiszDana(void *obj)
{
    printf("nazwisko: %s, wiek: %d\n",
           ((dana *)obj) -> nazwisko, ((dana *)obj) -> wiek);
}


/* zapiszDana: zapisuje do pliku odpowiednie pola elementu danych */
int zapiszDana(FILE *f, void *obj)
{
    return fprintf(f, "%s %d\n",
                   ((dana *)obj) -> nazwisko, ((dana *)obj) ->wiek);
}


/* wczytajDana: wczytuje z pliku dane i tworzy w pamieci element danych */
int wczytajDana(FILE *f, void **obj)
{
    char nazwisko[20];
    int wiek;
    int ret;

    ret = fscanf(f, "%s %d", nazwisko, &wiek);

    *obj = nowy(nazwisko, wiek);

    return ret;
}
w3cw3c
automatyka przemysłowa