Domanda [Aiuto]Implementazione Algorito Ricerca Binaria Ricorsiva

Stato
Discussione chiusa ad ulteriori risposte.
Ordina per data Ordina per reazioni
S

Santya95

Utente Jade
8 Gennaio 2010
2,564
58
429
789
Salve, il seguente è un esercizio che mi è stato assegnato.
Ho svolto tutti i punti, ma proprio non riesco a capire come implementare l'algoritmo di ricerca binaria...
Allego in basso il codice che ho scritto fino ad ora, avrei bisogno di aiuto.

Gestione archivio telefonico


Si vuole simulare l’archivio telefonico di un cellulare. Ogni nominativo è identificato
dal Cognome, Nome, numero telefonico. Provvedere all’implementazione
dell’algoritmo per la simulazione dell’archivio telefonico (massimo 30 nominativi).
Permettere, inoltre, all’utente di
• Inserire o cancellare un nominativo
• Dato il Cognome e il Nome di un utente visualizzare il numero telefonico
corrispondente (effettuare una ricerca binaria ricorsiva)
• Dato un numero telefonico vedere il numero totale di chiamate da e verso
quel numero

Ecco cosa ho steso fin ora.

Codice: 
/*Includo librerie*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>


/*SISTEMA = 1 -> Sistema Linux;*/
/*SISTEMA = 0 -> Sistema Windows;*/
#ifndef SISTEMA
#define SISTEMA 0
#endif


/*Scelgo la funzione di sistema per pulire lo schermo*/
#if SISTEMA==0
  char* pulisci = "cls";
#elif SISTEMA==1
  char* pulisci = "clear";
#endif


/*Creo la struttura per contenere i contatti*/
typedef struct
{
  char nome[50];
  char cognome[50];
  char telefono[30];
} t_contatto;


/*Creo la struttura la lista*/
struct elemento
{
  t_contatto inf;
  struct elemento *pun;
};


/*Prototipi delle funzioni*/
void visualizzaContatto(struct elemento* p);
struct elemento *aggiungiContatto(struct elemento *p);
struct elemento *rimuoviContatto(struct elemento *p);
void pausa();


int main()
{
/*Dichiaro la variabile scelta e la lista vuota*/
int scelta;
struct elemento *lista = NULL;
/*Ciclo infinito*/
  for ( ; ; )
  {
    /*Stampo il menu*/
    system(pulisci);
    printf (" #######################\n");
    printf (" #       RUBRICA       #\n");
    printf (" #######################\n\n");
    printf (" 1) VISUALIZZA CONTATTO\n\n");
    printf (" 2) AGGIUNGI CONTATTO\n\n");
    printf (" 3) RIMUOVI CONTATTO\n\n");
    printf (" 0) ESCI\n\n\n\n");
    printf (" la tua scelta > ");
    scanf ("%i", &scelta);
    scelta = (int)scelta;


    if (scelta == 0)
    {
    system(pulisci); /*PULISCE LO SCHERMO*/
      printf ("--------------------------------------\n");
      printf (" RUBRICA V. 0.1\n");
      printf (" Programma creato da Ettore Noviello\n");
      printf ("--------------------------------------\n\n");
      break;
}


    else if (scelta == 1) /*Visualizzo i contatti presenti*/
    {
      visualizzaContatto(lista);
      }
    else if (scelta == 2) /*Aggiungo un nuovo contatto*/
    {
      lista = aggiungiContatto(lista);
      }
    else if (scelta == 3) /*Rimuovo un contatto*/
    {
      lista = rimuoviContatto(lista);
     }
    }
   }


/*Fine del MAIN, adesso ci sono le funzioni che eseguono il compito a loro assegnato*/


