Stamenco

АПС - Спој листи

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