Algoritmo di Huffman

di Anonimizzato19239 il
7 risposte
/
Anonimizzato19239
Utente anonimizzato
Sto scrivendo il codice di un programma che permetta di applicare la compressione, in questo caso di una frase, basandomi sull'algoritmo di Huffman.
Usando uno shift indietro elimino le lettere della frase che si presentano, nella stessa frase, con minor frequenza. Utilizzo due vettori paralleli oltre a "frase": uno è quello che conserva le lettere presenti nella frase ("lettere"), e l'altro quello che conserva la frequenza della lettera nella frase ("conta"). Una volta caricati questi vettori il programma controlla, con l'ausilio di un ciclo, qual è la lettera che viene ripetuta meno volte e questa viene salvata all'interno della variabile "min". Qui utilizzo lo shift indietro, che modifica "frase" eliminando la lettera con minor frequenza al corrente giro del ciclo. Il fatto è che, man mano che vengono eliminate le lettere da "frase", ci sarà sempre una lettera con minor frequenza rispetto ad un'altra: come fare, quindi, per evitare che il vettore "frase" perda ogni carattere e che invece funzioni correttamente tenendo in "frase" le lettere che effettivamente si ripetono maggiormente?

Il codice: 
#include<stdio.h>
#include<ctype.h>
#include<string.h>

void sposta(int min, int conta[], char frase[], int lettere[])
{
    int i;

    for(i=min; i<strlen(frase); i++)
    {
        //printf("________________\n%s", frase);
        frase[i]=frase[i+1];
    }
}