/*Visualizza i contatti presenti*/
void visualizzaContatto(struct elemento* p)
{
  if (p == NULL)
  {


    /*Se non ci sono contatti lo stampo a video*/
    system(pulisci);
    printf (" #######################\n");
    printf (" #       RUBRICA       #\n");
    printf (" #######################\n");
    printf (" # VISUALIZZA CONTATTO #\n");
    printf (" #######################\n\n");
    printf (" Nessun contatto presente\n");
    pausa();


  } else {
    /*Stampo il primo contatto presente*/
    system(pulisci);
    /*Inizializzo variabile pseudocasuale per il numero di chiamate*/
    int chiamate_1=0;
    srand(time(NULL));
    for(chiamate_1=0; chiamate_1 <100; chiamate_1++)
    {}
    printf (" #######################\n");
    printf (" #       RUBRICA       #\n");
    printf (" #######################\n");
    printf (" # VISUALIZZA CONTATTO #\n");
    printf (" #######################\n\n");
    printf (" NOME > %s\n", p->inf.nome);
    printf (" COGNOME > %s\n", p->inf.cognome);
    printf (" TELEFONO > %s\n", p->inf.telefono);
    printf (" CHIAMATE EFFETTUATE A QUESTO NUMERO: %d\n", rand() % 11);
    printf (" CHIAMATE RICEVUTE DA QUESTO NUMERO: %d\n", rand() % 11);
    pausa();
    }
    while (p != NULL)
  {
   /*Stampo gli altri contatti*/
    system(pulisci);
    /*Inizializzo variabile pseudocasuale per il numero di chiamate*/
    int chiamate_2=0;
    srand(time(NULL));
    for(chiamate_2=0; chiamate_2 <100; chiamate_2++)
    {}
    printf (" #######################\n");
    printf (" #       RUBRICA       #\n");
    printf (" #######################\n");
    printf (" # VISUALIZZA CONTATTO #\n");
    printf (" #######################\n\n");
    printf (" NOME > %s\n", p->inf.nome);
    printf (" COGNOME > %s\n", p->inf.cognome);
    printf (" TELEFONO > %s\n", p->inf.telefono);
    printf (" CHIAMATE EFFETTUATE A QUESTO NUMERO: %d\n", rand() % 11);
    printf (" CHIAMATE RICEVUTE DA QUESTO NUMERO: %d\n", rand() % 11);
    pausa();
    /*Leggo l'elemento successivo*/
    p = p->pun;
  }
  return;
}
/*Aggiungo un nuovo contatto*/
struct elemento *aggiungiContatto(struct elemento *p)
{
  system(pulisci);
  printf (" #######################\n");
  printf (" #       RUBRICA       #\n");
  printf (" #######################\n");
  printf (" #  AGGIUNGI CONTATTO  #\n");
  printf (" #######################\n\n");


  /*Dichiaro le variabili*/
  char nome[50];
  char cognome[50];
  char telefono[30];
  t_contatto daInserire;
  struct elemento *punt;


  /*Popolo la variabile daInserire*/
  printf (" NOME > ");
  scanf ("%s", nome);
  strcpy(daInserire.nome, nome);
  printf (" COGNOME > ");
  scanf ("%s", cognome);
  strcpy(daInserire.cognome, cognome);
  printf (" TELEFONO > ");
  scanf ("%s", telefono);
  strcpy(daInserire.telefono, telefono);


  if(p != NULL)
  {
    /*Creazione elementi successivi*/
    /*Alloco la memoria necessaria*/
    punt = (struct elemento *)malloc(sizeof(struct elemento));
    /*Metto daInserire nell'informazione del puntatore*/
    punt->inf = daInserire;
    /*Metto il puntatore in testa alla lista*/
    punt->pun = p;


  } else {
    /*Creazione primo elemento*/
    /*Alloco la memoria necessaria*/
    p = (struct elemento *)malloc(sizeof(struct elemento));
    /*Metto daInserire nell'informazione del puntatore*/
    p->inf = daInserire;
    /*p punta a NULL, ovvero il marcatore di fine lista*/
    p->pun = NULL;
    /*Assegno p a punt*/
    punt = p;
   }
  /*Esce dalla funzione e restituisce la lista*/
  return(punt);


} /*Rimuovo un contatto*/
struct elemento *rimuoviContatto(struct elemento *p)
{
  struct elemento *aus;
  struct elemento *twin = p;
  int subscelta;
  int i=1;
  int n=1;


  /*Stampo la schermata*/
  system(pulisci);
  printf (" #######################\n");
  printf (" #       RUBRICA       #\n");
  printf (" #######################\n");
  printf (" #   RIMUOVI CONTATTO  #\n");
  printf (" #######################\n\n");


  while (p != NULL)
  {
    printf ("%i) \t %s \t %s\n", i, p->inf.nome, p->inf.cognome);
    p = p->pun;
    i++;
}
  /*Ottengo il valore originario di p*/
  p = twin;
  /*Scelgo l'emento da eliminare*/
  printf("\n\n Inserisci il numero del contatto che vuoi rimuovere: ");
  scanf("%i", &subscelta);
  if (subscelta < i)
  {
    /*Se la lista e' vuota esco*/
    if(p == NULL)
      return;
    /*Se la lista ha almeno due elmenti...*/
    if(p->pun != NULL)
    {
      /*Inizializzo un puntatore ausiliario...*/
      aus=p;
      n++;
      /*... e faccio un ciclo per trovare l'elemento da eliminare ...*/
      while(n != i)
      {
        if(subscelta == n)
        {
          aus->pun=aus->pun->pun;
        } else
        {
          aus=aus->pun;
          }
        n++;
     }
    }
    /*Se si vuole rimuovere il primo elemento, si assegna a p il valore del suo oggetto puntato; questo accade quando subscelta == 1*/
    if(subscelta == 1)
    {
      p=p->pun;
      }
  }
  twin = p;
  return twin;
}
/*Funzione che blocca lo schermo ad aspetta che l'utente prema INVIO*/
void pausa()
{
  char invio;
  printf("\n\n - Premi INVIO per continuare. -\n");
  invio = getchar();
  return;
}
 
Hai preso in considerazione che per sviluppare la ricerca binaria tutti gli elementi devono essere ordinati?
Inoltre ti complichi un po' la vita ad utilizzare un adt come la lista concatenata semplice, sarebbe più pratico utilizzare un array
 
Singh™ ha detto:
Hai preso in considerazione che per sviluppare la ricerca binaria tutti gli elementi devono essere ordinati?
Inoltre ti complichi un po' la vita ad utilizzare un adt come la lista concatenata semplice, sarebbe più pratico utilizzare un array
Clicca per espandere...

Non ho capito cosa intendi... Potresti farmi un esempio?
 
Ultima modifica:
Allora il prerequisito di una ricerca binaria(che sia ricorsiva o non) è il fatto che la struttura nella quale vuoi applicare il metodo deve essere ORDINATA
Ordinata -> tutti gli elementi devono essere crescenti o decrescenti(meglio crescenti)

Ecco un esempio
PHP: 
#include <iostream>
using namespace std;
int ric_bin(int *,int, int ); /*Struttura passata è l'array, non voglio risolverti l'esercizio ti mostro solo l'esempio cosi provi da solo*/
int selection_sort(int *,int);/*il selection sort, per eseguire l'ordinamento.Puoi usare qualsiasi algoritmo per ordinare, io mi trovo meglio con questo*/
int main()
{
int k,i;
cout<<"Inserisci dimensione"<<endl;//equivalente al printf
cin>>k; // scanf;
int *p = new int[k];
for(i =0;i<k;i++)
{
cin>>p[i];//caricamento
}
selection_sort(p,k);i
f(ric_bin(p,k,5)!=-1) cout<<"\ntrovato"<<endl;
else cout<<"fuck iea"<<endl;
}
int selection_sort(int *p, int k)
{
int i,j,temp;
for(i =0; i < k;i++)
{ for(j = i+1;j<k;j++) 
 {    if(p[j] < p[i]) // la famosa condizione, se la inverti l'ordinamento sarà decrescente
       { //effettuo lo swap
         temp = p[j];
         p[j] = p[i];
         p[i] = temp;
        } 
  }
 }
}
int ric_bin(int *p,int k,int d) //k la dimensione, d la chiave(elemento da trovare)
{
k = k/2;  
if(p[k] == d) return d;// per la ricorsione bisogna trovare il passo base, credo si chiami cosi
if(k == 0) return -1; // se non è stato trvoato;
if(p[k] >d) return ric_bin(p,k-1,d); /* se l'elemento all'iesimo posto è maggiore della chiave, significa che la chiave si trova nella prima parte dell'array.Ecco perchè bisogna ordinarlo*/    

return k+1+ric_bin(&p[k+1],k,d); /*sarebbe l'else, cioè che viene presa la seconda parte dell'array nel caso non si la chiave è maggiore di p[k];*/
}

