Listy jednokierunkowe (wersja z rozbudowaną strukturą danych)

    -- 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 {
    dana *obj;
    wezel *nastepny;
} wezel;

Zaprezentowana wersja biblioteki umożliwia przechowywanie w węzłach listy danych, o rozbudowanej strukturze: 


typedef struct dana {
    char *nazwisko;
    int wiek;
} dana;

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

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

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

/* wezel listy */
typedef struct wezel {
    dana *obj;
    struct wezel *nastepny;
} wezel;

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

dana *nowy(char *nazwisko, int wiek);
int wstawPocz(wezel **L, dana *obj);
int wstaw(wezel **L, int p, dana *obj);
int usun(wezel **L, int p);
int zwroc(wezel *L, int p, dana **obj);
int znajdz(wezel *L, int *p, char *nazwisko);
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 (wersja z rozbudowana struktura danych)
 * Sebastian Pawlak, 2003-12-11
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "lista.h"

/* nowy: tworzy w pamieci nowy element danych;
 *       te funkcje nalezy zmodyfikowac, jesli ulegnie zmianie struktura "dana"
 */
dana *nowy(char *nazwisko, int wiek)
{
    dana *d = NULL;

    if ((d = (dana *)malloc(sizeof (dana))) == NULL)
        return NULL;

    if ((d -> nazwisko = (char *)malloc(strlen(nazwisko) + 1)) == NULL)
        return NULL;

    strcpy(d -> nazwisko, nazwisko);

    d -> wiek = wiek;

    return d;
}


/* wstawPocz: tworzy i wstawia nowy element na poczatek listy */
int wstawPocz(wezel **L, dana *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, dana *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)
{
    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 -> obj -> nazwisko);  /* zmodyfikowac, jesli zmieni sie "dana" */
    free(T -> obj);
    free(T);

    return POPRAWNIE;
}


/* zwroc: przypisuje wskaznikowi "obj" p-ty element z listy */
int zwroc(wezel *L, int p, dana **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;
 *         szukamy zgodnosci nazwisk
 */
int znajdz(wezel *L, int *p, char *nazwisko)
{
    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 && (strcmp(L -> obj -> nazwisko, nazwisko))) {
        (*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 -> obj -> nazwisko); /* zmodyfikowac, jesli zmieni sie "dana" */
        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)
{
    while (L) {
        /* zmodyfikowac, jesli zmieni sie dana */
        printf("nazwisko: %s, wiek: %d\n",
               L -> obj -> nazwisko, L -> obj -> wiek);

        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) {
        /* zmodyfikowac, jesli zmieni sie dana */
        if (fprintf(f, "%s %d\n", L -> obj -> nazwisko, L -> obj -> wiek) < 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;
    char nazwisko[30];
    int wiek;

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

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

    /* zmodyfikowac, jesli zmieni sie dana */
    while (fscanf(f, "%s %d", nazwisko, &wiek) != EOF) { 
        if ((Q = (wezel *)malloc(sizeof (wezel))) == NULL)
            return BRAK_PAMIECI;

        /* zmodyfikowac, jesli zmieni sie dana */
        Q -> obj = nowy(nazwisko, wiek);
        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"


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);
    wypisz(L);
    printf("----------\n");

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

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

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

    zapisz(L, "lista");
    wyczysc(&L);
    wczytaj(&L, "lista");
    wczytaj(&L, "lista");
    wypisz(L);

    return 0;
}
w3cw3c
automatyka przemysłowa