Studia Licencjackie / Inżynierskie

Algorytmy i struktury danych

Wykład nr 4, część II

Listy

Załóżmy, że chcemy przechowywać dane (np. osobowe), przy czym:

-

nie jest z góry znany rozmiar danych (np. liczba osób)

-

dość często niektóre informacje są usuwane i dodawane są nowe.

Wówczas, zastosowanie tablic pociąga za sobą następujące problemy:

-

konieczne jest zadeklarowanie („zajęcie”) rozmiaru tablicy odpowiadającego maksymalnemu
przewidywanemu rozmiarowi danych;

-

każda operacja wstawiania i usuwania wymaga przemieszczania znacznej części danych.

M.in. w takich sytuacjach, stosujemy listy. Z punktu widzenia typów danych, możliwość utworzenia listy
wymaga jedynie utworzenia typu struktur zawierających (oprócz danych „właściwych”) jednego specyficznego
pola oznaczającego wskaźnik na następny element listy.

Na przykład:

struct elem {

char nazw[dlnazw];

//dane wlasciwe: nazwisko i wiek

int wiek

struct elem *nast;

// wskaznik na nastepny element

};

Przypomnijmy, że deklaracja

TYP *ZMIENNA;

tworzy zmienną, która jest wskaźnikiem na element typu

TYP

. A zatem

int *i;

oznacza, że zmienna

i

jest wskaźnikiem na element typu

int

, a

struct elem *nast; // wskaznik na nastepny element

oznacza, że zmienna

nast

jest wskaźnikiem na element typu

struct elem

. Natomiast zadeklarowanie

nast

jako pola struktury typu

struct elem

pozwoli nam tworzyć listy.

Dostęp do listy uzyskujemy poprzez wskaźnik na jej pierwszy element:

struct elem *lis;

Zauważmy, zadeklarowana powyżej zmienna

lis

ma taki sam typ jak pole

nast

w strukturze

struct

elem

.

Przykład

lis

↓

nazw

Kowal

nazw

Nowak

nazw

Smith

nazw

Ondracek

wiek

25

wiek

17

wiek

44

wiek

17

nast.

→→→

→→

nast.

→→→

→→

nast

→→→

→→

nast.

NULL

Jak powstaje lista...

Zadeklarowanie zmiennej

struct elem *lis;

nie powoduje utworzenia struktury typu

struct elem

a jedynie zmiennej, która jest wskaźnikiem na taką

strukturę. Utworzenie struktury wymaga zaalokowania pamięci:

lis = (struct elem *) malloc(sizeof(struct elem));

gdzie:

-

malloc(i)

rezerwuje pamięć o rozmiarze

i

„jednostek pamięci”

-

sizeof(TYP)

podaje liczbę jednostek pamięci zajmowanych przez elementy typu TYP

-

(struct elem *)

to rzutowanie typu, które powoduje, że wynik funkcji

malloc(...)

traktowany będzie jako wskaźnik na element typu

struct elem

.

Odwołania do pól struktur raz jeszcze...

Mamy następujące deklaracje:

struct elem x;

struct elem *y;

A zatem odwołania do pól wyglądają następująco:

x.nazw

*y.nazw

x.wiek

*y.wiek

x.nast

*y.nast

operator

*

przy

y

jest konieczny, ponieważ

y

nie jest strukturą lecz jedynie wskaźnikiem na nią.

Jednak zapis ten ma inną, bardziej intuicyjną alternatywę:

*y.nazw

y->nazw

*y.wiek

y->wiek

*y.nast

y->nast

Przykład – program umieszczaj

ą

cy dane o osobach na li

ś

cie

W pliku dane.txt umieszczamy informacje o osobach w nastepujacym formacie:

-

pierwszy wiersz pliku zawiera jedną liczbę – liczbę osób

-

każdy kolejny wiersz pliku zawiera nazwisko o osoby i jej wiek, oddzielone spacją.

Poniżej prezentujemy program, który dane z pliku umieszcza w liscie i wypisuje je na ekran.

#include <stdio.h>
#include <stdlib.h>
#define dlnazw 10
#define llat 100

/* lista nazwisk osob i ich wiek */

struct dana {
char nazw[dlnazw];
int wiek;
struct dana *nast;
};

struct dana *lis;//lis oznacza poczatek listy

int n;

