Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- class Elem //komorka listy
- {
- private:
- int v; //key, data
- Elem* next_elem;
- Elem* prev_elem;
- public:
- Elem(); //tworzy pusty element
- Elem(int x); //tworzy element przechowujący x
- int value(); //zwraca wartość
- void setValue(int v); //ustawia wartość v
- Elem* next(); //zwraca następny element
- Elem* prev(); //zwraca poprzednielement
- void setNext(Elem* p); //ustawia p jako następny element
- void setPrev(Elem* p); //ustawia p jako poprzedni element
- };
- Elem::Elem()
- {
- next_elem = NULL;
- prev_elem = NULL;
- v = 0; //zeby byla jakas wartosc
- }
- Elem::Elem(int x)
- {
- next_elem = NULL;
- prev_elem = NULL;
- v = x;
- }
- int Elem::value()
- {
- return v;
- }
- void Elem::setValue(int v)
- {
- this->v = v; //stary v staje sie nowym v, element, do ktorego sie teraz konkretnie odwoluje
- }
- Elem* Elem::next()
- {
- return next_elem;
- }
- Elem* Elem::prev()
- {
- return prev_elem;
- }
- void Elem::setNext(Elem* p)
- {
- next_elem = p;
- }
- void Elem::setPrev(Elem* p)
- {
- prev_elem = p;
- }
- class SortedDLList //lista
- {
- private:
- Elem* head; //wskaźnik na pierwszy element list
- Elem* tail; //wskaźnik na ostatni element list
- int list_size; //długość listy, czyli inaczej liczba elementow listy
- public:
- SortedDLList(); //tworzy pustą listę
- bool empty(); //zwraca prawdę jeśli lista pusta, fałsz w przeciwnym przypadku
- int size(); //zwraca wielkość listy (liczbę elementów w liście)
- Elem* first(); //zwraca pozycję pierwszego elementu
- Elem* last(); //zwraca pozycję ostatniego elementu
- Elem* next(Elem* p); //zwraca pozycję elementu następnego za p
- Elem* prev(Elem* p); //zwraca pozycję elementu poprzedniego przed p
- int retrieve(Elem* p); //zwraca element z pozycji p
- Elem* locate(int x); //zwrac pozycję pierwszego wystąpienia elementu x, -1 jeśli x nie występuje
- void insert(int x); //wstawia x z zachowniem porządku
- void del(int x); //usuwa pierwsze wystąpienie element x
- void delALLx(int x); //usuwa wszystkie wystapienia elementu x
- void clear(); //usuwa całą listę
- friend ostream& operator<<(ostream& out, SortedDLList& l); //wypisuje elementu listy
- };
- SortedDLList::SortedDLList()
- {
- head = tail = NULL;
- list_size = 0;
- }
- bool SortedDLList::empty()
- {
- if (list_size == 0)
- {
- return true;
- }
- else
- {
- return false;
- }
- }
- int SortedDLList::size()
- {
- return list_size;
- }
- Elem* SortedDLList::first()
- {
- return head;
- }
- Elem* SortedDLList::last()
- {
- return tail;
- }
- Elem* SortedDLList::next(Elem* p)
- {
- if (empty())
- {
- return NULL;
- }
- if (head == tail)
- {
- return NULL;
- }
- if (p == tail)
- {
- return NULL;
- }
- return p->next();
- }
- Elem* SortedDLList::prev(Elem* p)
- {
- if (empty())
- {
- return NULL;
- }
- if (head == tail)
- {
- return NULL;
- }
- if (p == head)
- {
- return NULL;
- }
- return p->prev();
- }
- int SortedDLList::retrieve(Elem* p)
- {
- if (empty())
- {
- return NULL;
- }
- else
- {
- return p->value();
- }
- }
- Elem* SortedDLList::locate(int x)
- {
- if (empty())
- {
- return NULL;
- }
- Elem* p = head;
- while (p->value() != x)
- {
- if (p == tail)
- return NULL;
- p = p->next();
- }
- return p;
- }
- void SortedDLList::insert(int x)
- {
- if (empty())
- {
- head = new Elem(x); //wywolujemy drugi konstruktor, tworzymy nowy pierwszy element
- tail = head;
- head->setNext(NULL);
- head->setPrev(NULL);
- list_size++;
- }
- else
- {
- if (head->value() >= x) //tworze nowy element przed dotychczasowa head
- {
- Elem* p = new Elem;
- p->setValue(x);
- p->setPrev(NULL);
- head->setPrev(p);
- p->setNext(head);
- head = p;
- list_size++;
- }
- else
- {
- if (head == tail) //nowy element jest wiekszy od head, czyli tworze nowy tail, bo lista jest jednoelementowa
- {
- tail = new Elem(x);
- head->setNext(tail);
- tail->setPrev(head);
- tail->setNext(NULL);
- list_size++;
- return;
- }
- Elem* p = head;
- while (p != tail)
- {
- if (p->next()->value() >= x) //wstawiam nowy element pomiedzy head i tail
- {
- Elem* newElem = new Elem(x);
- p->next()->setPrev(newElem);
- newElem->setNext(p->next());
- p->setNext(newElem);
- newElem->setPrev(p);
- list_size++;
- return;
- }
- p = p->next();
- }
- //wstawiam nowy element za tail
- Elem* new_elem = new Elem(x);
- new_elem->setPrev(tail);
- tail->setNext(new_elem);
- new_elem->setNext(NULL);
- tail = new_elem;
- list_size++;
- }
- }
- }
- void SortedDLList::del(int x)
- {
- Elem* p = locate(x);
- if (p == NULL) //elementu nie ma w liscie lub lista jest pusta
- {
- return;
- }
- else if (p == head) //poszukiwany element jest head
- {
- head = head->next();
- delete p;
- list_size--;
- }
- else if (p != tail) //poszukiwany element jest pomiedzy head a tail
- {
- p->prev()->setNext(p->next());
- p->next()->setPrev(p->prev());
- delete p;
- list_size--;
- }
- else //poszukiwany element jest tail
- {
- tail = tail->prev();
- delete p;
- list_size--;
- }
- }
- void SortedDLList::delALLx(int x)
- {
- if (empty())
- {
- return;
- }
- else
- {
- Elem* p = locate(x);
- while (p != NULL)
- {
- p = locate(x);
- if (p == NULL)
- break;
- if (p->prev() != NULL)
- {
- p->prev()->setNext(p->next());
- p->next()->setPrev(p->prev());
- delete p;
- list_size--;
- }
- else
- {
- head->next()->setPrev(NULL);
- head = head->next();
- delete p;
- list_size--;
- }
- }
- }
- }
- void SortedDLList::clear()
- {
- if (empty())
- {
- return;
- }
- else
- {
- while (head != NULL)
- {
- Elem* p = head;
- head->next()->setPrev(NULL);
- head = head->next();
- delete p;
- list_size = 0;
- }
- }
- }
- ostream& operator<<(ostream& out, SortedDLList& l)
- {
- if (l.empty())
- {
- return out;
- }
- Elem* temp = l.head;
- while (temp != NULL)
- {
- out << temp->value() << " ";
- temp = temp->next();
- }
- return out;
- }
- int main()
- {
- SortedDLList lista;
- lista.insert(2);
- lista.insert(5);
- lista.insert(5);
- lista.insert(8);
- lista.insert(1);
- lista.insert(1);
- lista.insert(9);
- cout << lista << endl;
- /**blad jest w insert na pewno**/
- /**juz nie ma, ale brakowalo linii 238 :)**/
- lista.delALLx(1);
- cout << lista << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement