Dicas de programação

1. Não escreva linhas com mais de 80 caracteres.
Esse padrão é adotado para ser possível visualizar o código sem precisar rolar a tela horizontalmente.


2. Caso seu programa esteja dando falha de segmentação, nem sempre adianta tentar depurá-lo espalhando "printf" no código porque às vezes o programa pára sem ter impresso tudo o que deveria, então você fica achando que a execução parou numa certa linha mas na verdade parou bem depois. Isso porque a mensagem do printf vai para um buffer e só sai de lá (só vai pra tela) quando ele fica cheio. Então a falha de segmentação pode acontecer antes desse buffer encher e as mensagens dos printf pelos quais ele já passou não serão exibidas na tela. Pra resolver esse problema, use a função fflush, que esvazia na hora os buffers. Exemplo:

while(umaCondição)
{
printf("Entrei no laço com i valendo %d", i);
fflush(NULL);
...
}

Assim, os "printf" de depuração ficam mais confiáveis.


3. Escrever um programa que a máquina entenda é fácil. Difícil é escrever um código que uma pessoa entenda.
(comente seu código, escolha nomes significativos pras variáveis, etc)


4. Quer aprender direito ponteiros, structs, lista ligada e etc em C?
www.ime.usp.br/~pf/algoritmos

Imprime árvore

Para ajudar a depurar os programas, fiz este código que imprime uma árvore (que não seja muito grande). Realmente ajuda bastante.
Existe uma solução para grafos que se chama Graphviz.

/*#include "imprimeArvore.h"*/
#include 
#include 

#define OK 0
#define OVERFLOW 1
#define UNDERFLOW -1

typedef struct cel
{
 char info;
 struct cel * filhoEsq;
 struct cel * filhoDir;
} noh;

/* Esta é a estrutura de um elemento da fila */
typedef struct elementoDaFila
{
 char info;
 noh *filhoEsq;
 noh *filhoDir;

 struct elementoDaFila *prox;
} enfileirado;

/* Funções de manipulação da fila */

void copiaCampos(noh origem, enfileirado* destino)
{
 if(destino == NULL)
   fprintf(stderr, "\n\nErro: o destino da cópia é null\n\n");
 else
 {
   destino->info = origem.info;
   destino->filhoEsq = origem.filhoEsq;
   destino->filhoDir = origem.filhoDir;
 }
}

void copiaCampos2(enfileirado origem, noh* destino)
{
 if(destino == NULL)
   fprintf(stderr, "\n\nErro: o destino da cópia é null\n\n");
 else
 {
   destino->info = origem.info;
   destino->filhoEsq = origem.filhoEsq;
   destino->filhoDir = origem.filhoDir;
 }
}

void enfileira(noh novoNo, enfileirado** primeiro, enfileirado** ultimo)
{
 enfileirado* novo = malloc(sizeof(enfileirado));
 copiaCampos(novoNo, novo);
 if(filaVazia(*primeiro, *ultimo))
 {
   *primeiro = novo;
   *ultimo = novo;
 }
 else
 {
   (*ultimo)->prox = novo;
   *ultimo = novo;
 }
}

int proximo(noh* devolvido, enfileirado** primeiro, enfileirado** ultimo)
{
 if(!filaVazia(*primeiro, *ultimo))
 {
   copiaCampos2(**primeiro, devolvido);
   if((*primeiro)->prox == NULL)
     *ultimo = NULL;
   *primeiro = (*primeiro)->prox;
   return OK;
 }
 else
 {
   devolvido = NULL;
   return UNDERFLOW;
 }
}

int filaVazia(enfileirado* primeiro, enfileirado* ultimo)
{
 return primeiro == NULL;
}


/* funções auxiliares */
void imprimeVarios(char c, int quantidade)
{
 while(quantidade > 0)
 {
   printf("%c", c);
   quantidade--;
 }
}

int maximo(int um, int outro)
{
 if(um > outro)
   return um;
 return outro;
}


int achaAltura(noh raiz)
{
 int alturaDir;
 int alturaEsq;

 alturaDir = 0;
 alturaEsq = 0;

 if(raiz.filhoEsq != NULL)
   alturaEsq = achaAltura(*(raiz.filhoEsq));
 if(raiz.filhoDir != NULL)
   alturaDir = achaAltura(*(raiz.filhoDir));

 return maximo(alturaEsq, alturaDir) + 1;
}

/* só serve pra expoente não-negativo */
int potencia(int base, int expoente)
{
 if(expoente == 0) /* supondo que zero elevado a zero é 1 */
   return 1;
 if(base == 0)
   return 0;
 return base*potencia(base, expoente-1);
}