void czyt(void)
{int i,wiek;
char nazwisko[dlnazw];
struct dana *x;
lis=NULL;

//na poczatku lista jest pusta

printf("Ile osob : "); scanf("%d\n", &n);
for (i=0; i<n; i++)
{ x=(struct dana *) malloc(sizeof(struct dana));
printf("Podaj nazwisko : ");
scanf("%s", x->nazw);

//bez kontroli dlugosci!!!

printf("Podaj wiek : ");
scanf("%d", &x->wiek);
x->nast=lis;

//”podpinamy” liste do nowego elementu

lis=x;

//zmieniamy wskaznik na poczatek listy

}
}

void druk(void)
{int i;
struct dana *x, *pom;
x=lis;
printf("\n");
while (x!=NULL)
{ printf("%s %d\n",x->nazw,x->wiek);
pom=x;
x=x->nast;

//przesuwamy si

ę

na nastepny element listy

free(pom);

// zwalniamy pamiec

}
}

main()
{
czyt();
druk();
}

Przykład – tablica list

Dla danych jak w powyższym zadaniu,

-

chcemy pogrupować je wg wieku osób (kolejność osób o tym samym wieku może być dowolna)

-

dodawanie nowego elementu nie powinno być kosztowne (bez przesuwania danych...).

Rozwiążemy ten problem poprzez:

-

utworzenie tablicy list

struct dana *tab[llat];

-

lista

tab[i]

przechowuje informacje o osobach w wieku

i

lat; dodawanie nowej osoby w wieku

i

lat polega na wstawieniu jej na początek listy

tab[i]

.

-

skoro wiek osoby wynika z tego na jakiej liście ją umieściliśmy, możemy usunąć pole

wiek

ze

struktury.

#include <stdio.h>
#include <stdlib.h>
#define dlnazw 10
#define llat 100

/* tablica list ;
i-ty element tablicy jest poczatkiem listy osob
w wieku i lat */

struct dana {
char nazw[dlnazw];
int wiek;
struct dana *nast;
};

struct dana *tab[llat];

int n;
FILE *fi, *fo;

void init()

// zainicjowanie pustych list; czasem NULL to wartosc domyslna

{ int i;
for (i=0; i<llat; i++) tab[i]=NULL;
}

void czytslowo(char *slowo)
{ int i=0;
char ch;
while (i<dlnazw && (ch=fgetc(fi))!=' ')
slowo[i++]=ch;
slowo[i]='\0';
}

void czyt(void)
{int i,wiek;
char nazwisko[dlnazw];
struct dana *x;

init();
fscanf(fi, "%d\n", &n);
for (i=0; i<n; i++)

{ x=(struct dana *)malloc(sizeof(struct dana));
czytslowo(x->nazw);
fscanf(fi, "%d\n",&wiek);
x->nast=tab[wiek];
tab[wiek]=x;
}
}

void druk(void)
{int i;
struct dana *x;
printf("\n");
for (i=0;i<llat; i++)
{while ((x=tab[i])!=NULL)
{ printf("%s %d",x->nazw,i);
tab[i]=x->nast;
free(x);
printf("\n");
}
}
}

main()
{
fi=fopen("Dane.txt","r");
fo=fopen("Wynik.txt","w");
czyt();
druk();
fclose(fi);
fclose(fo);
}

Listy ogólniej

Dotychczas prezentowane programy modyfikowały listę bądź tablicę list, które były zmiennymi globalnymi.
Teraz chcielibyśmy stworzyć uniwersalne funkcje, które wstawiają elementy do dowolnej listy ustalonego typu.

Jak poprzednio, będziemy wykonywać operacje na listach zdefiniowanych przez typ:

struct dana {
char nazw[dlnazw];
int wiek;
struct dana *nast;
};

Najpierw wprowadzimy funkcję, która tworzy jednoelementową listę o podanym nazwisku i wieku:

struct dana *utworz(int wiek, char *nazwisko)

{

//

utworzenie nowej jednoelementowej listy z danymi wiek i nazwisko

struct dana *pom;
int i;

pom=(struct dana *) malloc(sizeof(struct dana));

for(i=0; nazwisko[i]!='\0'; i++)

//przepisanie nazwiska

pom->nazw[i] = nazwisko[i];
pom->nazw[i] = nazwisko[i];
pom->wiek = wiek;

// pom->wiek i wiek to co innego!

pom->nast = NULL;
return pom;
}

Wydzieliliśmy tę funkcję osobno, aby pozostałe funkcje były niezależne od tego, jakie elementy zawiera
pojedyncza struktura wchodząca w skład listy.

