Podstawy programowania. Wykład 10  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
10. Lista jednokierunkowa (dowiązaniowa) ......................................................................... 2
10.1 Operacje ................................................................................................................... 2
10.1.1 Deklaracja............................................................................................................. 3
10.1.2 Wstawianie na początku ....................................................................................... 3
10.1.3 Wstawianie na końcu ........................................................................................... 3
10.1.4 Przeglądanie listy ................................................................................................. 4
10.1.5 Usuwanie elementu z listy.................................................................................... 4
10.2 Przykład ................................................................................................................... 5
1
Podstawy programowania. Wykład 10  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
10. Lista jednokierunkowa (dowiązaniowa)
Najprostszym sposobem pozwalającym grupować dowolną ilość danych (ograniczoną tylko
rozmiarem dostępnej pamięci) jest lista jednokierunkowa.
W tym przypadku każdy element jest pojedynczym rekordem (strukturą) składającym się z co
najmniej dwóch pól:
" pola wartości
" wskaz
nika do następnego elementu listy.
Wartością wskaz
nika umożliwiającą jednoznaczne zidentyfikowanie ostatniego elementu
listy jest specjalna wartość NULL.
Listę można przeglądać tylko po kolei (od początku do końca). Ponieważ każdy element
posiada jedynie wskaz
nik do jego następnika, więc dotarcie do n-tego elementu listy wymaga
wcześniej przejścia przez n-1 poprzedników. W tym wypadku mówimy zatem o dostępnie
sekwencyjnym.
" Pierwszy element  głowa (ang. head);
" Ostatni element  ogon (ang. tail);
10.1 Operacje
Najprostsze operacje, jakie możemy wykonać na liście jednokierunkowej:
- wstawienie elementu na początek listy,
- wstawienie elementu na koniec listy,
- wstawienie elementu, tak by lista była cały czas uporządkowana
- usunięcie pierwszego elementu listy,
- usunięcie ostatniego elementu listy,
- odczyt pierwszego elementu listy,
- dostęp do dowolnego elementu listy.
W zależności od wyboru podstawowych operacji wykonywanych na liście możemy wyróżnić
dwa podstawowe rodzaje struktur implementowanych na podstawie list jednokierunkowych:
2
Podstawy programowania. Wykład 10  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
- stos (możliwe jest wstawianie, usuwanie i odczyt pierwszego elementu listy 
wierzchołka;tego typu struktura nazywana jest LIFO (ang. Last In First
Out),
- kolejka (pojedyncza, jednokierunkowa): wstawianie elementu na koniec listy, odczyt i
usuwanie elementu pierwszego  struktura typu FIFO (ang. First In First Out).
10.1.1 Deklaracja
struct Wezel
{Elem elem;
Wezel *nast; /* wskaz
nik do następnego elementu listy */
};
Wezel *glowa;
10.1.2 Wstawianie na początku
Algorytm
1. przydzielić odpowiedni obszar pamięci (funkcja malloc),
2. skopiować w pole elem w nowo przydzielonym obszarze żądaną wartość,
3. nadać polu nast nowego elementu listy wartość dotychczasowej głowy,
4. nową głową uczynić adres nowo przydzielonego obszaru.
10.1.3 Wstawianie na końcu
Algorytm
1. przydzielić odpowiedni obszar pamięci,
2. skopiować w pole elem w nowo przydzielonym obszarze żądaną wartość,
3. nadać polu nast nowego elementu listy wartość NULL,
4. znalez
ć ostatni element (tj. element, którego pole nast == NULL),
3
Podstawy programowania. Wykład 10  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
5. w pole nast dotychczasowego ostatniego elementu listy wpisać adres nowo
przydzielonego obszaru,
10.1.4 Przeglądanie listy
Algorytm
1. Ustaw wskaz
nik roboczy na pierwszym elemencie listy.
2. Jeśli wskaz
nik ma wartość NULL, przerwij.
3. Wypisz element wskazywany przez wskaz
nik.
4. Przesuń wskaz
nik na element, który jest wskazywany przez pole nast.
5. Wróć do punktu 2.
10.1.5 Usuwanie elementu z listy.
Najprościej byłoby zrobić:
wsk->nast = wsk-> nast -> nast
ale wtedy element, na który wskazywał wcześniej wsk-> nast przestaje być dostępny i
zaśmieca pamięć. Trzeba go usunąć. Zauważmy, że aby usunąć element potrzebujemy
wskaz
nika do elementu go poprzedzającego (po to, by nie rozerwać listy).
Dodając nowe elementy do listy zmuszeni byliśmy do dynamicznego przydzielania im
pamięci przy każdorazowym utworzeniu nowego elementu za pomocą funkcji malloc.
Przed zakończeniem działania programu obowiązkiem programisty jest zwolnienie uprzednio
przydzielonego obszaru pamięci. Do tego celu użyjemy funkcji free. Zauważmy, że nie
wolno nam bezpośrednio usunąć początkowego elementu listy, wskazywanego przez glowa,
gdyż w takim wypadku utracilibyśmy wskaz
niki do pozostałej części listy. Wykorzystamy
zmienną pomocniczą p typu LISTA, aby bezpiecznie usunąć element z listy.
Cała operacja będzie miała następujący przebieg:
a) zmienna p wskazuje na początek listy;
p = lista;
b) lista wskazuje na element następny
lista = lista->nast;
c) usuń bezpiecznie element p;
free(p);
4
Podstawy programowania. Wykład 10  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
10.2 Przykład
Program, który:
1. generuje n liczb losowych.
2. tworzy z nich listę z dowiązaniami
a. w porządku, w jakim zostały wygenerowane
b. dodając kolejną na początek
c. dodając kolejną w kolejności rosnącej  lista jest stale uporządkowana
d. dodając kolejną po N elementach
3. wyświetla tę listę.
#include
#include
#include
typedef struct lista
{
int co;
struct lista *nast; /* wskaznik do nastepnego elementu listy */
} Lista;
void InicjujListe(Lista ** glowa); /* inicjuje pusta liste wskazywana przez glowa */
void DodajNaKoncu(int i, Lista** glowa); /* dodaje pozycje na koncu listy wskazywanej
przez glowa */
void DodajNaPoczatku(int i, Lista** glowa); /* dodaje pozycje na poczatku listy
wskazywanej przez glowa */
void DodajWKolejn(int i, Lista** glowa); /* dodaje pozycje w kolejności rosnącej listy */
/* wskazywanej przez glowa */
5
Podstawy programowania. Wykład 10  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
void WstawPoN (int i, Lista **glowa, int N);
void WyswietlListe(Lista * glowa); /* wyswietla liste wskazywana przez glowa */
int main()
{
const int ileLiczb = 10;
Lista *glowa;
int iSecret;
int co, ktory, i;
InicjujListe(&glowa);
/* inicjuj generacje liczb losowych */
srand ( time(NULL) );
for (i = 0; i iSecret = rand() % 100 + 1;
printf( "wstawiam %d \n",iSecret);
DodajWKolejn(iSecret, &glowa);
WyswietlListe(glowa);
}
WyswietlListe(glowa);
for (i=0; i<4; ++i){
printf("Co wstawiamy ");
scanf("%d", &co);
printf( "Po ktorym elemencie ");
scanf("%d", &ktory);
printf( "**** wstawiam %d po elemencie %d \n", co, ktory);
WstawPoN(co, &glowa, ktory);
WyswietlListe(glowa);
}
return 0;
}
void InicjujListe(Lista ** glowa)
/* inicjuje pusta liste wskazywana przez glowa */
{
*glowa = NULL;
}
void DodajNaKoncu(int i, Lista** glowa)
/* dodaje pozycje na koncu listy */
/* wskazywanej przez glowa */
{
Lista *pom;
Lista *nowy;
/* szukam końca listy; */
6
Podstawy programowania. Wykład 10  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
pom = *glowa;
if (*glowa !=NULL)
while (pom -> nast != NULL) pom = pom -> nast;
/* pom wskazuje na ostatni element listy */
/* tworze i wypelniam nowy elem */
nowy = malloc( sizeof(Lista));
nowy -> co = i;
nowy -> nast = NULL;
/* wstawiam na koniec listy */
if (*glowa !=NULL)
pom -> nast = nowy;
else
*glowa = nowy;
}
void DodajWKolejn(int i, Lista **glowa)
/* dodaje pozycje w kolejnosci rosnacej - lista caly czas uporzadkowana */
/* wskazywanej przez glowa */
{
Lista *pom, *poprz = NULL;
Lista *nowy;
/* tworze i wypelniam nowy elem */
nowy = malloc( sizeof(Lista));
nowy -> co = i;
nowy -> nast = NULL;
pom = *glowa;
if (*glowa !=NULL)
{
/* szukam miejsca do wstawienia nowego elementu; */
while (pom -> nast != NULL && pom->co < i)
{poprz = pom;
pom = pom -> nast;
}
/* pom wskazuje na ostatni element listy albo wiekszy lub rowny */
if (pom->co >= i){
if ( poprz!=NULL) { /*dodaje w srodek */
poprz->nast = nowy;
nowy -> nast = pom;
}
else /* dodaje na poczatku */
{
nowy -> nast = pom;
*glowa = nowy;
}
7
Podstawy programowania. Wykład 10  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
}
else
if (pom->nast ==NULL)
pom ->nast = nowy;
else
{
nowy -> nast = pom;
if (poprz != NULL)
poprz ->nast = nowy;
}
/* wstawiam na koniec listy */
}
else /* *glowa == NULL */
*glowa = nowy;
}
void DodajNaPoczatku(int i, Lista** glowa)
/* dodaje pozycje na poczatku listy */
/* wskazywanej przez glowa */
{
Lista *pom;
Lista *nowy;
/* tworze i wypelniam nowy elem */
nowy = malloc ( sizeof(Lista));
nowy -> co = i;
/* wstawiam na poczatek listy */
if (*glowa !=NULL)
nowy -> nast = *glowa;
else
nowy -> nast = NULL;
*glowa = nowy;
}
void WyswietlListe(Lista* glowa)
/* wyswietla liste wskazywana przez glowa */
{
Lista *pom;
/* ide do konca listy; */
printf( "Wyswietlam liste\n");
pom = glowa;
while (pom != NULL) {
printf( "%d\t", pom -> co);
pom = pom -> nast;
}
putchar('\n');
8
Podstawy programowania. Wykład 10  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
}
void WstawPoN (int i, Lista **glowa, int N){
/* Lista moze byc pusta!! */
/* przechodzi N elementow listy o ile istnieja */
/* po N wstawia */
/* Jezeli wczesniej koniec listy to komunikat */
int k= 0;
Lista *pom = *glowa;
Lista *poprz = NULL;
Lista *nowy;
/* tworze i wypelniam nowy elem */
nowy = malloc ( sizeof(Lista));
nowy -> co = i;
if (N <0) printf( "N ujemne\n");
else
if (*glowa == NULL)
printf( "Lista pusta\n");
else /* lista niepusta */
{
while (knast != NULL)
{
poprz = pom;
pom = pom -> nast;
++k;
}
if (pom->nast == NULL && k printf( "Lista zbyt krotka\n");
else
if (pom->nast == NULL && k==N) /*wstawiam na koncu */
{
printf("*** na koniec \t");
pom->nast = nowy;
nowy -> nast = NULL;
}
else
if (poprz == NULL && k==N)/* wstawiam na poczatku */
{
printf("*** na poczatek \t");
*glowa = nowy;
nowy ->nast = pom;
}
else
if (pom->nast != NULL && k==N) /* N jest wewnatrz listy */
{
printf("*** w srodek \t");
9
Podstawy programowania. Wykład 10  listy dowiązaniowe
Małgorzata Nalbach-Moszyńska
poprz->nast = nowy;
nowy ->nast = pom;
}
else
if (pom->nast ==NULL) /* wstawiam na koncu */
{
printf("*** na koniec 2\t");
pom->nast = nowy;
nowy->nast = NULL;
}
}
}
10