在C++合併排序代碼中的Segfault

試圖讓這個工作.. GDB似乎表明索引可能由於某種原因而關閉。我使用一個名爲Record的子類的向量，主要包含需要雙向排序的population（int）和name（string）。 bt表示第27行的空指針，它是isSmaller（）函數中的'if'語句。這個函數對於同一個程序中的插入排序代碼非常合適，但不是合併排序，所以我想知道合併排序代碼有什麼問題。請指教。算法有問題嗎？在C++合併排序代碼中的Segfault

BT返回以下結果：

#0 0x0000000000403160 in CensusData::isSmaller (this=0x7fffffffdd10, type=0,  r1=0x609590, r2=0x0) at CensusDataSorts.cpp:27 
#1 0x0000000000403510 in CensusData::mergeIt (this=0x7fffffffdd10, type=0,  list=..., p=0, q=1, r=2) at CensusDataSorts.cpp:96 
#2 0x0000000000403347 in CensusData::mergeSortIt (this=0x7fffffffdd10,  type=0, list=..., p=0, r=2) at CensusDataSorts.cpp:70 
#3 0x0000000000403645 in CensusData::mergeSort (this=0x7fffffffdd10, type=0) at CensusDataSorts.cpp:113 
#4 0x0000000000401a50 in runMergeSorts (fp=...) at CensusSort.cpp:106 
#5 0x0000000000401e6f in main (argc=2, argv=0x7fffffffe068) at CensusSort.cpp:174

代碼在CensusDataSorts.cpp下方出現

bool CensusData::isSmaller(int type, Record* r1, Record* r2) 
{ 
    if(type==POPULATION) 
    { 
     if(r1->population <= r2->population) 
      return true; 
    } 

    else if(type==NAME) 
    { 
     if(*(r1->city) <= *(r2->city)) 
      return true; 
    } 

    return false;   
} 

void CensusData::mergeSortIt(int type, vector<Record*>& list, int p, int r) 
{ 
    if(p < r) 
    { 
     int q = floor((p+r)/2); 
     mergeSortIt(type,list,p,q); 
     mergeSortIt(type,list,q+1,r); 
     mergeIt(type,list,p,q,r); 
    }   
}  

void CensusData::mergeIt(int type, vector<Record*>& list, int p, int q, int r) 
{ 
    int n1=q-p+1; 
    int n2=r-q; 
    int i,j; 

    vector<Record*> L(n1,0); 
    vector<Record*> R(n2,0); 

    for(i=0; i<n1; i++) 
     L[i]=list[p+i]; 

    for(j=0; j<n2; j++) 
     R[j]=list[q+j+1]; 

    i=0; 
    j=0; 

    for(int k=p; k<=r; k++) 
    { 
     if(isSmaller(type,L[i],R[j])) 
     { 
      list[k]=L[i]; 
      i++; 
     } 
     else 
     { 
      list[k]=R[j]; 
      j++; 
     } 
    } 
} 

void CensusData::mergeSort(int type) 
{ 
    mergeSortIt(type, data, 0, data.size()-1); 
}

來源

2014-02-28 Prasad

由於您已經在GDB中進行調試，請介意給我們函數調用backtrace？並且請指出在所示的代碼中發生崩潰的位置。當發生崩潰時，請添加所涉及向量的大小以及索引。 –

請調用堆棧.. – 51k

您的意思是在GDB中輸入bt並輸出後？編程接收到的信號SIGSEGV，分段故障。 0x0000000000403160在CensusData :: isSmaller在CensusDataSorts.cpp（此= 0x7fffffffdd10，類型= 0， R1 = 0x609590，R2 =爲0x0）：27 \t \t如果（R1->人口<= r2->人口） – Prasad

問題是你改寫合併的記錄方式：

for(int k=p; k<=r; k++) 
{ 
    // Here i or j can be outside L/R bounds 
    if(isSmaller(type,L[i],R[j])) 
    { 
     list[k]=L[i]; 
     i++; 
    } 
    else 
    { 
     list[k]=R[j]; 
     j++; 
    } 
}

這裏被改寫的版本：我不知道

int k=p; 
for(; k<=r; k++) 
{ 
    if(isSmaller(type,L[i],R[j])) 
    { 
     list[k]=L[i]; 
     i++; 
     if (i == L.size()) 
      break; 
    } 
    else 
    { 
     list[k]=R[j]; 
     j++; 
     if (j == R.size()) 
      break; 
    } 
} 
for (; i < L.size(); ++i) 
    list[k++]=L[i]; 
for (; j < R.size(); ++j) 
    list[k++]=R[j];

如果這可以讓程序工作按預期，但它應該修復你的段錯誤。

來源

2014-02-28 08:07:31 marcinj

它給了我一些進步，我在你的新代碼中做了一些小的改動...而不是最後2個循環的列表[k ++]，我使用了list [++ k]，它現在可以無縫工作！謝謝xD – Prasad

R2 =爲0x0）：27，即你有一個空指針。

也改變比較：

return r1->population < r2->population;

和

return *(r1->city) < *(r2->city);

否則沒有意義。你不能有< =因爲它在邏輯上是正確的。事實上，由於不適當的比較，我自己已經排序崩潰。

來源

2014-02-28 07:50:58 user2672165

第27行是簡單的，如果從功能isSmaller（）上面的代碼條件： \t \t如果（R1 - >人口<= r2->人口） – Prasad

是不是你需要警惕R2是空指針，或者你需要初始化指針r2正確。對不起，上面簡短的回答。 – user2672165

完全相同isSmaller（）函數在同一個程序中使用插入排序代碼完美地工作。所以我想知道合併排序代碼有什麼問題.. – Prasad

在C++合併排序代碼中的Segfault

回答

相關問題