[C++]Contare quante cifre di un numero intero sono presenti in un Altro

**Skull260287** · 16-06-2008, 19:52

Ciao a tutti, vi allego un esercizio, penso che dal punto di vista dell'algoritmo che lavora sull'albero non ci siano problemi, ma non sono riuscito a far andare in controllo di quante cifre di un numero sono presenti in un altro, ho cercato di fare qualcosa ma con scarsissimi risultati, vi allego la traccia ed il mio codice.

Il file albero.txt di parteza può essere 312 124 458 114 320 123 586 4178

La funzione interessata è int somma(PAnodo);

codice:

/*
   Note              : Dato un albero binario le cui chiavi sono interi,
                       determinare la somma delle chiavi dei nodi che hanno 
                       almeno due cifre in comune con almeno uno dei due figli.
*/     

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <math.h>

#define TIPO_DATO int
#define OFFSET_SPACE 5

struct node {
    int key;
    struct node* left;
    struct node* right;
};

struct node1{
        TIPO_DATO *info;           //Puntatore all'informazione tenuta dal nodo
        struct node1 *left;         //Puntatore sinistro
        struct node1 *right;        //Puntatore destro
};

struct elemCoda{
       struct node1 *elem;
       struct elemCoda *next;
};


struct Anodo{
             int key;
             Anodo *left,*right;
             };

typedef Anodo *PAnodo;

using namespace std;

void StampaBST(PAnodo ,int );
void CreaAlberoDaFile(PAnodo &);
PAnodo AlberoCasualebst(int ); //Generazione Alberi Casuali Ord
void InsertSort2( PAnodo &,int , bool &);
void DammiChiave(PAnodo ,int &);
void writeLevelTree(struct node1 *root); //Per Stampa Grafica
struct node1 *buildTree();  //Per Stampa Grafica
struct node1 *insertInOrder(struct node1 *root, TIPO_DATO info);  //Per Stampa Grafica
void pfileorder(PAnodo );
int Altezza(PAnodo );
int somma(PAnodo);

int main(){
    
    PAnodo A,B;
    struct node1 *root = NULL;
    
    CreaAlberoDaFile(A);
    //StampaBST(A,0);
    //system("pause");
    //Crea albero
    printf("\n\t\t .: 1 :. Costruzione albero...\n");
    root = buildTree();
    if (root==NULL) return 1;
    
    //Stampa albero per livelli
    system("cls");
    writeLevelTree (root);
    printf("\n\n\n");
    system("pause");
    
    cout<<"Somma: "<<somma(A)<<endl;
    
    system("pause");
    return 0;
    
}

int somma(PAnodo A){

    if(A->left!=NULL || A->right!=NULL){
                     int i=0,conta=0;
                     char* temp=(char*)A->key;
                     cout<<temp<<endl;
                     int n=0;
                     while(temp[n]!='\0') n++;
                     system("pause");
                     if(A->left!=NULL){ string temp1=(char*)A->left->key;
                     
                     for(i=0;i<n-1;i++){
                     if(temp1.find(temp[i])) conta++;
                     }}
                     
                     if(conta<2 && A->right!=NULL){
                                string temp1=(char*)A->right->key;
                                for(i=0;i<n-1;i++){
                                if(temp1.find(temp[i])) conta++;
                     }
                     }
                   
                   if(conta>=2) return somma(A->left)+somma(A->right)+A->key;
                   else return somma(A->left)+somma(A->right);
                   }}


int Altezza(PAnodo A)  
{ // CALCOLA L’ALTEZZA DELL’ALBERO A
  int Hs, Hd;
  if (A==NULL)
     return -1;
  else   {
     	Hs=Altezza(A->left); Hd=Altezza(A->right);
     	if (Hs > Hd)
        		return ++Hs;
     	else
        		return ++Hd;
 }
}

void visita(PAnodo a, int livello, int i, ofstream &outlista) {

// Check Livello
if (i == livello) {
outlista<<a->key<<"\t";
return;
}
// Incrementa contatore livello
i++;
// Visita Nodo Sinistro
if (a->left != NULL)
visita(a->left, livello, i,outlista);
// Visita Nodo Destro
if (a->right != NULL)
visita(a->right, livello, i,outlista);
}

void pfileorder(PAnodo Tree){
     
    int num;
    //cout<<"Salva Albero su FILE:"<<endl;
    string NomeLn,NomeOut;
    ifstream filista;
    ofstream outlista;
    NomeOut="albero.txt";
    outlista.open(NomeOut.c_str());
    if(!outlista){
        cerr<<"Non si puo' aprire il file!"<<endl;
        system("pause");
    }
    
    for(int k=0;k<=Altezza(Tree);k++)
    visita(Tree,k,0,outlista);
    
    outlista.close();
}

void DammiChiave(PAnodo TNode, int &TheKey)
{ //ritorna il key field del nodo puntato da Tnode, se Tnode è 
                              // NULL allora ritorna il valore di -100
	if (TNode != NULL )
	    TheKey= TNode ->key;
	else
	 TheKey= -100;
}


