Heap C++ implementation with dictionary.
English ver in comments...
/*****************************************************************************/ /* Heap C++ implementation, methods n algorithms + dictionary showing index */ /* of an element. Polish n English menu's versions available */ /* compile: g++ -Wall -pedantic heap.cpp */ /* how to use: ./a.out -> n do whatever u want */ #include <iostream> //#define PL #define ENG using namespace std; /*****************************************************************************/ /*! * \brief Object * \param value - wartosc liczbowa * \param key - klucz */ class Object { public: int value; int key; Object() { //srand((int)time(0)); //value=rand()%(10); value=0; } ~Object(){} }; /**/ /*****************************************************************************/ /*****************************************************************************/ /*! * \brief Heap * \param Tab - tablica wartosci kopca * \param Dictionary - slownik * \param n - takie n */ class Heap { public: Object *Tab; int n; int *Dictionary; /*! * \brief Tworzy tablice obiektow rozmiaru size * oraz slownik pozwalajacy na lokaalizacje * elementow kopca gdy jego porzadek zostanie * zaburzony * */ Heap(int size) { n=size; Tab=new Object[size+1]; Dictionary=new int[size+1]; for(int i=1;i<=size+1;i++) { Tab[i].key=i; } for(int i=1;i<size+1;i++) { Dictionary[i]=Tab[i].key; } } ~Heap(){cout<<"boom!!! free machines's brain"<<endl; delete[] Tab; delete Dictionary;} /*! * \brief Ustawia wartosc tablicy o danym kluczu */ void ChangeKElement(int k,int v) { Tab[Dictionary[k]].value=v; } /*! * \brief Wypisuje wartosci kopca */ void PrintHeap() { cout<<"Heap:"<<endl<<endl;; for(int i=1;i<n+1;i++) { cout<<Tab[i].value<<endl; } } /*! * \brief Wypisuje wartosci kluczy */ void PrintKeys() { cout<<"Keys:"<<endl<<endl;; for(int i=1;i<n+1;i++) { cout<<Tab[i].key<<endl; } } /*! * \brief Wypisuje slownik */ void PrintDictionary() { cout<<"Dictionary:"<<endl<<endl;; for(int i=1;i<n+1;i++) { cout<<Dictionary[i]<<endl; } } /*! * \brief Naprawia kopiec iteracyjnie */ void FixHeapIt() { int p,d,tmp_w,tmp_k; for(int i=2;i<=n;i++) { d=i; p=d/2; tmp_w=Tab[i].value; tmp_k=Tab[i].key; while((p>0)&&(Tab[p].value>tmp_w)) { Tab[d].value=Tab[p].value; Tab[d].key=Tab[p].key; Dictionary[Tab[p].key]=d; d=p; p=d/2; Tab[d].value=tmp_w; Tab[d].key=tmp_k; Dictionary[tmp_k]=d; } } } /*! * \brief tzw swap - zamiana elementow */ void siup(int *ptr1, int *ptr2) { int tmp=*ptr1; *ptr1=*ptr2; *ptr2=tmp; } /*! * \brief Naprawia kopiec rekurencyjnie */ void FixHeapRe(int i) { int star_wars=i; if(((2*i)<n+1) && (Tab[2*i].value<Tab[star_wars].value)) star_wars=2*i; if(((2*i+1)<n+1) && (Tab[2*i+1].value<Tab[star_wars].value)) star_wars=2*i+1; if(star_wars!=i) { siup(&Tab[star_wars].value,&Tab[i].value); siup(&Tab[star_wars].key,&Tab[i].key); siup(&Dictionary[Tab[star_wars].key],&Dictionary[Tab[i].key]); FixHeapRe(star_wars); } } /*! * \brief Buduje kopiec */ void BuildHeap() { for (int i=n+1;i>0;i--) { FixHeapRe(i); } } /*! * \brief Wypisuje proste menu */ void PrintMenu() { char opt='?'; #ifdef ENG while(opt!='q') { cout<<" "<<endl; cout<<"p - print heap"<<endl; cout<<"& - print keys"<<endl; cout<<"# - print dictionary"<<endl; cout<<"z - change value of key's element"<<endl; cout<<"r - fix heap"<<endl; cout<<"q - quit"<<endl; cin>>opt; switch(opt) { case 'p': cout<<"--------"<<endl; PrintHeap(); opt='?'; break; case '&': cout<<"--------"<<endl; PrintKeys(); opt='?'; break; case '#': cout<<"--------"<<endl; PrintDictionary(); opt='?'; break; case 'z': cout<<"object's key: "<<endl; int k1,w1; cin>>k1; cout<<"object's value: "<<endl; cin>>w1; ChangeKElement(k1,w1);opt='?'; break; case 'r': cout<<"fixed:"<<endl; BuildHeap(); PrintHeap(); opt='?'; break; case 'q': cout<<"maskotky's toy says hasta la vista!"<<endl;break; } #endif #ifdef PL while(opt!='q') { cout<<" "<<endl; cout<<"p - wypisz kopiec"<<endl; cout<<"& - wypisz klucze"<<endl; cout<<"# - wypisz slownik"<<endl; cout<<"z - zamien wartosc elementu o danym kluczu"<<endl; cout<<"r - napraw kopiec"<<endl; cout<<"q - zakoncz"<<endl; cin>>opt; switch(opt) { case 'p': cout<<"--------"<<endl; PrintHeap(); opt='?'; break; case '&': cout<<"--------"<<endl; PrintKeys(); opt='?'; break; case '#': cout<<"--------"<<endl; PrintDictionary(); opt='?'; break; case 'z': cout<<"klucz: "<<endl; int k1,w1; cin>>k1; cout<<"wartosc: "<<endl; cin>>w1; ChangeKElement(k1,w1);opt='?'; break; case 'r': cout<<"naprawiony:"<<endl; BuildHeap(); PrintHeap(); opt='?'; break; case 'q': cout<<"maskotky's toy says hasta la vista"<<endl; break; } #endif } } }; /**/ /*****************************************************************************/ int main() { cout<<"\nhello, this is heap toy!"<<endl; Heap My_Heap(8); //kopiec ma 8 elementow // ustawienie elementow kopca My_Heap.ChangeKElement(1,4); My_Heap.ChangeKElement(2,3);My_Heap.ChangeKElement(3,7); My_Heap.ChangeKElement(4,9);My_Heap.ChangeKElement(5,8); My_Heap.ChangeKElement(6,5);My_Heap.ChangeKElement(7,2); My_Heap.ChangeKElement(8,1); // //My_Heap.BuildHeap(); //My_Heap.PrintHeap(); //My_Heap.PrintKeys(); //My_Heap.PrintDictionary(); My_Heap.PrintMenu(); return 0; }
No comments:
Post a Comment