Stamenco

АПС - Сортирање со меурчиња кај листа

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