Advertisement
Guest User

Untitled

a guest
Jan 26th, 2015
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.77 KB | None | 0 0
  1. package dlll;
  2.  
  3.  
  4.     import java.io.BufferedReader;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.util.Iterator;
  8. import java.util.LinkedList;
  9. import java.util.NoSuchElementException;
  10.  
  11.  
  12.  
  13.     class DLLNode<E> {
  14.         protected E element;
  15.         protected DLLNode<E> pred, succ;
  16.  
  17.         public DLLNode(E elem, DLLNode<E> pred, DLLNode<E> succ) {
  18.             this.element = elem;
  19.             this.pred = pred;
  20.             this.succ = succ;
  21.         }
  22.  
  23.         @Override
  24.         public String toString() {
  25.             return "<-" + element.toString() + "->";
  26.         }
  27.     }
  28.  
  29.     class DLL<E> {
  30.         private DLLNode<E> first, last;
  31.  
  32.         public DLL() {
  33.             // Construct an empty SLL
  34.             this.first = null;
  35.             this.last = null;
  36.         }
  37.  
  38.         public void deleteList() {
  39.             first = null;
  40.             last = null;
  41.         }
  42.  
  43.         public int length() {
  44.             int ret;
  45.             if (first != null) {
  46.                 DLLNode<E> tmp = first;
  47.                 ret = 1;
  48.                 while (tmp.succ != null) {
  49.                     tmp = tmp.succ;
  50.                     ret++;
  51.                 }
  52.                 return ret;
  53.             } else
  54.                 return 0;
  55.  
  56.         }
  57.  
  58.         public void insertFirst(E o) {
  59.             DLLNode<E> ins = new DLLNode<E>(o, null, first);
  60.             if (first == null)
  61.                 last = ins;
  62.             else
  63.                 first.pred = ins;
  64.             first = ins;
  65.         }
  66.  
  67.         public void insertLast(E o) {
  68.             if (first == null)
  69.                 insertFirst(o);
  70.             else {
  71.                 DLLNode<E> ins = new DLLNode<E>(o, last, null);
  72.                 last.succ = ins;
  73.                 last = ins;
  74.             }
  75.         }
  76.  
  77.         public void insertAfter(E o, DLLNode<E> after) {
  78.             if (after == last) {
  79.                 insertLast(o);
  80.                 return;
  81.             }
  82.             DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
  83.             after.succ.pred = ins;
  84.             after.succ = ins;
  85.         }
  86.  
  87.         public void insertBefore(E o, DLLNode<E> before) {
  88.             if (before == first) {
  89.                 insertFirst(o);
  90.                 return;
  91.             }
  92.             DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
  93.             before.pred.succ = ins;
  94.             before.pred = ins;
  95.         }
  96.  
  97.         public E deleteFirst() {
  98.             if (first != null) {
  99.                 DLLNode<E> tmp = first;
  100.                 first = first.succ;
  101.                 if (first != null) first.pred = null;
  102.                 if (first == null)
  103.                     last = null;
  104.                 return tmp.element;
  105.             } else
  106.                 return null;
  107.         }
  108.  
  109.         public E deleteLast() {
  110.             if (first != null) {
  111.                 if (first.succ == null)
  112.                     return deleteFirst();
  113.                 else {
  114.                     DLLNode<E> tmp = last;
  115.                     last = last.pred;
  116.                     last.succ = null;
  117.                     return tmp.element;
  118.                 }
  119.             }
  120.             // else throw Exception
  121.             return null;
  122.         }
  123.  
  124.         @Override
  125.         public String toString() {
  126.             String ret = new String();
  127.             if (first != null) {
  128.                 DLLNode<E> tmp = first;
  129.                 ret += tmp + "<->";
  130.                 while (tmp.succ != null) {
  131.                     tmp = tmp.succ;
  132.                     ret += tmp + "<->";
  133.                 }
  134.             } else
  135.                 ret = "Prazna lista!!!";
  136.             return ret;
  137.         }
  138.  
  139.         public DLLNode<E> getFirst() {
  140.             return first;
  141.         }
  142.  
  143.         public DLLNode<E> getLast() {
  144.  
  145.             return last;
  146.         }
  147.         public void delete(DLLNode<E> node) {
  148.         //  System.out.println(node.element);
  149.  
  150.             //   if( node.element == t deleteFirst();
  151.            
  152.             if(node.pred == null){ first = first.succ; first.pred= null;}
  153.            
  154.             else if(node== this.last) deleteLast();
  155.            
  156.            
  157.        
  158.        
  159.             else {  DLLNode<E> tmp = node;
  160.             node.pred.succ = tmp.succ;
  161.             tmp.succ.pred=node.pred;
  162.            
  163.  
  164.            
  165.            
  166.            
  167.            
  168.                 //deleteFirst();
  169.                
  170.             }}
  171.          public DLLNode<E> get(int index){
  172.                 if (index<=this.length()-1){
  173.                         DLLNode<E> tmp = first;
  174.                         int k=0;
  175.                         while(tmp!=null){
  176.                                 if (k==index) break;
  177.                                         k++;
  178.                                         tmp = tmp.succ;
  179.                         }
  180.                         return tmp;
  181.                 }
  182.                 else return null;
  183.             }
  184.  
  185.         public void deleteSublist(DLL<E> list2){
  186.             boolean flag=true;
  187.             int begin=0, end=0, j=0;
  188.            
  189.             if (this.length()>=list2.length()){
  190.             DLLNode<E> tmp=null, tmp1 = null;
  191.             for (int i=0; i<this.length()-list2.length()+1;i++){
  192.                     flag = true;
  193.                     tmp = this.get(i);
  194.                     j =0;
  195.                         for (tmp1=list2.getFirst(); tmp1!=null;tmp1=tmp1.succ, tmp=tmp.succ){
  196.                             if (!tmp1.element.equals(tmp.element)){
  197.                                     flag=false;
  198.                                     break;
  199.                                     }
  200.                             j++;
  201.                     }
  202.                         if (flag){
  203.                     begin = i--;
  204.                     end = i+list2.length();
  205.                     break;
  206.                             }
  207.                     }
  208.                     if (flag){
  209.                             DLLNode<E> pom = first;
  210.                             int k=0;
  211.                             while(pom!=null){
  212.                                     if (!(k>=begin&&k<=end)) System.out.print(pom.element+" ");
  213.                                     pom = pom.succ;
  214.                                     k++;
  215.                             }
  216.                             if (end-begin==this.length()-1) System.out.println("EMPTY LIST");
  217.                     }
  218.                     else System.out.println("No such sublist is found.");
  219.             }
  220.             else{
  221.                     System.out.println("No such sublist is found.");
  222.             }
  223.         }
  224.        
  225.  
  226.         public void WHY(DLL<E> lista) {
  227.         DLLNode<E> tmp1= this.first; int count=0;
  228.         DLLNode<E> tmp2 = lista.first;
  229.         int s= lista.length();
  230.        
  231.         while(tmp1 != null) {
  232.             while(tmp2 != null && tmp1 !=null &&  tmp1.element.equals(tmp2.element))
  233.             {
  234.                 count++; tmp1= tmp1.succ; tmp2= tmp2.succ;
  235.             }
  236.            
  237.             if ( count== s) {
  238.                
  239.                  while(count !=0)
  240.                 {   System.out.println("Dali sum "+ tmp1.pred);
  241.                 if(tmp1.pred == null) System.out.println("eror"); //deleteFirst();
  242.                 this.delete(tmp1.pred);
  243.                 // System.out.println(tmp1.pred);
  244.                 // tmp1=tmp1.succ;
  245.                
  246.                 count-=1;
  247.             }}
  248.             tmp2=lista.first;
  249.              tmp1=tmp1.succ;
  250.              
  251.            
  252.         } if(this.length()>0)
  253.         { DLLNode<E>tmp3= this.first;
  254.           for(int i=0;i<this.length();i++)
  255.         {System.out.print( tmp3.element.toString() + " ");
  256.        
  257.            tmp3=tmp3.succ;
  258.         } }
  259.         else System.out.println("PRAZNA LISTA!");
  260.        
  261.        
  262.        
  263.     }}
  264.  
  265.  
  266.     public class ZastoNE {
  267.         public static void main(String[] args) throws IOException {
  268.  
  269.             BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
  270.             String s = stdin.readLine();
  271.             int N = Integer.parseInt(s);
  272.            
  273.            
  274.             DLL<Integer> lista1 = new DLL<Integer>();
  275.             s = stdin.readLine();
  276.             String[] pomniza = s.split(" ");
  277.             for (int i = 0; i < N; i++) {
  278.                 lista1.insertLast(Integer.parseInt(pomniza[i]));
  279.             }
  280.  
  281.             s = stdin.readLine();
  282.             N = Integer.parseInt(s);
  283.             DLL<Integer> lista2 = new DLL<Integer>();
  284.             s = stdin.readLine();
  285.             pomniza = s.split(" ");
  286.             for (int i = 0; i < N; i++) {
  287.                 lista2.insertLast(Integer.parseInt(pomniza[i]));
  288.             }
  289.  
  290.             //lista1.WHY(lista2);
  291.             System.out.println("na ivan :");
  292.             lista1.deleteSublist(lista2);
  293.         }
  294.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement