1

给定一个任意类型的数组（在这种情况下是整数）和一个 Map，它告诉我们应该在数组中交换哪些索引。我正在尝试进行干净的交换，但在使用 memcpy 的方式上遇到了问题。

这是我到目前为止所拥有的：

目标：给定一个 [1,3,-1,2] 的数据数组和一个 [[0,3],[3,2],[2,1],[1,0]] 的映射，一个干净的排列将是 [3,-1,2,1]。

我目前的实现：0 3 -1 2...我想我在某处有一个错误。

#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 的指针和指向函数的指针进行 指针运算，方法是将 void 或函数的大小视为 1。可以通过指定C 标准，例如 C99，使用-std选项 - 例如，-std=c99（有关详细信息，请参阅gcc 手册页）。-Wpointer-arith或者，您可以通过指定选项要求 gcc 针对此类情况发出警告。

回到问题上来，想想你写的时候会发生什么&data[tmpFrom]。获取指向的地址data，然后将tmpFrom字节添加到该地址。你想要的是添加tmpFrom * sizeof(int)字节。为此，您必须根据 type 的值tmpFrom和大小手动计算所需的字节数int，或者将指针声明data为指向 type 的指针int。第二种是首选方法，但如果您真的希望您的函数支持任意数据类型，那么您必须退回到更难的第一种方法。

下面是由 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.

一旦上述警告得到修复，它应该可以工作。然而，还有两个问题……

第一个问题是不正确的预期结果。它应该是3, -1, 1, 2而不是3, -1, 2, 1。映射应按如下方式排序：

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

排列应该分四步完成：

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

第二个问题是不正确的排序。通过执行两种排序，首先对“from”值进行排序，然后对“to”值进行排序，您最终会得到一个仅按“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例如，我认为不需要动态分配结构indexTo字段。MapEntry
  2. 你有不必要的强制转换void *。例如：void * a = (void *)malloc(szblob);应该只是void *a = malloc(szblob);.
  3. 不必要的转换void *为其他指针类型，如int *. 这在 C 中不是必需的，其中void *指针可以隐式转换为其他类型的指针。然而，对于 C++ 来说，情况并非如此。
  4. typedef除非目标是创建不透明类型（在您的情况下不是），否则不要构造。打字struct可能看起来像很多打字，但它为那些阅读你的代码的 C 开发人员提供了关于类型的很好的提示。例如，请参阅Linux Kernel Coding Style的第 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 *，map而您可能已经想到至少为 a 分配空间，MapEntry并且可能为 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()函数还需要一个参数——传递的映射条目数。

还有一个问题；您的is_valid ()函数置换（排序）您的map数组，因此在中指定的操作main()顺序不是在中执行的操作顺序permute()。此外，is_valid_map()我认为检查应该检查是否有任何两个映射具有相同的 from 和 to 索引；你可以在不排序的情况下做到这一点，尽管复杂度为 O(N 2 ) 而不是 O(N log N) 复杂度。但是您在执行此操作时不会置换地图。

我最终得到：

#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 回答