advanced code snippet search

Posted By

zoturk on 01/06/11


Tagged


Versions (?)

Zadatak 4 -SP

 / Published in: C++
 
Expand | Embed | Plain Text 
  1. // bstablo_polje.h
  2.  
  3.  
  4. typedef int labeltype;
  5.  
  6. struct element
  7. {
  8.        labeltype label;
  9.        int used;
  10. };
  11.  
  12. struct bt
  13. {
  14.        element elements[10000];
  15. };
  16.  
  17. typedef bt *btree;
  18. typedef int node;
  19.  
  20. node ParentB( int n, btree T)
  21. {
  22.           if (n==1)
  23.           {
  24.                    return 0;
  25.           }//if
  26.  
  27.           return n/2;
  28.  
  29. };
  30.  
  31. node LeftChildB(int n, btree T)
  32. {
  33.      if(T->elements[n*2].used==0)
  34.      {
  35.                                  return -1;
  36.      }//if
  37.  
  38.  
  39.      else return n*2;
  40.  
  41. };
  42.  
  43. node RightChildB(int n,btree T)
  44. {
  45.      if(T->elements[(n*2)+1].used==0) return -1;
  46.  
  47.      else return n*2+1;
  48. };
  49.  
  50. node LabelB(int n, btree T)
  51. {
  52.       if(T->elements[1].used == 0 || n<0) return 0;
  53.      return T->elements[n].label;
  54. };
  55.  
  56. node ChangeLabelB(int x,int n,btree T)
  57. {
  58.      T->elements[n].used=1;
  59.      T->elements[n].label=x;
  60.  
  61. };
  62.  
  63. node RootB(btree T)
  64. {
  65.  
  66.      return 1;
  67.  
  68. };
  69.  
  70. void CreateLeftB(int x,int n, btree T)
  71. {
  72.      if(n*2>10000) return;
  73.  
  74.      if(T->elements[n*2].used==1) return;
  75.  
  76.      else
  77.      {
  78.           T->elements[n*2].label=x;
  79.           T->elements[n*2].used=1;
  80.      }//else
  81. };
  82.  
  83. void CreateRightB(int x, int n, btree T)
  84. {
  85.      if(n*2+1>10000) return;
  86.  
  87.      if(T->elements[n*2+1].used==1) return;
  88.  
  89.      else
  90.      {
  91.           T->elements[n*2+1].label=x;
  92.           T->elements[n*2+1].used=1;
  93.      }//else
  94. };
  95.  
  96.  
  97. void DeleteB( int n, btree T)
  98. {
  99.      T->elements[n].used=0;
  100.  
  101.      if(LeftChildB(n,T)!=-1)
  102.      {
  103.                        DeleteB(LeftChildB(n,T),T);
  104.      }//if
  105.  
  106.      if(RightChildB(n,T)!=-1)
  107.      {
  108.                              DeleteB(RightChildB(n,T),T);
  109.      }//if
  110. };
  111.  
  112. btree InitB(int n, btree T)
  113. {     
  114.       if(T) delete T; 
  115.  
  116.       T = new bt;
  117.       T->elements[1].label = n;
  118.       T->elements[1].used=1;
  119.       T->elements[0].used=1;
  120.       for(int i=2;i<10000;i++) 
  121.               T->elements[i].used=0;
  122.  
  123.       return T;
  124. };
  125.  
  126.  
  127.  
  128. ///////////////////////////
  129. // bstablo_pokazivac.h
  130.  
  131. typedef int labeltype;
  132.  
  133. struct element
  134. {
  135.        labeltype label;
  136.        element *left, *right;
  137. };
  138.  
  139. typedef element *node;
  140. typedef element *btree;
  141.  
  142. node ParentB(node n, btree T)
  143. {
  144.      if(n == T) return NULL;
  145.  
  146.      node P = NULL;
  147.  
  148.      if(T->left!=NULL)
  149.      {
  150.      if(T->left == n) return T;
  151.  
  152.      else P = ParentB(n,T->left);
  153.      }//if
  154.  
  155.      if(T->right!=NULL)
  156.      {
  157.           if(T->right == n) return T;
  158.           else P = ParentB(n,T->right);
  159.      }//if
  160.  
  161.      return P;
  162. };
  163.  
  164. node LeftChildB(node n, btree T)
  165. {
  166.      if(n!=NULL || n -> left != NULL)
  167.                 return n -> left;
  168.      else NULL;
  169.  
  170. };
  171.  
  172.  
  173. node RightChildB(node n, btree T)
  174. {
  175.      if(n!=NULL || n -> right != NULL)
  176.                 return n -> right;
  177.      else NULL;
  178.  
  179. };
  180.  
  181. labeltype LabelB(node n, btree T)
  182. {
  183.           return n->label;
  184. };
  185.  
  186.  
  187. void ChangeLabelB(int x, node n, btree T)
  188. {
  189.      if(n==NULL)return;
  190.  
  191.      n->label = x;
  192.  
  193. };
  194.  
  195. node RootB(btree T)
  196. {
  197.      if(T!=NULL) return T;
  198.  
  199.      else return NULL;
  200. };
  201.  
  202. void CreateLeftB(int x, node n, btree T)
  203. {
  204.      if(n->left!=NULL) return;
  205.  
  206.      node novi = new element;
  207.      n->left= novi;
  208.      novi->label = x;
  209.      novi->left=NULL;
  210.      novi->right=NULL;
  211.  
  212. };
  213.  
  214. void CreateRightB(int x, node n, btree T)
  215. {
  216.      if(n->right!=NULL) return;
  217.  
  218.      node novi = new element;
  219.      n->right = novi;
  220.      novi->label = x;
  221.      novi->left=NULL;
  222.      novi->right=NULL;
  223.  
  224. };
  225.  
  226.  
  227. void DeleteB(node n, btree T)
  228. {
  229.      if(n->left!=NULL) DeleteB(n->left,T);
  230.  
  231.      if(n->right!=NULL) DeleteB(n->right,T);
  232.  
  233.      delete n;
  234. };
  235.  
  236. btree InitB(int n, btree T)
  237. {
  238.       if(T) delete T;
  239.       T = new element;
  240.  
  241.       T->label= n;
  242.       T->right =NULL;
  243.       T->left = NULL;
  244.  
  245.       return T;
  246. };
  247.  
  248.  
  249.  
  250. ///////////////////////////
  251. // Main.cpp
  252.  
  253.  
  254. #include<iostream>
  255. using namespace std;
  256. #include "bstablo_polje.h"
  257. //#include "bstablo_pokazivac.h"
  258.  
  259. int main()
  260. {
  261.     btree T;
  262.     int izbor,unos;
  263.     bool upis=false,upis2=false;
  264.     do{
  265.    cout<<"---------------------------------"<<endl
  266.    <<"0. Iniciranje binarnog stabla <InitB>"<<endl
  267.    <<"1. Dodavanje desnog i ljevog djeteta korjenu stabla <CreateLeftB, \n   CreateRightB>"<<endl
  268.    <<"2. Izmjena ljevog i desnog djeteta <ChangeLabelB>"<<endl
  269.    <<"3. Dodavanje desnog djeteta ljevom i desnom djetetu cvora <CreateLeftB,\n   CreateRightB>"<<endl
  270.    <<"4. Prikaz roditelja cvora <ParentB, LabelB>"<<endl
  271.    <<"5. Brisanje cvora <DeleteB>"<<endl
  272.    <<"9. Kraj"<<endl
  273.    <<"---------------------------------"<<endl;
  274.  
  275.     cin>>izbor;
  276.  
  277.     switch(izbor)
  278.     {
  279.                  case 0:
  280.                       cout<<"Korjen = ";
  281.                       cin>>unos;
  282.                       T=InitB(unos,T);
  283.                       cout<<"\t\t\t"<<LabelB(RootB(T),T)<<endl;
  284.                       break;
  285.  
  286.                  case 1:
  287.                       upis=true;
  288.                       cout<<"n_right= ";
  289.                       cin>>unos;
  290.                       CreateRightB(unos,RootB(T),T);
  291.                       cout<<"n_left= ";
  292.                       cin>>unos;
  293.                       CreateLeftB(unos,RootB(T),T);
  294.  
  295.                       cout<<"\t\t\t"<<LabelB(RootB(T),T)<<endl
  296.                       <<"\t\t   "<<LabelB(LeftChildB(RootB(T),T),T)<<"\t     "<<LabelB(RightChildB(RootB(T),T),T)<<endl;
  297.                       cout<<endl;
  298.                       break;
  299.  
  300.                  case 2:
  301.                       if (upis==false){
  302.                                        cout<<"Prvo koirstite migucnost 1...."<<endl;
  303.                                        break;
  304.                                        }
  305.                       cout<<"n_right= ";
  306.                       cin>>unos;
  307.                       ChangeLabelB(unos,RightChildB(RootB(T),T),T);
  308.                       cout<<"n_left= ";
  309.                       cin>>unos;
  310.                       ChangeLabelB(unos,LeftChildB(RootB(T),T),T);
  311.  
  312.                       cout<<"\t\t\t"<<LabelB(RootB(T),T)<<endl;
  313.                       cout<<"\t\t   "<<LabelB(LeftChildB(RootB(T),T),T)<<"\t     "<<LabelB(RightChildB(RootB(T),T),T)<<endl;
  314.  
  315.                       cout<<endl;
  316.                       break;
  317.  
  318.                  case 3:
  319.                       if (upis==false){
  320.                                        cout<<"Prvo koirstite migucnost 1...."<<endl;
  321.                                        break;
  322.                                        }
  323.  
  324.                       cout<<"n_right= ";
  325.                       cin>>unos;
  326.                       CreateRightB(unos,LeftChildB(RootB(T),T),T);
  327.  
  328.                       cout<<"\t\t\t"<<LabelB(RootB(T),T)<<endl;
  329.                       cout<<"\t\t   "<<LabelB(LeftChildB(RootB(T),T),T)<<"\t     "<<LabelB(RightChildB(RootB(T),T),T)<<endl;
  330.                       cout<<"\t\t     "<<LabelB(RightChildB(LeftChildB(RootB(T),T),T),T)<<endl;
  331.                       cout<<endl;
  332.  
  333.                       cout<<"n_right= ";
  334.                       cin>>unos;
  335.                       CreateRightB(unos,RightChildB(RootB(T),T),T);
  336.  
  337.                       cout<<"\t\t\t"<<LabelB(RootB(T),T)<<endl;
  338.                       cout<<"\t\t   "<<LabelB(LeftChildB(RootB(T),T),T)<<"\t     "<<LabelB(RightChildB(RootB(T),T),T)<<endl;
  339.                       cout<<"\t\t     "<<LabelB(RightChildB(LeftChildB(RootB(T),T),T),T)<<"\t       "<<LabelB(RightChildB(RightChildB(RootB(T),T),T),T)<<endl;
  340.                       cout<<endl;
  341.                       upis2=true;
  342.                       break;
  343.  
  344.                 case 4:
  345.                      cout<<"Roditelj broja "<<LabelB(LeftChildB(RootB(T),T),T)<<" je: "<<LabelB(ParentB(LeftChildB(RootB(T),T),T),T)<<endl;
  346.                      if(upis2==true){
  347.                      cout<<"Roditelj broja "<<LabelB(RightChildB(RightChildB(RootB(T),T),T),T)<<" je: "<<LabelB(ParentB(RightChildB(RightChildB(RootB(T),T),T),T),T)<<endl;
  348.                      }
  349.                      break;
  350.  
  351.                  case 5:
  352.                       DeleteB(LeftChildB(RootB(T),T),T);
  353.  
  354.                       cout<<"\t\t\t"<<LabelB(RootB(T),T)<<endl;
  355.                       cout<<"\t\t    "<<"\t     "<<LabelB(RightChildB(RootB(T),T),T)<<endl;
  356.                       cout<<"\t\t     "<<"\t       "<<LabelB(RightChildB(RightChildB(RootB(T),T),T),T)<<endl;
  357.  
  358.                       cout<<endl;
  359.                       break;
  360.  
  361.  
  362.     }//switch
  363. }while(izbor!=9);
  364.  
  365.  
  366.     system("pause");
  367.     return 0;
  368. };

Report this snippet  

You need to login to post a comment.