MAC122 - Princípios de Desenvolvimento de Algoritmos

Introdução

Slides

Revisão sobre linguagem C

Slides

Exercícios resolvidos sobre Strings:

Problema 1:

Faça um programa que lê uma linha de texto em uma string (sequência de caracteres terminada por '\0') e que conta o número de ocorrências de cada letra do alfabeto.

Solução: 

#include <stdio.h>
#define LIM 500
#define NLETRAS ('z'-'a'+1)

int main(){
  char texto[LIM];
  int freq[NLETRAS];
  int i;
  char c;

  /* Lê uma linha de texto */
  scanf("%[^\n]", texto);

  /* Inicializa com 0 o vetor de contadores */
  for(i = 0; i < NLETRAS; i++)
    freq[i] = 0;

  /* Percorre a string, contando a frequência das letras */
  i = 0;
  while(texto[i] != '\0'){
    c = texto[i];
    /* Identifica letras minúsculas */
    if(c >= 'a' && c <= 'z')
      freq[c - 'a']++;
    /* Identifica letras maiúsculas */
    else if(c >= 'A' && c <= 'Z')
      freq[c - 'A']++;
    i++;
  }

  /* Imprime a frequência das letras com contagem não nula */
  for(i = 0; i < NLETRAS; i++){
    if(freq[i] > 0)
      printf("letra: %c, freq: %d\n", 'a'+i, freq[i]);
  }
  
  return 0;
}

Problema 2:

Cebolinha é um personagem de história em quadrinhos que quando falava, trocava o "r" pelo "l" (problema conhecido como dislalia). Faça um programa que gera uma versão de um texto fornecido com todos "r" e "rr" trocados por "l", exceto no caso em que o "r" ocorre no final de uma palavra.

cebola_fig1

Solução: 

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

int main(){
  char str[] = "e chega de disputar essa rua com a monica, eu poderei comprar ruas, bairros inteiros";
  char dest[500];
  int i, j, n;
  char c;
  
  j = 0;
  n = strlen(str);
  for(i = 0; i < n; i++){
    if(str[i] == 'r' && str[i+1] >= 'a' && str[i+1] <= 'z'){
      c = 'l';
      if(str[i+1] == 'r')
        i++;
    }
    else
      c = str[i];

    dest[j] = c;
    j++;
  }
  dest[j] = '\0';

  printf("%s\n", dest);
  
  return 0;
}

Exercícios resolvidos sobre Funções & Strings:

Implemente as funções especificadas abaixo, usando apenas funções auxiliares que tiver implementado (sem utilizar as funções do <string.h>). Por questões de simplicidade, assuma o padrão ASCII.

1) void InverteString(char str[]);

Altera a própria string str de modo que ela fica invertida.
Exemplo: Se inicialmente temos:
    str="PAMELA SILVA", no final teremos:
    "AVLIS ALEMAP" em str. 
/* função auxiliar */
int TamanhoString(char str[]){
  int i = 0;
  while(str[i] != '\0'){
    i++;
  }
  return i;
}

void InverteString(char str[]) {
  int i,j;
  char tmp;
  
  j = TamanhoString(str) - 1;
  i = 0;

  while (i < j) {
    tmp = str[i];
    str[i] = str[j];
    str[j] = tmp;
    i++;
    j--;
  }
}

2) void InvertePalavras(char str[]);

Altera a própria string str de modo que todas as suas palavras individualmente ficam invertidas.
Exemplo: Se inicialmente temos:
    str="PAMELA SILVA", no final teremos:
    "ALEMAP AVLIS" em str. 
/* função auxiliar */
void InverteSubString(char str[], int i, int j){
  char tmp;
  
  while (i < j) {
    tmp = str[i];
    str[i] = str[j];
    str[j] = tmp;
    i++;
    j--;
  }
}

void InvertePalavras(char str[]){
  int i, j;
  i = 0;
  do {
    while(str[i] == ' ') i++;
    j = i;

    while(str[j] != '\0' && str[j] != ' ') j++;

    j = j - 1;
    if(i < j) InverteSubString(str, i, j);

    i = j + 1;
  } while (str[i] != '\0');
}

3) void ReduzEspacos(char dest[], char orig[]);

Gera em dest uma cópia de orig porém eliminando o excesso de espaços em branco, de modo que todas as sequências de espaços em branco consecutivos são convertidas em um único caracter de espaço. Assuma que o vetor dest é grande o suficiente para conter o resultado.
Exemplo: Se inicialmente temos:
    orig = "     Problema       de     Strings  ", no final teremos:
    dest = " Problema de Strings ". 
void ReduzEspacos(char dest[], char orig[]){
  int i, j;
  char t;
  i = 0;
  j = 0;
  while(orig[i] != '\0'){
    if(orig[i] != ' '){
      t = orig[i];
      i++;
    }
    else {
      t = orig[i];
      while(orig[i] == ' ') i++;
    }
    dest[j] = t;
    j++;
  }
  dest[j] = '\0';
}

4) void ProcuraEmail(char dest[], char orig[]);

Busca em orig por possíveis candidatos a endereços de e-mail. Copia em dest a primeira sequência de caracteres não brancos encontrada que contenha o caractere '@', ou uma string vazia caso contrário. Assuma que o vetor dest é grande o suficiente para conter a palavra encontrada.
Exemplo:
Para orig="Enviar mensagem para lucas@ig.com.br ou para outro moderador"
temos "lucas@ig.com.br" que ficará em dest. 
/* função auxiliar */
void CopiaSubString(char dest[], char orig[],
                    int inic, int fim){
  int i,j;
  j = 0;
  for(i = inic; i <= fim; i++){
    dest[j] = orig[i];
    j++;
  }
  dest[j] = '\0';
}

void BuscaEmail(char dest[], char orig[]){
  int i,inic,fim;
  /* Procura índice do caractere '@'*/
  i = 0;
  while(orig[i] != '\0'){
    if(orig[i] == '@')
      break;
    i++;
  }
  /* Nenhum email encontrado */
  if(orig[i] == '\0'){
    dest[0] = '\0';
    return;
  }
  inic = fim = i;
  while(inic > 0){
    if(orig[inic-1] == ' ') break;
    inic--;
  }

  while(orig[fim+1] != ' ' && orig[fim+1] != '\0')
    fim++;
  CopiaSubString(dest, orig, inic, fim);
}

Exemplo de função principal main:

#include <stdio.h>

