Este script serve para calcular a compactacao dos metodos MNP5 usando 2 à 10 caracteres repetidos e ha possivel compactação gerada pela tecnica de "Meio Byte". Pretendo atualizar o programa futuramente para botar outros calculos de compactação, a maioria dos detalhes pode ser vista comentada no fonte. Alem disso, ele serve de um bom estudo pra pronteiros e lista encadeada...

Duvidas? Email-me.

• Download listar.c
• Enviar nova versão

Esconder código-fonte

/* Feito por Ricardo Rodrigues Lucca
 *    em Primeiro de Abril de 2004
 *
 * Conceitos: Lista, Ponteiros, contador, retorno de funcoes
 *
 * Duvidas? Email : jllucca@cpovo.net
 *
**/

#include <stdio.h>

FILE *arq;
struct data {
   int r;
   struct data *prox;
} *l, *cl;

int monta(long int *tab)
{
   int ci=0, cp=0;
   int ch; /* Guarda caracter atual */
   int pch; /* Guarda caracter anterior */
   int r=0; /* repeticoes do caracter */
   int cr=0; /* repeticoes do caracter */
   void *iniciol; /* guarda o inicio da lista */
   void *iniciocl; /* guarda o inicio da lista */
   /* 
   sera usado para guardar a lista de ocorrencias repetidas 
   l para caracter iguais
   cl para caracteres com os 4bits mais significativos iguais
   elas estao definidas globalmente junto com o FILE.
   */

   /* aloca espaco para l */
   l = (struct data *) malloc(sizeof(struct data));
   if (l == NULL) return -1;
   l->r = 0;
   l->prox = NULL;
   
   /* aloca espaco para cl */
   cl = (struct data *) malloc(sizeof(struct data));
   if (cl == NULL) return -1;
   cl->r = 0;
   cl->prox = NULL;
   
   iniciol = l; /* atribui o primeiro elemento de l a iniciol */
   iniciocl = cl;

   cr = r = 0;   /* ZERA contadores */
   
   ch = fgetc(arq);
   while (!feof(arq)) {
      pch = ch;
      ch = fgetc(arq);

      if ( (pch & 240)==(ch & 240) ) {
         cr++;
         if (pch == ch) r++;
         tab[pch] = tab[pch]+1; /* escreve caracter na tabela */
         /******************************************************
          * Vou considerar que cr e r nunca vai ser tao        *
          * grande quanto um valor int. Claro que num caso,    *
          * muito dificil eh capaz de ocorrer. Mas, nao          *
          * vamos considerar hehehe :p               *
          ******************************************************/
      }
      else {
         /*
         r eh verdadeiro quando houverem caracteres
         repetidos exatamente iguais.
         */
         if (r) {
           l->r = r; 
           /* aloca memoria para o proximo */
           l->prox = (struct data *) malloc(sizeof(struct data));
           /* se falhar */
           if ((l->prox)==NULL) 
           {
              printf("I Armazenados %d\n", ci);
              return -2;
           }
           else {
             /* avanca e prepara o proximo */
               l = l->prox;
             l->r= 0;
             l->prox=NULL;
             ci++;
           }
           r = 0; /* zera contador */
         }
         /*
         cr eh verdadeiro quando os 4bits mais
         significativos sao iguais.
         */
         if (cr) {
           cl->r = cr; 
           /* prepara o proximo */
           cl->prox =(struct data *) malloc(sizeof(struct data));
           if ((cl->prox)==NULL) 
           {
              printf("P Armazenados %d\n", cp);
              return -2;
           }
           else {
             cl = cl->prox;
              cl->r=0;
             cl->prox=NULL;
             cp++;
           }
           cr = 0; /* zera contador */
         }
         /* escreve caracter na tabela */
         tab[pch] = tab[pch] + 1;
      }
   }

     l = iniciol; /* l recebe inicio da lista de chars iguais */
    cl = iniciocl; /* cl recebe inicio da lista de chars parecidos, o char eh parecido quando os 4bits de maior importancia sao iguais */
    
   return 0;
}

