Ошибка сегментирования
И вот...
#include <string.h>
#include <algorithm>
#include <vector>
#include <fstream>
#include <assert.h>
#include <math.h>
#define ArrSize 100
#define MaxWordSize 100
using namespace std;
int partition(vector<string>& library,int start,int end)
{
string x = library[start];
int i = start -1, j = end+1;
while (true)
{
do {--j;} while (strcmp(library[j].c_str(),x.c_str()) > 0);
do {++i;} while (strcmp(library.c_str(),x.c_str()) < 0);
if (i < j)
swap(library,library[j]);
else
return j;
}
}
void QuickSort(vector<string>& library, int start, int end)
{
if (start<end)
{
int q = partition(library, start, end);
QuickSort(library, start, q);
QuickSort(library, q+1, end);
}
}
bool check(vector<string>& library, int pos, const string& fragment)//сравнивает,есть ли префикс
{
return pos < (int)library.size() && library[pos].find(fragment) == 0;
}
int BinarySearch(vector<string>& library,const string& fragment)
{
int start(0), end(library.size()-1);
while (start < end)
{
int middle = (start+end)/2, cmp = strcmp(library[middle].c_str(),fragment.c_str());
if (cmp >= 0)
end = middle-1;
else
start = middle+1;
}
if (check(library, start, fragment) || check(library, ++start, fragment))
return start;
return -1;
}
int BinarySearch_last(vector<string>& library,const string& fragment)
{
int start(0), end(library.size()-1);
while (start < end)
{
int middle = (start+end)/2, cmp = strcmp(library[middle].c_str(),fragment.c_str());
if (cmp >= 0)
if (string(library[middle]).find(fragment) == 0)
start = middle+1;
else
end = middle-1;
else
start = middle+1;
}
if (check(library, start, fragment) || check(library, --start, fragment))
return start;
return -1;
}
int main(int argc,char** argv)
{
ifstream inFile(argv[1],ios::in);
char temp;
inFile.get(temp);
if (inFile.eof()) return 0;
vector<string> library;
library.reserve(200*1000);
// INITIALIZATION
int lib_it(0),max_size(0);
while (true)
{
int it(0);
string tmp;
while (temp != '\n')
{
tmp.push_back(temp);
inFile.get(temp);
if (inFile.eof()) break;
}
library.push_back(tmp);
if (inFile.eof()) break;
inFile.get(temp);
if (inFile.eof()) break;
}
QuickSort(library,0,library.size()-1);
string str;
ifstream input2(argv[2],ios::in);
while (!input2.eof())
{
char temporary;
input2.get(temporary);
if (input2.eof())
break;
str.push_back(temporary);
}
int First_Index = BinarySearch(library,str);
int Last_index = BinarySearch_last(library,str);
input2.close();
//out
ofstream output("out.txt",ios::out|ios::app);
output.put('\n');
output.put('\n');
output<<"Result:"<<endl;
output<<endl;
output<<library[First_Index]<<endl;
for (int u(First_Index+1);u<=Last_index;++u)
{
if (strcmp(library.c_str(),library[u-1].c_str())!=0)
output<<library<<endl;
}
library.clear();
return 0;
}
Компилирую: g++ 1.cpp
Дальше запускаю как надо: ./a.out library.txt 1.txt
library - файл в котором искать
1 - файл в котором записано что искать
При запуске выдает "Ошибка Сегментирования"
И вот... на выходе получается out.txt,но в него записывается только "Result:"
Собственно, в чем проблема? На VisualStudio на windows работала программа.
обычно ошибка сегментирования возникает при обращении к неициализированному или удаленному объекту.
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
int partition(vector<string>& library,int start,int end)
{
string x = library[start];
int i = start -1, j = end+1;
while (true)
{
do {--j;} while (strcmp(library[j].c_str(),x.c_str()) > 0);
do {++i;} while (strcmp(library.c_str(),x.c_str()) < 0);
if (i < j)
swap(library,library[j]);
else
return j;
}
}
void QuickSort(vector<string>& library, int start, int end)
{
if (start<end)
{
int q = partition(library, start, end);
QuickSort(library, start, q);
QuickSort(library, q+1, end);
}
}
bool check(vector<string>& library, int pos, const string& fragment)//сравнивает,есть ли префикс
{
return pos < (int)library.size() && library[pos].find(fragment) == 0;
}
int BinarySearch(vector<string>& library,const string& fragment)
{
int start(0), end(library.size()-1);
while (start < end)
{
int middle = (start+end)/2, cmp = strcmp(library[middle].c_str(),fragment.c_str());
if (cmp >= 0)
end = middle-1;
else
start = middle+1;
}
if (check(library, start, fragment) || check(library, ++start, fragment))
return start;
return -1;
}
int BinarySearch_last(vector<string>& library,const string& fragment)
{
int start(0), end(library.size()-1);
while (start < end)
{
int middle = (start+end)/2, cmp = strcmp(library[middle].c_str(),fragment.c_str());
if (cmp >= 0)
if (string(library[middle]).find(fragment) == 0)
start = middle+1;
else
end = middle-1;
else
start = middle+1;
}
if (check(library, start, fragment) || check(library, --start, fragment))
return start;
return -1;
}
int main(int argc,char** argv)
{
ifstream inFile(argv[1],ios::in);
if (inFile.eof()) return 0;
vector<string> library;
int lib_it(0),max_size(0);
char * buff=new char[2048];
while (!inFile.eof())
{
inFile.getline(buff,2048);
if(strlen(buff)>0)//Пропускаем пустые строки
library.push_back(string(buff));
}
QuickSort(library,0,library.size()-1);
ifstream input2(argv[2],ios::in);
input2.getline(buff,2048);
string str(buff);
delete [] buff;
int First_Index = BinarySearch(library,str);
int Last_index = BinarySearch_last(library,str);
input2.close();
//out
ofstream output("out.txt",ios::out|ios::app);
output<<endl<<endl<<"Result:"<<endl;
output<<library[First_Index]<<endl;
for (int u(First_Index+1);u<=Last_index;++u)
{
if (strcmp(library.c_str(),library[u-1].c_str())!=0)
output<<library<<endl;
}
library.clear();
return 0;
}
P.S. на будущее если инклюдишь math.h то компиль с ключем -lm (g++ 1.cpp -lm -o a.out)
P.P.S. а какая вообще задача этой проги?
Найди семь отличий:):
inFile.get(temp);
if (inFile.eof()) return 0;
vector<string> library;
library.reserve(200*1000);
// INITIALIZATION
int lib_it(0),max_size(0);
while (true)
{
int it(0);
string tmp;
while (temp != '\n')
{
tmp.push_back(temp);
inFile.get(temp);
if (inFile.eof()) break;
}
library.push_back(tmp);
if (inFile.eof()) break;
inFile.get(temp);
if (inFile.eof()) break;
}
QuickSort(library,0,library.size()-1);
string str;
ifstream input2(argv[2],ios::in);
while (!input2.eof())
{
char temporary;
input2.get(temporary);
if (input2.eof())
break;
str.push_back(temporary);
}
vector<string> library;
int lib_it(0),max_size(0);
char * buff=new char[2048];
while (!inFile.eof())
{
inFile.getline(buff,2048);
if(strlen(buff)>0)//Пропускаем пустые строки
library.push_back(string(buff));
}
QuickSort(library,0,library.size()-1);
ifstream input2(argv[2],ios::in);
input2.getline(buff,2048);
string str(buff);
delete [] buff;
А косяк в том что RTFM!!!
Задача - сортировка быстрая...
Дык g++ автоматически libm и libstdc++ линкует. )
Вы знакомы с такими инструментами, как gdb? valgrind?
2 aks, ух ты какой gcc умный :)
P.S.
А можно комментарии к int main ??? Пожалуйста... В общих чертах... Лабу завтра сдавать...
2 aks, ух ты какой gcc умный :)
gcc не умный - он обычный. ) Просто g++ всегда вызывает gcc с линковкой libm - вот такая вот особенность. Для удобства или наоборот. Может так исторически сложилось, дабы облегчить участь забывающих libm. А может libstdc++ зависит от неё. В любом случае раньше собрав плюсовый код через вызов gcc, а не g++ можно было получить на одну зависимость меньше. ) Как сейчас не знаю.
Нет наоборот - это средства отладки. Если gdb наверно будет тяжело сходу осилить без чтения документации - просто запустите софтину под valgrind хотя бы. Большинство ошибок работы с памятью (которые собственно и приводят к сигфолту) он покажет сразу.
Как сделать чтобы выводил все похожие результаты? То есть "СТО", "СТОЛ" и т.п.
Только вот у меня получается всего 1 слово выводить... А надо поболее
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
int partition(vector<string>& library,int start,int end)
{
string x = library[start];
int i = start -1, j = end+1;
while (true)
{
do {--j;} while (strcmp(library[j].c_str(),x.c_str()) > 0);
do {++i;} while (strcmp(library.c_str(),x.c_str()) < 0);
if (i < j)
swap(library,library[j]);
else
return j;
}
}
void QuickSort(vector<string>& library, int start, int end)
{
if (start<end)
{
int q = partition(library, start, end);
QuickSort(library, start, q);
QuickSort(library, q+1, end);
}
}
bool check(vector<string>& library, int pos, string fragment)//сравнивает,есть ли префикс
{
return pos < (int)library.size() && (library[pos].find(fragment) == 0);// || fragment.find(library[pos])==0);
}
int BinarySearch(vector<string>& library,string& fragment)
{
int start(0), end(library.size()-1);
int tmp;
while (start < end)
{
int middle = (start+end)/2, cmp = strcmp(library[middle].c_str(),fragment.c_str());
if (cmp < 0)
if(start!=middle)
start = middle;
else
start = middle+1;
else
if(end!=middle)
end = middle;
else
end = middle-1;
}
if (!(check(library, start, fragment) || check(library, start+1, fragment)))
{ cout<<fragment<<" not found :("<<endl;
if(fragment.length()>1)
{
fragment=fragment.substr(0,fragment.length()-1);
cout<<"Searching for: "<<fragment<<endl;
start=BinarySearch(library,fragment);
}
}
return start;
//return -1;
}
int BinarySearch_last(vector<string>& library,string fragment)
{
int start(0), end(library.size()-1);
while (start < end)
{
int middle = (start+end)/2, cmp = library[middle].find(fragment.c_str());
if (cmp == 0)
if(start!=middle)
start = middle;
else
start = middle+1;
else
if(end!=middle)
end = middle;
else
end = middle-1;
}
//if (!(check(library, start, fragment) || check(library, start-1, fragment)) && fragment.length()>0)
// return BinarySearch_last(library,fragment.substr(0,fragment.length()-1));
//else
return start;
//return -1;
}
int main(int argc,char** argv)
{
ifstream inFile(argv[1],ios::in);
if (inFile.eof()) return 0;
vector<string> library;
int lib_it(0),max_size(0);
char * buff=new char[2048];
while (!inFile.eof())
{
inFile.getline(buff,2048);
if(strlen(buff)>0)//Пропускаем пустые строки
library.push_back(string(buff));
}
QuickSort(library,0,library.size()-1);
ifstream input2(argv[2],ios::in);
input2.getline(buff,2048);
string str(buff);
delete [] buff;
int First_Index = BinarySearch(library,str);
int Last_index = BinarySearch_last(library,str);
//cout<<First_Index<<" "<<Last_index<<endl;
input2.close();
//out
ofstream output("out.txt",ios::out|ios::app);
output<<endl<<endl<<"Result:"<<endl;
output<<library[First_Index]<<endl;
for (int x=First_Index+1;x<Last_index;x+=1)
{
if (strcmp(library[x].c_str(),library[x-1].c_str())!=0)
output<<library[x]<<endl;
}
library.clear();
return 0;
}
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
int partition(vector<string>& library,int start,int end)
{
string x = library[start];
int i = start -1, j = end+1;
while (true)
{
do {--j;} while (strcmp(library[j].c_str(),x.c_str()) > 0);
do {++i;} while (strcmp(library.c_str(),x.c_str()) < 0);
if (i < j)
swap(library,library[j]);
else
return j;
}
}
void QuickSort(vector<string>& library, int start, int end)
{
if (start<end)
{
int q = partition(library, start, end);
QuickSort(library, start, q);
QuickSort(library, q+1, end);
}
}
bool check(vector<string>& library, int pos, string fragment)//сравнивает,есть ли префикс
{
return pos < (int)library.size() && (library[pos].find(fragment) == 0);// || fragment.find(library[pos])==0);
}
int BinarySearch(vector<string>& library,string& fragment)
{
int start(0), end(library.size()-1);
int tmp;
while (start < end)
{
int middle = (start+end)/2, cmp = strcmp(library[middle].c_str(),fragment.c_str());
if (cmp < 0)
if(start!=middle)
start = middle;
else
start = middle+1;
else
if(end!=middle)
end = middle;
else
end = middle-1;
}
if (!(check(library, start, fragment) || check(library, start+1, fragment)))
{ cout<<fragment<<" not found :("<<endl;
if(fragment.length()>1)
{
fragment=fragment.substr(0,fragment.length()-1);
cout<<"Searching for: "<<fragment<<endl;
start=BinarySearch(library,fragment);
}
}
return start;
//return -1;
}
int BinarySearch_last(vector<string>& library,string fragment,int start)
{
int end(library.size()-1);
while (start < end)
{
int middle = (start+end)/2, cmp = library[middle].find(fragment.c_str());
if (cmp == 0)
if(start!=middle)
start = middle;
else
start = middle+1;
else
if(end!=middle)
end = middle;
else
end = middle-1;
}
//if (!(check(library, start, fragment) || check(library, start-1, fragment)) && fragment.length()>0)
// return BinarySearch_last(library,fragment.substr(0,fragment.length()-1));
//else
return start;
//return -1;
}
int main(int argc,char** argv)
{
ifstream inFile(argv[1],ios::in);
if (inFile.eof()) return 0;
vector<string> library;
int lib_it(0),max_size(0);
char * buff=new char[2048];
while (!inFile.eof())
{
inFile.getline(buff,2048);
if(strlen(buff)>0)//Пропускаем пустые строки
library.push_back(string(buff));
}
QuickSort(library,0,library.size()-1);
ifstream input2(argv[2],ios::in);
input2.getline(buff,2048);
string str(buff);
delete [] buff;
int First_Index = BinarySearch(library,str);
int Last_index = BinarySearch_last(library,str,First_Index);
//cout<<First_Index<<" "<<Last_index<<endl;
input2.close();
//out
ofstream output("out.txt",ios::out|ios::app);
output<<endl<<endl<<"Result:"<<endl;
output<<library[First_Index]<<endl;
for (int x=First_Index+1;x<Last_index;x+=1)
{
if (strcmp(library[x].c_str(),library[x-1].c_str())!=0)
output<<library[x]<<endl;
}
library.clear();
return 0;
}
библиотека
qw
qwb
qwa
qss
qdf
qxc
qvv
qbh
qqq
qwz
qwer
qwerty
qwertyui
qwz
искомое слово
результат:
qwer
qwerty
qwertyui
swap(library,library[j]);
else
return j;
но получается ошибка сегментации...
{
string x = library[start];
int i = start -1, j = end+1;
while (true)
{
do {--j;} while (strcmp(library[j].c_str(),x.c_str()) < 0);
do {++i;} while (strcmp(library.c_str(),x.c_str()) > 0);
if (i < j)
swap(library,library[j]);
else
return j;
}
}
void QuickSort(vector<string>& library, int start, int end)
{
if (start<end)
{
int q = partition(library, start, end);
QuickSort(library, start, q);
QuickSort(library, q+1, end);
}
}
Это просто....