O Calculo e Estrutura de Dados

[pic 1][pic 2]

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

[pic 3]

---

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

...