Páginas: [1] 2 
|
 |
|
 Autor
|
Tema: Busqueda Binaria (Leído 1418 veces)
|
SanMagic
 Desconectado
Mensajes: 20
|
hola... aqui ando yo d nuevo d preguntona  me gustaria saber como podria implementar una busqueda binaria con un arregrlo d strings previamente ordenado alfabeticamente... se como funciona el metodo de busqueda binaria, y puedo implementarlo para numeros, pero la verdad no se como hacerle cuando se tratan d palabras... alquien me puede ayudar?? Gracias de antemadno  |
|
|
|
|
En línea
|
|
|
|
|
ghastlyX
|
Para estas cosas a mi me gusta trabajar con vectores de cadenas de esta forma: vector<string> cadena Aunque para gustos colores. Yo en mi caso para cuando tengo el vector lleno, lo ordeno alfabéticamente con sort: sort(cadena.begin(), cadena.end()); Si ya tienes tu forma para ordenarlo puedes olvidarte de esto. Ahora vamos a la búsqueda binaria. Podría ser así la función, tú hazla como más se adapte a lo que quieres hacer y como más cómodo te sea: void busqueda_binaria(int inicio, int final, vector<string> &cadena, string x)
{
//inicio es la primera posición de la lista, en principio será cero al llamar la función
//final es la última posición
//el vector contiene todas las cadenas
//x es la cadena que buscamos
int medio;
bool flag = false;
while((inicio <= final) && (!flag))
{
medio = (inicio + final) / 2;
//para comparar usamos compare() de string
if(x.compare(cadena[medio]) > 0) inicio = medio + 1;
else if(x.compare(cadena[medio]) < 0) final = medio - 1;
else flag = true;
}
if(flag) cout << "Elemento encontrado en la posicion " << medio << endl;
else cout << "El elemento no esta en la lista" << endl;
} Así ya tendrías la búsqueda binaria con palabras. Un saludo de ghastlyX  |
|
|
|
|
En línea
|
|
|
|
ҒrεακΠιи∂
Desconectado
Mensajes: 117
|
Buenas Otra forma es T *binsearch(T vector[], size_t ini, size_t length, const T str)
{
size_t mid = (ini + length) / 2;
if(ini < length){
if(vector[mid] > str)
binsearch(vector, ini, mid - 1, str);
else if(str > vector[mid])
binsearch(vector, mid + 1, length, str);
return vector + mid;
}
return NULL;
}
Disculpen si los templates no estan bien usados pero soy nuevo con eso) El operador > tiene que ser sobre-cargado Salu2, FreakMind |
|
|
|
|
En línea
|
Connoisseurs of C semantics find C++ inferior to ++C  |
|
|
SanMagic
Desconectado
Mensajes: 20
|
Gracias ghastlyX y FreakMind por su ayuda... ya pude hacer q funcionara conforme a mis necesidades ahora solo me resta una pregunta por hacerles... El programa lo hice en Windows en un programa llamado Dev C++ pero necesito pasarlo en linux, xq necesito q este funcionando junto con un programa que ya tengo hecho... para linux uso el Ubuntu y para programar ahi uso el Ajunta... pero al complilarlo me sale que no reconoce: #include <iostream> #include <string> por tanto me salen muchisimos errores... y a pesar d q es el mismito programa q si compila bien y funciona en Windows en linux no me sirve... alguna idea de como pueda arreglar esto?? De ante mano gracias por sus respuestas |
|
|
|
|
En línea
|
|
|
|
Cab Calloway
Colaborador
 Conectado
Mensajes: 4.293
|
¿? g++ -o sapiens sapiens.cpp ¿Cómo no te va a reconocer los #include? xD PD: Veo que has mirado lo de la STL, finalista |
|
|
|
|
En línea
|
Max 400; caracteres restantes: 366
|
|
|
SanMagic
Desconectado
Mensajes: 20
|
¿? g++ -o sapiens sapiens.cpp ¿Cómo no te va a reconocer los #include? xD PD: Veo que has mirado lo de la STL, finalista pues si... aunq no lo creas no los reconoce  |
|
|
|
|
En línea
|
|
|
|
Cab Calloway
Colaborador
Conectado
Mensajes: 4.293
|
¿Pero qué error te da? Te dice:
"No reconozco los #include".
Aunque viniendo de Ubuntu no me extrañaría, pero bueno xD
|
|
|
|
|
En línea
|
Max 400; caracteres restantes: 366
|
|
|
SanMagic
Desconectado
Mensajes: 20
|
a ver... especificamente el error es el siguiente... cadena2.c:1:20: error: iostream: No existe el fichero ó directorio
cadena2.c:2:18: error: string: No existe el fichero ó directorio y ya de ahi me salen muchisimos mas errores... pues precisamente porque no reconoce esos dos... bueno... espero a alguien se le ocurra algo... Gracias desde ahora |
|
|
|
|
En línea
|
|
|
|
Cab Calloway
Colaborador
Conectado
Mensajes: 4.293
|
¿Y si le pones .cpp?
|
|
|
|
|
En línea
|
Max 400; caracteres restantes: 366
|
|
|
SanMagic
Desconectado
Mensajes: 20
|
bueno... si le cambio el nombre al archivo por uno en donde la terminacion sea .cpp los errores son los siguientes: /tmp/ccdDbG2m.o: In function `__static_initialization_and_destruction_0(int, int)':
cadena2.cpp:(.text+0x23): undefined reference to `std::ios_base::Init::Init()'
/tmp/ccdDbG2m.o: In function `__tcf_0':
cadena2.cpp:(.text+0x6c): undefined reference to `std::ios_base::Init::~Init()'
/tmp/ccdDbG2m.o: In function `main':
cadena2.cpp:(.text+0xb0): undefined reference to `std::allocator<char>::allocator()'
.
.
. y asi muchos pero muchos por el estilo.... d paso pongo el codigo para que lo vean a ver si eso les ayuda a ustedes a ayudarme  #include <iostream>
#include <string>
using namespace std;
int main(){
string v[22] = {"auto", "break", "case", "conts", "continue", "default", "do", "else", "enum", "extern", "for", "goto", "if", "return", "sizeof", "struct", "switch", "ypedef", "union", "void", "volatile", "while"};
int inicio=0, fin=21, medio;
bool flag=false;
string x="return";
while((inicio<=fin) && (!flag)) {
medio=(inicio+fin)/2;
if(x.compare(v[medio])>0)
inicio=medio+1;
else if(x.compare(v[medio])<0)
fin=medio-1;
else
flag=true;
}
if(flag)
cout << "Elemento encontrado es: " << v[medio] << endl;
else cout << "El elemento: " << x << " no esta en la lista" << endl;
}
repito... en windows no me da ningun error escrito tal cual se los dejo aqui... como vera... use la sugerencia de ghastlyX ya que me parecio muy buena... Gracias desde ahora... |
|
|
|
« Última modificación: 16 Mayo 2008, 02:55 por SanMagic »
|
En línea
|
|
|
|
ҒrεακΠιи∂
Desconectado
Mensajes: 117
|
Buenas
Esta es una pregunta por las dudas (a mi me paso la primera vez q trate de usar Debian).
Ubuntu esta basado en Debian y este lo unico que te instala en la instalacion (valga la redundancia) es un sistema base y si queres el GUI. Pero las app de programacion (Anjuta, gcc, gdb, etc) no.
Instalaste el g++???
Saludos, FreakMind
|
|
|
|
|
En línea
|
Connoisseurs of C semantics find C++ inferior to ++C |
|
|
SanMagic
Desconectado
Mensajes: 20
|
instalar el g++?? estem... creo q no  o tal vez si pero no estoy segura... a ver... dime como se instala eso y yo te digo si lo hize o no, porq realmente no me acuerdo  Gracias desde ahora |
|
|
|
|
En línea
|
|
|
|
ҒrεακΠιи∂
Desconectado
Mensajes: 117
|
Buenas
De la misma forma que instalaste Anjuta, con el gestor de paquetes
Salu2, FreakMind
|
|
|
|
|
En línea
|
Connoisseurs of C semantics find C++ inferior to ++C |
|
|
SanMagic
Desconectado
Mensajes: 20
|
Hola..... gracias a todos por su ayuda.... a ver... despues d moverle un buen a mi compu, logre que me funcionara el dichoso programa en linux, solo q ahora resulta ser que lo tuve que modificar un poco para ponerlo a funcionar con el otro programa con el que debe d funcionar.... y me encuentro con el siguiente problema... bus_bin_string.c:13: error: no se puede convertir ‘std::string’ a ‘std::string*’ para el argumento ‘3’ para ‘void busqueda_binaria(int, int, std::string*, std::string)’ alguien me puede explicar a q se refiere con ese error?? xq la verdad ni la menor idea  y disculpen por preguntar tanto... pero soy nueva en esto (jajajaja se nota??  ) |
|
|
|
|
En línea
|
|
|
|
|
eagle17
|
Eso quiere decir que en la funcion busqueda binaria, el tercer argumento de la funcion es es un puntero a string, pero tu en la linea 13 estas llamando a la funcion con el tercer argumento de tipo string, revisa el tercer argumento que le pasas a la funcion Espero haberte sido de ayuda y haberme explicado mas o menos bien (yo tambien soy algo nuevo en esto) Para lo que nos necesites aqui nos tienes! Salu2 |
|
|
|
|
En línea
|
|
|
|
|
Páginas: [1] 2 
|
|
|
 |
