Estruturas de Dados I (TCC-00.171)

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

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

• Bruno Braga (brunobgcardoso@yahoo.com.br): terças e quintas de 14:00 às 18:00h.
• Mateus Rodrigues Alves (mateusra@outlook.com): quintas de 7:00 às 11:00h e sextas de 14:00 às 18:00h.

Aulas ministradas

• 10/03/15

  • Apresentação do curso: objetivos, tópicos a serem apresentados, critério de avaliação a ser empregado e literatura utilizada.
    

• 12/03/15

  • Introdução a linguagem C: tipos e variáveis;
  • Operadores: aritméticos, de incremento, de decremento, relacionais e lógicos; e
  • Precedência de operadores.
    

• 17/03/15

  • 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; e
  • Exemplo da calculadora "infinita".
    

• 19/03/15

  • Funções;
  • Pilha de execução;
  • Ponteiros;
  • Variáveis estáticas; e
  • Lista de exercícios.
    

• 24/03/15

  • Declaração de vetores;
  • Passagem de vetor como parâmetro de entrada de funções; e
  • Alocação dinâmica de vetores.
    

• 26/03/15

  • Cadeia de caracteres;
  • Leitura e escrita de cadeia de caracteres;
  • Exemplo de aplicação: escrita das funções strcpy e strcmp da biblioteca string.h;
  • Declaração de matrizes; e
  • Lista de exercícios.
    

• 31/03/15

  • Passagem de matriz como parâmetro de entrada de funções;
  • Alocação dinâmica de matrizes;
  • Exemplo de aplicação: escrita da função que gera a matriz transposta de uma matriz dinâmica passada como parâmetro de entrada;
  • Tipo estrutura;
  • Variáveis do tipo estrutura e do tipo ponteiro para estrutura; e
  • Lista de exercícios.
    

• 02/04/15 (não houve aula devido ao feriado da Semana Santa)

• 07/04/15

  • Motivação para o uso de listas;
  • Definição de listas;
  • Operações básicas: (a) inicialização e (b) inserção de um elemento no início da lista; e
  • Versões (iterativa e recursiva) de algumas operações básicas: (a) inserção de um elemento no fim da lista, (b) liberação da lista e (c) busca de um elemento.
    

• 09/04/15

  • Versões (iterativa e recursiva) de mais algumas operações básicas: (a) inserção de um elemento na lista ordenada, (b) remoção de um elemento da lista e (c) impressão de uma lista;
  • Exemplo de aplicação: retirar todas as ocorrências de um elemento, exceto a primeira; e
  • Lista de exercícios.
    

• 14/04/15

  • Exemplos iterativos e recursivos desenvolvidos em aula: substituição de todas as ocorrências de um elemento, passado como parâmetro de entrada, por seu antecessor e o seu sucessor; e
  • Exemplo iterativo: merge de duas listas ordenadas, não sendo possível criar ou destruir elementos e, além disso, não existia retorno da função.
    

• 16/04/15

  • Motivação para o uso de listas duplamente encadeadas;
  • Definição de listas duplamente encadeadas;
  • Versões iterativas e recursivas das operações básicas: (a) inserção de um elemento na lista e (b) remoção de um elemento;
  • Motivação para o uso de listas circulares;
  • Definição de listas circulares; e
  • Operações básicas: (a) inicialização, (b) busca de um elemento e (c) inserção mais barata de um elemento na lista.
    

• 21/04/15 (não houve aula devido ao feriado de Tiradentes)

• 23/04/15 (não houve aula devido ao ponto facultativo estabelecido)

• 28/04/15

  • Mais operações básicas de listas circulares: (a) impressão da lista e (b) liberação da lista;
  • Motivação para o uso de pilhas;
  • Exemplos de uso: impressão e ordenação 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.
    

• 30/04/15

  • Motivação para o uso de filas;
  • Exemplo de uso: merge de duas filas ordenadas; e
  • Questão de desafio para definição da data da primeira prova.
    

• 05/05/15

  • 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; e
  • Lista de exercícios.
  • OBS: Datas das provas
    • P1: 19/05/15
    • P2: 07/07/15
    • VR: 09/07/15
    • VS: 16/07/15
      
    
    

• 07/05/15

  • 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; e
  • Percurso em árvores binárias: pré-ordem, simétrica e pós-ordem.
    

• 12/05/15

  • Motivação para o uso de árvores binárias de busca;
  • Implementação de árvores binárias de busca;
  • Operações básicas: busca, retirada e inserção de um elemento; e
  • Questão de desafio de árvores binárias de busca.
    

• 14/05/15 (aula de dúvidas para a P1)

• 19/05/15 (P1 de 11:00 às 14:00h na sala 217)

