Caro estudante, você está participando de um processo de seleção para o cargo de desenvolvedor(a) em uma empresa de biotecnologia, com foco na área da genética. Sendo assim, é muito importante que leia o recorte do contexto abaixo, e acesse o link disponível para melhor compreensão do assunto de DNA.

"O DNA (ácido desoxirribonucleico) é um tipo de ácido nucleico que armazena a informação genética da grande maioria dos seres vivos. Essa molécula é formada por nucleotídeos e apresenta, geralmente, a forma de uma dupla-hélice. As bases nitrogenadas estão classificadas em dois grupos: as pirimidinas e purinas. Citosina (C), timina (T) e uracila (U) são pirimidinas, enquanto a adenina (A) e a guanina (G) são purinas. Das bases nitrogenadas citadas, apenas a uracila não é observada no DNA."

Disponível em https://brasilescola.uol.com.br/biologia/dna.htm

Com base no contexto da genética abordado acima, você deve construir um algoritmo em linguagem C utilizando os conceitos de FILA DINÂMICA e de PILHA DINÂMICA.

Para que este algoritmo funcione de acordo com o contexto apresentado, você deve:

1 - Ler a entrada de DNA com n caracteres compostos por uma sequência de nucleotídeos (A C T G) e armazená-los em uma estrutura de FILA DINÂMICA. 2 - Ao concluir a entrada, você deve remover a sequência da fila para a dupla fita do DNA convertendo a sequência de nucleotídeos (T G A C) e armazená-los em uma estrutura de PILHA DINÂMICA. 3 - Faça a impressão de ambas as estruturas.

Vale ressaltar, que a sequência de nucleotídeos é uma cadeia de caracteres (strings). Leal & Oliveira (2022), em Algoritmos e Lógica de Programação II, ressalta que um tripo string em C é um vetor do tipo char e que ao final da string é armazenado o ‘\0’, por isso é sempre necessário declarar uma string com uma posição a mais do que o número de caracteres que desejamos armazenar.

Oliveira, P. M.; Leal, G. C L. Algoritmos e Lógica de Programação II. Maringá-Pr.: Unicesumar, 2020.

Quanto as estruturas utilizadas na solução do problema, segundo Oliveira & Pereira (2019), a pilha é uma das estruturas mais simples e mais versáteis dentre as utilizadas na computação, onde os dados são inseridos e removidos no seu topo (LIFO – Last In, Firts Out), enquanto as filas, embora sejam também estruturas muito utilizadas, possuem particularidades fazem com seu funcionamento seja um pouco menos simples do que o das pilhas, pois usam o conceito FIFO (First In, First Out), ou seja, o primeiro que entra é o primeiro que sai.

Oliveira, P. M.; Pereira, R. de L. Estrutura de Dados I. Maringá-Pr.: Unicesumar, 2019.

Para solucionar o problema apresentado é fundamental desenvolver as seguintes funções de cada estrutura:

Inserir na fila Excluir da fila Imprimir a fila Inserir na pilha Imprimir a pilha

Exemplo:

Fila: ACTTGACCGTTA Pilha: TAACGGTCAAGT

Cada arquivo dessa aula será referente à uma aula prática, então esse projeto tem por objetivo ser um diário de estudos e não um projeto real.

Para executar a linguagem C no VC, você pode utilizar um compilador fora do editor (o mingw), o que será um tanto trabalhoso, e as extensões do VC para a linguagem C, entretanto, você pode executar facilmente aqui, que é a ferremanta que eu uso, é só se cadastrar e na página principal clicar em Create Repl, depois você pode copiar o código de cada arquivo aqui e colar ali.

OBS: Em C dependendo da ferramenta, não é possível, ou pelo menos ainda não encontrei informações sobre, utilizar acentuações atravéz da configuração UTF-8 para caracteres especiais contidos na lingua portuguesa

Fontes: Universidade Unicesumar e Livro Estruturas de Dados I, Estruturas de Dados II.

Para gerar números aleatório dentro de um array, podemos usar a função rand(); Para que a função rand sempre gere números diferentes, podemos usar o srand, pssando como parâmetro o horário (que sempre será diferente)

Ex:

Nesse exemplo, limitamos os número até o 100, aplicando % 100.

Lendo dados:

Preenchendo dados digitados:

Ex1:

Ex2:

Obs:. A função imprimir só conseguiu alterar o endereço porque recebeu o endereço e não a variável

Retorna o tamnanho em bits

Retorno:

O vetor já é uma ponteiro! OBS:. Cuidado ao guardar informações no vetor sem a alocação da memória, ele até aceita, porém pode ser sobreposto por outros programas

