Ir ao conteúdo
  • Cadastre-se

gabriel.c94

Membro Pleno
  • Posts

    136
  • Cadastrado em

  • Última visita

Reputação

1
  1. Obrigado pela resposta, tentei refazer as funções de rotação, dessa vez fiz 1 para cada caso, mas mesmo assim algo ainda esta dando errado :/ Do jeito que fiz as funções de inserir, eu sempre tenho o nó da esquerda e da direita de cada ultima no de cada subarvore como um nó sem conteudo, desse jeito, quando vou inserir precisa apenas adicionar o conteudo ao nó ja criado e criar dois outros nó vazios abaixo dele. Mas não sei se isso esta atrapalhando o balanceamento. Fiz funçoes que tiram essa nós vazios antes de balancear e acrescentam eles de volta depois, mas ainda não funciona. O codigo esta desse jeito agora: #include <stdio.h>#include <stdlib.h>#include <string.h>//Estruturas para a arvore avl//----------------------------typedef struct node{ struct registry *content; int fb; struct node *left; struct node *right; struct node *parent; int height;}node;typedef struct tree{ struct node *root;}tree;typedef struct registry{ int id; char name[50]; int colums;}registry;//---------------------------//Fim das estruturasvoid initialize_tree(tree *t){ t->root = NULL;}void initialize_node(node *n){ n->content = NULL; n->fb = 0; n->left = NULL; n->right = NULL; n->parent = NULL;}void clean_blanks(node *n){ free(n->left); free(n->right); n->left = NULL; n->right = NULL;}void add_blanks(node *n){ node *new_left = malloc(sizeof(node)); node *new_right = malloc(sizeof(node)); initialize_node(new_left); initialize_node(new_right); n->left = new_left; n->right = new_right;}void rotate_left_twice(node *n){ node *k1,*k2,*k3=n,*b,*c; k1=k3->left; k2=k1->right; b=k2->left; c=k2->right; //Clean blanks clean_blanks(k1->left); clean_blanks(k2->left); clean_blanks(k2->right); clean_blanks(k3->right); k1->right=b; k3->left=c; k2->left=k1; k2->right=k3; n=k2; //Add blanks back add_blanks(n->left->left); add_blanks(n->left->right); add_blanks(n->right->left); add_blanks(n->right->right);}void rotate_left(node *n){ struct node *k1,*k2=n,*x,*y,*z; k1=k2->left; x=k1->left; y=k1->right; z=k2->right; //Clean blanks clean_blanks(x); clean_blanks(y); clean_blanks(z); k1->right=k2; k2->left=y; n=k1; //Add blanks back add_blanks(x); add_blanks(y); add_blanks(z);}void rotate_right_twice(node *n){ struct node *k1=n,*k2,*k3,*b,*c; k3=k1->right; k2=k3->left; b=k2->left; c=k2->right; //Clean blanks clean_blanks(k1->left); clean_blanks(k2->left); clean_blanks(k2->right); clean_blanks(k3->right); k1->right=b; k3->left=c; k2->left=k1; k2->right=k3; n=k2; //Add blanks back add_blanks(n->left->left); add_blanks(n->left->right); add_blanks(n->right->left); add_blanks(n->right->right);}void rotate_right(node *n){ struct node *k1=n,*k2,*x,*y,*z; k2=k1->right; x=k1->left; y=k2->left; z=k2->right; //Clean blanks clean_blanks(x); clean_blanks(y); clean_blanks(z); k1->right=y; k2->left=k1; n=k2; //Add blanks back add_blanks(x); add_blanks(y); add_blanks(z);}void balance(node *n, registry *r){ if (n->fb > 1 && r->id < n->left->content->id){ rotate_right(n); } if (n->fb < -1 && r->id > n->right->content->id){ rotate_left(n); } if (n->fb > 1 && r->id > n->left->content->id){ rotate_right_twice(n); } if (n->fb < -1 && r->id < n->right->content->id){ rotate_left_twice(n); }}void insert_node(node *t, registry *n, node *p){ if (t->content == NULL){ t->content = n; node *new_left = malloc(sizeof(node)); node *new_right = malloc(sizeof(node)); initialize_node(new_left); initialize_node(new_right); t->left = new_left; t->right = new_right; t->parent = p; } else if (n->id < t->content->id){ insert_node(t->left, n, t); } else if (n->id > t->content->id){ insert_node(t->right, n, t); } else if (n->id == t->content->id){ printf("O banco ja contem esse registro\n"); } t->fb = calc_fb(t); balance(t, n);}void remove_registry(node *t, int d){ node *aux1; node *aux2; node *blank_node1 = malloc(sizeof(node)); initialize_node(blank_node1); if (t->content == NULL){ printf("Registro nao encontrado!\n"); } else{ if (t->content->id == d){ if (t->left->content == NULL){ if (t->right->content == NULL){ if (t->parent->left == t){ t->parent->left = blank_node1; } else{ t->parent->right = blank_node1; } free(t); } else{ t->content = t->right->content; free(t->right); t->right = blank_node1; } } else{ if (t->right->content == NULL){ t->content = t->left->content; free(t->left); t->left = blank_node1; } else{ aux1 = t->left; while (aux1->right->content != NULL){ aux1 = aux1->right; } t->content = aux1->content; aux1->content = aux1->left->content; free(aux1->left); aux1->left = blank_node1; } } } else{ if (t->content->id > d){ remove_registry(t->left, d); } else{ remove_registry(t->right, d); } } }}void show_tree(node *n){ if (n->content == NULL){ return; } show_tree(n->left); printf("%d - %s\n", n->content->id, n->content->name); show_tree(n->right);}void find_and_print_registry(node *n, int d){ if (n->content->id == d){ printf("%d - %s\n", d, n->content->name); } else{ if (n->content->id < d){ find_and_print_registry(n->right, d); } if (n->content->id > d){ find_and_print_registry(n->left, d); } }}struct registry *make_registry(){ struct registry *new_reg = malloc(sizeof(registry)); printf("Qual o id do registro que voce deseja inserir?\n"); scanf("%d", &new_reg->id); printf("Qual o nome do registro que voce deseja inserir?\n"); scanf("%s", &new_reg->name); return new_reg;}int height(node *n){ int h1; int h2; if ( n->content == NULL ){ return 0; } h1 = height(n->left); h2 = height(n->right); if (h1 > h2){ return h1 + 1; } else{ return h2 + 1; }}int calc_fb(node *n){ return (height(n->left) - height(n->right));}void menu(node *main_node){ int option = -1; int option2; registry *new_entry; while (option != 0){ printf("\nDigite:\n0 - Para sair\n1 - Para inserir novo registro\n2 - Para remover um registro\n3 - Para buscar e imprimir um registro\n4 - Para ver todos os registros\n\n"); scanf("%d", &option); switch (option){ case 1: new_entry = make_registry(); insert_node(main_node, new_entry, NULL); break; case 2: printf("Qual o id do registro que voce deseja remover?\n"); scanf("%d", &option2); remove_registry(main_node, option2); break; case 3: printf("Qual o id do registro que voce deseja buscar?\n"); scanf("%d", &option2); find_and_print_registry(main_node, option2); break; case 4: show_tree(main_node); printf("Altura da arvore: %d\n", height(main_node)); } }}void main(){ struct tree *new_tree = malloc(sizeof(tree)); initialize_tree(new_tree); struct node *main_node = malloc(sizeof(node)); initialize_node(main_node); menu(main_node);} Preciso entregar esse trabalho domingo, alguem da uma luz pfv
  2. Pra um trabalho da disciplina de estrutura de dados estou montando uma especie de banco de dados baseado em arvore avl. Primeiramente fazendo como uma arvore binaria normal tudo funciona como deveria, mas quando tento implementar o balanceamento dos nós o programa da crash e não consigo detectar o erro. Segue o codigo completo do programa: #include <stdio.h>#include <stdlib.h>#include <string.h>//Estruturas para a arvore avl//----------------------------typedef struct node{ struct registry *content; int fb; struct node *left; struct node *right; struct node *parent; int height;}node;typedef struct tree{ struct node *root;}tree;typedef struct registry{ int id; char name[50]; int colums;}registry;//---------------------------//Fim das estruturasvoid initialize_tree(tree *t){ t->root = NULL;}void initialize_node(node *n){ n->content = NULL; n->fb = 0; n->left = NULL; n->right = NULL; n->parent = NULL;}node *rotate_left(node *n){ node *aux1, *aux2, *aux3, *aux4, *aux5, *aux6, *aux7; aux1 = n; aux2 = n->right; aux3 = n->right->right; aux4 = n->left; aux5 = n->right->left; n->content = aux2->content; n->left->content = aux1->content; n->left->left = aux4; n->left->left->parent = n->left; n->left->right = aux5; n->left->right->parent = n->left; n->right = aux3; n->right->parent = n; return n;}node *rotate_right(node *n){ node *aux1, *aux2, *aux3, *aux4, *aux5, *aux6, *aux7; aux1 = n; aux2 = n->left; aux3 = n->left->left; aux4 = n->right; aux5 = n->left->right; n->content = aux2->content; n->right->content = aux1->content; n->right->right = aux4; n->right->right->parent = n->right; n->right->left = aux5; n->right->left->parent = n->right; n->left = aux3; n->left->parent = n; return n;}void balance(node *n, registry *r){ if (n->fb > 1 && r->id < n->left->content->id){ n = rotate_right(n); } if (n->fb < -1 && r->id > n->right->content->id){ n = rotate_left(n); } if (n->fb > 1 && r->id > n->left->content->id){ n->left = rotate_left(n->left); n = rotate_right(n); } if (n->fb < -1 && r->id < n->right->content->id){ n->right = rotate_right(n->right); n = rotate_left(n); }}void insert_node(node *t, registry *n, node *p){ if (t->content == NULL){ t->content = n; node *new_left = malloc(sizeof(node)); node *new_right = malloc(sizeof(node)); initialize_node(new_left); initialize_node(new_right); t->left = new_left; t->right = new_right; t->parent = p; } else if (n->id < t->content->id){ insert_node(t->left, n, t); } else if (n->id > t->content->id){ insert_node(t->right, n, t); } else if (n->id == t->content->id){ printf("O banco ja contem esse registro\n"); } t->fb = calc_fb(t); balance(t, n);}void remove_registry(node *t, int d){ node *aux1; node *aux2; node *blank_node1 = malloc(sizeof(node)); initialize_node(blank_node1); if (t->content == NULL){ printf("Registro nao encontrado!\n"); } else{ if (t->content->id == d){ if (t->left->content == NULL){ if (t->right->content == NULL){ if (t->parent->left == t){ t->parent->left = blank_node1; } else{ t->parent->right = blank_node1; } free(t); } else{ t->content = t->right->content; free(t->right); t->right = blank_node1; } } else{ if (t->right->content == NULL){ t->content = t->left->content; free(t->left); t->left = blank_node1; } else{ aux1 = t->left; while (aux1->right->content != NULL){ aux1 = aux1->right; } t->content = aux1->content; aux1->content = aux1->left->content; free(aux1->left); aux1->left = blank_node1; } } } else{ if (t->content->id > d){ remove_registry(t->left, d); } else{ remove_registry(t->right, d); } } }}void show_tree(node *n){ if (n->content == NULL){ return; } show_tree(n->left); printf("%d - %s\n", n->content->id, n->content->name); show_tree(n->right);}void find_and_print_registry(node *n, int d){ if (n->content->id == d){ printf("%d - %s\n", d, n->content->name); } else{ if (n->content->id < d){ find_and_print_registry(n->right, d); } if (n->content->id > d){ find_and_print_registry(n->left, d); } }}struct registry *make_registry(){ struct registry *new_reg = malloc(sizeof(registry)); printf("Qual o id do registro que voce deseja inserir?\n"); scanf("%d", &new_reg->id); printf("Qual o nome do registro que voce deseja inserir?\n"); scanf("%s", &new_reg->name); return new_reg;}int height(node *n){ int h1; int h2; if ( n->content == NULL ){ return 0; } h1 = height(n->left); h2 = height(n->right); if (h1 > h2){ return h1 + 1; } else{ return h2 + 1; }}int calc_fb(node *n){ return (height(n->left) - height(n->right));}void menu(node *main_node){ int option = -1; int option2; registry *new_entry; while (option != 0){ printf("\nDigite:\n0 - Para sair\n1 - Para inserir novo registro\n2 - Para remover um registro\n3 - Para buscar e imprimir um registro\n4 - Para ver todos os registros\n\n"); scanf("%d", &option); switch (option){ case 1: new_entry = make_registry(); insert_node(main_node, new_entry, NULL); break; case 2: printf("Qual o id do registro que voce deseja remover?\n"); scanf("%d", &option2); remove_registry(main_node, option2); break; case 3: printf("Qual o id do registro que voce deseja buscar?\n"); scanf("%d", &option2); find_and_print_registry(main_node, option2); break; case 4: show_tree(main_node); printf("Altura da arvore: %d\n", height(main_node)); } }}void main(){ struct tree *new_tree = malloc(sizeof(tree)); initialize_tree(new_tree); struct node *main_node = malloc(sizeof(node)); initialize_node(main_node); menu(main_node);} Se alguem puder dar ajuda ia ser otimo, to a dois dias parado no mesmo problema :/
  3. Galera, a muito tempo que eu jogo os mesmos jogos no meu computador os dois ao mesmo tempo (Tibia e Heroes of Newerth), nunca tive problemas em rodar os 2, mas de um tempo pra ca comecei a ter problemas primeiro em dar alt + tab enquanto dentro do HON, e agora quando abro o HON o fps do tibia cai pra tipo 9! algo muito alem do normal, antes ficava uns 40 mesmo com o HON aberto... Reinstalei o driver da placa de video, reiniciei o computador, mas nada resolveu, e o mais interessante é que eu fui checar o uso de minha gpu, e tava algo em torno de 20-30% Por algum motivo ela nao esta usando todo o potencial, nem metade pra falar a verdade, e isso me atrapalha muito... Alguem sabe como posso resolver este problema?
  4. Galera, to com a nescessidade de fazer uma revista pra um trabalho do colegio, vocês acham que da pra fazer tranquilamento no corel?Se der, alguem tem algum video tutorial mostrando como se faz? Agradeço desde já, Gabriel

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...