Poniższa funkcja wstawia nowy element na początek listy:

struct dana *wstawPocz(struct dana *lista, struct dana *nowy)
{

// nowy nie moze miec wartosci NULL

// nowy

dodajemy na poczatek listy

lista

nowy->nast = lista;
return nowy;
}

Zauważmy, że typ obu powyższych funkcji to

struct dana *

-

w pierwszym przypadku wynik to wskaźnik na nowo utworzoną strukturę;

-

w drugim przypadku wynikiem jest wskaźnik na listę powstałą przez wstawienie elementu

*nowy

na

początek listy na którą wskazuje

lista

.

Funkcja tworząca listę elementów pobranych z pliku i wykorzystująca powyższe funkcje może wyglądać
następująco:

struct dana *czyt()
{

//elementy z pliku umieszczane na liscie

//kolejnosc na liscie odwrotna ni

ż

w pliku

int i,aktwiek;
char aktnazwisko[dlnazw];
struct dana *x, *lista;

lista=NULL;
fscanf(fi, "%d\n", &n);
for (i=0; i<n; i++)
{
czytslowo(aktnazwisko);
fscanf(fi, "%d\n",&aktwiek);
x=utworz(aktwiek, aktnazwisko);

lista = wstawPocz(lista, x);

}
return lista;
}

Aby osoby zostały uporządkowane według wieku, wystarczy wymienić wywołanie funkcji

wstawPocz(lista, x);

na

wstawPorzadek(lista, x);

o następującej treści:

struct dana *wstawPorzadek(struct dana *lista, struct dana *nowy)
{

// nowy nie moze miec wartosci NULL

// wstawia wg wieku niemalejaco

struct dana *pom;
int pwiek;

if (lista==NULL || lista->wiek >= nowy->wiek){
nowy->nast = lista;
return nowy;}
else {
pom=lista; pwiek = nowy->wiek;
while (pom->nast != NULL && pom->nast->wiek < pwiek)
pom=pom->nast;
nowy->nast=pom->nast;
pom->nast=nowy;
return lista;
}
}

Komentarze:

-

warunek

(lista==NULL || lista->wiek >= nowy->wiek)

opisuje przypadki, w których

nowy element powinien być umieszczony na początku listy;

-

w pozostałych przypadkach chcemy „zatrzymać” przeglądanie (czyli wartość

pom

) na elemencie

poprzedzającym miejsce, w które należy wstawić nowy element; zauważmy, że dla tego elementu
zmieni się jego następnik:

Listy – usuwanie elementów

Poniżej prezentujemy funkcję, która usuwa element o podanej wartości pola

wiek

z nieuporządkowanej listy

struktur typu struct dana *

struct dana *usun(struct dana *lista, int uwiek)
{

// usuniecie pierwszej osoby o wskazanym wieku

struct dana *pom, *poprz;

pom = lista;

while (pom != NULL && pom->wiek != uwiek){

//poszukiwanie elementu o wieku uwiek

poprz = pom;

pom = pom->nast;

}

if (pom != NULL)

// na liscie wystapil uwiek

if (pom == lista) {

//do usuniecia pierwszy element

lista=lista->nast;

free(pom);

}

else {

// tworzymy powiazanie omijajace usuw.el.

poprz->nast = pom->nast;

pom

lista

nowy

free(pom);

}

return lista;

}

Komentarz:

-

pierwsza pętla przechodzi przez listę w poszukiwaniu elementu o wartości pola

wiek

równej

uwiek

;

-

usunięcie elementu z listy wymaga zmiany następnika jego poprzednika, dlatego pierwsza pętla
przechowuje wskaźnik na element poprzedni w zmiennej

poprz

;

-

w sytuacji, gdy usuwamy pierwszy element, zmianie musi też ulec wartość wskaźnika na początek listy.

poprz

pom

lista

Aby uniknąć pamiętania zawsze wskaźników na element „aktualny” i „poprzedni”, możemy zastosować metodę
użytą wcześniej przy wstawianiu elementu: pamiętamy tylko „element poprzedni” i sprawdzamy, czy do
usunięcia jest jego następnik:

