2

マージソートアルゴリズムを使用してリストをソートするプログラムを作成しました。

問題は、動作するはずだと思うのですが、動作していないことです。マージ関数は、パラメーターとして送信された配列を返します。私が書いたコードを見て、何が間違っているのか、どのように改善できるのか教えてください。

ありがとう

void merge_sort(int *niz, int low, int medium, int high) {

int *niz2 = new int[high-low];

int bottom = low;
int top = medium + 1;

for (int f1=low; f1<high-low; f1++) {
    if (low > medium) {
        niz2[f1] = niz[top++];
    }
    else if (top > high) {
        niz2[f1] = niz[bottom++];
    }
    else if (niz[bottom] < niz[top]) {
        niz2[f1] = niz[bottom++];
    }
    else {
        niz2[f1] = niz[top++];
    }
}
niz = niz2;
}

void merge(int *niz, int low, int high) {
if (low < high) {
    int medium = (high+low)/2;
    merge(niz, low, medium);
    merge(niz, medium+1, high);
    merge_sort(niz, low, medium, high);        
}
}

プログラムの出力:

3 5 2 3 4 9 5 2 7 10 
3 5 2 3 4 9 5 2 7 10
4

3 に答える 3

4

ポインターを値で渡しているため、niz関数内に割り当てる値は呼び出し元関数では表示されません。

署名は と である必要が void merge(int niz[], int low, int medium, int high)あり void merge_sort(int niz[], int low, int high)ます。

mergeという名前を付けた場合merge_sort、下部にある から の代わりに に内容をコピーして戻す必要がniz2ありnizますniz = niz2。

*編集-* また、merge関数が間違っています（名前は ですmerge_sort）。low = 100、medium = 120、 で関数を呼び出すとしますhigh = 140。

その後for (int f1=low; f1<high-low; f1++)、ループすることはありません。

である必要がありますfor (int f1=0; f1<high-low; f1++)。上記の間違いのもう1つの結果はSIGSGV、アクセスするため、niz2範囲外です（この例では）。

于 2012-09-15T07:31:26.410 に答える
3

このコードには多くのエラーがあると思いますが、最大のものは

niz = niz2;

niz2ここでは、配列を にコピーしようとしてnizいますが、それは行われず、ポインターをコピーするだけです。

于 2012-09-15T07:36:39.543 に答える
1

niz2の内容をnizviaに割り当てようとしているようですniz = niz2; 。nizは値渡しポインターでありniz2、配列を指すローカル ポインターであるため 、これは正しくありません。

のようなループが必要な場合はniz2、memcpyのような API 関数を使用して入力配列を上書きするか、新しく作成された配列を使用するようにポインターをリダイレクトしようとしている場合は、入力を次のように渡す必要があります。ポインタツーポインタは、それを直接変更します。たとえば、 経由で呼び出します。入力ポインターを変更して新しい配列を指すようにする場合は、まず古い配列を削除する必要があります。nizfor (int i = low; i < high; i++) niz[i] = niz2[i]int* nizniz2merge_sort(int** niz, int low...)merge_sort(&niz, 0, 20);delete [] *niz; *niz = niz2;

このステートメントは、 が指すアドレスをパラメーター リスト内の一時ポインターにniz = niz2;コピーします。( など)を受け取る関数にポインターを渡すと、送信したポインターは一時変数/ポインターにコピーされます。Usingは、「int のアドレス」だけでなく、「int へのポインタのアドレス」で動作していることを示します。この場合、 orのようなステートメントを介してリダイレクトできます。ソースで実際のまたはデータを取得するには、 を使用します。niz2nizint*foo(int* nPtr);nPtrfoo(int** nPtr);nPtr*nPtr = &tmpInt*nPtr = tmpPtrinttmpInt = **nPtr

于 2012-09-15T07:37:34.583 に答える