AVL com Ncurses em C
Posted on jul 17, 2008 under C | 3 ComentáriosOlhando os trabalhos que realizei na faculdade. Encontrei uma AVL desenvolvida para a cadeira de estutura de dados. Implementei utilizando como interface gráfica NCURSES, para mostrar a árvore.
Irei compartilhar o código. Com certeza será bastante util para quem está estudando.
Este código tem alguns conceitos interessantes como:
- Não utiliza variáveis globais
- Os dados são inseridos na árvore quando ficar desbalanceada é informado e solicitado ao usuário se deseja balancear a árvore
- Informe como a árvore esta desbalanceada em quatro casos: EE,ED,DD e DE
- Calcula a altura da árvore
- Menu em Ncurses
- Visualização da árvore com Ncurses
/* * Nome: Marlon Luis Petry * Description: AVL compilacao gcc "Avl-Marlon.c" -o "Avl-Marlon" -g -lncurses -w Data: 20/10/2005 * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include#include #include #include #define CENTERX COLS/2 #define CENTERY LINES/2 #define DIST 5 typedef char string[50]; typedef struct t { string info; int alt; struct t *pai; struct t *left; struct t *right; }tree; int tipoBal = -1; string bal[4] = {"Caso EE","Caso ED","Caso DD","Caso DE"}; tree *bal_esq(tree *aux); tree *bal_dir(tree *aux); tree *rotacaoRR(tree *aux); tree *rotacaoLL(tree *aux); tree *rotacaoLR(tree *aux); tree *rotacaoRL(tree *aux); tree *insere(tree **root, string info, int h) { char ch; tree *aux; if (*root == NULL) { aux = (tree *) malloc(sizeof(tree)); strcpy(aux->info,info); aux->left = NULL; aux->right = NULL; aux->pai = NULL; aux->alt = 0; h = 1; *root = aux; } else { if (strcmp(info,(*root)->info) < 0) { insere(&(*root)->left, info, h); //Atualiza PAI do nó inserido if ((*root)->left->pai == NULL) (*root)->left->pai = *root; if (h) switch((*root)->alt) { //Estava mais alto à direita e inseriur mais um nó à esquerda case -1: (*root)->alt = 0; h = 0; //Não propaga os ajustes nos fatores de balanceamento break; case 0: (*root)->alt = 1; //o lado esquerdo fica maior e os fatores de //balanceamento acima deverao ser ajustados break; case 1: mvprintw(8,10,"Arvore Desbalaceou a esquerda A = %s Y = %s",(*root)->info,info); mvprintw(9,10,"Baleancear (S)im (N)nao: "); scanw("%c",&ch); if(ch == 'S' || ch == 's') { *root = bal_esq(*root); //FB == 2 -> retorna a sub-árvore balanceada h = 0; //não propaga a atualização dos fatores de } //balanceamento break; } } else { insere(&(*root)->right, info, h); //Atualiza PAI do nó inserido if ((*root)->right->pai != NULL) (*root)->right->pai = *root; if (h) switch ((*root)->alt) { //estava mais alto à esquerda e inseriu mais um nó à direita case 1: (*root)->alt = 0; h = 0; //não propaga os ajustes nos fatores de balanceamneto break; case 0: (*root)->alt = -1; // o lado direito fica maior do que o esquerdo e // o ajuste deve ser propagado break; case -1: //FB == -2 -> retorna a sub-árvore balanceada mvprintw(8,10,"Arvore Desbalaceou a direita A = %s Y = %s",(*root)->info,info); refresh(); mvprintw(9,10,"Baleancear (S)im (N)nao: "); scanw("%c",&ch); if(ch == 'S' || ch == 's') { *root = bal_dir(*root); h = 0; //não propaga a atualização dos fatores de } //balanceamento break; } } } return(*root); } tree *bal_esq(tree *aux) { tree *p; p = aux->left; if (p->alt == 1) { //sinais iguais e positivo tipoBal = 1; aux = rotacaoLL(aux); } else { tipoBal = 2; aux = rotacaoLR(aux); //sinais diferentes } aux->alt = 0; return(aux); } /* * O novo nó foi inserido à direita. Ocorreu desbalanceamento (fb == 2) */ tree *bal_dir(tree *aux) { tree *p; p = aux->right; if (p->alt == -1) //Sinais iguais e negativo { tipoBal = 3; aux = rotacaoRR(aux); } else { tipoBal = 4; aux = rotacaoRL(aux); //Sinais diferentes } aux->alt = 0; refresh(); return(aux); } //rotacoes tree *rotacaoRR(tree *aux) { tree *p; p = aux->right; aux->right = p->left; if (p->left != NULL) p->left->pai = aux; p->left = aux; p->pai = aux->pai; aux->pai = p; aux->alt = 0; return(p); } tree *rotacaoLL(tree *aux) { tree *p; p = aux->left; aux->left = p->right; if (p->right != NULL) p->right->pai = aux; p->right = aux; p->pai = aux->pai; aux->pai = p; aux->alt = 0; return(p); } tree *rotacaoLR(tree *aux) { tree *pai; //ponteiro para depois atualizar o pai após a rotação tree *no_left; //ponteiro para o filho esquerdo para atualizar o FB após a rotação tree *novo_no; //ponteiro à ser retornado int FB_fright; //fator de balanceamento do no à direita do filho esquerdo pai = aux->pai; no_left = aux->left; FB_fright = no_left->right->alt; aux->left = rotacaoRR(no_left); novo_no = rotacaoLL(aux); novo_no->pai = pai; aux->alt = (FB_fright == 1)?-1:0; //Atualiza FB do nó rotacionado no_left->alt = (FB_fright == -1)?1:0; // Atualiza FB do nó à esquerda do nó rotacionado return(novo_no); } /* * Atualização do FB e balanceamento para a raÃz esquerda */ tree *balanceamento_esquerdo(tree *no, int h) { tree *f_dir; int fb_dir; switch (no->alt) { case 1: no->alt = 0; break; case 0: no->alt = -1; h = 1; break; case -1: f_dir = no->right; fb_dir = f_dir->alt; if (fb_dir <= 0) { f_dir = rotacaoRR(no); if (fb_dir == 0) { no->alt = -1; f_dir->alt = 1; h = 0; } else { no->alt = 0; f_dir->alt = 0; } no = f_dir; } else { no = rotacaoRL(no); no->alt = 0; } } return(no); } /* * Atualização do FB e balanceamento para a raiz direita */ tree *balanceamento_direito(tree *no, int h) { tree *f_esq; int alt_esq; switch (no->alt) { case -1: no->alt = 0; break; case 0: no->alt = 1; h = 0; break; case 1: f_esq = no->left; alt_esq = f_esq->alt; if (alt_esq >= 0) { f_esq = rotacaoLL(no); if (alt_esq == 0) { no->alt = 1; f_esq->alt = -1; h = 0; } else { no->alt = 0; f_esq->alt = 0; } no = f_esq; } else { no = rotacaoLR(no); no->alt = 0; } } return(no); } /* * Busca nó substituto e realizada a remoção (busca o mais à direita do nó esquerdo */ tree *busca_remove(tree *no, tree *no_chave, int h) { tree *no_removido; if (no->right != NULL) { no->right = busca_remove(no->right, no_chave, h); if (h) no = balanceamento_direito(no, h); } else { strcpy(no_chave->info,no->info); no_removido = no; no = no->left; if (no != NULL) no->pai = no_removido->pai; h = 1; //Deve propagar a atualização dos FB free(no_removido); } return(no); } /* * Remoção da Ãrvore AVL */ tree *removeTree(tree **raiz, int info, int h) { if (*raiz == NULL) { printf("Chave não localizada !"); h = 0; } else { if (strcmp((*raiz)->info, info) > 0) { removeTree(&(*raiz)->left, info, h); if (h) *raiz = balanceamento_esquerdo(*raiz, h); } else if (strcmp((*raiz)->info , info) < 0) { removeTree(&(*raiz)->right, info, h); if (h) *raiz = balanceamento_direito(*raiz,h); } else { //Encontrou o elemento a ser removido if ((*raiz)->right == NULL) { if ((*raiz)->left != NULL) //Escolhe o nó à esquerda como substituto (*raiz)->left->pai = (*raiz)->pai; *raiz = (*raiz)->left; h = 1; } else if ((*raiz)->left == NULL) { if ((*raiz)->right != NULL) //Escolhe o nó à direita como substituto (*raiz)->right->pai = (*raiz)->pai; *raiz = (*raiz)->right; h = 1; } else { // Busca o elemento mais à direita do nó esquerdo (*raiz)->left = busca_remove((*raiz)->left, *raiz, h); //Se necessário efetua balanceamento (Esquerdo pois a função //busca_remove foi para o nó esquerdo) if (h) *raiz = balanceamento_esquerdo(*raiz, h); } } } return(raiz); } tree *rotacaoRL(tree *aux) { tree *pai; //ponteiro para depois atualizar o pai após a rotação tree *no_right; //ponteiro para o filho direito para atualizar o FB após a rotação tree *novo_no; //ponteiro à ser retornado int FB_fleft; //fator de balanceamento do no à esquerda do filho direito pai = aux->pai; no_right = aux->right; FB_fleft = no_right->left->alt; aux->right = rotacaoLL(no_right); novo_no = rotacaoRR(aux); novo_no->pai = pai; aux->alt = (FB_fleft == -1)?1:0; //Atualiza FB do nó rotacionado no_right->alt = (FB_fleft == 1)?-1:0; // Atualiza FB do nó à direita do nó rotacionado return(novo_no); } int maxDepth(tree *node) { if (node==NULL) { return(0); } else { int lDepth = maxDepth(node->left); int rDepth = maxDepth(node->right); if (lDepth > rDepth) return(lDepth+1); else return(rDepth+1); } } //print int print(tree *r,int x, int y) { int TotalWidth = width(r)*DIST; int centerWidth = (x + TotalWidth/2); int tamStr; int d = 0; //int centerWidthLinen= centerWidth +20; char t; if(r != NULL) { int leftWidth = width(r->left) * DIST; int rigtWidth = width(r->right) * DIST; tamStr = strlen(r->info); mvprintw(y + (DIST/20),(centerWidth -1- (tamStr/2)),"%s", r->info); if (r->left != NULL) { int leftX = print(r->left, x , y + DIST); } if (r->right != NULL) { int rightX = print(r->right, x + leftWidth, y + DIST); } } return centerWidth; } int width(tree *root) { if(root == NULL) return 1; else if(root->left == NULL && root->right == NULL) return 1; else return width(root->left) + width(root->right); } main() { tree *root = NULL; char ch; string msg; string info; int opt; int d=0; initscr(); bkgd(COLOR_PAIR(4)); strcpy(msg,"Pressione Qualquer Tecla"); while(1) { clear(); mvprintw(1,10,"%s","(1) - Inserir novo valor "); mvprintw(2,10,"%s","(2) - Mostrar"); mvprintw(3,10,"%s","(3) - Remove"); mvprintw(4,10,"%s","(4) - Altura"); mvprintw(5,10,"%s","(5) - Sair"); mvprintw(6,10,"[ ]"); move(6,11); scanw("%d",&opt); refresh(); switch(opt) { mvprintw(10,10,"%d",opt); case 1: mvprintw(7,10,"%s","Informe Valor: "); refresh(); getstr(info); insere(&root,info,1); break; case 2: clear(); print(root,CENTERX,0); mvprintw(LINES -2,CENTERX,"%s",bal[tipoBal]); tipoBal = -1; mvprintw(LINES -1,CENTERX,"%s",msg); getch(); break; case 3: mvprintw(7,10,"%s","Informe Valor: "); refresh(); getstr(info); removeTree(&root,info,1); break; case 4: //mvprintw(LINES - 1,CENTERX,"%s","f para sair "); mvprintw(7,10,"%s","Nivel"); refresh(); d = maxDepth(root); mvprintw(8,10,"%d",d); refresh(); break; case 5: //mvprintw(LINES - 1,CENTERX,"%s","f para sair "); ch = 'f'; break; } refresh(); if(ch == 'f') break; } endwin(); }
Não se esqueça este código é GPL pode ser usado desde que mantido os direitos autorais.
Assinem os FEEDS é de graça. Só essa semana 
Loading ...
Me lembrou o tempo de estruturas… Saudade qnd o problema era só com ponteiros perdidos…. eu era feliz e não sabia :p
Ótimo post, ainda não testei… quero ver qual eh a desse ncurses
Abraços
Olá Wagner
Cara que legal que gostou do post.
Obrigado pelo Feed back.
Há algum problema com a codificação do código (p. ex.: nó r).
Dica: use o plugin smiley themer para mudar os smileys do WordPress. Os que vêm de fábrica são horríveis.
Ah, cheguei aqui através de seu post no fórum do AdSense. Você já pensou em usar o sistema de afiliados do Buscapé ou do JáCotei? Assim você poderia colocar anúncios de livros de programação, o que certamente seria atraente para o tipo de visitantes que recebe. Os dois sistemas que mencionei pagam por consulta de preço: basta o usuário verificar o preço do item numa loja para você ganhar.
Atualmente uso o AdSense e meus ganhos não são muito maiores que o seu… pretendo usar o JáCotei assim que possível para ver se ao menos consigo recuperar o que investi no domínio.