Estrutura de dados

Prévia do material em texto

Aula 4: Ornação e Pesquisa
Comparação de vetor 
Para compararmos vetores de char, usaremos a função strcmp()
Para copiarmos o conteúdo de um vetor de char nas posições ocupadas por outro vetor de char, usaremos strcpy.
//Usando biblioteca <cstring>
Métodos Simples
-Mais eficientes para pequenos conjuntos;
-Usam muitas comparações;
-Códigos pequenos;
-Códigos de fácil entendimento;
Exemplos:
-Selection sort (ordenação por seleção)
-Insertion sort (ordenação por inserção)
-Bubble sort (ordenação por troca)
Metodos eficientes ou sofisticados
-Indicados para conjuntos grandes;
-Usam menos comparações;
-Os códigos são grandes;
-Alguns incluem conceito de recursividade, deixando-os mais complexos.
Exemplos:
-Heap sort (ordenação por seleção em árvores)
-Shell sort (ordenação por inserção, vários segmentos)
3- Quick sort (ordenação por troca/partição)
Selection Sort 
O principio básico desse método é sempre buscar o menor dos valores restantes e leva-los às posições iniciais (ordenação crescente).
Void seleção (int vet[], int tam){		aux=j;
int j,i,aux,temp;					temp=vet[aux];
for (i=0;i<tam-1;i++){				vet[aux]=vet[i]
aux=i						vet[i]=temp;
for(j=i+1;j<tam;j++)				}}
if(vet[aux]>vet[j])
//o vetor embora não tenha o & sempre é passado por referencia
Insertion sort 
O principio básico desse método é considerar o vetor como dois subvetores, um ordenado e outro desordenado, buscando posicionar o elemento que se encontra no subvetor desordenado, no vetor ordenado.
Void insersao (int vet[], int tam){
int j,i,aux;
For(i=1;i<tam;i++){
aux=vet[i];
for (j=1;j>0 &&aux<vet[j-1]; j--)
vet[j]=vet[j-1];
vet[j]=aux;
}}
Bubble sort 
O principio básico desse meto é trocar as posições todas as vezes que forem encontrados valores de posição adjacentes fora de ordem.
Void bolha (int vet[], int tam){
Int j,i,aux;
for (i=0; i<tam-1;i++)
if (vet[j]<vet[j-1){
aux=vet[j];
vet[j]=vet[j-1];
vet[j-1]=aux;
}
}
Pesquisa sequencial 
- O vetor não precisa estar ordenado logo, é smples.
- A busca é mais simples porque percorre-se o vetor pelo índice
- Retorna a posição do elemento e não o elemento.
Cout <<”\n..?”;
Cin>> varprocura;
Achou=0;
For (l=0<tamlinha && achou==0;L++){
If (varprocura==vetor[l]{
Achou=1; 
posição=l;
}}
If (achou==1)
Cout<< “\n..:<<outrovetor[posição]<<endl;
Else
Cout<< “\nDado não achado\n”;
Binaria
-O vetor tem que estar ordenado
-Divide-se, sucessivamente, o vetor ao meio, comparando o elemento procurado com a posição central, descartando metade do vetor
-É Mais eficiente que a busca sequencial
Cout<<”\n...?”;
Cin>>procura;
Incio=0;
Fim=tamanho-1;
Meio=(inicio+fim)/2;
While (procura != nomevetor[meio] && inicio != fim) {
If (procura >nomevetor[meio])
Inicio=meio+1;
Else {
Fim=meio;
Meio=(incio+fim)/2;
}
If (nomevetor[meio]==procura)
Cout <<”\n...:” <<outrovetor[meio]<<endl;
Else
Cout <<”\n Dado não encontrado\n”;
Pilha ( LAST IN FIRST OUT )
Uma pilha é um tipo especial de lista linear em que todas as operações de inserção e remoção são realizadas numa mesma extremidade, denominada topo.
//pilha não se lista, não se ordena.
- Inserção ou remoção de elementos sempre acontecem nas exterminardes 
- Não existe movimentação na pilha quando inserimos ou removemos um elemento dela 
-Podemos usar matrizes homogêneas ou heterogêneas, alocação sequencial e uma variável para controlar o topo.
- Um dos fatores que limita o crescimento da pilha é a quantidade de memoria alocada quando usamos matrizes 
- Quando formos empilhar um elemento, é preciso verificar se a pilha não esta cheia. Isso evita overflow.
- Quando formos desempilhar um elemento é preciso verificar se a pilha não esta vazia. Isso evita underflow.
#include<iostream>
#include<cstdlib>
#define TAM 40
Using namespace std;
Void empilha (int [p], int &t, int v);
Void desimpilha (int [p], int &t);
Int main (){
int topo=-1,pilha[TAM]