如何为2D数组的qsort编写比较器函数? [英] How to write a comparator function for qsort for a 2D array?
本文介绍了如何为2D数组的qsort编写比较器函数?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有一个n * 2大小的数组.我想根据第二列的值使用qsort对它们进行排序.
#include<stdio.h>
int cmp(const int **a, const int **b) {
//return 0;
//return *a[1] - *b[1]
// return *a - *b;
}
int main()
{
int t; // test cases
scanf("%d", &t);
for(int i=0; i<t; i++) {
int n;
scanf("%d", &n); // size of array
int **arr = (int **)malloc(n * sizeof(int *));
for(int j =0; j< n; j++) {
arr[j] = (int *) malloc(2*sizeof(int));
}
for(int j =0; j< 2; j++) {
for(int k =0; k< n; k++) {
scanf("%d", &arr[k][j]);
}
}
for(int k =0; k< n; k++) {
for(int j =0; j<= 1; j++) {
printf("%d\t", arr[k][j]);
}
printf("\n");
}
// qsort(arr, n, sizeof(arr[0]), cmp);
}
return 0;
}
因此，输入
1 2
3 6
0 8
5 4
8 9
5 7
输出为
1 2
5 4
3 6
5 7
0 8
8 9
我尝试过，但无法根据它们的第二列进行排序.我对将数组元素传递给比较器感到困惑.还要随着元素的大小传递什么?但是我想下面的前2个是正确的.
qsort(arr, n, sizeof(arr[0]), cmp);
//qsort(arr, n, sizeof((int *)), cmp);
//qsort(arr, n, 2 * sizeof((int)), cmp);
我为比较器尝试了各种组合.
请指出方法或解释.
解决方案
比较函数的原型在qsort函数的原型中指定:
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
您的比较功能必须兼容，因此您可以通过以下方式进行定义:
int cmp(const void *a, const void *b) {
/* a and b are pointers to the array of pointers. */
int *aa = *(int * const *)a;
int *bb = *(int * const *)b;
return (aa[1] > bb[1]) - (aa[1] < bb[1]);
}
或者没有强制转换:
int cmp(const void *a, const void *b) {
/* a and b are pointers to the array of pointers. */
int * const *aa = a;
int * const *bb = b;
int ia = (*aa)[1];
int ib = (*bb)[1];
return (ia > ib) - (ia < ib);
}
请注意，您不能使用简单化的比较aa[1] - bb[1]，因为它会在较大的值时溢出，充其量只能产生不正确的输出.
此外，您输入的循环不正确:您应该以相反的顺序嵌套循环:
for (int k = 0; k < n; k++) {
for (int j = 0; j < 2; j++) {
scanf("%d", &arr[k][j]);
}
}
这是修改后的版本:
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
/* a and b are pointers to the array of pointers. */
int * const *aa = a;
int * const *bb = b;
int ia = (*aa)[1];
int ib = (*bb)[1];
return (ia > ib) - (ia < ib);
}
int main() {
int t; // test cases
scanf("%d", &t);
for (int i = 0; i < t; i++) {
int n;
scanf("%d", &n); // size of array
int **arr = malloc(sizeof(*arr) * n);
for (int j = 0; j < n; j++) {
arr[j] = malloc(sizeof(*arr[j]) * 2);
}
for (int k = 0; k < n; k++) {
for (int j = 0; j < 2; j++) {
scanf("%d", &arr[k][j]);
}
}
qsort(arr, n, sizeof(arr[0]), cmp);
for (int k = 0; k < n; k++) {
for(int j = 0; j < 2; j++) {
printf("%d\t", arr[k][j]);
}
printf("\n");
}
for (int j = 0; j < n; j++) {
free(arr[j]);
}
free(arr);
}
return 0;
}
您还可以使用实际的2D数组简化代码:
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
const int *aa = a;
const int *bb = b;
return (aa[1] > bb[1]) - (aa[1] < bb[1]);
}
int main() {
int t; // test cases
scanf("%d", &t);
for (int i = 0; i < t; i++) {
int n;
scanf("%d", &n); // size of array
int (*arr)[2] = malloc(sizeof(*arr) * n);
for (int k = 0; k < n; k++) {
scanf("%d%d", &arr[k][0], &arr[k][1]);
}
qsort(arr, n, sizeof(arr[0]), cmp);
for (int k = 0; k < n; k++) {
printf("%d\t%d\n", arr[k][0], arr[k][1]);
}
free(arr);
}
return 0;
}
I have an n*2 sized array. I want to sort them using qsort based on their value of the 2nd column.
#include<stdio.h>
int cmp(const int **a, const int **b) {
//return 0;
//return *a[1] - *b[1]
// return *a - *b;
}
int main()
{
int t; // test cases
scanf("%d", &t);
for(int i=0; i<t; i++) {
int n;
scanf("%d", &n); // size of array
int **arr = (int **)malloc(n * sizeof(int *));
for(int j =0; j< n; j++) {
arr[j] = (int *) malloc(2*sizeof(int));
}
for(int j =0; j< 2; j++) {
for(int k =0; k< n; k++) {
scanf("%d", &arr[k][j]);
}
}
for(int k =0; k< n; k++) {
for(int j =0; j<= 1; j++) {
printf("%d\t", arr[k][j]);
}
printf("\n");
}
// qsort(arr, n, sizeof(arr[0]), cmp);
}
return 0;
}
So for input,
1 2
3 6
0 8
5 4
8 9
5 7
Output is,
1 2
5 4
3 6
5 7
0 8
8 9
I tried but couldn't sort them according to their 2nd column. I am confused with passing array element to the comparator. Also with what to pass as the size of the element? But I guess that first 2 among below are correct.
qsort(arr, n, sizeof(arr[0]), cmp);
//qsort(arr, n, sizeof((int *)), cmp);
//qsort(arr, n, 2 * sizeof((int)), cmp);
I tried various combinations for the comparator.
Please hint out the way or perhaps an explanation.
解决方案
The prototype for the comparison function is specified in the prototype for the qsort function:
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
Your comparison function must be compatible, so you can define it this way:
int cmp(const void *a, const void *b) {
/* a and b are pointers to the array of pointers. */
int *aa = *(int * const *)a;
int *bb = *(int * const *)b;
return (aa[1] > bb[1]) - (aa[1] < bb[1]);
}
Or without casts:
int cmp(const void *a, const void *b) {
/* a and b are pointers to the array of pointers. */
int * const *aa = a;
int * const *bb = b;
int ia = (*aa)[1];
int ib = (*bb)[1];
return (ia > ib) - (ia < ib);
}
Note that you cannot use the simplistic comparison aa[1] - bb[1] as it can overflow for large values and at best produce incorrect output.
Furthermore, you input loop is incorrect: you should nest the loops in the opposite order:
for (int k = 0; k < n; k++) {
for (int j = 0; j < 2; j++) {
scanf("%d", &arr[k][j]);
}
}
Here is a modified version:
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
/* a and b are pointers to the array of pointers. */
int * const *aa = a;
int * const *bb = b;
int ia = (*aa)[1];
int ib = (*bb)[1];
return (ia > ib) - (ia < ib);
}
int main() {
int t; // test cases
scanf("%d", &t);
for (int i = 0; i < t; i++) {
int n;
scanf("%d", &n); // size of array
int **arr = malloc(sizeof(*arr) * n);
for (int j = 0; j < n; j++) {
arr[j] = malloc(sizeof(*arr[j]) * 2);
}
for (int k = 0; k < n; k++) {
for (int j = 0; j < 2; j++) {
scanf("%d", &arr[k][j]);
}
}
qsort(arr, n, sizeof(arr[0]), cmp);
for (int k = 0; k < n; k++) {
for(int j = 0; j < 2; j++) {
printf("%d\t", arr[k][j]);
}
printf("\n");
}
for (int j = 0; j < n; j++) {
free(arr[j]);
}
free(arr);
}
return 0;
}
You can also simplify the code using an actual 2D array:
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
const int *aa = a;
const int *bb = b;
return (aa[1] > bb[1]) - (aa[1] < bb[1]);
}
int main() {
int t; // test cases
scanf("%d", &t);
for (int i = 0; i < t; i++) {
int n;
scanf("%d", &n); // size of array
int (*arr)[2] = malloc(sizeof(*arr) * n);
for (int k = 0; k < n; k++) {
scanf("%d%d", &arr[k][0], &arr[k][1]);
}
qsort(arr, n, sizeof(arr[0]), cmp);
for (int k = 0; k < n; k++) {
printf("%d\t%d\n", arr[k][0], arr[k][1]);
}
free(arr);
}
return 0;
}
这篇关于如何为2D数组的qsort编写比较器函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
