1

任意のタイプの配列（この場合は整数）と、配列内でスワップされることになっているインデックスを示すマ​​ップが与えられます。クリーンスワップを実行しようとしていますが、memcpyの使用方法に問題が発生しています。

これが私がこれまでに持っているものです：

目標：[1,3、-1,2]のデータ配列と[[0,3]、[3,2]、[2,1]、[1,0]]のマッピングが与えられた場合、クリーンな順列[3、-1,2,1]になります。

私の現在の実装：0 3 -12...どこかに1つずつずれているエラーがあると思います。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAP_SIZE 4

typedef struct MapEntry {
    int indexFrom;
    int indexTo;
} MapEntry;

typedef MapEntry * Map;

int permute(void *data, int nblobs, int szblob, const Map map);

void build_map(Map);
void build_data(int *);
int is_map_valid(Map);
void print_map(Map);
int is_valid(Map);

int map_comparator(const void * a, const void * b);

int main(int argc, char const *argv[])
{
    int nblobs, * data, i;
    size_t szblob;
    Map map = (Map)malloc(sizeof(Map));
    data = (int *) malloc(sizeof(int) * 4);

    build_map(map);

    data[0] = 1;
    data[1] = 3;
    data[2] = -1;
    data[3] = 2;

    nblobs = 4;
    szblob = sizeof(int);

    if (!permute(data, nblobs, szblob, map)) {
        printf("Invalid Map\n");
        return 0;
    }

    i = 0;
    for (i = 0; i < szblob; ++i) {
        printf("%d ", data[i]);
    }

    return 0;
}

void print_map(Map map){
    int i;
    for (i = 0; i < MAP_SIZE; ++i) {
        printf("[%d - %d]\n", map[i].indexFrom, map[i].indexTo);
    }
}

int map_comparator(const void *a, const void *b)
{
    const MapEntry *s1 = a;
    const MapEntry *s2 = b;
    if (s2->indexFrom != s1->indexFrom) {
        return s1->indexFrom - s2->indexFrom;
    } else {
        return s1->indexTo - s2->indexTo;
    }
}

int is_map_valid(Map map) {
    int i,j;
    for (i = 1; i < MAP_SIZE; ++i){
        j = i - 1;
        if (map[j].indexFrom == map[i].indexFrom)
            return 0;
        if (map[j].indexTo == map[i].indexTo)
            return 0;
    }
    return 1;
}

int is_valid(Map map) {
    qsort(map, MAP_SIZE, sizeof(MapEntry), map_comparator);
    if (!is_map_valid(map)) return 0;
    return 1;
}


int permute(void *data, int nblobs, int szblob, const Map map){
    int i, tmpFrom, tmpTo;
    void * a = (void *)malloc(szblob);
    char *p = data;

    /* check if map has duplicate keys */
    /* sort the list, then check whether or not the map is valid */
    if (!is_valid(map)) return 0;
    /* where issues occur */

    for (i = 0; i < nblobs; ++i){

        tmpFrom = map[i].indexFrom;

        tmpTo = map[i].indexTo;

        memcpy(a, &p[tmpFrom*szblob], szblob);

        memcpy(&p[tmpFrom*szblob], &p[tmpTo*szblob], szblob);

        memcpy(&p[tmpTo*szblob], a, szblob);

    }

    return 1;

}
/* build mapping */
void build_map(Map map){
    map[0].indexFrom = 0;
    map[0].indexTo = 3;
    map[1].indexFrom = 3;
    map[1].indexTo = 2;
    map[2].indexFrom = 2;
    map[2].indexTo = 1;
    map[3].indexFrom = 1;
    map[3].indexTo = 0;

}
4

2 に答える 2

5

あなたはデフォルトで有効になっている非標準のGCC拡張機能の犠牲者であり、voidまたは関数のサイズを1として扱うことにより、voidへのポインターと関数へのポインターのポインター演算を許可 します。この拡張機能は、たとえば、オプションを使用したC99などのC標準（詳細については、 gccのマニュアルページを参照してください）。または、オプションを指定して、このような場合に警告を発行するようにgccに要求することもできます。-std-std=c99-Wpointer-arith

問題に戻って、を書いたときに何が起こるかを考えてみましょう&data[tmpFrom]。が指すアドレスdataが取得され、tmpFromそのアドレスにバイトが追加されます。代わりに必要なのは、tmpFrom * sizeof(int)バイトを追加することです。tmpFromこれを実現するには、型の値とサイズに基づいて必要なバイト数を手動で計算するか、型へのポインタとしてポインタをint宣言する必要があります。2番目の方法が推奨されますが、関数で任意のデータ型をサポートする必要がある場合は、より難しい最初のアプローチにフォールバックする必要があります。dataint

以下は、clangによって生成される警告のリストです（通常、診断の方がはるかに優れています）。

$ clang -Wall -pedantic -o test ./test.c
./test.c:109:18: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(a, &data[tmpFrom], szblob);
                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:36: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                   ^
./test.c:109:13: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(a, &data[tmpFrom], szblob);
                ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:36: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                   ^
./test.c:109:18: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(a, &data[tmpFrom], szblob);
                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:33: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                                ^
./test.c:109:13: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(a, &data[tmpFrom], szblob);
                ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:33: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                                ^
./test.c:111:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:54:21: note: expanded from macro 'memcpy'
  ((__darwin_obsz0 (dest) != (size_t) -1)                               \
                    ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:111:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:54:21: note: expanded from macro 'memcpy'
  ((__darwin_obsz0 (dest) != (size_t) -1)                               \
                    ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:111:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:30: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                             ^
./test.c:111:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:30: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                             ^
./test.c:111:31: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:36: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                   ^
./test.c:111:26: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:36: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                   ^
./test.c:111:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:62: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                                             ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:111:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:62: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                                             ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:111:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:27: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                          ^
./test.c:111:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:27: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                          ^
./test.c:111:31: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:33: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                                ^
./test.c:111:26: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:33: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                                ^
./test.c:113:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:54:21: note: expanded from macro 'memcpy'
  ((__darwin_obsz0 (dest) != (size_t) -1)                               \
                    ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:113:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:54:21: note: expanded from macro 'memcpy'
  ((__darwin_obsz0 (dest) != (size_t) -1)                               \
                    ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:113:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:30: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                             ^
./test.c:113:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:30: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                             ^
./test.c:113:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:62: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                                             ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:113:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:62: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                                             ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:113:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:27: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                          ^
./test.c:113:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:27: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                          ^
24 warnings generated.

上記の警告が修正されると、機能するはずです。ただし、さらに2つの問題があります...

最初の問題は、予期された結果が正しくないことです。あるべきであり3, -1, 1, 2、そうではありません3, -1, 2, 1。マッピングは次のように並べ替える必要があります。

0,3
1,0
2,1
3,2

そして、順列は4つのステップで実行する必要があります。

1) 2, 3, -1, 1
2) 3, 2, -1, 1
3) 3, -1, 2, 1
4) 3, -1, 1, 2

2番目の問題は正しくないソートです。最初に「from」値で、次に「to」値で2つのソートを実行することにより、「to」（最後に呼び出すソート）のみでソートされたマッピングが作成されます。代わりに実行する必要があるのは、各要素の「from」と「to」の両方を比較する述語を使用した単一のソートです。例えば：

int map_comparator(const void *a, const void *b)
{
    const MapEntry *s1 = a;
    const MapEntry *s2 = b;
    if (*s2->indexFrom != *s1->indexFrom) {
        return *s1->indexFrom - *s2->indexFrom;
    } else {
        return *s1->indexTo - *s2->indexTo;
    }
}

上記が修正されると、すべてが機能します。それ以外に、役立つかもしれないコードへの提案はほんのわずかです。

  1. 使用している動的割り当てが多すぎます。あなたがそれをどのように行うかを再考することを検討してください。たとえば、構造のフィールドを動的に割り当てる必要はないindexFromと思います。indexToMapEntry
  2. に不要なキャストがありvoid *ます。例：void * a = (void *)malloc(szblob);はだけである必要がありますvoid *a = malloc(szblob);。
  3. void *からのような他のポインタタイプへの不要なキャストint *。void *これは、ポインターが他のタイプのポインターに暗黙的に変換可能なCでは必要ありません。ただし、これはC++には当てはまりません。
  4. typedef不透明（OPAQUE）型を作成することが目的でない限り、構造化しないでください（あなたの場合はそうではありません）。入力structは多くの入力のように見えるかもしれませんが、コードを読むC開発者にとっては入力に関する優れたヒントとして役立ちます。たとえば、優れた説明については、 Linuxカーネルコーディングスタイルの第5章を参照してください。

コードを自分で修正することをお勧めしますが、参考のために、コードを機能させるために必要な最小限の変更を加えたコードを次に示します。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAP_SIZE 4

typedef struct MapEntry {
    int * indexFrom;
    int * indexTo;
} MapEntry;

typedef MapEntry * Map;

int permute(void *data, int nblobs, int szblob, const Map map);

void build_map(Map);
void build_data(int *);
int is_map_valid(Map);
void print_map(Map);
int is_valid(Map);

int map_comparator(const void * a, const void * b);

