反転カウントアルゴリズムによるセグメントエラー

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); 

プログラムが与えます私はクラス内の配列[]要素を出力してプログラムをデバッグしようとしました。コンストラクタでコピーされた配列[]は{9 12 3 1 6 8 2 5 14 13 11 7 10 4 0}と思われます。しかし、プログラムがカウントアップすると、クラスメンバ配列[]は{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); 

プログラムは、建設段階でセグメンテーションフォールトに実行されます。デバッグは、配列[]を配列[]にコピーするときにプログラムが一時停止することを示しています。

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++ではありません。あなたのコンパイラは、拡張機能として、それを許可する必要がありますが、その場合にはそれが何のスペースは、アレイ用に割り当てられていない」を意味し、私たちのようなものでしょう：あなたは、自分の書き込み権限そうするとき、これをやっていない

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使用することがはるかに優れています配列とコンスタにオフセットするiners - これはC++ライブラリが使用するものです。 size_tは符号なしタイプなので、ライブラリと同じ型を使用することで、 'signed/unsigned mismatch'という困難な問題を回避できます。 （効果は、あなたが期待するものではないことが多い）