Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "exception.cpp"
- template <class Item>
- class DoubleLinkedList
- {
- struct Element
- {
- Item inf;
- Element *next;
- Element *prev;
- Element(Item x) :inf(x), next(0), prev(0)
- {
- }
- };
- Element *head;
- Element *tail;
- int size;
- Element *Find(int index)
- {
- if ((index<1) || (index>size))
- {
- return NULL;
- }
- else
- {
- Element *cur=head;
- for (int i = 1; i < index; i++)
- {
- cur = cur->next;
- }
- return cur;
- }
- }
- public:
- //конструктор
- DoubleLinkedList() :head(0), tail(0), size(0)
- {
- }
- //деструктор
- ~DoubleLinkedList()
- {
- while (!Empty())
- {
- Remove(1);
- }
- }
- //проверяет список на пустоту
- bool Empty()
- {
- return head == 0;
- }
- //возвращает длину списка
- int GetLength()
- {
- return size;
- }
- //возвращает элемент на позиции index
- Item Get(int index)
- {
- if ((index<1) || (index>size))
- {
- throw DoubleListException("Exception: get - double-linked list error");
- }
- else
- {
- Element *r = Find(index);
- Item i = r->inf;
- return i;
- }
- }
- //вставить слева
- void InsertLeft(int index, Item data)
- {
- if ((index<1) || (index>size + 1))
- {
- throw DoubleListException("Exception: insert - double-linked list error");
- }
- else
- {
- Element *newPtr = new Element(data);
- size = GetLength() + 1;
- Element *cur = Find(index);
- if (cur == NULL)
- {
- head = newPtr;
- tail = newPtr;
- }
- else
- {
- newPtr->next = cur;
- newPtr->prev = cur->prev;
- cur->prev = newPtr;
- if (cur == head)
- {
- head = newPtr;
- }
- else
- {
- newPtr->prev->next = newPtr;
- }
- }
- }
- }
- //вставить справа
- void InsertRight(int index, Item data)
- {
- if ((index<1 && head != NULL) || (index>size + 1))
- {
- throw DoubleListException("Exception: insert - double-linked list error");
- }
- else
- {
- Element *newPtr = new Element(data);
- size = GetLength() + 1;
- Element *cur = Find(index);
- if (cur == NULL)
- {
- head = newPtr;
- tail = newPtr;
- }
- else
- {
- newPtr->next = cur->next;
- newPtr->prev = cur;
- cur->next = newPtr;
- if (cur == tail)
- {
- tail = newPtr;
- }
- else
- {
- newPtr->next->prev = newPtr;
- }
- }
- }
- }
- //удалить элемент на позиции index
- void Remove(int index)
- {
- if ((index<1) || (index>size))
- {
- throw DoubleListException("Exception: remove - double-linked list error");
- }
- else
- {
- Element *cur = Find(index);
- --size;
- if (size == 0)
- {
- head = NULL;
- tail = NULL;
- }
- else if (cur == head)
- {
- head = head->next;
- head->prev = NULL;
- }
- else if (cur == tail)
- {
- tail = tail->prev;
- tail->next = NULL;
- }
- else
- {
- cur->prev->next = cur->next;
- cur->next->prev = cur->prev;
- }
- cur->next = NULL;
- cur->prev = NULL;
- delete cur;
- }
- }
- //распечатать слева направо
- void PrintLeftToRight()
- {
- for (Element *cur = head; cur != NULL; cur = cur->next)
- {
- fout << cur->inf << " ";
- }
- fout << endl;
- }
- //распечатать справа налево
- void PrintRightToLeft()
- {
- for (Element *cur = tail; cur != NULL; cur = cur->prev)
- {
- fout << cur->inf << " ";
- }
- fout << endl;
- }
- };
- /////////////////////////////////////////////////////////////////////////////////
- #include "exception"
- #include "string"
- using namespace std;
- class DoubleListException : public exception
- {
- public:
- DoubleListException(const string & message = "") : exception(message.c_str())
- {
- }
- };
- /////////////////////////////////////////////////////////////////////////////////
- 1 1 1 4 6 6 0 5 1 1
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement