Baixe o app para aproveitar ainda mais
Prévia do material em texto
Cursos de Computação Disciplina: Estrutura de Dados Rio de Janeiro Novembro de 2021 UNIVERSIDADE VEIGA DE ALMEIDA Estrutura de Dados. Texto apresentado como pré-requisito da disciplina Estrurura de Dados dos Cursos de Computação da Universidade Veiga de Almeida. Professor Dr. Engo. Carlos A. Sicsú A. do Nascimento. Rio de Janeiro Novembro de 2021 SUMÁRIO Introdução 4 1 Atividade Individual Avaliativa para a Prova A2 5 1.1 Problema 1 5 1.2 Problema 1 11 1.3 Problema 1 16 1.4 Problema 1 23 2 Conclusão 25 2.1 Conclusões e Considerações Finais 25 3 Bibliografia 26 INTRODUÇÃO Através desse trabalho, será desenvolvido a solução para os problemas propostos na A2 de Estrutura de Dados. Foi pedido para ser feito uma pilha dinâmica para empilhar e desempilhar dados de clientes de uma empresa de companhia elétrica. No segundo problema, usando os mesmos tipos de dados, é pedido para desenvolver uma lista simplesmente encadeada para inclusão, remoção, listagem, uma opção para pecorrer os elementos que estão na lista e por último uma função para inserir um novo elemento no meio da lista. O problema 3 pede uma lista duplamente encadeada, contendo as mesmas funções que o problema anterior, contudo, por ser uma lista duplamente encadeada, é possível percorrer a lista nos dois sentidos. Ao final foi pedido uma aplicação com uma função iterativa, uma função de Fibonacci que foi montada utilizando a estrutura de repetição For. 1 – Atividade Avaliativa Individual para a Prova A2. 1.1 Problema 1. (2.5pts). Dada uma estrutura para o armazenamento dos dados de uma conta de luz, conforme descrito a seguir: Dado: Tipo Código do Cliente Inteiro Nome do Cliente Texto de 40 caracteres Consumo (qtd. KWh) Inteiro Preço unitário Real Valor Total Real Data do vencimento (dia, mês e ano) Inteiros Crie uma aplicação de Pilha dinâmica, com inclusão, remoção, e listagem dos elementos da Pilha. Apresente para cada elemento os valores armazenados e os endereços de memória dos elementos e ponteiros. Resposta: Programa: #include <stdio.h> #include <stdlib.h> #include <locale.h> #include <string.h> #include <stdbool.h> typedef struct Item { int codigo_cliente, consumo, dia_venc, mes_venc, ano_venc; char nome[40]; float preco_unitario, valor_total; struct Item *anterior; } Elemento; void Inicializar(Elemento **topo) { *topo = NULL; } bool EstaVazia(Elemento **topo) { if(*topo == NULL) return true; else return false; } void Empilhar(Elemento** topo) { int codigo_cliente, consumo, dia_venc, mes_venc, ano_venc; char nome[40]; float preco_unitario, valor_total; Elemento *novo; novo = (Elemento *) malloc(sizeof(Elemento)); printf("\n---------------------------------\n"); printf("DIGITE O CÓDIGO DO CLIENTE..: "); scanf("%d", &codigo_cliente); printf("DIGITE O NOME DO CLIENTE..: "); scanf("%s", &nome); printf("DIGITE O CONSUMO DO CLIENTE..: "); scanf("%d", &consumo); printf("DIGITE O VALOR UNITÁRIO..: R$ "); scanf("%f", &preco_unitario); valor_total = preco_unitario * (float)consumo; printf("DIGITE O DIA DE VENCIMENTO DA CONTA..: "); scanf("%d", &dia_venc); printf("DIGITE O MÊS DO VENCIMENTO DA CONTA..: "); scanf("%d", &mes_venc); printf("DIGITE O ANO DE VENCIMENTO DA CONTA..: "); scanf("%d", &ano_venc); novo->codigo_cliente = codigo_cliente; novo->consumo = consumo; novo->dia_venc = dia_venc; novo->mes_venc = mes_venc; novo->ano_venc = ano_venc; strcpy(novo->nome, nome); novo->preco_unitario = preco_unitario; novo->valor_total = valor_total; novo->anterior = *topo; *topo = novo; } void Desempilhar(Elemento **topo) { Elemento *antigo; antigo = *topo; if(EstaVazia(topo)) {printf("\n Pilha Vazia!!! \n");} else { *topo = antigo->anterior; free(antigo); } } void MostrarPilha(Elemento *topo) { int i = 0; Elemento *item; printf("\n\n Listando...\n\n"); printf("---------------------------------\n"); if (EstaVazia(&topo)) { printf ("A Pilha esta vazia!!!\n"); } else { item = topo; printf("\nItem Valor Endereco Ativo: %p Endereco Anterior: %p \n", item, item->anterior); while(item != NULL) { i++; printf("[%2d ] CodCliente..: %2d \n", i, item->codigo_cliente); printf("[%2d ] Nome do Cliente..: %s \n", i, item->nome); printf("[%2d ] Consumo..: %.2d KWh \n", i, item->consumo); printf("[%2d ] Valor Unitário..: R$ %.2lf \n", i, item->preco_unitario); printf("[%2d ] Valor Total..: R$ %.2lf \n", i, item->valor_total); printf("[%2d ] Data Vencimento..: %2d/%2d/%2d \n", i, item->dia_venc, item->mes_venc, item->ano_venc); printf("------------------------\n"); item = item->anterior; } } printf("---------------------------------\n\n"); } void Menu() { printf( "\n-- Por favor, digite a sua escolha --\n" " 1 - EMPILHAR ELEMENTO \n" " 2 - DESEMPILHAR \n" " 3 - FINALIZAR \n" "Opção..: "); } int main(){ setlocale(LC_ALL, "Portuguese"); Elemento *topo; Inicializar(&topo); int opcao; Menu(); scanf("%d", &opcao); while (opcao != 3) { switch (opcao) { case 1: Empilhar(&topo); MostrarPilha(topo); break; case 2: printf("\nValor do código cliente a ser desempilhado = %d", topo->codigo_cliente); printf("\nValor do nome a ser desempilhado = %s", topo->nome); printf("\nValor do consumo a ser desempilhado = %d", topo->consumo); printf("\nValor do valor unitário a desempilhado = %.2lf", topo->preco_unitario); printf("\nValor do valor total a ser desempilhado = %.2lf", topo->valor_total); printf("\nValor da data de vencimento a ser desempilhada = %d/%d/%d", topo->dia_venc, topo->mes_venc, topo->ano_venc); Desempilhar(&topo); MostrarPilha(topo); break; default: printf(" Escolha inválida!!!\n\n"); break; } Menu(); scanf("%d", &opcao); } return 0; } Testes realizados com as capturas das telas: 1.2 Problema 2. (2.5pts). Dada uma estrutura para o armazenamento dos dados de uma conta de luz, conforme descrito a seguir: Dado: Tipo Código do Cliente Inteiro Nome do Cliente Texto de 40 caracteres Consumo (qtd. KWh) Inteiro Preço unitário Real Valor Total Real Data do vencimento (dia, mês e ano) Inteiros · Crie uma aplicação de Lista Simplesmente Encadeada, com inclusão, remoção, listagem dos elementos e uma opção de percorrer os elementos da lista. Apresente para cada elemento os valores armazenados e os endereços de memória dos elementos e ponteiros. · Inclua uma função para inserir um novo elemento no meio da lista ao percorrer a lista. Resposta: Programa: #include <stdio.h> #include <stdlib.h> #include <locale.h> typedef struct Elemento_Fila { int codigo_cliente; char nome_cliente[40]; int consumo; float preco_unitario; float valor_total; int dia_vencimento; int mes_vencimento; int ano_vencimento; struct Elemento_Fila *proximo; } Elemento_Fila; typedef struct Fila { struct Elemento_Fila *inicio; struct Elemento_Fila *fim; } Fila; int escolha; Fila *criar_fila() { Fila *fila = (Fila *) malloc(sizeof(Fila)); if (!fila) exit(1); else { fila->inicio = NULL; fila->fim = NULL; } return fila; } int fila_vazia(Fila *fila) { if (fila == NULL) return 1; if (fila->inicio == NULL) return 1; else return 0; } struct Elemento_Fila *ler_valor() { Elemento_Fila *cliente = (Elemento_Fila *) malloc(sizeof(Elemento_Fila));printf("\nDigite os dados do cliente:\n"); printf("Codigo: "); scanf("%i", &cliente->codigo_cliente); printf("Nome: "); scanf("%s", &cliente->nome_cliente); printf("Consumo: "); scanf("%i", &cliente->consumo); printf("Preco unitario: "); scanf("%f", &cliente->preco_unitario); printf("Ano vencimento: "); scanf("%i", &cliente->ano_vencimento); printf("Mes vencimento: "); scanf("%i", &cliente->mes_vencimento); printf("Dia vencimento: "); scanf("%i", &cliente->dia_vencimento); return cliente; } struct Elemento_Fila *alocar(struct Elemento_Fila *value) { void *pint = malloc(sizeof(Elemento_Fila)); if (!value) { exit(1); } else { value->proximo = NULL; } free(pint); return value; } void enfileirar(Fila *fila) { Elemento_Fila *no_fila = alocar(ler_valor()); if (!no_fila) exit(1); if (fila->inicio == NULL) fila->inicio = no_fila; else fila->fim->proximo = no_fila; fila->fim = no_fila; } int desenfileirar(Fila *fila) { if (fila_vazia(fila)) return 0; Elemento_Fila *no_fila = fila->inicio; fila->inicio = fila->inicio->proximo; if (fila->inicio == NULL) fila->fim = NULL; free(no_fila); return 1; } void exibir_fila(Fila *fila) { if (fila_vazia(fila)) { printf("Fila vazia\n"); printf("\n Fila endereco inicio %p: ", fila->inicio); printf("\n Fila endereco fim %p: ", fila->fim); return; } Elemento_Fila *aux = fila->inicio; printf("Fila atual\n"); printf("\n Fila - endereco inicio %p: ", fila->inicio); printf("\n Fila - endereco fim %p: ", fila->fim); printf("\n"); while (aux != NULL) { printf("\nCodigo cliente: %d \n", aux->codigo_cliente); printf("Nome cliente: %s \n", aux->nome_cliente); printf("Consumo cliente: %d \n", aux->consumo); printf("Preco unitario: %.2f \n", aux->preco_unitario); aux->valor_total = aux->consumo * aux->preco_unitario; printf("Valor total: %.2f \n", aux->valor_total); printf("Data vencimento: %d/%d/%d", aux->dia_vencimento, aux->mes_vencimento, aux->ano_vencimento); printf("\n==================================================="); aux = aux->proximo; } printf("\n"); } void opcoes(int escolha, Fila *fila) { switch (escolha) { case 1: enfileirar(fila); exibir_fila(fila); break; case 2: desenfileirar(fila); exibir_fila(fila); break; default: if (escolha != 0) printf(" Opcao Invalida\n"); } } int menu() { printf("\n Opções da fila: \n"); printf("\n0 - Sair \n"); printf("1 - Inserir na Fila \n"); printf("2 - Sair da Fila \n"); printf("\n Escolha: \n"); scanf("%i", &escolha); return escolha; } int main() { setlocale(LC_ALL, "Portuguese"); Fila *fila = criar_fila(); exibir_fila(fila); do { escolha = menu(); opcoes(escolha, fila); } while (escolha); return 0; } Testes realizados com as capturas das telas: 1.3 Problema 3. (3.0pts). Dada uma estrutura para o armazenamento dos dados de uma conta de luz, conforme descrito a seguir: Dado: Tipo Código do Cliente Inteiro Nome do Cliente Texto de 40 caracteres Consumo (qtd. KWh) Inteiro Preço unitário Real Valor Total Real Data do vencimento (dia, mês e ano) Inteiros · Crie uma aplicação de Lista Duplamente Encadeada, com inclusão, remoção, listagem dos elementos e uma opção de percorrer os elementos da lista nos dois sentidos. Apresente para cada elemento os valores armazenados e os endereços de memória dos elementos e ponteiros. · Inclua uma função para inserir um novo elemento no meio da lista ao percorrer a lista. Resposta: Programa: #include <stdio.h> #include <stdlib.h> #include <locale.h> typedef struct Elementos_Fila{ int codigo; char Nome [40]; int consumo; float precoU; float valorT; int dataD; int dataM; int dataA; int valor; struct Elementos_Fila *proximo; struct Elementos_Fila *anterior; }Elementos_Fila; typedef struct Fila{ struct Elementos_Fila *inicio; struct Elementos_Fila *fim; }Fila; int escolha; void Exibir_Elementos(Elementos_Fila *aux){ printf("\n"); printf("Endereco atual: %p ", aux); printf("Endereco anterior: %p ", aux->anterior); printf("valor: %i ", aux->valor); printf("Endereco proximo: %p", aux->proximo); } Fila* Criar_Fila(){ Fila *f = (Fila*) malloc(sizeof(Fila)); if(!f) exit(1); else{ f->inicio=NULL; f->fim=NULL; } return f; } int Fila_Vazia(Fila *f){ if(f==NULL) return 1; if(f->inicio==NULL) return 1; else return 0; } struct Elementos_Fila *ler_valor(){ Elementos_Fila *cliente = (Elementos_Fila *) malloc(sizeof(Elementos_Fila)); printf("\n Digite as informacoes do cliente:\n"); printf("Codigo:"); scanf("%i", &cliente->codigo); printf("Nome:"); scanf("%s", &cliente->Nome); printf("Consumo:"); scanf("%i", &cliente->consumo); printf("Preco U.:"); scanf("%f", &cliente->precoU); printf("Dia do vencimento:"); scanf("%i", &cliente->dataD); printf("Mes do vencimento:"); scanf("%i", &cliente->dataM); printf("Ano do vencimento:"); scanf("%i", &cliente->dataA); return cliente; } struct Elementos_Fila *alocar(struct Elementos_Fila *value, struct Elementos_Fila *ant) { void *pint = malloc(sizeof(Elementos_Fila)); if (!value) { exit(1); } else { value->proximo = NULL; value->anterior = ant; } free(pint); return value; } void Enfileirar(Fila *f){ Elementos_Fila *no_fila = alocar(ler_valor(), f->fim); if(!no_fila) exit(1); if(f->fim == NULL) f->inicio = no_fila; else f->fim->proximo = no_fila; f->fim = no_fila; } int Desenfileirar(Fila *f){ if (Fila_Vazia(f)) return 0; Elementos_Fila *no_fila = f->inicio; printf("Elemento retirado:"); Exibir_Elementos(no_fila); f->inicio = f->inicio->proximo; if(f->inicio==NULL) f->fim = NULL; else f->inicio->anterior = NULL; free(no_fila); return 1; } void Exibir_Fila(Fila *f){ if(Fila_Vazia(f)){ printf("Fila Vazia!\n"); printf("\n Fila Endereco Inicial %p: ", f->inicio); printf("\n Fila Endereco Final %p: ", f->fim); return; } Elementos_Fila *aux = f->inicio; printf("\n Fila Atual: "); printf("\n Fila Endereco Inicio %p: ", f->inicio); printf("\n Fila Endereco Final %p: ", f->fim); printf("\n"); while(aux != NULL){ printf("\nCodigo: %d\n", aux->codigo); printf("\nNome: %s \n", aux->Nome); printf("\nConsumo: %d \n", aux->consumo); printf("\nPreco Unitario: %2.f \n", aux->precoU); aux->valorT = aux->consumo * aux->precoU; printf("Valor total: %.2f \n", aux->valorT); printf("Data de vencimento: %d/%d/%d", aux->dataD, aux->dataM, aux->dataA); printf("\n=============================================================="); aux = aux->proximo; } printf("\n"); } void Percorrer_Fila(Fila *f){ int opcao, continua=-1; if(Fila_Vazia(f)){ printf("\nFila Vazia"); return ; } Elementos_Fila *elemento = f->inicio; printf("\n Primeiro Elemento da Fila:"); Exibir_Elementos(elemento); do{ printf("\n Percorrer Fila; \n"); printf(" 0 Sair; \n"); printf(" 1 Proximo; \n"); printf(" 2 Anteriro; \n"); scanf("%d", &opcao); switch(opcao){ case 0: continua=0; break; case 1: if(elemento->proximo != NULL){ elemento = elemento->proximo; Exibir_Elementos(elemento); } else { printf("\nFim da fila!\n"); } break; case 2: if(elemento->anterior != NULL){ elemento = elemento->anterior; Exibir_Elementos(elemento); } else { printf("\nInicio da fila!\n"); } break; default: printf("\n Opção Invalida! \n"); } }while(continua); } void opcoes(int escolha, Fila *f){ int d; switch(escolha){ case 1: Enfileirar(f); Exibir_Fila(f); break; case 2: d = Desenfileirar(f); if(d==1) Exibir_Fila(f); else printf("\n Fila Vazia! \n"); break; case 3: Percorrer_Fila(f);break; default: if(escolha != 0) printf("\nOpção Inválida!\n"); } } int menu(){ printf("\n Opções da Fila;\n"); printf(" 0 Sair; \n"); printf(" 1 Inserir na Fila; \n"); printf(" 2 Remover da Fila; \n"); printf(" 3 Percorrer a Fila; \n"); printf("\n Escolha: "); scanf("%i", &escolha); return escolha; } int main (void){ setlocale(LC_ALL, "Portuguese"); Fila *f = Criar_Fila(); do{ escolha = menu(); opcoes(escolha,f); }while(escolha); return 0; } Testes realizados com as capturas das telas: 1.4 Problema 4. (1.0pt). Faça uma aplicação em linguagem com uma função iterativa (utilizando a repetição for) para determinar o valor de um determinado elemento da série de Fibonacci. A função de Fibonacci é definida assim: F(0) = 0, F(1) = 1 e F(n) = F(n-1) + F(n-2) para n > 1. Resposta: Programa: #include <stdio.h> #include <stdlib.h> #include <locale.h> void fibo(int valor){ int a=0, b=1, val, i; for(i=0; i<valor; i++){ val = a+b; a = b; b = val; } printf("%d\n", abs(a)); } int main(void){ setlocale(LC_ALL, "Portuguese"); printf("\nValor na posição %d da sequência de fibonacci: ", 0); fibo(0); printf("---------\n"); printf("Valor na posição %d da sequência de fibonacci: ", 1); fibo(1); printf("---------\n"); printf("Valor na posição %d da sequência de fibonacci: ", 10); fibo(10); printf("---------\n"); printf("Valor na posição %d da sequência de fibonacci: ", 20); fibo(20); printf("---------\n"); printf("Valor na posição %d da sequência de fibonacci: ", 30); fibo(30); } Testes realizados com as capturas das telas: 2 – Conclusão. 2.1 Conclusões e Considerações Finais. Através deste trabalho, tivemos a oportunidade de exercitar mais nosso conhecimento sobre a linguagem C e aprender mais sobre ela. Com as práticas ensinadas durante as aulas de Estrutura de Dados desenvolvemos os problemas propostos na atividade e obtivemos um bom resultado. Tivemos dificuldades ao longo do trajeto, mas através da pesquisa conseguimos sanar as dúvidas e finalizar da melhor maneira. Agradeço ao professor pelo aprendizado passado, pretendemos aprimorar o conhecimento. 3 - Bibliografia. · http://www.cprogrammingnotes.com/question/dynamic-stack.html (Acesso em 21 de Novembro de 2021) · https://steemit.com/utopian-io/@luisrod/dynamic-stacks-using-c-language (Acesso em 19 de Novembro de 2021) · https://icarus.cs.weber.edu/~dab/cs1410/textbook/7.Arrays/dynamic_stack.html (Acesso em 21 de Novembro de 2021) · https://algorithms.tutorialhorizon.com/double-threaded-binary-tree-complete-implementation/ (Acesso em 24 de Novembro de 2021) · https://iq.opengenus.org/threaded-binary-tree/ (Acesso em 24 de Novembro de 2021) · https://www.geeksforgeeks.org/double-threaded-binary-search-tree/ (Acesso em 25 de Novembro de 2021) · https://br.ccm.net/faq/10263-listas-simplesmente-encadeadas (Acesso em 1 de Dezembro de 2021) · https://www.ime.usp.br/~pf/algoritmos/aulas/lista.html (Acesso em 2 de Dezembro de 2021) · https://www.vivaolinux.com.br/script/Lista-Simplesmente-Encadeada (Acesso em 2 de Dezembro de 2021) · https://wagnergaspar.com/comparando-o-algoritmo-de-fibonacci-recursivo-e-iterativo-tempo-de-execucao/ (Acesso em 25 de Novembro de 2021). · https://medium.com/@marcellguilherme/fibonacci-9aded34b2fb6 (Acesso em 26 de Novembro de 2021). · http://dan-scientia.blogspot.com/2009/08/funcoes-recursivas-e-funcoes-iterativas.html (Acessado em 26 de Novembro de 2021). · Aprendizado e notas feito durante as aulas de Estrutura de Dados.
Compartilhar