• 21/05/15

  • Motivação para o uso de árvores binárias AVL;
  • Implementação de árvores binárias AVL;
  • Operações básicas: rotação a esquerda, rotação a direita, rotação dupla esquerda-direita e rotação dupla direita-esquerda; e
  • Apresentação, por meio de exemplos, da operação de inserção em AVL, utilizando, quando necessário, as operações de rotação.
    

• 26/05/15

  • Código da operação de inserção em AVL; e
  • Apresentação, por meio de exemplos, da operação de remoção em AVL, utilizando, quando necessário, as operações de rotação.
    

• 28/05/15

  • Trabalho computacional: codificação usando Código de Huffman (seis pontos) e por meio de grafos orientados (quatro pontos).
    • Grupo de no mínimo dois e de no máximo três discentes.
    • Data de entrega: 07/07/15 à 23:59h.
    • Dias de apresentação: 08/07, 09/07 e 10/07
    • Descrição: dada uma frase de entrada, seu programa deve codificar essa frase usando Código de Huffman (retornando o código gerado, a tabela de conversão e a árvore de codificação) e grafos orientados (nesse caso, a resposta é o grafo gerado).
    
    

• 02/06/15 (revisão de nota da P1)

• 04/06/15 (não houve aula devido ao feriado de Corpus Christi)

• 09/06/15

  • Código da operação de remoção em AVL;
  • Grafos e dígrafos: apresentação de conceitos;
  • Exemplos de aplicação que usam grafos;
  • Representação por meio de matrizes de adjacências; e
  • Representação de grafos por meio de listas encadeadas.
    

• 11/06/15

  • Operações em grafos: (a) inicialização, (b) busca de nós e arestas, (c) inserção de nós e arestas, (d) retirada de arestas (versões iterativa e recursiva); e
  • Lista de exercícios.
    

• 16/06/15

  • Mais operações em grafos: (a) remoção de nós e (b) liberação de grafo alocado dinamicamente;
  • Motivação para o uso de árvores genéricas;
  • Exemplo de aplicação deste tipo de árvore;
  • Implementação de árvores genéricas; e
  • Operações básicas: (a) criação, (b) inserção de filhos e (c) busca de um elemento.
    

• 18/06/15

  • Mais operações básicas de árvores genéricas: (a) impressão e (b) liberação; e
  • Apresentação de um código de AVL.
    

• 23/06/15

  • Algoritmos de ordenação: bolha, insertsort, mergesort e quicksort.
  • Ordem de apresentação do trabalho computacional:
    • 08/07/15 de 11:00 às 12:00h - G06 (Lucas Domingues e Thiago Soares)
    • 08/07/15 de 12:00 às 13:00h - G03 (Arthur, Guilherme e Rodrigo Marins)
    • 08/07/15 de 16:00 às 17:00h - G07 (Eduardo Motta e Yago)
    • 08/07/15 de 17:00 às 18:00h - G14 (Felipe Nacif e Maykom)
    • 08/07/15 de 18:00 às 19:00h - G12 (Adonis e Caroline)
    • 09/07/15 de 15:00 às 16:00h - G10 (Leticia, Rafael Skinner e Victor Ferreira)
    • 09/07/15 de 16:00 às 17:00h - G05 (Augusto e Thiago Cordeiro)
    • 10/07/15 de 15:00 às 16:00h - G11 (Daniel Arena e Rodrigo Lugão)
    • 10/07/15 de 16:00 às 17:00h - G08 (Daniel Carias e Lucas Monteiro)
    • 10/07/15 de 17:00 às 18:00h - G13 (Eduardo Busch, Gabriel e Henrique)
    • 13/07/15 de 10:00 às 11:00h - G01 (Leandro Petito e Vitor Lourenço)
    • 13/07/15 de 11:00 às 12:00h - G04 (Elias, Leandro Silva e Victor Verdan)
    • 13/07/15 de 13:00 às 14:00h - G02 (Felipe Lopes)
    • 13/07/15 de 14:00 às 15:00h - G09 (Ana e Meirylene)
    • 13/07/15 de 15:00 às 16:00h - G15 (Flavio e Vynicius)
      
    
    

• 25/06/15

  • quicksort (juntamente com o procedimento qsort existente na biblioteca stdlib.h);
  • 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.
    

• 30/06/15 (dúvidas para a segunda prova)

• 02/07/15 (dúvidas para a segunda prova)

• 07/07/15 (P2 de 11:00 às 14:00h na sala 217)

• 09/07/15 (VR de 11:00 às 14:00h na sala 217)

• 14/07/15 (revisão de nota da P2 e da VR)

• 16/07/15 (VS de 11:00 às 14:00h na sala 217)

• 21/07/15 (revisão de nota da VS de 11:00 às 14:00h na sala 217)

  • NOTAS FINAIS.