int analisa(void)
{
   long int ascii[256];
   /*
   total guardara o total de caracteres (Somatorio de ascii)
   elim guardara os caracteres eliminados - isto eh - compactados
   i sera um contador simples
   */
   long int elim, total;
   int i;
   void *inicio;

   for (i=0; i < 256; i++) ascii[i]=0; /* Zera tabela ascii */
   i = monta(ascii);
   if (i == -1) return -1;
   else if (i== -2) return -2;

   /* PREPARA TABELA */
   printf("Codificacao\t\tChars Elim.\t\tPorcentagem C.\n");

   /************************************************
   *      Calculo para total          *
   *         Equivale a pegar o tamanho do arquivo   *
   *************************************************/
   for (i=0, total=0; i < 256; i++)   total+=ascii[i];

   /*****************************************************************
   * Calculo para MNP5 - repetidos de 2 ate 10 chars       *
   * NOTA: MNP5v? eh como chamei a variacao pro calculo.       *
   *      A MNP5 original diz que devemos repetir 3 simbolos que o    *
   *      proximo eh quantos faltam.             *
   *****************************************************************/
   inicio=l; /* guarda o primeiro elemento de l */
   for (i=2; i<11; i++)
   {
      float pc=0;
      l = inicio;
      elim = 0; /* eliminados recebe zero */
      while (l->prox != NULL) {
         if (l->r >= i-1) 
            elim += (l->r) - i;
      
         l = l->prox;
      }
      
      printf("MNP5v%1d\t\t\t%11ld\t\t",i, elim);

      pc=(elim*100.0)/total;
      printf("%9.3f\n", pc);
   }
   l=inicio; /* volta pro primeiro elemento */

   /*******************************************************************
   *   Calculo para Compactacao de Meio Byte            *
   *      - Preenchendo "lacunas"               *
   *   Quando nao se preenche podemos ganhar mais compactacao      *
   *   ja que meio byte ganho aqui, meio ali...         *
   *                           *
   *   PS: nao tenho certeza desse calculo            *
   ********************************************************************/
   inicio=cl; /* colocar o primeiro em inicio */
   /* 
      elim recebe 0, executa o for ate que for encontrado NULL e
      a cada interacao vai "subindo" na lista.
   */
   for (elim=0; cl->prox != NULL; cl=cl->prox)
   {
      elim += (cl->r)+1;
   }
   elim = (total - elim) * -2; /* Calcula os elementos solitarios */
   cl=inicio; /* volta pro primeiro */
   i=0;
   while (cl->prox != NULL) /* calcula os elementos agrupados */
   {
      /*
        se um agrupamento for maior que 15,
        isto eh, maior que meio byte "inferiores"
        ou ainda, a metade direita hehehe.
      */
      if ((cl->r)>=15) {
         if ( i == 0 ) printf("*");
         i = 1;
         if (cl->prox == NULL) break; /* sai fora */
         else cl = cl -> prox;
         continue; /* forca proxima interacao */
      }
      elim += ((cl->r)+1)/2+2;
      cl = cl -> prox;
   }
   printf("HalfByte\t\t%11ld\t\t", elim);
   printf("%9.3f\n",(elim*100.0)/total); /*calculo da percentagem */
   cl=inicio; /* volta pro primeiro */
   
   return 0;
}

int main(void) {
   char nome[256]; /* pode dar overflow */
   
   printf("Arquivo: ");
   scanf(" %s", nome);

   arq = fopen(nome,"r");
   
   if (arq==NULL)
      printf("Arquivo nao existe!\n");
   else {
      int cod;
      cod = analisa();

      if (cod==-1) printf("Memoria Insuficiente para iniciar");
      if (cod==-2) printf("Memoria Insuficiente");
      
      fclose(arq);
   }
   
   return 0;
}

Ponteiros para funções

Jogo da Forca

Regra de Horner para cálculo do polinômio

Divisores de um inteiro positivo em C++

Fazendo o somatório de 1 até N