Algorytmy i struktury danych

Laboratorium 5

Listy

Listy

Listą nazywamy uporządkowany zbiór składników, z którego w dowolnym miejscu można
usunąć dany składnik lub dodać nowy. W zależności od typu powiązań pomiędzy składnikami
listy wyróżniamy: listy jednokierunkowe, dwukierunkowe, cykliczne.

Lista jednokierunkowa

Dodawanie nowego składnika do listy

Algorytmy i struktury danych

Laboratorium 5

Listy

Usuwanie wybranego składnika z listy

Lista dwukierunkowa

typedef struct Element_listy
{
// dane
int zmienna1;
float zmianna2;
// ... inne dane
// wskaźnik na następny element listy
struct Element_listy *wskaznik1;
} Lista;

Plik nagłówkowy

#include<list>

Stworzenie pustej listy

list<typ> nazwa;

np.:

list<int> liczby;

Algorytmy i struktury danych

Laboratorium 5

Listy

Operacje na listach:

size() – zwraca aktualną liczbę elementów listy;
empty() – zwraca informację czy lista jest pusta;
front() – zwraca pierwszy element listy;
back() – zwraca ostatni element listy;
begin() – zwraca iterator dla pierwszego elementu listy;
end() – zwraca iterator dla ostatniego elementu listy;
push_back() – dołącza kopię elementu na końcu listy;
push_front() – dołącza kopię elementu na początku listy;
pop_back() – usuwa ostatni element listy;
pop_front() – usuwa pierwszy element listy;
insert() – dołącza kopię elementu w środku listy;
erase() – usuwa element w środku listy;
clear() – usuwa wszystkie elementy z listy.

Np.:

int main()
{
list<int> liczby; //stworzenie listy przechowującej liczby
int r;
r=liczby.size(); //sprawdzenie rozmiaru listy
liczby.push_front(1); //dodanie na początek listy liczby 1

cout<<r<<endl;
}

Deklaracja iteratora:

list<typ>::iterator nazwa;

Np.:

int main()
{
list<int> liczby;
list<int>::iterator wsk;
for(wsk=liczby.begin();wsk!=liczby.end();wsk++)
cout<<*wsk<<endl;
}

1. Zadania

Zadanie 1.

Stwórz listę zawierającą znaki, a następnie:

a) sprawdź rozmiar listy oraz wyświetl informację czy lista jest pusta;
b) dodaj do końca listy 3 dowolne znaki;
c) dodaj na początek listy 2 dowolne znaki;
d) wyświetl informację o rozmiarze listy oraz czy lista jest pusta;

Algorytmy i struktury danych

Laboratorium 5

Listy

e) wyświetl pierwszy i ostatni element listy;
f) wyświetl całą zawartość listy;
g) usuń pierwszy element listy;
h) wyświetl całą zawartość listy;
i) usuń ostatni element listy;
j) wyświetl całą zawartość listy.