tou com algumas dificuldades a descubrir onde está o erro…aqui vai o codigo…se alguem descobrir me diga!!!
obrigado
-
Dicionário com estrutura de um ARRAY para implementar:
-
- Pesquisa digital
-
- Pesquisa Sequencial exaustiva
-
- Pesquisa Sequencial esfomeada
-
- Pesquisa binária
-
- Pesquisa interpolativa
*/
public class DicionarioArray {
private no[] nos; private int N; private int contudo;
private class no{
public int ID; //item_type
public int info; //info_typepublic no(int id,int data){ ID=id; info=data; } }
public DicionarioArray(int max){ N=max; nos=new no[N]; contudo=0; }
public DicionarioArray(int max,int l,int r,int extensao){ N=max;nos=new no[N]; contudo=Math.min(N,r-l); max=l+Math.min(N,r-l);
for(int i=l,j=0;i<max;++i,++j) nos[j]=new no(i,(int)Math.round(Math.random()*extensao)); }
public void presentar(){ for (int i=0;i<contudo;++i) System.out.print("["+i+"]=<a>ID:"+nos[i].ID+",Info:"+nos[i].info+"</a> "); System.out.println(); } private int pesquisa_digital(int id){ if (id>-1&&id<contudo) return nos[id].info; else return -1; }
private int pesquisa_seq_exaustiva(int id){ for(int i=0;i<contudo;i++) if (nos[i].ID==id) return nos[i].info; return -1; }
private int pesquisa_seq_esfomeada(int id){ for(int i=0;i<contudo&&nos[i].ID<=id;i++) if (nos[i].ID==id) return nos[i].info; return -1; }
private int pesquisa_binaria(int id){ int l=0,r=contudo-1,x; while (r>=l){ x=(l+r)/2; if (id==nos[x].ID) return nos[x].info; if (id<nos[x].ID) r=x-1; else l=x+1; } return -1; }
private int pesquisa_interpolativa(int id){ int l=0,r=contudo-1,x; while (r>l){ x=(id-nos[l].ID)*(r-l)/(nos[l].ID-nos[l].ID); if (id==nos[x].ID) return nos[x].info; if (id<nos[x].ID) r=x-1; else l=x+1; } return -1; }
public static void main(String[] args){ int N=100,l=0,r=10,extensao=4; DicionarioArray Dicionario=new DicionarioArray(N,l,r,extensao); Dicionario.presentar();
for (int i=0;i<Dicionario.contudo-1;++i){ int key=((int)Math.round(Math.random()*2*(r-l))); System.out.println("Procura da Informação attribuido ao Chave "+key+":"); System.out.println(" - De acordo com a Pesquisa digital:"+Dicionario.pesquisa_digital(key)); System.out.println(" - De acordo com a Pesquisa sequencial exaustiva:"+Dicionario.pesquisa_seq_exaustiva(key)); System.out.println(" - De acordo com a Pesquisa sequencial esfomeada:"+Dicionario.pesquisa_seq_esfomeada(key)); System.out.println(" - De acordo com a Pesquisa binária:"+Dicionario.pesquisa_binaria(key)); System.out.println(" - De acordo com a Pesquisa interpolativa:"+Dicionario.pesquisa_interpolativa(key)); } }
}
- Pesquisa interpolativa
