Advertisement
Guest User

Untitled

a guest
Nov 23rd, 2017
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.95 KB | None | 0 0
  1. #include <fstream>
  2. #include <string>
  3. using namespace std;
  4. class DoubleLinkedList
  5. {
  6. struct Element
  7. {
  8. int inf;
  9. Element *next;
  10. Element *prev;
  11. Element(int x) : inf(x), next(0), prev(0) {}
  12. };
  13. Element *head;
  14. Element *tail;
  15. int size;
  16.  
  17. //возвращает указатель на элемент списка с номером index
  18. Element *Find(int index)
  19. {
  20. if ((index<1) || (index>size))
  21. {
  22. return 0;
  23. }
  24. else
  25. {
  26. Element *cur = head;
  27. for (int i = 1; i<index; i++)
  28. {
  29. cur = cur->next;
  30. }
  31. return cur;
  32. }
  33. }
  34. public:
  35. DoubleLinkedList() :head(0), tail(0), size(0) //конструктор
  36. {}
  37.  
  38. bool Empty() //проверяет список на пустоту
  39. {
  40. return head == 0;
  41. }
  42. int GetLength() //возвращает количество элементов в списке
  43. {
  44. return size;
  45. }
  46. //возвращает значение элемента списка по его номеру
  47. int Get(int index)
  48. {
  49. if ((index<1) || (index>size))
  50. {
  51. return 0;
  52. }
  53. else
  54. {
  55. Element *r = Find(index);
  56. int i = r->inf;
  57. return i;
  58. }
  59. }
  60.  
  61. //осуществляет вставку элемента со значением data слева от
  62. //элемента с позицией index
  63. void InsertLeft(int index, int data)
  64. {
  65. if ((index<1) || (index>size + 1))
  66. {
  67. return;
  68. }
  69. else
  70. {
  71. Element *newPtr = new Element(data);
  72. size = GetLength() + 1; //увеличиваем размерность списка
  73. //устанавливаем указатель на элемент списка с заданным номером
  74. Element *cur = Find(index);
  75. //если этот указатель 0, то список был пуст, поэтому
  76. //новый элемент будет и первым и последним
  77. if (cur == 0)
  78. {
  79. head = newPtr;
  80. tail = newPtr;
  81. }
  82. else
  83. //иначе производим вставку в непустой список, при этом
  84. //есть два случая: 1 -частный случай (вставка перед
  85. //первым элементом списка), 2 - общий случай
  86. {
  87. newPtr->next = cur;
  88. newPtr->prev = cur->prev;
  89. cur->prev = newPtr;
  90. if (cur == head)
  91. {
  92. head = newPtr; //случай 1
  93. }
  94. else
  95. {
  96. newPtr->prev->next = newPtr; //случай 2
  97. }
  98. }
  99. }
  100. }
  101. //осуществляет вставку элемента со значением data слева от
  102. //элемента с позицией index
  103. void InsertRight(int index, int data)
  104. {
  105. if ((index<1 && head != 0) || (index>size + 1))
  106. {
  107. return;
  108. }
  109. else
  110. {
  111. Element *newPtr = new Element(data);
  112. size = GetLength() + 1; //увеличиваем размерность списка
  113. //устанавливаем указатель на элемент списка с заданным номером
  114. Element *cur = Find(index);
  115. //если этот указатель NULL, то список был пуст, поэтому
  116. //новый элемент будет и первым и последним
  117. if (cur == 0)
  118. {
  119. head = newPtr;
  120. tail = newPtr;
  121. }
  122. else
  123. //иначе производим вставку в непустой список, при этом
  124. //есть два случая: 1 - вставка после последнего элемента
  125. //списка, 2 - вставка в середину списка
  126. {
  127. newPtr->next = cur->next;
  128. newPtr->prev = cur;
  129. cur->next = newPtr;
  130. if (cur == tail)
  131. {
  132. tail = newPtr; //случай 1
  133. }
  134. else
  135. {
  136. newPtr->next->prev = newPtr; //случай 2
  137. }
  138. }
  139. }
  140. }
  141. //осуществляет удаление элемента с номером index из списка
  142. //выделяем четыре случая: 1 - после удаления список становится пустым
  143. //2 - удаляем первый элемент, 3 - удаляем последний элемент
  144. // 4 - общий случай
  145. void Remove(int index)
  146. {
  147. if ((index<1) || (index>size))
  148. {
  149. return;
  150. }
  151. else
  152. {
  153. //устанавливаем указатель на заданный элемент
  154. Element *cur = Find(index);
  155. --size; //уменьшаем размерность списка
  156. if (size == 0) //случай 1
  157. {
  158. head = 0;
  159. tail = 0;
  160. }
  161. else if (cur == head) //случай 2
  162. {
  163. head = head->next;
  164. head->prev = 0;
  165. }
  166. else if (cur == tail) //случай 3
  167. {
  168. tail = tail->prev;
  169. tail->next = 0;
  170. }
  171. else //случай 4
  172. {
  173. cur->prev->next = cur->next;
  174. cur->next->prev = cur->prev;
  175. }
  176. cur->next = 0;
  177. cur->prev = 0;
  178. delete cur;
  179. }
  180. }
  181. };
  182.  
  183. //определяем глобальные потоки
  184. ifstream in("input.txt");
  185. ofstream out("output.txt");
  186. int main()
  187. {
  188. DoubleLinkedList l;
  189. int value;
  190. int temp;
  191. //пока файл не пуст, считываем из него очередной элемент и помещаем в список
  192. while(in >> value)
  193. {
  194. l.InsertRight(l.GetLength(), value);
  195. }
  196. in.close();
  197.  
  198. for (int i = 1; i <= l.GetLength();i++)
  199. {
  200. if (l.Get(i) > 0) //если значение элемента в i-той позиции больше 0
  201. {
  202. l.InsertLeft(1, l.Get(i)); //добавляем его в начало списка
  203. l.Remove(i+1); //и удаляем данный элемент из списка
  204. }
  205. if (l.Get(i) == 0) //если значение элемента в i-той позиции равно 0
  206. {
  207. l.Remove(i); //то удаляем данный элемент из списка
  208. i--;
  209. }
  210.  
  211. }
  212. for (int i = 1; i <= l.GetLength();i++)
  213. {
  214. out << l.Get(i)<<endl;
  215. }
  216. return 0;
  217. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement