plano_de_aula_estruturas_de_dados

Prévia do material em texto

<p>Plano de Aula: Estruturas de Dados - Árvores, Listas, Pilhas e Filas</p><p>Objetivos:</p><p>Compreender as estruturas de dados: Árvores, Listas, Pilhas e Filas.</p><p>Entender suas aplicações e implementações em C.</p><p>Aplicar os conceitos em um exercício prático envolvendo todas as estruturas.</p><p>1. Introdução (5 minutos)</p><p>As estruturas de dados são fundamentais para a organização de informações e otimização de algoritmos.</p><p>Nesta aula, abordaremos as listas, pilhas, filas e árvores, suas implementações e aplicações.</p><p>2. Listas (10 minutos)</p><p>Definição: Estrutura linear que permite inserção, remoção e acesso sequencial de elementos.</p><p>Tipos:</p><p>- Lista Simplesmente Encadeada: Cada nó contém um valor e um ponteiro para o próximo nó.</p><p>- Lista Duplamente Encadeada: Cada nó possui ponteiros para o próximo e o anterior.</p><p>Código Exemplo em C (Lista Simplesmente Encadeada):</p><p>```c</p><p>#include <stdio.h></p><p>#include <stdlib.h></p><p>struct Node {</p><p>int data;</p><p>struct Node* next;</p><p>};</p><p>// Função para inserir um novo nó no início</p><p>void insert(struct Node** head, int newData) {</p><p>struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));</p><p>newNode->data = newData;</p><p>newNode->next = (*head);</p><p>(*head) = newNode;</p><p>}</p><p>// Função para imprimir a lista</p><p>void printList(struct Node* n) {</p><p>while (n != NULL) {</p><p>printf("%d ", n->data);</p><p>n = n->next;</p><p>}</p><p>}</p><p>int main() {</p><p>struct Node* head = NULL;</p><p>insert(&head, 10);</p><p>insert(&head, 20);</p><p>insert(&head, 30);</p><p>printf("Lista: ");</p><p>printList(head);</p><p>return 0;</p><p>}</p><p>```</p><p>3. Pilhas (10 minutos)</p><p>Definição: Estrutura de dados LIFO (Last In, First Out), onde o último elemento a entrar é o primeiro a sair.</p><p>Operações:</p><p>- push: Insere um elemento no topo.</p><p>- pop: Remove o elemento do topo.</p><p>Código Exemplo em C (Pilhas):</p><p>```c</p><p>#include <stdio.h></p><p>#include <stdlib.h></p><p>#define MAX 5</p><p>int stack[MAX], top = -1;</p><p>// Função para adicionar um elemento na pilha</p><p>void push(int value) {</p><p>if (top == MAX - 1)</p><p>printf("Pilha cheia</p><p>");</p><p>else</p><p>stack[++top] = value;</p><p>}</p><p>// Função para remover um elemento da pilha</p><p>int pop() {</p><p>if (top == -1)</p><p>printf("Pilha vazia</p><p>");</p><p>else</p><p>return stack[top--];</p><p>}</p><p>int main() {</p><p>push(10);</p><p>push(20);</p><p>push(30);</p><p>printf("Elemento removido: %d</p><p>", pop());</p><p>return 0;</p><p>}</p><p>```</p><p>4. Filas (10 minutos)</p><p>Definição: Estrutura de dados FIFO (First In, First Out), onde o primeiro elemento a entrar é o primeiro a sair.</p><p>Operações:</p><p>- enqueue: Insere um elemento no final da fila.</p><p>- dequeue: Remove o elemento do início.</p><p>Código Exemplo em C (Fila Simples):</p><p>```c</p><p>#include <stdio.h></p><p>#define MAX 5</p><p>int queue[MAX], front = -1, rear = -1;</p><p>// Função para adicionar um elemento à fila</p><p>void enqueue(int value) {</p><p>if (rear == MAX - 1)</p><p>printf("Fila cheia</p><p>");</p><p>else {</p><p>if (front == -1)</p><p>front = 0;</p><p>queue[++rear] = value;</p><p>}</p><p>}</p><p>// Função para remover um elemento da fila</p><p>int dequeue() {</p><p>if (front == -1 || front > rear) {</p><p>printf("Fila vazia</p><p>");</p><p>return -1;</p><p>} else {</p><p>return queue[front++];</p><p>}</p><p>}</p><p>int main() {</p><p>enqueue(10);</p><p>enqueue(20);</p><p>printf("Elemento removido: %d</p><p>", dequeue());</p><p>return 0;</p><p>}</p><p>```</p><p>5. Árvores (10 minutos)</p><p>Definição: Estrutura hierárquica com nós conectados por arestas, onde cada nó pode ter filhos.</p><p>Tipos de Árvores:</p><p>- Árvore Binária: Cada nó possui no máximo dois filhos (esquerda e direita).</p><p>- Árvore de Busca Binária: Árvores onde o nó à esquerda é menor e o à direita é maior que o nó raiz.</p><p>Código Exemplo em C (Árvore Binária de Busca):</p><p>```c</p><p>#include <stdio.h></p><p>#include <stdlib.h></p><p>struct Node {</p><p>int data;</p><p>struct Node* left;</p><p>struct Node* right;</p><p>};</p><p>// Função para criar um novo nó</p><p>struct Node* newNode(int value) {</p><p>struct Node* node = (struct Node*)malloc(sizeof(struct Node));</p><p>node->data = value;</p><p>node->left = NULL;</p><p>node->right = NULL;</p><p>return node;</p><p>}</p><p>// Função para inserir um nó na árvore binária de busca</p><p>struct Node* insert(struct Node* node, int value) {</p><p>if (node == NULL)</p><p>return newNode(value);</p><p>if (value < node->data)</p><p>node->left = insert(node->left, value);</p><p>else if (value > node->data)</p><p>node->right = insert(node->right, value);</p><p>return node;</p><p>}</p><p>// Função para imprimir a árvore em ordem</p><p>void inorder(struct Node* root) {</p><p>if (root != NULL) {</p><p>inorder(root->left);</p><p>printf("%d ", root->data);</p><p>inorder(root->right);</p><p>}</p><p>}</p><p>int main() {</p><p>struct Node* root = NULL;</p><p>root = insert(root, 50);</p><p>insert(root, 30);</p><p>insert(root, 70);</p><p>insert(root, 20);</p><p>insert(root, 40);</p><p>printf("Inorder traversal: ");</p><p>inorder(root);</p><p>return 0;</p><p>}</p><p>```</p><p>6. Exercício Prático (15 minutos)</p><p>Desafio: Implementar uma função que recebe uma lista encadeada, transfere os elementos para uma pilha e, em seguida, transfere da pilha para uma fila, imprimindo os elementos em ordem de saída.</p><p>7. Encerramento e Discussão (5 minutos)</p><p>Revisão dos conceitos abordados, tirando dúvidas e destacando as principais aplicações de cada estrutura de dados.</p>