Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <string>
- using namespace std;
- class DoubleLinkedList
- {
- struct Element
- {
- int inf;
- Element *next;
- Element *prev;
- Element(int x) : inf(x), next(0), prev(0) {}
- };
- Element *head;
- Element *tail;
- int size;
- //возвращает указатель на элемент списка с номером index
- Element *Find(int index)
- {
- if ((index<1) || (index>size))
- {
- return 0;
- }
- else
- {
- Element *cur = head;
- for (int i = 1; i<index; i++)
- {
- cur = cur->next;
- }
- return cur;
- }
- }
- public:
- DoubleLinkedList() :head(0), tail(0), size(0) //конструктор
- {}
- bool Empty() //проверяет список на пустоту
- {
- return head == 0;
- }
- int GetLength() //возвращает количество элементов в списке
- {
- return size;
- }
- //возвращает значение элемента списка по его номеру
- int Get(int index)
- {
- if ((index<1) || (index>size))
- {
- return 0;
- }
- else
- {
- Element *r = Find(index);
- int i = r->inf;
- return i;
- }
- }
- //осуществляет вставку элемента со значением data слева от
- //элемента с позицией index
- void InsertLeft(int index, int data)
- {
- if ((index<1) || (index>size + 1))
- {
- return;
- }
- else
- {
- Element *newPtr = new Element(data);
- size = GetLength() + 1; //увеличиваем размерность списка
- //устанавливаем указатель на элемент списка с заданным номером
- Element *cur = Find(index);
- //если этот указатель 0, то список был пуст, поэтому
- //новый элемент будет и первым и последним
- if (cur == 0)
- {
- head = newPtr;
- tail = newPtr;
- }
- else
- //иначе производим вставку в непустой список, при этом
- //есть два случая: 1 -частный случай (вставка перед
- //первым элементом списка), 2 - общий случай
- {
- newPtr->next = cur;
- newPtr->prev = cur->prev;
- cur->prev = newPtr;
- if (cur == head)
- {
- head = newPtr; //случай 1
- }
- else
- {
- newPtr->prev->next = newPtr; //случай 2
- }
- }
- }
- }
- //осуществляет вставку элемента со значением data слева от
- //элемента с позицией index
- void InsertRight(int index, int data)
- {
- if ((index<1 && head != 0) || (index>size + 1))
- {
- return;
- }
- else
- {
- Element *newPtr = new Element(data);
- size = GetLength() + 1; //увеличиваем размерность списка
- //устанавливаем указатель на элемент списка с заданным номером
- Element *cur = Find(index);
- //если этот указатель NULL, то список был пуст, поэтому
- //новый элемент будет и первым и последним
- if (cur == 0)
- {
- head = newPtr;
- tail = newPtr;
- }
- else
- //иначе производим вставку в непустой список, при этом
- //есть два случая: 1 - вставка после последнего элемента
- //списка, 2 - вставка в середину списка
- {
- newPtr->next = cur->next;
- newPtr->prev = cur;
- cur->next = newPtr;
- if (cur == tail)
- {
- tail = newPtr; //случай 1
- }
- else
- {
- newPtr->next->prev = newPtr; //случай 2
- }
- }
- }
- }
- //осуществляет удаление элемента с номером index из списка
- //выделяем четыре случая: 1 - после удаления список становится пустым
- //2 - удаляем первый элемент, 3 - удаляем последний элемент
- // 4 - общий случай
- void Remove(int index)
- {
- if ((index<1) || (index>size))
- {
- return;
- }
- else
- {
- //устанавливаем указатель на заданный элемент
- Element *cur = Find(index);
- --size; //уменьшаем размерность списка
- if (size == 0) //случай 1
- {
- head = 0;
- tail = 0;
- }
- else if (cur == head) //случай 2
- {
- head = head->next;
- head->prev = 0;
- }
- else if (cur == tail) //случай 3
- {
- tail = tail->prev;
- tail->next = 0;
- }
- else //случай 4
- {
- cur->prev->next = cur->next;
- cur->next->prev = cur->prev;
- }
- cur->next = 0;
- cur->prev = 0;
- delete cur;
- }
- }
- };
- //определяем глобальные потоки
- ifstream in("input.txt");
- ofstream out("output.txt");
- int main()
- {
- DoubleLinkedList l;
- int value;
- int temp;
- //пока файл не пуст, считываем из него очередной элемент и помещаем в список
- while(in >> value)
- {
- l.InsertRight(l.GetLength(), value);
- }
- in.close();
- for (int i = 1; i <= l.GetLength();i++)
- {
- if (l.Get(i) > 0) //если значение элемента в i-той позиции больше 0
- {
- l.InsertLeft(1, l.Get(i)); //добавляем его в начало списка
- l.Remove(i+1); //и удаляем данный элемент из списка
- }
- if (l.Get(i) == 0) //если значение элемента в i-той позиции равно 0
- {
- l.Remove(i); //то удаляем данный элемент из списка
- i--;
- }
- }
- for (int i = 1; i <= l.GetLength();i++)
- {
- out << l.Get(i)<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement