我收到错误分段错误,但我不知道问题出在哪里。我尝试在终端中以gdb模式运行该程序,然后将其抛出。
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff74d730e in _int_malloc (av=av@entry=0x7ffff782ec40 <main_arena>,
bytes=bytes@entry=1904) at malloc.c:3557
3557 malloc.c: No such file or directory.
这是我的程序:
#include<iostream>
#include<chrono>
#include<random>
#include<cstdlib>
#include<vector>
#include<fstream>
#include<stdint.h>
#include<algorithm>
using namespace std;
using namespace std::chrono;
int found=0;
int notfound;
double ltimex = 0;
double lavgtime = 0;
double btimex = 0;
double bavgtime = 0;
float comparison=0;
float position=0;
int linearsearch(vector<int> a, int key, float &position){ //linear search
int j;
for(j=1; j<a.size(); j++){
if(key==a[j]){
position = j;
found++;
break;
}
}
if(position == j){
return position;
}
else
{
notfound = -1;
return notfound;
}
}
int binarysearch(vector<int>a, int first, int last, int key, float &comparison){ //binary search
int l=a[first];
int r=a[last];
if (r >= l) {
int mid = l + (r - l) / 2;
comparison++;
if (a[mid] == key)
return mid;
if (a[mid] > key)
return binarysearch(a, l, mid - 1, key, comparison);
return binarysearch(a, mid + 1, r, key, comparison);
}
return -1;
}
int main(){
int i,j,l;
srand(time(0));
for(i=120; i<=3600; i=i+120){
vector<int>a;
for(j=0; j<100; j++) //loop for test case, 100
{
for(int k=1; k<=i-1; k++){
int z = rand()%i+100;
a.push_back(z);
}
int key = rand()%i+100;
sort(a.begin(), a.end());
//time functions.
//linear search
auto start = high_resolution_clock::now();
linearsearch(a,key, position);
auto stop = high_resolution_clock::now();
ltimex = duration_cast<microseconds>(stop - start).count();
lavgtime = lavgtime + ltimex;
// //binary search
auto bstart = high_resolution_clock::now();
binarysearch(a,0, i,key, comparison);
auto bstop = high_resolution_clock::now();
btimex = duration_cast<microseconds>(bstop - bstart).count();
bavgtime = bavgtime + btimex;
}
comparison = comparison/100;
position = position/100;
cout << "\nAverage Time taken by linear function: "<< lavgtime << " microseconds";
cout << "\nAverage Time taken by binary function: "<< bavgtime << " microseconds";
ofstream fout;
fout.open("data.csv", ios::out | ios::app);
while (fout)
{
if (position != -1)
fout<<i<<","<<lavgtime<<","<<position<<","<<bavgtime<<","<<comparison<<"\n"; //size of array, linear, postion, binary, comparison
break;
}
fout.close();
}
return 0;
}
我以前使用快速排序,但是后来我从cpp的STL切换到此排序功能,这可能是原因吗?请帮我解决这个问题,我感到困惑,因为我似乎无法找出错误。您的帮助将不胜感激:)
您的问题是您不检查索引值是否在向量大小内。
第一个错误:
//binarysearch function
int r = a[last]; // last is 120, the size of the vector is 119, the 119'th element is the allocator, so the biggest number you can to have is 118
第二个错误:
//binarysearch function
int mid = l + (r - l) / 2; // the mid is 159, so you have index out of bounds
可能会有更多错误,因此您必须检查索引的值。
l
和r
表示如下的std::vector<int> a
更新代码的索引, int l = first;
int r = last;
代替
int l = a[first];
int r = a[last];
vector<int>a
中的元素总数始终为i-1
,因此必须从0
到i-2
进行访问。更正传递给binarysearch
的索引