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