metalni

APS 1. Kolokvium 1. Termin

Nov 28th, 2020 (edited)
905
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Dadeni se dve sortirani listi, prvata vo rastecki redosled, vtorata vo opagjacki redosled. Da se spojat dvete listi taka sto rezultatnata lista da bide sortirana vo opagjacki redosled.
  2. //Na vlez se dadeni najprvin 2 broevi koi gi oznacuvaat dolzinite na dvete listi, pa potoa se dadeni elementite na dvete listi
  3.  
  4. import java.util.Scanner;
  5.  
  6. public class DvojnaLista {
  7.     public static void main(String [] args) {
  8.  
  9.         Scanner input = new Scanner(System.in);
  10.         //citanje na broj na elementi
  11.         int m = input.nextInt();
  12.         int n = input.nextInt();
  13.  
  14.         DLL<Integer> lista1 = new DLL<Integer>();
  15.         DLL<Integer> lista2 = new DLL<Integer>();
  16.         DLL<Integer> lista3 = new DLL<Integer>();
  17.  
  18.         //citaj listi, edna po edna
  19.         for (int i = 0; i < m; i++) {
  20.             int el = input.nextInt();
  21.             lista1.insertLast(el);
  22.         }
  23.  
  24.         for (int i = 0; i < n; i++) {
  25.             int el = input.nextInt();
  26.             lista2.insertLast(el);
  27.         }
  28.  
  29.         DLLNode<Integer> firstHead = lista1.getFirst();
  30.         DLLNode<Integer> secHead = lista2.getFirst();
  31.         DLLNode<Integer> firstTail = lista1.getFirst();
  32.  
  33.         while(firstTail.succ != null)
  34.             firstTail = firstTail.succ;
  35.  
  36.         while(true){
  37.             if(firstTail == null){
  38.                 while(secHead != null){
  39.                     lista3.insertLast(secHead.element);
  40.                     secHead = secHead.succ;
  41.                 }
  42.                 break;
  43.             } else if(secHead == null){
  44.                 while(firstTail != null){
  45.                     lista3.insertLast(firstTail.element);
  46.                     firstTail = firstTail.pred;
  47.                 }
  48.                 break;
  49.             } else if(firstTail.element >= secHead.element){
  50.                 lista3.insertLast(firstTail.element);
  51.                 firstTail = firstTail.pred;
  52.             } else if(secHead.element >= firstTail.element){
  53.                 lista3.insertLast(secHead.element);
  54.                 secHead = secHead.succ;
  55.             }
  56.         }
  57.  
  58.  
  59.  
  60.         //pecatenje
  61.         System.out.println(lista3.toString());
  62.         System.out.println(lista3.toStringR());
  63.     }
  64.  
  65. }
  66.  
  67.  
  68. class DLLNode<E> {
  69.     protected E element;
  70.     protected DLLNode<E> pred, succ;
  71.  
  72.     public DLLNode(E elem, DLLNode<E> pred, DLLNode<E> succ) {
  73.         this.element = elem;
  74.         this.pred = pred;
  75.         this.succ = succ;
  76.     }
  77.  
  78.     @Override
  79.     public String toString() {
  80.         return element.toString();
  81.     }
  82.  
  83. }
  84.  
  85. class DLL<E> {
  86.     private DLLNode<E> first, last;
  87.  
  88.     public DLL() {
  89.         // Construct an empty SLL
  90.         this.first = null;
  91.         this.last = null;
  92.     }
  93.  
  94.     public void deleteList() {
  95.         first = null;
  96.         last = null;
  97.     }
  98.  
  99.     public int length() {
  100.         int ret;
  101.         if (first != null) {
  102.             DLLNode<E> tmp = first;
  103.             ret = 1;
  104.             while (tmp.succ != null) {
  105.                 tmp = tmp.succ;
  106.                 ret++;
  107.             }
  108.             return ret;
  109.         } else
  110.             return 0;
  111.  
  112.     }
  113.  
  114.     public DLLNode<E> find(E o) {
  115.         if (first != null) {
  116.             DLLNode<E> tmp = first;
  117.             while (tmp.element != o && tmp.succ != null)
  118.                 tmp = tmp.succ;
  119.             if (tmp.element == o) {
  120.                 return tmp;
  121.             } else {
  122.                 System.out.println("Elementot ne postoi vo listata");
  123.             }
  124.         } else {
  125.             System.out.println("Listata e prazna");
  126.         }
  127.         return first;
  128.     }
  129.  
  130.     public void insertFirst(E o) {
  131.         DLLNode<E> ins = new DLLNode<E>(o, null, first);
  132.         if (first == null)
  133.             last = ins;
  134.         else
  135.             first.pred = ins;
  136.         first = ins;
  137.     }
  138.  
  139.     public void insertLast(E o) {
  140.         if (first == null)
  141.             insertFirst(o);
  142.         else {
  143.             DLLNode<E> ins = new DLLNode<E>(o, last, null);
  144.             last.succ = ins;
  145.             last = ins;
  146.         }
  147.     }
  148.  
  149.     public void insertAfter(E o, DLLNode<E> after) {
  150.         if(after==last){
  151.             insertLast(o);
  152.             return;
  153.         }
  154.         DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
  155.         after.succ.pred = ins;
  156.         after.succ = ins;
  157.     }
  158.  
  159.     public void insertBefore(E o, DLLNode<E> before) {
  160.         if(before == first){
  161.             insertFirst(o);
  162.             return;
  163.         }
  164.         DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
  165.         before.pred.succ = ins;
  166.         before.pred = ins;
  167.     }
  168.  
  169.     public E deleteFirst() {
  170.         if (first != null) {
  171.             DLLNode<E> tmp = first;
  172.             first = first.succ;
  173.             if (first != null) first.pred = null;
  174.             if (first == null)
  175.                 last = null;
  176.             return tmp.element;
  177.         } else
  178.             return null;
  179.     }
  180.  
  181.     public E deleteLast() {
  182.         if (first != null) {
  183.             if (first.succ == null)
  184.                 return deleteFirst();
  185.             else {
  186.                 DLLNode<E> tmp = last;
  187.                 last = last.pred;
  188.                 last.succ = null;
  189.                 return tmp.element;
  190.             }
  191.         }
  192.         // else throw Exception
  193.         return null;
  194.     }
  195.  
  196.     public E delete(DLLNode<E> node) {
  197.         if(node==first){
  198.             deleteFirst();
  199.             return node.element;
  200.         }
  201.         if(node==last){
  202.             deleteLast();
  203.             return node.element;
  204.         }
  205.         node.pred.succ = node.succ;
  206.         node.succ.pred = node.pred;
  207.         return node.element;
  208.  
  209.     }
  210.  
  211.     @Override
  212.     public String toString() {
  213.         String ret = new String();
  214.         if (first != null) {
  215.             DLLNode<E> tmp = first;
  216.             ret += tmp + "<->";
  217.             while (tmp.succ != null) {
  218.                 tmp = tmp.succ;
  219.                 ret += tmp + "<->";
  220.             }
  221.         } else
  222.             ret = "Prazna lista!!!";
  223.         return ret;
  224.     }
  225.  
  226.     public String toStringR() {
  227.         String ret = new String();
  228.         if (last != null) {
  229.             DLLNode<E> tmp = last;
  230.             ret += tmp + "<->";
  231.             while (tmp.pred != null) {
  232.                 tmp = tmp.pred;
  233.                 ret += tmp + "<->";
  234.             }
  235.         } else
  236.             ret = "Prazna lista!!!";
  237.         return ret;
  238.     }
  239.  
  240.     public DLLNode<E> getFirst() {
  241.         return first;
  242.     }
  243.  
  244.     public DLLNode<E> getLast() {
  245.  
  246.         return last;
  247.     }
  248.  
  249.     public void izvadiDupliIPrebroj(){
  250.  
  251.     }
  252. }
  253.  
RAW Paste Data