#include #include #include ARVORE_B.h #include #define TOTAL_PAISES 198 char paises[TOTAL_PAISES][60] = { Afeganistao, Africa do Sul, Albania, Alemanha, Andorra, Angola, Antigua e Barbuda, Arabia Saudita, Argelia, Argentina, Armenia, Australia, Austria, Azerbaijao, Bahamas, Bangladesh, Barbados, Bahrein, Belgica, Belize, Benin, Bielorrussia , Bolivia, Bosnia Herzegovina, Botsuana, Brasil, Brunei, Bulgaria, Burkina-Fasso, Burundi, Butao, Cabo Verde, Camaroes, Camboja, Canada, Catar, Cazaquistao, Chade, Chile, China, Chipre, Cingapura, Colombia, Congo, Comores, Coreia do Norte, Coreia do Sul, Costa do Marfim, Costa Rica, Croacia, Cuba, Dinamarca, Djibuti, Dominica, Egito, El Salvador, Emirados Arabes Unidos, Equador, Eritreia, Escocia, Eslovaquia, Eslovenia, Espanha, Estados Unidos, Estonia, Etiopia, Federacao Russa, Fiji, Filipinas, Finlandia, Formosa , Franca, Gabao, Gambia, Gana, Georgia, Gra-Bretanha , Granada, Grecia, Groenlandia, Guatemala, Guiana, Guiana Francesa , Guine, Guine Bissau, Guine Equatorial, Haiti, Holanda, Honduras, Hungria, Iemen, Ilhas Marshall, Ilhas Salomao, India, Indonesia, Ira, Iraque, Irlanda, Irlanda do Norte , Islandia, Israel, Italia, Jamaica, Japao, Jordania, Kiribati, Kuweit, Laos, Lesoto, Letonia, Libano, Liberia, Libia, Liechtenstein, Lituania, Luxemburgo, Macedonia, Madagascar, Malasia, Malaui, Maldivas, Mali, Malta, Marrocos, Mauricio, Mauritania, México, Mianmar, Micronesia, Mocambique, Moldavia, Monaco, Mongolia, Namibia, Nauru, Nepal, Nicaragua, Niger, Nigeria, Noruega, Nova Zelandia, Oma, Panama, Palau, Papua Nova Guine, Paquistao, Paraguai, Peru, Polonia, Porto Rico , Portugal, Quenia, Quirguistao, Reino Unido, Rep. Centro-Africana, Rep. Dominicana, Republica Tcheca, Romenia, Ruanda, Samoa, San Marino, Santa Lucia, Sao Cristovao e Nevis, Sao Tome e Príncipe, Sao Vicente e Granadinas, Seicheles, Senegal, Serra Leoa, Servia e Montenegro, Siria, Somalia, Sri Lanka, Suazilandia, Sudao, Suecia, Suica, Suriname, Tadjiquistao, Tailandia, Tanzania, Togo, Tonga, Trinidad e Tobago, Tunisia, Turcomenistao, Turquia, Tuvalu, Ucrania, Uganda, Uruguai, Uzbequistao, Vanuatu, Vaticano, Venezuela, Vietna, Zaire , Zambia, Zimbabue }; void init_seletor(){ /* Inicializa semente */ srand(time(NULL)); } char* selecione_um_pais(){ // Gera numeros aletórios na faixa: 0 a 197 int i = rand() % TOTAL_PAISES; return paises[i]; } AB *cria_arvore(AB *nodo){ AB * novo = (AB*)malloc(sizeof(AB)); novo -> folha = true; novo -> n = 0; //O N é a quantidade de paises inseridos nodo = novo; return nodo; } AB *cria_nodo(){ AB *nodo = (AB*)malloc(sizeof(AB)); int i; nodo -> n = 0; for(i = 0; i < ((2*t)-1); i++) nodo -> chaves[i] = NULL; for(i = 0; i < (2*t); i++) nodo -> filhos[i] = NULL; nodo -> folha = false; return nodo; } void divide_filho_arvore_B(AB **nodo, int i){//divide_filho_arvore_B(var T : nodo, i : inteiro); AB *dir = cria_nodo(); AB *esq = (*nodo)->filhos[i]; int j; dir->folha = esq->folha; dir->n = t-1; for(j=0; j < (t-1); j++){ dir->chaves[j] = esq->chaves[j+t]; } if(esq->folha == 0){//quando não é folha for(j=0; jfilhos[j] = esq->filhos[j+t]; } } esq->n = (t-1); (*nodo)->filhos[i+1] = dir; (*nodo)->chaves[i] = esq->chaves[t-1]; (*nodo)->n = (*nodo)->n + 1; for(j=0; jchaves[j+2] = NULL; } void insere_em_nodo_nao_cheio(AB **nodo, char *chave){ //insere_em_nodo_nao_cheio(var *T : nodo, chave : literal[60]); int i = (*nodo)->n; int j; char letra1, letra2 = *chave; if((*nodo)->folha == 1){ for(j=0 ; jchaves[j]); if(letra2 < letra1) break; } while(i != j){ (*nodo)->chaves[i] = (*nodo)->chaves[i-1]; i--; } (*nodo)->chaves[i] = chave; (*nodo)->n += 1; }else{ for(j=0 ; jchaves[j]); if(letra2 < letra1) break; } if((*nodo)->filhos[j]->n == 5){ while(i != j){ (*nodo)->chaves[i] = (*nodo)->chaves[i-1]; i--; } } if((*nodo)->filhos[j]->n == ((2*t)-1)){ divide_filho_arvore_B(&(*nodo), j); } insere_em_nodo_nao_cheio(&(*nodo)->filhos[j], chave); } } void insere_nodo(AB **nodo, char *chave){ //insere_nodo(var *T : nodo, chave : literal[60]); AB *raiz = (*nodo); if(raiz->n == ((2*t)-1)){ AB *aux = cria_nodo(); (*nodo) = aux; aux->filhos[0] = raiz; divide_filho_arvore_B(&(aux), 0); insere_em_nodo_nao_cheio(&(aux),chave); } else{ insere_em_nodo_nao_cheio(&(raiz), chave); } } void pesquisa_nodos(AB *raiz, char letra){ int i=0, j=0, k=0; if(raiz != NULL){ if(raiz->n > 0){ char ch; while(j < raiz->n){ ch = *(raiz->chaves[j]); if(letra == ch){ printf(\nQuantidade de chaves: %d, raiz->n); printf(\nChaves encontradas: ); while(k < raiz->n){ printf(%s,,raiz->chaves[k]); k++; } printf(\nO nodo e folha?\n); if(raiz->folha == 0) printf(Nao\n); else printf(Sim\n); } j++; } if(raiz->folha == 0){ while(i < (2*t)){ pesquisa_nodos(raiz->filhos[i], letra); i++; } } } } } void imprime(AB *raiz){ int i=0, j=0, k=0; if(raiz != NULL){ if(raiz->n > 0){ // while(k < raiz->n){ printf(\nQuantidade de chaves: %d, raiz->n); printf(\nChaves encontradas: ); while(k < raiz->n){ printf( %s,,raiz->chaves[k]); k++; } printf(\nO nodo e folha?\n); if(raiz->folha == 0) printf(Nao\n); else printf(Sim\n); // j++; // } } if(raiz->folha == 0){ while(i < (2*t)){ imprime(raiz->filhos[i]); i++; } } } }
Posted on: Tue, 05 Nov 2013 10:48:14 +0000
Trending Topics
© 2015