Itens Gerais

• Cronograma

Bibliografia

• C

  • Introdução a Estruturas de Dados - Com Técnicas de Programação em C

• C++

  • Objetos, Abstração, Estrutura de Dados e Projeto Usando C++

  • Estrutura de Dados e Algoritmos em C++

  • C++ Eficaz

Slides e Implementações

• Material

• Implementações

Material

• Alocação Dinâmica e Ponteiros (slides) (narrados)

• Alocação Dinâmica de Vetores e Matrizes (slides) (narrados)

• Ponteiros para Funções (slides) (narrados)

• Listas Encadeadas (slides) (narrados)

• Listas Simplesmente Encadeadas em C (slides) (narrados)

• Listas Duplamente Encadeadas em C (slides) (narrados)

  • Exemplos em

    • C++: https://www.geeksforgeeks.org/list-cpp-stl/

    • Java: https://www.geeksforgeeks.org/linked-list-in-java/

    • Python: https://realpython.com/linked-lists-python/

    • JavaScript: https://www.geeksforgeeks.org/implementation-linkedlist-javascript/

    • C#: https://www.geeksforgeeks.org/linked-list-implementation-in-c-sharp/

    • C:

      • https://developer.ibm.com/tutorials/l-glib/

      • https://docs.gtk.org/glib/struct.List.html

      • Codigo de GList (de Glib):

        • https://github.com/GNOME/glib/blob/main/glib/glist.h

        • https://github.com/GNOME/glib/blob/main/glib/glist.c

• Exemplos de Listas (vide material em "Implementações")

• • Listas de tipos estruturados

  • Listas usando void*

    • Exemplo mais simples

    • Exemplo mais elaborado

  • Listas de tipos heterogêneos

• Pilhas (pdf) e Filas (pdf)

  • Respostas dos exercícios (pdf)

  • Implementação (vide livro Celes)

• Extras

  • Exemplo de uso de strstr para buscar por sub-strings

    • Programação com strings em C (slides prof. Deise)

  • Geração de números aleatórios

    • Calculo de datas em C++

Árvores

• Árvores de n-filhos (pdf)

  • Exemplo de implementação

    • Em C (dados char)

• Árvores Binárias (pdf)

  • Exemplo de implementação

    • Em C (dados char)

  • Respostas Exercícios (pdf)

  • Percursos em Árvores Binárias (pdf)

• Árvores Binárias de busca (pdf)

  • Exemplo de implementação

    • Em C

  • Rotações em ABBs (pdf)

• Árvores AVL (pdf)

  • Exemplo ABBs vs AVL (pdf)

  • Visualização de Operações em árvores AVL:

    • AVL Tree Visualization (usfca.edu)

Grafos

• • Introdução (pdf)

  • Buscas

    • em largura (pdf)

    • em profundidade (pdf)

  • Árvore de amplitude mínima (pdf)

    • Prim: https://archive.org/details/bstj36-6-1389

    • Kruskal: http://www.jstor.org/stable/pdfplus/2033241.pdf

  • Caminho mínimo - algoritmo de Dijkstra (pdf)

    • Exemplo: http://www.youtube.com/watch?v=8Ls1RqHCOPw

      • Artigo: http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf

  • Exercícios (pdf)

    • Respostas (pdf)

• Trabalho 1 - Alocação Dinâmica, Listas

  • Criar um programa para controle acadêmico, que atenda aos seguintes requisitos mínimos:

    1. Os dados devem ser armazenados em listas em memória.

    2. Deve ser possível cadastrar alunos, professores, disciplinas e turmas (operações: incluir, excluir, buscar e visualizar).

    3. Cada aluno deve ter os seguintes dados: matrícula, nome, curso.

    4. Cada professor deve ter os seguintes dados: código, nome.

    5. Cada disciplina deve ter os seguintes dados: código, curso, nome, carga horária.

    6. Deve ser possível matricular alunos em uma turma. Uma turma pode ter apenas um professor associado.

• Trabalho 2 - Árvores binárias de busca

  • Considere uma lista de carros, onde cada carro possui os seguintes campos: placa, marca e ano. Crie um programa com os seguintes requisitos:

    1. A lista deve ser ordenada fisicamente pela placa dos carros.

    2. Deve ser possivel incluir e excluir carros na lista.

    3. Deve ser mantida em memória uma árvore binária relativa à placa dos carros.

    4. Deve ser mantida em memória uma árvore binária cujo percurso seja equivalente à lista ordenada pelo marca.

    5. Deve ser mantida em memória uma árvore binária cujo percurso seja equivalente à lista ordenada pela ano.

    6. Deve ser possível buscar carros pela placa, usando a árvore binária auxiliar.

    7. Deve ser possivel listar os carros ordenadamente pela placa, percorrendo a lista.

    8. Deve ser possivel listar os carros ordenadamente pelo marca, através da árvore auxiliar.

    9. Deve ser possivel listar os carros ordenadamente pela ano, através da árvore auxiliar.

• Trabalho 3 - Grafos

  • Utilize o material de apoio no site da disciplina e crie um programa que receba um grafo (com nós numerados) como entrada e seja capaz de atender aos seguintes requisitos:

    1. O grafo deve ser representado usando listas de adjacência (veja o slide 38 de "Grafos - Introducao").

    2. O programa deve ser capaz de percorrer o grafo a partir de um nó informado pelo usuário por largura ou por profundidade, mostrando o percurso em pré-ordem e em pós-ordem (veja os slides de "Grafos - Busca em Largura" e "Grafos - Busca em Profundidade".

• Prova 1

  • Conteúdo: Alocação dinâmica e Ponteiros, Listas, Pilhas e Filas

  • Sugestão de leitura - Livro Celes - Bibliografia básica:

    • Cap 7 - Alocação Dinâmica, 8 - Cadeias de Caracteres, 9 - Tipos Estruturados

    • Cap 12 - Tipos Abstratos de Dados, 14 - Listas Encadeadas, 15 - Pilhas e Filas e 17 - Estruturas Genéricas (17.1 e 17.2)