Ciao a tutti! Sto preparando programmazione2 e avrei bisogno di capire come funzionano le strutture annidate.
Devo implementare una BST-List, ossia una lista i cui elementi sono degli alberi che possono contenere al più k elementi. Se l'albero continiene già k elementi, allora creo un nuovo nodo della lista che sarà quindi il nuovo albero.
Ho implementato sia lista che albero ma il mio problema sorge quando devo fare la struttura annidata. Esattamente alla insert. Qualcuno può aiutarmi??
PS: Lista e Albero hanno tutti i metodi perfettamente funzionanti.
codice:#include <iostream> using namespace std; template <class H> class NodoL{ private: NodoL<H>*prev, *next; H*key; public: NodoL(H*key=NULL){ if(key){this->key=new H(*key);} next=prev=NULL; } NodoL<H>*getNext(){return next;} NodoL<H>*getPrev(){return prev;} H*getKey(){return key;} void setNext(NodoL<H>*next){this->next=next;} void setPrev(NodoL<H>*prev){this->prev=prev;} void setKey(H*key){this->key=key;} }; template <class H> class DList{ private: NodoL<H>* head, *tail, *current; public: DList(){ head=new NodoL<H>(); tail=new NodoL<H>(); head->setNext(tail); tail->setPrev(head); } //inserimento ordinato DList<H> *ins(H elDaInserire){ // il nome intendo elementDaInser NodoL<H>*nodoDaInserire=new NodoL<H>(&elDaInserire); //questo è il nodo da inserire NodoL<H>*tmp=head->getNext(); // cout<<"*tmp->getKey(): "<<tmp->getKey()<<endl; // cout<<"elDaInserire: "<<elDaInserire<<endl; while(tmp!=tail&&*tmp->getKey()<elDaInserire){ // &elDaInserire? tmp=tmp->getNext(); } nodoDaInserire->setNext(tmp); nodoDaInserire->setPrev(tmp->getPrev()); tmp->getPrev()->setNext(nodoDaInserire); tmp->setPrev(nodoDaInserire); return this; } void insertL(H x){ ins(&x); } H* search(H elDaCercare){ //elemDaCercare NodoL<H>*tmp=head->getNext(); while(tmp!=tail&&*tmp->getKey()!=elDaCercare){ tmp=tmp->getNext(); } if(tmp!=tail){ // cout<<"Elemento "<<elDaCercare<<" trovato."<<endl; return tmp->getKey(); } else{ //cout<<"Elemento "<<elDaCercare<<" non trovato."<<endl; return NULL; } } DList<H>* print(){ NodoL<H>*tmp=head->getNext(); cout<<"Lista: "; while(tmp!=tail){ cout<<*tmp->getKey()<<" "; tmp=tmp->getNext(); } cout<<endl; return this; } DList<H>*canc(H elDaCancellare){ // NodoL<H>*nodoDaCancellare=new NodoL<H>(elDaCancellare); NodoL<H>*tmp=head->getNext(); while(tmp!=tail&&*tmp->getKey()!=elDaCancellare){ tmp=tmp->getNext(); } if(tmp!=tail){ tmp->getNext()->setPrev(tmp->getPrev()); tmp->getPrev()->setNext(tmp->getNext()); delete tmp; return this; } else return this; } H*begin(){ current=head; return next(); } H*next(){ if(current==tail)return NULL; if(current->getNext()==tail)return NULL; current=current->getNext(); return current->getKey(); } }; template<class H> class NodoT{ private: NodoT<H>*right, *left, *parent; H*key; public: NodoT(H*key=NULL){ if(key)this->key=new H(*key); left=right=parent=NULL; } NodoT<H>*getLeft(){return left;} NodoT<H>*getRight(){return right;} NodoT<H>*getParent(){return parent;} H* getKey(){return key;} void setRight(NodoT<H>*right){this->right=right;} void setLeft(NodoT<H>*left){this->left=left;} void setParent(NodoT<H>*parent){this->parent=parent;} void setKey(H*key){this->key=key;} }; template<class H>class BST{ private: NodoT<H>*root; int n; public: BST(){ root=NULL; n=0; } NodoT<H>*getMin(NodoT<H>*x){ if(!x)return NULL; NodoT<H>*tmp=x; while(tmp->getLeft()){ tmp=tmp->getLeft(); } return tmp; } H*minimum(){ NodoT<H>*min=getMin(root); if(min!=NULL)return min->getKey(); else return NULL; } NodoT<H>*successor(NodoT<H>*x){ NodoT<H>*tmp=x; if(tmp->getRight()){return getMin(tmp->getRight());} else{ NodoT<H>*el=tmp->getParent(); while(el&&el->getRight()==tmp){ tmp=el; el=el->getParent(); } return el; } } H*succ(H x){ NodoT<H>*s=new NodoT<H>(&x); NodoT<H>*n=successor(s); if(n!=NULL)return n->getKey(); else return NULL; } H*search(H x){ NodoT<H>*tmp=root; while(tmp&&*tmp->getKey()!=x){ if(x>=*tmp->getKey()){ tmp=tmp->getRight(); } else tmp=tmp->getLeft(); } if(tmp){ return tmp->getKey(); } else return NULL; } BST<H>*ins(H elDaInserire){ if(n<4){ NodoT<H>*tmp=root; NodoT<H>*nodoDaInserire=new NodoT<H>(&elDaInserire); NodoT<H>*tparent=NULL; while(tmp){ tparent=tmp; if(elDaInserire>=*tmp->getKey()){ tmp=tmp->getRight(); } else tmp=tmp->getLeft(); } nodoDaInserire->setParent(tparent); if(!tparent){root=nodoDaInserire;} else if(elDaInserire>=*tparent->getKey()){tparent->setRight(nodoDaInserire);} else tparent->setLeft(nodoDaInserire); return this; } else cout<<"Albero pieno!"<<endl; return this; } void insertb(H x){ ins(x); } void trapianta(NodoT<H>*a, NodoT<H>*b){ if(!a->getParent()){ root=b; } else{ if(a==a->getParent()->getRight()){a->getParent()->setRight(b);} else a->getParent()->setLeft(b); } if(b){b->setParent(a->getParent());} } NodoT<H>*find(H x){ NodoT<H>*tmp=root; while(tmp&&*tmp->getKey()!=x){ if(x>=*tmp->getKey()){ tmp=tmp->getRight(); } else tmp=tmp->getLeft(); } return tmp; } BST<H>*canc(H elDaCancellare){ //cout<<"entro nella canc"<<endl; NodoT<H>*nodoDaCancellare=find(elDaCancellare); if(nodoDaCancellare){ // cout<<"canc:"<<elDaCancellare; if(!nodoDaCancellare->getRight()){ trapianta(nodoDaCancellare, nodoDaCancellare->getLeft()); } else if(!nodoDaCancellare->getLeft()){ trapianta(nodoDaCancellare, nodoDaCancellare->getRight()); } else{ NodoT<H>*succ=getMin(nodoDaCancellare->getRight()); if(nodoDaCancellare!=succ->getParent()){ trapianta(succ, succ->getRight()); succ->setRight(nodoDaCancellare->getRight()); nodoDaCancellare->getRight()->setParent(succ); } trapianta(nodoDaCancellare, succ); nodoDaCancellare->getLeft()->setParent(succ); succ->setLeft(nodoDaCancellare->getLeft()); } delete nodoDaCancellare; n--; //return this; } return this; } void inOrder(NodoT<H>*p){ if(p){ inOrder(p->getLeft()); cout<<*p->getKey()<<" "; inOrder(p->getRight()); } } bool pieno(){ if(n=4)return true; else return false; } void print(){ cout<<"BST: "; inOrder(root); cout<<endl; } }; template<class H> class BSTList{ private: DList< BST<H> >*bl; public: BSTList(){ bl=new DList< BST<H> >(); } BSTList<H>*insert(H x){ if(!bl->begin()){ BST<H>*nuovo=new BST<H>(); nuovo->insertb(x); bl->insertL(nuovo); } else{ BST<H>*el=bl->begin(); if(!el->pieno()){ BST<H>*nuovo=new BST<H>(); nuovo->insertb(x); bl->insertL(nuovo); } else { el->insertb(x); } } return this; } void print(){ BST<H>*tmp=bl->head->getNext(); while(tmp){ bl->print(); tmp=bl->next(); } } }; int main(){ BSTList<int>*bl=new BSTList<int>(); bl->insert(8); return 0; }
Rispondi quotando
