[C] Trovare una lettera non utilizzata

**Neptune** · 29-05-2010, 18:54

Salve a tutti,
ho un vettore di chiamato nt1[] di 50 caratteri. Non è a forza tutto pieno, e può presentare caratteri non ripetuti. Come carattere tappo ho appiccicato alla fine "NULL".

Ora, io devo cercare una lettera dell'alfabeto libera, ovvero che non è presente in quel vettore, e restituirla in uscita da quella funzione, e ho provato a farlo con queste due funzioni ma c'è qualcosa che non va:

codice:

int ricerca_lineare(int nt[], int cercato)
{
    int i=0;
    int ritorno = 0;//in caso di elemento non trovato
    while((nt[i] != cercato) && (nt[i] != NULL))
    {
        i++;            
    }    
    if(nt[i] == cercato)
    {
         ritorno = 1;        
    }
    return ritorno;
}
//funzione per la ricerca di un nt non utilizzato
char trova_nt_libero(char nt1[])
{
     int i,j;
     char ritorno = 'A';
     int return_ricerca = -1;
     i=0;
     while(nt1[i] != NULL)
     {
        do
        {
            ritorno++;
            return_ricerca = ricerca_lineare(nt1,ritorno);         
        }while(return_ricerca == 1);           
        i++;
     }
      nt1[i] = ritorno;
      nt1[i+1] = NULL;
      return ritorno;               
}

La prima è il semplice algoritmo di ricerca lineare, la seconda è la mia funzione vera e propria che semplicemente scandisce il vettore degli nt, quindi finchè non arrivi al carattere tappo "NULL", e partendo dalla lettera "A" effettua la ricerca.

Se trova che quella lettera è presente nel vettore nt1, grazie al do-while, incremente di uno la lettera e continua la ricerca, non fermandosi finchè non trova una lettera non trovata e passando quindi alla posizione successiva.

Le ultime due assegnazioni sono semplicemenente delle funzione che fanno in modo di riaggiornare la lista dei nuovi non terminali ovvero, alla prossima chiamata della funzione non dovrò ne riutilizzare l'attuale lettera usata e ne quella che era stata usata in precedenza.

Quello che non capisco è perchè non va, se nel vettore ho ABC, alla prima chiamata mi da I, poi mi da K, e poi mi da di nuovo K.

Di regola dovrebbe darmi D, poi E, poi F ma sbagierò qualcosa nella logica dell'algoritmo.

Vi ringrazio in anticipo,
Neptune.

**Xaratroom** · 31-05-2010, 18:05

Non va perché hai combinato un mezzo casotto...
Prova a implementare partendo da qui:

codice:

int ricerca_lineare(int *nt, int cercato) { //cerca un carattere nell'array
	while(*nt != NULL) {
		if(*nt == cercato)
			return 0;
		nt++;
	}
	return -1;
}

int scorri_alfabeto (char *ch) { //incrementa il carattere
	if ((*ch < 'Z') && (*ch > 'A')) {
		(*ch)++;
		return 0;
	}
	return -1;
}

char trova_nt_libero(char nt1[]) { //trova la prima lettera "libera"
	char lettera = 'A';
	while (scorri_alfabeto(&lettera) == 0) {
		if (ricerca_lineare(nt1, lettera) == 0)
			return lettera;
	}
	return '\0';
}

**simo_us** · 31-05-2010, 20:29

Non va perché hai combinato un mezzo casotto...
Prova a implementare partendo da qui:
codice:

codice:

int ricerca_lineare(int *nt, int cercato) { //cerca un carattere nell'array
	while(*nt != NULL) {
		if(*nt == cercato)
			return 0;
		nt++;
	}
	return -1;
}

int scorri_alfabeto (char *ch) { //incrementa il carattere
	if ((*ch < 'Z') && (*ch > 'A')) {
		(*ch)++;
		return 0;
	}
	return -1;
}

char trova_nt_libero(char nt1[]) { //trova la prima lettera "libera"
	char lettera = 'A';
	while (scorri_alfabeto(&lettera) == 0) {
		if (ricerca_lineare(nt1, lettera) == 0)
			return lettera;
	}
	return '\0';
}

Nelle prime 2 funzioni se ritorni 1 invece di 0, nell'ultima non ti serve nemmeno il confronto "== 0" quando le richiami.

**Xaratroom** · 31-05-2010, 21:10

Grazie della precisazione ma le funzioni ritornano dei "valori standard"... ossia 0 in caso di successo e -1 in caso di errore.
Non credo sia corretto (da un punto di vista di buona programmazione) modificare i valori di ritorno.

**Neptune** · 31-05-2010, 21:25

A parte vari smanacciamenti mi sono accorto che faceva casino perchè invece di un array di char nt l'avevo passato come un array di int alla funzione di ricerca ed ovviamente mi prendeva caratteri a razzo.

Ora l'ho riaggiustata un pochino (anche perchè vedendo che non andava l'avevo pastrocchiata molto, ed è la seguente:

codice:

//Funzione di ricerca binaria
int ricerca_lineare(char nt[], char cercato)
{
    int i=0;
    int ritorno = 0;//in caso di elemento non trovato
    while((nt[i] != cercato) && (nt[i] != NULL))
    {
        i++;            
    }    
    if(nt[i] == cercato)
    {
         ritorno = 1;        
    }
    return ritorno;
}
//funzione per la ricerca di un nt non utilizzato
char trova_nt_libero(char nt1[])
{
     int i,j;
     char ritorno = 'A';
     int return_ricerca = -1;
     i=0;
     //finchè ci sono simboli non terminali
     while(nt1[i] != NULL)
     {
        do
        {
            //cerca se l'attuale lettera dell'alfabeto contenuta in ritorno è utilizzata
            return_ricerca = ricerca_lineare(nt1,ritorno);  
            if(return_ricerca == 1)
            {
                //se è già utilizzata passa alla prosisma lettera
                ritorno++;                  
            }       
        }while(return_ricerca == 1);
        //prosegue finchè non si trova una lettera non utilizzata           
        i++;
     }
      nt1[i] = ritorno;
      nt1[i+1] = NULL;
      return ritorno;               
}

Voi dite che è ancora incasinata?

**simo_us** · 31-05-2010, 21:37

Grazie della precisazione ma le funzioni ritornano dei "valori standard"... ossia 0 in caso di successo e -1 in caso di errore.
Non credo sia corretto (da un punto di vista di buona programmazione) modificare i valori di ritorno.

Sbagli.
Non esiste un valore arbitrario.
if (condizione) valuta se la condizione è vera (1), falso (0). Il valore di ritorno che tu dai al main è un'altra cosa.. Sta a significare che il programma è uscito senza errori, questioni del SO (a parte che nessuno ti vieta di ritornare un qualsiasi valore), ma non ha senso applicare questo concetto ad una funzione a parte che hai sviluppato tu.
Come codice di esempio ti posto questo piccolo esercizio:

codice:

#include <stdio.h>

#define N 10

int compare(int a[], int b[]);

int main()
{
  int i, a[] = {0,1,2,3,4,5,6,7,8,9}, b[] = {0,1,2,3,4,5,6,7,8,0};
  
  for(i=0;i<N;i++)
    printf("a[%d] = %d\tb[%d] = %d\n", i, a[i], i, b[i]);

  if(compare(a, b))
    printf("The two arrays are equals\n");
  else
    printf("The two arrays are differents\n");
    
  return 0;
}

int compare(int a[], int b[])
{
  int i = 0;

  while(i<N) {
   if(a[i] == b[i])
    i++;
   else
    return 0;
  }
  return 1;
}

Prova a cambiare i valori di ritorno nella funzione compare e vedi che i risultati sono differenti, e non corretti secondo l'implementazione dell' if in main..
Bueno, non voglio interfierire troppo con queste cose con la domanda di Neptune.

**simo_us** · 31-05-2010, 21:59

La funzione ricerca lineare io la cambierei cosi

codice:

int ricerca_lineare(char nt[], char cercato)
{
    int i=0;
    while(i<sizeof(nt))
    {
      if(nt[i] == cercato)
        i++;       
      else    
        return 0;
    }
    
    return 0;
}

Spero e penso vada bene salvo errori.. La seconfa ora non ho tempo.. Vedremo..

**simo_us** · 31-05-2010, 23:11

No, è sbagliata la logica del mio precendete, ma a parte quello è sbagliata anche la logica della tua funzione (ed io segui la tua..

)
Questa è corretta:

codice:

int ricerca_lineare(char nt[], char cercato)
{
  int i=0;
  
  while(i<sizeof(nt))      
    if(nt[i] != cercato)
      i++;
    else    
      return 1;
      
  return 0;
}

Non esiste un valore arbitrario.

Volevo dire "predefinito", scusa.

ma non ha senso applicare questo concetto ad una funzione a parte che hai sviluppato tu.

Salvo che tu voglia proprio ritornare un valore specifico in particolare. In quel caso si che ha senso if((funzione)==N))

**simo_us** · 01-06-2010, 00:17

Rompo ancora le palle ma anche quella di prima è incorretta. Se il carattere fosse all'ultimo elemento dell'array non lo troverebbe.
Questa è la definitivamente corretta:

codice:

int ricerca_lineare(char nt[], char cercato)
{
  int i=0;
  
  while(!nt) /* questa è la giusta condizione */
  {
    i++;   
    if(nt[i] != cercato)
      return 0;
    else
    {
      break;
      return 1;
    }
  }
}

Scusa ma se faccio un errore e poi ne sono coscente, mi impegno per correggerlo.

**Xaratroom** · 01-06-2010, 01:24

È conveniente spezzare il problema principale in sottoproblemi.

La logica del mio programma non funziona semplicemente perchè l'ho scritto live, solo per fornire uno spunto e ho mantenuto alcuni errorucci presenti nel codice di partenza.
Le funzioni che ho scritto possono essere utilizzate al di fuori di questo contesto, mentre, ammassare il codice non serve a molto.

Il codice completo e funzionante è il seguente:

codice:

#include <stdio.h>

int ricerca_lineare(char *nt, char cercato) { //cerca un carattere nell'array
	while(*nt != '\0') {
		if(*nt == cercato)
			return 0;
		nt++;
	}
	return -1;
}

int scorri_alfabeto (char *ch) { //incrementa il carattere
	if ((*ch <= 'Z') && (*ch >= 'A')) {
		(*ch)++;
		return 0;
	}
	return -1;
}

char trova_libero(char nt1[]) { //trova la prima lettera "libera"
	char lettera = 'A';
	do {
		if (ricerca_lineare(nt1, lettera) == -1)
			return lettera;
	} while (scorri_alfabeto(&lettera) == 0);
	return '\0';
}

int main (int argc, char* argv[]) {
	char stringa[200];
	printf("Inserire una stringa: ");
	scanf("%s%*c", stringa);
	printf("Ho trovato %c\n", trova_libero(stringa));
	return 0;
}

@simo_us Nei tuoi innumerevoli post mi sembra di capire che non hai proprio afferrato quello che scrivo, pertanto ti consiglio di andare a vedere un po' il funzionamento della standard library del c. La maggior parte delle funzioni ritornano 0 in caso di successo e -1 in caso contrario. Per convenzione, visto che stiamo programmando in c, sarebbe preferibile mantenere questo standard di codifica.

Grazie della precisazione ma le funzioni ritornano dei "valori standard"... ossia 0 in caso di successo e -1 in caso di errore.
Non credo sia corretto (da un punto di vista di buona programmazione) modificare i valori di ritorno.

Sbagli.
Non esiste un valore arbitrario.
if (condizione) valuta se la condizione è vera (1), falso (0). Il valore di ritorno che tu dai al main è un'altra cosa.. Sta a significare che il programma è uscito senza errori, questioni del SO (a parte che nessuno ti vieta di ritornare un qualsiasi valore), ma non ha senso applicare questo concetto ad una funzione a parte che hai sviluppato tu.

Qui i valori di ritorno del programma non centrano nulla.
Ha tanto senso mantenere uno standard quando si scrive del codice (questo può migliorare il processo di apprendimento e semplificare la vita di chi utilizza librerie o framework scritti da te).

Conosco il costrutto selettivo. Non era necessaria una spiegazione: pessimo codice con dentro una funzione che "fa uso del preprocessore".

Discussione: [C] Trovare una lettera non utilizzata

Strumenti discussione

Ricerca discussione

Visualizza

[C] Trovare una lettera non utilizzata

Permessi di invio