Algoritmo che non funziona come dovrebbe... [C]

[Dreamer89]

Ciao a tutti. Premetto: STO IMPAZZENDO! XD Allora, la prof giovedì ha dato la seguente traccia di un programma da fare in C: data una stringa, stampare a video le lettere che la compongono e il numero di volte che si ripetono. Es. la parola "pippo" dovrebbe far stampare a video questo:

p 3
i 1
o 1

Io ho provato a creare un algoritmo, ho fatto anche diagramma di flusso e ci ho fatto tanto ragionamenti sopra... conclusione?? Trovo che sia fatto giusto, ma il problema è che alla fine il risultato non è quello desiderato. Per il momento mi sono limitato a creare una stringa composta da lettere che non si ripetono:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    char parola[20],parolaF[20];
    int i,j,cont=0;
    bool flag = false;

    printf("Inserisci parola: ");
    gets(parola);

    for (i=0;i<strlen(parola);i++)
    {
        for (j=0;j<strlen(parola);j++)
        {
            if (parola[i] == parola[j])
            {
                if (flag == false)
                {
                    parolaF[cont] = parola[i];
                    cont++;
                    flag = true;
                }
            }
        }
        flag = false;
    }

    parolaF[cont] = '\0';

    printf("%s\n",parolaF);

    system("pause");
    return 0;
}

Se ad esempio inserisco la parola "casa", non solo la lettera "a" viene ripetuta 2 volte, ma la prima lettera ("c") viene anche eliminata e davvero non riesco a spiegarmi il perchè. Se c'è qualcuno che mi potrebbe dare una mano, mi sarebbe davvero di grandissimo aiuto! ^^

[MacApp]

Incomincia dalle cose semplici.
Prima scrivi un programmino che conta (ad esempio) quante 'a' ci sono in una stringa. Testalo bene, accertati che faccia bene il suo lavoro.

Poi scrivine un altro che conta quante 'b'.

Quando sarai arrivato alla 'c', (la necessità aguzza l'ingegno) ti scervellerai per trovare un modo per parametrizzare (forte dell'assioma di Peano) le due distinte funzioni utilizzate per contare le 'a' e le 'b'.

Quindi finalmente avrai una funzione ben testata per contare quante volte un certo carattere è presente in una stringa.

Arrivato a questo punto, ti dovrebbe essere abbastanza semplice, trovare il modo di iterare tra i caratteri di una stringa e contare quante volte il tal carattere sia presente nella stringa stessa.

Finalmente quando riuscirai ad evitare di ricontare (perchè lo avevi già contato) la presenza di un tal carattere nella stringa, il problema sarà risolto, ed avrai un po' di funzioni testate e riutilizzabili per risolvere futuri problemi a venire.
;-)

[alde90]

Be e se molto semplicemente come ha detto MacApp ti conti quante volte appare un carattere in una stringa e poi la chiami in un for nel tipo:

int n;
char c;
for(c='a';c<='z';c++)
{
  n = contaCarattere(stringa, c);
  if(n > 0)
    printf("%c %d", c, n);
}

e questa è un'idea, altrimenti ti fai un bel vettore di 26 e lo incrementi v[c]...

[MacApp]

Originariamente inviato da alde90 {...omissis...}
altrimenti ti fai un bel vettore di 26 e lo incrementi v[c]...

quello a cui alludi è roba sconsigliabile per chi è agli inizi.. quasi diseducativo ;-P

[alde90]

Ma dai...................non ci credo!!

A me sembra la cosa più semplice del mondo..........tipo un alfabeto che incremento in corrispondenza della lettera a mò database....

[MacApp]

Originariamente inviato da alde90
Ma dai...................non ci credo!!

A me sembra la cosa più semplice del mondo..........tipo un alfabeto che incremento in corrispondenza della lettera a mò database....

Supponi di non avere a che fare con un alfabeto di sole 26 lettere ma.. milioni...

[MItaly]

