Struktury danych/Implementacje w C++/Listy

Z Wikibooks, biblioteki wolnych podręczników.
Przejdź do nawigacji Przejdź do wyszukiwania

Lista jednokierunkowa[edytuj]

Generyczna implementacja wskaźnikowa[edytuj]

  1 template <typename Type>
  2 // Implementacja listy jednokierunkowej.
  3 class List {
  4     struct Node { 
  5     // Zagnieżdżona klasa pomocnicza.
  6     Type  value;
  7         Node* next;
  8         Node(Type d) {      // Konstruktor jednoargumentowy.
  9             value = d;      // Przypisanie wartości podczas konstrukcji.
 10             next = nullptr;
 11         }
 12     };
 13 
 14     Node* head; // Wskaźnik do głowy listy.
 15     Node* tail; // Wskaźnik do ogona listy.
 16 
 17 public:
 18     List();  // Konstruktor listy.
 19     ~List(); // Destruktor listy.
 20 
 21     void insert(Type data); // Dodaje do listy w czasie O(1).
 22     void remove(int n);     // Usuwa n-ty element listy.
 23     Type find(int n);       // Zwraca wartosc z n-tego elementu listy.
 24     void clear();           // Usuwa wszystkie elementy z listy.
 25     void display();         // Funkcja wypisująca całą listę, elementy oddzielone spacją.
 26 };
 27 
 28 
 29 template <typename Type>
 30 List<Type>::List() {
 31     head = nullprt;
 32     tail = nullptr;
 33 }
 34 
 35 template <typename Type>
 36 List<Type>::~List() {
 37     Node* temp = head;
 38         while (temp != tail) {    // Do momentu kiedy nie natrafimy na ogon.
 39             head = temp->next;    // Podmieniamy head na następny element.
 40             delete temp;          // Usuwamy węzeł, na który wskazuje zmienna pomocnicza.
 41             temp = head;          // Idziemy dalej aż nie natrafimy na ogon.
 42 	}
 43     delete tail;                  // Usuwamy węzeł, na który wskazuje ogon.
 44 }
 45 
 46 template <typename Type>
 47 void List<Type>::insert(Type data){
 48     if (head != nullprt) {        // W przypadku gdy mamy jakieś elementy w liście.
 49         Node* temp = new Node(data);
 50         if (temp == nullprt) 
 51             throw "Błąd alokacji pamięci, przy dodawaniu elementu do listy!";
 52         tail->next = temp;
 53         tail = temp;
 54     }
 55     else {
 56         head = new Node(data);
 57         tail = head;
 58     }
 59 }
 60 
 61 template <typename Type>
 62 void List<Type>::remove(int n) {
 63     Node* temp = head;
 64     Node* prev = nullptr;
 65         for (int i=0; i<n; ++i){  // W pętli będziemy szukać elementu do usuniecia.
 66             if (temp != nullptr) {
 67 	        prev = temp;
 68 	        temp = temp->next;	
 69 	    }
 70 	    else
 71                 throw "Lista jest krótsza niż argument w remove!";
 72 	}
 73 
 74     // Przepinamy tutaj wskaźnik do następnego elementu poprzedniego rekordu listy
 75     // na ten, na który wskazywał element, który mamy usunąć
 76     // następnie go usuwamy.
 77     prev->next = temp->next;
 78     delete temp;
 79 }
 80 
 81 template <typename Type>
 82 Type List<Type>::find(int n) {
 83     Node* temp = head;
 84     for (int i=0; i<n; ++i) {   // W pętli będziemy szukać elementu do usuniecia.
 85         if (temp != nullptr)
 86 	    temp = temp->next;	
 87         else
 88             throw "Lista jest krótsza niż argument w remove!";
 89     }
 90     return temp->value;
 91 }
 92 
 93 template <typename Type>
 94 void List<Type>::clear() {
 95     Node* temp = head;
 96     while (temp != tail) {     // Do momentu kiedy nie natrafimy na ogon.
 97         head = temp->next;     // Podmieniamy head na następny element.
 98         delete temp;           // Usuwamy węzeł, na który wskazuje zmienna pomocnicza.
 99         temp = head;           // Idziemy dalej aż nie natrafimy na ogon.
100     }
101     delete tail;               // Usuwamy węzeł, na który wskazuje ogon.
102 	
103     head = nullptr;
104     tail = nullptr;
105 }
106 
107 template <typename Type>
108 void List<Type>::display() {
109     Node* i = head;
110     while (i!=nullptr) {
111         std::cout << i->wartosc << " ";
112         i=i->next;
113     }
114     std::cout << std::endl;
115 }