/* Função para a impressão de uma árvore binária */
void imprimeArvoreBinaria(noh raiz)
{
 int i;
 int nivel; /* nível atual */
 int altura;
 int numFolhas; /* número de folhas que teria
  a árvore se ela fosse cheia */
 int d; /* esta variável guarda o número de folhas
  que teria uma árvore cheia com altura igual
  a altura da árvore - nível atual.*/

 /* variáveis da fila */
 enfileirado *primeiro;
 enfileirado *ultimo;

 noh *temp;
 noh *espaco; /* usado para "preencher" buracos na árvore, pois ela pode
  não ser cheia, mas devemos ter um nó fictício no lugar*/

 espaco = malloc(sizeof(noh));
 espaco->info = ' ';
 espaco->filhoEsq = NULL;
 espaco->filhoDir = NULL;

 temp = malloc(sizeof(noh));

 primeiro = NULL;
 ultimo = NULL;

 altura = achaAltura(raiz);
 numFolhas = potencia(2, altura-1);

 d = numFolhas;

 nivel = 1;
 enfileira(raiz, &primeiro, &ultimo);

 while(nivel <= altura)
 {
   /* gambiarra's.. */
   if(d == 1)
     d = 0;
  
   /* imprimindo a linha com as infos */
   for(i = 0; i < potencia(2,nivel-1); i++)
   {
     if(proximo(temp, &primeiro, &ultimo) == UNDERFLOW)
       fprintf(stderr, "poatz... underflow mano...");
    
     imprimeVarios(' ', d);
     if(temp->info == ' ')
       imprimeVarios(' ', d-2);
     else
       imprimeVarios('_', d-2);
     if(temp == NULL || temp->info == '\0')
       printf(" ");
     else
       printf("%c", temp->info);
     if(temp->info == ' ')
       imprimeVarios(' ', d-2);
     else
       imprimeVarios('_', d-2);
    
     /* se for a última iteração... */
     if(i == potencia(2,nivel-1)-1)
       printf("\n");
     else
       imprimeVarios(' ', d+3);
    
     /* enfileirando os filhos */  
     if(temp->filhoEsq == NULL)
       enfileira(*espaco, &primeiro, &ultimo);
     else
       enfileira(*(temp->filhoEsq), &primeiro,&ultimo);
     if(temp->filhoDir == NULL)
       enfileira(*espaco, &primeiro, &ultimo);
     else
       enfileira(*(temp->filhoDir), &primeiro,&ultimo);
   }
  
   /* imprimindo a linha com os "galhos" da árvores */
   if(d != 0) /* gambiarra's */
   {
     for(i = 0; i < potencia(2,nivel-1); i++)
     {
       imprimeVarios(' ', d-1);
       printf("/");
       imprimeVarios(' ', 2*d-3);
       printf("\\");
      
       /* se for a última iteração, pula linha */
       if(i == potencia(2,nivel-1)-1)
         printf("\n");
       else
         imprimeVarios(' ', d+2);
     }
   }
   nivel++;
   d = d/2;
 }
}


int main()
{
 noh* varre;
 noh* raiz = malloc(sizeof(noh));

 raiz->info = 'A';
 raiz->filhoEsq = malloc(sizeof(noh));
 raiz->filhoDir = malloc(sizeof(noh));

 varre = raiz->filhoEsq;
 varre->info = 'B';
 varre->filhoEsq = malloc(sizeof(noh));
 varre->filhoDir = malloc(sizeof(noh));

 varre = raiz->filhoDir;
 varre->info = 'C';
 varre->filhoEsq = malloc(sizeof(noh));
 varre->filhoDir = malloc(sizeof(noh));

 varre = (raiz->filhoEsq)->filhoEsq;
 varre->info = 'D';
 varre->filhoEsq = NULL;
 varre->filhoDir = NULL;

 varre = (raiz->filhoEsq)->filhoDir;
 varre->info = 'E';
 varre->filhoEsq = NULL;
 varre->filhoDir = NULL;

 varre = (raiz->filhoDir)->filhoEsq;
 varre->info = 'F';
 varre->filhoEsq = NULL;
 varre->filhoDir = NULL;

 varre = (raiz->filhoDir)->filhoDir;
 varre->info = 'G';
 varre->filhoEsq = NULL;
 varre->filhoDir = NULL;
 imprimeArvoreBinaria(*raiz);
 return 0;
}

Tabela de hashing

Nesta aula, vimos a estrutura tabela de hashing (ou de espalhamento). A aplicação para esta estrutura foi buscar a palavra mais freqüente em um texto. Em particular, pegamos o texto da bíblia sagrada em inglês e descobrimos que a palavra mais freqüente é "the".

/**
* MAC 2301 - Laboratório de Programação
*
* Exercício da aula 11
*
* Assunto: Lista de espalhamento (hashing table)
* Aplicação: descobrir a palavra mais freqüente num texto longo
*
**/

#include 
#include 
#include 

#define MAX_PALAVRA 80
#define MAX 167 /* tamanho da tabela de hashing -> melhor se for um primo */

