Estruturas de Dados I (TCC-00.294)

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

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): terças de 9:00 às 11:00h e de 14:00 às 16:00h, e quintas de 7:00 às 11:00h.

Aulas ministradas

• 30/08/16

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

• 01/09/16

  • Introdução a linguagem C: tipos e variáveis;
  • Operadores: aritméticos, de incremento, de decremento, relacionais, lógicos e bit a bit; e
  • Precedência de operadores.
  • Datas das provas:
    • P1: 08/11/16
    • P2: 20/12/16
    • VR: 03/01/17
    • VS: 17/01/17
    
    

• 06/09/16

  • Entrada e saída básicas (scanf e printf);
  • Decisões com if;
  • Repetições com while, for e do-while;
  • break e continue;
  • Seleção com switch-case-default;
  • Exemplos ministrados em sala de aula: calculadora "infinita" e informar se um número lido é primo; e
  • Exercícios.
    

• 08/09/16

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

• 13/09/16

  • 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;
  • Cadeia de caracteres;
  • Leitura e escrita de cadeia de caracteres;
  • Exemplo de aplicação: escrita das funções strlen e strcmp da biblioteca string.h; e
  • Exercícios.
    

• 15/09/16

  • Escrita das funções strcat e strcpy da biblioteca string.h;
  • 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; e
  • Exercícios.
    

• 20/09/16

  • Tipo estrutura;
  • Variáveis do tipo estrutura e ponteiros para estrutura;
  • 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; e
  • 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 e (c) impressão de uma lista.
    

• 22/09/16

  • Versões (iterativa e recursiva) de inserção de um elemento em uma lista previamente ordenada, mantendo a ordenação, de liberação da lista, e de remoção da primeira ocorrência de um elemento da lista;
  • Exemplos desenvolvidos em sala: versões (iterativa e recursiva) de ordenação de uma lista passada como parâmetro, e três implementações de retirada de todos os elementos repetidos em uma lista (duas versões iterativa e recursiva, usando as funções da biblioteca de lista, e uma abordagem iterativa, sem utilizar as funções da referida biblioteca); e
  • Exercícios.
    

• 27/09/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 pelo token, (e) impressão da lista, (f) liberação da lista e (g) 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
  • Versões iterativas das operações básicas: (a) remoção da primeira ocorrência de um elemento da lista, (b) inserção de um elemento no início da lista e (c) inserção de um elemento na lista ordenada.
    

• 29/09/16

  • Exercícios de lista desenvolvidos em sala de aula: (a) versões (iterativa e recursiva) da inserção do elemento y antes e após cada ocorrência do elemento x (ambos x e y passados como parâmetros de entrada), e (b) inversão da lista, sem poder alterar o ponteiro que indica o início da lista.
    

• 04/10/16

  • Motivação para o uso de pilhas;
  • Exemplos de uso: cópia e ordenação de uma pilha. Na última operação, foram feitas duas versões, void ordena (TPilha* p) e TPilha* ordena (TPilha* p), onde era possível modificar e onde não era permitido alterar a pilha passada como parâmetro de entrada, respectivamente;
  • 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; e
  • Mais um exemplo de uso: simulação de uma calculadora "infinita" com notação pós-fixada, como os modelos HP (Hewlett-Packard).
    

• 06/10/16

  • Motivação para o uso de filas;
  • Exemplos de uso: separação de elementos pares e ímpares em suas respectivas filas e 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.
    

• 11/10/16

  • Motivação para o uso de árvores (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 e (c) 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).
    

• 13/10/16

  • Motivação para o uso de árvores binárias de busca (ABB);
  • Implementação de árvores binárias de busca;
  • Operações básicas (que diferem de árvore binária original): busca, retirada e inserção de um elemento; e
  • Exemplo: construção de uma ABB a partir de um vetor ordenado de maneira crescente.
    

• 18/10/16 (não houve aula: Semana Acadêmica)

• 20/10/16 (não houve aula: Semana Acadêmica)

• 25/10/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.
    

• 27/10/16

  • Código da árvore binária de busca AVL;
  • 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; e
  • Exercícios.
    

• 01/11/16

  • Grafos e dígrafos: apresentação de conceitos;
  • Representação por meio de matrizes de adjacências; e
  • Representação de grafos por meio de listas encadeadas.
  • Trabalho computacional: simulação de uma árvore de diretórios que funcione PERFEITAMENTE no Linux, usando árvores n-árias e ponteiros para void.
    • Operações obrigatórias (em arquivos e em diretórios): inserir, destruir, buscar, renomear, mover e transformar de um tipo para outro.
    • Informações relevantes que devem ser armazenadas em diretórios: nome, número de arquivos e diretórios que ele contem, e data da criação e da última modificação, contendo dia e hora.
    • Dados importantes que devem ser armazenados em arquivos: nome, tipo de arquivo (ou binário, ou texto), e data da criação e da última modificação, contendo dia e hora.
    • Exemplo de arquivo de entrada. Independente do tipo de informação (isto é, se é ou diretório (D), ou um arquivo texto (T), ou um arquivo binário (B)), os campos existentes no arquivo são os seguintes (todos separados por /): nome do arquivo ou diretório, pai, tamanho - SOMENTE PARA ARQUIVOS, data e hora da criação.
    • Grupo de no mínimo dois e de no máximo três discentes.
    • Data de entrega: 02/01/17 à 23:59h.
    • Dias de apresentação: a definir.
    
    