int main()
{
    char frase[1000];
    int c, ascii, i=0, z, s=0, a=0;
    int conta[26], lettere[26];

    printf("Frase: "); fgets(frase, 1000, stdin);

    for(z=0; z<strlen(frase);z++)
        frase[z]=tolower(frase[z]);

    for(ascii=97; ascii<=122; ascii++)
    {
        i=0;
        s=0;

        while(s<=strlen(frase))
        {
            if(frase[s]==ascii)
                i++;
            s++;
        }

        if(i>0)
        {
            conta[a]=i;
            lettere[a]=ascii;
        }


        a++;

    }

   for(z=0; z<=strlen(frase); z++)
    {
        for(c=0; c<=25; c++)
        {
            int min=0;

            if(conta[c]>0 && conta[c]<conta[c+1])
                min=c;

            sposta(min, conta, frase, lettere);

        }
    }

    printf("________________\nFrase compressa: %s\n\n", frase);

7 Risposte

  • /
    Anonimizzato16009
    Utente anonimizzato
    Ogni volta che "frase" perde un carattere , es . frase = "qwerty" , quindi se perde "y" lo memorizzi su un altra variabile o vettore , frase2 = "quert"
    , ma mantieni la principale originale , frase = "querty" , alla fine diventerà frase = "quertyuiop" , e frase2 = " etuip" , poi confronti "frase" con "frase2" . Spero di non sbagliarmi .
  • /
    Anonimizzato16009
    Utente anonimizzato
    Ho modificato il tuo programma , ma lascia stare le prime due righe sono per il c++ " #include<iostream>
    using namespace std;", e anche i cin>> e cout<< ,ho messo le barrette , basta che fai copia e incolla per il linguaggio c, cmq provalo. 
    //#include<iostream>
//using namespace std;
#include<stdio.h>
#include<ctype.h>
#include<string.h>

void sposta(int min, int conta[], char frase[], int lettere[])
{

	int t = 0;
	//char frase[1000];

	int c = 0, i = 0, z, s = 0, a = 0;
	//int conta[26], lettere[26];
	char ascii;
	int ascii2 = 0;






	for (i = min; i < strlen(frase); i++)
	{

		cout << frase;
		//printf("________________\n%s", frase);
		frase[i] = frase[i + 1];

		//cin >> t;
		//t = getchar();

		if (i > 0)
		{
			conta[a] = i;
			lettere[a] = ascii;
			ascii2 = ascii;
			//cout << "  Quantita' = "<< conta[a]<<"  Lettera = "<<ascii<<"  Codice ascii = "<<ascii2<<"  \n";
			printf(" Quantita' = %i", conta[a]);
			printf("  Lettera  = %c ", ascii);
			printf("  Codice ascii = %i \n", ascii2);
		}

		a++;

		printf("________________\nFrase compressa:  %s \n\n DIGITARE FRASE COMPRESSA : \n", frase);
		//cout << "Frase compressa : " << frase;
		//t = getchar();
		//cin >> i;
		fgets(frase, 1000, stdin);
		for (z = 0; z < strlen(frase); z++)
			frase[z] = tolower(frase[z]);

		for (ascii = 97; ascii <= 122; ascii++)
		{
			i = 0;
			s = 0;

			while (s <= strlen(frase))
			{
				if (frase[s] == ascii)

					i++;
				s++;
				ascii2 = ascii;
			}

			if (i > 0)
			{
				conta[a] = i;
				lettere[a] = ascii;
				ascii2 = ascii;
				//cout << "  Quantita' = "<< conta[a]<<"  Lettera = "<<ascii<<"  Codice ascii = "<<ascii2<<"  \n";
				printf(" Quantita' = %i", conta[a]);
				printf("  Lettera  = %c ", ascii);
				printf("  Codice ascii = %i \n", ascii2);
			}

			a++;


		}

	}

}

int main()
{
	int t = 0;
	char frase[1000];
	
	int c, i = 0, z, s = 0, a = 0;
	int conta[26], lettere[26];
	char ascii;
	int ascii2 = 0;
	printf("Frase: "); fgets(frase, 1000, stdin);
	
	for (z = 0; z < strlen(frase); z++)
		frase[z] = tolower(frase[z]);

	for (ascii = 97; ascii <= 122; ascii++)
	{
		i = 0;
		s = 0;

		while (s <= strlen(frase))
		{
			if (frase[s] == ascii )
			
				i++;
			s++;
			ascii2 = ascii;
		}

		if (i > 0)
		{
			conta[a] = i;
			lettere[a] = ascii ;
			ascii2 = ascii;
			//cout << "  Quantita' = "<< conta[a]<<"  Lettera = "<<ascii<<"  Codice ascii = "<<ascii2<<"  \n";
			printf(" Quantita' = %i",conta[a] );
			printf("  Lettera  = %c ", ascii);
			printf("  Codice ascii = %i \n", ascii2);
		}

		a++;

		
	}


	for (z = 0; z <= strlen(frase); z++)
	{
		
		for (c = 0; c <= 25; c++)
		{

			int min = 0;

			if (conta[c] > 0 && conta[c] < conta[c + 1])
				min = c;

			sposta(min, conta, frase, lettere);


		
	

			
			t = getchar();
			//cin >> t;
		}
		//printf("________________\nFrase compressa: %s\n\n", frase);
	}
	t = getchar();

	
	//cin >>t;
}
  • /
    Anonimizzato19239
    Utente anonimizzato
    Ciao, grazie! Comunque il programma che hai scritto funge male e non fa ciò che dovrebbe: la frase compressa stampata stampa spesso caratteri a caso e non comprime come dovrebbe. E poi non capisco perché dopo aver chiesto la frase da comprimere, fai inserire la "frase compressa" all'utente :\
  • /
    Anonimizzato16009
    Utente anonimizzato
    Si , forse devo aver capito male , comunque ti conta la Quantità delle lettere che compaiono su una frase di mille caratteri o meglio , di ogni singola lettera, e quindi sai perfettamente quelle che compaiono di meno e di più e successivamente crei la tua frase "compressa" , basta metterle in ordine numerico , se non sbaglio ??
  • /
    Anonimizzato19239
    Utente anonimizzato
    Ma non dev'essere l'utente a dover creare la propria frase "compressa". È l'elaboratore che lo deve fare data una frase
  • /
    Anonimizzato16009
    Utente anonimizzato
    Si ho capito , ma adesso hai la quantità di ogni singola lettera . Quindi io proverei almeno a scrivere il resto del codice…..prima di farmelo fare da qualcuno , non è semplicissimo ma neanche difficilissimo.
  • /
    Anonimizzato19239
    Utente anonimizzato
    La avevo già prima la quantità di ogni lettera! Il vettore "conta" serve proprio a quello
    Inoltre non sto chiedendo di scrivermi il codice, sto semplicemente chiedendo come evitare che vengano cancellate tutte le lettere, correggendomi negli errori che ho fatto nel mio codice. E non capisco a cosa ti riferisci con "scrivere il resto del codice" dato che bisogna modificare, non aggiungere
Devi accedere o registrarti per scrivere nel forum
7 risposte