typedef struct node
{
 char palavra[MAX_PALAVRA];
 int freq;
 struct node* prox;
} noh;

/**
* Função de "espalhamento". Pode ser qualquer função que
* leve um dado de um nó num número entre 0 e MAX
* O ideal é que ela distribua uniformemente entre os
* possíveis resultados para diminuir o número de colisões.
**/
int funcaoDeHashing(char palavra[MAX_PALAVRA])
{
 int resultado = (int) palavra[0] % MAX;

 /* correção de um bug: caracteres acentuados viravam valores negativos */
 if(resultado < 0)
   resultado = -resultado;
 return resultado;
}

void insereNaLista(char novaEntrada[MAX_PALAVRA], noh** lista) /* sem cabeça */
{
 int encontrou;
 noh *novo, *varre;
 varre = *lista;
 while(varre != NULL)
 {
   /* se encontrou novaEntrada na lista, apenas
    * incrementa o contador da freqüência e sai da função */
   if(strcmp(varre->palavra, novaEntrada) == 0)
   {
     (varre->freq)++;
     return;
   }
   varre = varre->prox;
 }
 /* se chegar nesse ponto, não há a novaEntrada na lista, então inserimos */
 novo = malloc(sizeof(noh));
 strcpy(novo->palavra, novaEntrada);
 novo->freq = 1;
 if(*lista != NULL)
   novo->prox = *lista;
 else
   novo->prox = NULL;
 *lista = novo;
}

/* Função de inserção na tabela de hashing */
void insereNaTabela(char novaEntrada[MAX_PALAVRA], noh* tabela[MAX])
{
 insereNaLista(novaEntrada, &(tabela[funcaoDeHashing(novaEntrada)]));
}


/**
* Procedimento usado apenas para depurar.
**/
void imprimeLista(noh *lista)
{
 noh *varre = lista;
 printf("\n\n  -----\n |\n | Conteúdo da lista: \n |\n"); fflush(NULL);
 while(varre != NULL)
 {
   printf(" |  %s \n", varre->palavra);
   varre = varre->prox;
 }
 printf(" |\n  -----\n\n"); fflush(NULL);
}

/**
* Procedimento usado apenas para depurar.
**/
void imprimeTudo(noh* tabela[MAX])
{
 int i;
 noh* varre;

 varre = malloc(sizeof(noh));

 printf("\nEstado atual: \n");

 for(i = 0; i < MAX; i++)
 {
   varre = tabela[i];
   while(varre != NULL)
   {
     printf(" [%d] -> %s apareceu %d vezes\n", i,
            varre->palavra, varre->freq);
     varre = varre->prox;
   }
 }
 printf("----\n\n");
 fflush(NULL);
}

void removeLista(noh* lista) /* sem cabeça */
{
 noh* varre;
 if(lista != NULL)
 {
   if(lista->prox != NULL)
   {
     varre = lista->prox;
     while(varre != NULL)
     {
       lista->prox = varre->prox;
       free(varre);
       varre = lista->prox;
     }
   }
   free(lista);
 }
}

void imprimeResultado(noh* tabela[MAX])
{
 int i, freqMax;
 noh* varre;
 noh* maisFrequentes; /* lista com as palavras com a frqüência máxima */

 maisFrequentes = NULL;
 freqMax = 0;
 varre = malloc(sizeof(noh));
 for(i = 0; i < MAX; i++)
 {
   varre = tabela[i];
   while(varre != NULL)
   {
     if(varre->freq == freqMax)
     {
       insereNaLista(varre->palavra, &maisFrequentes);
     }
     else if (varre->freq > freqMax)
     {
       freqMax = varre->freq;
       removeLista(maisFrequentes);
       maisFrequentes = NULL;
       insereNaLista(varre->palavra, &maisFrequentes);
     }
     varre = varre->prox;
   }
 }
 printf("\n\n   Palavra(s) mais freqüênte(s) no texto (%dx):\n\n", freqMax);
 varre = maisFrequentes;
 while (varre != NULL)
 {
   printf("      \"%s\"\n", varre->palavra);
   varre = varre->prox;
 }
 printf("\n\n   ");
}


int main()
{
 noh* tabela[MAX];
 noh* umNoh;
 char umaPalavra[MAX_PALAVRA];
 int final, i;

 umNoh = NULL;

 /* inicializando a tabela inteira de hashing com null */
 for(i = 0; i < MAX; i++)
   tabela[i] = NULL;

 /* Pega a primeira palavra da entrada padrão */
 final = scanf("%s", &umaPalavra);

 /* Laço que pega cada palavra da entrada padrão
  * e insere na tabela de hashing */
 while(final != EOF)
 {
   insereNaTabela(umaPalavra, tabela);
   final = scanf("%s", &umaPalavra);
 }

 imprimeResultado(tabela);

 system("pause");

 printf("\n");

 return 0;
}