Estruturas de Dados I (TCC-00.294)

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

• Victor Ferreira Teixeira da Silva (victor_ock@hotmail.com e mavericktailsdoll@gmail.com): segundas de 11:00 às 13:00h, quartas e quintas de 16:00 às 18:00h, e sextas de 9:00 às 11:00h.

Aulas ministradas

• 26/04/16

  • 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;
  • Operadores: aritméticos, de incremento, de decremento, relacionais e lógicos; e
  • Precedência de operadores.
    

• 28/04/16

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

• 03/05/16

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

• 05/05/16

  • Declaração de vetores;
  • Passagem de vetor como parâmetro de entrada de funções;
  • Alocação dinâmica de vetores;
  • Cadeia de caracteres;
  • Leitura e escrita de cadeia de caracteres;
  • Exemplo de aplicação: escrita das funções strcat e strcmp da biblioteca string.h; e
  • Exercícios.
  • OBS: definidas as datas das provas:
    • P1: 02/06/16
    • P2: 19/07/16
    • VR: 21/07/16
    • VS: 02/08/16
      
    
    

• 10/05/16

  • Declaração de matrizes;
  • 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 triangular inferior ou 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
  • Exercícios.
    

• 12/05/16

  • 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, (c) busca de um elemento, (d) inserção de um elemento na lista ordenada e (e) impressão de uma lista.
    

• 17/05/16

  • Versões (iterativa e recursiva) de remoção 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
  • Versões iterativas e recursivas das operações básicas: (a) remoção da primeira ocorrência de um elemento da lista, (b) inserção de um elemento no fim da lista e (c) inserção de um elemento na lista ordenada.
    

• 19/05/16

  • 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) inserção mais barata de um elemento na lista, (d) inserção de um elemento antes do nó apontado por token, (e) impressão da lista, (f) liberação da lista e (g) retirada de uma ocorrência de um elemento da lista;
  • Motivação para o uso de pilhas;
  • Exemplos de uso: ordenação de uma pilha; e
  • Exercícios.
    

• 24/05/16

  • Implementação de pilhas com vetores e listas;
  • 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;
  • 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; e
  • Exercícios.
    

• 26/05/16 (não houve aula devido ao feriado de Corpus Christi)

• 31/05/16

  • Exercícios para a primeira prova: versões iterativa e recursiva de ordenação na própria lista, inversão de uma lista, retirada de todas as ocorrências de um elemento na lista e deslocamento de elementos em uma lista, de acordo com o valor de um parâmetro de entrada.
    

• 02/06/16 (P1 de 11:00 às 14:00h na sala 217)

• 07/06/16

  • Motivação para o uso de árvores;
  • Implementação de árvores binárias;
  • Percurso em árvores binárias: pré-ordem (ou profundidade), simétrica e pós-ordem; e
  • Operações básicas: (a) inicialização, (b) liberação de árvores binárias, (c) busca e (d) diversas formas de impressão (profundidade, largura, simétrica e pós-ordem).
    

• 09/06/16

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

• 14/06/16 (não houve aula)

• 16/06/16 (revisão de nota da P1, com a apresentação do gabarito adotado)

• 21/06/16

  • 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, das operações de inserção e retirada em AVL, utilizando, quando necessário, as operações de rotação supracitadas.
    

• 23/06/16

  • Código da árvore binária de busca AVL;
  • Grafos e dígrafos: apresentação de conceitos;
  • Representação por meio de matrizes de adjacências;
  • Representação de grafos por meio de listas encadeadas; e
  • Operações em grafos: (a) inicialização, (b) busca de nós e arestas e (c) inserção de nós e arestas.
    

• 28/06/16

  • Mais operações em grafos: retirada de nós e arestas; e
  • AVP: definição da estrutura e implementação da operação de inserção (e da correção das cores após a inserção de um nó vermelho).
  • Trabalho computacional: sistema gerenciador de matrículas de discentes de um curso de graduação hipotético usando AVP.
    • Operações obrigatórias: inserção de aluno (que é uma estrutura composta de matrícula, nome e CR, sendo a matrícula uma informação única), retirada de aluno (dada a matrícula como entrada), atualização de nome, CR e matrícula (que implica na retirada do aluno com a matrícula antiga e a inserção do mesmo aluno com o novo número de identificação).
    • Grupo de no mínimo dois e de no máximo três discentes.
    • Data de entrega: 20/07/16 à 23:59h.
    • Dias de apresentação: 21/07, 22/07 e 25/07.
    
    

• 30/06/16

  • Algoritmos de ordenação: selectsort (em vetores e listas) e quicksort (juntamente com o procedimento qsort existente na biblioteca stdlib.h).
  • Ordem de apresentação do trabalho computacional:
    • 21/07/16 às 15:00h - G03 (GLAUCIO DE OLIVEIRA ALMEIDA, MALKAI OLIVEIRA e PHELIPE GONCALVES MARTINS)
    • 21/07/16 às 15:45h - G04 (CAROLINA ALVES DE OLIVEIRA RANSATTO, GUSTAVO PÉRGOLA BAHIENSE DIAS e HELENA CAMPO MACEIRA BELAY)
    • 21/07/16 às 16:30h - G11 (ALEXANDRE SANTIAGO RODRIGUES, RAFFAEL MURALHA PARANHOS e RAPHAEL LEARDINI BENDAS ROBERTO)
    • 22/07/16 às 10:30h - G06 (FELIPE JOSÉ PERPÉTUO ASSAD, PEDRO PAULO BASTOS TEIXEIRA e THIAGO AUGUSTO SIVIRINO)
    • 22/07/16 às 11:15h - G08 (ALYSSON GERALDO GOMES DA SILVA e ANDRÉ LUIZ PEREIRA DE OLIVEIRA JÚNIOR)
    • 22/07/16 às 13:00h - G01 (ARTHUR BASTOS BRAGA COELHO, ARTHUR MONTEIRO FERRAZ e LEONARDO SCHIMPF MACHADO)
    • 22/07/16 às 13:45h - G07 (FELIPE DE BRITO VIEIRA e JOÃO PEDRO SÁ MEDEIROS)
    • 22/07/16 às 14:30h - G10 (VINÍCIUS MARCH DE CARVALHO ABIABIB e YURI SANTOS MASCARENHAS)
    • 22/07/16 às 15:15h - G09 (LUIZA MORGADO DE CASTRO ROSA e MATHEUS LOPES CARAPINA DO NASCIMENTO)
    • 25/07/16 às 11:00h - G02 (JOÃO GABRIEL QUINTÃO PUGLIESE e JÚLIA FIGUEIREDO SIMÃO FALCÃO)
    • 25/07/16 às 11:45h - G13 (RODRIGO DA SILVA MOURA)
    • 25/07/16 às 13:45h - G14 (LUCAS LOPES DE MORAES PINTO)
    • 25/07/16 às 14:30h - G05 (ERICK SIMAS GRILO, MATHEUS TAVARES PRADO e VITOR SANTOS DE ARAÚJO)
    • 25/07/16 às 15:15h - G12 (MAYKOM VANDERSON DA ROCHA CAMPOS)
      
    
    

• 05/07/16

  • 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;
  • Algoritmo de ordenação heapsort; e
  • Motivação para o uso de árvores n-árias.
    

• 07/07/16

  • 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 (em O(1) e O(n), onde n corresponde ao número de filhos de um nó), (c) busca de um elemento, (d) impressão e (e) liberação;
  • Exercícios desenvolvidos em sala: teste se duas árvores n-árias são iguais e a construção de uma árvore de busca binária balanceada a partir de um vetor ordenado; e
  • Exercícios.
    

• 12/07/16 (dúvidas para a segunda prova)

  • Exemplos desenvolvidos em sala: função que retorna o maior elemento de uma árvore binária e de uma árvore de busca binária, funções básicas de heap binário de mínimo, incluindo min_heapfy e build_min_heap, e função de colorir um grafo, sendo que dois nós vizinhos não podem ter a mesma cor e, exceto para grafos completos, o número de cores não pode ser igual a n, onde n corresponde ao número de nós de um grafo.
    

• 14/07/16 (dúvidas para a segunda prova)

  • Exemplos desenvolvidos em sala: função que verifica se uma árvore binária segue um determinado padrão, função de comparação para ser utilizada no procedimento qsort da stdlib.h e inserções e retiradas em uma AVL.
    

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

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

• 21, 22 e 25/07/16 (apresentação de trabalho computacional)

• 26/07/16 (revisão de nota da P2 e da VR)

• 28/07/16 (não houve aula)

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

• 04/08/16 (revisão de nota da VS)

  • Divulgação das notas revisadas.