void StampaBST(PAnodo Tree,int i){
    if(Tree!=NULL){
        StampaBST(Tree->right,i+1);
        for(int j=1;j<=i;j++)
            cout<<" ";
        cout<<Tree->key;
        cout<<endl;
        StampaBST(Tree->left,i+1);
    }
}

void CreaAlberoDaFile(PAnodo &Tree){
    int num;
    cout<<"Crea Albero da FILE:"<<endl;
    Tree=NULL;
    string NomeLn,NomeOut;
    ifstream filista;
    ofstream outlista;
    NomeLn="albero.txt";
    filista.open(NomeLn.c_str());
    if(!filista){
        cerr<<"Non si puo' aprire il file!"<<endl;
        system("pause");
    }
   filista>>num;  
   while (!filista.eof()) { 
      bool temp=false;
      InsertSort2( Tree, num, temp); 
      if (temp==false) cout<<"Numero preesistente ="<<num<<endl;
      else cout<<" Inserito numero= "<<num<<endl;
      filista>>num;;
      }
      system("pause");
    filista.close();
}

void InsertSort2( PAnodo &A,int m, bool &inserito)   { //OK
      if(A==NULL)  {
         A=new Anodo;
         A->key = m;
         A->left=NULL;
         A->right=NULL;
         inserito=true;
         }          
      else if(A->key<m)  InsertSort2(A->right,m,inserito);
      else if(A->key>m)  InsertSort2(A->left,m,inserito);
      else inserito=false;
}

/*
 Helper function that allocates a new node
 with the given data and NULL left and right
 pointers.
*/
struct node* NewNode(int data) {
  struct node* node = new(struct node);    // "new" is like "malloc"
  node->key = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
} 

/*
 Give a binary search tree and a number, inserts a new node
 with the given number in the correct place in the tree.
 Returns the new root pointer which the caller should
 then use (the standard trick to avoid using reference
 parameters).
*/

struct node* insert(struct node* node, int data) {
  // 1. If the tree is empty, return a new, single node
  if (node == NULL) {
    return(NewNode(data));
  }
  else {
    // 2. Otherwise, recur down the tree
    if (data <= node->key) node->left = insert(node->left, data);
    else node->right = insert(node->right, data);

    return(node); // return the (unchanged) node pointer
  }
} 


struct node1 *buildTree(){
      /* int info;
       struct node1 *root = NULL;

       for(;info!=0;){
          printf("\n\tInserire elementi (0 per terminare): ");
          scanf("%d",&info);
          if (info!=0){
             printf("\tInserisco elemento %d nell'albero\n",info);
             root = insertInOrder(root,info);
             }
          }
       return root;*/
    int num;
    cout<<"Crea Albero da FILE:"<<endl;
    struct node1 *root=NULL;
    string NomeLn,NomeOut;
    ifstream filista;
    ofstream outlista;
    NomeLn="albero.txt";
    filista.open(NomeLn.c_str());
    if(!filista){
        cerr<<"Non si puo' aprire il file!"<<endl;
        system("pause");
    }
    filista>>num;
    while(!filista.eof()){
        root = insertInOrder(root,num);
        filista>>num;
    }
    filista.close();
    return root;
}

/* 2 */
       /* 2.1 */
       struct node1 *newNode(TIPO_DATO x){
              struct node1 *elem = (struct node1 *)malloc (sizeof(struct node1));
              TIPO_DATO *info = (TIPO_DATO *)malloc (sizeof(TIPO_DATO));

              if ((elem==NULL)||(info==NULL)) return NULL;

              *info =  x;
              elem->info = info;
              elem->left = NULL;
              elem->right = NULL;

              return elem;
       }

struct node1 *insertInOrder(struct node1 *root, TIPO_DATO info){
       //Caso base
       if (root == NULL) return (newNode(info));

       //Ricorsione
       if (info > *(root->info))
          root->right = insertInOrder(root->right, info);
       else
          root->left = insertInOrder(root->left, info);
       return root;
}

/* 5 */
        /* 5.1 */
        /*     Restituisce il numero di livelli dell'albero   */
        /*     (Necessario per una corretta spaziatura)       */
        int contaLivelli(struct node1 *root, int nLeft, int nRight){
            int x,y;

            if (root==NULL) return 0;
            x = contaLivelli(root->left, nLeft+1, nRight);
            y = contaLivelli(root->right, nLeft, nRight+1);

            if (x>y) return (x+1);
            return (y+1);
        }

        /* 5.2 */
        /*     Inserisce in coda alla lista puntata da "coda" il nodo x       */
        struct elemCoda *insertInTail(struct elemCoda *coda,struct node1 *x){
               struct elemCoda *tmp = (struct elemCoda *) malloc (sizeof(struct elemCoda));
               struct elemCoda *conta;

               if (tmp==NULL) return NULL;
               if (x==NULL){
                  tmp->elem = NULL;
                  tmp->next = NULL;
               } else{
                    tmp->elem = x;
                    tmp->next = NULL;
                 }

               if (coda==NULL) return tmp;

               for(conta=coda;conta->next!=NULL;conta=conta->next);

               conta->next = tmp;

               return coda;
        }


