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;
}
