Estruturas de Dados I (TCC-00.171)

horários das aulas: terças e quintas de 11:00 às 13:00h na sala 504 (UFASA)

Objetivos

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

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

• Filipe (filipe_santiago@id.uff.br): segundas e quartas de 14:00 às 17:00h, e sextas de 14:00 às 16:00h.
• Matheus (matheusmanzolini@gmail.com): terças e quintas de 14:00 às 18:00h.

Aulas ministradas

• 18/02/14

  • Apresentação do curso: objetivos, tópicos a serem apresentados, critério de avaliação a ser empregado e literatura utilizada.
  • Introdução a linguagem C: tipos e variáveis; e
  • Operadores: aritméticos, de incremento, de decremento, relacionais e lógicos.
    

• 20/02/14 (não houve aula)

• 25/02/14

  • Precedência de operadores;
  • Entrada e saída básicas (scanf e printf);
  • Pilha de execução;
  • Decisões com if;
  • Repetições com while, for e do-while;
  • break;
  • Seleção com switch-case-default; e
  • Exercícios.
    

• 27/02/14

  • Funções;
  • Pilha de execução; e
  • Ponteiros.
    

• 11/03/14

  • Declaração de vetores;
  • Passagem de vetor como parâmetro de entrada de funções;
  • Alocação dinâmica de vetores;
  • Exemplo de aplicação: ordenação dos dados de um vetor;
  • Cadeia de caracteres;
  • Leitura e escrita de cadeia de caracteres;
  • Exemplo de aplicação: escrita da função strcmp da biblioteca string.h; e
  • Exercícios.
    

• 13/03/14

  • Declaração de matrizes;
  • Passagem de matriz como parâmetro de entrada de funções;
  • Alocação dinâmica de matrizes;
  • Tipo estrutura;
  • Variáveis do tipo estrutura e do tipo ponteiro para estrutura;
  • Exercícios;
  • Motivação para o uso de listas;
  • Definição de listas; e
  • Operações básicas: (a) inicialização, (b) inserção de um elemento no início da lista e (c) inserção de um elemento no fim da lista (versões iterativa e recursiva).
    

• 18/03/14

  • Mais operações básicas (versões iterativa e recursiva): (a) inserção ordenada de um elemento na lista, (b) impressão da lista, (c) liberação da lista, (d) busca de um elemento, (e) inserção de um elemento na lista ordenada e (f) remoção de um elemento da lista;
  • Exemplo de aplicação: retirar todas as ocorrências de um elemento, exceto a primeira; e
  • Exercícios.
    

• 20/03/14

  • Exemplos iterativos desenvolvidos em aula, usando arquivos lista.h e lista.c: remoção de todos os elementos repetidos e inserção de antecessores de um elemento passado como parâmetro de entrada; e
  • Exemplo recursivo: merge de duas listas ordenadas.
    

• 25/03/14

  • Motivação para o uso de listas duplamente encadeadas;
  • Definição de listas duplamente encadeadas;
  • Operações básicas: (a) inicialização, (b) impressão reversa da lista, (c) inserção de um elemento na lista e (d) remoção de um elemento; e
  • Exemplo iterativo desenvolvido em aula: inserção de antecessores de um elemento passado como parâmetro de entrada.
    

• 27/03/14

  • Motivação para o uso de listas circulares;
  • Definição de listas circulares;
  • Operações básicas: (a) inicialização, (b) busca de um elemento, (c) impressão da lista, (d) liberação da lista e (e) inserção mais barata de um elemento na lista;
  • Motivação para o uso de pilhas;
  • Exemplos de uso: impressão de uma pilha e cópia de uma pilha.
  • 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.
    

• 01/04/14

  • Motivação para o uso de filas;
  • Implementação de fila com vetores e listas;
  • Operações básicas: (a) inicialização e destruição da fila, (b) inserção de um elemento no fim da fila, (c) retirada do início da fila, e (d) teste se a fila está vazia;
  • Exemplo de aplicação: cópia de uma fila; e
  • Exercícios.
  • OBS: Datas das provas
    • primeira prova: 29/04/14
    • segunda prova: 29/05/14
    • VR: 10/06/14
    • VS: 24/06/14
      
    
    

• 03/04/14

  • Motivação para o uso de árvores;
  • Implementação de árvores binárias;
  • Operações básicas: (a) inicialização, (b) impressão e (c) liberação de árvores binárias;
  • Outras funções: cálculo da altura e teste de igualdade de duas árvoes;
  • Motivação para o uso de árvores binárias de busca;
  • Implementação de árvores binárias de busca;
  • Operações básicas: busca e inserção de um elemento; e
  • Exemplo desenvolvido em sala de aula: gerar uma árvore binária a partir de um vetor ordenado.
    

• 08/04/14

  • Remoção em árvores binárias de busca.
  • Motivação para o uso de árvores AVL e AVP;
  • Implementação de árvores binárias AVL; e
  • Operações básicas: rotação a esquerda, rotação a direita, rotação dupla esquerda-direita e rotação dupla direita-esquerda.
    

• 10/04/14

  • Apresentação, por meio de exemplos, das operações de inserção e de remoção em AVL.
    

• 15/04/14

  • Grafos e dígrafos: apresentação de conceitos, representação por meio de matrizes de adjacências e exemplos de aplicação.
  • Representação de grafos por meio de listas encadeadas; e
  • Operações em grafos: (a) inicialização, (b) destruição de grafos, (c) impressão, (d) busca e (e) inserção de nós e arestas.
    