EX:

Quando você quiser descobrir a quantidade de elementos de um vetor:

A função malloc aloca um espaço de memória e retorna um ponteiro do tipo void para o início do espaço de memória alocado.

<ponteiro> = (<cast>*) malloc(<tamanho em bytes>); 
p = (int*) malloc(4);

A função free libera o espaço de memória alocado.

O objetivo desses vetores é usar somente a quantidade de memória que for precisar, aqui ao contrário dos vetores de tamanho fixo, não ficamos limitados ao tamanho.

Como utilizar:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() {
    int tam;
    int *vetor;

    printf ("Escolha o tamanho do vetor: ");
    scanf("%d", &tam);

    vetor = (int *) malloc(sizeof (int)*tam);
    for (int i = 0; i < tam; i++) {
        vetor[i] = pow(2,i);
        printf ("Posicao %d: %d\n", i, vetor[i]);
    }
    system("Pause");
    return(0);
}

O operador sizeof indica a quantidade de armazenamento, em bytes, necessária para armazenar um objeto do tipo do operando.

Como saber o tamanho do vetor?

Pilha ou stack é uma lista linear em que todas as inserções e remoções de elemento só podem ser feitos em uma extremidade chamada topo.As pilhas também são chamadas de estruturas LIFO (Last In First Out) ou seja o último elemento inserido é o primeiro removido.

Push Empilhar | Pop Desempilhar

Estrutura de Dados da Pilha

struct tipo_pilha {
    int dados [tamanho];
    int inicio;
    int topo;
}

Este tipo de estrutura de dados é dita ser FIFO (First in, first out), ou seja, o primeiro elemento a entrar na estrutura é o primeiro a sair. O nome fila, por si só, já é auto-explicativo. Imagine uma fila de banco. A primeira pessoa que chegou na fila, é a que vai ser atendida primeiro.

Estrutura de Dados da Fila

struct tipo_pilha {
    int dados [tamanho];
    int inicio;
    int fim;
}

Primeiro, empilhamos:

No a, você tem algum nó adjacente não visitado? Se sim, empilha, se não desempilha:

Depois Desempilhamos:

Enfileirandoo:

No a, você tem algum nó adjacente não visitado? Se sim, visita, se não desenfilera:

Nó "a" foi desinfileirado e o b é a corrente

No "b", você tem algum nó adjacente não visitado? Se sim, visita, se não desenfilera:

Nó "c" não foi visitado, visita ele e enfilera

No "c", você tem algum nó adjacente não visitado? Se sim, visita, se não desenfilera:

Nó "b" foi desinfileirado

Nó "d" foi desinfileirado

Nó "c" foi desinfileirado

Uma árvore binária é uma estrutura de dados que pode ser representada como uma hierarquia onde cada elemento é chamado de nó. O nó inicial ou o primeiro elemento é chamado de raiz.

Só existe um caminho de um nó ao outro

Definição: Conjunto finito de elementos T = { R, E, D}

• No exemplo acima há três subconjuntos distintos:

• Raiz (R);

• Subárvore binária esquerda (E);

• Subárvore binária direita (D).

• Pode ser vazio, T = 0.

Exemplo:

T.a = { R.a, E.a, D.a }

R.a = {A}

E.a = T.b

D.a = T.c

Nesse exemplo A é pai de B e C, da mesma maneira C e B é filho de A. Um nó sem filho é um nó folha.

Os nós acima são nós ancestrais e abaixo descendente.

Obs: Qual a altura de B?

Árvore estritamente binária: Cada nó possui exatamente 0 ou 2 filhos. Árvore binária completa: Nós com menos de 2 filhos ficam no úlimo ou no penúltimo nível da árvore. Árvore binária cheia: Nós com menos de 2 filhos ficam no último nível da árvore.

n° de nós = (2*folhas) -1

Seguindo o exemplo: Nós = (6 * 2) -1 => Nós = 11.

Árvore binária completa : em uma árvore binária completa todos os níveis, exceto possivelmente o último , está completamente cheia, e todos os nós no último nível são, tanto à esquerda quanto possível. Assim fica claro entender o termo, "tanto à esquerda quanto possível". Caso contrário, os nós vão se sobrepôr.

Obs: Uma árvore binária completa também é uma árvore estritamente binária, porém uma árvore binária não é, necessariamente, uma árvore binária completa!

Estática: Sem registros e com registros; Dinâmicas: Utiliza registros com ponteiros.

• Árvore binária ordenada;
• Árvore balanceada.

Direita

Esquerda

Ex:

Abrindo o "x"

Esquerda

Direita

Ex: