Prova Estrutura de Dados 1 - Listas Duplamente Encadeadas 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 25112023 A2 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 29112023 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 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 Faça um programa que a 10 ponto Cadastre o nome e o salário de 6 funcionários em uma lista duplamente encadeada e ordenada pelo salário de forma decrescente b 10 ponto Tenha uma função que mostre o nome valor do imposto e o valor a receber ou seja o salário menos o imposto de todos os funcionários cadastrados c 10 ponto Tenha uma função que deve mostrar os nomes e os salários dos funcionários cujos nomes comecem com uma letra digitada pelo usuário pode ser maiúscula ou minúscula Se nenhum funcionário tem o nome começado com a letra digitada pelo usuário mostrar mensagem Nenhum funcionário com esta letra d 10 ponto Tenha uma função que apresente a listagem dos nomes e salários dos funcionários por ordem crescente de salário Obs os percentuais de imposto são Salário até 2700 é isento Salário entre 2700 e 4200 o imposto é 10 do salário Salário acima de 4200 o imposto é 20 do salário 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 Usando as funções definidas em filah implemente um programa que simule o controle de uma pista de decolagem de aviões em um aeroporto Considere que os aviões possuem um nome e um número inteiro com o identificador Adicione outras características conforme achar necessário Neste programa o usuário deve ser capaz de realizar as seguintes tarefas i 05 ponto Listar o número de aviões aguardando na fila de decolagem ii 05 ponto Autorizar a decolagem do primeiro avião da fila iii 05 ponto Adicionar um avião à fila de espera iv 05 ponto Listar todos os aviões na fila de espera v 05 ponto Listar as características do primeiro avião da fila 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 15 ponto Em uma pilha que contenha números inteiros dispostos aleatoriamente construa uma função para determinar o maior e o menor dos números contidos na pilha A pilha deve ser mantida com o mesmo conjunto de dados ao final da função O protótipo desta função é o seguinte void MaiorMenor Tpilha p c 20 pontos Implemente uma função que dada uma pilha de entrada p retorne uma pilha com todos os elementos de p ordenados de maneira crescente Ao final da execução desta função p permanecerá com todos os seus elementos O protótipo desta função é o seguinte TPilha ordena TPilha f