struct dana *usun2(struct dana *lista, int uwiek)
{

// usuniecie pierwszej osoby o wskazanym wieku

struct dana *pom, *pom2;

if (lista == NULL) return NULL;
if (lista->wiek == uwiek) {

//do usuniecia pierwszy element

pom = lista;
lista = lista->nast;
free(pom);
return lista;}
pom = lista;
while (pom->nast != NULL && pom->nast->wiek != uwiek)

pom = pom->nast;

//poszukiwanie elementu o wieku uwiek

if (pom->nast != NULL){

//wystepuje element o wieku uwiek

pom2 = pom->nast;
pom->nast = pom2->nast;
free(pom2);
}
return lista;
}

Komentarze:

-

teraz zmienna

pom

ma zawsze wskazywać na element już sprawdzony, czyli różny od

uwiek

-

dlatego na początku osobno traktujemy przypadek gdy lista jest pusta bądź jej pierwszy element jest do
usunięcia.

Operacje na listach rekurencyjnie

Korzystamy z następującego typu:

struct dana {
char nazw[dlnazw];
int wiek;
struct dana *nast;
};

Najpierw wprowadzimy funkcję, która tworzy jednoelementową listę o podanym nazwisku i wieku:

struct dana *utworz(int wiek, char *nazwisko)

{

//

utworzenie nowej jednoelementowej listy z danymi wiek i nazwisko

struct dana *pom;
int i;

pom=(struct dana *) malloc(sizeof(struct dana));

for(i=0; nazwisko[i]!='\0'; i++)

//przepisanie nazwiska

pom->nazw[i] = nazwisko[i];
pom->nazw[i] = nazwisko[i];
pom->wiek = wiek;

// pom->wiek i wiek to co innego!

pom->nast = NULL;
return pom;
}

Wydzieliliśmy tę funkcję osobno, aby pozostałe funkcje były niezależne od tego, jakie elementy zawiera
pojedyncza struktura wchodząca w skład listy.


Wypisywanie elementów:

void drukRek(struct dana *lista)
{
if (lista != NULL){
printf("%d\n", lista->wiek);
drukRek(lista->nast);
}
}

Wstawianie elementu do listy uporządkowanej:

struct dana *wstawPorzadekRek(struct dana *lista, struct dana *nowy)
{

// wstawia element,na który wskazuje nowy

// nowy nie moze miec wartosci NULL

// wstawia wg wieku niemalejaco

struct dana *pom;
int pwiek;

if (lista==NULL || lista->wiek >= nowy->wiek){
nowy->nast = lista;
return nowy;}
else {
pom = wstawPorzadekRek(lista->nast,nowy);
lista->nast = pom;
return lista;
}
}

Usuwanie elementu z listy (nie korzystamy z uporządkowania):

struct dana *usunRek(struct dana *lista, int uwiek)
{

// usuniecie pierwszej osoby o wskazanym wieku

// z listy nieuporzadkowanej

struct dana *pom, *pom2;

if (lista != NULL)
if (lista->wiek == uwiek) {

//do usuniecia pierwszy element

pom = lista;
lista = lista->nast;
free(pom); }
else{
pom = usunRek(lista->nast, uwiek);
lista->nast = pom;
}
return lista;
}

Listy a tablice:

Lista

Tablica

dostęp do elementu na określonej pozycji wymaga
czasu proporcjonalnego do odległości od początku listy

dostęp do elementu na określonej pozycji w czasie
niezależnym od rozmiaru tablicy

zajętość pamięci jest proporcjonalna do aktualnej
liczby elementów

zajęta pamięć jest proporcjonalna do rozmiaru tablicy

wyszukanie elementu wymaga liniowego czasu
(proporcjonalnego do liczby elementów na liście)

wyszukiwanie w czasie liniowym, ale w przypadku
uporządkowania elementów w tablicy, wyszukanie
elementu możliwe jest w czasie logarytmicznym

usunięcie wskazanego elementu lub wstawienie
elementu na wskazanej pozycji można zrealizować w
czasie niezależnym od rozmiaru listy

usunięcie elementu znajdującego się na określonej
pozycji lub wstawienie elementu na wskazaną pozycję
wymaga czasu proporcjonalnego do liczby elementów
(konieczne przesuwanie elementów)

Usprawnienia i rozszerzenia:

•

Dodanie wartownika na końcu listy (przyspieszenie wyszukiwania).

•

Listę opisuje wskaźnik na pierwszy i na ostatni element na liście (umożliwia szybkie wstawianie na
koniec listy).

•

Lista dwukierunkowa (wskaźniki do następnego i poprzedniego elementu).