qsort 无法正常使用 long long
qsort not working properly with long long
我正在对二维数组 a[n][2] 进行排序,相对于 a[i][0],a[i+1][0] 打破与非递减 a[i] 的关系[1],a[i+1][1]。
qsort 对整数数组工作正常,但对 long long 数组无效。
整数数组代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
int cmpfunc(const void* a, const void* b)
{
int x = ((int*)a)[0] - ((int*)b)[0];
if (x != 0) {
return x;
}
return ((int*)a)[1] - ((int*)b)[1];
}
int main(int argc, char const* argv[])
{
int n, i, j;
scanf("%d", &n);
int a[n][2];
for (i = 0; i < n; i = i + 1) {
scanf("%d %d", &a[i][0], &a[i][1]);
}
qsort(a, n, sizeof(a[0]), cmpfunc);
for (i = 0; i < n; i = i + 1) {
printf("%d %d\n", a[i][0], a[i][1]);
}
return 0;
}
长长数组代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
int cmpfunc(const void* a, const void* b)
{
int x = ((int*)a)[0] - ((int*)b)[0];
if (x != 0) {
return x;
}
return ((int*)a)[1] - ((int*)b)[1];
}
int main(int argc, char const* argv[])
{
int n, i, j;
scanf("%d", &n);
long long a[n][2];
for (i = 0; i < n; i = i + 1) {
scanf("%I64d %I64d", &a[i][0], &a[i][1]);
}
qsort(a, n, sizeof(a[0]), cmpfunc);
for (i = 0; i < n; i = i + 1) {
printf("%I64d %I64d\n", a[i][0], a[i][1]);
}
return 0;
}
输入:
5
4 3
4 2
4 1
4 1
4 1
第一个代码的输出:
4 1
4 1
4 1
4 2
4 3
第二个代码的输出:
4 2
4 1
4 1
4 1
4 3
即使您将数据类型更改为 long long
,您仍然在比较函数中转换为 int *
。
如果您在编译时启用警告(-Wall -pedantic
for gcc),您应该注意到 long long int
需要不同的占位符,并且您不能假设它是 64-bit
。您还错误地转换了比较函数的参数。
请注意,两个 long long int
之间的差异可能超出 int
的范围,因此您不能使用那个(我写的那个)qsort()
比较实现。这是代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
int cmpfunc(const void *a,const void *b){
long long int x=((long long int *)a)[0]-((long long int *)b)[0];
if(x!=0){
return x;
}
return ((long long int *)a)[1]-((long long int *)b)[1];
}
int main(int argc, char const *argv[]){
int n,i;
scanf("%d",&n);
long long a[n][2];
for(i=0;i<n;i=i+1){
scanf("%lld %lld",&a[i][0],&a[i][1]);
}
qsort(a,n,sizeof(a[0]),cmpfunc);
for(i=0;i<n;i=i+1){
printf("%lld %lld\n",a[i][0],a[i][1]);
}
return 0;
}
您实际上有 两个 问题:第一个是无效转换。第二个是也关于无效转换但出于另一个原因。
正如我的一条评论所述,qsort
函数将指针 传递给比较函数 的元素。如果你有一个数组 arr
那么 qsort
将使用类似 &arr[0]
的参数。这意味着如果数组的数据本身就是数组,那么参数将是指向数组的指针。在您的特定情况下,参数类型实际上是 long long (*)[2]
,而不仅仅是 long long *
.
所以比较函数应该看起来像这样:
int cmpfunc(const void* a_, const void* b_)
{
long long (*a)[2] = (long long (*)[2]) a_;
long long (*b)[2] = (long long (*)[2]) b_;
long long result;
if ((*a)[0] - (*b)[0] != 0)
result = (*a)[0] - (*b)[0];
else
result = (*a)[1] - (*b)[1];
if (result < 0)
return -1;
else if (result > 0)
return 1;
else
return 0;
}
我正在对二维数组 a[n][2] 进行排序,相对于 a[i][0],a[i+1][0] 打破与非递减 a[i] 的关系[1],a[i+1][1]。 qsort 对整数数组工作正常,但对 long long 数组无效。
整数数组代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
int cmpfunc(const void* a, const void* b)
{
int x = ((int*)a)[0] - ((int*)b)[0];
if (x != 0) {
return x;
}
return ((int*)a)[1] - ((int*)b)[1];
}
int main(int argc, char const* argv[])
{
int n, i, j;
scanf("%d", &n);
int a[n][2];
for (i = 0; i < n; i = i + 1) {
scanf("%d %d", &a[i][0], &a[i][1]);
}
qsort(a, n, sizeof(a[0]), cmpfunc);
for (i = 0; i < n; i = i + 1) {
printf("%d %d\n", a[i][0], a[i][1]);
}
return 0;
}
长长数组代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
int cmpfunc(const void* a, const void* b)
{
int x = ((int*)a)[0] - ((int*)b)[0];
if (x != 0) {
return x;
}
return ((int*)a)[1] - ((int*)b)[1];
}
int main(int argc, char const* argv[])
{
int n, i, j;
scanf("%d", &n);
long long a[n][2];
for (i = 0; i < n; i = i + 1) {
scanf("%I64d %I64d", &a[i][0], &a[i][1]);
}
qsort(a, n, sizeof(a[0]), cmpfunc);
for (i = 0; i < n; i = i + 1) {
printf("%I64d %I64d\n", a[i][0], a[i][1]);
}
return 0;
}
输入:
5
4 3
4 2
4 1
4 1
4 1
第一个代码的输出:
4 1
4 1
4 1
4 2
4 3
第二个代码的输出:
4 2
4 1
4 1
4 1
4 3
即使您将数据类型更改为 long long
,您仍然在比较函数中转换为 int *
。
如果您在编译时启用警告(-Wall -pedantic
for gcc),您应该注意到 long long int
需要不同的占位符,并且您不能假设它是 64-bit
。您还错误地转换了比较函数的参数。
请注意,两个 long long int
之间的差异可能超出 int
的范围,因此您不能使用那个(我写的那个)qsort()
比较实现。这是代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
int cmpfunc(const void *a,const void *b){
long long int x=((long long int *)a)[0]-((long long int *)b)[0];
if(x!=0){
return x;
}
return ((long long int *)a)[1]-((long long int *)b)[1];
}
int main(int argc, char const *argv[]){
int n,i;
scanf("%d",&n);
long long a[n][2];
for(i=0;i<n;i=i+1){
scanf("%lld %lld",&a[i][0],&a[i][1]);
}
qsort(a,n,sizeof(a[0]),cmpfunc);
for(i=0;i<n;i=i+1){
printf("%lld %lld\n",a[i][0],a[i][1]);
}
return 0;
}
您实际上有 两个 问题:第一个是无效转换。第二个是也关于无效转换但出于另一个原因。
正如我的一条评论所述,qsort
函数将指针 传递给比较函数 的元素。如果你有一个数组 arr
那么 qsort
将使用类似 &arr[0]
的参数。这意味着如果数组的数据本身就是数组,那么参数将是指向数组的指针。在您的特定情况下,参数类型实际上是 long long (*)[2]
,而不仅仅是 long long *
.
所以比较函数应该看起来像这样:
int cmpfunc(const void* a_, const void* b_)
{
long long (*a)[2] = (long long (*)[2]) a_;
long long (*b)[2] = (long long (*)[2]) b_;
long long result;
if ((*a)[0] - (*b)[0] != 0)
result = (*a)[0] - (*b)[0];
else
result = (*a)[1] - (*b)[1];
if (result < 0)
return -1;
else if (result > 0)
return 1;
else
return 0;
}