Prova Estrutura de Dados 1 - Lista Duplamente Encadeada e Recursividade em C

ATIVIDADE INDIVIDUAL AVALIATIVA CURSO DISCIPLINA Ciência da Computação Engenharia da Computação Estrutura de Dados 1 ASS NOME Professor Douglas Oliveira DATA Nº de ordem GRAU PROVA TURMA MATRÍCULA 02122023 A3 LEIA ATENTAMENTE ÀS INSTRUÇÕES 1 Forma de entrega Os programas devem ser enviados em um arquivo zip na Área Atividade Avaliativa até o dia 09122023 2 OBS Caso dois ou mais alunos entreguem programas com códigos iguais ou extremamente semelhantes as notas de ambos serão desconsideradas e zeradas 3 Todas as implementações abaixo devem ser feitas usando a linguagem de programação C Questão 1 Avaliação e Aplicação Em uma lista duplamente encadeada cada elemento ou nó é composto normalmente por uma variável que guarda a informação Objeto inteiro cadeia de caracteres etc e dois ponteiros referências a endereços de memória que permitem a ligação entre os vários nós desta lista conforme a figura abaixo A função destas variáveis é guardar o endereço de memória do nó anterior e do nó posterior identificados normalmente como ant e prox Com estas estruturas podemos realizar diversas tarefas que seriam muito dispendiosas com uma lista simplesmente encadeada No modelo mais simples deste tipo de lista ao criar a lista o primeiro nó tem seu ponteiro ant apontando sempre para nulo e o último nó com seu prox apontando para nulo Um determinado professor deseja criar um programa para armazenar as notas dos alunos de suas turmas Basicamente cada aluno possui matrícula e três notas como exemplificado na tabela abaixo Matricula Nota A1 Nota A2 Nota A3 20170123456 100 100 100 20160223456 90 80 70 Considere uma lista duplamente encadeada que armazena os seguintes dados de alunos de uma disciplina Número de Matrícula número inteiro Nota A1 Número de ponto flutuante Nota A2 Número de ponto flutuante Nota A3 Número de ponto flutuante a 15 ponto Escreva uma função recursiva que dada uma lista duplamente encadeada l de alunos inverta os elementos de l em uma outra lista duplamente encadeada de saída Portanto a lista de entrada não pode ser alterada A função deve ser implementada de forma recursiva e o protótipo da função de inversão é o seguinte TLDE inverterecursivo TLDE l b 15 ponto Escreva uma função recursiva em C que receba um vetor de n alunos e construa uma lista duplamente encadeada armazenando os elementos do vetor nos nós da lista garantindo a mesma ordem do vetor Se o vetor não tiver elementos a função retorna uma lista vazia O protótipo da função é dado por TLDE constroirecursivoint n Aluno v Questão 2 As filas são estruturas de dados baseadas no princípio FIFO first in first out em que os elementos que foram inseridos no início são os primeiros a serem removidos Uma fila possui duas funções básicas INSERE que adiciona um elemento ao final da fila e RETIRA que remove o elemento no início da fila A operação RETIRA só pode ser aplicada se a fila não estiver vazia Por exemplo a figura abaixo apresenta como seria o comportamento da fila ao inserir e retirar os elementos 12345 Leve em consideração a existência de um tipo abstrato fila de números inteiros cuja a interface é definida no arquivo filah da seguinte forma typedef struct fila TFila TFila inicializa void TFila insere TFila f int elem int retira TFila f void libera TFila f int vazia TFila f a 10 ponto Usando as funções definidas em filah implemente uma função que receba uma fila f e some todos os valores positivos guardados em f Ao final da execução desta função a fila f permanecerá com todos os seus elementos e retornase a soma O protótipo desta função é o seguinte int somapositivoTFila f b 20 pontos Usando as funções definidas em filah implemente uma função que dada uma fila de entrada f retorne uma fila com todos os elementos de f ordenados de maneira crescente Ao final da execução desta função a fila f permanecerá com todos os seus elementos O protótipo desta função é o seguinte TFila Ordena TFila f c 10 ponto Implemente uma função que crie uma cópia de uma fila passada como parâmetro de entrada A função não deve alterar a fila de entrada e deve ter o seguinte protótipo TFila copia TFila f Questão 3 A pilha é uma estrutura de dados baseada no princípio LIFO LAST in FIRST out na qual os dados que foram inseridos primeiros na pilha serão os últimos a serem removidos Existem duas funções que se aplicam a todas as pilhas PUSH que insere um dado no topo da pilha e POP que remove o item no topo da pilha Por exemplo a figura abaixo apresenta como seria o comportamento da pilha ao realizar PUSH e POP dos elementos 12345 Considere a existência de um tipo abstrato pilha de números inteiros cuja a interface é definida no arquivo pilhah da seguinte forma typedef struct pilha TPilha TPilha inicializa void void push TPilha p int elem int pop TPilha p void libera TPilha p int vazia TPilha p a 10 ponto Usando somente as operações definidas para fila e pilha escreva uma função que dada uma fila f retorne uma pilha contendo todos os elementos de f e obedecendo a ordem de entrada dos inteiros na fila f isto é o primeiro inteiro que sair da fila f deve ser o primeiro inteiro a sair da pilha Não é possível alterar a ordem dos elementos da fila de entrada A função deve obedecer o seguinte protótipo TPilha Fila2Pilha TFila f b 20 pontos Usando somente as operações definidas para fila e pilha escreva uma função que dada uma pilha p retorne uma fila contendo todos os elementos de p e obedecendo a ordem de entrada dos inteiros na pilha p isto é o primeiro inteiro que sair da pilha p deve ser o primeiro inteiro a sair da fila Não é possível alterar a ordem dos elementos da pilha de entrada A função deve obedecer o seguinte protótipo TFila Pilha2Fila TPilha p