Advertisement
SlavkovB

[АПС] Избриши подлисти во листа

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