Wyszukiwanie binarne słów

0

Witam. Mam problem z napisaniem programu, ktory bedzie w ciagu słów wyszukiwał słowa, ktore znajduja sie w uporzadkowanym alfabetycznie pliku.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
using namespace std;

int main(){
	string slowa="piotrek kasia zosia ala ewa jan kuba"; //to co chcemy przeszukać
	vector <string> slowa2;
	
	fstream plik;
	plik.open("slowa.txt", ios::in); //plik z lista slow - imion
	
	if(!plik){
 		cout << "Plik nie zostal otwarty" << endl;
 		return 1;
 	}
	
	lover_bound(slowa2.begin(), slowa2.end(), plik);
	
	return 0;
}

Próbowalem z czyms takim, ale nie wiem, czy nawet to jest dobry pomysł :/

0
  1. Prościej przez: http://www.cplusplus.com/reference/algorithm/binary_search/
  2. Co w czym masz wyszukiwać, zdecyduj się.
  3. Bez uprzedniego wczytania całego pliku (ewentualnie można wczytać tylko pozycje słów w pliku), np do vectora - nie da się.
0

Tylko jak w takim razie mam posortować swojego stringa?
bo w tym przykladzie na stronce sortuje tablice intów i pozniej wyszukuje konkretnej wartosci tam, np 3. a jak mam plik z 100 imionami?

0
goal napisał(a):

Tylko jak w takim razie mam posortować swojego stringa?
Nie widzę nic takiego w podanym przez ciebie zadaniu.

0

uzywajac funkcji binary_search podaje tam, to co chce przeszukać, koniec i poczatek wektora, oraz wartość która chce znaleźć, tak?

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
using namespace std;

int main(){
	string slowa="piotrek kasia zosia ala ewa jan kuba"; //to co chcemy przeszukać
	vector <string> slowa2(slowa.size(), slowa);
	
	
	fstream plik;
	plik.open("slowa.txt", ios::in); //plik z lista slow - imion
	
	if(!plik){
 		cout << "Plik nie zostal otwarty" << endl;
 		return 1;
 	}
	if(	binary_search(slowa2.begin(), slowa2.end(), "ala")){
            cout<<"znaleziono";
       }
	
	return 0;
}

tak to powinno wyglądać, tak?

ale co, jesli mam w pliku 100 wyrazów, to jak sprawdzać po kolei czy którys z wyrazów z pliku wystepuje w moim ciagu imion? zeby nie wpisywać w funkcji binary_search konkretnego imienia?

//mam wyszukać czy w moim stringu slowa znajduje się słowa z pliku

0

http://ideone.com/RkS1Z6

#include <unordered_set>
#include <string>
#include <iostream>
using namespace std;
 
int main()
  {
   unordered_set<string> slowa{"piotrek","kasia","zosia","ala","ewa","jan","kuba"};
   if(slowa.find("ala")!=slowa.end()) cout<<"znaleziono";
   return 0;
  }

Tylko wg tekstu masz słowa wyszukiwać w pliku a nie na odwrót jak próbujesz.
Po to ci podano że plik jest uporządkowany aby ułatwić szukanie słów w nim.

Owszem jest możliwość że autor zadania chciał aby odszukałeś te słowa w pliku bez ładowania całego pliku do pamięci,
tworząc algorytm podobny do scalania dwóch zbiorów uporządkowanych, porzucasz minimalny element, jeżeli zaś brak minimalnego to mamy trafienie i porzucamy z obu zbiorów.

0

tak, bo wlasciwie jesli w tym moim stringu z imionami, znajduje sie jakies słowo, które również znajduje sie w pliku, mam je z tego stringa usunąć.
i tak, ciagle szukam odwrotnie, dzieki za spostrzeżenie.

w takim razie jak sie do tego zabrać, moze lower_bound?

0

Możesz użyć: lower_bound, binary_search, unordered_set lub algorytm który opisałem w poprzednim poście lub wiele innych rozwiązań w zależności od tego co potrzebujesz zrobić.
Zaś co potrzebujesz zrobić tego nie wiem.

0

konkretnie no to, mam jakiś string w którym zawarte są różne słowa (jest wynikiem wcześniejszych działań programu) oraz mam plik z posortowanymi słowami. Wynikiem moich działań ma być zwrócenie słów, które znajdują się w owym stringu, a nie znajdują się w pliku ze słowami.

Moim pomyslem bylo to, zeby jesli któreś ze słów z owego stringa znajduje się również w pliku ze słowami, usunąć je z tego stringa.

0

To unordered_set - będzie najbardziej pożyteczny.

0

a jak działa unordered_set? nie mialem z tym nigdzie stycznosci a ciezko znalezc cos z dobrym przykladem po polsku

0

Nie potrzebujesz przykład po polsku, potrzebujesz przykład po C++ - jest w każdej przyzwoitej dokumentacji.

0
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

int main(){
	string slowa="piotrek kasia zosia ala ewa jan kuba"; //to co chcemy przeszukać
	unordered_set <string> slowa2 = slowa;
	
	
	fstream plik;
	plik.open("words.txt", ios::in); //plik z lista slow - imion
	
	if(!plik){
 		cout << "Plik nie zostal otwarty" << endl;
 		return 1;
 	}
	
	string slowo;
	
	while(getline(plik, slowo)){
		unordered_set<string>const_iterator got = slowa2.find (slowo);
		if ( got == slowa2.end() )
    cout << "not found in slowa2";
  	else
    cout << *got << " is in slowa2";
	}

	return 0;
}

tak to znajdywać?

0
#include <string>
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <unordered_set>
using namespace std;
 
int main() 
  {
   vector<string> input { "siema", "herbata", "krzeslo" };
   unordered_set<string> drop { "herbata" };
   vector<string> result;
   copy_if
     (
      begin(input),end(input),back_inserter(result),
      [&drop](const string &s) { return drop.find(s)==drop.end(); } 
     );
   ostream_iterator<string> iout(cout,"\n");
   copy(begin(result),end(result),iout);
   return 0;
  }

To nawet przykład napisany przez ciebie.
Tylko co w wypadku, kiedy ciąg słów wygląda tak "piotrek kasia zosia ala ewa jan kuba" ?

0

Ehhh ... dopóki gotowca nie dostanie ... :/

#include <string>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
 
inline void fatal(bool bad,const char *msg) { if(bad) exit((cerr<<msg<<endl).good()); }
 
int main()
  {
   istringstream sin("piotrek kasia zosia ala ewa jan kuba");
   istream_iterator<string> b(sin),e;
   unordered_set<string> wordset(b,e);   
   ifstream fin("smiec.cpp");
   fatal(!fin,"Plik nie zostal otwarty");
   for(string word;fin>>word;) wordset.erase(word);
   for(auto &word:wordset) cout<<word<<' ';
   return 0;
  }

1 użytkowników online, w tym zalogowanych: 0, gości: 1