• 22/04/14

  • Apresentação de um código de AVL; e
  • Exemplos desenvolvidos em sala de aula: (a) encontrar, numa AVL, o antecessor e o sucessor de um elemento passado como parâmetro; (b) testar se uma árvore é AVL; e (c) realizar a impressão em largura de uma árvore.
    

• 24/04/14

  • Dúvidas para a primeira prova.
  • Trabalho computacional: manipulação de grafos não-orientados.
    • Grupo de no mínimo dois e de no máximo três discentes.
    • Semana de entrega: de 02/06/14 a 06/06/14.
    • Descrição: dado um grafo de entrada (que inicialmente é definido em um arquivo texto, cujo nome será informado como argumento para a main), seu programa deve possibilitar as seguintes operações ao usuário:
      1. inserir e retirar nós e arestas;
      2. verificar se o grafo é conexo. Se a resposta for verdadeira, seu programa deve informar, no arquivo pontes.txt, o número de pontes (isto é, uma aresta é considerada uma ponte quando sua remoção desconecta o grafo) que o grafo possui e quais são elas. Se a resposta for falsa, seu programa deve retornar, no arquivo componentes.txt, o número de componentes conexas que o grafo possui e quais são os nós que formam cada componente; e
      3. armazenar no arquivo novo-‹nome do arquivo de entrada› o grafo modificado pelo usuário.
    • Exemplo de arquivo de entrada.
    
    

• 29/04/14 (primeira prova)

• 06/05/14

  • Operações em grafos: remoção de nós e de arestas.
  • Ordem de apresentação do trabalho computacional:
    • 02/06/14 de 11:00 às 12:00h - G07 (Braian e Lucas Barros)
    • 02/06/14 de 12:00 às 13:00h - G02 (Gabriel Saldanha, Igor Martire e Natalia)
    • 02/06/14 de 17:00 às 18:00h - G05 (Bruno Braga, Leonardo Lopes e Matheus Filipe)
    • 03/06/14 de 11:00 às 12:00h - G01 (Matheus Alves, Monique e Pedro Fadel)
    • 03/06/14 de 12:00 às 13:00h - G10 (Fabio Nonato e Luiz Carlos)
    • 03/06/14 de 14:00 às 15:00h - G09 (João Vitor e Omar)
    • 04/06/14 de 11:00 às 12:00h - G15 (Mateus Rodrigues)
    • 04/06/14 de 12:00 às 13:00h - G16 (Igor Palmieri)
    • 05/06/14 de 11:00 às 12:00h - G03 (Leonardo Perazzini, Ralf e Thales Athayde)
    • 05/06/14 de 12:00 às 13:00h - G12 (Beatriz e Gabriel Ribeiro)
    • 05/06/14 de 14:00 às 15:00h - G08 (Cafer, Gabriel Carrara e Romulo Martins)
    • 05/06/14 de 15:00 às 16:00h - G06 (Bernardo e Walace)
    • 05/06/14 de 16:00 às 17:00h - G11 (Daniel, Kelly e José Henrique)
    • 06/06/14 de 11:00 às 12:00h - G14 (Leonardo Brito, Romulo Mourão e Thiago Baltar)
    • 06/06/14 de 12:00 às 13:00h - G13 (Filippo, Gabriel Cardoso e Victor Marcos)
    • 06/06/14 de 14:00 às 15:00h - G04 (Guilherme Macedo, Lucas Jannuzzi e Nicholas)
      
    
    

• 08/05/14

  • Algoritmos de ordenação: bolha, insertsort, mergesort e quicksort (juntamente com o procedimento qsort existente na biblioteca stdlib.h).
    

• 13/05/14

  • Motivação para o aprendizado de heaps;
  • Operações básicas de heaps, incluindo max_heapfy e build_max_heap; e
  • Algoritmo de ordenação heapsort.
    

• 15/05/14

  • Revisão da nota da primeira prova.
    

• 20/05/14

  • Motivação para o uso de Tabelas hash (ou Tabelas de dispersão);
  • Definição de Tabelas hash;
  • Tratamentos de colisão: (a) uso da primeira posição livre e (b) uso de listas lineares;
  • Explicação das operações comuns aos dois tipos de tratamentos de colisão;
  • Definição das operações busca, insere e retira com o tratamento "uso da primeira posição livre"; e
  • Definição da operação busca com o tratamento "uso de listas lineares".
    

• 22/05/14

  • Definição das operações insere e retira com o tratamento "uso de listas lineares";
  • Exercícios em árvores: (a) testar se uma árvore n-ária é uma árvore binária e (b) verificar se uma árvore binária segue os seguintes padrões:
    1. o filho da esquerda é sempre folha; e
    2. os nós com altura par tem dois filhos e os nós de altura ímpar tem somente um filho (se o nó é filho da esquerda, ele possui o filho da esquerda. O mesmo se aplica aos filhos que estão a direita da árvore).
       
  • Exercícios.
    

• 27/05/14 (dúvidas para a segunda prova)

• 29/05/14 (segunda prova)

• 02/06/14 a 06/06/14 (apresentação do trabalho computacional)

• 10/06/14 (VR)

• 24/06/14 (sala 504 da UFASA)

  • Revisão da nota da P2 e da VR de 8:00 às 10:00h; e
  • VS (de 10:00 às 13:00h).
  • OBS: Devido ao fechamento dos prédios da UFF até o dia 24/06/14, a revisão da nota da P2 e da VR será no mesmo dia da VS.
  • NOTAS FINAIS.