A maior rede de estudos do Brasil

Grátis
70 pág.
Estruturas de Dados - UNICAMP (Notas de Aula - Profº Ivan Luiz Marques Ricarte)

Pré-visualização | Página 1 de 20

DEPARTAMENTO DE ENGENHARIA DE COMPUTAÇÃO E AUTOMAÇÃO INDUSTRIAL
FACULDADE DE ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO
UNIVERSIDADE ESTADUAL DE CAMPINAS
Estruturas de dados
Ivan Luiz Marques Ricarte
http://www.dca.fee.unicamp.br/~ricarte/
2008
Sumário
1 Tipos de dados 2
1.1 Tipos primitivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Valores booleanos . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Caracteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.3 Valores numéricos inteiros . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.4 Valores numéricos reais . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.5 Declaração de variáveis . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.6 Ponteiros e referências . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Tipos definidos pelo programador . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.1 Strings em C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 Bibliotecas de classes . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Tipos agregados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Estruturas lineares 15
2.1 vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Estrutura interna . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2 Criação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.3 Operações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.4 Iteradores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 deque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1 Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.1 Aspectos de implementação . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Busca em estruturas lineares . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5 Ordenação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5.1 Algoritmos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5.3 Radix sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5.4 Ordenação em STL . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
i
Sumário ii
3 Estruturas associativas 36
3.1 set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2 map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3 Aspectos de implementação . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1 Árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.2 Tabelas hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4 Representação interna de valores 47
4.1 Representação de caracteres . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2 Representação numérica binária . . . . . . . . . . . . . . . . . . . . . . . . 47
5 A linguagem de programação C++ 50
5.1 Fundamentos de C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.1.1 Organização de programas . . . . . . . . . . . . . . . . . . . . . . . 50
5.1.2 Expressões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.1.3 Expressões condicionais . . . . . . . . . . . . . . . . . . . . . . . . 55
5.1.4 Controle do fluxo de execução . . . . . . . . . . . . . . . . . . . . . 56
5.1.5 Arquivos em C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 Palavras reservadas em C e C++ . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3 Precedência de operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6 Exercícios 63
Estruturas de dados
Em diversos contextos, disciplinas associadas à programação recebem a denominação
de “processamento de dados”. Esta denominação não é gratuita — de fato, embora seja
possível criar procedimentos que não manipulem nenhum dado, tais procedimentos seriam
de pouco valor prático. Uma vez que procedimentos são, efetivamente, processadores de
dados, a eficiência de um procedimento está muito associada à forma como seus dados são
organizados. Estrutura de dados é o ramo da computação que estuda os diversos mecanismos
de organização de dados para atender aos diferentes requisitos de processamento.
Nesta apostila são apresentadas algumas estruturas de dados, com ênfase naquelas que
são utilizadas posteriormente no decorrer do texto. Assim, algumas estruturas de importância
para outros tipos de aplicações — como a representação de matrizes esparsas, fundamental
para a área de computação científica — não estão descritas aqui.
As estruturas de dados definem a organização, métodos de acesso e opções de proces-
samento para coleções de itens de informação manipulados pelo programa. Dois tipos de
coleções são apresentados. Estruturas lineares são aquelas que mantém os seus itens de
forma independente de seus conteúdos, ou seja, na qual qualquer tipo de interpretação dos
dados que são armazenados é irrelevante para a manutenção da estrutura. Estruturas associa-
tivas são aquelas que levam em consideração a interpretação do valor (ou de parte dele) para
a manutenção dos itens na estrutura.
Apresenta-se inicialmente uma visão conceitual de cada tipo de estrutura, com ilustrações
que utilizam estruturas pré-definidas na biblioteca padrão de gabaritos (STL) da linguagem
C++. São apresentados também aspectos da organização interna de uma estrutura de dados.
Tais aspectos são relevantes para o projeto e implementação de uma nova estrutura de dados e
normalmente não são manipulados por um programador que simplesmente utiliza estruturas
já existentes na linguagem. Entretanto, é importante que o usuário detenha tal conhecimento
por dois motivos. O primeiro é simplesmente ter parâmetros para poder selecionar qual a
implementação mais adequada, se houver mais de uma disponível, para a sua aplicação. O
segundo motivo é ter conhecimento para, se for necessário por não haver nenhuma imple-
mentação disponível, desenvolver a sua própria implementação de uma estrutura adequada
às suas necessidades.
Capı´tulo 1
Tipos de dados
Internamente, todos os dados são representados no computador como seqüências de bits,
ou seja, uma seqüência de dígitos binários (o nome bit é derivado da expressão binary digit),
onde cada bit é usualmente representado pelos símbolos 0 ou 1. Esta é a forma mais conve-
niente para manipular os dados através de circuitos digitais, que podem diferenciar apenas
entre dois estados (on ou off, verdadeiro ou falso, 0 ou 1). Em assembly, tipicamente to-
dos os valores escalares são representados na forma de bytes (grupos de 8 bits), words (dois
bytes ou 16 bits) ou long words (quatro bytes ou 32 bits) — uma seqüência de n bits pode
representar uma faixa com 2n valores distintos. Nestes casos, a interpretação desses valores
é tipicamente delegada ao programador da aplicação.
Em linguagens de programação de alto nível, é desejável ter flexibilidade para lidar com
diferentes interpretações para essas seqüências de bits de acordo com o que elas representam.
Esse grau de abstração é oferecido por meio dos tipos primitivos da linguagem, que estabele-
cem estruturas de armazenamento e conjuntos de operações para esses valores. Além disso,
as linguagens de programação oferecem usualmente mecanismos para trabalhar com conjun-
tos de valores e, em alguns casos, oferecem a possibilidade de criar novos tipos que podem
ser usados pelos programadores. Tais princípios de representação são apresentados a seguir.
1.1 Tipos primitivos
O

Crie agora seu perfil grátis para visualizar sem restrições.