2º Projeto de Algoritmo e Estrutura de Dados
1. Objetivos
O objetivo do projeto consiste no desenvolvimento de um programa em linguagem C para criar um dicionário utilizando árvore AVL.
2. Requisitos
O programa deve:
Possuir um menu para seleção das operações que podem ser realizadas;
Listar, em ordem crescente, as palavras do dicionário;
Listar, em ordem crescente, as palavras que começam com uma determinada letra;
Permitir inserir, pesquisar, alterar e excluir palavras;
Utilizar funções, árvore AVL e uma lista dinâmica linear;
O programa deverá ser totalmente desenvolvido pelo aluno, não sendo permitida a utilização de funções e bibliotecas já prontas;
Em caso de dupla, as notas poderão ser diferenciadas caso seja percebida a participação maior de algum deles. Os alunos poderão ser chamados para a defesa do trabalho, a qualquer momento, caso a professora assim desejar.
3. Dicionário
O dicionário será organizado dentro de uma árvore AVL, onde cada nó será composto pelos seguintes campos:
1) um campo para armazenar uma letra do alfabeto, sobre a qual serão realizadas as pesquisas, inserções, alterações, listagens e remoções de palavras;
2) um campo para armazenar as palavras/descrição em uma lista. Desse modo, cada nó também deverá ter uma lista encadeada, a qual deve permitir inserir, listar, alterar, remover e pesquisar as palavras que iniciem com a letra correspondente a esse nó da árvore;
3) dois campos para armazenar referência ao filho da direita e da esquerda.
Programa
/* 2ª Projeto de Estrutura de dados
Autoras: Stanelle Silveira , Ayres Rodrigues
Matriculas:2551 , 2510 */
//Bibliotecas necessárias
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
//#include <conio.h>
//Inicio do programa
/*****************************************************************************************************************/
//ESTRUTURA NECESSARIA
typedef struct lista_de_palavra{ /*Estrutura tipo lista dinâmica duplamente encadeada*/
char palavra[15],descri[500]; /*Declaração das string*/
struct lista_de_palavra *prox, *ant; /*Ponteiro de prox que vai guarda o proximo da lista e o ant, vai guarda o endereço do anterior */
}lista;
typedef struct arvore_dado{ /*Estrutura da arvore*/
lista *lista_palavra; /*Declaração da lista onde será amazenar as palavras e descrições*/
int bal; /*Varíavel tipo inteiro para auxílio do balanceamento*/
char letra; /*Varíavel */
struct arvore_dado *esq, *dir; /*Ponteiros para ligação das folhas e subarvore da arvore letra*/
}arvore;
/*****************************************************************************************************************/
//INICIALIZAÇÃO E FUNÇÃO PARA VERIFICAÇÃO ESTÁ VAZIA
arvore *inicializa(arvore *ABC){
ABC = NULL;
return ABC; //inicializar arvore
}
bool estaVazia(arvore *ABC){
return (ABC == NULL); //Verifica se está vazia a arvore
}
/*****************************************************************************************************************/
//PROTÓTIPO DAS FUNÇÕES NECESSARIAS
void Menu_principal(arvore *ABC); //Função do menu principal
void Menu_listar(arvore *ABC); //Função da menu lista
void Menu_Manter(arvore *ABC); //função do menu manter o dicionari
void imprimir_por_letra(arvore *R); //Função onde vai imprimir a palavra por letra
int avl_insere(arvore **R, char letra1); //Função inserir arvore ordenado e balaceando
void avl_aux2(arvore **R); //Função que auxilia a inseção
void avl_aux1(arvore **R); //Função que auxilia a inseção
void avl_esqdir(arvore **R); //Função de rotação da arvore de esquerda para direta
void avl_rotesq(arvore **R); // Função de rotação da arvore para o lado equerda
void avl_rotdir(arvore **R); //Função de rotação da arvore para o lado direito
/*****************************************************************************************************************/
//FUNÇÃO PARA AUXILIO DAS ROTAÇÕES
void avl_rotdir(arvore **R){ //Função do tipo void, usando ponteiro para ponteiro para que possa fazer seguinte alterações :
arvore *aux; //Declaração de um ponteiro auxiliar
aux=(*R)->esq; //O auxiliar vai receber o endereço do lado esquerdo
(*R)->esq=aux->dir; //A letra que estar no nó R o seu lado esquerdo irá apontar para o que está no lado direito do aux
aux->dir = *R; //A letra que aux recebeu, o seu lado direito irá apontar para a variável do R
(*R)->bal=0; // o fator de controle do balanceamento recebe 0
*R =aux; // R vai aponta para o aux fazendo assim modificação na lista
}
/*****************************************************************************************************************/
//ROTAÇÃO PARA A ESQUERDA
void avl_rotesq(arvore **R){ //Função do tipo void, usando ponteiro para ponteiro para que possa fazer seguinte alterações :
arvore *aux; //Declaração de um ponteiro auxiliar
aux=(*R)->dir; //O auxiliar vai receber o endereço do lado direito de R
(*R)->dir=aux->esq; //A letra que estar no nó R o seu lado direito irá apontar para o que está no lado esquerdo do aux
aux->esq = *R; //A letra que aux recebeu, o seu lado esquerdo irá apontar para a variável do R
(*R)->bal=0; // bal (variavel do balanceamento) recebe 0
*R =aux; // R passa a ser aux
}
/*****************************************************************************************************************/
//ROTAÇÃO DUPLA PARA A DIREITA - REALIZANDO PRIMEIRO A ESQUERDA E DEPOIS A DIREITA
void avl_esqdir(arvore **R){
arvore *fe, *ffd; //declaração de dois ponteiro do tipo arvore
fe=(*R)->esq; //fe recebe o endereço a esquerda de R, para realizar tal movimentação, já que não podemos modificar os ponteiros ainda
ffd=fe->dir; //ffd recebe o endereço a direita de fe que e a esquerda de R
//Rotação a esquerda
fe->dir=ffd->esq; //a direita de fe recebe o endereço da esquerda de ffd ou seja o menor elemento de ffd vai ser apontado pelo fe
ffd->esq=fe; //a esquerda de ffd recebe fe
//Rotação a direita
(*R)->esq=ffd->dir; //a esquerda de R recebe o endereço da direita de ffd
ffd->dir=*R; //a direita de ffd recebe R, assim a arvore vai estar balaceada
if(ffd->bal==+1) //se o fator de balanceamento de ffd for +1
(*R)->bal=-1; // o fator de balanceamento de R passará a ser -1
else
(*R)->bal=0; //senão passará a ser 0
if(ffd->bal==-1) //se o fator de balanceamento de ffd for igual a -1
fe->bal=1; //o fator de balanceamento de fe passará a ser 1
else
fe->bal=0; //senão a passará a ser o
*R=ffd; //R receberá ffd fazendo então as modificação na arvore
}
/*****************************************************************************************************************/
//ROTAÇÃO DUPLA PARA A ESQUERDA - FAZENDO A DIREITA SOBRE O FILHO E A ESQUERDA
void avl_diresq(arvore **R){
arvore *fe, *ffd; //declaração de ponteiros do tipo arvore para auxilio
fe= (*R)->dir; //fe recebe o endereço a direita de R, para realizar tal movimentação, já que não podemos modificar os ponteiros ainda
ffd=fe->esq; //ffd recebe o endereço a esquerda de fe que e a direita de R
//Rotação a direita
fe->esq=ffd->dir; //a esquerda de fe receberá o endereço a direita de ffd
ffd->dir=fe; //a direita de ffd receberá o endereço de fe
//Rotação a esquerda
(*R)->dir=ffd->esq; //a direita de R receberá o endereço a esquerda de ffd
ffd->esq=*R; //a esquerda de ffd receberá R, assim a arvore vai estar balaceada
if(ffd->bal==+1) // se o fator de balanceamento de ffd for igual a +1
(*R)->bal=-1; // o fator de balanceamento de R passará a ser -1
else
(*R)->bal=0; //senão passará a ser 0
if(ffd->bal==-1) //se o fator de balanceamento de ffd for -1
fe->bal=1; // o fator de balanceamento de fe passaá a ser 1
else //senão
fe->bal=0; //passará a ser 0
*R=ffd; //R receberá ffd fazendo então as modificação na arvore
}
/*****************************************************************************************************************/
//AUXILIAR DE ROTAÇÃO
void avl_aux1(arvore **R){
arvore *fe; //declaração de ponteiro do tipo arvore
fe =(*R)->esq; // fe recebe o endereço esquerda de R
if(fe->bal==+1) // se o fator de balanceamento for +1
avl_rotdir(&(*R)); // é chamado a rotação a direita
else //senão
avl_esqdir(&(*R)); //é chamado a rotação esquerda/direita(Dupla a direita)
(*R)->bal=0; //o fator de balanceamento recebe 0
}
/*****************************************************************************************************************/
//AUXILIAR DE ROTAÇÃO
void avl_aux2(arvore**R){
arvore *fd; //declaração de ponteiro do tipo arvore
fd=(*R)->dir; //fd recebe a direita de R
if(fd->bal==-1) //se o ofator de balanceamento desse nó for -1
avl_rotesq(&(*R)); //é chamado a rotação a esquerda
else //senão
avl_diresq(&(*R));// é chamado a direita/esquerda(Dupla a esquerda )
(*R)->bal=0; //fator de balanceamento recebe 0
}
/*****************************************************************************************************************/
//FUNÇÃO PARA INSERÇÃO DOS NÓS NA ARVORE BALANCEANDO
int avl_insere(arvore **R, char letra1){ //Função tipo inteiro, com parâmetro ponteiro para ponteiro e a letra de inserção
int certo; //Declaração da Variável auxiliar
if(*R==NULL){ //Só vai entrar nesse nó em dois casos:1-arvore vazia , 2- só depois que retornar a recursiva assim encontrando o local onde será inserido.
*R = (arvore*) malloc (sizeof(arvore)); //Alocação de memoria para para o nó R
if(*R==NULL) //caso nao seja possivel aloca retorna 0;
return 0; //Retorno zero
(*R)->lista_palavra=NULL; //Inicializa a lista de palavra com NULL
(*R)->esq=NULL; //O lado esquerdo recebe NULL
(*R)->dir=NULL; //O lado direito recebe NULL
(*R)->letra=letra1; //O nó recebe a letra que o usuário deseja inserir
(*R)->bal=0; //Atualiza o fator de balanceamento
return 1; //retorna 1
}
if(letra1< (*R)->letra){ //Nessa função de condição é verificado se a letra é menor que a letra que estar localizada na arvore
certo= avl_insere(&((*R)->esq),letra1); //Chama a funça de inserir novamente, passando como parâmetro o lado esquerdo para verificação e aguardar o retorno 1 para o fazer as modificações abaixo :
if(certo){ //Se a variável for igual a 0 entra nessa condição
switch ((*R)->bal){ //função de condição para verificação do fator
case -1: //caso seja -1 entra no case
(*R)->bal=0; //Atualiza o fator de balanceamento
certo=0; // Certo recebe 0, retornando para chamada recursiva
break;
case 0: //Caso seja 0 entra no case
(*R)->bal=+1; //Atualiza o fator de balanceamento
break;
case +1: //caso seja 1 entra no case
avl_aux1(&(*R)); //Chamada da função auxiliar 1, irá acontecer a rotação: direita ou a dupla, esquerda e direita
certo=0; // Certo recebe 0, retornando para chamada recursiva
break;
}
}
}
else //Caso a letra for maior ou igual a letra armazanada na arvore, entra nessa condição
if(letra1 >(*R)-> letra){ //Entra nessa função se a letra for maior que a letra da arvore
certo=avl_insere(&((*R)->dir),letra1); //Chama a funça de inserir novamente, passando como parâmetro o lado direito para verificação e aguardar o retorno 1 para o fazer as modificações abaixo :
if(certo){ //caso a variavel certo seja igual a 0, entra nessa condição
switch ((*R)->bal){ //função de condição para verificação do fator
case +1: //caso seja 1 entra no case
(*R)->bal=0; //Atualiza o fator de balanceamento
certo =0; // Certo recebe 0, retornando para chamada recursiva
break;
case 0: //Caso seja 0 entra nesse case
(*R)->bal= -1; //Atualiza o fator de balanceamento
break;
case -1 : //Caso seja -1 entra nesse case
avl_aux2(&(*R)); //Chamada da função auxiliar 2, irá acontecer a rotação: esquerda ou a dupla, direita e esquerda
certo =0; // Certo recebe 0, retornando para chamada recursiva
break;
}
}
}
else { //Caso a letra seja igual entra nessa função
certo =0; // Certo recebe 0, retornando para chamada recursiva
}
return certo;
}
/*****************************************************************************************************************/
//FUNÇÃO PARA ENCONTRAR O MAIOR NÓ A DIREITA
arvore *maximo(arvore *R){
if(estaVazia(R)) //Se a arvore estiver vazia
return NULL; //retorna NULL
else //senão
if( estaVazia(R->dir) ) //chamo estaVazia novamente passando a direita de R
return R; //se estiver vazia retorno R
else //senão estiver vazia
return maximo(R->dir); //chamo a função máximo novamente passando a direita de R
}
/*****************************************************************************************************************/
//FUNÇÃO PARA ATUALIZAR OS FATORES DE BALANCEAMENTO DEPOIS DA EXCLUSÃO
int Altura_atualiza(arvore *R) {
if (R == NULL) //Ponto de parada da recursão
return 0;
int hesq =Altura_atualiza(R->esq); //hesq receberá altura da sub arvore a esquerda
int hdir = Altura_atualiza(R->dir); //hdir receberá a altura da sub arvore a direita
R->bal = hesq - hdir; //bal receberá a diminuição da altura a esquerda pela a direita
if(hesq > hdir) //se a sub arvore a esquerda for maior q a direita
return hesq + 1; //retornará a altura + 1 para o lado esquerdo
else //se o lado direito for menor entra nesse else
return hdir + 1; //retornará a altura direita + 1 para o lado direito
}
/*****************************************************************************************************************/
//VERIFICA SE A ÁRVORE ESTÁ BALANCEADA APOS A EXCLUSÃO,CASO NÃO ESTEJA CHAMA A ROTAÇÃO NECESSÁRIA
void verifica(arvore **R){ //função que trabalha junto a função Altura_atualiza
int aux; //Declaração de aux
aux = Altura_atualiza(*R); //aux receberá o retorno da função Altura_atualiza
if(aux >2 && ((*R)->esq != NULL || (*R)->dir != NULL)){//caso aux for menor que dois não precisa entrar na função
//pois mesmo apos a exclusão continua balanceada
if(*R == NULL) //ponto de parada
verifica(&((*R)->esq)); //passo a esquerda
if((*R)->bal < 0 && ((*R)->dir->bal == 0 || (*R)->dir->bal == -1 )){//se o bal for negativo e o filho a direita
avl_rotesq(&(*R)); // for 0 ou -1
//será uma rotação simples a esquerda
}else if((*R)->bal>0 &&((*R)->esq->bal == 0 || (*R)->esq->bal == 1)){ //se bal for positivo e o filho a esquerda
avl_rotdir(&(*R)); //for 0 ou 1
//rotação simples a direita
}else if( (*R)->bal < 0 && (*R)->dir->bal == 1){//se o bal for negativo e o filho a direita
avl_diresq(&(*R)); // for 1 rotação dupla a esquerda
}else if((*R)->bal >0 && (*R)->esq->bal == -1){ //se bal for positivo e o filho a esquerda
avl_esqdir(&(*R)); //for -1 rotação dupla a direita
}
verifica(&((*R)->dir)); //passo a direita
}
}
/*****************************************************************************************************************/
//FUNÇÃO PARA REMOÇÃO DOS NÓS DA ARVORE
arvore *remover(arvore *R, char letra){ //Função remover do tipo arvore
arvore *aux; //ponteiro auxiliar do tipo arvore
if(R!=NULL) //So vai entrar nessa função caso R seja diferente de NULL
if(letra < R->letra) //Caso a letra seja menor que a letra existente na arvore entra nesse if
R->esq = remover(R->esq, letra); //irá percorre toda subarvore a esquerda, para achar a letra que o usuário deseja excluir
else //A letra e maior ou igual a letra existente na arvore
if(letra>R->letra) //se a letra que vai ser removida for maior que a que está na arvore
R->dir = remover(R->dir,letra); //irá percorre toda subarvore a direito, para achar a letra que o usuário deseja excluir
else { //caso não satisfaz nenhum dos caso feito anteriormente quer dizer que achou a letra
if(!estaVazia(R->esq) && !estaVazia(R->dir) ){//Verificação se o nó nao tem filhos
aux = maximo(R->esq); //aux recebe o endereço do nó maior a esquerda
R->letra = aux->letra; //R recebe a letra maior da esquerda
R->esq = remover(R->esq, R->letra); //A esquerda de R recebe o retorno da função remover
}
else{ //caso tenha filho ou subarvore entra no else
aux = R; //aux recebe o nó R
if(estaVazia(R->esq)) //se a esquerda de R está vazia entra nesse if
R = R->dir; // verificação para o retorno dos nó : R recebe o endereço a direita de R
else //senão
R = R->esq; //R recebe o endereço a esquerda de R
free(aux); // libera a memória ocupada por aux
}
}
return R; //Retorno do R
}
/*****************************************************************************************************************/
//FUNÇÃO PARA IMPRIMIR TODAS AS PALAVRAS E SUAS DESCRIÇÕES DO DICIONÁRIO EM ORDEM ALFABÉTICA
void imprimir_completo(arvore *R){
lista *aux3; //ponteiro do tipo lista ,onde estão as palavras
if(R != NULL){ //se a arvore não estiver vazia
imprimir_completo(R->esq); //chamo imprimir completo passando a esquerda
aux3 = R->lista_palavra; //aux3 recebe o o endereço que o nó R aponta, sendo o primeiro endereço da lista
printf("\n\n\n");
printf("|-----------------------------------------------------------------------|\n"); //tabela
printf(" *** %c *** \n",toupper(aux3->palavra[0])); // imprimi a letra
printf("|-----------------------------------------------------------------------|\n"); //tabela
printf(" PALAVRA \t| DESCRICAO \n");//tabela
printf("|-----------------------------------------------------------------------|\n");
while (aux3!= NULL){ //entra em um laço de repetição parando quando chegar ao fim da lista de palavras
printf(" * %s \t| %s \n",aux3->palavra,aux3->descri); //imprimi a palavra
printf("|-----------------------------------------------------------------------|\n"); // e sua descrição
aux3 = aux3->prox; //aux3 recebe o endereço do próximo nó da lista
}
imprimir_completo(R->dir); //passo a direita
}
}
/*****************************************************************************************************************/
//FUNÇÃO DE INSERIR PALAVRA NA LISTA ORDENADA.
arvore *inserir_palavra(arvore *R, char palav[]){ //função que insere ordenado as palavras na lista da letra começada com a palavra
lista *aux, *auxI; //ponteiro auxiliares do tipo lista duplamente encadeada
aux =(lista*)malloc(sizeof(lista)); //alocação da variavel aux
if(aux == NULL) // se aux for igual a null a alocação nao foi possível
printf("A alocacao nao foi porssivel"); //caso entre no if o usuario será informado que alocação nao foi possível
else{ //Caso a alocação foi feita com sucesso, entra nesse else
strupr(palav); //função da biblioteca string.h para transformar minúsculas em maiúsculas
strcpy(aux->palavra,palav); //função da biblioteca string.h para copiar uma string em outra, assim aux recebe a palavra
fflush(stdin); //limpo o buffer
scanf("%s",&aux->descri); // função gets para pegar a descrição da palavra
if((R->lista_palavra == NULL)|| (strcmp(aux->palavra,R->lista_palavra->palavra)<0)){//Entra nessa condição em dois momento: 1- nao existe no nenhum na lista 2- a palavra que o usuário deseja inserir e menor que a primeira da lista
aux->prox = R->lista_palavra; //o prox do aux recebe o proximo da lista, caso seja o primeiro a ser inserido, aux prox recebe NULL
aux->ant = NULL; // o ant de aux recebe NULL
if(R->lista_palavra!= NULL) //Caso nao seja o primeiro nó entra nesse if
R->lista_palavra->ant= aux; //O ponterio que aponta para o primeiro nó da lista, recebe aux
R->lista_palavra = aux; // o endereço do primeiro nó da lista passa a ser aux
}else { //caso nao satisfaz as condições acima entra nesse else
auxI = R->lista_palavra; //auxI recebe o endereço do primeiro nó da lista de palavras, para uma pesquisa
while (auxI->prox != NULL && ( strcmp(aux->palavra,auxI->palavra)>=0))// entra nessa condição se a palavra e maior ou igual a palavra que a auxiliar 2
auxI = auxI->prox; //Aux1 vai recebe a proxima palavra
if(strcmp(aux->palavra,auxI->palavra)>=0){ // Inserir no final o novo nó que será o ultimo da lista
aux->prox = NULL; //O prox de aux recebe NULL
aux->ant = auxI; //A posição ant recebe o endereço do ultimo nó
auxI->prox = aux; //O ultimo nó passa apontar para o novo nó
}else{ //se não satisfaz a condição anterior, entra nesse caso que vai inserir no meio
aux->prox = auxI; //O novo nó na posição prox recebe e endereço de aux1
aux->ant = auxI->ant; //O ant do aux recebe o endereço do do ant da auxiliar aux1
aux->prox->ant = aux; //O novo nó na posição prox que aponta para o endereço do próximo na posição ant recebe endereço de aux
aux->ant->prox = aux; //O novo nó na posição ant que aponta para o endereço do anterior na posição prox recebe endereço de aux
}
}
}
return R; //retorno R
}
/*****************************************************************************************************************/
//FUNÇÃO PARA PESQUISA NA ARVORE
arvore* pesq_arvore(arvore *R, char dadoPesq){ //recebe R e o dado a ser pesquisado
while (R != NULL && R->letra != dadoPesq){ //entra no laço de repetição enquanto R for diferente de NULL e a letra proxima for diferente da letra procurada
if (dadoPesq < R->letra) // a letra pesquisada e menor que a letra encontrada na arvore
R = R->esq; //caso o dado pesquisado for menor do que a letra que está na arvore, R percorre o lado esquerdo
else //caso nao satisfaz a condição anterior entra nesse else
R = R->dir; //caso o dado pesquisado for maior do que a letra que está na arvore, R percorre o lado direito
}
return R; //retorno o endereço onde o dado localiza
}
/*****************************************************************************************************************/
//FUNÇÃO PARA IMPRIMIR PALAVRAS
lista *imprimir_palavra(arvore *R,char palavra[]){
char prim_letra; //prim_letra para receber a letra inicial da palavra
lista *aux; //ponteiro do tipo lista
arvore *pesq; //ponteiro do tipo arvore
aux=NULL; //aux inicializado com NULL
prim_letra=palavra[0]; //prim_letra recebe a inicial da palavra
if (estaVazia(R)){ //se a lista está vazia
printf("\n\nLista VAZIA!\n\n");//informa ao usuário
}
else{
pesq = pesq_arvore(R,prim_letra); //pesq recebe o enderço que será retornado por pes_arvore
if(pesq == NULL){ // se pesq for NULL é porque não existe a palavra procurada
printf("\nPalavra nao existe\n");//informe ao usuário
aux = NULL; //aux recebe NULL
}else{
aux = pesq->lista_palavra;
while(aux != NULL && strcmp(aux->palavra,palavra) != 0)
aux = aux->prox;
if(aux==NULL)//se aux for igual a NULL
printf("\nPalavra nao existe\n"); //mensagem ao usuário
else { //senão imprimi a palavra e sua descrição
printf("\n|--------------------------------|\n"); //tabela
printf(" %s \n",aux->palavra);//imprimi a palavra
printf("\n|________________________________|\n");
printf(" %s \n",aux->descri); //imprimi a descrição
printf("\n|--------------------------------|\n");
}
}
}
return aux; //retorno de aux
}
/*****************************************************************************************************************/
//NESSA FUNÇÃO VAI PESQUISAR SE A PALAVRA EXISTE E SE JÁ TEM UM NÓ NA ARVORE COMERÇADA COM A INICIAL DA PALAVRA
arvore* pesq_inserir(arvore *R){ //Função tipo arvore
arvore *pesq; //ponteiro auxiliar para pesquisa tipo arvore
lista *aux,*auxp; //ponteiros auxiliares do tipo lista
char resp,prim_letra,palavra[10]; //variáveis do tipo char - caracter
int resb,num; //variáveis do tipo int - inteiro
printf("\n Entre com a palavra por favor:\n"); //mensagem ao usuário
fflush(stdin); //limpa o buffer
scanf("%s",&palavra); //função gets para inserir a palavra
strupr(palavra); //função para transforma minúscula em maiúscula
printf("\nDeseja inserir descricao? \n\n S=sim ou N=nao: _");//mensagem ao usuário
do{ //laço de repetição
resp=toupper(getch());//receber a resposta do usuário
}while(resp !='S' && resp != 'N'); //repete enquanto a resposta do usuário for dirente de S e N
if(resp=='N'){//se a resposta do usuário for N entra nesse if
auxp=imprimir_palavra(R,palavra); // Chama a função onde irá informa se a palavra existe e caso existir vai imprimir
}else{//caso o usuário digite S entra nesse else
prim_letra=palavra[0];//variavel vai reveber a primeira letr da palavra
pesq = pesq_arvore(R,prim_letra);//pesquisar se existe o primeirora letra na arvore
if(pesq==NULL){//caso a pesquisa volte NULL entra nessa função, onde irá criar um nó para ela
num=avl_insere(&R,prim_letra);//insere o nó na arvore e logo balacea
printf("\nDigite a descricao da palavra %s\n\n",palavra);
pesq=pesq_arvore(R,prim_letra);//pesquisa novamente o endereeço do nó na arvore, onde está a inicial da palavra
pesq =inserir_palavra(pesq,palavra);//insere a palavra na lista de palavras
}
else {//caso nao satisfaz as condições anteriores entra nesse else
if(pesq!=NULL){//Nesse caso já existe o nó da inicial na arvore
aux= pesq->lista_palavra;//aux vai axiliar na inserção da palavra, ele recebe o primeiro da lista
while(aux != NULL && strcmp(aux->palavra,palavra) != 0) //pesquisa da palavras , tem que ser diferente de NULL e diferente da palavra procurada
aux = aux->prox;//aux vai caminhar até encontrar a palavra igual ou nao existe
if(aux==NULL){ //se aux for igual a NULL
printf("\nDigite a descricao da palavra %s\n\n",palavra);//imprimi mensagem
pesq=pesq_arvore(R,prim_letra);//pesquisa novamente o nó da inicial
pesq =inserir_palavra(pesq,palavra);//insere a palavra
}else //caso NULL for diferente de NULL, que dizer que a palavra já existe
if(aux!=NULL){ // senão se aux for diferente de NULL
printf("\n O dicionario ja possui essa palavra\n");//imprimi a mensagem
auxp=imprimir_palavra(R,palavra);//imprimi a palavra e sua descrição
}
}
}
}
return R; //retorno arvore
}
/*************************************************************************************/
//FUNÇÃO EXCLUIR PALAVRA
arvore *excluir(arvore *R,char dado[]){
lista *aux; //Um ponteiro auxiliar do tipo lista de palavra
char resp,letra; //variavel resp para as reposta do usuario e letra para receber a primeira letra da palavra
arvore *pesq; // Um ponteiro tipo arvore para pesquisar a primeira letra na arvore
system("cls");
pesq=NULL; //inicializa o ponteiro
if (estaVazia(R)) //verificar se alista está vazia
printf("\n\nLista VAZIA!\n\n"); //informar o usuario
else{ //caso nao esteja vazia entra nesse condição
letra=dado[0]; //letra vai receber a primeira letra da palavra
aux = imprimir_palavra(R,dado); //minha auxiliar vai receber o retorno do função imprimir palavra, e nessa função irá ser verificado a existencia da palavra
if(aux!=NULL){ // caso aux seja diferente de NUll quer dizer que existe a palavra, entra nesse if
printf("\n\nDeseja realmente excluir palavra s-sim , N- nao\n\n");
fflush(stdin);
do{
resp=toupper(getch()); //receber a resposta
}while(resp !='S' && resp != 'N'); //caso ele digite outro caracter nao pedido, voltar a pedi novamente
if (resp=='S'){ // se a reposta for sim entra nesse if para que seja feita a exclusão
pesq=pesq_arvore(R,letra); // pesquisar a existencia da letra na arvore
if(aux == pesq->lista_palavra){ // aux é o endereço onde estar a palavra a ser excluido, logo se ela for igual o edereço da primeira palavra do no que pesq quarda o endereço, entra nesse if.
if (aux->prox != NULL) //Existe uma proxima palavra depois daquela que deseja excluir
aux->prox->ant = NULL; //O nó da palavra que vem depois da que deseja excluir recebe NULL
pesq->lista_palavra = pesq->lista_palavra->prox; // a lista na arvore irá apontar para a proxima palavra
}else{ //caso nao seja a palvra próxima entra nessa condição
if (aux->prox != NULL) //Existe uma proxima palavra depois daquela que deseja excluir
aux->prox->ant = aux->ant; //Vai ligar os nó que estão ao redor do nó excluido
aux->ant->prox = aux->prox; // O anterior recebe o proximo depois do que o usuário deseja excluido
}
if(pesq->lista_palavra==NULL){ //Caso a palavra seja a ultima do nó da arvore entra nesse if
R=remover(R,letra); //remove o nó da inicial da palavra na arvore
}
free(aux); //nó excluido
}
}
}
system("pause");
return R;//retorna modificações
}
/*****************************************************************************************************************/
//FUNÇÃO PARA ALTERAR AS DESCRIÇÕES DAS PALAVRAS
arvore *Alterar(arvore *R){
char palavra[10],descri[100],op; //variáveis do tipo char - caracter
lista *auxp;
lista *aux; //Um ponteiro auxiliar do tipo lista de palavra
char resp,letra; //variavel resp para as reposta do usuario e letra para receber a primeira letra da palavra
arvore *pesq; // Um ponteiro tipo arvore para pesquisar a primeira letra na arvore
int resb;
pesq=NULL; //inicializa o ponteiro
//ponteiro do tipo arvore
printf("\n\nDigite a palavra desejada : "); //mensagem ao usuário
fflush(stdin); //limpeza do buffer
scanf("%s",&palavra); //função para pegar a palavra digitada
strupr(palavra); // função que transforma minúscula em maiúscula
if (estaVazia(R)) //verificar se alista está vazia
printf("\n\nLista VAZIA!\n\n"); //informar o usuario
else{
letra=palavra[0]; //letra vai receber a primeira letra da palavra
//caso nao esteja vazia entra nesse condição
aux = imprimir_palavra(R,palavra);
//system("pause>>null");
//chamada da função para imprimir a palavra e sua descrição
if(aux != NULL){
printf("\n\n\nPara alterar a palavra e descricao digite S\nPara alterar apenas a descricao digite D\nCaso deseja nao alterar nada dite N \n\n");//mensagem ao usuário
do{
op = toupper(getch());
}while(op == 'S'&& op=='D' && op=='N'); //função getchar para pegar aresposta do usuário e ao mesmo tempo transformar em maiúscula
if(op=='D'){
printf("\nDigite a nova descricao: "); //mensagem ao usuário
fflush(stdin); //limpeza do buffer
scanf("%s",&descri); //altera a descrição, pegando uma nova
strcpy(aux->descri,descri); //copia da string descri para a descrição do nó lista
} else if(op=='S') { //que está na arvore
//minha auxiliar vai receber o retorno do função imprimir palavra, e nessa função irá ser verificado a existencia da palavra
//receber a resposta
//caso ele digite outro caracter nao pedido, voltar a pedi novamente
// se a reposta for sim entra nesse if para que seja feita a exclusão
pesq=pesq_arvore(R,letra); // pesquisar a existencia da letra na arvore
if(aux == pesq->lista_palavra){ // aux é o endereço onde estar a palavra a ser excluido, logo se ela for igual o edereço da primeira palavra do no que pesq quarda o endereço, entra nesse if.
if (aux->prox != NULL) //Existe uma proxima palavra depois daquela que deseja excluir
aux->prox->ant = NULL; //O nó da palavra que vem depois da que deseja excluir recebe NULL
pesq->lista_palavra = pesq->lista_palavra->prox; // a lista na arvore irá apontar para a proxima palavra
}else{ //caso nao seja a palvra próxima entra nessa condição
if (aux->prox != NULL) //Existe uma proxima palavra depois daquela que deseja excluir
aux->prox->ant = aux->ant; //Vai ligar os nó que estão ao redor do nó excluido
aux->ant->prox = aux->prox; // O anterior recebe o proximo depois do que o usuário deseja excluido
}
if(pesq->lista_palavra==NULL){ //Caso a palavra seja a ultima do nó da arvore entra nesse if
R=remover(R,letra);
//remove o nó da inicial da palavra na arvore
}
free(aux); //nó excluido
resb = Altura_atualiza(R);//função para Atualizar o fator
verifica(&R);//verificar se a arvore está balanceada se nao balanceia
resb = Altura_atualiza(R);
R=pesq_inserir(R);
}else if(op=='N')
printf("Palavra nao alterada\n");
}
}
system("pause");
return R;//retorna modificações
return R; //retorno R com as modificações
}
/*****************************************************************************************************************/
//FUNÇÃO PARA IMPRIMIR A PALAVRA
void imprimir_por_letra(arvore *R){
arvore *aux1;//auxiliar tipo arvore
lista *aux2;//auxiliar tipo arvore
char letra;//
printf("Digite a letra para a impressao : ");
fflush(stdin);
letra = toupper(getchar());//ler a letra
aux1 = pesq_arvore(R,letra);//pesquisa se existe a letra na arvore
if(aux1!=NULL){//caso aux1 for diferente de NULL quer dizer que existe a letra na arvore
if(aux1->lista_palavra == NULL)//teste para verificar se existe alguma letra na arvore
printf("\nNão existem palavras com a inicial %c nesse dicionario\n ",letra);
else{//imrpimir a palavra com a sua descrição
aux2 = aux1->lista_palavra;//auxiliar vai receber o endereço da lista de palavra
printf("\n\n");
printf(" %c\n\n",toupper(letra));//Imprimir
printf("|---------------------------------------------------|\n");
printf(" \tPalavra \tDescricao \n");
printf("|---------------------------------------------------|\n");
while (aux2!= NULL){//Se existi mais de uma palavra começada com a lentra acima, será impresso toda aqui
printf(" \t%s \t%s \n",aux2->palavra,aux2->descri);
aux2 = aux2->prox;
}
}
}
else printf("\n Não existem palavras com a inicial %c nesse dicionario \n",letra);
}
/*****************************************************************************************************************/
//MENU MANTER : O USUÁRIO PODERÁ EXCLUIR, ALTERAR E INSERIR DE ACORDO COM SUA NECESSIDADE
void Menu_Manter(arvore *ABC){
int op;//variável que vai receber a opção do usuario
int resb;
char palavra[10],resp;
do{
system("cls");
printf("\nDICIONARIO ABC\n\n");
printf("\nMENU MANTER DICIONARIO\n\n");
printf("[ I ] Inserir palavras\n");
printf("[ L ] Listar palavras\n");
printf("[ A ] Alterar palavras \n");
printf("[ E ] Excluir palavras \n");
printf("[ P ] Menu Principal\n");
printf("\n\nopcao : ");
fflush(stdin);
op = toupper(getch());//receber a opção do usuario em letra maiúscula
switch (op){
case 'I' ://Quando entrar nessa condição pedirá a paralvra a ser inserida
ABC =pesq_inserir(ABC);// função que pesquisa se a palavra já existe e isere caso o usuário digite a descrição
system("pause");
Menu_principal(ABC);//Retorna ao menu principal;
break;
case 'L' ://condição para entrar chamar o menu listar onde la encontrará duas forma de lista as palavras
Menu_listar(ABC);//função manter lista
break;
case 'A' ://caso o usuário digite A, será pedido a palavra que deseja altera-la
ABC = Alterar(ABC);//Função para alterar a palavra
system("pausenull");
Menu_principal(ABC);//Retorna a menu principal
break;
case 'E' ://Qando entra nessa condição o usuario deseja excluir uma palavra
printf("\nDigite a palavra a ser excluida : ");
fflush(stdin);
gets(palavra);//receber a palavra que o usuário deseja excluir
strupr(palavra);//converte uma string para maiúsculas
ABC = excluir(ABC,palavra);//função para excluir a palavra
resb = Altura_atualiza(ABC);//função para Atualizar o fator
verifica(&ABC);//verificar se a arvore está balanceada se nao balanceia
resb = Altura_atualiza(ABC);//função para Atualizar o fator
Menu_principal(ABC);//Retorna ao menu principal
break;
case 'P' ://opção para retorna o menu principal
Menu_principal(ABC);//função para retorno do menu principal
}
}while(op!='I' && op!='L' && op !='A' && op!='E'&& op!='P');//Um laço para fazer o usuário digitar uma das opções encotrada no menu
}
/*****************************************************************************************************************/
//MENU LISTA, TEM COMO FUNÇÃO LISTAR AS PALAVRAS POR COMEÇO DE LETRA OU TODAS PALAVRAS EXISTENTE
void Menu_listar(arvore *ABC){//Função tipo Void
char op;//variável que vai receber a opção do usuario
do{
system("cls");
printf("\nDICIONARIO ABC\n\n");
printf("\nMENU LISTAR\n\n");
printf("[ L ] Por letra _ apenas palavras que começam com um letra\n");
printf("[ C ] Completo- todas palavras e suas descricoes\n");
printf("[ M ] Menu manter dicionario \n");
printf("[ P ] Menu Principal \n");
printf("\n\nopcao : ");
fflush(stdin);
op = toupper(getch());//receber a opção do usuario em letra maiúscula
switch (op){//Condição para acessar as impressões das palavras
case 'L': //Opção para imprimir por letra
imprimir_por_letra(ABC);//Chama função para imprimir as palavras, por letra que o usuário desejar
system("pause");
Menu_principal(ABC); //Retorna ao menu principal
break;
case 'C' ://Opção C irá imprimir todas as palavras
imprimir_completo(ABC);//Função que imprimi as palavras do dicionário
system("pause");
Menu_principal(ABC);//Retorna ao menu principal
break;
case 'M' ://Opção M vai para função manter dicionário
Menu_Manter(ABC);
case 'P' ://Opção P retorna ao menu principal
Menu_principal(ABC);
}
}while(op!='L'&& op!='C' && op!='M' && op!='P');//Um laço para fazer o usuário digitar uma das opções encotrada no menu
}
/*****************************************************************************************************************/
//MENU PRINCIPAL: NELLE E ENCONTRADO OPÇÕES PARA ACESSAR AS PALAVRAS, MATER O DICIONARIO E SAIR
void Menu_principal(arvore *ABC){
lista *auxi;//auxiliar para imprimir a palavra quando o usuário optar por Pesquisar palavra
char op;///variável que vai receber a opção do usuario
char palavra[15];//receber a palavra
do{
system("cls");
printf("\nDICIONARIO ABC\n\n");
printf("\n***MENU PRINCIPAL***\n\n");
printf("[ P ] Pesquisar Palavras\n");
printf("[ M ] Manter dicionario\n");
printf("[ S ] Sair do Sistema \n");
printf("\n\nopcao : ");
fflush(stdin);
op = toupper(getch());//receber a opção do usuario em letra maiúscula
switch (op){
case 'P' ://Ao escolher essa opção o usuário irá digita a palavra que necessita pesquisar, logo o programa irá imprimi se existe ou nao, se existi imprime a palavra com descrição
printf("\n\nDigite a palavra a ser pesquisada : ");
fflush(stdin);
gets(palavra);//receber o palavra
strupr(palavra);//converte uma string para maiúsculas
auxi = imprimir_palavra(ABC,palavra);//imprimir a palavra
system("pause");
Menu_principal(ABC);//Retorna no menu principal
break;
case 'M' ://Chama a função do menu manter, onde o usuario poderá iserir, excluir e alterar a palavra
Menu_Manter(ABC);
}
}while(op!='P' && op!='M' && op!='S' );//Um laço para fazer o usuário digitar uma das opções encotrada no menu
}
/*****************************************************************************************************************/
//FUNÇÃO PRINCIPAL
int main(){
arvore *ABC;//declaração da arvore
ABC = inicializa(ABC);//inicialização da arvore
Menu_principal(ABC);//chamando o menu principal
printf("Obrigado pela preferencia\nExecute sempre %c\n",3);//Agradecimento
system("pause");
return 0;
}
