我正在尝试使用向量和迭代器在 C++ 中实现合并排序。该程序编译正常,但是当我尝试运行它时,它崩溃了。我尝试调试它但没有成功。
使用数组的实现很简单,但是当我尝试使用向量实现完全相同的算法时,程序无法运行。
#include <iostream>
#include <vector>
#include <algorithm>
void mergesort(std::vector<int>& A, int l, int r);
void merge(std::vector<int>& A, int l, int m, int r);
void mergesort(std::vector<int>& A, int l, int r) {
if(l < r) {
int m = l + (r - l) / 2;
mergesort(A, l, m);
mergesort(A, m + 1, r);
merge(A, l, m, r);
}
}
void merge(std::vector<int>& A, int l, int m, int r) {
std::vector<int> L(A.begin() + l, A.begin() + (m - 1));
std::vector<int> R(A.begin() + m, A.begin() + r);
std::vector<int>::iterator i = L.begin();
std::vector<int>::iterator j = R.begin();
std::vector<int>::iterator k = A.begin() + l;
while(i != L.end() && j != R.end()) {
if(*i <= *j) {
*k = *i;
i++;
}
else {
*k = *j;
j++;
}
k++;
}
while(i != L.end()) {
*k = *i;
i++;
k++;
}
while(j != R.end()) {
*k = *j;
j++;
k++;
}
}
void print_vector(std::vector<int> A) {
std::vector<int>::iterator it;
for(it = A.begin(); it != A.end(); ++it) {
std::cout << *it << " ";
}
}
int main() {
std::vector<int> A = {178, 1156, 136, 5, 6, 7};
mergesort(A, 0, A.size() - 1);
print_vector(A);
}
在这个部分
if(l < r) {
int m = l + (r - l) / 2;
mergesort(A, l, m);
mergesort(A, m + 1, r);
merge(A, l, m, r);
}
当 r = l + 1 你得到 m = l 然后你调用合并排序要求函数对一个空向量进行排序,而合并排序的代码假设它不为空。
什么是
std::vector<int> L(A.begin() + l, A.begin() + (m - 1));
在这种情况下?
这应该是进行调试的一个很好的起点。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句