L'ho scritto adesso al volo, non ci dovrebbero essere errori, se ci sono, chiedo venia
 
Singh™ ha detto:
Allora il prerequisito di una ricerca binaria(che sia ricorsiva o non) è il fatto che la struttura nella quale vuoi applicare il metodo deve essere ORDINATA
Ordinata -> tutti gli elementi devono essere crescenti o decrescenti(meglio crescenti)

Ecco un esempio
PHP: 
#include <iostream>
using namespace std;
int ric_bin(int *,int, int ); /*Struttura passata è l'array, non voglio risolverti l'esercizio ti mostro solo l'esempio cosi provi da solo*/
int selection_sort(int *,int);/*il selection sort, per eseguire l'ordinamento.Puoi usare qualsiasi algoritmo per ordinare, io mi trovo meglio con questo*/
int main()
{
int k,i;
cout<<"Inserisci dimensione"<<endl;//equivalente al printf
cin>>k; // scanf;
int *p = new int[k];
for(i =0;i<k;i++)
{
cin>>p[i];//caricamento
}
selection_sort(p,k);i
f(ric_bin(p,k,5)!=-1) cout<<"\ntrovato"<<endl;
else cout<<"fuck iea"<<endl;
}
int selection_sort(int *p, int k)
{
int i,j,temp;
for(i =0; i < k;i++)
{ for(j = i+1;j<k;j++) 
 {    if(p[j] < p[i]) // la famosa condizione, se la inverti l'ordinamento sarà decrescente
       { //effettuo lo swap
         temp = p[j];
         p[j] = p[i];
         p[i] = temp;
        } 
  }
 }
}
int ric_bin(int *p,int k,int d) //k la dimensione, d la chiave(elemento da trovare)
{
k = k/2;  
if(p[k] == d) return d;// per la ricorsione bisogna trovare il passo base, credo si chiami cosi
if(k == 0) return -1; // se non è stato trvoato;
if(p[k] >d) return ric_bin(p,k-1,d); /* se l'elemento all'iesimo posto è maggiore della chiave, significa che la chiave si trova nella prima parte dell'array.Ecco perchè bisogna ordinarlo*/    

return k+1+ric_bin(&p[k+1],k,d); /*sarebbe l'else, cioè che viene presa la seconda parte dell'array nel caso non si la chiave è maggiore di p[k];*/
}

L'ho scritto adesso al volo, non ci dovrebbero essere errori, se ci sono, chiedo venia
Clicca per espandere...

Saresti cosi gentile da convertirmela in C? Sarebbe uun gran bel aiuto, dato che non ho mai studiato C++.
 
Santya95 ha detto:
Saresti cosi gentile da convertirmela in C? Sarebbe uun gran bel aiuto, dato che non ho mai studiato C++.
Clicca per espandere...
PHP: 
#include <stdio.h>#include <stdlib.h>int ric_bin(int *,int, int ); /*Struttura passata è l'array, non voglio risolverti l'esercizio ti mostro solo l'esempio cosi provi da solo*/int selection_sort(int *,int);/*il selection sort, per eseguire l'ordinamento.Puoi usare qualsiasi algoritmo per ordinare, io mi trovo meglio con questo*/int main(){int k,i;printf("Inserisci dimensione");//equivalente al printfscanf("%d",&k); // scanf;int *p = (int *)malloc(sizeof(int)*k); // sostituisci con int p[500] se vuoi gestire tutto staticamentefor(i =0;i<k;i++){scanf("%d",&p[i]);//caricamento}selection_sort(p,k);if(ric_bin(p,k,5)!=-1) printf("\nTrovato");else printf("\nfuck iea");}int selection_sort(int *p, int k){int i,j,temp;for(i =0; i < k;i++){ for(j = i+1;j<k;j++)  {    if(p[j] < p[i]) // la famosa condizione, se la inverti l'ordinamento sarà decrescente       { //effettuo lo swap         temp = p[j];         p[j] = p[i];         p[i] = temp;        }   } }}int ric_bin(int *p,int k,int d) //k la dimensione, d la chiave(elemento da trovare){k = k/2;  if(p[k] == d) return d;// per la ricorsione bisogna trovare il passo base, credo si chiami cosiif(k == 0) return -1; // se non è stato trvoato;if(p[k] >d) return ric_bin(p,k-1,d); /* se l'elemento all'iesimo posto è maggiore della chiave, significa che la chiave si trova nella prima parte dell'array.Ecco perchè bisogna ordinarlo*/    
return k+1+ric_bin(&p[k+1],k,d); /*sarebbe l'else, cioè che viene presa la seconda parte dell'array nel caso non si la chiave è maggiore di p[k];*/}

