Advertisement
dzocesrce

[APS] Merge Sorted Lists

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