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

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] = '[=10=]';
    str2[0] = '[=10=]';

    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 跳到 0x7fff58e9fb38 8 (sizeof(int *))，而 A[ 0] 存储在 0x7fff58e9fb34 （整数的大小）。

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

Answer 1

我认为连接整数来比较行不是一个好主意。通常，结果字符串可以有不同的大小。至少您必须为每个转换后的数字添加前导零，以对齐字符串并考虑整数的符号。

此外，您还错误地解除了 void 指针的引用。

qsort 的调用是不正确的，尽管它可以工作，前提是 sizeof( int * ) 等于 sizeof( int )。你应该写

qsort(A, len, sizeof( int[COL_SIZE] ), cmp_func);

我会这样写程序

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

#define COL_SIZE 3

int cmp_rows(const void *a, const void *b)
{
    const int *left  = *(const int(*)[COL_SIZE])a;
    const int *right = *(const int(*)[COL_SIZE])b;

    for (size_t i = 0; i < COL_SIZE; i++)
    {
        if ( left[i] < right[i]) return -1;
        else if (right[i] < left[i]) return 1;
    }

    return 0;
}

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

    qsort(A, sizeof(A) / sizeof(*A), sizeof(int[COL_SIZE]), cmp_rows);

    for (size_t i = 0; i < sizeof(A) / sizeof(*A); i++)
    {
        for (size_t j = 0; j < COL_SIZE; j++) printf("%d ", A[i][j]);
        printf("\n");
    }

    return 0;
}

程序输出为

Answer 2

问题出在这里：

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

你告诉 qsort() 对 'A' 进行排序，它有 'len'(5) 个项目，每个项目都是 3 *int 的大。但是，'A' 是由 int 组成的，而不是 *int 组成的。

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

试一试。

Answer 3

在这两行中：

const int **ia = (const int **)a;
const int **ib = (const int **)b;

这是不正确的，您只需要一个 * 指针，因为您要将每一行中的元素与其他行进行比较。

这需要更改为：

const int *ia = (const int *)a;
const int *ib = (const int *)b;

此外，这一行：

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

需要改为：

qsort(A, len, sizeof(*A), cmp_func);

qsort 中的第三个参数只需要它比较的大小。在这种情况下，每行的大小，可以表示为 sizeof(*A) 或 sizeof(A[0]).

此外，来自莫斯科的@Vlad 有一个更好的方法，不需要连接字符串。

如果您仍然希望使用字符串方法，可以试试这个：

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

#define STRSIZE 100
#define COL_SIZE 3

int cmp_func(const void *a, const void *b) {
    char str1[STRSIZE], str2[STRSIZE], temp[STRSIZE];
    size_t i;

    const int *row1 = (const int *)a;
    const int *row2 = (const int *)b;

    *str1 = '[=14=]';
    *str2 = '[=14=]';

    for (i = 0; i < COL_SIZE; i++) {
        sprintf(temp, "%d", row1[i]);
        strcat(str1, temp);

        sprintf(temp, "%d", row2[i]);
        strcat(str2, temp);
    }  

    return strcmp(str1, str2);

}

void print_array(int A[][COL_SIZE], size_t len) {
    size_t row, col;

    for (row = 0; row < len; row++) {
        for (col = 0; col < COL_SIZE; col++) {
            printf("%d ", A[row][col]);
        }
        printf("\n");
    }
}

int main(void) {
    size_t len;
    int A[][COL_SIZE] = {{1,2,0},
                         {1,19,0},
                         {1,19,0},
                         {1,19,0},
                         {1,2,0}};

    len = sizeof(A)/sizeof(*A);

    printf("\nBefore:\n");
    print_array(A, len);

    qsort(A, len, sizeof(*A), cmp_func);

    printf("\nAfter:\n");
    print_array(A, len);

    return 0;
}

输出：

Answer 4

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

这将导致以下代码，它需要 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()的指针是指向COLSint数组的指针，或者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 }

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

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

Sort a array of array of integers lexicographically

c

pointers

lexicographic