Advertisement
Chris2o2

[APS] SpecialSLLJoin

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