2

C の qsort 関数と同じ方法で、独自の Mergesort 関数を作成しようとしています。既知の項目の配列に対して MergeSort を書いていれば問題はありませんが、それらがどうなるかわからないため、ループに陥ります。

私の教授から与えられた仕様では、マージに別の関数を使用することは望まれていませんでした。そのため、Mergesort 関数自体の内部にその実装を記述しています。つまり、qsort() と同じ情報が得られるということです。

  • void* base- 並べ替える配列の最初の要素へのポインタ
  • size_t nel- 配列の要素数
  • size_t width- 各要素のサイズ
  • int (*compar)( const void*, const void* )- 各要素を比較する方法を示す関数

私が抱えている問題は、マージ部分にあります。私が見たすべての実装では、一時的な配列を使用して、並べ替え中のアイテムを格納していました。私は void ポインターの操作に慣れていません。私が見つけた最大の障害は、移動して配列に値を代入することです。が指す配列の 2 番目のインデックスの値を見つけるにはどうすればよいbaseですか? その配列の値を一時配列に割り当てるにはどうすればよいですか? その一時的な配列を作成するにはどうすればよいですか?

void ポインターを char にキャストし、それらを幅だけインクリメントすると機能しますか? ただし、割り当てがどのように機能するかはわかりません。

4

2 に答える 2

3

base が指す配列の 2 番目のインデックスの値を見つけるにはどうすればよいですか?

を使用し(char *)base + (width*i)ます。これにより、i 番目の要素のアドレスが得られます。

その配列の値を一時配列に割り当てるにはどうすればよいですか?

データをコピーするだけです。for (int n=0;n<width;n++) { //copy one byte from }

一時配列を作成するにはどうすればよいですか?

何かのようなもの：

c -void* tempArray = malloc(width*elementsNeeded);

c++ -void* tempArray = (void*) (new char[width*elementsNeeded]);

編集：

データのコピーについてもう少し詳しく説明するには、次のことを行う必要があります。

for (int n=0;n<width;n++) {
  adressTo[n] = addressFrom[n];
}
// This will copy the contents of pointer addressFrom to addressTo.
于 2010-10-03T02:05:56.850 に答える
2

base が指す配列の 2 番目のインデックスの値を見つけるにはどうすればよいですか? void ポインターを char にキャストし、それらを幅だけインクリメントすると機能しますか?

はい、そうです。char のサイズは標準で 1 と定義されているため、指定された「幅」は、定義により、各要素の char のサイズです。したがって、次のようにアドレスを見つけることができます。

void *second_element_ptr = ((char*)base) + width;

valueが見つからないのは、その型がわからないため、それが占有するメモリを理解できないためです。しかし、それは問題ありません。このインターフェイスを使用して C でオブジェクトをソートするために、それらの値を知る必要はありません。コンパレーター関数に渡すことができるオブジェクトへのポインターが必要であり、オブジェクトをコピーできる必要があります。

その配列の値を一時配列に割り当てるにはどうすればよいですか?

char temporary_array[width]; // this is a C99 VLA, you might want to 
                             // allocate the array differently
memcpy(temporary_array, second_element_ptr, width);

その一時的な配列を作成するにはどうすればよいですか?

ああ、私はこれらの質問を間違った順序で受けたと思います。単一の要素を含む小さな配列の場合、VLA でチャンスをつかむことができます。または、次のように malloc を使用できます。

// an array half the size of the input
// using char*, since unlike void* we can do arithmetic on it
char *big_temp_array = malloc(width * (nel + 1)/2);

ところで、gcc はvoid*コンパイラ拡張機能としての算術演算をサポートしており、算術演算のように扱っていchar*ます。これを使用できる/使用するかどうかは、あなた次第です。

于 2010-10-03T02:05:23.710 に答える