int main(int argc, char const *argv[])
{
    int nblobs, * data, i;
    size_t szblob;
    Map map = (Map)malloc(sizeof(Map));
    data = (int *) malloc(sizeof(int) * 4);

    build_map(map);

    data[0] = 1;
    data[1] = 3;
    data[2] = -1;
    data[3] = 2;

    nblobs = 4;
    szblob = sizeof(int);

    if (!permute(data, nblobs, szblob, map)) {
        printf("Invalid Map\n");
        return 0;
    }

    i = 0;
    for (i = 0; i < szblob; ++i) {
        printf("%d ", data[i]);
    }

    return 0;
}

void print_map(Map map){
    int i;
    for (i = 0; i < MAP_SIZE; ++i) {
        printf("[%d - %d]\n", *map[i].indexFrom, *map[i].indexTo);
    }
}

int map_comparator(const void *a, const void *b)
{
    const MapEntry *s1 = a;
    const MapEntry *s2 = b;
    if (*s2->indexFrom != *s1->indexFrom) {
        return *s1->indexFrom - *s2->indexFrom;
    } else {
        return *s1->indexTo - *s2->indexTo;
    }
}

int is_map_valid(Map map) {
    int i,j;
    for (i = 1; i < MAP_SIZE; ++i){
        j = i - 1;
        if (*map[j].indexFrom == *map[i].indexFrom)
            return 0;
        if (*map[j].indexTo == *map[i].indexTo)
            return 0;
    }
    return 1;
}

int is_valid(Map map) {
    qsort(map, MAP_SIZE, sizeof(MapEntry), map_comparator);
    if (!is_map_valid(map)) return 0;
    return 1;
}


int permute(void *data, int nblobs, int szblob, const Map map){
    int i, tmpFrom, tmpTo;
    void * a = (void *)malloc(szblob);
    char *p = data;

    /* check if map has duplicate keys */
    /* sort the list, then check whether or not the map is valid */
    if (!is_valid(map)) return 0;
    /* where issues occur */

    for (i = 0; i < nblobs; ++i){

        tmpFrom = *map[i].indexFrom;

        tmpTo = *map[i].indexTo;

        memcpy(a, &p[tmpFrom*szblob], szblob);

        memcpy(&p[tmpFrom*szblob], &p[tmpTo*szblob], szblob);

        memcpy(&p[tmpTo*szblob], a, szblob);

    }

    return 1;

}
/* build mapping */
void build_map(Map map){
    int i;
    for (i = 0; i < MAP_SIZE; ++i) {
        map[i].indexFrom = (int *)malloc(sizeof(int));
        map[i].indexTo = (int *)malloc(sizeof(int));
    }

    *map[0].indexFrom = 0;
    *map[0].indexTo = 3;

    *map[1].indexFrom = 3;
    *map[1].indexTo = 2;

    *map[2].indexFrom = 2;
    *map[2].indexTo = 1;

    *map[3].indexFrom = 1;
    *map[3].indexTo = 0;

}

それが役に立てば幸い。暖かく、幸運を祈ります！

于 2012-11-10T04:18:55.610 に答える
1

Vlad Lazarenkoによって非常にうまく概説された問題に加えて、私はあなたがいくつかのメモリ割り当ての問題を抱えていると思います。（構造内のポインターに必要な過剰な割り当てについても話していません。）

でmain()、あなたは持っています：

Map map = (Map)malloc(sizeof(Map));

MapEntry *これにより、1のサイズがに割り当てられmapますが、おそらく少なくともaMapEntryとおそらく4つのMapEntry値にスペースを割り当てることを念頭に置いていたでしょう。次に、次のように呼び出します。

build_map(map);

関数内では、4つの値の配列があるかのように扱いMapEntryます。したがって、次のように書く必要があります。

Map map = (Map)malloc(MAP_SIZE * sizeof(*map));

の下でコードを実行した場合valgrind、この問題についても確実に通知されます。malloc()Cでキャストを使用するプログラマーを非難する人がいます。私はその一人ではありません（私は自分でキャストを頻繁に使用します）。しかし、批判の理由に注意してください。

次を使用してコードを簡略化できます。

int data[MAP_SIZE] = { 1, 3, -1, 2 };

たぶん、これはmalloc()できるだけ頻繁に使用するための単なる演習です。

急進的になり、すべての動的メモリ割り当てを回避することもできます。

typedef struct MapEntry
{
    int indexFrom;
    int indexTo;
} MapEntry;

