Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <sstream>
- #include <cstring>
- using namespace std;
- struct wiersze
- {
- int wiersz;
- wiersze * next;
- wiersze()
- {
- next = 0;
- }
- };
- struct lista
- {
- wiersze * pierwszy;
- wiersze * ostatni;
- //int f = 1;
- lista()
- {
- pierwszy = 0;
- }
- void dodaj(int wiersz)
- {
- if(pierwszy == 0){
- ostatni = new wiersze;
- ostatni->wiersz = wiersz;
- pierwszy = new wiersze;
- pierwszy->next = ostatni;
- }
- else{
- wiersze * nowy = new wiersze;
- nowy->wiersz = wiersz;
- ostatni->next = nowy;
- ostatni = nowy;
- }
- }
- void show()
- {
- wiersze * pom = pierwszy;
- pom = pom->next;
- while(pom){
- cout<<pom->wiersz<<" ";
- pom = pom->next;
- }
- }
- short last()
- {
- wiersze * pom = pierwszy;
- if(pom){
- if(pom->next){
- while(pom->next->next){
- pom = pom->next;
- }
- return pom->wiersz;
- }
- }
- }
- int ost()
- {
- return ostatni->wiersz;
- }
- };
- struct Wierzcholek
- {
- public:
- string klucz;
- lista * l = new lista;
- Wierzcholek* ojciec;
- Wierzcholek* lsyn;
- Wierzcholek* psyn;
- Wierzcholek(string klucz, int wiersz)
- {
- this->klucz=klucz;
- ojciec=NULL;
- lsyn=NULL;
- psyn=NULL;
- }
- };
- struct Drzewo
- {
- public:
- Wierzcholek* korzen;
- Drzewo()
- {
- korzen=NULL;
- }
- Wierzcholek* FindW(string klucz)
- {
- Wierzcholek* w=this->korzen;
- while(w!=NULL)
- {
- if(w->klucz==klucz)
- return w;
- else if(w->klucz>klucz)
- w=w->lsyn;
- else
- w=w->psyn;
- }
- return w;
- }
- void inOrder(Wierzcholek* x)
- {
- if(x->lsyn != NULL)
- inOrder(x->lsyn);
- cout << x->klucz<< " =>" << " ";
- x->l->show();
- cout<<endl;
- if(x->psyn != NULL)
- inOrder(x->psyn);
- }
- bool exist(string klucz)
- {
- Wierzcholek* w=this->korzen;
- while(w!=NULL)
- {
- if(w->klucz==klucz)
- return true;
- else if(w->klucz>klucz)
- w=w->lsyn;
- else
- w=w->psyn;
- }
- return false;
- }
- void dodaj(Wierzcholek* nowy)
- {
- Wierzcholek* y=NULL;
- Wierzcholek* x=this->korzen;
- while(x!=NULL)
- {
- y=x;
- if(x->klucz > nowy->klucz)
- x=x->lsyn;
- else if(x->klucz < nowy->klucz)
- x=x->psyn;
- else{
- return;
- }
- }
- nowy->ojciec=y;
- if(y==NULL){
- this->korzen=nowy;
- }
- else{
- if(y->klucz > nowy->klucz)
- y->lsyn=nowy;
- else
- if(y->klucz < nowy->klucz)
- y->psyn=nowy;
- }
- }
- };
- string Mala(string a)
- {
- int b = a.at(0);
- if(b >= 65 && b <= 90){
- a.at(0) = a.at(0)+32;
- return a;
- }
- else{
- return a;
- }
- }
- bool Czy_Duza(string a)
- {
- int b = a.at(0);
- if(b >= 65 && b <= 90)
- return true;
- else
- return false;
- }
- int main()
- {
- Drzewo *drzewko = new Drzewo();
- int n,m;
- string temp;
- cin>>n;
- Wierzcholek *w;
- for(int i = 0; i < n; i++){
- cin>>m;
- for(int j = 0; j < m; j++){
- cin>>temp;
- if(drzewko->exist(temp) == false){
- w = new Wierzcholek(temp,i+1);
- w->l->dodaj(i+1);
- drzewko->dodaj(w);
- }
- else{
- w = drzewko->FindW(temp);
- if(w->l->ost() != i+1)
- w->l->dodaj(i+1);
- }
- }
- }
- drzewko->inOrder(drzewko->korzen);
- cout<<endl<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement