Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Ошибка сегментирования

62K
09 июня 2011 года
EugeneNK
25 / / 09.06.2011
Задача была - написать программу сортировки QuickSort. Код есть.
И вот...
Код:
#include <iostream>
#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 работала программа.
11
09 июня 2011 года
oxotnik333
2.9K / / 03.08.2007
на какой строке хоть?
обычно ошибка сегментирования возникает при обращении к неициализированному или удаленному объекту.
62K
09 июня 2011 года
EugeneNK
25 / / 09.06.2011
Да просто... Пишет Ошибка сегментации...
277
09 июня 2011 года
arrjj
1.7K / / 26.01.2011
Вот подчистил main немного - теперь не падает с ош сегментирования. падало из-за кривого считывания, в результате BinarySearch/BinarySearch_last выдают -1...(думаю в этом проблема была)
Код:
#include <iostream>
#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. а какая вообще задача этой проги?
62K
09 июня 2011 года
EugeneNK
25 / / 09.06.2011
О... Спасибо... А можно поподробнее: где подчистил и в чем косяк был...
277
09 июня 2011 года
arrjj
1.7K / / 26.01.2011
Цитата: EugeneNK
О... Спасибо... А можно поподробнее: где подчистил и в чем косяк был...



Найди семь отличий:):

Код:
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);
    }

Код:
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;

А косяк в том что RTFM!!!
62K
09 июня 2011 года
EugeneNK
25 / / 09.06.2011
Все равно выдает ошибку сегментирования....

Задача - сортировка быстрая...
240
09 июня 2011 года
aks
2.5K / / 14.07.2006
Цитата: arrjj
P.S. на будущее если инклюдишь math.h то компиль с ключем -lm (g++ 1.cpp -lm -o a.out)


Дык g++ автоматически libm и libstdc++ линкует. )

240
09 июня 2011 года
aks
2.5K / / 14.07.2006
Цитата: EugeneNK
Все равно выдает ошибку сегментирования....


Вы знакомы с такими инструментами, как gdb? valgrind?

62K
09 июня 2011 года
EugeneNK
25 / / 09.06.2011
Только знаю, что это статические анализаторы кода... И всё...
277
09 июня 2011 года
arrjj
1.7K / / 26.01.2011
Покажи свои 1.txt и 3.txt, т.к. у меня всё норм работает
2 aks, ух ты какой gcc умный :)
62K
09 июня 2011 года
EugeneNK
25 / / 09.06.2011
А... не.... Сработало...
62K
09 июня 2011 года
EugeneNK
25 / / 09.06.2011
Да-да... Мой оксяк... Прошу прощения... Кривые были тексты... сейчас норма... Спасибо....

P.S.
А можно комментарии к int main ??? Пожалуйста... В общих чертах... Лабу завтра сдавать...
62K
10 июня 2011 года
EugeneNK
25 / / 09.06.2011
Спасибо всем. Разобрался
240
10 июня 2011 года
aks
2.5K / / 14.07.2006
Цитата: arrjj

2 aks, ух ты какой gcc умный :)


gcc не умный - он обычный. ) Просто g++ всегда вызывает gcc с линковкой libm - вот такая вот особенность. Для удобства или наоборот. Может так исторически сложилось, дабы облегчить участь забывающих libm. А может libstdc++ зависит от неё. В любом случае раньше собрав плюсовый код через вызов gcc, а не g++ можно было получить на одну зависимость меньше. ) Как сейчас не знаю.

240
10 июня 2011 года
aks
2.5K / / 14.07.2006
Цитата: EugeneNK
Только знаю, что это статические анализаторы кода... И всё...


Нет наоборот - это средства отладки. Если gdb наверно будет тяжело сходу осилить без чтения документации - просто запустите софтину под valgrind хотя бы. Большинство ошибок работы с памятью (которые собственно и приводят к сигфолту) он покажет сразу.

62K
10 июня 2011 года
EugeneNK
25 / / 09.06.2011
если нам надо найти слово "СТОО", а его в библиотеке нет, то выдает ошибку.
Как сделать чтобы выводил все похожие результаты? То есть "СТО", "СТОЛ" и т.п.
62K
10 июня 2011 года
EugeneNK
25 / / 09.06.2011
help...
240
10 июня 2011 года
aks
2.5K / / 14.07.2006
Ты хочешь чтоб за тебя алгоритм что ли написали? Сначала определись хотя бы с критерием похожести.
62K
10 июня 2011 года
EugeneNK
25 / / 09.06.2011
Да не, не алгоритм... Там просто где-то поставить условие в BinarySearch...
Только вот у меня получается всего 1 слово выводить... А надо поболее
277
10 июня 2011 года
arrjj
1.7K / / 26.01.2011
Код:
#include <iostream>
#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;
}
62K
10 июня 2011 года
EugeneNK
25 / / 09.06.2011
Выдаёт всего одно слово...
62K
10 июня 2011 года
EugeneNK
25 / / 09.06.2011
Первый и последний индекс одинаковый получается....
277
10 июня 2011 года
arrjj
1.7K / / 26.01.2011
А нуда это у меня словарь такой удачный получился :)
Код:
#include <iostream>
#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;
}

библиотека
Код:
q
qw
qwb
qwa
qss
qdf
qxc
qvv
qbh
qqq
qwz
qwer
qwerty
qwertyui
qwz

искомое слово
 
Код:
qwep

результат:
 
Код:
Result:
qwer
qwerty
qwertyui
62K
16 июня 2011 года
EugeneNK
25 / / 09.06.2011
Слушайте, а что поменять, чтобы сортировал с Я до А... Пробовал сделать так
Цитата:
if (i > j)
swap(library,library[j]);
else
return j;


но получается ошибка сегментации...

62K
16 июня 2011 года
EugeneNK
25 / / 09.06.2011
По идее же в первой функции идёт смена местами строк
62K
17 июня 2011 года
EugeneNK
25 / / 09.06.2011
Пробовал так:

Цитата:
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);
}
}

277
17 июня 2011 года
arrjj
1.7K / / 26.01.2011
Двоичный поиск тоже нужно переделывать. Совет: просто выводи в обратном порядке.
62K
17 июня 2011 года
EugeneNK
25 / / 09.06.2011
Ну так-то я придумал:)
Это просто....
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог