C++ help con bubble sort e strcmp

[Prometheus ts]

int x, y;

impiegato hold;

for(x = 1; x <= SIZE - 1; x++)
{
for(y = 0; y <= SIZE - 2; y++)
{
if(strcmp(Selezionaimpiegato[y].nome, Selezionaimpiegato[y + 1].nome) > 0)



{

hold = Selezionaimpiegato[y];
Selezionaimpiegato[y] = Selezionaimpiegato[y + 1];
Selezionaimpiegato[y +1] = hold;
}
}
}

fa parte ovviamente di un altro pezzo di codice , immagino non avrete problemi a capire i riferimenti a funzioni e strutture esterne , cmq il mioproblema è che non riesco a trovare una spiegazione di come in questo meccanismo strcmp confronti ed ordini le stringhe , va bene che prende carattere per carattere ogni stringa , tuttavia come fa il confrontoi ? il valore intero che restituisce cosa rappresenta ? E come fa a sapere che è l'ordine giusto alfabetico basandosi su di un calcolo matematico , che credo venga fatto , da strcmp?
Grazie mille per le vostre risposte...

[stella_650]

va bene che prende carattere per carattere ogni stringa , tuttavia come fa il confrontoi ? il valore intero che restituisce cosa rappresenta ?

Allora la funzione strcmp(const char *s1, const char *s2)della libraria string.h, è una funzione che come hai detto confronta due stringhe,passate in input.Essa restituisce 3 tipi di valore:
-un intero minore di 0 se s1 è minore di s2( o meglio i primi n caratteri della stringa s1 sono minori degli n caratteri della stringa s2)
-un intero maggiore di 0 se s1 è maggiore di s2(i caratteri della prima stringa sono maggiori di quelli della seconda stringa)
-0 se sono uguali le due stringhe.


Ritornando al codice da te riportato, quindi, nell'if tu vai a confrontare precisamente se il primo parametro e' maggiore del secondo(riferimenti al nome)e lì non effettui affatto l'ordinamento delle componenti, cioè non è strcmp che lo determina bensì le istruzioni che vengono dopo quel costrutto di selezione cioe':

if(strcmp(Selezionaimpiegato[y].nome, Selezionaimpiegato[y + 1].nome) > 0)



{

//salvi in hold il campo con valore maggiore
hold = Selezionaimpiegato[y];
Selezionaimpiegato[y] = Selezionaimpiegato[y + 1];
//per poi aggiornarlo con quello minore
Selezionaimpiegato[y +1] = hold;
}
//alla fine di questo ciclo in pratica ti trovi le componenti ordinate.
//Per comprenderlo meglio, cerca di farti un esempio proprio come un nome 
//sostituendo i valori delle variabili con questi nomi e vedi che il ragionamento torna.

Spero di essere stata di aiuto...

[Prometheus ts]

Questo lo sapevo , ma la mia domanda è più specifica , in pratica vorrei sapere in base a cosa calcola i valori che restituisce e cosa rappresentano i valori maggiori o minori di 0 nel caso siano anche diversi da 1 o -1 , in pratica qual'è il processo che permette a strcmp di tirar fuori un valore di questo tipo ,

cosa intendi per iprimi n caratteri della stringa sono minori degli n della seconda? se due stringhe per esempio sono di 5 caratteri entrambe , differendo solo per le ultime due , come fa ad ordinarle? in base a quali valori l'algoritmo decide che una stringa viene prima di un altra in ordine alfabetico ?

in sostanza come viene deciso l'ordine alfabetico ? Qual'è la connessione nujerica?

[mapomapo]

uhm...azzardo un'ipotesi...penso ci sia una sorta di corrispondenza tra lettera e intero... quindi ad es ad 'a' è associato 1, a 'b' 2 ecc...

io prima di conoscere il return di strcmp pensavo di fare una cosa simile per ordinare alfabeticamente, ovvero utilizzando atoi e poi confrontare gli interi resituiti...

Vito

[Prometheus ts]

mi chiedo invece se strcmp non faccia in pratica una sottrazione tra valori ascii dei caratteri ed in base a questo risultato dia la differenza ..... ma è solo una mia ipotesi , vorrei avere una risposta certa....

[andbin]

Originariamente inviato da Prometheus ts

mi chiedo invece se strcmp non faccia in pratica una sottrazione tra valori ascii dei caratteri ed in base a questo risultato dia la differenza ..... ma è solo una mia ipotesi , vorrei avere una risposta certa....

Questa è una tipica implementazione:

int __cdecl strcmp (
        const char * src,
        const char * dst
        )
{
    int ret = 0 ;

    while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
        ++src, ++dst;

    if ( ret < 0 )
        ret = -1 ;
    else if ( ret > 0 )
        ret = 1 ;

    return( ret );
}

[Prometheus ts]

sI Ma strcmp cosa fa esattamente?

[Prometheus ts]

QUALCUNO HA IL SOURCE CODE DI STRCMP PER IL C++?

[andbin]

Originariamente inviato da Prometheus ts

QUALCUNO HA IL SOURCE CODE DI STRCMP PER IL C++?

La strcmp è la strcmp! Non è che c'è una strcmp per il C e una per il C++. Semmai in C++ c'è la classe string che ha ovviamente i suoi metodi per comparare 2 stringhe, e credo che faccia una cosa poi molto simile.

