Cola Prova 2

Prévia do material em texto

public class ArvoreArvore {
private No raiz;
public ArvoreArvore() {
raiz = null;
inserir('M');
inserir('T');
inserir('F'); }
public void inserir(char letra){ }
public void inserir(String s){
inserir(s, raiz); }
public void inserir(String s, No i) throws Exception {
if (i == null) {
throw new Exception("Erro ao inserir: caractere invalido!");
} else if (s.charAt(0) < i.elemento) {
inserir(x, i.esq);
} else if (s.charAt(0) > i.elemento) {
inserir(x, i.dir);
} else {
i.outro = inserir(s, i.outro); } }
private No2 inserir(String s, No2 i) throws Exception {
if (i == null) {
i = new No2(x);
} else if (s.compareTo(i.elemento) < 0) {
i.esq = inserir(x, i.esq);
} else if (s.compareTo(i.elemento) > 0) {
i.dir = inserir(x, i.dir);
} else {
throw new Exception("Erro ao inserir: elemento existente!"); }
return i; }
public void mostrar(){
mostrar(raiz); }
public void mostrar(No i){
if (i != null){
mostrar(i.esq);
mostrar(i.outra);
mostrar(i.dir); } }
public void mostrar(No2 i){
if (i != null){
mostrar(i.esq);
System.out.println(i.elemento);
mostrar(i.dir); } }
public boolean hasStringTam10(){
return hasStringTam10(raiz); }
public boolean hasStringTam10(No i){
boolean resp = false;
if(i != null){
resp = hasStringTam10(i.outro) || hasStringTam10(i.esq) ||
hasStringTam10(i.dir); }
return resp; }
public boolean hasStringTam10(No2 i){
boolean resp = false;
if(i != null){
resp = i.elemento.length() == 10 || hasStringTam10(i.esq) ||
hasStringTam10(i.dir); }
return resp; }
public boolean hasStringTam10(char c){
return hasStringTam10(raiz, c); }
public boolean hasStringTam10(No i, char c){
boolean resp;
if (i == null) {
resp = false;
} else if (c < i.elemento) {
resp = hasStringTam10(i.esq, c);
} else if (c > i.elemento) {
resp = hasStringTam10(i.dir, c);
} else {
resp = hasStringTam10(i.outro); }
return resp; }
public boolean pesquisar(String elemento) {
return pesquisar(raiz, elemento); }
private boolean pesquisar(No no, String x) {
boolean resp;
if (no == null) {
resp = false;
} else if (x.charAt(0) < no.elemento) {
resp = pesquisar(no.esq, x);
} else if (x.charAt(0) > no.elemento) {
resp = pesquisar(no.dir, x);
} else {
resp = pesquisarSegundaArvore(no.outro, x); }
return resp; }
private boolean pesquisarSegundaArvore(No2 no, String x) {
boolean resp;
if (no == null) {
resp = false;
} else if (x.compareTo(no.elemento) < 0) {
resp = pesquisarSegundaArvore(no.esq, x);
} else if (x.compareTo(no.elemento) > 0) {
resp = pesquisarSegundaArvore(no.dir, x);
} else {
resp = true; }
return resp; }
public int contPalavra(char letra){
return contPalavra(letra, raiz); }
public int contPalavra(char letra, No i) throws Exception {
int resp = 0;
if (i == null) {
throw new Exception("Erro ao pesquisar: caractere invalido!");
} else if (letra < i.elemento) {
resp = contPalavra(letra, i.esq);
} else if (letra > i.elemento) {
resp = contPalavra(letra, i.dir);
} else {
resp = contPalavra(i.outro); }
return resp; }
public int contPalavra(No2 i){
int resp = 0;
if(i != null){
resp = 1 + contPalavra(i.esq) + contPalavra(i.dir); }
return resp; } }
—----------------------------------------------------------------------------------------------------
class ArvoreTrie {
private No raiz;
public ArvoreTrie(){
raiz = new No(); }
public boolean pesquisar(String s) throws Exception {
return pesquisar(s, raiz, 0); }
public boolean pesquisar(String s, No no, int i) throws Exception {
boolean resp;
public class ArvoreBinaria {
private No raiz;
public ArvoreBinaria() {
raiz = null; }
public boolean pesquisar(int x) {
return pesquisar(x, raiz); }
private boolean pesquisar(int x, No i) {
boolean resp;
if (i == null) {
resp = false;
} else if (x == i.elemento) {
resp = true;
} else if (x < i.elemento) {
resp = pesquisar(x, i.esq);
} else {
resp = pesquisar(x, i.dir); }
return resp; }
public void caminharCentral() {
System.out.print("[ ");
caminharCentral(raiz);
System.out.println("]"); }
private void caminharCentral(No i) {
if (i != null) {
caminharCentral(i.esq);
System.out.print(i.elemento + " ");
caminharCentral(i.dir); } }
public void caminharPre() {
System.out.print("[ ");
caminharPre(raiz);
System.out.println("]"); }
private void caminharPre(No i) {
if (i != null) {
System.out.print(i.elemento + " ");
caminharPre(i.esq);
caminharPre(i.dir); } }
public void caminharPos() {
System.out.print("[ ");
caminharPos(raiz);
System.out.println("]"); }
private void caminharPos(No i) {
if (i != null) {
caminharPos(i.esq);
caminharPos(i.dir);
System.out.print(i.elemento + " "); } }
public void inserir(int x) throws Exception {
raiz = inserir(x, raiz); }
private No inserir(int x, No i) throws Exception {
if (i == null) {
i = new No(x);
} else if (x < i.elemento) {
i.esq = inserir(x, i.esq);
} else if (x > i.elemento) {
i.dir = inserir(x, i.dir);
} else {
throw new Exception("Erro ao inserir!"); }
return i; }
public void inserirPai(int x) throws Exception {
if(raiz == null){
raiz = new No(x);
} else if(x < raiz.elemento){
inserirPai(x, raiz.esq, raiz);
} else if(x > raiz.elemento){
inserirPai(x, raiz.dir, raiz);
} else {
throw new Exception("Erro ao inserirPai!"); } }
private void inserirPai(int x, No i, No pai) throws Exception {
if (i == null) {
if(x < pai.elemento){
pai.esq = new No(x);
} else {
pai.dir = new No(x); }
} else if (x < i.elemento) {
inserirPai(x, i.esq, i);
} else if (x > i.elemento) {
inserirPai(x, i.dir, i);
} else {
throw new Exception("Erro ao inserirPai!"); } }
public void remover(int x) throws Exception {
raiz = remover(x, raiz); }
private No remover(int x, No i) throws Exception {
if (i == null) {
throw new Exception("Erro ao remover!");
} else if (x < i.elemento) {
i.esq = remover(x, i.esq);
} else if (x > i.elemento) {
i.dir = remover(x, i.dir);
} else if (i.dir == null) {
i = i.esq;
} else if (i.esq == null) {
i = i.dir;
} else {
i.esq = maiorEsq(i, i.esq); }
return i; }
private No maiorEsq(No i, No j) {
if (j.dir == null) {
i.elemento = j.elemento;
j = j.esq;
} else {
j.dir = maiorEsq(i, j.dir); }
return j; }
public int getMaior(){
int resp = -1;
if(raiz != null){
No i;
for(i = raiz; i.dir != null; i = i.dir);
resp = i.elemento; }
return resp; }
public int getMenor(){
int resp = -1;
if(raiz != null){
No i;
for(i = raiz; i.esq != null; i = i.esq);
resp = i.elemento; }
return resp; }
public int getAltura(){
return getAltura(raiz, 0); }
public int getAltura(No i, int altura){
if(i == null){
altura--;
public class Alvinegra {
private NoAN raiz;
public Alvinegra() {
raiz = null; }
public boolean pesquisar(int elemento) {
return pesquisar(elemento, raiz); }
private boolean pesquisar(int elemento, NoAN i) {
boolean resp;
if (i == null) {
resp = false;
} else if (elemento == i.elemento) {
resp = true;
} else if (elemento < i.elemento) {
resp = pesquisar(elemento, i.esq);
} else {
resp = pesquisar(elemento, i.dir); }
return resp; }
public void caminharCentral() {
System.out.print("[ ");
caminharCentral(raiz);
System.out.println("]");
}
private void caminharCentral(NoAN i) {
if (i != null) {
caminharCentral(i.esq);
System.out.print(i.elemento + ((i.cor) ? "(p) " : "(b) "));
caminharCentral(i.dir); } }
public void caminharPre() {
System.out.print("[ ");
caminharPre(raiz);
System.out.println("]"); }
private void caminharPre(NoAN i) {
if (i != null) {
System.out.print(i.elemento + ((i.cor) ? "(p) " : "(b) "));
caminharPre(i.esq);
caminharPre(i.dir); } }
public void caminharPos() {
System.out.print("[ ");
caminharPos(raiz);
System.out.println("]");
}
private void caminharPos(NoAN i) {
if (i != null) {
caminharPos(i.esq);
caminharPos(i.dir);
System.out.print(i.elemento + ((i.cor) ? "(p) " : "(b) ")); } }
public void inserir(int elemento) throws Exception {
if (raiz == null) {
raiz = new NoAN(elemento);
System.out.println("Antes, zero elementos. Agora, raiz(" +
raiz.elemento + ").");
} else if (raiz.esq == null && raiz.dir == null) {
if (elemento < raiz.elemento) {
raiz.esq = new NoAN(elemento);
System.out.println("Antes, um elemento. Agora, raiz(" +
raiz.elemento+ ") e esq(" + raiz.esq.elemento + ").");
} else {
raiz.dir = new NoAN(elemento);
System.out.println("Antes, um elemento. Agora, raiz(" +
raiz.elemento + ") e dir(" + raiz.dir.elemento + ")."); }
} else if (raiz.esq == null) {
if (elemento < raiz.elemento) {
raiz.esq = new NoAN(elemento);
System.out.println("Antes, dois elementos(A). Agora, raiz(" +
raiz.elemento + "), esq (" + raiz.esq.elemento + ") e dir(" + raiz.dir.elemento +
").");
} else if (elemento < raiz.dir.elemento) {
raiz.esq = new NoAN(raiz.elemento);
raiz.elemento = elemento;
System.out.println("Antes, dois elementos(B). Agora, raiz(" +
raiz.elemento + "), esq (" + raiz.esq.elemento + ") e dir(" + raiz.dir.elemento +
").");
} else {
raiz.esq = new NoAN(raiz.elemento);
raiz.elemento = raiz.dir.elemento;
raiz.dir.elemento = elemento;
System.out.println("Antes, dois elementos(C). Agora, raiz(" +
raiz.elemento + "), esq (" + raiz.esq.elemento + ") e dir(" + raiz.dir.elemento +
")."); }
raiz.esq.cor = raiz.dir.cor = false;
} else if (raiz.dir == null) {
if (elemento > raiz.elemento) {
raiz.dir = new NoAN(elemento);
System.out.println("Antes, dois elementos(D). Agora, raiz(" +
raiz.elemento + "), esq (" + raiz.esq.elemento + ") e dir(" + raiz.dir.elemento +
").");
} else if (elemento > raiz.esq.elemento) {
raiz.dir = new NoAN(raiz.elemento);
raiz.elemento = elemento;
System.out.println("Antes, dois elementos(E). Agora, raiz(" +
raiz.elemento + "), esq (" + raiz.esq.elemento + ") e dir(" + raiz.dir.elemento +
").");
} else {
raiz.dir = new NoAN(raiz.elemento);
raiz.elemento = raiz.esq.elemento;
raiz.esq.elemento = elemento;
System.out.println("Antes, dois elementos(F). Agora, raiz(" +
raiz.elemento + "), esq (" + raiz.esq.elemento + ") e dir(" + raiz.dir.elemento +
")."); }
raiz.esq.cor = raiz.dir.cor = false;
} else {
System.out.println("Arvore com tres ou mais elementos...");
inserir(elemento, null, null, null, raiz); }
raiz.cor = false; }
private void balancear(NoAN bisavo, NoAN avo, NoAN pai, NoAN i) {
if (pai.cor == true) {
if (pai.elemento > avo.elemento) {
if (i.elemento > pai.elemento) {
avo = rotacaoEsq(avo);
} else {
avo = rotacaoDirEsq(avo); }
} else {
if (i.elemento < pai.elemento) {
avo = rotacaoDir(avo);
} else {
avo = rotacaoEsqDir(avo); } }
if (bisavo == null) {
raiz = avo;
} else if (avo.elemento < bisavo.elemento) {
public class AVL {
private No raiz;
public AVL() {
raiz = null; }
public boolean pesquisar(int x) {
return pesquisar(x, raiz); }
private boolean pesquisar(int x, No i) {
boolean resp;
if (i == null) {
resp = false;
} else if (x == i.elemento) {
resp = true;
} else if (x < i.elemento) {
resp = pesquisar(x, i.esq);
} else {
resp = pesquisar(x, i.dir); }
return resp; }
public void caminharCentral() {
System.out.print("[ ");
caminharCentral(raiz);
System.out.println("]"); }
private void caminharCentral(No i) {
if (i != null) {
caminharCentral(i.esq);
System.out.print(i.elemento + " ");
caminharCentral(i.dir); } }
public void caminharPre() {
System.out.print("[ ");
caminharPre(raiz);
System.out.println("]"); }
private void caminharPre(No i) {
if (i != null) {
System.out.print(i.elemento + "(fator " + (No.getNivel(i.dir) -
No.getNivel(i.esq)) + ") "); // Conteudo do no.
caminharPre(i.esq);
caminharPre(i.dir); } }
public void caminharPos() {
System.out.print("[ ");
caminharPos(raiz);
System.out.println("]"); }
private void caminharPos(No i) {
if (i != null) {
caminharPos(i.esq);
caminharPos(i.dir);
System.out.print(i.elemento + " "); } }
public void inserir(int x) throws Exception {
raiz = inserir(x, raiz); }
private No inserir(int x, No i) throws Exception {
if (i == null) {
i = new No(x);
} else if (x < i.elemento) {
i.esq = inserir(x, i.esq);
} else if (x > i.elemento) {
i.dir = inserir(x, i.dir);
} else {
throw new Exception("Erro ao inserir!"); }
return balancear(i); }
public void remover(int x) throws Exception {
raiz = remover(x, raiz); }
private No remover(int x, No i) throws Exception {
if (i == null) {
throw new Exception("Erro ao remover!");
} else if (x < i.elemento) {
i.esq = remover(x, i.esq);
} else if (x > i.elemento) {
i.dir = remover(x, i.dir);
} else if (i.dir == null) {
i = i.esq;
} else if (i.esq == null) {
i = i.dir;
} else {
i.esq = maiorEsq(i, i.esq); }
return balancear(i); }
private No maiorEsq(No i, No j) {
if (j.dir == null) {
i.elemento = j.elemento;
j = j.esq;
} else {
j.dir = maiorEsq(i, j.dir); }
return j; }
private No balancear(No no) throws Exception {
if (no != null) {
int fator = No.getNivel(no.dir) - No.getNivel(no.esq);
if (Math.abs(fator) <= 1) {
no.setNivel();
} else if (fator == 2) {
int fatorFilhoDir = No.getNivel(no.dir.dir) - No.getNivel(no.dir.esq);
if (fatorFilhoDir == -1) {
no.dir = rotacionarDir(no.dir); }
no = rotacionarEsq(no);
} else if (fator == -2) {
int fatorFilhoEsq = No.getNivel(no.esq.dir) -
No.getNivel(no.esq.esq);
if (fatorFilhoEsq == 1) {
no.esq = rotacionarEsq(no.esq); }
no = rotacionarDir(no);
} else {
throw new Exception(
"Erro no No(" + no.elemento + ") com fator de balanceamento
(" + fator + ") invalido!"); } }
return no; }
private No rotacionarDir(No no) {
System.out.println("Rotacionar DIR(" + no.elemento + ")");
No noEsq = no.esq;
No noEsqDir = noEsq.dir;
noEsq.dir = no;
no.esq = noEsqDir;
no.setNivel();
noEsq.setNivel();
return noEsq; }
private No rotacionarEsq(No no) {
System.out.println("Rotacionar ESQ(" + no.elemento + ")");
No noDir = no.dir;
No noDirEsq = noDir.esq;
noDir.esq = no;
no.dir = noDirEsq;
no.setNivel();
noDir.setNivel();
return noDir; } }
if(no.prox[s.charAt(i)] == null){
resp = false;
} else if(i == s.length() - 1){
resp = (no.prox[s.charAt(i)].folha == true);
} else if(i < s.length() - 1 ){
resp = pesquisar(s, no.prox[s.charAt(i)], i + 1);
} else {
throw new Exception("Erro ao pesquisar!"); }
return resp; }
public void inserir(String s) throws Exception {
inserir(s, raiz, 0); }
private void inserir(String s, No no, int i) throws Exception {
System.out.print("\nEM NO(" + no.elemento + ") (" + i + ")");
if(no.prox[s.charAt(i)] == null){
System.out.print("--> criando filho(" + s.charAt(i) + ")");
no.prox[s.charAt(i)] = new No(s.charAt(i));
if(i == s.length() - 1){
System.out.print("(folha)");
no.prox[s.charAt(i)].folha = true;
}else{
inserir(s, no.prox[s.charAt(i)], i + 1); }
} else if (no.prox[s.charAt(i)].folha == false && i < s.length() - 1){
inserir(s, no.prox[s.charAt(i)], i + 1);
} else {
throw new Exception("Erro ao inserir!"); } }
public void mostrar(){
mostrar("", raiz); }
public void mostrar(String s, No no) {
if(no.folha == true){
System.out.println("Palavra: " + (s + no.elemento));
} else {
for(int i = 0; i < no.prox.length; i++){
if(no.prox[i] != null){
System.out.println("ESTOU EM (" + no.elemento + ") E VOU
PARA (" + no.prox[i].elemento + ")");
mostrar(s + no.elemento, no.prox[i]); } } } }
public int contarAs(){
int resp = 0;
if(raiz != null){
resp = contarAs(raiz); }
return resp; }
public int contarAs(No no) {
int resp = (no.elemento == 'A') ? 1 : 0;
if(no.folha == false){
for(int i = 0; i < no.prox.length; i++){
if(no.prox[i] != null){
resp += contarAs(no.prox[i]); } } }
return resp; } }
—----------------------------------------------------------------------------------------------------
public class Hash {
int tabela[];
int m1, m2, m, reserva;
final int NULO = -1;
public Hash() {
this(13, 7); }
public Hash(int m1, int m2) {
this.m1 = m1;
this.m2 = m2;
this.m = m1 + m2;
this.tabela = new int[this.m];
for (int i = 0; i < m1; i++) {
tabela[i] = NULO; }
reserva = 0; }
public int h(int elemento) {
return elemento % m1; }
public boolean inserir(int elemento) {
boolean resp = false;
if (elemento != NULO) {
int pos = h(elemento);
if (tabela[pos] == NULO) {
tabela[pos] = elemento;
resp = true;
} else if (reserva < m2) {
tabela[m1 + reserva] = elemento;
reserva++;
resp = true; } }
return resp; }
public boolean pesquisar(int elemento) {
boolean resp = false;
int pos = h(elemento);
if (tabela[pos] == elemento) {
resp = true;
} else if (tabela[pos] !=NULO) {
for (int i = 0; i < reserva; i++) {
if (tabela[m1 + i] == elemento) {
resp = true;
i = reserva; } } }
return resp; }
boolean remover(int elemento) {
boolean resp = false;
return resp; } }
} else {
int alturaEsq = getAltura(i.esq, altura + 1);
int alturaDir = getAltura(i.dir, altura + 1);
altura = (alturaEsq > alturaDir) ? alturaEsq : alturaDir; }
return altura; }
public void remover2(int x) throws Exception {
if (raiz == null) {
throw new Exception("Erro ao remover2!");
} else if(x < raiz.elemento){
remover2(x, raiz.esq, raiz);
} else if (x > raiz.elemento){
remover2(x, raiz.dir, raiz);
} else if (raiz.dir == null) {
raiz = raiz.esq;
} else if (raiz.esq == null) {
raiz = raiz.dir;
} else {
raiz.esq = maiorEsq(raiz, raiz.esq); } }
private void remover2(int x, No i, No pai) throws Exception {
if (i == null) {
throw new Exception("Erro ao remover2!");
} else if (x < i.elemento) {
remover2(x, i.esq, i);
} else if (x > i.elemento) {
remover2(x, i.dir, i);
} else if (i.dir == null) {
pai = i.esq;
} else if (i.esq == null) {
pai = i.dir;
} else {
i.esq = maiorEsq(i, i.esq); } }
public int getRaiz() throws Exception {
return raiz.elemento; }
public static boolean igual (ArvoreBinaria a1, ArvoreBinaria a2){
return igual(a1.raiz, a2.raiz); }
private static boolean igual (No i1, No i2){
boolean resp;
if(i1 != null && i2 != null){
resp = (i1.elemento == i2.elemento) && igual(i1.esq, i2.esq) &&
igual(i1.dir, i2.dir);
} else if(i1 == null && i2 == null){
resp = true;
} else {
resp = false; }
return resp; }
public int soma(){
return soma(raiz); }
public int soma(No i){
int resp = 0;
if(i != null){
resp = i.elemento + soma(i.esq) + soma(i.dir); }
return resp; }
public int quantidadePares(){
return quantidadePares(raiz); }
public int quantidadePares(No i){
int resp = 0;
if(i != null){
resp = ((i.elemento % 2 == 0) ? 1 : 0) + quantidadePares(i.esq) +
quantidadePares(i.dir); }
return resp; }
public boolean hasDiv11(){
return hasDiv11(raiz); }
public boolean hasDiv11(No i){
boolean resp = false;
if(i != null){
resp = (i.elemento % 11 == 0) || hasDiv11(i.esq) || hasDiv11(i.dir); }
return resp; } }
—----------------------------------------------------------------------------------------------------
public class HashIndiretoLista {
Lista tabela[];
int tamanho;
final int NULO = -1;
public HashIndiretoLista() {
this(7); }
public HashIndiretoLista(int tamanho) {
this.tamanho = tamanho;
tabela = new Lista[tamanho];
for (int i = 0; i < tamanho; i++) {
tabela[i] = new Lista(); } }
public int h(int elemento) {
return elemento % tamanho; }
boolean pesquisar(int elemento) {
int pos = h(elemento);
return tabela[pos].pesquisar(elemento); }
public void inserirInicio(int elemento) {
int pos = h(elemento);
tabela[pos].inserirInicio(elemento); }
public int remover(int elemento) {
int resp = NULO;
if (pesquisar(elemento) == false) {
throw new Exception("Erro ao remover!");
} else {
int pos = h(elemento);
resp = tabela[pos].remover(elemento); }
return resp; } }
bisavo.esq = avo;
} else {
bisavo.dir = avo; }
avo.cor = false;
avo.esq.cor = avo.dir.cor = true;
System.out.println("Reestabeler cores: avo(" + avo.elemento +
"->branco) e avo.esq / avo.dir("
+ avo.esq.elemento + "," + avo.dir.elemento + "-> pretos)"); } }
private void inserir(int elemento, NoAN bisavo, NoAN avo, NoAN pai,
NoAN i) throws Exception {
if (i == null) {
if (elemento < pai.elemento) {
i = pai.esq = new NoAN(elemento, true);
} else {
i = pai.dir = new NoAN(elemento, true); }
if (pai.cor == true) {
balancear(bisavo, avo, pai, i); }
} else {
if (i.esq != null && i.dir != null && i.esq.cor == true && i.dir.cor == true) {
i.cor = true;
i.esq.cor = i.dir.cor = false;
if (i == raiz) {
i.cor = false;
} else if (pai.cor == true) {
balancear(bisavo, avo, pai, i); } }
if (elemento < i.elemento) {
inserir(elemento, avo, pai, i, i.esq);
} else if (elemento > i.elemento) {
inserir(elemento, avo, pai, i, i.dir);
} else {
throw new Exception("Erro inserir (elemento repetido)!"); } } }
private NoAN rotacaoDir(NoAN no) {
System.out.println("Rotacao DIR(" + no.elemento + ")");
NoAN noEsq = no.esq;
NoAN noEsqDir = noEsq.dir;
noEsq.dir = no;
no.esq = noEsqDir;
return noEsq; }
private NoAN rotacaoEsq(NoAN no) {
System.out.println("Rotacao ESQ(" + no.elemento + ")");
NoAN noDir = no.dir;
NoAN noDirEsq = noDir.esq;
noDir.esq = no;
no.dir = noDirEsq;
return noDir; }
private NoAN rotacaoDirEsq(NoAN no) {
no.dir = rotacaoDir(no.dir);
return rotacaoEsq(no); }
private NoAN rotacaoEsqDir(NoAN no) {
no.esq = rotacaoEsq(no.esq);
return rotacaoDir(no); } }
—----------------------------------------------------------------------------------------------------
public class HashRehash {
int tabela[];
int m;
final int NULO = -1;
public Hash() {
this(13); }
public Hash(int m) {
this.m = m;
this.tabela = new int[this.m];
for (int i = 0; i < m; i++) {
tabela[i] = NULO; } }
public int h(int elemento) {
return elemento % m; }
public int reh(int elemento) {
return ++elemento % m; }
public boolean inserir(int elemento) {
boolean resp = false;
if (elemento != NULO) {
int pos = h(elemento);
if (tabela[pos] == NULO) {
tabela[pos] = elemento;
resp = true;
} else {
pos = reh(elemento);
if (tabela[pos] == NULO) {
tabela[pos] = elemento;
resp = true; } } }
return resp; }
public boolean pesquisar(int elemento) {
boolean resp = false;
int pos = h(elemento);
if (tabela[pos] == elemento) {
resp = true;
} else if (tabela[pos] != NULO) {
pos = reh(elemento);
if (tabela[pos] == elemento) {
resp = true; } }
return resp; }
boolean remover(int elemento) {
boolean resp = false;
return resp; } }
—----------------------------------------------------------------------------------------------------
class Patricia {
No raiz;
String[] array;
public Patricia(){
raiz = new No();
array = null; }
public void setArray(String[] array) throws Exception {
this.array = array;
for(int i = 0; i < array.length; i++){
inserir(i); } }
private String string(No no){
return (no == raiz) ? " " : string(no.i, no.j, no.k); }
private String string(int i, int j, int k){
return array[i].substring(j,k+1); }
public void inserir(int i) throws Exception {
System.out.print("\n===========================================
========= INSERINDO : " + array[i]);
inserir(raiz, i, 0);
mostrar(); }
private void inserir(No no, int i, int j) throws Exception {
System.out.println("\nEM NO(" + string(no) + ") i("+ i +") j(" + j + ")");
if(no.prox[array[i].charAt(j)] == null){
no.prox[array[i].charAt(j)] = new No(i, j, array[i].length()-1, true);
System.out.print("--> criando folha(" + array[i].charAt(j) + "/" +
string(no.prox[array[i].charAt(j)]) + ")");
} else {
String prox = string(no.prox[array[i].charAt(j)]);
String inserindo = array[i].substring(j);
System.out.println("prox(" + prox + ") e inserindo(" + inserindo + ")");
int k;
for(k = 1; k < prox.length() && k < inserindo.length() && prox.charAt(k)
== inserindo.charAt(k); k++);
System.out.println("k (" + k + ")");
if(k == prox.length()){
if(no.prox[array[i].charAt(j)].folha == true){
throw new Exception("Erro: exite um prefixo de [" + array[i] + "] na
arvore");
} else {
inserir(no.prox[array[i].charAt(j)], i, j + k); }
} else if (k == inserindo.length()){
throw new Exception("Erro: [" + array[i] + "] é prefixo de outra palavra
da árvore");
} else {
No novo = new No(i, j, j + k - 1, false);
novo.prox[prox.charAt(k)] = no.prox[array[i].charAt(j)];
novo.prox[prox.charAt(k)].j = j + k;
novo.prox[inserindo.charAt(k)] = new No(i, j + k, array[i].length()-1,
true);
no.prox[array[i].charAt(j)] = novo;
System.out.println("no(" + string(no) + ") e filhoNOVO(" + string(novo)
+ ") neto1(" + string(novo.prox[inserindo.charAt(k)]) + ") neto2(" +
string(novo.prox[prox.charAt(k)]) + ")"); } } }
public boolean pesquisar(String s){
System.out.println("\n==========================================
========== PESQUISAR: " + s);
return pesquisar (raiz, s, 0); }
public boolean pesquisar (No no, String s, int cont){
boolean resp;
System.out.println("EM NO(" +string(no) + ") s("+ s +") cont(" + cont + ")
prox(" + no.prox[s.charAt(cont)] + ")");
if(no.prox[s.charAt(cont)] == null){
System.out.println("não existe filho para [" + s.charAt(cont) + "]");
resp = false;
} else {
String prox = string(no.prox[s.charAt(cont)]);
System.out.println("prox: " + prox);
int i1, i2;
for(i1 = 0, i2 = cont; i1 < prox.length() && i2 < s.length() &&
prox.charAt(i1) == s.charAt(i2); i1++, i2++);
if(i2 == s.length()){ System.out.println("resp =
consumiuTodosOsCaracteresDeProx(" + (i1 == prox.length()) + ") and
proxFolha(" + (no.prox[s.charAt(cont)].folha) + ")");
resp = i1 == prox.length() && no.prox[s.charAt(cont)].folha;
} else {
resp = pesquisar(no.prox[s.charAt(cont)], s, i2); } }
return resp; }
public void mostrar(){
System.out.println("\n==========================================
========== MOSTRAR: ");
mostrar("", raiz); }
public void mostrar(String s, No no) {
if(no.folha == true){
System.out.println("Palavra: " + (s + string(no)));
} else {
for(int i = 0; i < no.prox.length; i++){
if(no.prox[i] != null){ System.out.println("ESTOU EM (" + string(no) +
") E VOU PARA (" + string(no.prox[i]) + ")");
mostrar(s + string(no), no.prox[i]); } } } }
public int contarAs(){
int resp = 0;
if(raiz != null){
resp = contarAs(raiz); }
return resp; }
public int contarAs(No no) {
int resp = 0;
String palavra = string(no);
for(int i = 0; i < palavra.length(); i++){
if(palavra.charat(i) == 'A'){
resp++; } }
if(no.folha == false){
for(int i = 0; i < no.prox.length; i++){
if(no.prox[i] != null){
resp += contarAs(no.prox[i]); } } }
return resp; } }