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