/* Inserir nesse ponto o código das funções anteriores */


int main(){
  char str1[] = "PAMELA SILVA";
  char str2[] = "PAMELA SILVA";
  char str3[] = "Enviar mensagem para lucas@ig.com.br ou para outro moderador";
  char email[500];
  char B[500];

  InverteString(str1);
  printf("%s.\n", str1);

  InvertePalavras(str2);
  printf("%s.\n", str2);

  ReduzEspacos(B, "     Problema       de     Strings  ");
  printf("%s.\n", B);

  BuscaEmail(email, str3);
  printf("Email: %s.\n",email);
  
  return 0;
}

Ponteiros

Slides

Alocação dinâmica de memória

Slides

Exercícios resolvidos sobre Alocação Dinâmica de memória:

Escreva um programa que leia um número inteiro positivo n seguido de n números inteiros e imprima esses n números em ordem invertida. Por exemplo, ao receber 
5 22 33 44 55 88
o seu programa deve imprimir: 
88 55 44 33 22
O programa não deve impor limitações sobre o valor de n. 
  #include <stdio.h>
  #include <stdlib.h>

  int main() {
    int n, i, num;
    int *vet = NULL;
  
    /*Lê o tamanho do vetor.*/
    scanf("%d", &n);
  
    /*Aloca um vetor com n inteiros (n*4 bytes) na heap. 
      O endereço do vetor alocado fica armazenado
      no apontador "vet". */
    vet = (int *)malloc(n*sizeof(int));

    /*Lê "n" números da entrada padrão (teclado), 
      e preenche o vetor alocado. */
    for (i = 0; i < n; i++) {
      scanf("%d", &num);
      vet[i] = num;
    }

    /*Imprime o vetor em ordem invertida.*/
    for (i = n-1; i >= 0; i--)
      printf(" %d ",vet[i]);
    printf("\n");

    /*Libera a memória alocada do vetor.*/
    free(vet);

    return 0;
  }

Exercícios resolvidos sobre Alocação Dinâmica de Matrizes & Arquivos (modo texto):

Faça um programa em C que:
  1. Leia uma imagem em tons de cinza no formato PGM do arquivo lenna.pgm,
  2. Permute a metade superior da imagem com sua metade inferior, conforme no exemplo abaixo, e
  3. Salve a imagem resultante no disco no arquivo "saida.pgm".
entrada saida
(a) Exemplo de imagem de entrada,(b) imagem de saída resultante.

Uma explicação sobre o formato de imagem PGM pode ser encontrada aqui.

Solução: 

#include <stdio.h>
#include <stdlib.h>

int main(){
  char nome[120];
  char tipo[10];
  FILE *fp;
  int **M;
  int *tmp;
  int nlinhas, ncolunas, valmax, i, j;
  printf("Digite o nome do arquivo: ");
  scanf("%s", nome);

  /* Abrindo o arquivo em modo de leitura: */
  fp = fopen(nome, "r");
  if(fp == NULL){
    printf("Erro na leitura\n");
    return 0;
  }

  /* Leitura do cabeçalho do arquivo: */
  fscanf(fp, "%s", tipo);
  fscanf(fp, "%d %d", &ncolunas, &nlinhas);
  fscanf(fp, "%d", &valmax);

  /* Alocação de memória da matriz */
  M = (int **)malloc(sizeof(int *)*nlinhas);
  if(M == NULL){
    printf("Erro ao alocar a matriz\n");
    return 0;
  }

  for(i = 0; i < nlinhas; i++)
    M[i] = (int *)malloc(sizeof(int)*ncolunas);

  /* Preenchendo a matriz com os dados da imagem: */
  for(i = 0; i < nlinhas; i++)
    for(j = 0; j < ncolunas; j++)
      fscanf(fp, "%d", &M[i][j]);

  fclose(fp);

  /* Processamento da imagem: */
  for(i = 0; i < nlinhas/2; i++){
    tmp = M[i];
    M[i] = M[i+nlinhas/2];
    M[i+nlinhas/2] = tmp;
  }
 
  /* Gravação da imagem resultante: */
  fp = fopen("saida.pgm", "w");

  fprintf(fp, "P2\n");
  fprintf(fp, "%d %d\n", ncolunas, nlinhas);
  fprintf(fp, "%d\n", valmax);
  for(i = 0; i < nlinhas; i++){
    for(j = 0; j < ncolunas; j++)
      fprintf(fp, "%d ", M[i][j]);
    fprintf(fp, "\n");
  }
  fclose(fp);

  /* Liberar memória: */
  for(i = 0; i < nlinhas; i++)
    free(M[i]);
  free(M);
  
  return 0;
}

Exercícios resolvidos sobre Alocação Dinâmica & Strings:

Para uma dada string, contendo uma linha de texto, faça uma função em C que separa cada palavra do texto:
A função deve devolver o endereço de um vetor de apontadores criado dinamicamente com tamanho igual ao número de palavras do texto. Os apontadores desse vetor devem apontar para cópias das palavras do texto. Cada cópia deve ser amazenada em um vetor alocado dinamicamente, usando a menor quantidade de memória possível.

Use o protótipo abaixo:

char **VetorDePalavras(char texto[], int *npal);

tal que npal aponta para uma variável que irá guardar o número de palavras encontradas.

Exemplo:
Para o texto de entrada: "A primeira Guerra Mundial    completa 100 anos em 2014", no final teremos os seguintes vetores alocados:

#include <stdio.h>
#include <stdlib.h>


char **ListaPalavras(char texto[], int *npalavras){
  char **L = NULL;
  int i,j,tam,npal,inic;
  char *pal;

  /* Conta o número de palavras. */
  i = 0;
  npal = 0;
  while(texto[i] != '\0'){
    while(texto[i] == ' ')
      i++;
    if(texto[i] != '\0'){
      npal++;
      while(texto[i] != ' ' && texto[i] != '\0')
        i++;
    }
  }
  *npalavras = npal;

  /* Aloca o vetor de apontadores. */
  L = (char **)malloc(npal*sizeof(char *));
  if(L == NULL){
    printf("Memoria insuficiente.\n");
    exit(1);
  }

  i = 0;
  j = 0;
  while(texto[i] != '\0'){
    while(texto[i] == ' ')
      i++;
    inic = i;
    while(texto[i] != ' ' && texto[i] != '\0')
      i++;

    tam = i - inic;
    if(tam > 0){
      pal = (char *)malloc(sizeof(char)*(tam+1));
      if(pal == NULL){
        printf("Memoria insuficiente.\n");
        exit(1);
      }
      L[j] = pal;
      i = inic;
      while(texto[i] != ' ' && texto[i] != '\0'){
        pal[i-inic] = texto[i];
        i++;
      }
      pal[i-inic] = '\0';
      j++;
    }
  }
  return L;
}