Se non ti è chiaro il codice sopra .... è semplice da spiegare: la strcmp prende ogni singolo carattere (allo stesso indice) di ognuna delle due stringhe e lo compara. Fino a quando due caratteri sono uguali, va avanti. Appena trova due caratteri diversi o trova il nullo su una stringa, allora esce.

[mapomapo]

mi chiedo invece se strcmp non faccia in pratica una sottrazione tra valori ascii dei caratteri ed in base a questo risultato dia la differenza ..... ma è solo una mia ipotesi , vorrei avere una risposta certa....

questo è il prototipo di string compare:

int strcmp(const char *s1, const char *s2);

vuol dire che inseriti 2 puntatori a char (ricordo che il "nome" di un array è di per sè un puntatore al primo carattere dell'array), nel fare la "comparazione" restituisce un intero...
questo intero è maggiore, minore o uguale a 0 a seconda che s1 sia maggiore, minore o uguale a s2.
banalmente nel tuo main hai una cosa di questo tipo...la butto giù lì velocemente..

#include <stdio.h>
#include <string.h>

int main()
{
          char stringa1[20], stringa2[20]; //array da comparare
          int confronto; //variabile per effettuare il controllo

          printf("Carica la prima stringa: ");
          scanf("%s", stringa1);
          printf("Carica la seconda stringa: ");
          scanf("%s", stringa2);

          confronto=strcmp(stringa1,stringa2);
          if(confronto>0)
                    printf("La stringa 2 viene prima della 1");
          else
          {
                    if(confronto<0)
                               printf("La stringa 1 viene prima della 2");
                    else
                               printf("Le due stringhe sono identiche");
          }
}

[Prometheus ts]

Forse non sono stato chiaro , quello che volgio sapere è "come" e non cosa faccia , e non mi riferisco al come agisca all'interno di un altro programma , ma cosa accafdaall'interno della funzione strcmp , confronta un carattere con l'altro daccordo , ma come? quali algoritmi usa ? che numeri tira fuori , e cosa vuol dire che un carattere è maggiore di un altro?

[mapomapo]

presumo e dico presumo che, brutalmente, faccia una sottrazione tra i rispettivi codici ascii, ovvero i numeri che vengono "ritornati" dalla funzione atoi...
i numeri associati ai caratteri, in ascii, sono sequenziali, quindi presumo che strcmp esamini il risultato della differenza e poi restituisca il -1, lo 0 oppure l'1...

esempio:
il carattere 'a' ha codice 97, e così via la 'b', la 'c'...fino a 'z' che ha 122.
supponendo di confrontare i due valori di 'a' (della stringa 1) e 'z' (della stringa 2) verrebbe 97 - 122 che è ovviamente < 0...quindi, indipendentemente dal risultato, strcmp(stringa1,stringa2) restituirà un valore pari a -1
confrondando, al contrario, 'z' ed 'a' (quindi strcmp(stringa2,stringa1)) si ha un valore > 0 e strcmp "ritorna" 1.
nel caso in cui si confrontino due stringhe con char uguali la differenza è banalmente zero.

spero di essere stato esauriente,

Vito

[Prometheus ts]

E' la stessa presunzione che ho fatto io , ma vorrei averne una certezza , possibile che non c'è nessun codice da vedere?

[marco.r]

Originariamente inviato da Prometheus ts

E' la stessa presunzione che ho fatto io , ma vorrei averne una certezza , possibile che non c'è nessun codice da vedere?

No, o meglio, se vuoi c'e' il codice del compilatore.
Per il compilatore C++ i caratteri non sono altro che dei numeri, cambiano solo le funzioni che le manipolano (ad esempio vengono stampati a video in modo diverso) , per cui quando fai 'a' < 'b' o 97 < 98 non cambia nulla. La "conversione" da 'a' a 97 avviene nel momento in cui il tuo codice viene letto dal frontend del compilatore oppure viene letto l'input da tastiera, poi e' solo un numero. Questo perlomeno nell'implementazione piu' "cruda", in cui ad esempio le lettere maiuscole (che hanno codice piu' basso di quelle minuscole) vengono considerate "minori" di quelle minuscole, cosi' che hai "ZZZ" minore di "aaa". In C++ hai pure la possibilita' (usando le string) di scegliere un tipo di confronto diverso.

[Prometheus ts]

Ok quindi ad esempioc come funzionerebbe mettere in ordine le tre parole come :

abcd
abde
abco

?

[marco.r]

Originariamente inviato da Prometheus ts

Ok quindi ad esempioc come funzionerebbe mettere in ordine le tre parole come :

abcd
abde
abco

?

Con l'algoritmo che e' stato spiegato sopra. Nota che per il computer vuol dire confrontare gli array
{ 97, 98, 99, 100, 0 }
{ 97, 98, 100, 101, 0 }
{ 97, 98, 99, 111, 0 }

Quando confronta i primi due, fa le seguenti considerazioni
confronta 97 con 97, sono uguali e quindi passa al successivo; confronta 98 con 98, sono uguali e passa al terzo elemento. 99 pero' e' minore di 100 per cui l'algoritmo si ferma e ritorna -1

[Prometheus ts]

qUINDI TIENE IN CONSIDERAZIONE IL VALORE DEL CHAR , MA ANCHE L'ORDINE in cui sono disposti giucsto? per esempio se al terzo char trova che la prima stringa contiene un char < del terzo char della seconda stringa si ferma nell'analisi e restituisce direttamente un -1?

[marco.r]

esatto