Advertisement
Guest User

Untitled

a guest
Sep 21st, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.17 KB | None | 0 0
  1. #include <iostream>
  2. #include <sstream>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. struct wiersze
  9. {
  10.     int wiersz;
  11.     wiersze * next;
  12.     wiersze()
  13.     {
  14.         next = 0;
  15.     }
  16. };
  17.  
  18. struct lista
  19. {
  20.     wiersze * pierwszy;
  21.     wiersze * ostatni;
  22.     //int f = 1;
  23.     lista()
  24.     {
  25.         pierwszy = 0;
  26.     }
  27.  
  28.     void dodaj(int wiersz)
  29.     {
  30.         if(pierwszy == 0){
  31.             ostatni = new wiersze;
  32.             ostatni->wiersz = wiersz;
  33.             pierwszy = new wiersze;
  34.             pierwszy->next = ostatni;
  35.         }
  36.         else{
  37.             wiersze * nowy = new wiersze;
  38.             nowy->wiersz = wiersz;
  39.             ostatni->next = nowy;
  40.             ostatni = nowy;
  41.         }
  42.  
  43.     }
  44.  
  45.     void show()
  46.     {
  47.         wiersze * pom = pierwszy;
  48.         pom = pom->next;
  49.         while(pom){
  50.             cout<<pom->wiersz<<" ";
  51.             pom = pom->next;
  52.         }
  53.     }
  54.     short last()
  55.     {
  56.         wiersze * pom = pierwszy;
  57.         if(pom){
  58.             if(pom->next){
  59.                 while(pom->next->next){
  60.                     pom = pom->next;
  61.                 }
  62.                 return pom->wiersz;
  63.             }
  64.         }
  65.     }
  66.     int ost()
  67.     {
  68.         return ostatni->wiersz;
  69.     }
  70. };
  71.  
  72.  
  73. struct Wierzcholek
  74. {
  75. public:
  76.     string klucz;
  77.     lista * l = new lista;
  78.     Wierzcholek* ojciec;
  79.     Wierzcholek* lsyn;
  80.     Wierzcholek* psyn;
  81.  
  82.     Wierzcholek(string klucz, int wiersz)
  83.     {
  84.         this->klucz=klucz;
  85.         ojciec=NULL;
  86.         lsyn=NULL;
  87.         psyn=NULL;
  88.     }
  89. };
  90.  
  91. struct Drzewo
  92. {
  93. public:
  94.     Wierzcholek* korzen;
  95.  
  96.     Drzewo()
  97.     {
  98.         korzen=NULL;
  99.     }
  100.     Wierzcholek* FindW(string klucz)
  101.     {
  102.         Wierzcholek* w=this->korzen;
  103.         while(w!=NULL)
  104.         {
  105.             if(w->klucz==klucz)
  106.                 return w;
  107.             else if(w->klucz>klucz)
  108.                 w=w->lsyn;
  109.             else
  110.                 w=w->psyn;
  111.         }
  112.         return w;
  113.     }
  114.  
  115.  
  116.     void inOrder(Wierzcholek* x)
  117.     {
  118.         if(x->lsyn != NULL)
  119.             inOrder(x->lsyn);
  120.         cout << x->klucz<< " =>" << " ";
  121.         x->l->show();
  122.         cout<<endl;
  123.         if(x->psyn != NULL)
  124.             inOrder(x->psyn);
  125.     }
  126.  
  127.     bool exist(string klucz)
  128.     {
  129.         Wierzcholek* w=this->korzen;
  130.         while(w!=NULL)
  131.         {
  132.             if(w->klucz==klucz)
  133.                 return true;
  134.             else if(w->klucz>klucz)
  135.                 w=w->lsyn;
  136.             else
  137.                 w=w->psyn;
  138.         }
  139.         return false;
  140.     }
  141.  
  142.     void dodaj(Wierzcholek* nowy)
  143.     {
  144.  
  145.         Wierzcholek* y=NULL;
  146.         Wierzcholek* x=this->korzen;
  147.  
  148.         while(x!=NULL)
  149.         {
  150.             y=x;
  151.             if(x->klucz > nowy->klucz)
  152.                 x=x->lsyn;
  153.             else if(x->klucz < nowy->klucz)
  154.                 x=x->psyn;
  155.             else{
  156.                 return;
  157.  
  158.             }
  159.         }
  160.  
  161.         nowy->ojciec=y;
  162.         if(y==NULL){
  163.             this->korzen=nowy;
  164.         }
  165.         else{
  166.             if(y->klucz > nowy->klucz)
  167.                 y->lsyn=nowy;
  168.             else
  169.             if(y->klucz < nowy->klucz)
  170.                 y->psyn=nowy;
  171.  
  172.         }
  173.     }
  174. };
  175.  
  176. string Mala(string a)
  177. {
  178.     int b = a.at(0);
  179.     if(b >= 65 && b <= 90){
  180.         a.at(0) = a.at(0)+32;
  181.         return a;
  182.     }
  183.     else{
  184.         return a;
  185.     }
  186. }
  187.  
  188. bool Czy_Duza(string a)
  189. {
  190.     int b = a.at(0);
  191.     if(b >= 65 && b <= 90)
  192.         return true;
  193.     else
  194.         return false;
  195. }
  196.  
  197.  
  198.  
  199.  
  200. int main()
  201. {
  202.  
  203.     Drzewo *drzewko = new Drzewo();
  204.  
  205.     int n,m;
  206.     string temp;
  207.     cin>>n;
  208.     Wierzcholek *w;
  209.     for(int i = 0; i < n; i++){
  210.         cin>>m;
  211.         for(int j = 0; j < m; j++){
  212.             cin>>temp;
  213.             if(drzewko->exist(temp) == false){
  214.                 w = new Wierzcholek(temp,i+1);
  215.                 w->l->dodaj(i+1);
  216.                 drzewko->dodaj(w);
  217.             }
  218.             else{
  219.                 w = drzewko->FindW(temp);
  220.                 if(w->l->ost() != i+1)
  221.                     w->l->dodaj(i+1);
  222.             }
  223.  
  224.         }
  225.     }
  226.     drzewko->inOrder(drzewko->korzen);
  227.     cout<<endl<<endl;
  228.     return 0;
  229.  
  230. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement