Informatyka rozszerzona. Dynamiczne struktury danych – lista jednokierunkowa, cz. 1

main.cpp

#include <iostream>

using namespace std;

// Lista jednokierunkowa – najprostsza struktura dynamiczna
// Program demonstrujący kilka prostych operacji na liście
// jednokierunkowej

// Definicja typu strukturalnego jako elementu listy
struct element {
    int wartosc;
    element *nastepny;
};

// Zmienna zawierająca wskaźnik na początek listy (glówę, ang. head)
// WAŻNE: nie można dopuścić do utraty wskaźnika przechowywanego w tej zmiennej!
element* glowa;

// Podstawowe operacje na liście jednokierunkowej
// – wyszukiwanie elementu listy o wskazanym indeksie
//   (podobnie, jak to ma miejsce w tablicy, ale póki co bez przeciążania
//   operatorów); indeksowanie od 0!
element* znajdz(int);
// – dodawanie nowego elementu na początek listy
element* dodaj_na_pocz(int);
// – dodawanie nowego elementu na koniec listy
element* dodaj_na_koniec(int);
// – zwracanie liczby wszystkich elementów listy
int licz_elementy();
// – usuwanie listy z pamięci
void niszcz();

int main()
{
    cout << "Dodawanie 100 elementów na początek listy..." << endl;

    for (int i = 0; i < 100; i++) {
      dodaj_na_pocz(i);
    }

    cout << "Dodawanie 100 elementów na koniec listy..." << endl;

    for (int i = 0; i < 100; i++) {
      dodaj_na_koniec(i);
    }

    cout << "Liczba elementów listy: " << licz_elementy() << endl;

    element* p = znajdz(0);
    cout << "Element nr 1 ma wartość: " << p->wartosc << endl;
    p = znajdz(99);
    cout << "Element nr 100 ma wartość: " << p->wartosc << endl;
    p = znajdz(100);
    cout << "Element nr 101 ma wartość: " << p->wartosc << endl;
    p = znajdz(199);
    cout << "Element nr 200 ma wartość: " << p->wartosc << endl;

    cout << "Wszystkie elementy listy (od początku do końca):" << endl;
    p = glowa;
    while (p != NULL) {
        cout << p->wartosc << endl;
        p = p->nastepny;
    }

    cout << "Usuwanie listy z pamięci..." << endl;
    niszcz();

    return 0;
}

element* znajdz(int indeks) {
    element* tmp = glowa;
    int i = 0;
    while (tmp != NULL) {
      if (i == indeks) {
        return tmp;
      }
      i++;
      tmp = tmp->nastepny;
    }
    return NULL;
}

element* dodaj_na_pocz(int wart) {
    element* tmp = new element;

    tmp->wartosc = wart;
    tmp->nastepny = glowa;

    glowa = tmp;

    return tmp;
}

element* dodaj_na_koniec(int wart) {
    element* tmp = glowa;

    // Odnajdujemy ostatni element listy
    while (tmp->nastepny != NULL) {
        tmp = tmp->nastepny;
    }

    // Tworzymy nowy element
//    element* nowy = new element;
//    nowy->wartosc = wart;
//    nowy->nastepny = NULL;
    // Dodajemy go do listy na jej koniec
//    tmp->nastepny = nowy;

    // Wersja bez zmiennej pomocniczej "nowy"
    tmp->nastepny = new element;
    tmp->nastepny->wartosc = wart;
    tmp->nastepny->nastepny = NULL;

    return tmp->nastepny;
//    return nowy;
}

int licz_elementy() {
    element* tmp = glowa;
    int licz = 0;

    while (tmp != NULL) {
      licz++;
      tmp = tmp->nastepny;
    }

    return licz;
}

void niszcz() {
    element* tmp = glowa;
    element* p = tmp->nastepny;

    while (p != NULL) {
       delete tmp;
       tmp = p;
       p = p->nastepny;
    }
}