Estrutura de Dados I

Prévia do material em texto

Estrutura de Dados
Introdução à Estrutura de Dados e Métodos de Ordenação
Material Teórico
Responsável pelo Conteúdo:
Prof. Ms. Amilton Souza Martha
Revisão Textual:
Profa. Ms. Fatima Furlan
5
• Introdução
• O que é Dado?
• Tipos de Dados
Para essa manipulação vamos usar os tipos abstratos de dados, ou TADs, no nosso caso usaremos 
as classes Java para representá-los. Para quem precisa de um reforço em POO é interessante pegar 
um livro de Java e rever os conceitos estudados. Existem vários livros na biblioteca da universidade 
e também na biblioteca virtual.
Também veremos aqui alguns métodos de ordenação. Os algoritmos já são colocados em Java no 
material, porém seria interessante poder simular como eles fazem a ordenação. Para isso existem 
links de apoio no Material Complementar com simuladores e vídeos.
Para um bom aproveitamento do curso, leia o material teórico atentamente antes de realizar as 
atividades. É importante também respeitar os prazos estabelecidos no cronograma.
 · Nesta unidade vamos conhecer os conceitos fundamentais 
da Estrutura de Dados, como por exemplo, entender o que 
é um dado e como organizamos os dados na memória do 
computador para poder manipulá-los.
Introdução à Estrutura de Dados e 
Métodos de Ordenação
• Tipo Abstrato de Dados (TAD)
• Métodos de Ordenação
6
Unidade: Introdução à Estrutura de Dados e Métodos de Ordenação
Um programa de computador está dividido em dados e em algoritmos que manipulam os 
dados. Diversos algoritmos de manipulação de estruturas de dados já são amplamente usados 
na ciência da computação e estudá-los evita “reinventar a roda” quando um problema ocorrer, 
podendo apenas selecionar a melhor estrutura para determinado problema.
Também veremos durante o curso que existem várias situações nas quais podemos usar os 
conceitos de Pilhas, Filas, Listas Ordenadas, Árvores ou Hash. Acredite, esse ferramental teórico 
será muito útil para sua vida como analista/programador.
Contextualização
Para Pensar
Por exemplo, se quisermos ordenar um conjunto de 
elementos desordenados, como faremos? 
Já existem vários algoritmos que fazem isso, portanto, 
basta escolher um e usar. 
Não é necessário criar outro.
7
Um computador é dividido em duas partes que trabalham juntas, o Hardware e o Software. 
O Hardware representa a parte física do computador como mouse, teclado, memórias, monitor 
etc. O Software é a parte lógica que são os programas de computador.
O desenvolvimento de um programa de computador pode ser dividido, de forma genérica, 
nos dados e nas instruções que manipulam esses dados. Para organizar os dados dentro da 
memória do computador temos a Estrutura de Dados e para manipular esses dados temos os 
Algoritmos, conforme ilustrado na Figura 1.
Figura 1 – Ilustração de Estrutura de Dados e Algoritmos
Já que estamos falando de Estrutura de Dados, cabe aqui tentarmos definir o que é dado. 
Muitos devem ter pensando “Dados é uma informação”. Está certo, mas agora defina o que é 
informação? A sua resposta foi “Informação é um dado”? 
Nesse caso, temos uma recursão, e aparentemente são sinônimos, mas não são. Outros 
termos podem entrar nessa conversa como conhecimento e sabedoria. Veja a Figura 2 a seguir:
Introdução
O que é Dado?
8
Unidade: Introdução à Estrutura de Dados e Métodos de Ordenação
Figura 2 – Hierarquia dos Dados
Dados: podemos definir dado como o registro de uma medida ou anotação que não 
possui um conteúdo semântico associado. Por exemplo, fazemos uma pesquisa de opinião 
de um novo produto com centenas de pessoas. Os registros anotados são apenas dados.
Informações: Informação é o resultado de um conjunto de dados analisados. As 
informações possuem significados e servem para tomada de decisões. Por exemplo, na 
pesquisa citada anteriormente, constatou-se que o novo produto não agradou a maioria. 
Essa informação pode fazer a empresa rever o produto.
Conhecimento: Conhecimento é o acúmulo de informações já trabalhadas. Refere-
se à análise de informações já colhidas. Por exemplo, outros produtos da mesma linha 
já foram analisados anteriormente no mercado, até mesmo por outras marcas e esse 
conhecimento proporciona aprender com isso e não cometer os mesmos erros. 
Sabedoria: Sabedoria é o mais alto nível de abstração que consiste em analisar os conhecimentos 
adquiridos. Não basta ter conhecimentos das coisas, é preciso saber onde e como usá-los.
Dessa forma, como o nome da disciplina diz, Estrutura de Dados se propõe a manipular os 
dados em memória para que os algoritmos possam tratá-los, não importando o que são e nem 
pensando no significado que eles possuem. Podemos criar uma lista de alunos, de carros, de 
professores, de números e todos serão tradados apenas como “dados”.
A unidade básica de informação dentro da memória do computador é o bit (binary digit), que 
são representados por 0 ou 1. Obviamente que com um único bit não poderíamos representar 
muita informação, porém, agrupados podem representar uma enorme quantidade e variedade 
de informações. Surge então o conceito de byte, que é o conjunto de 8 bits.
Porém, um conjunto de bytes pode ser interpretado de formas diferentes de acordo com 
o tipo de dados que será armazenado nessa área de memória. Um tipo de dados pode ser 
entendido como um método para interpretar os padrões de bits em memória. No entanto, 
Tipos de Dados
9
pode ser visto de uma perspectiva totalmente diferente, não mais em relação às funções 
implementadas eletronicamente no computador, mas em relação ao ponto de vista do usuário 
e das suas expectativas.
Tipos de Dados Primitivos
São os tipos de dados que além de depender das características do sistema, dependem do 
processador. Os tipos de dados primitivos ou básicos são aqueles a partir dos quais podemos 
definir os demais tipos ou organizações de informações, quase sempre mais complexas. Esses 
tipos são implementados e manipulados pelos compiladores: o compilador é o responsável 
pelo armazenamento e processamento (operações) desses tipos de dados. Os tipos de dados 
primitivos mais frequentes e suas operações são:
Tipo de dado Algumas operações possíveis Exemplo de utilização
Inteiro
Soma, subtração, multiplicação, divisão, 
igualdade etc. Usado para representar valores 
que não podem ter casas decimais.
Idade, ano, dia, número de filhos.
Real
Soma, subtração, multiplicação, divisão, 
igualdade etc. Usado para representar 
valores que podem ser fracionados (com 
casas decimais).
Peso, estatura, salário.
Caracteres
Igualdade, concatenação etc. Usado para 
informações armazenadas como uma 
sequencia de caracteres contáveis de objetos.
Nome, endereço, cargo ocupacional.
Lógico E, OU, NÃO. Valores verdadeiro ou falso. Formado, solteiro.
Ponteiro Igualdade, soma, subtração etc. Armazenam um endereço da memória do computador.
Frente Fila, primeiro, próximo.
Tipos de Dados Estruturados
Os tipos de dados estruturados são organizações de dados que são obtidas a partir dos tipos 
de dados primitivos. A maioria das linguagens de programação provê alguns tipos estruturados 
para facilitar a organização de dados. Os mais frequentes são:
• Arranjos (arrays) Array em Pascal, C e BASIC;
• Registros Record em Pascal, struct em C, Type em Visual Basic;
• Conjuntos Set em Pascal.
10
Unidade: Introdução à Estrutura de Dados e Métodos de Ordenação
Pode ser definido como um conjunto de valores e por uma série de operações que atuam 
sobre esses valores. As operações devem ser consistentes com os tipos de valores. Funções e 
valores constituem um modelo matemático que pode ser empregado para implementar um tipo 
de dado abstrato. Em programação Orientada a Objetos, as classes representam um TAD, sendo 
que os valores são os atributos de uma classe, e as operações, os métodos.
Para a implementação de um TAD, devemos usar os tipos de dados existentes e implementar 
as operações possíveis sobre esses dados.
Veja na Figura 3 um exemplo de TAD usando uma classe. Energia,forca e qtdvidas são os 
dados que o tipo pode armazenar e são do tipo primitivo. Socar, pular, mover e morrer são as 
ações que esse tipo pode executar.
Podemos implementar um TAD usando uma classe em uma linguagem POO ou estruturas 
(structs ou record) como na linguagem C.
Figura 3 – Exemplo de Tipo Abstrato de Dados
Classe Inimigo
+energia: int
+forca: int
+qtdvidas: int
+socar(): void
+pular(): void
+mover() : void
+morrer(): void
Um dos algoritmos mais usados em Estruturas de Dados consiste em ordenar um vetor de 
elementos desordenados. Para “criar ordem ao caos” existem vários algoritmos que ordenam 
um conjunto de dados, alguns mais complexos, outros mais simples.
Existem basicamente duas categorias de métodos de ordenação:
a) Ordenação Interna (ou em memória): nesse método todos os elementos a serem 
ordenados estão na memória, por exemplo, um vetor de elementos. Podemos usar esses 
métodos quando os elementos cabem na memória.
b) Ordenação Externa: nesse outro método, os elementos não cabem todos na memória, 
sendo necessário o uso de técnicas de swap para poder ordenar os elementos, por 
exemplo, um arquivo de 1GB. 
Tipo Abstrato de Dados (TAD)
Métodos de Ordenação
11
Estudaremos apenas os algoritmos de ordenação interna. Nesse caso, selecionamos 
quatro algoritmos de ordenação para entender seus princípios.
Bubble Sort
Por ser simples e de fácil entendimento e implementação, o Bubblesort (Método da Bolha) 
está entre os mais conhecidos e difundidos métodos de ordenação de arranjos. Mas não se trata 
de um algoritmo eficiente, é estudado para fins de desenvolvimento de raciocínio. 
O princípio do Bubblesort é a troca de valores entre posições consecutivas, fazendo com que os 
valores mais altos (ou mais baixos) “borbulhem” para o final do arranjo (daí o nome Bubblesort). 
Na Figura 5, podemos ver a implementação em Java do método BubbleSort. Note que o 
algoritmo baseia-se em troca de valores.
A Figura 4 ilustra a primeira passagem 
do algoritmo BubbleSort em um vetor 
desordenado de 5 elementos. Note que 
ele sempre compara o elemento ao 
seu vizinho. Comparando 5 com o 3 
(posição 1 com posição 2) notamos que 
estão fora de ordem (5>3). Nesse caso, 
faz-se a troca. Em seguida compara-se 
5 com 1 (posição 2 com posição 3) e 
novamente faz-se a troca, e assim por 
diante. Podemos notar que o número 
5 vai sendo jogado para o final. Após 
a primeira passagem, executamos 
novamente o algoritmo da posição 1 até 
4 (já que a quinta já está em ordem).
Figura 4 – Primeira passagem do BubbleSort
12
Unidade: Introdução à Estrutura de Dados e Métodos de Ordenação
Figura 5 – Implementação em Java do BubbleSort
Selection Sort
O método de ordenação por seleção (Seleção Direta) pode ser comparado à ordenação de 
cartas. Imagine todas as cartas espalhadas na mesa e o jogador seleciona a menor de todas e 
a coloca em sua mão, assim até o final das cartas. Desse modo, no final do processo, as cartas 
estarão ordenadas. 
O método de ordenação por Seleção Direta é levemente mais eficiente que o método Bubblesort, 
ainda que se trate de um algoritmo apenas para estudo e ordenação de pequenos arranjos.
public static void bubbleSort(int vetor[]){
 int aux;
 int tam = vetor.length;
 for(int i=0; i < tam - 1; i++ ){
 for(int j=0; j < tam - 1 - i; j++){
 if(vetor[j] > vetor[j+1]){
 aux = vetor[j];
 vetor[j] = vetor[j+1];
 vetor[j+1] = aux;
 }
 }
 }
}
A lógica consiste em se varrer o arranjo 
comparando todos os seus elementos com 
o primeiro. Caso o primeiro elemento esteja 
desordenado em relação ao elemento que está 
sendo comparado com ele no momento, é 
feita a troca. Ao se chegar ao final do arranjo, 
teremos o menor valor (ou o maior, conforme 
a comparação) na primeira posição do arranjo. 
Este primeiro passo nos garante que o menor 
elemento fique na primeira posição. 
Analisando a Figura 6 podemos notar que 
o primeiro elemento (posição 1) está sendo 
comparado com todas as posições à direita dele 
e cada vez que um elemento encontrado for 
menor que a primeira posição, o valor é trocado. 
Desse modo, ao término da primeira passagem 
temos certeza de que o primeiro elemento do 
vetor é o menor de todos. Em seguida, basta 
aplicar o mesmo algoritmo da segunda posição 
em diante, depois terceira e quarta.
Figura 6 – Primeira passagem do SelectionSort
13
Veja na Figura 7 a implementação do Algoritmo em Java. Note que esse algoritmo também 
se baseia em troca.
Figura 7 – Implementação em Java do SelectionSort
Insertion Sort
O método de ordenação por inserção é bastante simples e eficiente para um pequeno 
número de dados a se ordenar. Consiste em ir inserindo os dados um a um já na posição 
correta onde deve ficar, sendo que no final da inserção do último elemento, todos os 
dados já estarão ordenados. 
A ideia é semelhante à ordenação de cartas de baralho na mão do jogador. O jogador 
coloca uma carta por vez na mão, e a cada carta que insere, já a põe na ordem correta, 
sendo que ao final, todas as cartas estarão na ordem. 
O método de ordenação por Inserção Direta é o mais rápido entre os outros métodos 
considerados básicos – Bolha (Bubblesort) e Seleção Direta (SelectSort). 
A principal característica desse método consiste em ordenarmos nosso arranjo utilizando 
um subarranjo ordenado localizado em seu início, e a cada novo passo, acrescentamos 
a este subarranjo mais um elemento, até que atingimos o último elemento do arranjo 
fazendo assim com que ele se torne ordenado. 
public static void selectionSort(int vetor[]){
 int aux;
 int tam = vetor.length;
 for(int i=0; i < tam - 1; i++){
 for(int j = i + 1; j < tam; j++){
 if(vetor[j] < vetor [i]){
 aux = vetor[j];
 vetor[j] = vetor[i];
 vetor[i] = aux;
 }
 }
 }
}
14
Unidade: Introdução à Estrutura de Dados e Métodos de Ordenação
Recursividade
Os três algoritmos de ordenação estudados são chamados iterativos, ou seja, utilizam estrutura 
de repetição. Nosso último método de ordenação utiliza outro recurso chamado recursividade. 
Um algoritmo, que para resolver um problema divide-o em subproblemas mais simples, cujas 
soluções requerem a aplicação dele mesmo, é chamado recursivo. 
public static void insertSort(int vetor[]){
 int aux;
 int tam = vetor.length;
 int j;
 for(int i=1; i < tam; i++){
 aux = vetor[i];
 j = i - 1;
 while(j > = 0 && aux < vetor[j]){
 vetor[j+1] = vetor[j];
 j--;
 }
 vetor[j+1] = aux;
 }
}
Na Figura 8, inicialmente consideramos o primeiro 
elemento do arranjo como se ele estivesse ordenado, ele 
será considerado o nosso subarranjo ordenado inicial.
Após copiá-lo, devemos percorrer o subarranjo a 
partir do último elemento para o primeiro. Assim 
poderemos encontrar a posição correta da nossa 
variável auxiliar dentro do subarranjo.
Vamos comparar a cópia com os valores no 
subvetor ordenado. A cada vez que o elemento 
for menor que o elemento a ser comparado, 
deve-se copiar o elemento para a direita.
A cada nova interação, o elemento é inserido na 
posição correta.
Veja na Figura 9 a implementação do Algoritmo 
em Java. Note que esse algoritmo se baseia na 
inserção de elementos.
Figura 8 – Trecho do InsertionSort
Figura 9 – Implementação em Java do InsertionSort
15
Em termos de programação, uma rotina é recursiva quando ela chama a si mesma, seja 
de forma direta ou indireta. Em geral, uma rotina recursiva R pode ser expressa como uma 
composição formada por um conjunto de comandos C (que não contêm chamadas a R) e uma 
chamada (recursiva) à rotina R: 
Todo algoritmo recursivo tem duas partes: 
• Solução Trivial: dada por definição, isto é, não necessita de recursão para ser obtida. 
É o critério de parada da recursividade que se não for bem implementado, pode deixar o 
programa em looping infinito. 
• Solução Recursiva: parte do problema que em essência é igual ao problema original, 
sendo, no entanto menor. Nesse caso, a chamada recursiva sempre utiliza um termo 
menor e sempre precisa deum parâmetro. 
Um exemplo bastante comum para explicar recursividade é o fatorial. Podemos resolver o 
fatorial de forma iterativa ou recursiva.
5! = 5.4.3.2.1 = 120
O algoritmo acima mostra a solução iterativa através da multiplicação de todos os fatores. 
Podemos usar um comando de repetição para realizar a operação.
Porém podemos dizer que 5! = 5.4!
Notem que o resultado de um fatorial (5!) depende da resposta de outro fatorial (4!) e isso é 
recursividade. Certo, mas quanto é 4!?
Até onde vamos com isso? Cada vez que, para resolver um algoritmo você chama a ele mes-
mo (geralmente com um parâmetro menor) temos o que chamamos que solução recursiva. Po-
rém, para não entrarmos em looping infinito, uma hora isso deve parar, é a nossa solução trivial.
No nosso exemplo, 0! é por definição 1. Ou seja, não é mais necessário chamar a recursivi-
dade e você pode resolver as contas pendentes. 
4! = 4.3! e quanto é 3! ?
3! = 3.2! e quanto é 2! ?
2! = 2.1! e quanto é 1! ?
1! = 1.0! e quanto é 0! ?
16
Unidade: Introdução à Estrutura de Dados e Métodos de Ordenação
Quick Sort
Seu algoritmo consiste em dividir o problema em problemas menores, utilizando um algoritmo 
recursivo para a ordenação dos elementos. Um dos aspectos interessantes da ordenação por 
segmentação é que ela ordena as coisas quase da mesma maneira como fazem as pessoas. 
Primeiro, ela cria grandes “pilhas”, e depois, as ordena em pilhas cada vez menores, terminando 
finalmente com um array inteiramente ordenado. 
O algoritmo de ordenação por segmentação começa estimando um valor de intervalo médio 
para o array. Se o array for composto de números de 1 a 10, o ponto médio poderia ser 5 ou 6 
(elemento pivô). O valor exato do ponto médio não é fundamental. O algoritmo vai trabalhar 
com um ponto médio de qualquer valor. Entretanto, quanto mais próximo o ponto médio 
estimado estiver do ponto médio real do array, mais rápida será a ordenação.
A rotina calcula um ponto médio considerando o primeiro e o último elemento da parte do 
array que está sendo ordenada.
Depois que a rotina seleciona um ponto médio, ela coloca todos os elementos menores que 
o ponto médio na parte inferior do array e todos os elementos maiores na parte superior. Em 
seguida, o algoritmo se repete na parte inferior do array e na parte superior, sucessivamente, até 
que o sub-array tenha apenas um elemento.
Veja na Figura 10 a implementação em Java. Esse algoritmo não é baseado em trocas e nem 
em inserção, é considerado algoritmo de ordenação por segmentação.
Figura 10 – Implementação em Java do QuickSort
public static void quickSort(int vetor[]){
 quickSort(vetor, 0, vetor.length - 1);
}
public static void quickSort(int vetor[], int i, int s){
 int e=i, d=s;
 int item = vetor[((e+d)/2)];
 while(e < = d){
 while(vetor[e] < item) e++;
 while(vetor[d] > item) d--;
 if(e < = d){
 int aux; // Variável auxiliar para as trocas
 aux = vetor[e];
 vetor[e] = vetor[d];
 vetor[d] = aux;
 d--;
 e++;
 }
 }
 if(d - i > 0) quickSort(vetor, i, d);
 if(s - e > 0) quickSort(vetor, e, s);
}
17
Material Complementar
Simuladores:
• http://pages.stern.nyu.edu/~panos/java/Quicksort/ 
• http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/
Sort2-E.html
• http://cg.scs.carleton.ca/~morin/misc/sortalg/
YouTube
• http://youtu.be/YKlDz1J3TSw
Wikipedia:
• http://pt.wikipedia.org/wiki/Estrutura_de_dados
• http://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o
Livros Disponíveis na Biblioteca 
• PREISS, B. R. Estruturas de Dados e Algoritmos: Padrões de 
Projetos Orientados a Objetivos Com. Rio de Janeiro: Campus, 2001.
• WIRTH, N. Algoritmos e Estruturas de Dados. Rio de Janeiro: Ltc-
Livros Técnicos e Científicos, 1999.
• MORAES, C. R. Estruturas de Dados e Algoritmos: Uma 
Abordagem Didática. São Paulo: Berkeley, 2001.
• FORBELLONE, A. L. V.; EBERSPACHER, H. F. Lógica de Programação: 
A Construção de Algoritmos e Estrutura de Dados. 3. ed. São 
Paulo: Makron Books do Brasil, 2005.
• VELOSO, P.; FURTADO, A.; SANTOS, C. S. Estruturas de Dados. 
26. ed. Rio de Janeiro: Campus, 2003.
• TENENBAUM, A. M.; LANGSAM, Y. Estruturas de Dados Usando C. 
São Paulo: Makron Books do Brasil, 2005.
• DROZDEK, A. Estrutura de Dados e Algoritmos em C++. 
São Paulo: Pioneira Thomson Learning, 2005.
Livros Disponíveis na Biblioteca Virtual 
• ASCENCIO, Ana F.G., Aplicações das Estruturas de Dados em Delphi. 
São Paulo: Pearson Prendice Hall, 2005
• ASCENCIO, Ana F.G., Estruturas de Dados: algoritmos, 
análise da complexidade e implementações em Java e C/
C++ São Paulo: Pearson Prendice Hall, 2010
• DEITEL, Harvey M., Java Como Programar, 8.ed. São Paulo: 
Pearson Prentice Hall, 2010
18
Unidade: Introdução à Estrutura de Dados e Métodos de Ordenação
ASCENCIO, Ana F.G., Aplicações das Estruturas de Dados em Delphi. São Paulo: 
Pearson Prendice Hall, 2005.
GOODRICH, M. T.; TAMASSIA, R. Estruturas de Dados e Algoritmos em Java. 2. ed. 
Porto Alegre: Bookman, 2002.
LAFORE, R. Estruturas de Dados & Algoritmos em Java. Rio de Janeiro: Ciência Moderna, 
2004.
PEREIRA, S. L. Estruturas de Dados Fundamentais: Conceitos e Aplicações. 9. ed. São 
Paulo: Erica, 2001.
WEISS, M. A. Data Structures And Algorithm Analysis In Java. 2. ed. Massachusetts: 
Addison-Wesley, 2007.
Referências
19
Anotações
20
www.cruzeirodosulvirtual.com.br
Campus Liberdade
Rua Galvão Bueno, 868
CEP 01506-000
São Paulo SP Brasil 
Tel: (55 11) 3385-3000
www.cruzeirodosulvirtual.com.br
Rua Galvão Bueno, 868
Tel: (55 11) 3385-3000