int main(){
  char texto[] = "A  primeira Guerra Mundial    completa 100 anos    em 2014";
  char **L;
  int n,i;

  L = ListaPalavras(texto, &n);

  printf("Lista de palavras:\n");
  for(i = 0; i < n; i++){
    printf("%s.\n",L[i]);
  }

  /* Libera memória */
  for(i = 0; i < n; i++){ 
    free(L[i]);
  }
  free(L);

  return 0;
}

Estruturas/registros

Slides

Exercícios resolvidos sobre Estruturas & Arquivos (modo texto)

Problema 1a:

Um triângulo pode ser representado pelas coordenadas reais (float) dos seus três vértices (Xa, Ya), (Xb, Yb), e (Xc, Yc). Escreva uma possível definição em C para as estruturas de um vértice e de um triângulo, e implemente as seguintes funções em C:

float Distancia(struct Vertice A, struct Vertice B);

Calcula a distância euclidiana entre os vértices (pontos) A e B.
OBS: Use a função float sqrtf(float x); para calcular a raiz quadrada.

float Perimetro(struct Triangulo T);

Calcula o perímetro do triângulo T.

Solução: 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct Vertice{
  float x;
  float y;
};

struct Triangulo{
  struct Vertice A;
  struct Vertice B;
  struct Vertice C;
};

float Distancia(struct Vertice A, struct Vertice B){
  float dx, dy, d;
  dx = (B.x - A.x);
  dy = (B.y - A.y);
  d = sqrtf(dx*dx + dy*dy);
  return d;
}


float Perimetro(struct Triangulo T){
  float d = 0.0;
  d += Distancia(T.A, T.B);
  d += Distancia(T.A, T.C);
  d += Distancia(T.B, T.C);
  return d;
}

Problema 1b:

Dado um arquivo texto "entrada.txt" que possui em sua primeira linha um inteiro que indica a quantidade de triângulos e nas demais linhas os dados dos triângulos (um triângulo por linha segundo o formato: "Xa Ya Xb Yb Xc Yc"), conforme o exemplo:
5
0.0  0.0  0.0  1.0  1.0  0.0
0.0  0.0  0.0  0.1  0.1  0.0
2.0  2.0  3.0  2.0  2.5  3.0
2.0  2.0  2.1  2.0  2.05 2.1
8.0  1.0  7.0  3.0  2.0  1.0
Escreva um programa que: Exemplo do arquivo "saida.txt":
3
0.00 0.00 0.00 1.00 1.00 0.00
2.00 2.00 3.00 2.00 2.50 3.00
8.00 1.00 7.00 3.00 2.00 1.00

Solução: 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* Inserir nesse ponto o código das funções e as definições de estruturas do problema anterior */


int main(){
  FILE *fp = NULL;
  struct Triangulo *T = NULL;
  int n, nn = 0, i;

  fp = fopen("entrada.txt", "r");
  if(fp == NULL){
    printf("Erro na leitura do arquivo.\n");
    exit(1);
  }
  fscanf(fp, "%d", &n);
  T = (struct Triangulo *)malloc(n*sizeof(struct Triangulo));
  if(T == NULL){
    printf("Memoria insuficiente.\n");
    exit(1);
  }
  for(i = 0; i < n; i++){
    fscanf(fp, "%f %f", &(T[i].A.x), &(T[i].A.y));
    fscanf(fp, "%f %f", &(T[i].B.x), &(T[i].B.y));
    fscanf(fp, "%f %f", &(T[i].C.x), &(T[i].C.y));

    if( Perimetro(T[i]) > 0.5 ) nn++;
  }
  fclose(fp);

  fp = fopen("saida.txt", "w");
  fprintf(fp, "%d\n", nn);
  for(i = 0; i < n; i++){
    if( Perimetro(T[i]) > 0.5 ){
      fprintf(fp, "%.2f %.2f ",  T[i].A.x, T[i].A.y);
      fprintf(fp, "%.2f %.2f ",  T[i].B.x, T[i].B.y);
      fprintf(fp, "%.2f %.2f\n", T[i].C.x, T[i].C.y);
    }
  }
  fclose(fp);
  free(T);

  return 0;
}

Exercícios resolvidos sobre Estruturas & Arquivos (modo texto e binário)

Problema 1:

Faça um programa em C que leia uma planilha de alunos de um arquivo texto "alunos.txt", sendo que o número total de alunos está indicado na primeira linha do arquivo e nas demais linhas temos um registro de aluno por linha no formato CSV, no qual o caracter separador é a vírgula (,). Os dados devem ser lidos em um vetor de estruturas de alunos alocado dinamicamente. Os dados dos alunos devem então ser impressos e o vetor de estruturas deve ser gravado no disco em modo binário no arquivo "saida.bin". Cada registro de aluno deve conter seu nome (string), número usp (inteiro), coeficiente de rendimento (real) e sexo (caractere). Um exemplo de arquivo é indicado abaixo:

libreoffice_a

Solução: 

#include <stdio.h>
#include <stdlib.h>

struct Aluno{
  char nome[100];
  int n_usp;
  float cr;
  char sexo;
};

void ImprimeAluno(struct Aluno A){
  printf("Nome: %s, ", A.nome);
  printf("NUSP: %d, ", A.n_usp);
  printf("CR: %.2f, ", A.cr);
  printf("Sexo: %c\n", A.sexo);
}

int main(){
  char arquivo[100];
  FILE *fp;
  int nalunos, i;
  struct Aluno *V;
  printf("Digite o nome do arquivo: ");
  scanf("%s", arquivo);

  fp = fopen(arquivo, "r");
  fscanf(fp, "%d", &nalunos);

  V = (struct Aluno *)malloc(sizeof(struct Aluno)*nalunos);
  for(i = 0; i < nalunos; i++){
    fscanf(fp, " %[^,],", V[i].nome);
    fscanf(fp, "%d,", &V[i].n_usp);
    fscanf(fp, "%f,", &V[i].cr);
    fscanf(fp, " %c", &V[i].sexo);
  }
  fclose(fp);

  for(i = 0; i < nalunos; i++)
    ImprimeAluno(V[i]);

  fp = fopen("saida.bin", "wb");

  fwrite(V, sizeof(struct Aluno), nalunos, fp);

  fclose(fp);
  free(V);
  return 0;
}
Curiosidade: Arquivos no formato CSV são reconhecidos pelo OpenOffice/LibreOffice e programas similares. Abaixo mostramos o arquivo de entrada do exemplo sendo aberto no LibreOffice:
libreoffice_a libreoffice_b