• 03/11/16

  • Representação de grafos por meio de listas encadeadas;
  • Operações em grafos: (a) inicialização, (b) impressão e (c) liberação da estrutura;
  • Operações de busca, inserção e retirada, realizadas em nós e arestas do grafo;
  • Representação por meio de matrizes de adjacências; e
  • Operações em grafos: (a) inicialização, (b) liberação da estrutura e (c) mapeamento para a matriz contida na estrutura de grafo para esta forma de representação.
    

• 08/11/16 (P1 de 11:00 às 14:00h na sala 204)

• 10/11/16

  • Operações de busca, inserção e retirada, realizadas em nós e arestas do grafo, para a representação por meio de matrizes de adjacências; e
  • Exemplos de aplicação: verificar se um grafo está conectado, usando, no máximo, duas arestas.
    

• 15/11/16 (não houve aula: feriado)

• 17/11/16

  • 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.
      
  • OBS: maneira de descobrir data e hora do sistema: uso das constantes __DATE__ e __TIME__ presentes na biblioteca time.h.
    

• 22/11/16 (não houve aula: feriado)

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

• 29/11/16

  • Algoritmos de ordenação: bolha, insertsort e quicksort (juntamente com o procedimento qsort existente na biblioteca stdlib.h).
  • Ordem de apresentação do trabalho computacional:
    • 04/01/17 às 10:30h - G08 (ALEXANDRE SANTIAGO RODRIGUES e PEDRO PAULO BASTOS TEIXEIRA)
    • 04/01/17 às 11:15h - G12 (CAIO MARINHO AMERICO e MATHEUS MORAES DA CRUZ)
    • 04/01/17 às 12:00h - G01 (CARLOS HENRIQUE DOMINGOS CORREIA SANTOS, GABRIELA GOMES DA SILVA e VITOR AUGUSTO BASTOS PINHEIRO)
    • 04/01/17 às 16:00h - G07 (GABRIEL DUARTE RODRIGUES, HENRIQUE PROENCA DICKSON SERRANO e RODRIGO QUEIROZ SOUZA DA CONCEICAO)
    • 05/01/17 às 10:00h - G09 (FELIPE GENU SIMOES, GABRIEL COSTA E SILVA e GABRIEL FIUZA DE ALBUQUERQUE EL HAGE)
    • 05/01/17 às 10:45h - G10 (DOUGLAS ATHOS COELHO, MATHEUS COSTA MAIA PERRUT e VICTOR ASSUMPCAO LEITE COELHO NUNES)
    • 05/01/17 às 11:30h - G11 (FABRICIO MARTINS FARIAS e GUSTAVO ALBINO DOS SANTOS)
    • 05/01/17 às 13:30h - G02 (MAYKOM VANDERSON DA ROCHA CAMPOS, PHELIPE GONCALVES MARTINS e RENATO LUIZ MOURA DE AZEVEDO)
    • 05/01/17 às 14:15h - G03 (JULIA FIGUEIREDO SIMAO FALCAO, LUIS FELIPE PEREIRA DE FREITAS e RAPHAEL LEARDINI BENDAS ROBERTO)
    • 05/01/17 às 15:00h - G06 (JOAO VITOR MONTEIRO FERNANDES CORREA, LUCAS RAMALHO LUIZ DA SILVA e MATEUS AZEREDO TORRES)
    • 05/01/17 às 15:45h - G14 (JOAO GABRIEL MOUTELLA SANTOS CUNHA e RENATO ARAUJO BASTOS)
    • 06/01/17 às 10:30h - G05 (ALEXANDRE DE FARIA CARDOSO, DANIEL CALLADO PARRILHA DE LIMA e NICHOLAS VASCONCELOS QUINTELLA)
    • 06/01/17 às 11:15h - G13 (ALAN LIRA NUNES e GABRIEL SANTOS DE ARAUJO DO NASCIMENTO)
    • 06/01/17 às 12:00h - G04 (ALEXANDRE PEDROZA MACHADO, JULIA DRUMMOND NOCE e MAURICIO MILANO SANTOS DA SILVA JUNIOR)
      
    
    

• 01/12/16

  • Algoritmo de ordenação mergesort;
  • 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.
    

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

  • Exemplos desenvolvidos em sala: (a) ordenação de uma lista de inteiros quaisquer; (b) função que, dados uma árvore binária de busca e um elemento, retorna uma lista de todos os múltiplos desse elemento, ordenados de maneira crescente, sem usar algoritmos de ordenação; (c) inserções e retiradas em uma AVL; e (d) percorrimentos (pré-ordem, pós-ordem, simétrica e largura) em árvores binárias; e
  • Exercícios.
    

• 08/12/16 (não houve aula)

• 13/12/16 (não houve aula)

• 15/12/16 (não houve aula)

• 20/12/16 (P2 de 11:00 às 14:00h na sala 204)

• 22/12/16 (não houve aula)

• 03/01/17 (VR de 11:00 às 14:00h na sala 204)

• 04, 05 e 06/01/17 (apresentação de trabalho computacional)

• 10/01/17 (revisão de nota da P2 e da VR)

• 12/01/17 (não houve aula)

• 17/01/17 (VS de 11:00 às 14:00h na sala 204)

• 19/01/17 (revisão de nota da VS)

  • Divulgação das notas.