Baixe o app para aproveitar ainda mais
Prévia do material em texto
ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 1ªAtividade - Implemente na linguagem C/C++ uma lista encadeada e suas operações de busca, inserção e remoção com estrutura de um elemento conforme abaixo : struct cel { int conteudo; struct cel *prox; }; Obs: Implemente um menu de operações como interface para o usuário. #include <stdio.h> #include <stdlib.h> struct cel { int conteudo; struct cel *prox; }; /* NOVO ITEN */ void inserir(struct cel **lista) { int iten; printf("\nDigite o novo iten: "); scanf("%d", &iten); struct cel *novo = (struct cel *) malloc(sizeof(struct cel *)); novo->conteudo = iten; novo->prox = *lista; *lista = novo; } /* IMPRESSÃO */ void mostrar(struct cel *lista) { system("clear"); printf("\nLista: "); while (lista != NULL) { printf("%d -> ", lista->conteudo); lista = lista->prox; } printf("NULL"); } /* REMOÇÃO */ void remover(struct cel **lista) { /* VERIFICANDO SE ESTA VAZIA */ ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 if (*lista == NULL) { printf("Não possui iten!"); return; } int iten; printf("\nDigite que será removido: "); scanf("%d", &iten); /* BUSCANDO ITEN PARA DELETAR */ struct cel *aux, *remover = NULL; if(*lista){ if((*lista)->conteudo == iten){ remover = *lista; *lista = remover->prox; } else{ aux = *lista; while(aux->prox && aux->prox->conteudo != iten) aux = aux->prox; if(aux->prox){ remover = aux->prox; aux->prox = remover->prox; } } } return; } int main() { int escolha; struct cel * lista = NULL; /* MENU */ while (1) { printf("\n Digite sua escolha:\n\t"); printf("\n\t 1 - Inserir itens \n\t 2 - Visualizar itens \n\t 3 - Remover itens \n\t 4 - Sair\n"); scanf("%d", &escolha); switch (escolha) { case 1: inserir(&lista); break; case 2: mostrar(lista); ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 break; case 3: remover(&lista); break; case 4: exit(0); default: printf( "\nOPCAO INVALIDA! \n" ); } } } 2ª Atividade - Implemente na linguagem C/C++ uma pilha e suas operações básicas de empilhar, desempilhar, retornar topo, vazia, cheia e etc com estrutura de um elemento conforme abaixo : struct Pilha { int topo; int capa; float *pElem; }; Obs: Implemente um menu de operações como interface para o usuário. #include <stdio.h> #include <stdlib.h> struct Pilha { int topo; int capa; float *pElem; }; /* INICIA A PILHA */ void iniciarpilha( struct Pilha *p, int c ){ p->topo = -1; p->capa = c; p->pElem = (float*) malloc (c * sizeof(float)); } /* VERIFICA SE ESTA VAZIA E CHEIA */ int verificarpilha ( struct Pilha *p ){ if( p-> topo == -1 ) return 0; ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 if (p->topo == p->capa - 1) return 1; } /* ADICIONA UM ELEMENTO NA PILHA */ void empilhar ( struct Pilha *p, float v){ p->topo++; p->pElem [p->topo] = v; } /* REMOVE UM ELEMENTO NA PILHA */ float desempilhar ( struct Pilha *p ){ float aux = p->pElem [p->topo]; p->topo--; return aux; } /* MOSTRA O ELEMENTO DO TOPO */ float mostratopo ( struct Pilha *p ){ return p->pElem [p->topo]; } int main(){ struct Pilha elementos; int tamanho, escolha; float iten; printf("\nDigite a quantidade de itens:? "); scanf("%d", &tamanho); iniciarpilha (&elementos, tamanho); while( 1 ){ /* MENU */ printf("\n Digite sua escolha:\n\t"); printf("\n\t1 - Empilhar\n\t2 - Desempilhar\n\t3 - Retorna o topo\n\t4 - Sair\n"); scanf("%d", &escolha); switch (escolha){ case 1: /* CHAMA A FUNÇÃO PARA VERIFICAR SE ESTA CHEIA*/ ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 if (verificarpilha(&elementos) == 1) printf("\nPILHA CHEIA! \n"); else { printf("\nDigite o novo iten: "); scanf("%f", &iten); /* CHAMA A FUNÇÃO PARA ADICIONAR UM ELEMENTO*/ empilhar (&elementos, iten); } break; case 2: /* CHAMA A FUNÇÃO PARA VERIFICAR SE ESTA VAZIA*/ if (verificarpilha(&elementos) == 0 ) printf( "\nPILHA VAZIA! \n" ); else{ /* CHAMA A FUNÇÃO PARA REMOVE UM ELEMENTO*/ iten = desempilhar (&elementos); printf ( "\n%.1f DESEMPILHADO!\n", iten ); } break; case 3: /* CHAMA A FUNÇÃO PARA VERIFICAR SE ESTA VAZIA*/ if ( verificarpilha (&elementos) == 0 ) printf( "\nPILHA VAZIA!\n" ); else { /* CHAMA A FUNÇÃO PARA MOSTRA O TOPO*/ iten = mostratopo (&elementos); printf ( "\nTOPO: %.1f\n", iten ); } break; case 4: exit(0); default: printf( "\nOPCAO INVALIDA! \n" ); } } } ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 3ª Atividade - Implemente na linguagem C/C++ uma Lista de Prioridade em um Heap por meio de um vetor conforme abaixo : Obs: Mostre os valores do nó e de seu pai e filho(s) a partir da chave informada pelo usuário. #include <stdio.h> #include <stdlib.h> int main() { /* posicao - VARIáVEL PARA CALCULAR A POSIÇÃO vetor[] - VALORES DA ARVORE */ int posicao, vetor[10] = {17,12,8,5,3,6,2,4,2,1}; /* REPETE ATÉ QUE SEJA DIGITADO 0 */ while (posicao != 0){ printf("Digite a posição ('0' para terminar):"); scanf("%d", &posicao); /* VERICA SE A POSIÇÃO E VÁLIDA*/ if(posicao < 0 || posicao > 10){ printf("\nPosição inválida!\n\n"); }else{ /* VERIFICA SE O ELEMENTO E O PAI*/ if (posicao == 1){ printf("\n\tElemento da posição: %d", vetor[posicao-1]); } else{ printf("\n\tElemento da posição: %d", vetor[posicao-1]); /* CALCULA A POSIÇÃO DO ELEMENTO PAI */ printf("\n\tElemento pai: %d", vetor[posicao/2 - 1]); }ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 /* VERIFICA SE A POSIÇÃO ESTA DENTRO DO LIMITE */ if (posicao*2 - 1 > 10) printf("\n\tFilho à esquerda: NULL"); else /* CALCULA A POSIÇÃO DO ELEMENTO FILHO DA ESQUERDA */ printf("\n\tFilho à esquerda: %d", vetor[posicao*2 - 1]); /* VERIFICA SE A POSIÇÃO ESTA DENTRO DO LIMITE */ if (posicao*2 >= 10) printf("\n\tFilho à direita: NULL\n\n"); else /* CALCULA A POSIÇÃO DO ELEMENTO FILHO DA DIREITA */ printf("\n\tFilho à direita: %d\n\n", vetor[posicao*2]); } } } 4ª Atividade - Inclua na implementação anterior de sua Lista de Prioridade (Heap) as funções incluir, extrair e corrigir o Heap. Obs: para realizar a extração será necessário corrigir o Heap (Heapify). #include <stdio.h> #include <stdlib.h> int valor, maximo = 15, tamanho = 0; int vetor[15] = {17, 12, 8, 5, 3, 6, 2, 4, 2, 1}; int direita(int aux){ if (2 * aux + 1 >= maximo) return maximo - 1; return 2 * aux + 2; } int esquerda(int aux){ if (2 * aux + 1 >= maximo) ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 return maximo - 1; return 2 * aux + 1; } void troca(int *aux1, int *aux2){ int temporario = *aux2; *aux2 = *aux1; *aux1 = temporario; } void terceiraquestao(void){ int posicao; printf("Digite a posição:"); scanf("%d", &posicao); /* VERICA SE A POSIÇÃO E VÁLIDA*/ if(posicao < 0 || posicao > 10){ printf("\nPosição inválida!\n\n"); }else{ if (posicao == 1){ printf("\n\tElemento da posição: %d", vetor[posicao-1]); } else{ printf("\n\tElemento da posição: %d", vetor[posicao-1]); /* CALCULA A POSIÇÃO DO ELEMENTO PAI */ printf("\n\tElemento pai: %d", vetor[posicao/2 - 1]); } /* VERIFICA SE A POSIÇÃO ESTA DENTRO DO LIMITE */ if (posicao*2 - 1 > 10) printf("\n\tFilho à esquerda: NULL"); else /* CALCULA A POSIÇÃO DO ELEMENTO FILHO DA ESQUERDA */ printf("\n\tFilho à esquerda: %d", vetor[posicao*2 - 1]); /* VERIFICA SE A POSIÇÃO ESTA DENTRO DO LIMITE */ if (posicao*2 >= 10) printf("\n\tFilho à direita: NULL\n\n"); else /* CALCULA A POSIÇÃO DO ELEMENTO FILHO DA DIREITA */ printf("\n\tFilho à direita: %d\n\n", vetor[posicao*2]); } return; } ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 void corrigir(int *vetor, int tamanho, int posicao){ if (tamanho == 0) printf("\nNão pussui elemento"); if (tamanho == 1) printf("\nPossui somentes 1 elemento."); else{ int maior = posicao; int dir = direita(posicao); int esq = esquerda(posicao); if (dir < tamanho && vetor[dir] > vetor[maior]) maior = dir; if (esq < tamanho && vetor[esq] > vetor[maior]) maior = esq; if (maior != posicao){ troca(&vetor[posicao], &vetor[maior]); corrigir(vetor, tamanho, maior); } } } void inserir(int *vetor){ printf("\nInforme o elemento para inserção:"); scanf("%d", &valor); if (tamanho == 0){ vetor[0] = valor; tamanho += 1; } else{ vetor[tamanho] = valor; tamanho += 1; for (int i = tamanho / 2 - 1; i >= 0; i--){ corrigir(vetor, tamanho, i); } } printf("Novo elemento!\n"); } void remover(int *vetor){ printf("\nInforme o elemento para remoção:"); scanf("%d", &valor); int i; for (i = 0; i < tamanho; i++){ if (valor == vetor[i]) break; } ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 troca(&vetor[i], &vetor[tamanho - 1]); tamanho -= 1; for (int i = tamanho / 2 - 1; i >= 0; i--){ corrigir(vetor, tamanho, i); } printf("Realizado a remoção!\n"); } void imprimir(int *vetor, int tamanho){ for (int i = 0; i < tamanho; ++i) printf("%d ", vetor[i]); } int main(){ tamanho = 10; int escolha; while (1){ printf("\n Digite sua escolha:\n\t"); printf("\n\t1 - Terceira questão\n\t2 - Inserir\n\t3 - Remover\n\t4 - Imprimir\n\t5 - Sair\n"); scanf("%d", &escolha); switch (escolha){ case 1: terceiraquestao(); break; case 2: inserir(vetor); break; case 3: remover(vetor); break; case 4: imprimir(vetor, tamanho); break; case 5: exit(0); default: printf( "\nOPCAO INVALIDA! \n" ); } } } ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 5ª Atividade - Pesquise sobre funções Hashing, relacione e descreva pelo menos 3 aplicações atuais dessa tecnologia Checksums As funções de hash podem ser usadas para detectar operações durante downloads. Por exemplo, se você deseja baixar um programa, você precisa ter certeza de que é o programa original e que nada foi modificado durante o processo de download. Para evitar isso, você pode calcular o hash do programa antes de baixá-lo. Isso é então e usado como uma impressão digital. Após o download, você usa a mesma função para calcular o hash novamente. Se os dois valores forem iguais, não houve modificação do original. Assinatura Eletrônica Assinaturas digitais são projetadas para confirmar a integridade de uma mensagem. O remetente de uma mensagem digital pode usar uma função de hash para convertê-la em um valor de hash. Em seguida, ele criptografa esse valor com a chave privada. Ele envia a mensagem e o valor criptografado para o destinatário. Os destinatários agora podem garantir que a mensagem que estão lendo não foi adulterada quando foi enviada. Podendo descriptografar com a chave oficial para obter o hash da mensagem calculada anteriormente. Ele pode então calcular a própria mensagem usando a mesma função de hash usada pelo remetente. Agora o destinatário pode comparar os dois valores. Se o valor obtido no cálculo corresponder ao valor obtido na decodificação do valor enviado com a mensagem, então é a mensagem original. Armazenamento de senha Hash são usadas para armazenar senhas foi mencionado emvários lugares. Se as senhas forem armazenadas em texto simples, elas poderão ser lidas no caso de um ataque. Isso não acontece se você usar uma função de hash para converter a senha em um valor de hash e apenas armazenar esse valor. Se o usuário quiser entrar no sistema, ele digita sua senha, cria um hash a partir da senha inserida usando a mesma função de antes. Se esse valor recém-determinado corresponder ao valor armazenado, o usuário será autenticado. Hashing de dados o hash de dados pode ser usado em lojas online. Todos os dados pessoais, como nomes de usuário ou endereços de e-mail, são criptografados. Em vez de texto simples, apenas armazene o hash. Dessa forma, os usuários da loja online podem permanecer anônimos enquanto seus dados, como preferências, podem ser usados. Essas informações podem ser usadas para fins mais específicos, garantindo a proteção de dados. 6ª Atividade - Implementar na linguagem C/C++, a função Hash, as estruturas de dados de suporte necessárias (dicionários), e aplicá-la para o armazenamento de uma coleção de 20 registros a sua escolha contendo as seguintes informações sobre pessoas: CPF, Nome e Endereço. ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 #include <stdio.h> #include <stdlib.h> // constante representa o tamanho da tabela #define M 20 // estrutura Pessoa com nome e uma matrícula typedef struct{ int cpf; char nome[50]; char endereco[50]; }Pessoa; // nossa tabela hash do tipo Pessoa Pessoa tabelaHash[M]; // inicializa nossa tabela com o valor de codigo -1 void inicializarTabela(){ int i; for(i = 0; i < M; i++) tabelaHash[i].cpf = -1; } // função de espalhamento (resto da divisão da chave por M) int gerarCodigoHash(int chave){ return chave % M; } // função para ler e retornar uma pessoa Pessoa lerPessoa(){ Pessoa p; printf("Digite a CPF: "); scanf("%d", &p.cpf); scanf("%*c"); printf("Digite o nome: "); fgets(p.nome, 50, stdin); printf("Digite o endereço: "); fgets(p.endereco, 50, stdin); return p; } // inserir uma pessoa na tabela void inserir(){ Pessoa pes = lerPessoa(); int indice = gerarCodigoHash(pes.cpf); while(tabelaHash[indice].cpf != -1) indice = gerarCodigoHash(indice + 1); tabelaHash[indice] = pes; ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 } Pessoa* buscar(int chave){ int indice = gerarCodigoHash(chave); while(tabelaHash[indice].cpf != -1){ if(tabelaHash[indice].cpf == chave) return &tabelaHash[indice]; else indice = gerarCodigoHash(indice + 1); } return NULL; } void imprimir(){ int i; printf("\n------------------------TABELA---------------------------\n"); for(i = 0; i < M; i++){ if(tabelaHash[i].cpf != -1) printf("%2d = %3d %s %s", i,tabelaHash[i].cpf, tabelaHash[i].nome, tabelaHash[i].endereco); else printf("%2d =\n", i); } printf("\n----------------------------------------------------------\n"); } int main() { int op, chave; Pessoa *p; inicializarTabela(); do{ printf("1 - Inserir\n2 - Buscar\n3 - Imprimir\n0 - Sair\n"); scanf("%d", &op); switch(op){ case 0: printf("Saindo...\n"); break; case 1: inserir(); break; case 2: printf("Digite a CPF a ser buscada: "); scanf("%d", &chave); p = buscar(chave); ATIVIDADE AVALIATIVA VIRTUALIZADA CURSO: Engenharia e Ciência da Computação DISCIPLINA: Estrutura de Dados Avançadas ASSINATURA: JEYSON LUCAS DA SILVA MOREIRA NOME: JEYSON LUCAS DA SILVA MOREIRA DATA: 03/10/2022 AIA: A1 TURMA INF8260_22 MATRÍCULA 20111101214 if(p) printf("\n\tCPF: %d \tNome: %s Endereço: %s \n", p->cpf, p->nome,p- >endereco); else printf("\nCPF nao encontrado!\n"); break; case 3: imprimir(); break; default: printf("Opcao invalida!\n"); } }while(op != 0); return 0; }
Compartilhar