Estruturas de Dados I (TCC-00.294)
horários das aulas: terças e quintas de 11:00 às 13:00h na sala 215
Objetivos
Familiarizar os alunos com as principais estrururas de dados e suas correspondentes abstrações.
Tópicos Abordados
- Listas, pilhas e filas;
- Árvores binárias (e binárias de busca) e árvores balanceadas (AVP e AVL);
- Grafos e dígrafos; e
- Ordenação.
Critério de avaliação
O sistema de avaliação da disciplina consiste na realização de duas provas (P1 e P2) e de um trabalho computacional de grande porte (T).
Sejam as médias M = [(P1 + P2)/2 + T/10], calculada a partir das notas anteriormente citadas, e MF a nota que consta no histórico escolar do discente.
Se T < 4.0, o aluno será reprovado com MF igual ao mínimo entre 3.9 e M.
Se M ≥ 6.0, o aluno será aprovado e MF será igual a M.
Senão, se M < 4.0, o aluno será reprovado com MF igual a M.
Caso contrário, o discente fará uma verificação suplementar (VS), com data e horário pré-estabelecidos, respeitando-se o prazo de, no mínimo, três dias úteis após a divulgação de M. As provas serão realizadas nos horários de aula.
Literatura básica
- W. Celes, R. Cerqueira e J.L. Rangel, Introdução a Estruturas de Dados, Campus.
- T.H. Cormen, C.E. Leiserson e R.L. Rivest, Introduction to algorithms, McGraw-Hill.
- J. Szwarcfiter e L. Markenzon, Estruturas de Dados e Algoritmos, LTC.
- B.W. Kernighan e D.M. Ritchie, C: a linguagem de programação (Padrão ANSI), Campus.
Horários de Monitoria
- Murilo Brugger Stockinger (
murilobs@gmail.com): terças e quintas de 14:00 às 16:00h, e quartas e sextas de 11:00 às 13:00h.
- Vitor Santos Araujo (
vitoraraujo@id.uff.br): segundas de 09:00 às 11:00h, quintas de 14:00 às 16:00h, e sextas de 11:00 às 13:00h e de 14:00 às 16:00h.
Aulas ministradas
21/03/17
- Apresentação do curso: objetivos, tópicos a serem apresentados, critério de avaliação a ser empregado e literatura utilizada.
23/03/17
- Introdução a linguagem C: tipos e variáveis;
- Operadores: aritméticos, de incremento, de decremento, relacionais, lógicos e bit a bit;
- Precedência de operadores; e
- Entrada e saída básicas (scanf e printf).
28/03/17
- Entrada e saída básicas (scanf e printf);
- Decisões com if;
- Repetições com while, for e do-while;
- break;
- Seleção com switch-case-default;
- Exemplos ministrados em sala de aula: calculadora "infinita" e informar "infinitamente" todos os primos menores ou iguais a um número lido; e
- Exercícios.
- Datas das provas:
- P1: 18/05/17
- P2: 27/06/17
- VR: 29/06/17
- VS: 18/07/17
30/03/17 (não houve aula)
04/04/17
- Funções;
- Pilha de execução;
- Ponteiros; e
- Variáveis estáticas.
06/04/2017
- Declaração de vetores;
- Passagem de vetor como parâmetro de entrada de funções;
- Alocação dinâmica de vetores;
- Explicação das funções malloc, realloc e free da biblioteca stdlib.h; e
- Exercícios.
11/04/17
- Cadeia de caracteres;
- Leitura e escrita de cadeia de caracteres;
- Exemplo de aplicação: escrita das funções (nas versões iterativa e recursiva) strcmp, strcat e strcpy da biblioteca string.h;
- Declaração de matrizes; e
- Exercícios.
13/04/17 (não houve aula)
18/04/17
- Passagem de matriz como parâmetro de entrada de funções;
- Alocação dinâmica de matrizes;
- Exercício: escrita da função que gera, ou a matriz triangular inferior, se a matriz passada como parâmetro de entrada é simétrica, ou a matriz transposta, se a matriz de entrada não for simétrica;
- Tipo estrutura;
- Variáveis do tipo estrutura e ponteiros para estrutura; e
- Exercícios.
20/04/17
- Motivação para o uso de listas;
- Definição de listas simplesmente encadeadas;
- Operações básicas: (a) inicialização e (b) inserção de um elemento no início da lista;
- Versões (iterativa e recursiva) de algumas operações básicas: (a) inserção de um elemento no fim da lista, (b) busca de um elemento, (c) impressão de uma lista, (d) inserção de um elemento em uma lista previamente ordenada, mantendo a ordenação, e (e) liberação da lista; e
- Exercícios.
25/04/17
- Versões (iterativa e recursiva) de remoção da primeira ocorrência de um elemento da lista;
- Exemplo desenvolvido em sala: versões (iterativa e recursiva) de ordenação de uma lista passada como parâmetro;
- Motivação para o uso de listas circulares;
- Definição de listas circulares; e
- Operações básicas: (a) inicialização, (b) versões iterativa e recursiva de busca a um elemento, (c) inserção mais barata de um elemento na lista e (d) inserção de um elemento antes do nó apontado pelo token.
27/04/17
- Operações básicas em listas circulares: (a) versões iterativa e recursiva de impressão da lista, (b) liberação da lista e (c) retirada da primeira ocorrência de um elemento da lista;
- Motivação para o uso de listas duplamente encadeadas;
- Definição de listas duplamente encadeadas; e
- Operações básicas de inserção: (a) no início da lista, (b) na lista ordenada e (c) no final da lista.
02/05/17
- Operação de retirada da primeira ocorrência de um elemento em listas duplamente encadeadas;
- Exemplo em sala de aula: retirada de todas as ocorrências de um elemento numa lista (
void rto (TLSE* l, int x));
- Motivação para o uso de pilhas;
- Exemplos de uso: impressão e ordenação de uma pilha. Na última operação, foi feita a versão
void ordena (TPilha* p), onde era necessário alterar a pilha passada como parâmetro de entrada;
- Implementação de pilhas com vetores e listas; e
- Operações básicas: (a) inicialização, (b) retirada de um elemento do topo da pilha - a operação pop, (c) inserção de um elemento no topo da pilha - a operação push, (d) teste se a pilha está vazia e (e) liberação da lista.
04/05/17
- Motivação para o uso de filas;
- Exemplos de uso: impressão de fila;
- Implementação de fila com vetores e listas;
- Operações básicas: (a) inicialização da fila, (b) destruição da fila, (c) inserção de um elemento no fim da fila, (d) retirada do início da fila, e (e) teste se a fila está vazia; e
- Exercícios.
09/05/17
- Motivação para o uso de árvores binárias (AB);
- Implementação de árvores binárias;
- Percurso em árvores binárias: pré-ordem (ou profundidade), simétrica, pós-ordem e largura; e
- Operações básicas: (a) inicialização, (b) busca, (c) libera e (d) diversas formas de impressão: profundidade (versões iterativa, por meio do uso de uma implementação específica de pilha, e recursiva), simétrica, pós-ordem e largura (por meio do uso de uma implementação particular de fila).
11/05/17
- Motivação para o uso de árvores binárias de busca (ABB);
- Implementação de árvores binárias de busca; e
- Operações básicas (que diferem de árvore binária original): busca, retirada e inserção de um elemento.
16/05/17 (exercícios de revisão para a primeira prova)
18/05/17 (P1 de 11:00 às 13:45h na sala 215)
23/05/17
- Comentários sobre a P1;
- Motivação para o uso de árvores binárias AVL;
- Definição de árvores binárias AVL; e
- Operações básicas: (a) altura de uma árvore, (b) rotação a esquerda e (c) rotação a direita.
25/05/17
- Rotações duplas esquerda-direita e direita-esquerda;
- Apresentação, por meio de exemplos, das operações de inserção e retirada em AVL, utilizando, quando necessário, as operações de rotação supracitadas; e
- Código da árvore binária de busca AVL.
30/05/17
- Grafos e dígrafos: apresentação de conceitos;
- Representação de grafos por meio de listas encadeadas; e
- Operações em grafos: (a) inicialização e (b) busca e inserção, realizadas em nós e arestas do grafo.
01/06/17
- Revisão de nota da P1, com a apresentação do gabarito adotado; e
- Trabalho computacional: manipulação em grafos orientados e não-orientados que funcione PERFEITAMENTE no Linux → dado um grafo em um arquivo texto, passado como parâmetro de entrada para o seu programa, verifique:
- se esse grafo é orientado ou não. Se for orientado, informe sua(s) componente(s) fortemente conexa(s). Um grafo orientado é fortemente conexo se para qualquer par
(v,w) de seus vértices existe um caminho de v a w e também um caminho de w para v.
- se esse grafo não for orientado, verifique se ele é conexo. Se for conectado, indique as pontes (ponte é uma aresta cuja a remoção desconecta o grafo) e os pontos de articulação (um ponto de articulação é um vértice de um grafo tal que a remoção desse vértice provoca um aumento no número de componentes conectados) existentes no grafo. Se não for conectado, informe os componentes conexos desse grafo.
- Informações importantes:
- A primeira linha do arquivo de entrada é um valor inteiro que indica o número de nós que o grafo possui. As demais linhas representam as conexões entre os nós (isto é, as arestas).
- Operações obrigatórias (em nós e em arestas) que devem estar disponíveis para os usuários do seu programa: inserir, retirar e buscar.
- Grupo de no mínimo dois e de no máximo três discentes.
- Data de entrega: 18/06/17 à 23:59h.
- Semana de apresentação: 19 a 23/06/17.
06/06/17
- Mais operações em grafos: (a) Operações de retirada, realizadas em nós e arestas do grafo, (b) impressão e (c) liberação da estrutura;
- Definição de arquivo;
- Tipos de arquivos: binários e de texto;
- Funções para manipulação de arquivos em C (biblioteca stdio.h):
- fopen e fclose para abrir e fechar arquivos, respectivamente; e
- fscanf e fprintf para leitura e escrita de informações em arquivos texto, respectivamente.
08/06/17
- Explicação da alteração no enunciado do trabalho.
- Ordem de apresentação do trabalho computacional:
- 19/06/17 - 10:30h → G09 (DANIEL XIN XIN YE, MATHEUS MORGADO CORREA e RODRIGO JUNGER DE CARVALHO)
- 19/06/17 - 11:15h → G11 (BRUNO BITTENCOURT SANTOS e GABRIEL DE ALBUQUERQUE MENDES FERREIRA)
- 19/06/17 - 13:00h → G14 (GABRIEL SANTOS DE ARAUJO DO NASCIMENTO, MATHEUS ERTHAL AMANCIO DA SILVA e VICTOR ASSUMPCAO LEITE COELHO NUNES)
- 19/06/17 - 13:45h → G15 (LUIZ FELIPE MATOS DE MELO, MARLON CRISTO JARDIM e PEDRO RIBEIRO PESSOA)
- 19/06/17 - 14:30h → G03 (CAIO CESAR GUIMARAES COSTA, JOAO GABRIEL MOUTELLA SANTOS CUNHA e RODRIGO CALAFATE CAVOTE)
- 19/06/17 - 16:00h → G18 (DIEGO CARRICO CACAU e VITOR COSTA HARDOIM)
- 20/06/17 - 10:15h → G12 (LUCAS RAMALHO LUIZ DA SILVA e YAGO DE REZENDE DOS SANTOS)
- 21/06/17 - 10:30h → G16 (ALLANA CAPISTRANO DE OLIVEIRA, GUSTAVO MARTINS PIEDADE e LUCAS DE CASTRO PEREIRA)
- 21/06/17 - 11:15h → G07 (GABRIEL HENRIQUE COELHO DA SILVA, LUCIANO FERREIRA PLOUVIER e MATHEUS MORAES DA CRUZ)
- 21/06/17 - 13:00h → G04 (LUAN SIMOES CARDOSO, LUCAS ALEXANDRE SIQUEIRA DOS SANTOS e VINICIUS RAMOS CHAVES NEVES)
- 21/06/17 - 13:45h → G10 (DANIEL DE SOUZA ZAMBRANO BRASIL, GUSTAVO FERREIRA LOPES GONCALVES e MARCOS PAULO DE SOUZA FRANCA)
- 21/06/17 - 14:30h → G02 (ALEXANDRE PEDROZA MACHADO, ANDRE LUIZ LIMA PRATA RODRIGUES e CAIO NOGUEIRA VIVAS)
- 21/06/17 - 15:15h → G06 (DAVI DA SILVA RODRIGUES, JOAO VITOR MONTEIRO FERNANDES CORREA e MAURICIO MILANO SANTOS DA SILVA JUNIOR)
- 21/06/17 - 16:00h → G17 (JOAO PEDRO CARDOSO BASTOS ALVIM, LUIZA MORGADO DE CASTRO ROSA e MATHEUS LOPES CARAPINA DO NASCIMENTO)
- 23/06/17 - 10:30h → G05 (LEONARDO MACHADO DA SILVA, MARCO DE SOUSA MELO e PATRICIA RAPOSO SANTANA LIMA)
- 23/06/17 - 11:15h → G13 (JORGE FELIPE CAMPOS CHAGAS, LUCAS SANTANA BICALHO DA COSTA e RAMON ROCHA REZENDE)
- 23/06/17 - 13:00h → G19 (ALAN LIRA NUNES)
- 23/06/17 - 13:45h → G08 (ALLAN PATRICK DE FREITAS SANTANA e RONALD MACHADO CAMPBELL JUNIOR)
- 23/06/17 - 14:30h → G01 (FELIPE HOLANDA DE SOUZA, GUSTAVO LOPES DE PAULA e MATHEUS BELO DA COSTA)
- 23/06/17 - 15:15h → G20 (GABRIEL HENRIQUE BRANDAO CORREA SILVA e GUSTAVO ALBINO DOS SANTOS)
13/06/2017
- Exemplo de aplicação de árvores n-árias: árvore de diretórios;
- Implementação de árvores n-árias somente com dois ponteiros (um para o primeiro filho e outro para o próximo irmão);
- Operações básicas: (a) criação de um nó, (b) inserção de filhos, (c) busca de um elemento, (d) impressão e (e) liberação;
- Exercício feito em sala de aula: teste se duas árvores n-árias são iguais;
- Algoritmos de ordenação: selectSort, insertsort e quicksort; e
- Exercícios.
15/06/17 (não houve aula)
20/06/17
- Algoritmo de ordenação quickSort: procedimento geral qsort existente na biblioteca stdlib.h;
- Motivação para o aprendizado de heaps binários;
- Propriedades para se ter heaps binários de máximo e de mínimo;
- Operações básicas de heap binário de máximo, incluindo max_heapfy e build_max_heap; e
- Algoritmo de ordenação heapsort.
22/06/17
- Algoritmo de ordenação mergesort; e
- Exercícios de revisão para a P2: (a) inserções e retiradas em AVL, (b) descoberta do maior (menor) elemento numa árvore binária (árvore binária de busca) e (c) construção de uma árvore binária de busca a partir de um vetor ordenado de maneira crescente.
27/06/17 (P2 de 11:00 às 13:45h na sala 206)
29/06/17 (VR de 11:00 às 13:45h na sala 215)
04/07/17 (não haverá aula)
06/07/17 (revisão de nota da P2 e da VR)
18/07/17 (VS de 11:00 às 13:45h na sala 215)
20/07/17 (revisão de nota da VS e publição das notas finais.)