[C] Controllare se un array è ordinato

[blackdemonbd]

Salve ragazzi..sono al mio primo post ed inizio con questa domanda; sto studiando il c da poco per passione e anche xkè mi tocca far l'esame di università =)
ho una domanda da farvi...devo fare un programma che inseriti 20 caratteri in un array, controlli l'array...se esso è ordinato esegue una ricerca binaria di un carattere immesso precedentemente, altrimenti devo fare solo la ricerca lineare;
il problema è nel fare il sottoprogramma che verifichi se l'array è ordinato o meno...pls help
tks in anticipo...bel forum che avete

[unomichisiada]

Originariamente inviato da blackdemonbd
Salve ragazzi..sono al mio primo post ed inizio con questa domanda; sto studiando il c da poco per passione e anche xkè mi tocca far l'esame di università =)
ho una domanda da farvi...devo fare un programma che inseriti 20 caratteri in un array, controlli l'array...se esso è ordinato esegue una ricerca binaria di un carattere immesso precedentemente, altrimenti devo fare solo la ricerca lineare;
il problema è nel fare il sottoprogramma che verifichi se l'array è ordinato o meno...pls help
tks in anticipo...bel forum che avete

Dato che l'array contiene caratteri presumo tu intenda un ordinamento lessicografico, cioè a < b < c....
Dovresti chiarire anche se le maiuscole e le minuscole vanno distinte.

Comunque quanlunque sia il tipo di ordinamento che intendi, per controllare che un array sia ordinato c'è un'unica strada:fare come faresti a mano, cioè scandirlo elemento per elemento e (supposto un ordinamento crescente) controllare che ogni elmento sia < (o <= se accetti duplicati) del successivo, se c'è anche un solo elemnto che non verifica la condizione l'esito è negativo altrimenti arrivi a fine array e puoi asserire che è ordinato.

[blackdemonbd]

Originariamente inviato da unomichisiada
Dato che l'array contiene caratteri presumo tu intenda un ordinamento lessicografico, cioè a < b < c....
Dovresti chiarire anche se le maiuscole e le minuscole vanno distinte.

Comunque quanlunque sia il tipo di ordinamento che intendi, per controllare che un array sia ordinato c'è un'unica strada:fare come faresti a mano, cioè scandirlo elemento per elemento e (supposto un ordinamento crescente) controllare che ogni elmento sia < (o <= se accetti duplicati) del successivo, se c'è anche un solo elemnto che non verifica la condizione l'esito è negativo altrimenti arrivi a fine array e puoi asserire che è ordinato.

si a questo effettivamente c'ero arrivato, ma non riesco a tradurre ciò in codice c.... cmq si mi serve per un array di caratteri anche se ora lo sto facendo per un array di interi ....

[unomichisiada]

Ci risiamo...spero che tu non te la prenda ma ritengo che l'iter da seguire sia: tu scrivi del codice in cui provi a fare ciò che ti serve (che per altro è banale in questo caso anche per il fatto che l'algoritmo te l'ho già detto io a parole)--> se hai problemi,difficoltà, errori posti questo codice spiegando dove e come si verificano,-->io ti aiuto a risolvere questi errori. Spero tu ne convenga, aspetto tue notizie e il tuo codice..

[blackdemonbd]

Originariamente inviato da unomichisiada
Ci risiamo...spero che tu non te la prenda ma ritengo che l'iter da seguire sia: tu scrivi del codice in cui provi a fare ciò che ti serve (che per altro è banale in questo caso anche per il fatto che l'algoritmo te l'ho già detto io a parole)--> se hai problemi,difficoltà, errori posti questo codice spiegando dove e come si verificano,-->io ti aiuto a risolvere questi errori. Spero tu ne convenga, aspetto tue notizie e il tuo codice..

Hai più che ragione, cmq ora sto per crollare dal sonno ti farò sapere domattina ok? notte e grazie per l'aiuto!!!

[blackdemonbd]

Ecco qui il pezzo di codice da sistemare

int main()
{
  int a[SIZE];
  int i;
  int key;
  
  for (i=0; i<SIZE; i++) 
    {
      a[i]=2*i;
    }
  
      /*assegnazione temporanea per modificare l'array*/
     a[1]=10;

      printf("Immetti un numero tra 0 e 38: ");
      scanf("%d", &key);

      for (i=0; i<SIZE; i++)
	{
	  if(a[i]<a[i+1])
	    {
	      binary(a, key, 0, SIZE-1);
		}
	  else
	    {
	      linear(a , key, SIZE);
	    }
	  return 0;
	}
}

allora... SIZE è 5 quindi l'array in fine risulta:
0, 10, 4, 6, 8

il mio problema è quando devo eseguire il controllo per vedere se l'array è ordinato dunque...

for (i=0; i<SIZE; i++)
	{
	  if(a[i]<a[i+1])
	    {
	      binary(a, key, 0, SIZE-1);
		}
	  else
	    {
	      linear(a , key, SIZE);
	    }

il primo controllo che fa è se 0<10 e siccome è vero esegue
binary(a, key, 0, SIZE-1); però il programma dovrebbe eseguire quell'istruzione solo se TUTTO l'array è ordinato...come potrei fare?

[unomichisiada]

Originariamente inviato da blackdemonbd
Ecco qui il pezzo di codice da sistemare

int main()
{
  int a[SIZE];
  int i;
  int key;
  
  for (i=0; i<SIZE; i++) 
    {
      a[i]=2*i;
    }
  
      /*assegnazione temporanea per modificare l'array*/
     a[1]=10;

      printf("Immetti un numero tra 0 e 38: ");
      scanf("%d", &key);

      for (i=0; i<SIZE; i++)
	{
	  if(a[i]<a[i+1])
	    {
	      binary(a, key, 0, SIZE-1);
		}
	  else
	    {
	      linear(a , key, SIZE);
	    }
	  return 0;
	}
}

allora... SIZE è 5 quindi l'array in fine risulta:
0, 10, 4, 6, 8

il mio problema è quando devo eseguire il controllo per vedere se l'array è ordinato dunque...

for (i=0; i<SIZE; i++)
	{
	  if(a[i]<a[i+1])
	    {
	      binary(a, key, 0, SIZE-1);
		}
	  else
	    {
	      linear(a , key, SIZE);
	    }

il primo controllo che fa è se 0<10 e siccome è vero esegue
binary(a, key, 0, SIZE-1); però il programma dovrebbe eseguire quell'istruzione solo se TUTTO l'array è ordinato...come potrei fare?

Allora facciamo un po d'ordine:
innanzitutto metti il codice che verifica se l'array è ordinato oppure no all'interno di una funzione a parte che fa solo quello, chiamiamola isOrdered.Questa funzione sarà della forma

int isOrdered(int a[],int len);

Quindi tu nella tua main avrai questo codice

int main()
{
  int a[SIZE];
  int key;
  ...codice per acquisire i dati nell'array e il valore di key
  if(isOrdered(a,SIZE) == 1) 
  {
    binary(a, key, 0, SIZE-1);
  }
  else
  {
    linear(a , key, SIZE);
  }
}

Il codice per la fnzione isOrdered lo lascio a te dandoti questo suggerimento:

usa una variabile flag (bandierina).La variabile la inizializzi col valore 1 (vero, cioè è ordinato), poi fai un ciclo for in cui scandisci l'array e metti il flag a 0 (falso,cioè non è ordinato) solo se trovi una coppia elemento -successore che non verifica la condizione di ordinamento.Al termine del ciclo ritorni il valore della variabile flag.
Ciao

[blackdemonbd]

int main()
{
  int a[SIZE]={0,1,2,3,4};
  int i;
  int key;
.....
.....
.....
}

int isOrdered(int vet[],int len)
{
int flag, i;
flag=1;
for(i=0; i<SIZE; i++)
{
printf("Valore di flag: %d\n", flag);
if (vet[i]>vet[i+1])
{
flag=0;
}
}
printf("Valore di flag: %d\n", flag);
return flag;
}

mmh..dunque ho seguito il consiglio tuo...ma il prog nn va lo stesso...cioè mi esegue sempre la ric lineare ma forse ho capito xkè....dunque in questo codice ho aggiunto anche due printf che stampano il valore del flag...SIZE è 5
l output del programma è il seguente:

bash-3.00# ./tot
Immetti un numero tra 0 e 4: 3
Valore di flag: 1
Valore di flag: 1
Valore di flag: 1
Valore di flag: 1
Valore di flag: 1
Valore di flag: 0
Ricerca lineare
Valore trovato nell'elemento 3
 bash-3.00#

c'è sempre quello 0 finale che mi altera il valore del flag quindi fa sempre la ric lineare..ma come posso ovviare?
ho provato a modificare la condizione if (vet[i]>vet[i+1])
ma senza successo

[unomichisiada]

Devi arrivare solo fino al penultimo con il ciclo (cioè fino a size -1) perchè per ogni elemento accedi anche al successivo quindi se arrivi fino all'ultimo elemento fai il confronto con una locazione non valida (e sei anche fortunato che non ti crasha il programma), mi sembrava ovvio ma evidentemente no.Tieni conto che così stai considerando array con duplicati inclusi.

[blackdemonbd]

Ok perfetto...effettivamente così funziona...l'ho convertito anche in char senza grossi problemi... grazie