Estruturas ligadas

Slides

1. Exemplo de código simples usando estruturas ligadas:

O seguinte programa ilustra a criação de uma lista de estruturas, ligadas através de um campo apontador presente nas estruturas. Cada estrutura armazena um número inteiro. No exemplo, os números de 0 a 3 são inseridos na lista. Como as inserções são sempre feitas no início da lista, os números ficam armazenados em ordem invertida. Em seguida, o programa imprime os números e depois libera a memória da lista. 
  #include <stdio.h>
  #include <stdlib.h>

  struct bloco{
    int num;
    struct bloco *prox;
  };

  void ImprimeLista(struct bloco *L){
    struct bloco *T = L;
    while(T != NULL){
      printf(" %d ",T->num);
      T = T->prox;
    }
    printf("\n");
  }

  void LiberaLista(struct bloco *L){
    struct bloco *T,*P;
    T = L;
    while(T != NULL){
      P = T->prox;
      free(T);
      T = P;
    }
  }

  int main(){
    struct bloco *L = NULL;
    struct bloco *N;
    int i;

    /* Aloca lista ligada */
    for(i = 0; i<= 3; i++){
      N = (struct bloco *)malloc(sizeof(struct bloco));
      N->num = i;
      N->prox = L;
      L = N;
    }

    /* Imprime elementos da lista */
    ImprimeLista(L);

    /* Libera a memória utilizada pela lista */
    LiberaLista(L);
    return 0;
  }

2. Exemplo de aplicação: Manipulação de polinômios

Exemplo de manipulação de polinômios de grau n≥0.

P(x) = an xn + an-1 xn-1 + ... + a1 x1 + a0 x0

A solução a seguir usa listas circulares com nó–cabeça, a fim de utilizar a técnica de sentinelas. Consideramos que:

  1. Cada nó representa um termo com coeficiente não nulo;
  2. Os termos estão em ordem decrescente dos expoentes;
  3. O nó–cabeça tem expoente –1 (conveniente para as operações).

Definição típica da estrutura utilizada:

struct Termo{
  float coef;
  int expo;
  struct Termo *prox;
};

typedef struct Termo* Polinomio;

Alocando memória:

A função abaixo aloca dinamicamente memória para um dos termos do polinômio. 
struct Termo *AlocaTermo(){
  struct Termo *p;
  p = (struct Termo*)malloc(sizeof(struct Termo));
  if(p == NULL)
    exit(1);
  return p;
}
Para criar um polinômio nulo, alocamos o nó–cabeça com expoente –1: 
Polinomio CriaPolinomioNulo(){
  Polinomio p;
  p = AlocaTermo();
  p->coef = 0.0;
  p->expo = -1;
  p->prox = p;
  return p;
}

Inserindo novo termo no polinômio:

Dado que os termos estão em ordem decrescente dos expoentes, precisamos buscar a posição correta para efetuar a inserção. 
void InsereTermo(Polinomio p, float coef, int expo){
  struct Termo *t, *at,*q;
  /* Aloca memória para o novo termo: */
  q = AlocaTermo();
  q->coef = coef;
  q->expo = expo;
  /* Busca a posição correta para inserir o novo termo,
     O novo termo será inserido entre os termos apontados 
     por at e t.
  */
  at = p;
  t = p->prox;
  while(expo < t->expo){
    at = t;
    t = t->prox;
  }
  q->prox = t;
  at->prox = q;
}

Imprimindo o polinômio:

Exemplo de função que imprime o polinômio. 
void ImprimePolinomio(Polinomio p){
  struct Termo *t;
  
  t = p->prox;
  while(t != p){
    printf("%.2f*x^%d",t->coef,t->expo);
    t = t->prox;
    if(t != p){
      if(t->coef >= 0.0)
        printf("+");
    }
  }
  printf("\n");
}

Criando um novo polinômio a partir de uma expressão (string):

A função abaixo lê expressões matemáticas em strings como "5.0*x^4 + 7.5*x^2 + 3.0*x^1", e gera a lista circular com nó–cabeça do polinômio correspondente.
Ao invés de ler a expressão caracter por caracter, no código abaixo usamos a função sscanf. A função sscanf é similar a função scanf, porém, ao invés de ler a entrada padrão (teclado), ela lê os dados diretamente de uma string (vetor), que é passada como o primeiro parâmetro do método. O "%n" é usado para monitorar a quantidade de caracteres lidos a cada execução do sscanf. A variável nn é usada como um contador (acumulador) do total de caracteres lidos. O valor de nn é utilizado como índice na expressão, permitindo avançar pela string a cada chamada do sscanf. Para isso, usamos a aritmética de ponteiros expr+nn. 
Polinomio CriaPolinomio(char expr[]){
  Polinomio p;
  int expo,r,n,nn;
  float coef,sinal = 1.0;
  char c;

  nn = 0;
  p = CriaPolinomioNulo();
  while(1){
    r = sscanf(expr+nn," %f * x ^ %d %n",&coef, &expo,&n);
    if(r == 0 || r == EOF) 
      break;
    nn += n;

    InsereTermo(p, sinal*coef, expo);
    
    r = sscanf(expr+nn,"%c %n",&c,&n);
    if(r == EOF || r == 0)
      break;
    nn += n;

    if(c == '-')
      sinal = -1.0;
    else
      sinal = 1.0;
  }
  return p;
}

Somando dois polinômios:

Exemplo de função que soma dois polinômios. Ela percorre simultaneamente as duas listas somando os termos com expoentes iguais e copiando de modo intercalado aqueles que não tem correspondente no outro. 
Polinomio SomaPolinomios(Polinomio p,
                         Polinomio q){
  Polinomio r;
  struct Termo *pp, *qq, *rr;
  float cf;

  r = CriaPolinomioNulo();
  rr = r;
  pp = p->prox;
  qq = q->prox;
  while(pp->expo > -1 || qq->expo > -1){
    if(pp->expo < qq->expo){
      InsereTermo(rr, qq->coef, qq->expo);
      rr = rr->prox;
      qq = qq->prox;
    }
    else if(qq->expo < pp->expo){
      InsereTermo(rr, pp->coef, pp->expo);
      rr = rr->prox;
      pp = pp->prox;
    }
    else{ /* pp->expo == qq->expo */
      cf = pp->coef + qq->coef;
      if(cf != 0.0){
        InsereTermo(rr, cf, pp->expo);
        rr = rr->prox;
      }
      pp = pp->prox;
      qq = qq->prox;
    }

  }
  return r;
}

Programa principal:

Exemplo de programa principal que chama as funções anteriores. 
int main(){
  Polinomio p,q,r;

  p = CriaPolinomio("5.0*x^3 -4.0*x^1 + 2.0*x^0");  
  ImprimePolinomio(p);

  q = CriaPolinomio("  8.0*x^4 + 2.0*x^3 + 4.0*x^1");
  ImprimePolinomio(q);

  r = SomaPolinomios(p, q);
  ImprimePolinomio(r);

  return 0;
}

Exercícios resolvidos sobre Estruturas Ligadas

Problema 1:

Faça uma função que inverte uma lista simples de estruturas ligadas, contendo um campo apontador e um campo que armazena um número inteiro, alterando somente os campos dos apontadores. A função deve devolver o novo início da lista.

Solução: 

struct Reg{
  int dado;
  struct Reg *prox;
};

struct Reg *InverteLista(struct Reg *L){
  struct Reg *T, *A;
  A = NULL;
  T = L;
  while(T != NULL){
    L = L->prox;
    T->prox = A;
    A = T;
    T = L;
  }
  return A;
}

Programa principal:

Exemplo de programa principal que chama a função anterior. 
int main(){
  struct Reg *L = NULL, *N;
  int i;

  /* Criando uma lista para teste: */
  for(i = 0; i < 4; i++){
    N = (struct Reg *)malloc(sizeof(struct Reg));
    N->dado = i;
    N->prox = L;
    L = N;
  }

  printf("Invertendo a lista: \n");
  L = InverteLista(L);

  return 0;
}

Vazamento de memória e depuradores de código

Slides

Matriz Esparsa

Slides

Pilhas e filas

Slides

Transformação da notação infixa para pós-fixa

A manipulação de expressões matemáticas é um exemplo de aplicação do uso de pilhas. Aqui vamos mostrar a transformação da notação infixa para pós-fixa.
Na notação tradicional (notação infixa) temos que o operador aparece entre os seus dois operandos. Já na notação pós-fixa, também conhecida como notação polonesa inversa, o operador é colocado após os seus dois operandos.

Exemplos:
infixapós-fixa
a-bab-
a-b*cabc*-
(a-b)*cab-c*
a+b*c^d-eabcd^*+e-
a*(b+c)*(d-g)*habc+*dg-*h*
a*b-c*d^e/f+g*hab*cde^*f/-gh*+

Na notação pós-fixa é importante observar que:

Nos exemplos acima, podemos observar também que:

Observe no exemplo "a+b*c^d-e" que os operadores +,*,^ aparecem na expressão pós-fixa "abcd^*+e-" em ordem inversa. Isso sugere o uso de uma pilha para armazenar os símbolos, visto que em uma pilha o último elemento a entrar é o primeiro a sair (política LIFO). Ou seja, elementos removidos de uma pilha aparecem em ordem invertida em relação a ordem de inserção.

Durante o processo de conversão, os caracteres da expressão infixa são processados da esquerda para a direita. Quando operadores com maior prioridade são vistos, esses são empilhados de modo a ocupar o topo da pilha. Eles devem permanecer na pilha até aparecer na entrada um operador de prioridade menor ou igual. Nesse caso, não há porque postergar a sua execução, e o operador deve ser impresso imediatamente na saída.

Problema:

Faça uma função que recebe uma string contendo uma expressão em notação infixa e que imprime a sua expressão correspondente em notação pós-fixa. Considere os seguintes operadores: '+', '-', '*', '/' e '^'. No caso de operadores de mesmo nível de prioridade, considere a associação à esquerda. A exceção é o operador '^' que deve ser associado a direita.

Resolução:

void In2Pos(char expr[]){
  Pilha p;
  int i = 0;
  char c,t;

  p = CriaPilha();
  Empilha(p, '(');

  do{
    c = expr[i];
    i++;
    if(c >= 'a' && c <= 'z'){
      printf("%c", c);
    }
    else if(c == '('){
      Empilha(p, '(');
    }
    else if(c == ')' || c == '\0'){
      do{
        t = Desempilha(p);
        if(t != '(')
          printf("%c", t);
      }while(t != '(');
    }
    else if(c == '+' || c == '-' || 
            c == '*' || c == '/' ||
            c == '^' ){
      while(1){
        t = Desempilha(p);
        if(Prioridade(c,t)){
          Empilha(p, t);
          Empilha(p, c);
          break;
        }
        else{
          printf("%c", t);
        }
      }
    }
  }while(c != '\0');
  printf("\n");
  LiberaPilha(p);
}

Função auxiliar:

A função acima necessita de uma função auxiliar para realizar a comparação das prioridades dos operadores. A prioridade varia, conforme o símbolo se encontre na entrada ou no topo da pilha, de acordo com a seguinte tabela:

SímboloPilhaEntrada
^34
*, /22
+, -11
(04

int Prioridade(char c, char t){
  int pc,pt;

  if(c == '^')
    pc = 4;
  else if(c == '*' || c == '/')
    pc = 2;
  else if(c == '+' || c == '-')
    pc = 1;
  else if(c == '(')
    pc = 4;

  if(t == '^')
    pt = 3;
  else if(t == '*' || t == '/')
    pt = 2;
  else if(t == '+' || t == '-')
    pt = 1;
  else if(t == '(')
    pt = 0;

  return (pc > pt);
}

Exemplo de programa principal:

int main(){
  char expr[] = "a*b+c*d^e/f-g*h";
 
  In2Pos(expr);
  return 0;
}

Aplicações de filas

1. Custo de caminhos entre cidades:

A seguir, mostraremos um exemplo de aplicação de filas para calcular distâncias entre cidades. Considere um conjunto de N cidades, sendo que algumas estão interligadas por vias diretas de mão única (Fig.1). Inicialmente vamos supor que todas estradas existentes possuem o mesmo custo de transporte.

Fig.1Fig.2Fig.3

Primeiramente vamos considerar uma camada de abstração utilizando o conceito matemático de grafos.
Um grafo orientado, ou grafo dirigido, G(V,A) é definido pelo par de conjuntos V e A, onde:

Por exemplo, no nosso problema de N cidades (numeradas de 0 a N-1) temos o grafo da Fig.2, onde: Uma das formas de representar um grafo, em linguagem C, é através da sua matriz de adjacência (Fig.3). Uma matriz de adjacência A é uma matriz quadrada NxN, onde os valores de A[i][j] são iguais a 1 se os vértices vi e vj são adjacentes, isto é, (vi,vj) ∈ A, e 0 caso contrário.

Um caminho no grafo é uma sequência de vértices adjacentes (de cada um dos vértices existe um arco para o vértice seguinte).
O comprimento do caminho é o número de arcos que o caminho usa. No nosso problema, o caminho é uma sequência de cidades, interligadas por vias diretas, a partir de uma cidade de origem até uma cidade de destino.

A importância do uso da abstração por grafos reside no fato de que muitos problemas provenientes de diversas áreas podem ser tratados com o uso de algoritmos comuns em grafos, permitindo o reaproveitamento do código.

Para resolver o problema dos caminhos de menor comprimento a partir de uma cidade de origem, considere o arquivo de código abaixo contendo a implementação de uma fila usando listas ligadas circulares.

Arquivo: fila_lig.c
typedef enum boolean {false,true} bool;

typedef struct _RegFila{
  TipoDado         dado;
  struct _RegFila *prox;
} RegFila;

typedef RegFila* Fila;

RegFila *AlocaRegFila(){
  RegFila* q;
  q = (RegFila*)calloc(1, sizeof(RegFila));
  if(q==NULL) exit(-1);  
  return q;
}

Fila     CriaFila(){
  Fila p;
  p = AlocaRegFila();
  p->prox = p;
  return p;
}

void     LiberaFila(Fila p){
  RegFila *q,*t;
  q = p->prox;
  while(q!=p){
    t = q;
    q = q->prox;
    free(t);
  }
  free(p);
}

bool     FilaVazia(Fila p){
  return (p==p->prox);
}

void     InsereFila(Fila *p, TipoDado x){
  RegFila *q;
  q = AlocaRegFila();
  q->dado = x;
  q->prox = (*p)->prox;
  (*p)->prox = q;
  *p = q;
}

TipoDado RemoveFila(Fila *p){
  RegFila *q,*t;
  TipoDado x;
  q = (*p)->prox;
  if(q==*p) exit(-1); /* Fila Vazia */
  t = q->prox;
  x = t->dado;
  q->prox = t->prox;
  if(t==*p) *p = q;
  free(t);
  return x;
}

Comprimento dos menores caminhos a partir de uma cidade de origem:

Função que calcula os comprimentos dos menores caminhos a partir de uma cidade de origem para as outras cidades. 
/* Numero de cidades consideradas */
#define N 6

void Comprimentos(int A[N][N], 
                  int orig, int C[N]) {
  Fila f;
  int i,j;
  f = CriaFila();
  for (i = 0; i < N; i++)
    C[i] = INT_MAX;

  C[orig] = 0;
  InsereFila(&f, orig);

  while ( !FilaVazia(f) ) {
    i = RemoveFila(&f);

    for (j = 0; j < N; j++) {
      if (A[i][j] == 1 && C[j] == INT_MAX) {
        C[j] = C[i] + 1;
        InsereFila(&f, j);
      }
    }
  }
  LiberaFila(f);
}

Caminho de comprimento mínimo entre cidade de origem e destino:

Função que calcula um caminho de comprimento mínimo entre uma cidade de origem e uma cidade de destino. 
void Caminho(int A[N][N], 
             int orig, 
             int dest,
             int C[N],
             int P[N]) {
  Fila f;
  int i,j;
  f = CriaFila();
  for (i = 0; i < N; i++) {
    C[i] = INT_MAX;
    P[i] = -1;
  }

  C[orig] = 0;
  InsereFila(&f, orig);

  while ( !FilaVazia(f) ) {
    i = RemoveFila(&f);

    if (i == dest) break;

    for (j = 0; j < N; j++) {
      if (A[i][j] == 1 && C[j] == INT_MAX){
        C[j] = C[i] + 1;
        P[j] = i;
        InsereFila(&f, j);
      }
    }
  }
  LiberaFila(f);
}

Exemplo de função principal main:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

/* Numero de cidades consideradas */
#define N 6

/* Para utilizar as funcoes de manipulacao de fila 
   presentes no arquivo fila_lig.c */
typedef int TipoDado;
#include "fila_lig.c"


/* Inserir nesse ponto o código das demais funções anteriores */


int main() {
/*
  A[i][j] indica se existe caminho direto da 
  cidade i para a cidade j.
*/
  int A[N][N] = {{0,0,0,0,0,0},
                 {0,0,1,0,0,1},
                 {1,0,0,0,0,0},
                 {0,0,1,0,0,0},
                 {0,1,0,0,0,1},
                 {1,0,0,0,0,0} };
/* C[i] vai armazenar o comprimento minimo de caminho
   de uma cidade de origem ate a cidade i */
  int C[N]; 
/* P[i] sera a cidade predecessora de i no  
   caminho otimo calculado, ou P[i] == -1 se i for
   a cidade de origem */
  int P[N];
/* Vetor auxiliar temporario */
  int T[N]; 
  int i,j;
  int orig, dest;

/* Calcula os menores valores de comprimento para
   todas cidades a partir de uma cidade de origem 
   (cidade 4 no exemplo abaixo) */
  orig = 4;
  Comprimentos(A, orig, C);

/* Imprime os comprimentos calculados: */
  for (i = 0; i < N; i++) {
    if (C[i] == INT_MAX)
      printf(" MAX");
    else
      printf(" %d", C[i]);
  }
  printf("\n");

/* Calcula um caminho de comprimento minimo entre uma 
   cidade de origem e uma cidade de destino fornecidas 
   (4 e 0 no exemplo) */
  dest = 0;
  Caminho(A, orig, dest, C, P);

/* Copia as cidades percorridas no sentido inverso
   (que é dado pelo mapa de predecessores) no vetor T */
  j = 0;
  i = dest;
  while ( i != -1 ) {
    T[j] = i;
    j++;
    i = P[i];
  }

/* Imprime cidades percorridas no sentido correto 
   de orig para dest */
  j--;
  for ( ; j >= 0; j--) {
    printf(" %d", T[j]);
  }
  printf("\n");

  return 0;
}

Custo de caminhos entre cidades em grafos com pesos nas arestas:

Imagine agora que o conjunto de N cidades numeradas de 0 a N-1 são interligadas por estradas que possuem um custo de transporte (distância, pedágios, etc). Nesse caso, A[i][j] pode conter, ao invés de 1 quando houver uma aresta entre vi e vj, o peso dessa mesma aresta (isto é, o custo de transporte da cidade vi para a cidade vj). Valores de A[i][j] nulos são usados para indicar a ausência de uma via direta da cidade vi para a cidade vj. Um grafo com pesos nas arestas é chamado de grafo valorado ou grafo ponderado.

O custo de um caminho num grafo ponderado é a soma dos custos das arestas atravessadas. Para encontrar de modo eficiente os caminhos de custo mínimo podemos usar o Algoritmo de Dijkstra, e quando conhecemos de antemão qual é a cidade de destino, podemos usar o Algoritmo A* (Lê-se: A-estrela). Esses algoritmos são mais sofisticados e utilizam filas de prioridade. Aqui iremos apenas discutir uma possível solução menos eficiente para o problema usando filas simples (no caso quando os pesos são valores inteiros) que reutiliza os códigos vistos acima.

A idéia é criar um grafo não-ponderado com vértices adicionais, de modo que os comprimentos dos caminhos nesse novo grafo correspondam aos custos dos caminhos para pares de vértices correspondentes no primeiro grafo. Por exemplo, um arco de peso 3 de vi para vj deverá ser trocado por três arcos não-ponderados, sendo necessária a criação de duas cidades fictícias (vértices adicionais) entre vi e vj. Logo, podemos calcular os comprimentos dos caminhos no novo grafo, consequentemente resolvendo o problema dos custos do primeiro grafo ponderado.

Funções recursivas

Slides

Torre de Hanoi no filme Planet of the Apes:

Algoritmos de enumeração: subsequências, subsequências recursiva, permutação

Link externo

Problema das 8 Rainhas

É possível colocar 8 rainhas do jogo de xadrez sobre o tabuleiro de modo que nenhuma das rainhas possa atacar outra? O programa abaixo encontra todas as 92 soluções do problema por busca exaustiva (força bruta). Uma das soluções é mostrada abaixo:

♛
♛
♛
♛
♛
♛
♛
♛

Com base nas informações do problema, vamos tentar reduzir o máximo possível o espaço de busca de modo a tornar a solução por força bruta viável. Abaixo discutimos algumas opções:

  1. Testar todas possíveis posições das rainhas: Um tabuleiro 8x8 tem 64 posições. Para a primeira rainha temos 64 possibilidades, para a segunda 63, para a terceira 62, ... Logo temos 64*63*62*61*60*59*58*57/8! = C64,8, ou seja, o número de combinações de 64 elementos tomados 8 a 8. C64,8 = 64!/(8!*(64-8)!) = 64!/(8!*56!) = 4426165368. Espaço de busca grande demais!
  2. Vamos reduzir o espaço de busca sabendo que as rainhas ocupam diferentes colunas (numeradas de zero a sete).
    • A rainha R1 tem 8 possibilidades de linhas na coluna 0,
    • A rainha R2 tem 8 possibilidades de linhas na coluna 1,
    • ...
    • A rainha R8 tem 8 possibilidades de linhas na coluna 7.
    No total temos 88 = 16777216.
  3. Vamos reduzir o espaço de busca ainda mais sabendo que as rainhas não podem ocupar a mesma linha.
    • A rainha R1 tem 8 possibilidades de linhas na coluna 0,
    • A rainha R2 tem 7 possibilidades de linhas na coluna 1,
    • A rainha R3 tem 6 possibilidades de linhas na coluna 2,
    • ...
    No total temos 8! = 40320, ou seja, o número de permutações de 8 elementos. Esse espaço de busca pode ser rapidamente testado por um programa de computador.

Resolução:

Adotamos o espaço de busca da terceira opção, tendo como base o código que gera as permutações dos elementos de um vetor. Cada permutação corresponde a uma solução candidata que deve ser verificada pelo programa. Como, por construção, os elementos do espaço de busca da terceira opção já satisfazem as restrições em linhas e colunas, só falta verificar as restrições nas diagonais.

Considere uma matriz do tabuleiro 8x8, com índices de zero a sete nas linhas e colunas. Cada possível configuração das rainhas no tabuleiro, dentro do espaço de busca considerado, é representada por um vetor int linhas[8];, onde a i-ésima rainha Ri ocupa a posição (x,y)=(i-1, linhas[i-1]) do tabuleiro.

Por exemplo, o vetor int linhas[8] = {0, 1, 2, 3, 4, 5, 6, 7}; corresponde a seguinte configuração:

♛
♛
♛
♛
♛
♛
♛
♛
O programa abaixo testa todas as 8! permutações dos elementos do vetor linhas e imprime todas as soluções do problema.

Funções auxiliares:

Para gerar as permutações do vetor, precisamos de uma função auxiliar que troca/inverte dois elementos de um vetor: 
void Troca(int v[], int i, int j) {
  int tmp;
  tmp = v[i]; 
  v[i] = v[j]; 
  v[j] = tmp;
}
Também precisamos de uma função que verifica se uma dada permutação do vetor linhas corresponde a uma solução do problema. Para isso, precisamos verificar as diagonais. 
int SolucaoValida(int linhas[]){
  int i;
  int x,y;
  int xx,yy;

  for(i = 0; i < 8; i++){
    x = i;
    y = linhas[i];

    xx = x;
    yy = y;
    while(1){
      xx += 1;
      yy -= 1;
      if(xx > 7 || yy < 0) break;
      
      if(yy == linhas[xx]) 
        return 0;
    }

    xx = x;
    yy = y;
    while(1){
      xx -= 1;
      yy -= 1;
      if(xx < 0 || yy < 0) break;
      
      if(yy == linhas[xx]) 
        return 0;
    }
  }
  return 1;
}
Precisamos também de uma função para imprimir as soluções encontradas: 
void ImprimeSolucao(int linhas[]){
  char tabuleiro[8][8];
  int i,j;
  int x,y;
  static int nsols = 0;

  nsols++;

  printf("******** SOL: %d ********\n",nsols);

  for(i = 0; i < 8; i++)
    for(j = 0; j < 8; j++)
      tabuleiro[i][j] = '.';

  for(i = 0; i < 8; i++){
    x = i;
    y = linhas[i];
    tabuleiro[y][x] = 'R';
  }

  for(i = 0; i < 8; i++){
    for(j = 0; j < 8; j++){
      printf(" %c ",tabuleiro[i][j]);
    }    
    printf("\n");
  }
}

Testando as permutações:

Iniciamos com a construção do vetor int linhas[8] = {0, 1, 2, 3, 4, 5, 6, 7};, e, em seguida, chamamos a função recursiva TestaPermutacoes, responsável por gerar as permutações, iniciando no índice zero (segundo parâmetro da função). 
void Solucoes8Rainhas() {
  int linhas[8];
  int i;
  for(i = 0; i < 8; i++)
    linhas[i] = i;
  TestaPermutacoes(linhas, 0);
}
Na função TestaPermutacoes, os elementos com índices menores que k estão fixos. A função deve gerar as permutações dos elementos com índices maiores ou iguais a k. Se k=8, então todos elementos estão fixos e o vetor deve ser verificado e impresso (caso trivial). Caso contrário, fixamos um novo elemento na posição k e testamos as permutações a partir do índice k+1. Repetimos esse processo fixando todos os possíveis elementos na posição k. 
void TestaPermutacoes(int linhas[], int k) {
  int i;
  
  if(k == 8) {
    if(SolucaoValida(linhas))
      ImprimeSolucao(linhas);
  }
  else{
    for(i = k; i < 8; i++) {
      Troca(linhas, k, i);
      TestaPermutacoes(linhas, k + 1);
      Troca(linhas, i, k);
    }
  }
}

Exemplo de programa principal:

#include <stdio.h>
#include <stdlib.h>

/*Colocar aqui as funções anteriores*/
...

int main(){
  Solucoes8Rainhas();
  return 0;
}

Filas de prioridades

Slides

Ordenação de vetores

Quick Sort:

#include <stdio.h>
#include <stdlib.h>

void troca(int V[], int a, int b){
  int tmp;
  tmp = V[a];
  V[a] = V[b];
  V[b] = tmp;
}

void quicksort(int V[], int inic, int fim){
  int pivo, i, f;
  if(inic < fim){
    pivo = V[inic];
    i = inic + 1;
    f = fim;

    while(i <= f){
      if(V[i] <= pivo)
        i++;
      else if(V[f] > pivo)
        f--;
      else{
        troca(V, i, f);
        i++;
        f--;
      }
    }

    i--;
    troca(V, inic, i);
    quicksort(V, inic, i-1);
    quicksort(V, i+1, fim);
  }
}

int main(){
  int V[] = {8,4,6,1,7,3,5,2,0};
  int i;

  quicksort(V, 0, 8);

  for(i = 0; i <= 8; i++)
    printf("%d ", V[i]);
  printf("\n");
  
  return 0;
}

Merge Sort:

#include <stdio.h>
#include <stdlib.h>

void intercala(int v1[], int i1, int f1,
               int v2[], int i2, int f2,
               int v3[]){
  int n1,n2,n3,k1,k2;
  int i;
  n1 = f1-i1+1;
  n2 = f2-i2+1;
  n3 = n1+n2;
 
  k1 = i1;
  k2 = i2;
  for(i = 0; i < n3; i++){
    if(k1 <= f1 && k2 <= f2){
      if(v1[k1] <= v2[k2]){ v3[i] = v1[k1]; k1++; }
      else{ v3[i] = v2[k2]; k2++; }
    }
    else if(k1 <= f1){ v3[i] = v1[k1]; k1++; }
    else{ v3[i] = v2[k2]; k2++; }
  }
}

void mergesort(int v[], int inic, int fim){
  int *aux;
  int m = (inic+fim)/2;
  int i;
  if(inic < fim){
    mergesort(v, inic, m);
    mergesort(v, m+1, fim);
 
    aux = (int *)malloc(sizeof(int)*(fim-inic+1));
 
    intercala(v, inic, m,
              v, m+1, fim,
              aux);
    for(i = 0; i < fim-inic+1; i++)
      v[inic + i] = aux[i];
    free(aux);
  }
}

int main(){
  int v[] = {6,8,5,7,4,1,2,3};
  int i;
  mergesort(v, 0, 7);
  for(i = 0; i < 8; i++)
    printf(" %d ", v[i]);
  printf("\n");
 
  return 0;
}

Heap Sort:

#include <stdio.h>
#include <stdlib.h>

void troca(int V[], int a, int b){
  int tmp;
  tmp = V[a];
  V[a] = V[b];
  V[b] = tmp;
}

int HeapPai(int i){
  return ((i - 1) / 2);
}

int HeapFilhoEsq(int i){
  return (2 * i + 1);
}

int HeapFilhoDir(int i){
  return (2 * i + 2);
}

void Sobe(int V[], int n, int i){
  int j, val;
  val = V[i];
  j = HeapPai(i);
  while(i > 0 && V[j] < val){
    V[i] = V[j];
    i = j;
    j = HeapPai(j);
  }
  V[i] = val;
}

void Desce(int V[], int n, int i){
  int k, val;
  val = V[i];
  k = HeapFilhoEsq(i);
  while(k < n){
    if(k+1 < n){ /* Pega o maior filho. */
      if(V[k] < V[k+1])
        k = k+1;
    }
    if(V[k] > val){
      V[i] = V[k];
      i = k;
      k = HeapFilhoEsq(k);
    }
    else break;
  }
  V[i] = val;
}

void OutroConstroiHeap(int V[], int n){
  int i,u;
  /* último nó não folha. */
  u = HeapPai(n - 1);
  for(i = u; i >= 0; i--)
    Desce(V, n, i);
}

void heapsort(int V[], int n){
  int i;
  OutroConstroiHeap(V, n);
  for(i = n-1; i > 0; i--){
    troca(V, 0, i);
    n--;
    Desce(V, n, 0);
  }
}

int main(){
  int V[] = {8,2,5,7,3,9,1,0};
  int i, n = 8;

  heapsort(V, n);
  for(i = 0; i < n; i++)
    printf("%d ", V[i]);
  printf("\n");
  
  return 0;
}