void writeLevelTree (struct node1 *root){
     struct elemCoda *coda=NULL,
                     *tmp=NULL;
                                        /* Per una "corretta" spaziatura        */
     int nLevel,                        //#livelli
         nNodesCurrentLevel,            //#nodi del livello correntemente elaborato
         currentLevel=0,                //#livello correntemente elaborato
         conta,                         //var. per ciclo spaziatura
         nCurrentNode=0;                //#nodo correntemente in esame

     //Calcolo numero livelli dell'albero
     nLevel = contaLivelli(root,1,1);  /* 5.1 */

     //Inserimento radice albero in coda alla lista
     coda = insertInTail(coda,root);   /* 5.2 */

     //Fin quando la coda dei nodi è piena...
     for(;coda!=NULL;){

              nNodesCurrentLevel=(int)pow (2, currentLevel); //#nodi del corrente livello (per spaziatura)
              ++nCurrentNode;                                //#nodo corrente rispetto al livello (per spaziatura)

              //Spaziatura prima del valore del nodo
              for (conta=0; conta<(OFFSET_SPACE*nLevel/nNodesCurrentLevel); ++conta)
                  printf(" ");

              //Valore del nodo (se il nodo non esiste, NULL, due spazi)
              if (coda->elem!=NULL)
                 printf("%d",*(coda->elem->info));
              else printf("  ");

              //Spaziatura dopo il valore del nodo
              for (conta=0; conta<(OFFSET_SPACE*nLevel/nNodesCurrentLevel); ++conta)
                  printf(" ");

              //Se sono stati stampati tutti i nodi di questo livello
              // vai a capo, azzera il #nodo corrente e incrementa
              // il valore del livello corrente
              if (nCurrentNode == nNodesCurrentLevel){
                 currentLevel++;
                 nCurrentNode=0;
                 //cout<<"\n L "<<currentLevel<<"     \n";
                printf("\n\n\n");
              }

              //Inserisci in coda i due figli (destro e sinistro) del nodo corrente.
              tmp = coda;
              coda = coda->next;
              if (tmp->elem!=NULL){
                 coda = insertInTail(coda,tmp->elem->left);
                 coda = insertInTail(coda,tmp->elem->right);
              } else
                    //Se il nodo corrente è NULL e questo in corso di elaborazione
                    // non è l'ultimo livello, inserisci in coda due figli NULL
                    // (destro e sinistro del nodo NULL) in coda (per una
                    //  "corretta" spaziatura)
                    if (currentLevel<nLevel-1){
                       coda = insertInTail(coda,NULL);
                       coda = insertInTail(coda,NULL);
                    }
     }
}

Graze 1000 a tutti

**Skull260287** · 19-06-2008, 16:02

Risolto con queste due funzioni modificate ed adattate. La funzione occorrenze ritengo sia molto utile per quello che svolge, può sempre servire infatti contare quante cifre in comune vi sono tra due numeri interi.

codice:

int occorrenze(int num, int num1)
{
 int j = 0;
 bool check=false;
 int a,b;
 int k;
 int cont = 0;
 char buff1[10], buff2[10],buff3[10];
 itoa(num, buff1, 10);
 itoa(num1, buff2, 10);
 for (k=0; k<strlen(buff1); k++)
 {
  while(j < strlen(buff2) && !check){
          a=(int) buff1[k] - (int) '0';
          b=(int) buff2[j] - (int) '0';
    if(a==b){
     cont++; check=true;
     }
     j++;
     }
    j=0;check=false;
 }
 if(num<0 && num1<0) cont-=1;
 return cont;
}  

int somma(PAnodo A){

    if(A!=NULL){
                   if(A->left!=NULL && occorrenze(A->key,A->left->key)>=2)
                   return somma(A->left)+somma(A->right)+A->key;
                   
                   else if(A->right!=NULL && occorrenze(A->key,A->right->key)>=2)
                   return somma(A->left)+somma(A->right)+A->key;
                   
                   else return somma(A->left)+somma(A->right);
                   }
                   else return 0;
                   }

Grazie a tutti cmq

**mondobimbi** · 19-06-2008, 18:21

una sola osservazione, ma con un prototipo

codice:

int occorrenze (int num, int num1) ;

come faccio a capire se sono le occorenze di num in num1 o di num1 in num ?
Prova a dare a le funzioni e agli argomenti nomi più significativi.
ciao
sergio

**Skull260287** · 19-06-2008, 19:21

Originariamente inviato da mondobimbi
una sola osservazione, ma con un prototipo

codice:

int occorrenze (int num, int num1) ;

come faccio a capire se sono le occorenze di num in num1 o di num1 in num ?
Prova a dare a le funzioni e agli argomenti nomi più significativi.
ciao
sergio

Ok, grazie mille della correzione di forma :-)

Discussione: [C++]Contare quante cifre di un numero intero sono presenti in un Altro

Strumenti discussione

Ricerca discussione

Visualizza

[C++]Contare quante cifre di un numero intero sono presenti in un Altro

Permessi di invio