Advertisement
Guest User

Untitled

a guest
Sep 18th, 2019
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.76 KB | None | 0 0
  1.  
  2. /*
  3. Дадена е едонстрано поврзана листа SLL чии што јазли содржат по еден природен број.
  4. Да се трансформира листата така што сите соседни јазли ќе си ги
  5. заменат местата.
  6. Блез: Во првиот ред е даден бројот на елементи во листата, а потоа елементите во листата
  7. 7
  8. 1 2 3 4 5 6 7
  9. Излез:
  10. 2 1 4 3 6 5 7
  11. * */
  12. import java.io.BufferedReader;
  13. import java.io.IOException;
  14. import java.io.InputStreamReader;
  15. import java.util.Iterator;
  16. import java.util.NoSuchElementException;
  17.  
  18. class SLL<E> {
  19. SLLNode<E> first;
  20.  
  21. public SLL() {
  22. // Construct an empty SLL
  23. this.first = null;
  24. }
  25.  
  26. public void deleteList() {
  27. first = null;
  28. }
  29.  
  30. public int length() {
  31. int ret;
  32. if (first != null) {
  33. SLLNode<E> tmp = first;
  34. ret = 1;
  35. while (tmp.succ != null) {
  36. tmp = tmp.succ;
  37. ret++;
  38. }
  39. return ret;
  40. } else
  41. return 0;
  42.  
  43. }
  44.  
  45. @Override
  46. public String toString() {
  47. String ret = new String();
  48. if (first != null) {
  49. SLLNode<E> tmp = first;
  50. ret += tmp + " ";
  51. while (tmp.succ != null) {
  52. tmp = tmp.succ;
  53. ret += tmp + " ";
  54. }
  55. } else
  56. ret = "Prazna lista!!!";
  57. return ret;
  58. }
  59.  
  60. public void insertFirst(E o) {
  61. SLLNode<E> ins = new SLLNode<E>(o, first);
  62. first = ins;
  63. }
  64.  
  65. public void insertAfter(E o, SLLNode<E> node) {
  66. if (node != null) {
  67. SLLNode<E> ins = new SLLNode<E>(o, node.succ);
  68. node.succ = ins;
  69. } else {
  70. System.out.println("Dadenot jazol e null");
  71. }
  72. }
  73.  
  74. public void insertBefore(E o, SLLNode<E> before) {
  75.  
  76. if (first != null) {
  77. SLLNode<E> tmp = first;
  78. if (first == before) {
  79. this.insertFirst(o);
  80. return;
  81. }
  82. // ako first!=before
  83. while (tmp.succ != before)
  84. tmp = tmp.succ;
  85. if (tmp.succ == before) {
  86. SLLNode<E> ins = new SLLNode<E>(o, before);
  87. tmp.succ = ins;
  88. } else {
  89. System.out.println("Elementot ne postoi vo listata");
  90. }
  91. } else {
  92. System.out.println("Listata e prazna");
  93. }
  94. }
  95.  
  96. public void insertLast(E o) {
  97. if (first != null) {
  98. SLLNode<E> tmp = first;
  99. while (tmp.succ != null)
  100. tmp = tmp.succ;
  101. SLLNode<E> ins = new SLLNode<E>(o, null);
  102. tmp.succ = ins;
  103. } else {
  104. insertFirst(o);
  105. }
  106. }
  107.  
  108. public E deleteFirst() {
  109. if (first != null) {
  110. SLLNode<E> tmp = first;
  111. first = first.succ;
  112. return tmp.element;
  113. } else {
  114. System.out.println("Listata e prazna");
  115. return null;
  116. }
  117. }
  118.  
  119. public E delete(SLLNode<E> node) {
  120. if (first != null) {
  121. SLLNode<E> tmp = first;
  122. if (first == node) {
  123. return this.deleteFirst();
  124. }
  125. while (tmp.succ != node && tmp.succ.succ != null)
  126. tmp = tmp.succ;
  127. if (tmp.succ == node) {
  128. tmp.succ = tmp.succ.succ;
  129. return node.element;
  130. } else {
  131. System.out.println("Elementot ne postoi vo listata");
  132. return null;
  133. }
  134. } else {
  135. System.out.println("Listata e prazna");
  136. return null;
  137. }
  138.  
  139. }
  140.  
  141. public SLLNode<E> getFirst() {
  142. return first;
  143. }
  144.  
  145. public SLLNode<E> find(E o) {
  146. if (first != null) {
  147. SLLNode<E> tmp = first;
  148. while (tmp.element != o && tmp.succ != null)
  149. tmp = tmp.succ;
  150. if (tmp.element == o) {
  151. return tmp;
  152. } else {
  153. System.out.println("Elementot ne postoi vo listata");
  154. }
  155. } else {
  156. System.out.println("Listata e prazna");
  157. }
  158. return first;
  159. }
  160.  
  161. public Iterator<E> iterator() {
  162. // Return an iterator that visits all elements of this list, in left-to-right
  163. // order.
  164. return new LRIterator<E>();
  165. }
  166.  
  167. // //////////Inner class ////////////
  168.  
  169. private class LRIterator<E> implements Iterator<E> {
  170.  
  171. private SLLNode<E> place, curr;
  172.  
  173. private LRIterator() {
  174. place = (SLLNode<E>) first;
  175. curr = null;
  176. }
  177.  
  178. public boolean hasNext() {
  179. return (place != null);
  180. }
  181.  
  182. public E next() {
  183. if (place == null)
  184. throw new NoSuchElementException();
  185. E nextElem = place.element;
  186. curr = place;
  187. place = place.succ;
  188. return nextElem;
  189. }
  190.  
  191. public void remove() {
  192. // Not implemented
  193. }
  194. }
  195.  
  196. public void mirror() {
  197. if (first != null) {
  198. // m=nextsucc, p=tmp,q=next
  199. SLLNode<E> tmp = first;
  200. SLLNode<E> newsucc = null;
  201. SLLNode<E> next;
  202.  
  203. while (tmp != null) {
  204. next = tmp.succ;
  205. tmp.succ = newsucc;
  206. newsucc = tmp;
  207. tmp = next;
  208. }
  209. first = newsucc;
  210. }
  211.  
  212. }
  213.  
  214. public void merge(SLL<E> in) {
  215. if (first != null) {
  216. SLLNode<E> tmp = first;
  217. while (tmp.succ != null)
  218. tmp = tmp.succ;
  219. tmp.succ = in.getFirst();
  220. } else {
  221. first = in.getFirst();
  222. }
  223. }
  224. }
  225.  
  226. class SLLNode<E> {
  227. protected E element;
  228. protected SLLNode<E> succ;
  229.  
  230. public SLLNode(E elem, SLLNode<E> succ) {
  231. this.element = elem;
  232. this.succ = succ;
  233. }
  234.  
  235. @Override
  236. public String toString() {
  237. return element.toString();
  238. }
  239. }
  240.  
  241. public class Test {
  242.  
  243. public static void main(String[] args) throws IOException {
  244. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  245. int N = Integer.parseInt(br.readLine());
  246. SLL<Integer> lista = new SLL<Integer>();
  247. String[] pom = br.readLine().split(" ");
  248. for (int i = 0; i < N; i++) {
  249. lista.insertLast(Integer.parseInt(pom[i]));
  250. }
  251.  
  252. SLLNode<Integer> tmp = lista.getFirst();
  253. SLLNode<Integer> prvaIteracija = tmp.succ;
  254. SLLNode<Integer> dvizhi = tmp.succ.succ;
  255. tmp.succ = dvizhi;
  256. prvaIteracija.succ = tmp;
  257. lista.first = prvaIteracija;
  258.  
  259. while (dvizhi.succ != null) {
  260. SLLNode<Integer> next = dvizhi.succ;
  261. tmp.succ = next;
  262. dvizhi.succ = next.succ;
  263. next.succ = dvizhi;
  264. tmp = next.succ;
  265. if (dvizhi.succ != null) {
  266. dvizhi = dvizhi.succ;
  267. }
  268. }
  269. System.out.println(lista);
  270.  
  271. }
  272.  
  273. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement