DamSi

Untitled

Nov 16th, 2015
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.88 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5.  
  6. class DLL<E> {
  7.  
  8.     private DLLNode<E> first, last;
  9.  
  10.     public DLL() {
  11.         // Construct an empty SLL
  12.         this.first = null;
  13.         this.last = null;
  14.     }
  15.  
  16.     public void deleteList() {
  17.         first = null;
  18.         last = null;
  19.     }
  20.  
  21.     public int length() {
  22.         int ret;
  23.         if (first != null) {
  24.             DLLNode<E> tmp = first;
  25.             ret = 1;
  26.             while (tmp.succ != null) {
  27.                 tmp = tmp.succ;
  28.                 ret++;
  29.             }
  30.             return ret;
  31.         } else {
  32.             return 0;
  33.         }
  34.  
  35.     }
  36.  
  37.     public DLLNode<E> find(E o) {
  38.         if (first != null) {
  39.             DLLNode<E> tmp = first;
  40.             while (tmp.element != o && tmp.succ != null) {
  41.                 tmp = tmp.succ;
  42.             }
  43.             if (tmp.element == o) {
  44.                 return tmp;
  45.             } else {
  46.                 System.out.println("Elementot ne postoi vo listata");
  47.             }
  48.         } else {
  49.             System.out.println("Listata e prazna");
  50.         }
  51.         return first;
  52.     }
  53.  
  54.     public void insertFirst(E o) {
  55.         DLLNode<E> ins = new DLLNode<E>(o, null, first);
  56.         if (first == null) {
  57.             last = ins;
  58.         } else {
  59.             first.pred = ins;
  60.         }
  61.         first = ins;
  62.     }
  63.  
  64.     public void insertLast(E o) {
  65.         if (first == null) {
  66.             insertFirst(o);
  67.         } else {
  68.             DLLNode<E> ins = new DLLNode<E>(o, last, null);
  69.             last.succ = ins;
  70.             last = ins;
  71.         }
  72.     }
  73.  
  74.     public void insertAfter(E o, DLLNode<E> after) {
  75.         if (after == last) {
  76.             insertLast(o);
  77.             return;
  78.         }
  79.         DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
  80.         after.succ.pred = ins;
  81.         after.succ = ins;
  82.     }
  83.  
  84.     public void insertBefore(E o, DLLNode<E> before) {
  85.         if (before == first) {
  86.             insertFirst(o);
  87.             return;
  88.         }
  89.         DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
  90.         before.pred.succ = ins;
  91.         before.pred = ins;
  92.     }
  93.  
  94.     public E deleteFirst() {
  95.         if (first != null) {
  96.             DLLNode<E> tmp = first;
  97.             first = first.succ;
  98.             if (first != null) {
  99.                 first.pred = null;
  100.             }
  101.             if (first == null) {
  102.                 last = null;
  103.             }
  104.             return tmp.element;
  105.         } else {
  106.             return null;
  107.         }
  108.     }
  109.  
  110.     public E deleteLast() {
  111.         if (first != null) {
  112.             if (first.succ == null) {
  113.                 return deleteFirst();
  114.             } else {
  115.                 DLLNode<E> tmp = last;
  116.                 last = last.pred;
  117.                 last.succ = null;
  118.                 return tmp.element;
  119.             }
  120.         }
  121.         // else throw Exception
  122.         return null;
  123.     }
  124.  
  125.     public E delete(DLLNode<E> node) {
  126.         if (node == first) {
  127.             deleteFirst();
  128.             return node.element;
  129.         }
  130.         if (node == last) {
  131.             deleteLast();
  132.             return node.element;
  133.         }
  134.         node.pred.succ = node.succ;
  135.         node.succ.pred = node.pred;
  136.         return node.element;
  137.  
  138.     }
  139.  
  140.     @Override
  141.     public String toString() {
  142.         String ret = new String();
  143.         if (first != null) {
  144.             DLLNode<E> tmp = first;
  145.             ret += tmp + " ";
  146.             while (tmp.succ != null) {
  147.                 tmp = tmp.succ;
  148.                 ret += tmp + " ";
  149.             }
  150.         } else {
  151.             ret = "Prazna lista!!!";
  152.         }
  153.         return ret;
  154.     }
  155.  
  156.     public String toStringR() {
  157.         String ret = new String();
  158.         if (last != null) {
  159.             DLLNode<E> tmp = last;
  160.             ret += tmp + "<->";
  161.             while (tmp.pred != null) {
  162.                 tmp = tmp.pred;
  163.                 ret += tmp + "<->";
  164.             }
  165.         } else {
  166.             ret = "Prazna lista!!!";
  167.         }
  168.         return ret;
  169.     }
  170.  
  171.     public DLLNode<E> getFirst() {
  172.         return first;
  173.     }
  174.  
  175.     public DLLNode<E> getLast() {
  176.  
  177.         return last;
  178.     }
  179. }
  180. class DLLNode<E> {
  181.     protected E element;
  182.     protected DLLNode<E> pred, succ;
  183.  
  184.     public DLLNode(E elem, DLLNode<E> pred, DLLNode<E> succ) {
  185.         this.element = elem;
  186.         this.pred = pred;
  187.         this.succ = succ;
  188.     }
  189.  
  190.     @Override
  191.     public String toString() {
  192.         return element.toString();
  193.     }
  194. }
  195. /**
  196.  *
  197.  * @author Damjan
  198.  */
  199. public class BubbleSortDLL {
  200.  
  201.     public static void main(String[] args) throws IOException {
  202.         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  203.         DLL<Integer> list = new DLL<>();
  204.         String input = reader.readLine();
  205.         int N = Integer.parseInt(input);
  206.         input = reader.readLine();
  207.         String[] arrayElements = input.split(" ");
  208.         for (int i = 0; i < N; ++i) {
  209.             list.insertLast(Integer.parseInt(arrayElements[i]));
  210.         }
  211.         bubbleSort(list);
  212.         printDLL(list);
  213.  
  214.     }
  215.  
  216.     static void printDLL(DLL<Integer> list) {
  217.         DLLNode<Integer> node = list.getFirst();
  218.         while (node != null) {
  219.             System.out.print(node.element);
  220.             if (node.succ != null) {
  221.                 System.out.print(" ");
  222.             }
  223.             node = node.succ;
  224.         }
  225.     }
  226.  
  227.     static void bubbleSort(DLL<Integer> list) {
  228.         for (DLLNode<Integer> node = list.getFirst(); node.succ != null; node = node.succ) {
  229.             for (DLLNode<Integer> tmp = list.getFirst(); tmp.succ != null; tmp = tmp.succ) {
  230.                 if (tmp.element > tmp.succ.element) {
  231.                     int temp = tmp.element;
  232.                     tmp.element = tmp.succ.element;
  233.                     tmp.succ.element = temp;
  234.                 }
  235.             }
  236.         }
  237.     }
  238. }
Advertisement
Add Comment
Please, Sign In to add comment