C++ - Lista jednokierunkowa

Ten post będzie dotyczył zastosowania oraz wykonania listy jednokierunkowej.

Opis

Lista jednokierunkowa daje możliwość grupowania dowolnej liczby elementów. Jedynym ograniczeniem dla niej jest ilość dostępnej pamięci. Jak jej nazwa wskazuje można ją przeglądać tylko w jedną stronę tzn, od początku do końca. 

W celu jej budowy wykorzystuje się dwa typy komórek pamięci. Jeden z nich zawiera wskaźnik do początku oraz do końca listy. Drugi typ natomiast zawiera pole z wartością oraz wskaźnik na kolejny element z listy.

Działanie jest dosyć proste. Jeżeli na liście nie znajdują się żadne informacje to występują dwa wskaźniki do wartości typu NULL. Jest on pewnym adresem, nie koniecznie równym zero, na który żadna z występujących zmiennych nie będzie wskazywać. 

Czyli każdy z elementów listy będzie się składać z wartości oraz wskaźnika na kolejny element.

Konstruktor mógłby wyglądać w następujący sposób:

1. struct Produkt
2. {
3.     string Nazwa;
4.     string Opis;
5.     int ID;
6.     float Cena;
7.  
8.     //wskazanie na kolejny element z listy
9.     Produkt *nastepny;
10.  
11.     //Stworzony konstruktor
12.     Produkt()
13.     {
14.         // wczytujemy dane
15.         cout << "Nazwa - ";
16.         cin >> Nazwa;
17.         cout << "Opis - ";
18.         cin >> Opis;
19.         cout << "ID produktu - ";
20.         cin >> ID;
21.         cout << "Cena - ";
22.         cin >> Cena;
23.  
24.         //wskazniki ustawiamy na NULL
25.         nastepny = NULL;
26.     }
27.  
28.     void wypisz()
29.     {
30.         cout << "Nazwa - " << Nazwa << "Opis - " << Opis << "ID produktu - " << ID << "Cena - " << Cena << endl;
31.     }
32. };

Struktura powinna zawierać definicję poszczególnych składowych. Kolejnym elementem jest wskaźnik na następny element listy. Ostatnimi elementami są konstruktory powiązane z struktura.

Na liście można dokonywać następujących operacji:

Dodawanie elementu do listy, po czym następuje segregowanie elementów i sprawdzanie czy już nie ma takiego samego na liście:

1. void DodajProdukt(Produkt **poczatek)
2. {
3.     //Tworzenie nowego produktu
4.     Produkt *nowa;
5.     nowa = new Produkt;
6.  
7.     //Zdefiniownaie pomocniczych wskazników
8.     Produkt *zmiennapomocnicza = (*poczatek);
9.     Produkt *zmiennapomocnicza2 = NULL;
10.  
11.     // dopoki nie wyszlismy za liste i nazwisko na liscie jest przed nowym nazwiskiem poruszamy sie dalej
12.     while (zmiennapomocnicza != NULL && (zmiennapomocnicza->Nazwa).compare(nowa->Nazwa) == -1)
13.     {
14.         //Wskazanie na poprzedni element
15.         zmiennapomocnicza2 = zmiennapomocnicza;
16.         zmiennapomocnicza = zmiennapomocnicza -> nastepny;
17.     }
18.  
19.     //Produkt o takiej nazwie znajduje się juz na liscie
20.     if (zmiennapomocnicza != NULL && (zmiennapomocnicza->Nazwa).compare(nowa->Nazwa) == 0)
21.     {
22.         cout << "Produkt" << nowa->Nazwa << " juz istanieje w wizytowniku\n";
23.         //Usunięcie nowego produktu
24.         delete nowa;
25.     }
26.     //Nowy element znajdzie sie na poczatku listy
27.     else if ((*poczatek) == NULL || (zmiennapomocnicza == (*poczatek) && (zmiennapomocnicza->Nazwa).compare(nowa->Nazwa) == 1))
28.     {
29.         nowa->nastepny = (*poczatek);
30.         (*poczatek) = nowa;
31.     }
32.     //Element zostanie dodany w innym miejscu listy
33.     else
34.     {
35.         zmiennapomocnicza2 -> nastepny = nowa;
36.         nowa -> nastepny = zmiennapomocnicza;
37.     }
38. }

Poniżej pojedyncza funkcja pozwalająca na umieszczenie elementu na początku listy:

1. int DodajNaPoczatek(Produkt **poczatek)
2. {
3.      Produkt *nowa;
4.      nowa = new Produkt;
5.  
6.      Produkt *zmiennapomocnicza = (*poczatek);
7.      Produkt *zmiennapomocnicza2 = NULL;
8.  
9.      zmiennapomocnicza->Nazwa;
10.  
11.      if (nowa==NULL)
12.      {
13.         cout << "Brak wolnej pamieci";
14.         return 1;
15.      }
16.  
17.      nowa->nastepny = (*poczatek);
18.      (*poczatek) = nowa;
19.      return 0;
20. }

Dodawanie elementu w środku lub na końcu listy:

1. int DodajZaBiazacy(Produkt **poczatek)
2. {
3.      Produkt *nowa;
4.      nowa = new Produkt;
5.  
6.      Produkt *zmiennapomocnicza = (*poczatek);
7.      Produkt *zmiennapomocnicza2 = NULL;
8.  
9.      zmiennapomocnicza->Nazwa;
10.  
11.      if (nowa==NULL)
12.      {
13.         cout << "Brak wolnej pamieci";
14.         return 1;
15.      }
16.  
17.      zmiennapomocnicza2 -> nastepny = nowa;
18.      nowa -> nastepny = zmiennapomocnicza;
19.  
20.      return 0;
21. }

Wyszukiwanie produktu:

1. void SzukajProduktu(Produkt *poczatek, string szukany)
2. {
3.     //Przeszukiwanie listy element po elemencie, do mommentu znalezienia pasujacego lub
4.     //zakonczenia listy
5.     do
6.     {
7.        poczatek = poczatek->nastepny;
8.     }while(poczatek != NULL && (poczatek->Nazwa).compare(szukany) != 0);
9.  
10.     if (poczatek == NULL)
11.     {
12.         cout << "Nie znaleziono produktu " << szukany << endl;
13.     }
14.     else
15.     {
16.         poczatek->wypisz();
17.     }
18. }

Wypisanie szukanych elementów:

1. void WypiszProdukt(Produkt *poczatek)
2. {
3.     cout << "Produkty zdefioniowane w liscie: \n";
4.  
5.     //Perla dziala az do konca listy
6.     while(poczatek != NULL)
7.     {
8.         poczatek->wypisz();
9.         poczatek = poczatek->nastepny;
10.     }
11. }

Usuniecie zadanego elementu:

1. bool UsunProdukt(Produkt **poczatek, string UsuwanyProdukt)
2. {
3.     //Lista nie zawiera elementow
4.     if (*poczatek == NULL)
5.     {
6.         return false;
7.     }
8.     //Pomocnicze elementu
9.     Produkt *zmiennapomocnicza = (*poczatek), *zmiennapomocnicza2 = NULL;
10.  
11.     while(zmiennapomocnicza != NULL && (zmiennapomocnicza->Nazwa).compare(UsuwanyProdukt) != 0) // dopoki nie znajdziemy wizytowki z podanym nazwiskiem lub nie przeszukamy calego wizytownika
12.     {
13.         zmiennapomocnicza2 = zmiennapomocnicza;
14.         zmiennapomocnicza = zmiennapomocnicza->nastepny;
15.     }
16.  
17.     //Nie ma nazwiska na liscie
18.     if (zmiennapomocnicza == NULL)
19.     {
20.         return false;
21.     }
22.     else if (zmiennapomocnicza == (*poczatek))
23.     {
24.         (*poczatek) = (*poczatek)->nastepny;
25.         delete zmiennapomocnicza;
26.     }
27.     //Usuniecie ze srodka lub konca listy
28.     else
29.     {
30.         zmiennapomocnicza2->nastepny = zmiennapomocnicza->nastepny;
31.         delete zmiennapomocnicza;
32.     }
33.     return true;
34. }

Można te funkcje uprościć i usunąć pierwszy z listy poprzez wywołanie następującej funkcji:

1. void UsunPoczatek(Produkt *&poczatek)
2. {
3.      Produkt *nowa;
4.      nowa = new Produkt;
5.  
6.      poczatek = nowa->nastepny;
7.      free(nowa);
8. }

Usuwanie całej listy:

1. void UsunWszystkie(Produkt *&poczatek)
2. {
3.     Produkt *nowa;
4.     while (poczatek != NULL)
5.     {
6.         nowa = poczatek;
7.         poczatek = nowa->nastepny;
8.         free(nowa);
9.     }
10. }

Bibliografia

[1] Algorytmy i złożoności Wykład 3. Listy jednokierunkowe
[2] Algorytmy, struktury danych i techniki programowania, Wróblewski, Wyd 3