int main(void)  // argc, argv unused
{
    int nblobs, i; 
    size_t szblob;
    MapEntry map[] = { { 0, 3 }, { 3, 2 }, { 3, 1 }, { 1, 0 } };
    enum { NUM_MAPENTRIES = sizeof(map) / sizeof(map[0]) };
    int data[]     = { 1, 3, -1, 2 };
    enum { NUM_DATAENTRIES = sizeof(data) / sizeof(data[0]) };

permute()関数にはもう1つの引数、つまり渡されたマップエントリの数が必要だと思います。

もう1つの問題。is_valid ()関数は配列を並べ替える（並べ替える）ためmap、で指定された操作の順序は、で実行されるmain()操作の順序ではありませんpermute()。また、このis_valid_map()チェックは、2つのマッピングのfromインデックスとtoインデックスが同じであるかどうかをチェックすることになっていると思います。O（N log N）の複雑さではなく、O（N 2）の複雑さではありますが、ソートせずにこれを行うことができます。しかし、それを行うときにマップを並べ替えることはありません。

私は結局：

#include <assert.h>
#include <stdio.h>
#include <string.h>

typedef struct MapEntry
{
    int indexFrom;
    int indexTo;
} MapEntry;

static int  permute(void *data, size_t nblobs, size_t szblob, MapEntry *map, size_t szmap);
static void print_data(const char *tag, int *data, size_t ndata);
static void print_map(const char *tag, MapEntry *map, size_t szmap);

int main(void)
{
    MapEntry map[] = { { 0, 3 }, { 3, 2 }, { 3, 1 }, { 1, 0 } };
    enum { NUM_MAPENTRIES = sizeof(map) / sizeof(map[0]) };
    int data[]     = { 1, 3, -1, 2 };
    enum { NUM_DATAENTRIES = sizeof(data) / sizeof(data[0]) };

    print_data("Initial data", data, NUM_DATAENTRIES);
    print_map(" Initial map", map, NUM_MAPENTRIES);

    if (!permute(data, NUM_DATAENTRIES, sizeof(int), map, NUM_MAPENTRIES))
    {
        printf("Invalid Map\n");
        return 0;
    }

    print_data("Result", data, NUM_DATAENTRIES);

    return 0;
}

static void print_data(const char *tag, int *data, size_t ndata)
{
    const char *pad = ": ";
    fputs(tag, stdout);
    for (size_t i = 0; i < ndata; ++i)
    {
        printf("%s%2d", pad, data[i]);
        pad = ", ";
    }
    putchar('\n');
}

static void print_map(const char *tag, MapEntry * map, size_t szmap)
{
    printf("%s:", tag);
    for (size_t i = 0; i < szmap; ++i)
        printf(" [%d - %d]", map[i].indexFrom, map[i].indexTo);
    putchar('\n');
}

static int is_map_valid(MapEntry *map, size_t szmap)
{
    for (size_t i = 0; i < szmap; ++i)
    {
        for (size_t j = i + 1; j < szmap; ++j)
        {
            if ((map[j].indexFrom == map[i].indexFrom) &&
                (map[j].indexTo == map[i].indexTo))
            {
                printf("map[%zu].indexFrom = %d = map[%zu].indexFrom = %d\n",
                        j, map[j].indexFrom, i, map[i].indexFrom);
                printf("map[%zu].indexTo = %d = map[%zu].indexTo = %d\n",
                        j, map[j].indexTo, i, map[i].indexTo);
                return 0;
            }
        }
    }
    return 1;
}

static int permute(void *data, size_t nblobs, size_t szblob, MapEntry *map, size_t szmap)
{
    char  tmp[szblob];
    char *base = data;

    if (!is_map_valid(map, szmap))
        return 0;

    for (size_t i = 0; i < szmap; ++i)
    {
        print_map("Switch", &map[i], 1);
        print_data("Before", data, nblobs);
        size_t tmpFr = map[i].indexFrom;
        size_t tmpTo = map[i].indexTo;
        assert(tmpFr < nblobs && tmpTo < nblobs);
        char *src = base + (tmpFr * szblob);
        char *tgt = base + (tmpTo * szblob);
        memcpy(tmp, src, szblob);
        memcpy(src, tgt, szblob);
        memcpy(tgt, tmp, szblob);
        print_data(" After", data, nblobs);
    }

    return 1;
}

サンプル出力：

Initial data:  1,  3, -1,  2
 Initial map: [0 - 3] [3 - 2] [3 - 1] [1 - 0]
Switch: [0 - 3]
Before:  1,  3, -1,  2
 After:  2,  3, -1,  1
Switch: [3 - 2]
Before:  2,  3, -1,  1
 After:  2,  3,  1, -1
Switch: [3 - 1]
Before:  2,  3,  1, -1
 After:  2, -1,  1,  3
Switch: [1 - 0]
Before:  2, -1,  1,  3
 After: -1,  2,  1,  3
Result: -1,  2,  1,  3

これは期待する結果とは異なりますが、開始データから期待するものをどのように取得するかはわかりません。

于 2012-11-10T05:18:00.713 に答える