将 qsort 与定义结构一起使用
Using qsort with a define struct
我正在学习 C 并正在解决 this challenge,我不打算将它提交到 uva 平台,我编写此练习的原因是为了学习,也许不是解决问题的最佳方法,但我正在尝试。
我在终端中打印的输入如下:
4
3
20 30 40 50 30 40
Res: 2
4
20 30 10 10 30 20 40 50
Res: 4
3
10 30 20 20 30 10
Res: 2
4
10 10 20 30 40 50 39 51
Res: 3
每次输入测试的答案都不正确,我认为原因是 qsort 函数。我对如何使用结构使用 qsort 函数感到困惑,我正在调用称为数组的结构,后跟输入的大小,然后使用 sizeof(int) 但我需要使用 int 还是 sizeof 我的结构,最后我调用我的比较函数。我的代码是:
#include <stdio.h>
#include <string.h>
struct Dolls{
int w;
int h;
}array[20005];
int cmp(struct Dolls a, struct Dolls b){
if(a.w==b.w){
return a.h < b.h;
}else{
return a.w > b.w;
}
}
int arr[20005];
int dp[20005];
int n;
int bSearch(int num, int k){
int low=1;
int high = k;
int mid;
while(low<= high){
mid = (low+high)/2;
if(num>=dp[mid]){
low=mid+1;
}else{
high=mid-1;
}
}
return low;
}
int res_dolls(){
int k=1;
int i,pos;
dp[i]=arr[1];
for(i=2;i<=n;i++){
if(arr[i]>=dp[k]){
dp[++k] = arr[i];
}else{
pos = bSearch(arr[i],k);
dp[pos] = arr[i];
}
}
return k;
}
int main(){
int t,j;
scanf("%d",&t);
while(t--){
memset(array,0,sizeof(array));
scanf("%d",&n);
for(j=1;j<=n;j++){
scanf("%d %d",&array[j].w, &array[j].h);
}
qsort(array,n,sizeof(int),cmp);
for(j=1;j<=n;j++){
arr[j] = array[j].h;
}
printf("%d\n",res_dolls());
}
return 0;
}
您的 cmp
函数需要定义为 int (*)(const void *, const void *)
才能用于 qsort
。
您进行比较的方式也不正确。来自 qsort 的手册页:
The comparison function must return an integer less than, equal to,
or greater than zero if the first argument is considered to be
respec- tively less than, equal to, or greater than the second. If
two members compare as equal, their order in the sorted array is
undefined.
您正在进行的比较 return <
或 >
运算符的结果,即 0 或 1。您需要明确检查每个案例,并且 return 正确的值。
int cmp(const void *va, const void *vb){
const struct Dolls *a = va;
const struct Dolls *b = vb;
if(a->w > b->w) {
return 1;
} else if(a->w < b->w){
return -1;
} else if(a->h > b->h) {
return 1;
} else if(a->h < b->h){
return -1;
} else {
return 0;
}
}
至于对qsort
的调用,你需要给它一个数组元素的大小,即整个结构,而不是子字段的大小:
qsort(array,n,sizeof(struct Dolls),cmp);
编辑:
修正了参数名称的错误。还更改了执行排序的方式以符合比较函数的行为方式。
我正在学习 C 并正在解决 this challenge,我不打算将它提交到 uva 平台,我编写此练习的原因是为了学习,也许不是解决问题的最佳方法,但我正在尝试。
我在终端中打印的输入如下:
4
3
20 30 40 50 30 40
Res: 2
4
20 30 10 10 30 20 40 50
Res: 4
3
10 30 20 20 30 10
Res: 2
4
10 10 20 30 40 50 39 51
Res: 3
每次输入测试的答案都不正确,我认为原因是 qsort 函数。我对如何使用结构使用 qsort 函数感到困惑,我正在调用称为数组的结构,后跟输入的大小,然后使用 sizeof(int) 但我需要使用 int 还是 sizeof 我的结构,最后我调用我的比较函数。我的代码是:
#include <stdio.h>
#include <string.h>
struct Dolls{
int w;
int h;
}array[20005];
int cmp(struct Dolls a, struct Dolls b){
if(a.w==b.w){
return a.h < b.h;
}else{
return a.w > b.w;
}
}
int arr[20005];
int dp[20005];
int n;
int bSearch(int num, int k){
int low=1;
int high = k;
int mid;
while(low<= high){
mid = (low+high)/2;
if(num>=dp[mid]){
low=mid+1;
}else{
high=mid-1;
}
}
return low;
}
int res_dolls(){
int k=1;
int i,pos;
dp[i]=arr[1];
for(i=2;i<=n;i++){
if(arr[i]>=dp[k]){
dp[++k] = arr[i];
}else{
pos = bSearch(arr[i],k);
dp[pos] = arr[i];
}
}
return k;
}
int main(){
int t,j;
scanf("%d",&t);
while(t--){
memset(array,0,sizeof(array));
scanf("%d",&n);
for(j=1;j<=n;j++){
scanf("%d %d",&array[j].w, &array[j].h);
}
qsort(array,n,sizeof(int),cmp);
for(j=1;j<=n;j++){
arr[j] = array[j].h;
}
printf("%d\n",res_dolls());
}
return 0;
}
您的 cmp
函数需要定义为 int (*)(const void *, const void *)
才能用于 qsort
。
您进行比较的方式也不正确。来自 qsort 的手册页:
The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respec- tively less than, equal to, or greater than the second. If two members compare as equal, their order in the sorted array is undefined.
您正在进行的比较 return <
或 >
运算符的结果,即 0 或 1。您需要明确检查每个案例,并且 return 正确的值。
int cmp(const void *va, const void *vb){
const struct Dolls *a = va;
const struct Dolls *b = vb;
if(a->w > b->w) {
return 1;
} else if(a->w < b->w){
return -1;
} else if(a->h > b->h) {
return 1;
} else if(a->h < b->h){
return -1;
} else {
return 0;
}
}
至于对qsort
的调用,你需要给它一个数组元素的大小,即整个结构,而不是子字段的大小:
qsort(array,n,sizeof(struct Dolls),cmp);
编辑:
修正了参数名称的错误。还更改了执行排序的方式以符合比较函数的行为方式。