Curso Online de Algoritmos e Estruturas de Dados : Listas, filas e pilhas

Valdey valente silva FAPEN
Ciencia da computação

Algoritmos e Estruturas de Dados
Aula : 01

Listas, filas e pilhas
Alocação sequencial
Listas encadeadas
Listas circulares
Listas duplamente encadeadas
Filas e pilhas

Objetivos

Mapear o domínio do problema no domínio da solução utilizando estruturas de armazenamento de informações adequadas e algorítimos eficientes.
Construir estruturas a partir de abstrações tanto de informações quanto do procedimentos.
Construir e analisar algorítimos para manipular e armazenar dados em programas.

Programa

Introdução
Tipos abstratos de dados
Registros
Procedimentos e funções
Recursividade
Complexidade de algoritmos
Introdução
Tipos de complexidade
Notação O
Algoritmos ótimos

Programa

Listas, filas e pilhas
Alocação sequencial
Listas encadeadas
Listas circulares
Listas duplamente encadeadas
Filas e pilhas
Árvores Aula 02
Percurso em árvores
Árvores AVL
Árvores rubro-negras
Árvores múltiplas

Bibliografia

Tenenbaum, A. M. et all. Estruturas de Dados Usando C. Makron Books. São Paulo, 1995.
Estruturas de dados. Paulo Veloso, Clésio Veloso dos Santos e outros. Ed. Campus.
Algorítmos e Estruturas de dados. Guimarães Lages. Ed. LTC.
Estruturas de dados Fundamentais: conceitos e aplicações. Silvio do Lago. Ed. Érica

Desenvolvimento de Programas

O processo de solução de problemas por meio de computador pode ser descrito a partir das seguintes etapas:
1. Especificação do problema
2. Projeto em alto nível
3. Análise de alternativas
4. Refinamento e codificação
5. Verificação do comportamento

Desenvolvimento de Programas

Nesta descrição devemos ressaltar 3 pontos:
Estruturas de dados, que retratam as relações lógicas existentes entre os dados, de modo análogo ao uso de um modelo matemático para espelhar alguns aspectos de uma realidade física.
Operações, manipulam as estruturas de dados transformando-as.
Estruturas de Representação, que são formas de armazenar na memória os dados, isto é, as estruturas de dados manipuladas pelas operações, que devem:
Preservar as relações lógicas existentes entre os dados.
Permitir que as operações sejam descritas por procedimentos simples e eficientes.

Tipos Abstratos de Dados

Tipos Abstratos de Dados

Para descrever os algorítimos e procedimentos durante o curso, vamos utilizar uma linguagem de descrição algoritmica.
A noção do tipo de dados ocorre na maioria das linguagens de programação. O tipo da variável delimita o conjunto de valores que ela pode tomar e as operações que podemos efetuar com elas.
Geralmente uma linguagem de programação oferece 2 tipos de Tipos de dados:
Tipos Primitivos: São tipos básicos pré definidos
Tipos construídos: tipos criados a partir de mecanismos presentes na linguagem.

Tipos primitivos Operações aceitas
inteiro - int + - * div mod
real - real + - * /
lógico - log e ou não (.e. & .ou. V )
caracter- car = 

Exemplos: Tipos inteiro ? Real ? Lógico ? Caracter ?

5 div 2 = 2
5 mod 2 = 1

5 2
1 2

V= F e F = V

Funções de Transferência

São operações especiais que manipulam variáveis de tipos primitivos, diferentes entre si, por exemplo: Xi sendo X real e inteiro.
Comparações também podem ser consideradas funções de transferência, por exemplo:X < i sendo X real e i inteiro e o resultado lógico F(V)
Trunc, converte um numero real em inteiro trunc (75.37)=75
Tier, converte inteiro em real tier (75)= 75.0
Ord, transforma car em int que é seu numero de ordem no conjunto de caracteres ASCII ord (‘0’) < ord (‘9’)< ord(‘A’)< ord(‘a’). Mais funções de transferencia podem ser obtidas nos tipos construídos.