Estruturas de Dados I (TCC-00.171)
horário: terças (UFASA: 301) e quintas (UFASA: 401) de 11:00 às 13:00h
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.
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.
- B.W. Kernighan e D.M. Ritchie, C: a linguagem de programação (Padrão ANSI), Editora Campus.
Aulas ministradas
06/03
- Apresentação do curso: objetivos e tópicos abordados.
08/03
- Critério de avaliação;
- Introdução a linguagem C: tipos, variáveis e constantes;
- Operadores: aritméticos, de incremento, de decremento, relacionais e lógicos;
- Precedência de operadores;
- Entrada e saída básicas (scanf e printf);
- Decisões com if;
- Repetições com while e for;
- break;
- Seleção com switch-case-default;
- Exercício em sala: simulação de calculadora; e
- Lista de exercícios.
13/03
- Funções;
- Pilha de execução; e
- Ponteiros.
15/03
- Declaração de vetores;
- Passagem de vetor como parâmetro de entrada de funções;
- Exemplo de aplicação: ordenação de um vetor usando o algoritmo da bolha;
- Alocação dinâmica de vetores;
- Exemplo de aplicação: ordenação dos dados de um vetor em um outro vetor alocado dinamicamente; e
- Exercícios.
20/03
- Cadeia de caracteres;
- Leitura e escrita de cadeia de caracteres;
- Tipo estrutura;
- Variáveis do tipo estrutura e ponteiros para o tipo estrutura; e
- Exercícios.
22/03
- 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, (c) busca de um elemento, (d) impressão da lista, (e) liberação da lista e (f) inserção de um elemento na lista ordenada; e
- Primeiro trabalho computacional com data de entrega em 17/05.
- OBS: Datas das provas
- primeira prova: 08/05
- segunda prova: 03/07
- VS: 10/07
27/03 (não houve aula)
29/03 (não houve aula)
03/04
- Revisão;
- Remoção de um elemento da lista; e
- Exemplos: vários tipos de remoção.
10/04 (Alguns exemplos desenvolvidos no computador)
- OBS: Horários de Monitoria (Lucas Carreiro: lucascp.17@gmail.com)
- segunda-feira: de 14:00h às 18:00h
- terça-feira: de 14:00 às 18:00h
12/04
- Motivação para o uso de listas duplamente encadeadas;
- Definição de listas duplamente encadeadas;
- 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 de um elemento na lista;
- 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 de um elemento na lista.
17/04
- Motivação para o uso de pilhas;
- 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 e (d) teste se a pilha está vazia; e
- Exemplos: impressão de uma pilha, ordenação de uma pilha (em uma pilha de saída diferente da pilha de entrada) e merge de duas pilhas.
19/04
- Motivação para o uso de filas;
- Implementação de filas com vetores e listas;
- Operações básicas: (a) inicialização, (b) retirada do primeiro elemento da fila, (c) inserção de um elemento no fim da fila, e (d) teste se a fila está vazia;
- Exemplo de aplicação: impressão de uma fila; e
- Exercícios.
24/04 (não houve aula)
26/04 (aula de dúvidas no LCC)
03/05
- Motivação para o uso de árvores;
- Implementação de árvores binárias; e
- Operações básicas: (a) inicialização, (b) impresão, e (c) criação de árvores binárias.
08/05 (primeira prova)
10/05
- 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 e inserção de um elemento.
15/05
- Remoção em árvores binárias de busca; e
- Exercícios de árvores.
- OBS: Horários das apresentações:
- 17/05 - 11:00h: G09 (Breno, Thadeu e Victor)
- 17/05 - 12:00h: G12 (Gabriel e Lucas Paim)
- 17/05 - 14:00h: G10 (Alexandre, Ian e Larissa)
- 17/05 - 15:00h: G01 (Manzoli)
- 18/05 - 08:00h: G08 (Luiz Felipe Passos)
- 18/05 - 09:00h: G05 (Daniel e Luiz Felipe Aires)
- 18/05 - 10:00h: G06 (Augusto, Fernando e Luana)
- 18/05 - 11:00h: G02 (Igor, Leandro e Leonardo)
- 18/05 - 12:00h: G03 (Felipe Calçado)
- 18/05 - 12:45h: G13 (Heitor)
- 18/05 - 14:00h: G04 (Carlos e Lucas Vaccari)
- 18/05 - 15:00h: G07 (Marcelo e Vinicius)
- 18/05 - 16:00h: G11 (Gisele, Jorge e Roberto)
17/05 (apresentação do primeiro trabalho)
18/05 (apresentação do primeiro trabalho)
22/05
- Motivação para o uso de árvores AVP;
- Implementação de árvores AVP;
- Apresentação de algumas operações básicas; e
- Segundo trabalho computacional com data de entrega em 21/06.
24/05
- Apresentação de mais algumas operações básicas: inserção, correção da inserção e rotações a esquerda e a direita.
- OBS: Data da VR: 26/06
29/05 (revisão da nota da primeira prova)
- OBS: Horários disponíveis:
- 04/06 - de 10:00h às 10:30h
- 04/06 - de 10:30h às 11:00h
- 04/06 - de 11:00h às 11:30h
- 04/06 - de 11:30h às 12:00h
- 04/06 - de 12:00h às 12:30h
- 04/06 - de 14:00h às 14:30h
- 04/06 - de 14:30h às 15:00h
- 04/06 - de 15:00h às 15:30h
- 04/06 - de 15:30h às 16:00h
- 04/06 - de 16:00h às 16:30h
- 04/06 - de 16:30h às 17:00h
- 06/06 - de 10:00h às 10:30h
- 06/06 - de 10:30h às 11:00h
- 06/06 - de 11:00h às 11:30h
- 06/06 - de 11:30h às 12:00h
- 06/06 - de 12:00h às 12:30h
- 06/06 - de 14:00h às 14:30h
- 06/06 - de 14:30h às 15:00h
- 06/06 - de 15:00h às 15:30h
- 06/06 - de 15:30h às 16:00h
- 06/06 - de 16:00h às 16:30h
- 06/06 - de 16:30h às 17:00h
31/05
- Exemplos de inserção de elementos em uma AVP.
05/06
- Apresentação de mais algumas operações básicas de AVP: sucessor, mínimo, retirada e correção da remoção; e
- Exercícios.
12/06
- Algoritmos de ordenação: seleção, bolha, quicksort e mergesort.
14/06
- Motivação para o aprendizado de heaps;
- Operações básicas de heaps; e
- Algoritmo de ordenação heapsort.
19/06 (não houve aula)
21/06 (aula de exercícios sobre árvores binárias no LCC)
26/06 (VR)
28/06 (revisão da nota da VR)
03/07 (segunda prova)
- OBS: Horários das apresentações:
- 05/07 - 15:00h (até 15:45h): G02 (Alexandre, Ian e Larissa)
- 05/07 - 17:30h (até 18:15h): G06 (Breno, Thadeu e Victor)
- 06/07 - 08:00h (até 08:45h): G11 (Igor)
- 06/07 - 08:45h (até 09:30h): G01 (Leandro, Leonardo e Matheus)
- 06/07 - 09:30h (até 10:15h): G08 (Gabriel e Lucas Paim)
- 06/07 - 10:15h (até 11:00h): G04 (Luiz Felipe Passos)
- 06/07 - 11:00h (até 11:45h): G07 (Augusto, Fernando e Luana)
- 06/07 - 11:45h (até 12:30h): G03 (Gisele, Jorge e Roberto)
- 05/07 - 12:30h (até 13:15h): G12 (Daniel e Luiz Felipe Aires)
- 06/07 - 13:30h (até 14:15h): G09 (Carlos e Lucas Vaccari)
- 06/07 - 14:15h (até 15:00h): G05 (Marcelo e Vinicius)
- 06/07 - 15:00h (até 15:45h): G10 (Felipe Calçado e Heitor)
05/07 (revisão da nota da segunda prova e apresentação do segundo trabalho)
06/07 (apresentação do segundo trabalho)
09/07 (apresentação do segundo trabalho)
10/07 (apresentação do segundo trabalho)
13/07 (VS - das 10:00 às 13:00h na Sala de Seminários do Instituto de Computação)