aisd5-1

Studia Licencjackie / Inżynierskie

Algorytmy i struktury danych

Wykład nr 5, część I

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

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) // wstawia kolejne osoby na początek listy

{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) // wypisuje zawartosc listy

{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 120

struct dana {

char nazw[dlnazw];

int wiek;

struct dana *nast;

};

/* tablica list ;

i-ty element tablicy jest poczatkiem listy osob

w wieku i lat */

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

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 nowy do lista 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:

lista

pom

Listy – usuwanie elementów

nowy

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;

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;

lista

poprz

pom

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

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->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 do lista

// 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

dostęp do elementu na określonej pozycji w czasie

czasu proporcjonalnego do odległości od początku listy niezależnym od rozmiaru tablicy zajętość pamięci jest proporcjonalna do aktualnej

zajęta pamięć jest proporcjonalna do rozmiaru tablicy

liczby elementów

wyszukanie elementu wymaga liniowego czasu

wyszukiwanie w czasie liniowym, ale w przypadku

(proporcjonalnego do liczby elementów na liście)

uporządkowania elementów w tablicy, wyszukanie

elementu możliwe jest w czasie logarytmicznym

usunięcie wskazanego elementu lub wstawienie

usunięcie elementu znajdującego się na określonej

elementu na wskazanej pozycji można zrealizować w

pozycji lub wstawienie elementu na wskazaną pozycję

czasie niezależnym od rozmiaru listy

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).