- - - Updated - - -

:| sto editor sfascia via tutto


Ecco http://pastebin.com/V0QpxL7v

- - - Updated - - -

Te lo posso semplificare ancora di più se non capisci
 
Singh™ ha detto:
Allora il prerequisito di una ricerca binaria(che sia ricorsiva o non) è il fatto che la struttura nella quale vuoi applicare il metodo deve essere ORDINATA
Ordinata -> tutti gli elementi devono essere crescenti o decrescenti(meglio crescenti)

Ecco un esempio
PHP: 
#include <iostream>
using namespace std;
int ric_bin(int *,int, int ); /*Struttura passata è l'array, non voglio risolverti l'esercizio ti mostro solo l'esempio cosi provi da solo*/
int selection_sort(int *,int);/*il selection sort, per eseguire l'ordinamento.Puoi usare qualsiasi algoritmo per ordinare, io mi trovo meglio con questo*/
int main()
{
int k,i;
cout<<"Inserisci dimensione"<<endl;//equivalente al printf
cin>>k; // scanf;
int *p = new int[k];
for(i =0;i<k;i++)
{
cin>>p[i];//caricamento
}
selection_sort(p,k);i
f(ric_bin(p,k,5)!=-1) cout<<"\ntrovato"<<endl;
else cout<<"fuck iea"<<endl;
}
int selection_sort(int *p, int k)
{
int i,j,temp;
for(i =0; i < k;i++)
{ for(j = i+1;j<k;j++) 
 {    if(p[j] < p[i]) // la famosa condizione, se la inverti l'ordinamento sarà decrescente
       { //effettuo lo swap
         temp = p[j];
         p[j] = p[i];
         p[i] = temp;
        } 
  }
 }
}
int ric_bin(int *p,int k,int d) //k la dimensione, d la chiave(elemento da trovare)
{
k = k/2;  
if(p[k] == d) return d;// per la ricorsione bisogna trovare il passo base, credo si chiami cosi
if(k == 0) return -1; // se non è stato trvoato;
if(p[k] >d) return ric_bin(p,k-1,d); /* se l'elemento all'iesimo posto è maggiore della chiave, significa che la chiave si trova nella prima parte dell'array.Ecco perchè bisogna ordinarlo*/    

return k+1+ric_bin(&p[k+1],k,d); /*sarebbe l'else, cioè che viene presa la seconda parte dell'array nel caso non si la chiave è maggiore di p[k];*/
}

L'ho scritto adesso al volo, non ci dovrebbero essere errori, se ci sono, chiedo venia
Clicca per espandere...

Ormai è tempo che non prendo un manuale in mano e quindi molte cose me le sono ormai dimenticate (o mai studiate [emoji38]) ma questo non dovrebbe creare un Memory Leak? Credo ti sia proprio dimenticato di deallocare la memoria allocata nel main col malloc (o col new in caso si parli di C++)..
 
Skhiroth ha detto:
Ormai è tempo che non prendo un manuale in mano e quindi molte cose me le sono ormai dimenticate (o mai studiate [emoji38]) ma questo non dovrebbe creare un Memory Leak? Credo ti sia proprio dimenticato di deallocare la memoria allocata nel main col malloc (o col new in caso si parli di C++)..
Clicca per espandere...
Si beh, mi sono dimenticato

- - - Updated - - -

Ma ormai l'autore ha capito e credo abbia implementato il suo codice prendendo esempio dal mio
 
Stato
Discussione chiusa ad ulteriori risposte.

DISCUSSIONI SIMILI

D
Guida Split-lock in Linux: che cos'è?
Risposte 
0
Visualizzazioni 
81
DispatchCode ha risposto
DispatchCode
Indietro
Top Bottom