Advertisement
Guest User

Untitled

a guest
Nov 19th, 2017
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.56 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5. class DLLNode<E> {
  6. protected E element;
  7. protected DLLNode<E> pred, succ;
  8.  
  9. public DLLNode(E elem, DLLNode<E> pred, DLLNode<E> succ) {
  10. this.element = elem;
  11. this.pred = pred;
  12. this.succ = succ;
  13. }
  14.  
  15. @Override
  16. public String toString() {
  17. return element.toString();
  18. }
  19. }
  20.  
  21. class DLL<E> {
  22. private DLLNode<E> first, last;
  23.  
  24. public DLL() {
  25.  
  26. this.first = null;
  27. this.last = null;
  28. }
  29.  
  30. public void deleteList() {
  31. first = null;
  32. last = null;
  33. }
  34.  
  35. public int length() {
  36. int ret;
  37. if (first != null) {
  38. DLLNode<E> tmp = first;
  39. ret = 1;
  40. while (tmp.succ != null) {
  41. tmp = tmp.succ;
  42. ret++;
  43. }
  44. return ret;
  45. } else
  46. return 0;
  47. }
  48.  
  49. public void insertFirst(E o) {
  50. DLLNode<E> ins = new DLLNode<E>(o, null, first);
  51. if (first == null)
  52. last = ins;
  53. else
  54. first.pred = ins;
  55. first = ins;
  56. }
  57.  
  58. public void insertLast(E o) {
  59. if (first == null)
  60. insertFirst(o);
  61. else {
  62. DLLNode<E> ins = new DLLNode<E>(o, last, null);
  63. last.succ = ins;
  64. last = ins;
  65. }
  66. }
  67.  
  68. public void insertAfter(E o, DLLNode<E> after) {
  69. if(after==last){
  70. insertLast(o);
  71. return;
  72. }
  73. DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
  74. after.succ.pred = ins;
  75. after.succ = ins;
  76. }
  77.  
  78. public void insertBefore(E o, DLLNode<E> before) {
  79. if(before == first){
  80. insertFirst(o);
  81. return;
  82. }
  83. DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
  84. before.pred.succ = ins;
  85. before.pred = ins;
  86. }
  87.  
  88. public E deleteFirst() {
  89. if (first != null) {
  90. DLLNode<E> tmp = first;
  91. first = first.succ;
  92. first.pred = null;
  93. if (first == null)
  94. last = null;
  95. return tmp.element;
  96. } else
  97. return null;
  98. }
  99.  
  100. public E deleteLast() {
  101. if (first != null) {
  102. if (first.succ == null)
  103. return deleteFirst();
  104. else {
  105. DLLNode<E> tmp = last;
  106. last = last.pred;
  107. last.succ = null;
  108. return tmp.element;
  109. }
  110. }
  111. return null;
  112. }
  113.  
  114. @Override
  115. public String toString() {
  116. String ret = new String();
  117. if (first != null) {
  118. DLLNode<E> tmp = first;
  119. ret += tmp + "<->";
  120. while (tmp.succ != null) {
  121. tmp = tmp.succ;
  122. ret += tmp + "<->";
  123. }
  124. } else
  125. ret = "Prazna lista!!!";
  126. return ret;
  127. }
  128.  
  129. public DLLNode<E> getFirst() {
  130. return first;
  131. }
  132.  
  133. public DLLNode<E> getLast() {
  134. return last;
  135. }
  136. }
  137.  
  138. public class BubbleSortDLL
  139. {
  140. public static void bubbleSort(DLL<Integer> lista)
  141. {
  142. DLLNode<Integer> list = lista.getFirst();
  143. int t = 0;
  144. for (int i=0;i<lista.length();i++)
  145. {
  146. while(list != null)
  147. {
  148. if (list.succ != null)
  149. {
  150. if (list.succ.element < list.element)
  151. {
  152. t = list.succ.element;
  153. list.succ.element = list.element;
  154. list.element = t;
  155. }
  156. }
  157. list = list.succ;
  158. }
  159. list = lista.getFirst();
  160. }
  161.  
  162. DLLNode<Integer> tmp = lista.getFirst();
  163. while (tmp != null) {
  164. System.out.print(tmp.element);
  165. if(tmp.succ != null)
  166. System.out.print(" ");
  167. tmp = tmp.succ;
  168. }
  169. if(tmp == null)
  170. System.out.println();
  171. }
  172.  
  173. public static void main(String[] args) throws IOException {
  174. DLL<Integer> lista = new DLL<Integer>();
  175. BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
  176. String s = stdin.readLine();
  177. int N = Integer.parseInt(s);
  178. s = stdin.readLine();
  179. String[] pomniza = s.split(" ");
  180. for (int i = 0; i < N; i++) {
  181. lista.insertLast(Integer.parseInt(pomniza[i]));
  182. }
  183. bubbleSort(lista);
  184. }
  185. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement