反转计数算法的段错误

Question

我正在开发一个使用合并排序算法实现倒置计数的程序。

当我用给定的测试用例测试我的程序时。我遇到了分段错误，我找不到原因。

一个测试用例如下代码所示：

    int inputArray[5] = {5,4,3,2,1};
    inversionCount Inversion(inputArray, 5);
    count = Inversion.totalinversionCount(0, 4);

程序给出的正确答案是 10。

另一个测试用例是：

    int inputArray[15] = {9, 12, 3, 1, 6, 8, 2, 5, 14, 13, 11, 7, 10, 4, 0};
    inversionCount Inversion(inputArray, 15);
    count = Inversion.totalinversionCount(0, 14);

程序给出的答案是 48，而正确答案是 56。我试图通过在 class 中打印 array[] 元素来调试程序。在构造函数中，复制的数组 [] 似乎是 {9 12 3 1 6 8 2 5 14 13 11 7 10 4 0}。但是，当程序开始计数时，class 成员数组[] 变为 {0 12 3 1 6 8 2 5 14 13 11 7 10 4 0}。第一个元素从9变成了0，不知道为什么。

最后一个测试用例是：

    int inputArray[100] = { 4, 80, 70, 23, 9, 60, 68, 27, 66, 78, 12, 40, 52, 53, 44, 8, 49, 28, 18, 46, 21, 39, 51, 7, 87, 99, 69, 62, 84, 6, 79, 67, 14, 98, 83, 0, 96, 5, 82, 10, 26, 48, 3, 2, 15, 92, 11, 55, 63, 97, 43, 45, 81, 42, 95, 20, 25, 74, 24, 72, 91, 35, 86, 19, 75, 58, 71, 47, 76, 59, 64, 93, 17, 50, 56, 94, 90, 89, 32, 37, 34, 65, 1, 73, 41, 36, 57, 77, 30, 22, 13, 29, 38, 16, 88, 61, 31, 85, 33, 54 };
    inversionCount Inversion(inputArray, 100);
    count = Inversion.totalinversionCount(0, 99);

程序在构造步骤中遇到段错误。调试显示程序在将 Array[] 复制到 array[] 时暂停。

Signal received: SIGSEGV (Segmentation fault)
For program algorithm_design_i_week_1, pid 23,328
You may discard the signal or forward it and you may continue or pause the process

我的程序如下。请帮我找出分段错误的原因。非常感谢。

inversionCount.h

#ifndef INVERSIONCOUNT_H
#define INVERSIONCOUNT_H

#include <iostream>

using namespace std;   

class inversionCount {
private:
    int length;
    int array[];

public:
    inversionCount(int Array[], int Length);
    int splitCount(int first, int mid, int last);
    int totalinversionCount(int first, int last);
};

#endif /* INVERSIONCOUNT_H */

inversionCount.cpp

#include "inversionCount.h"

inversionCount::inversionCount(int Array[], int Length) {
    length = Length;
    for (int i = 0; i < length; i++) 
        array[i] = Array[i];
}

int inversionCount::splitCount(int first, int mid, int last) {
    int first1 = first, last1 = mid;
    int first2 = mid + 1, last2 = last;
    int tempArray[length];
    int i = first;
    int totalSplitCount = 0;
    while (i < last && first1 <= last1 && first2 <= last2) {
        if (array[first1] < array[first2]) {
            tempArray[i] = array[first1];
            first1++;
            i++;
        }
        else {
            tempArray[i] = array[first2];
            totalSplitCount += last1 + 1 - first1;   
            first2++;
            i++;
        }           
    }
    while (first1 <= last1) {
        tempArray[i] = array[first1];
        first1++;
        i++;
    }   
    while (first2 <= last2) {
        tempArray[i] = array[first2];
        first2++;
        i++;
    }  
    for (int j = first; j < last + 1; j++) 
        array[j] = tempArray[j];
    return totalSplitCount;
}

int inversionCount::totalinversionCount(int first, int last) {    
    int totalCount = 0;
    if (first < last) {
        int mid = (first + last) / 2;
        totalCount = totalinversionCount(first, mid) + totalinversionCount(mid + 1, last) + splitCount(first, mid, last);
    }       

    return totalCount;
}

countDriver.cpp

#include "inversionCount.h"

int main(int argc, char** argv) {
    int inputArray[5] = {5,4,3,2,1};

    inversionCount Inversion(inputArray, 5);
    int count = 0;
    count = Inversion.totalinversionCount(0, 4);
    cout<<"The number of inversions is "<<count<<endl;
    return 0;
}

Answer 1

int array[];作为成员变量的定义是不合法的C++。您的编译器必须允许它作为扩展，但在那种情况下，它意味着“没有 space 分配给数组，但我们会做类似的事情：

A* pA = static_cast<A*>(malloc(sizeof(A) + Length*sizeof(int));

你没有这样做，所以当你写入数组时，你覆盖了一些随机的内存位，所以不好的事情发生了。

最好的办法是使用 std::vector。

class inversionCount {
private:
    std::vector<int> array;

public:
    inversionCount(int Array[], int Length) : array(Array, Array+Length) {}
    int splitCount(int first, int mid, int last);
    int totalinversionCount(int first, int last);
};

另一条评论：使用 size_t 作为数组和容器中的长度和偏移量的类型要好得多——这是 C++ 库使用的。 size_t 是无符号类型，因此通过使用与库相同的类型，可以避免 'signed/unsigned mismatch' 的难题。（效果往往出乎你的意料。）

反转计数算法的段错误

Segement fault with Inversion Counting algorithm

c++

mergesort

segmentation-fault