Fala prof Zika! Segue abaixo o código fonte e o link para o vídeo do Lab 3!Tenho breves palavras para descrever como esse lab me ajudou com manipulação de árvores que, por mais que já tenha sido cobrada em prova, ainda não tinha ficado 100% clara para mim. É com satisfação e alegria que apresento, no prazo, o código fonte do lab devidamente comentado :). Aproveito para relembrar que o curso de CES-11 foi muito importante para acrescentar muito conteúdo na minha formação acadêmica, acredito que aproveitei todas as aulas com muito apreço e extraí o máximo de informação que eu pude sobre os conteúdos desde listas, pilhas e filas, passando por árvores, algoritmos de ordenação e, por fim, grafos. Sobre o lab 3, além de me ajudar com a questão da manipulação de árvores com nós encadeados, mostrou como é possível imprimir o conteúdo de uma árvore em pré ordem utilizando recursão. Até o Lab 4 e 5!! Tamo Junto !!!
Vídeo:
Parte 1 : https://www.youtube.com/watch?v=E_NxiCRaEX4
Parte 2 : https://youtu.be/8Z5Ym8Ug_U0
Código fonte da Atividade 3:
///Murilo Orofino Tarosso
///TURMA T-19.3
#include<stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
///Declarações iniciais
struct node
{
char letra;///a letra que vem na palavra
int cont;/// quantas vezes já apareceu; 0 se não aparecer uma palavra da raíz até esse nó
node* filhos[26];///NULL quando não houver filho na letra
};
typedef struct node node;
typedef node* arvore;
typedef node* posicao;
int Letra(char carac)/// Função para alocar a letra dentro de cada "casa" do vetor, retorna a posição relativa da letra em relação a letra 'a'
{
if(carac >= 'A' && carac <= 'Z')///se a letra é maiúscula
return carac - 'A';
if(carac >= 'a' && carac <= 'z')///se a letra é minúscula
return carac - 'a';
}
arvore preencher(char a)///coloca a letra em um novo node, com o contado nulo. Todos os filhos recebem NULL.
{
arvore A = NULL;
A = (node*)malloc(sizeof(node));///alocando o novo node arvore
A->letra = a;///a letra de A será a
A->cont = 0;///contador inicialmente nulo
for(int i = 0; i < 26; i++) ///percorre todos os filhos de A, aterrando-os
{
A->filhos[i] = NULL;
}
return A;///retorna a arvore criada
}
void Ler(FILE *arqEntrada, arvore inicial)///essa função lê o arquivo de entrada construindo a arvore e a estrutura de dados requisitada
{
posicao q = NULL;
char aux[200];
while(fscanf(arqEntrada,"%s", &aux) != EOF)///até identificar o fim do arquivo, EOF é #define -1
{
q = inicial;///Inicializa o ponteiro posicao no inicio da arvore.
for(int i = 0; aux[i]!='\0'; i++) ///percorre cada palavra até o fim da string
{
if(aux[i] == '-')///se o caracter for um hífen deve-se encerrar a palavra e recomeçar uma nova palavra após o hífen
{
q->cont = q->cont + 1;
q = inicial;///retornando até o início da árvore(raíz) para a construção da nova palavra.
i++;///avança o contador pra ler a proxima palavra(pula para a proxima letra)
}
if(!isalpha(aux[i]))
{
continue;
}
else///se for qualquer caractere que não seja letra e nem o hífen(caso estudado abaixo) o programa deve passar pelo caractere, sem fazer nada
{
///verificando se já está incializado
if(q->filhos[Letra(aux[i])] == NULL)///se estiver aterrado(não inicializado)
{
q->filhos[Letra(aux[i])] = preencher(aux[i]);///utiliza a função do preenchimento
}
q = q->filhos[Letra(aux[i])];///se estiver inicializados... move o ponteiro pra posição da próxima letra
}
}
q->cont++;///ao finalizar essa palavra incrementa o contador dela;
}
}
void Imprimir(FILE *arqSaida, posicao q, int i, char *palavra)///essa função imprime uma palavra especificada, é recursiva a fim de imprimir em pré ordem e ordem alfabética
{
if(q == NULL)///posição vazia... fim da palavra ou nenhuma palavra
{
return;///sai da função
}
palavra[i] = q->letra;///vai vendo de letra em letra
i++;///incrementa a letra
if(q->cont != 0)/// verifica as palavras que existem e o término da palavra... se a palavra não exite ela volta ao condicional inicial
{
fprintf(arqSaida, "%d ", q->cont);
for(int r = 1; r < i; r++)
{
fprintf(arqSaida, "%c", Letra(palavra[r])+'a');
}
fprintf(arqSaida,"\n");///espaço necessário entre as linhas e última linha vazia no arqSaida
}
for(int k = 0; k < 26; k++)
{
Imprimir(arqSaida, q->filhos[k], i, palavra);///recursão pra percorrer cada letra da palavra, chamando a função para a proxima node
}
}
int main()
{
FILE *arqEntrada, *arqSaida;
arqEntrada = fopen("entrada.txt", "r");///já existe
arqSaida = fopen("saida.txt", "w");///será criado
arvore inicial = preencher('#');///char lixo padronizado no arquivo do lab enviado por email
char palavra[100];
Ler(arqEntrada, inicial);
Imprimir(arqSaida, inicial, 0, palavra);///inicia a recursão em i = 0, primeiro caractere da palavra
fclose(arqEntrada);
fclose(arqSaida);
return 0;
}
terça-feira, 27 de outubro de 2015
domingo, 4 de outubro de 2015
EXERCÍCIOS 1 E 4 - P1 DE CES11
Segue o código do Exercício 1 da P1:
O exercício tinha por objetivo o cálculo de expressões algébricas na forma simples, utilizando a estrutura de dados de árvores encadeadas diretas. A estrutura utilizada foi a de uma árvore binária, afinal, é uma árvore encadeada direta.
Código - fonte exercício 1:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
struct node
{
float info1, info2;
char operacao;///citar a operação : multiplicação, soma, etc.
node *filho_esq, *filho_dir;
};
typedef node* raiz;
typedef node* arvore;
void Iniciar_Arvore(arvore a, char *exp, int *i);
raiz Formando_Arvore(char *exp);
float Calculo_Expr(raiz A);
void free_raiz(raiz A);
float CalcExpr(char *str);
raiz Formando_Arvore(char *exp)/// Recebe a expressão, contruíndo a árvore binária. Retorna um ponteiro para a sua raíz
{
int j = 1;
raiz A = (node*)malloc(sizeof(node));
Iniciar_Arvore(A, exp, &j);
return A;
}
void Iniciar_Arvore(arvore a, char *exp, int *i)
{
if(isdigit(exp[*i]))
{
a->info1 = exp[*i] - '0';
(*i)++;
a->filho_esq = NULL;
}
else
{
a->filho_esq = (node*)malloc(sizeof(node));
(*i)++;
Iniciar_Arvore(a->filho_esq, exp, i);
}
a->operacao = exp[*i];
(*i)++;
if(isdigit(exp[*i]))
{
a->info2 = exp[*i] - '0';
(*i)++;
a->filho_dir = NULL;
}
else
{
a->filho_dir = (node*)malloc(sizeof(node));
(*i)++;
Iniciar_Arvore(a->filho_dir, exp, i);
}
(*i)++;
}
/// libera a arvore em pós-ordem
void free_raiz(raiz A)
{
if(A != NULL)
{
free_raiz(A->filho_esq);
free_raiz(A->filho_dir);
free(A);
}
}
float Calculo(char *str)
{
raiz A = Formando_Arvore(str);
float expr = Calculo_Expr(A);
free_raiz(A);
return expr;
}
float Calculo_Expr(raiz A)///Valor calculado
{
float raiz1, raiz2;
if(A->filho_esq != NULL)
raiz1 = Calculo_Expr(A->filho_esq);
else
raiz1 = A->info1;
if(A->filho_dir != NULL)
raiz2 = Calculo_Expr(A->filho_dir);
else
{
raiz2 = A->info2;
if(A->operacao == '+')
return raiz1 + raiz2;
else if(A->operacao == '-')
return raiz1 - raiz2;
else if(A->operacao == '*')
return raiz1 * raiz2;
else if(A->operacao == '/')
return raiz1 / raiz2;
}
}
int main()
{
char expressao[200];
while(1)
{
printf("DIGITE A EXPRESSAO A SER CALCULADA (DIGITE 'OK' PARA ENCERRAR O PROGRAMA) :\n");
scanf("%s", expressao);
if(strcmp(expressao,"OK") == 0)
break;
printf("VALOR TOTAL: %f\n\n", Calculo(expressao));
}
return 0;
}
Código do Exercício 4 da P1:
O exercício tinha por objetivo, percorrer uma árvore binária e imprimir os nós que tem "avôs" múltiplos de 5.
Foi utilizada a estrutura de nós encadeados para árvores binárias, o que demandou o uso de recursão.
Código fonte exercício 4:
#include <stdio.h>
#include <stdlib.h>
typedef struct cell cell;
struct cell
{
int info;
cell *arvore_a, *filho_esq, *filho_dir;
};
typedef cell* arvore;
///Recebe um ponteiro para a raíz e printa os nós que tem avôs múltiplos de 5
void Avo_MultCinco(arvore raiz)
{
if(raiz != NULL)
{
Avo_MultCinco(raiz->filho_esq);
if((raiz->arvore_a != NULL) && (raiz->arvore_a->arvore_a != NULL) && (raiz->arvore_a->arvore_a->info)%5 == 0)
printf("%d ", raiz->info);
Avo_MultCinco(raiz->filho_dir);
}
}
int main ()
{
///lê uma árvore
return 0;
}
Assinar:
Comentários (Atom)