Mitrezzz

[АПС - Колоквиум 1] PodeliSporedParnost

Nov 25th, 2020
1,472
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Дадена е двострано поврзана листа чии што јазли содржат по еден природен број.
  2. Листата треба да се подели на две резултантни листи, т.ш. во првата резултанта листа
  3. ќе бидат бидат сместени јазли од влезната листа кои содржат парни броеви, а во втората
  4.  – непарните. Јазлите во резултантните листи се додаваат наизменично почнувајќи од почетокот
  5. и крајот на влезната листа (т.е. прво се разгледува првиот елемент од листата и се додава во
  6. соодветната резултантна листа, па последниот, па вториот итн...)
  7.  
  8. Во првиот ред од влезот е даден бројот на јазли во листата,
  9.  а во вториот ред се дадени броевите од кои се составени јазлите по редослед во листата.
  10. Во првиот ред од излезот треба да се испечатат јазлите по редослед од првата резултантна листа (т.е. парните),
  11. во вториот ред од втората (т.е. непарните) .
  12.  
  13. Име на класа (за Java): PodeliSporedParnost
  14.  
  15. Делумно решение: Задачата се смета за делумно решена доколку се поминати 7 тест примери.
  16.  
  17. Забелешка: При реализација на задачите МОРА да се користат дадените структури, а не да користат помошни структури како низи или сл.
  18.  
  19. Sample input
  20. 5
  21. 1 2 3 4 5
  22. Sample output
  23. 2 4
  24. 1 5 3
  25.  
  26. #include<stdio.h>
  27. #include<malloc.h>
  28.  
  29. //Implementacijata na dvojnata lista e so jazel vodich
  30.  
  31. typedef struct element{
  32.         int info;
  33.         struct element *llink, *rlink;
  34. }node;
  35.  
  36. node * novaDvojna()
  37. {
  38.       node *v = (node *)malloc(sizeof(node));
  39.       v -> llink = v;
  40.       v -> rlink = v;
  41.       return v;
  42. }
  43.  
  44. void dodadi(node **pok_v, int broj){
  45.     //dodavanja na broj na kraj na dvojnata lista
  46.     node *temp;
  47.     temp=(node *)malloc(sizeof(node));
  48.     temp->info=broj;
  49.     temp -> llink = (*pok_v) -> llink;
  50.     temp -> rlink = *pok_v;
  51.     (*pok_v) -> llink -> rlink = temp;
  52.     (*pok_v) -> llink = temp;
  53. }
  54.  
  55. void podeliParnost(node *l, node *lparni, node *lneparni){
  56.  
  57.         // Vasiot kod tuka
  58.  
  59. }
  60.  
  61. int main(){
  62.     node *lista=NULL, *parni=NULL, *neparni=NULL;
  63.     int i,n,info;
  64.  
  65.     lista=novaDvojna();
  66.     scanf("%d",&n);
  67.     for(i=0;i<n;i++)
  68.     {
  69.        scanf ("%d", &info);
  70.        dodadi(&lista,info);
  71.     }
  72.  
  73.     parni=novaDvojna();
  74.     neparni=novaDvojna();
  75.  
  76.     podeliParnost(lista, parni, neparni) ;
  77.  
  78.     //Pechatenje na parni
  79.     node *p=parni->rlink;
  80.     while (parni != p)
  81.     {
  82.         printf ("%d", p->info);
  83.         if(p->rlink!=parni) printf (" ");
  84.         p=p->rlink;
  85.     }
  86.     printf ("\n");
  87.  
  88.     //Pechatenje na neparni
  89.     p=neparni->rlink;
  90.     while (neparni != p)
  91.     {
  92.         printf ("%d", p->info);
  93.         if(p->rlink!=neparni) printf (" ");
  94.         p=p->rlink;
  95.     }
  96.     printf ("\n");
  97.  
  98.     return 0;
  99. }
  100. ----------------------------------------------------------------
  101. import java.io.BufferedReader;
  102. import java.io.IOException;
  103. import java.io.InputStreamReader;
  104.  
  105. class DLLNode<E> {
  106.     protected E element;
  107.     protected DLLNode<E> pred, succ;
  108.  
  109.     public DLLNode(E elem, DLLNode<E> pred, DLLNode<E> succ) {
  110.         this.element = elem;
  111.         this.pred = pred;
  112.         this.succ = succ;
  113.     }
  114.  
  115.     @Override
  116.     public String toString() {
  117.         return element.toString();
  118.     }
  119. }
  120.  
  121. class DLL<E> {
  122.     private DLLNode<E> first, last;
  123.  
  124.     public DLL() {
  125.         // Construct an empty SLL
  126.         this.first = null;
  127.         this.last = null;
  128.     }
  129.  
  130.     public void deleteList() {
  131.         first = null;
  132.         last = null;
  133.     }
  134.  
  135.     public int length() {
  136.         int ret;
  137.         if (first != null) {
  138.             DLLNode<E> tmp = first;
  139.             ret = 1;
  140.             while (tmp.succ != null) {
  141.                 tmp = tmp.succ;
  142.                 ret++;
  143.             }
  144.             return ret;
  145.         } else
  146.             return 0;
  147.  
  148.     }
  149.  
  150.     public void insertFirst(E o) {
  151.         DLLNode<E> ins = new DLLNode<E>(o, null, first);
  152.         if (first == null)
  153.             last = ins;
  154.         else
  155.             first.pred = ins;
  156.         first = ins;
  157.     }
  158.  
  159.     public void insertLast(E o) {
  160.         if (first == null)
  161.             insertFirst(o);
  162.         else {
  163.             DLLNode<E> ins = new DLLNode<E>(o, last, null);
  164.             last.succ = ins;
  165.             last = ins;
  166.         }
  167.     }
  168.  
  169.     public void insertAfter(E o, DLLNode<E> after) {
  170.         if (after == last) {
  171.             insertLast(o);
  172.             return;
  173.         }
  174.         DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
  175.         after.succ.pred = ins;
  176.         after.succ = ins;
  177.     }
  178.  
  179.     public void insertBefore(E o, DLLNode<E> before) {
  180.         if (before == first) {
  181.             insertFirst(o);
  182.             return;
  183.         }
  184.         DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
  185.         before.pred.succ = ins;
  186.         before.pred = ins;
  187.     }
  188.  
  189.     public E deleteFirst() {
  190.         if (first != null) {
  191.             DLLNode<E> tmp = first;
  192.             first = first.succ;
  193.             first.pred = null;
  194.             if (first == null)
  195.                 last = null;
  196.             return tmp.element;
  197.         } else
  198.             return null;
  199.     }
  200.  
  201.     public E deleteLast() {
  202.         if (first != null) {
  203.             if (first.succ == null)
  204.                 return deleteFirst();
  205.             else {
  206.                 DLLNode<E> tmp = last;
  207.                 last = last.pred;
  208.                 last.succ = null;
  209.                 return tmp.element;
  210.             }
  211.         }
  212.         // else throw Exception
  213.         return null;
  214.     }
  215.  
  216.     @Override
  217.     public String toString() {
  218.         String ret = new String();
  219.         if (first != null) {
  220.             DLLNode<E> tmp = first;
  221.             ret += tmp + "<->";
  222.             while (tmp.succ != null) {
  223.                 tmp = tmp.succ;
  224.                 ret += tmp + "<->";
  225.             }
  226.         } else
  227.             ret = "Prazna lista!!!";
  228.         return ret;
  229.     }
  230.  
  231.     public DLLNode<E> getFirst() {
  232.         return first;
  233.     }
  234.  
  235.     public DLLNode<E> getLast() {
  236.  
  237.         return last;
  238.     }
  239.  
  240. }
  241.  
  242. public class PodeliSporedParnost {
  243.  
  244.     public static void podeliParnost(DLL<Integer> lista, DLL<Integer> lparni, DLL<Integer> lneparni) {
  245.  
  246.         /*
  247.          *
  248.          *
  249.          * Vasiot kod tuka
  250.          *
  251.          *
  252.          */
  253.                
  254.  
  255.     }
  256.  
  257.     public static void main(String[] args) throws IOException {
  258.         DLL<Integer> lista = new DLL<Integer>(), parni = new DLL<Integer>(), neparni = new DLL<Integer>();
  259.         BufferedReader stdin = new BufferedReader(new InputStreamReader(
  260.                 System.in));
  261.         String s = stdin.readLine();
  262.         int N = Integer.parseInt(s);
  263.         s = stdin.readLine();
  264.         String[] pomniza = s.split(" ");
  265.         for (int i = 0; i < N; i++) {
  266.             lista.insertLast(Integer.parseInt(pomniza[i]));
  267.         }
  268.  
  269.         podeliParnost(lista, parni, neparni);
  270.  
  271.         // Pecatenje parni
  272.         DLLNode<Integer> tmp = parni.getFirst();
  273.         while (tmp != null) {
  274.             System.out.print(tmp.element);
  275.             if (tmp.succ != null)
  276.                 System.out.print(" ");
  277.             tmp = tmp.succ;
  278.         }
  279.         System.out.println();
  280.         // Pecatenje neparni
  281.         tmp = neparni.getFirst();
  282.         while (tmp != null) {
  283.             System.out.print(tmp.element);
  284.             if (tmp.succ != null)
  285.                 System.out.print(" ");
  286.             tmp = tmp.succ;
  287.         }
  288.         System.out.println();
  289.     }
  290.  
  291. }
  292.  
  293. //reshenie
  294. public static void podeliParnost(DLL<Integer> lista, DLL<Integer> lparni, DLL<Integer> lneparni) {
  295.  
  296.         DLLNode<Integer> first = lista.getFirst();
  297.         DLLNode<Integer> last = lista.getLast();
  298.  
  299.         while (first != last) {
  300.  
  301.             if (first.element % 2 == 0) {
  302.                 lparni.insertLast(first.element);
  303.             } else {
  304.                 lneparni.insertLast(first.element);
  305.             }
  306.  
  307.             first = first.succ;
  308.  
  309.             //last
  310.             if (last.element % 2 == 0) {
  311.                 lparni.insertLast(last.element);
  312.             } else {
  313.                 lneparni.insertLast(last.element);
  314.             }
  315.  
  316.             last = last.pred;
  317.  
  318.             if (first == last.succ) {
  319.                 break;
  320.             }
  321.         }
  322.  
  323.         if (lista.length() % 2 != 0) {
  324.             if (first.element % 2 == 0) {
  325.                 lparni.insertLast(first.element);
  326.             } else {
  327.                 lneparni.insertLast(first.element);
  328.             }
  329.         }
  330.     }
  331.  
RAW Paste Data