c - 按字典顺序对整数数组进行排序

Question

我正在使用 qsort() 按字典顺序对二维整数数组进行排序，每一行都是一个输入，但在遍历数组中的一行时指针算法有问题。

想法是将一行中的每一列连接成一个字符串，并将 strcmp 与从其他行类似计算的其他字符串连接起来。

输入仅限于正整数。下面是一些排序示例，
{1, 1, 10} 在{1, 2, 0}
之前 {3, 1, 5} 在{3, 11, 5}
之前 {1, 19, 2} 在 {1, 2, 1} 之前

#define COL_SIZE 3  

int cmp_func (const void *a, const void *b) {
    char str1[100], str2[100], temp[10];
    int i;
    const int **ia = (const int **)a;
    const int **ib = (const int **)b;

    printf("(a: %p), (b: %p)\n", a, b);
    str1[0] = '\0';
    str2[0] = '\0';

    for (i = 0; i < COL_SIZE; i++) {
        printf("(ia+%d: %p), (ib+%d: %p)\n", i, (ia + i), i, (ib + i));
        sprintf(temp, "%d", (int)*(ia + i));
        strcat(str1, temp);

        sprintf(temp, "%d", (int)*(ib + i));
        strcat(str2, temp);
    }

    printf("a: %s, b:%s\n", str1, str2);
    return(strcmp(str1, str2));
}

int main (void) {
    int i, len;
    int A[][COL_SIZE] = {{1,2,3},
                         {1,1,5},
                         {1,0,1},
                         {1,2,1},
                         {1,2,0}};

    len = sizeof(A)/sizeof(A[0]);
    printf("sizeof(int): %ld, sizeof(int *): %ld\n", sizeof(int), sizeof(int *));

    for (i = 0; i < len; i++) {
        printf("Address of A[%d][0]: %p\n", i, A[i]);
    }

    qsort(A, len, COL_SIZE * sizeof(int *), cmp_func);
    return 0;
}

下面是输出:

sizeof(int): 4, sizeof(int *): 8  
Address of A[0][0]: 0x7fff58e9fb30  
Address of A[1][0]: 0x7fff58e9fb3c  
Address of A[2][0]: 0x7fff58e9fb48
Address of A[3][0]: 0x7fff58e9fb54  
Address of A[4][0]: 0x7fff58e9fb60  
(a: 0x7fff58e9fb30), (b: 0x7fff58e9fb48)  
(ia+0: 0x7fff58e9fb30), (ib+0: 0x7fff58e9fb48)  
(ia+1: 0x7fff58e9fb38), (ib+1: 0x7fff58e9fb50)  
(ia+2: 0x7fff58e9fb40), (ib+2: 0x7fff58e9fb58)  
a: 131, b:112  
(a: 0x7fff58e9fb48), (b: 0x7fff58e9fb60)  
(ia+0: 0x7fff58e9fb48), (ib+0: 0x7fff58e9fb60)  
(ia+1: 0x7fff58e9fb50), (ib+1: 0x7fff58e9fb68)  
(ia+2: 0x7fff58e9fb58), (ib+2: 0x7fff58e9fb70)  
Abort trap: 6

*(ia + 1) 的指针算法导致每次迭代中的地址从 0x7fff58e9fb30 跳转 8 (sizeof(int *)) 到 0x7fff58e9fb38，而 A[0] 中的下一个值存储在 0x7fff58e9fb34(int 大小)。

我该如何解决这个问题，才能获得 4 而不是 8 的偏移量？

Answer 1

您正在对数组数组而不是指针数组进行排序。因此，您需要清理比较函数中的代码。此外，比较器的当前版本在进行任何比较之前将所有数字转换为字符串。在每一行中一次转换一个数字并在发现差异时停止，只有在前一个数字相同时才转换下一个数字是可行且明智的。

这导致以下代码，它需要 C99 编译器或支持 VLA(可变长度数组)的 C11 编译器，这在 C99 中是必需的，但在 C11 中是可选的:

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

static void dump_array(const char *tag, size_t n_rows, size_t n_cols, int A[n_rows][n_cols]);

enum { COLS  = 3 };

extern int cmp_func (const void *a, const void *b);

int cmp_func(const void *va, const void *vb)
{
    const int *a = *(const int (*)[COLS])va;
    const int *b = *(const int (*)[COLS])vb;

    for (int i = 0; i < COLS; i++)
    {
        char str1[20], str2[20];
        sprintf(str1, "%d", a[i]);
        sprintf(str2, "%d", b[i]);
        int rc = strcmp(str1, str2);
        if (rc != 0)
            return rc;
    }
    return 0;
}

int main(void)
{
    int A[][COLS] =
    {
        { 1, 91, 10 },
        { 1,  9,  9 },
        { 1,  9, 11 },
        { 1,  1,  5 },
        { 1,  9, 10 },
        { 1,  0,  1 },
        { 1,  2,  3 },
        { 1, 91, 10 },
        { 1, 19,  0 },
        { 1, 91,  0 },
        { 1,  2,  0 },
        { 1,  2,  1 },
    };
    enum { ROWS = sizeof(A) / sizeof(A[0]) };

    dump_array("Before", ROWS, COLS, A);
    qsort(A, ROWS, sizeof(A[0]), cmp_func);
    dump_array("After", ROWS, COLS, A);
    return 0;
}

static void dump_array(const char *tag, size_t n_rows, size_t n_cols, int A[n_rows][n_cols])
{
    printf("%s:\n", tag);
    for (size_t r = 0; r < n_rows; r++)
    {
        const char *pad = "{";
        for (size_t c = 0; c < n_cols; c++)
        {
            printf("%s%3d", pad, A[r][c]);
            pad = ",";
        }
        puts(" }");
    }
}

传递给 cmp_func() 的指针是指向 COLS int 或 int (*)[COLS ]; a 和 b 的赋值生成一个数组 int [COLS]，它会衰减为 int *。我通常使用 v 作为比较器的 const void * 参数的前缀，并删除函数中工作变量的 v。

那里的测试数据包括评论中的测试值，输出为:

Before:
{  1, 91, 10 }
{  1,  9,  9 }
{  1,  9, 11 }
{  1,  1,  5 }
{  1,  9, 10 }
{  1,  0,  1 }
{  1,  2,  3 }
{  1, 91, 10 }
{  1, 19,  0 }
{  1, 91,  0 }
{  1,  2,  0 }
{  1,  2,  1 }
After:
{  1,  0,  1 }
{  1,  1,  5 }
{  1, 19,  0 }
{  1,  2,  0 }
{  1,  2,  1 }
{  1,  2,  3 }
{  1,  9, 10 }
{  1,  9, 11 }
{  1,  9,  9 }
{  1, 91,  0 }
{  1, 91, 10 }
{  1, 91, 10 }

此代码类似于 code通过 RoadRunner ，但主要区别在于更简单、更高效的比较函数 cmp_func()，它不必在每次比较两行时将每行中的所有数字都转换为字符串。 (在示例数据中，第一个值始终为 1，因此至少转换了两对数字。但这可能不正常。)