使用C++中的字符串堆分類代碼獲取分段錯誤

int heapSize = 20; //variable 
int left(int i) { 
return (2 * i) + 1; 
} 

int right(int i) { 
return (2 * i) + 2; 
} 

void heapify(string arr[], int i) { 
int l = left(i); 
int great=0; 
int r = right(i); 
if (((strcmp(arr[l].c_str(),arr[i].c_str()))>0) && (l < heapSize)) { 
great = l; 
} 
else { 
great = i; 
} 

if (((strcmp(arr[r].c_str(),arr[great].c_str()))>0) && (r < heapSize)) { 
great = r; 
} 
if (great != i) { 
string temp = arr[i]; 
arr[i] = arr[great]; 
arr[great] = temp; 
heapify(arr, great); //Getting segment here 
} 

} 

void BuildMaxHeap(string arr[]) { 
for (int i = (heapSize - 1)/2; i >= 0; i--) { 
heapify(arr, i); 
} 
} 

void HeapSort(string arr[]) { 
BuildMaxHeap(arr); // 
for (int i = heapSize; i > 0; i--) { 
string temp = arr[0]; 
arr[0] = arr[heapSize - 1]; 
arr[heapSize - 1] = temp; 
heapSize = heapSize - 1; 
heapify(arr, 0); 
} 

}

對於heapSize大於15的此字符串堆排序代碼（例如20個元素）獲取分段錯誤。任何想法的原因？使用C++中的字符串堆分類代碼獲取分段錯誤

我backtraced它在gdb，我得到這個

#0 0x0038124b in ??() from /lib/tls/i686/cmov/libc.so.6 
#1 0x08048f62 in heapify(std::string*, int)() 
#2 0x08049050 in heapify(std::string*, int)() 
#3 0x080490ae in BuildMaxHeap(std::string*)() 
#4 0x080490d3 in HeapSort(std::string*)() 
#5 0x080494f5 in main()

那麼，什麼是錯的heapify功能？

來源

2011-11-27 codeflow

Err ...你爲什麼在C++字符串上使用'strcmp'？無論發生什麼'<'/'=='/'>'？ –

你很可能超出你的數組範圍。簡單地放置斷點並檢查這些數組索引。 –

我正在使用>或<而不是任何更改 – codeflow

在if是你應該檢查指標都在陣的邊界，然後再嘗試比較蜇傷：

if ((l < heapSize) && (arr[l] > arr[great])) {

來源

2011-11-27 15:47:53 sth

非常感謝你:) – codeflow

這是你的數組索引。查看left & right函數以及爲它們提供的for循環參數。使用奇數編號的「heapSize」值left最終將返回超過數組末尾的索引。使用偶數編號的'heapSize'，right就可以做到。

例如當'heapSize'== 15時，那麼傳遞給'heapify'的最大'i'將是7（012-1）。將它傳遞給'left'，你會得到15個。對於數組來說太大了，所以當試圖獲取'strcmp'的字符串時會發出cro s聲。

也許我做錯了什麼，但是我沒有讓你的代碼運行，不管堆的大小。

PS。使用'-g3'標誌構建gdb以獲得更好的調試符號。 g++ -g3 heap.cc

來源

2011-11-27 17:43:46 pedorro

使用C++中的字符串堆分類代碼獲取分段錯誤

回答

相關問題