Baixe o app para aproveitar ainda mais
Prévia do material em texto
Questão A: Em outras palavras, se p é um nó qualquer então: p->chave ≤ Questões Resposta da A Link Principal - https://uploaddeimagens.com.br/imagens/arvore_binaria_de_busca-jpg Link Alternativo - https://ibb.co/gMtmXm Resposta da B - O caminho para se chegar até o nó 4: 15 – 3 – 8 e 4. Resposta da C Link Principal - https://uploaddeimagens.com.br/imagens/arvorebinaria-_remocao-jpg Link Alternativo - https://ibb.co/gw0LCm A partir do filho da esquerda do número 3 localiza-se o elemento que está a direita dele. É esse nó que irá substituir o nó que está sendo excluído da árvore, deve se tomar o cuidado de atualizar os ponteiros tanto do pai do 3 como do pai do 4 e dos filhos que ele passará a ter, antes de remover o nó que comporta o número 3 e o 4 assumir o seu lugar. Resposta da D Ela é uma Árvore Binária Degenerada. Link Principal - https://uploaddeimagens.com.br/imagens/arvore_degenerada-jpg Link Alternativo - https://ibb.co/mSo1JR _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Questão B: Resposta da A Eu acredito que seja lista, por um momento cheguei a pensar que poderia ser fila mas se analisarmos existem ultrapassagens ou seja não enquadra na lei de uma fila que é FIFO ( First In First Out). Pensando deste modo a lista é a melhor opção pois assim conseguimos uma manipulação melhor de dados. Fiz o exercício em lista dinâmica duplamente encadeada, uma lista dinâmica não é limitada apesar de ter colocado uma quantidade máxima pra ela. Utilizei duplo encadeamento assim fica muito melhor a manipulação da lista, tornando mais fácil a manipulação do código-fonte. Também fiz uso do nó descritivo facilitando ainda mais a manipulação da lista, podendo controlar a quantidade de elementos que ela possui, a quantidade máxima que ela suporta, e um apontamento para o início e fim. Resposta da B e C #include <stdio.h> #include <conio.h> #include <stdlib.h> #include <time.h> #include <locale.h> typedef struct informacao { int velocidade, numRegistro, tempo; /* velocidade dele, numero único de registro do automóvel e o tempo que ele permanecerá no anel */ short faixa; /* faixa em que ele está */ }info; struct elementos { struct informacao dados; /* dados dos veículos */ struct elementos* prox, *ant; /* os apontamentos para os próximos e anteriores da lista */ }; /** nó discritor */ struct noDiscritor { struct elementos* pInicio, *pFinal; /* apontamento para o inicio da lista e para o final */ unsigned long qtd, MAX; /* quantidade de elementos que a lista possui e quantidade máxima que ela pode possuir */ }; /* apenas typedefs para facilitar a manipulação das mesmas */ typedef struct elementos elem; typedef struct noDiscritor lista; short criaLista(lista**, unsigned long); short liberaLista(lista*); short criaNo(elem**, info); short listaVazia(lista*); short listaCheia(lista*); short consultaListaPos(lista* , unsigned long , info*); short insereListaFinal(lista*, info); short alteraFaixa(lista*, int, short); short alteraVelocidade(lista* , int, int); short ImprimirLista(lista*); short removeInicio(lista*); void pausa(); void main() { lista* li; info veiculo; int i, j, op; int tam = 10; long max = 10, qtd = 10; short bol; setlocale(LC_ALL, ""); /* adiciona os acentos brasileiros */ srand(time(NULL)); /* cria seeds diferentes toda vez que é executado o programa */ criaLista(&li, max); /* cria a lista */ for (i = 0; i < 10; ++i) /* cria os 10 primeiros elementos aleatórios */ { veiculo.faixa = rand() % 2 + 1; /* faixa só pode ser 1 ou 2, desta maneira ele escolherá aleatoriamente um dos dois*/ veiculo.numRegistro = rand() % 999999 + 1; /* numero de registro */ veiculo.velocidade = rand() % 100; /* velocidade, do veiculo aleatório até 100 km */ veiculo.tempo = rand() % 40 + 1; /* tempo do veiculo, ele ficara no maximo mas pode mudar o limite caso queira*/ insereListaFinal(li, veiculo); /* insere o veiculo na lista */ } printf("Começando a Inserir Carros:\n"); ImprimirLista(li); /* imprimirá a lista de veiculos */ op = rand() % 4 + 1; /* na primeira vez op não pode ser 0 por isso o + 1 */ while (op != 0) /* ficara escolhendo as funções aleatóriamente, até que op seja 0 */ { switch (op) /* escolherá aleatóriamente a função */ { case 1: tam = rand() % tam + 1; for (i = 0; i < tam; ++i, --qtd) { bol = removeInicio(li); if (bol != 1) break; } if (qtd < 0) /* checa se o for não foi executado mais uma vez após chegar em lista vaiza, caso chegue*/ qtd = 0; /* caso sim atribui zero a qtd */ break; case 2: tam = rand() % max + 1; for (i = 0; i < tam; ++i, ++qtd) { veiculo.faixa = rand() % 2 + 1; veiculo.numRegistro = rand() % 999999 + 1; veiculo.velocidade = rand() % 200; veiculo.tempo = rand() % 120 + 1; bol = insereListaFinal(li, veiculo); if (bol != 1) break; } if (qtd > max) /* checa se não foi tentado introduzir uma elemento a mais caso a lista esta cheia*/ qtd = max; /* caso sim, diminui o valor de qtd para o max*/ break; case 3: tam = rand() % qtd + 1; for (j = 0; j < tam; ++j) { i = rand() % qtd + 1; consultaListaPos(li, (unsigned long)(i), &veiculo); /* casting do i para evitar erros */ alteraVelocidade(li, veiculo.numRegistro, rand() % 200); } break; case 4: tam = rand() % qtd + 1; for (j = 0; j < tam; ++j) { i = rand() % qtd + 1; consultaListaPos(li, (unsigned long)(i), &veiculo); /* casting do i para evitar erros */ alteraFaixa(li, veiculo.numRegistro, rand() % 2 + 1); } break; } op = rand() % 5; /* limite 5, ou seja, poderá conter valores de 0 a 4 */ } printf("\nNova Simulação: \n"); ImprimirLista(li); /* imprime a lista para nós vermos o resultado final */ liberaLista(li); /* libera a lista */ pausa(); } /** informações do veiculo */ /** elementos da lista */ void pausa() { printf("\n Pressione uma Tecla"); _getch(); } short criaLista(lista** li, unsigned long MAX) /* note que a lista é passada como ** de lista isto se deve a passagem por referência */ { *li = (lista*)malloc(sizeof(lista)); /* aloca a lista*/ if (!li) /* verifica se a lista foi alocada corretamente, caso contrario retorna -1 */ return -1; (*li)->pInicio = NULL; /* seta os apontamentos para NULL */ (*li)->pFinal = NULL; (*li)->qtd = 0; /* inicia o qtd em 0 */ (*li)->MAX = MAX; /* inicia o max no valor passado pelos parâmetros */ return 1; /* retorna 1 pois a alocação foi um sucesso */ pausa(); } short liberaLista(lista* li) { elem* no; /* cria nó auxiliar, para poder andar pela lista e ir liberando, assim não perde o apontamento para o inicio da lista */ if (!li) /* verifica se a lista existe */ return -1; while ((li->pInicio) != NULL) /* enquanto houver elemento na lista, remova os elementos */ { no = li->pInicio; /* utiliza o nó para não perder o apontamento da lista */ li->pInicio = li->pInicio->prox; /* atribua a próxima posição da lista ao inicio */ free(no); /* remove antigo inicio */ } free(li); /* remove lista */ return 1; /* retorna 1 a liberação foi um sucesso */ pausa(); } short criaNo(elem** no, info dado) { *no = (elem*)malloc(sizeof(elem)); /* aloca o nó */ if (!no) /* verifica se não houve erro ao alocar. */ return 0; /* retorna 0 caso falha */ (*no)->dados = dado; /* atribui os dados passados ao nó */ (*no)->prox = NULL; /* seta os apontamentos em NULL. */ (*no)->ant = NULL; return 1; /* retorna 1 caso sucesso */ pausa(); } short listaVazia(lista* li) { if (!li) /* verifica se a lista existe */ return -1; return (li->qtd == 0); /*retorna um 1 caso seja vazia, ou 0 caso o oposto */ } short listaCheia(lista* li) { if (!li) return -1; return (li->qtd == li->MAX); pausa(); } short insereListaFinal(lista* li, info dado) /* passa a lista que deseja a inserção, e o dado a ser inserido. */ { elem* no; /* no auxiliar para poder inserir na lista */ short bol = criaNo(&no, dado); /* função que cria o nó */ if ((!li) || (!bol)) /* verifica se a lista e o nó é existentes */ return -1; if (listaCheia(li)) /* verifica se a lista está cheia */ return 0; no->ant = li->pFinal; /* seta o apontamento do anterior do nó no final da lista */ if (listaVazia(li)) /* caso a lista seja vazia o final e o inicio irão apontar para nó */ li->pInicio = no; else li->pFinal->prox = no; /* caso contrario o antigo final apontará para nó */ li->pFinal = no; /* nó vira o novo final */ ++li->qtd; /* atualiza a quantidade de elementos da lista */ return 1; pausa(); } short removeInicio(lista* li) { elem* no; /* cria o nó que ira auxiliar a liberar o dado desejado */ if (!li) /* verifica se lista existe */ return -1; if (listaVazia(li)) /* verifica se a lista não esta vazia */ return 0; no = li->pInicio; /* aponta o no ao inicio da lista */ if (li->qtd == 1) /* caso tenha apenas um elemento, a lista se tornará vazia. */ { li->pFinal = NULL; /* mudando o apontamento para NULL */ li->pInicio = NULL; } else { li->pInicio = li->pInicio->prox; /* caso contrario, atualize a apontamento para o novo inicio */ li->pInicio->ant = NULL; /* atualize o apontamento do novo inicio, desvinculando-o do anterior */ } --li->qtd; /* atualize a quantidade de elementos */ free(no); /* libere o antigo inicio */ return 1; pausa(); } short consultaListaPos(lista* li, unsigned long pos, info* dado) /* passe a lista por parâmetro, a posição que deseja consultar e onde ira receber o dado */ { elem* no; /* no auxiliar, para percorrer a lista, assim não perde o apontamento para o inicio */ register unsigned long i; /* contador */ if (!li) /* checa se a lista existe */ return -1; if ((listaVazia(li)) || (pos <= 0) || (pos > li->qtd)) /* chega se a lista esta vazia, ou, posição é 0 ou inferior ou se posição é maior que a quantidade de elementos da lista */ return 0; for (i = 1, no = li->pInicio; (i != pos) && (no != NULL); ++i, no = no->prox); /* encontra a posição do dado */ if (no == NULL) /* verifica se a posição era de fato existente */ return 0; *dado = no->dados; /* atribuir ao dado, o dado da lista */ return 1; pausa(); } short alteraFaixa(lista* li, int numRegistro, short faixa) { elem* no; /* nó auxiliar, para percorrer a lista */ if (!li) /* verifica se a lista existe */ return -1; if (listaVazia(li)) /* verifica se a mesma não é vazia */ return 0; if (li->pInicio->dados.numRegistro == numRegistro) /* se for igual o numRegisto, atribua o novo valor */ { li->pInicio->dados.faixa = faixa; return 1; } if (li->pFinal->dados.numRegistro == numRegistro) /* similar ao anterior */ { li->pFinal->dados.faixa = faixa; return 1; } if ((no = li->pInicio->prox) == NULL) /* aponta o nó ao próximo e checa se a lista não contém somente um elemento */ return 0; while ((no != li->pFinal) && (no->dados.numRegistro != numRegistro)) /* encontra o veiculo */ no = no->prox; if (no == li->pFinal) /* checa se foi encontrado mesmo de fato */ return 0; no->dados.faixa = faixa; /* atribui o novo valor faixa */ return 1; pausa(); } short alteraVelocidade(lista* li, int numRegistro, int velocidade) { elem* no; if (!li) return -1; if (listaVazia(li)) return 0; if (li->pInicio->dados.numRegistro == numRegistro) { li->pInicio->dados.velocidade = velocidade; return 1; } if (li->pFinal->dados.numRegistro == numRegistro) { li->pFinal->dados.velocidade = velocidade; return 1; } if ((no = li->pInicio->prox) == NULL) return 0; while ((no != li->pFinal) && (no->dados.numRegistro != numRegistro)) no = no->prox; if (no == li->pFinal) return 0; no->dados.velocidade = velocidade; return 1; pausa(); } short ImprimirLista(lista* li) { elem* no; register unsigned long i; setlocale(LC_ALL, ""); /* comando da locale.h para poder ter acentos */ if (!li) return -1; if (listaVazia(li)) return 0; printf("\n\t##### ...Imprimindo Veículos na via... #####\n"); for (no = li->pInicio, i = 1; no != NULL; no = no->prox, ++i) printf("\n%luº Carro:" "\nFaixa: %hi" "\nVelocidade: %3i km/h" "\nNumero de Registro: %6i." "\nTempo que Permanecerá: %3i min" "\n ----------\n", i, no->dados.faixa, no->dados.velocidade, no->dados.numRegistro, no->dados.tempo); printf("\n\t##### ...Termino da Impressão de Veículos no Anel viário... #####\n"); return 1; pausa(); }
Compartilhar