Originariamente inviato da MacApp
Supponi di non avere a che fare con un alfabeto di sole 26 lettere ma.. milioni...

#define NUMEROMILIONI 5 //dico per dire
char occorrenze[NUMEROMILIONI * 1000000];

That's it!

Scherzi a parte, non vedo perché non dovrebbe usare questo sistema: per contare le lettere (che, al di fuori dell'immaginazione, sono 26, al massimo 256 se consideriamo tutti i caratteri rappresentabili in un char) è il sistema più facile ed immediato...

[shodan]

Dimentichi unicode o UTF8

[alde90]

Sì vabbè ho capito unicode però comunque alla fine sono "solo" 65536 caratteri....il carattere si usa come indice perciò poco male no??? anche per visualizzarlo molto semplicemente si scrive (chiedo scusa se scrivo gastronerie, ma programmo principalmente in java quindi forse c'è un pò di linguaggio misto ) :

printf("ASCII\tCARATTERE\tOCCORRENZE);
for(i=0;i<65536;i++)
{
  printf("%d\t%c\t%d",i,(char)i,v[i]);
}

una cosa così molto semplice e pulita o sbaglio??

[Vincenzo1968]

La cosa può essere gestita utilizzando un albero binario di ricerca :

#include <stdio.h>
#include <tchar.h>
#include <malloc.h>

typedef struct tagTree
{
	_TCHAR info;
	int count;
	struct tagTree *left;
	struct tagTree *right;
} Tree;

Tree *NewNode(_TCHAR info)
{
	Tree *r;

	r = (Tree *) malloc(sizeof(Tree));

	if(!r)
	{
		_tprintf(_T("Memoria insufficiente\n"));
		return NULL;
	}

	r->info = info;
	r->count = 1;
	r->left = NULL;
	r->right = NULL;

	return r;
}

void TraverseInOrder(Tree *root)
{
	if(!root)
		return;

	TraverseInOrder(root->left);
	if(root->info)
		_tprintf(_T("%c -> %d\n"), root->info, root->count);
	TraverseInOrder(root->right);
}

Tree *UpdateTree(Tree *root, _TCHAR key)
{
	if( !root ) /* L'albero è vuoto */
	{
		root = NewNode(key);
		return root;
	}
	
	while( 1 )
	{
		if ( key < root->info )
		{
			if ( !root->left )
			{
				root->left = NewNode(key);
				break;
			}
			root = root->left;
		}
		else if ( key > root->info )
		{
			if ( !root->right )
			{
				root->right = NewNode(key);
				break;
			}
			root = root->right;
		}
		else
		{
			root->count++;
			break;
		}
	}

	return root;
}

void FreeTree(Tree *root)
{
	if(!root)
		return;

	FreeTree(root->left);
	FreeTree(root->right);
	if( root->info )
		free(root);
}

int _tmain(int argc, _TCHAR* argv[])
{
	_TCHAR * pStr;
	Tree * Radice = NULL;

	if ( argc < 2 )
	{
		_tprintf(_T("Numero di argomenti non valido!\n"));
		return -1;
	}

	pStr = argv[1];

	_tprintf(_T("Stringa di input: %s\n"), pStr);

	while ( *pStr != _T('\0') )
	{
		if ( !Radice )
			Radice = UpdateTree(Radice, *pStr);
		else
			UpdateTree(Radice, *pStr);
		pStr++;
	}

	TraverseInOrder(Radice);

	FreeTree(Radice);

	return 0;
}

Il programma sopra riportato, legge una stringa dalla riga dei comandi e crea l'albero binario ordinato. Per ogni carattere letto dalla stringa di input, se è gia presente nell'albero, incrementiamo il conteggio altrimenti lo inseriamo.
Infine, stampiamo i risultati attraversando l'albero "in order"; visitiamo prima il sottoalbero sinistro, poi la radice e infine il sottoalbero destro.

Avviando il programma con la seguente riga di comando :

ContaCaratteri pippo

l'output è il seguente:

i -> 1
o -> 1
p -> 3