我的 Qsort 比较函数在内存中导致奇怪的东西 [英] My Qsort comparison function causes strange stuff in memory
问题描述
为了习惯动态创建二维数组，我想创建一个可以按每个数组中的第五个成员排序的数组.该数组是双精度组的多维数组.每组有五场双打.最后两个双打是根据我写的一些随机表达式根据前 3 个计算得出的.数组的数量与它从文件中读取的双精度组一样多.当我写它时，我从排序中得到了非常随机的结果.
To get used to dynamically creating two dimensional arrays, I wanted to create one that could be sorted by the fifth member in each array. The array is a multidimensional array of groups of doubles. Each group holds five doubles. The last two doubles are calculated based on the previous 3 by some random expression I wrote. There are as many arrays as there are groups of doubles it reads from a file. When I wrote it, I got very random results from the sort.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int getAllDoubles(char *, double ***);
void printDouble(int, int, double **, char);
int doubleCmp(const void *, const void *);
int main(){
double **arrayAll;
char *fileName = "doubles.dat";
int doublesCount = getAllDoubles(fileName, &arrayAll);
printf("%d doubles successfully copied\n", doublesCount);
printf("As a sample, here's #161\n");
printDouble(161, doublesCount, arrayAll, 'a');
double *tp = *(arrayAll + doublesCount-1) + 4;
printf("The last double is at %p and is %f\n", tp, *tp);
printf("The first double * is at %p\n", &arrayAll[0]);
printDouble(1, doublesCount, arrayAll, 'f');
printf("The first quaternary double is %f and it's at %p\n", arrayAll[0][4], &arrayAll[0][4]);
qsort(arrayAll, doublesCount, sizeof(double *), doubleCmp);
int i;
for(i = 1; i < 100; i++){
printDouble(i, doublesCount, arrayAll, 'f');
}
return 0;
}
int getAllDoubles(char *filename, double ***arrayAllPtr){
FILE *fp;
int x, y, doublesCount = 0;
double **arrayAll;
char c;
if((fp = fopen(filename, "r")) == NULL)
return -1;
while((c = getc(fp)) != EOF)
if(c == 'd')
doublesCount++;
fclose(fp);
if((fp = fopen(filename, "r")) == NULL)
return -1;
arrayAll = *arrayAllPtr = malloc(sizeof(double *) * doublesCount);
for(y = 0; (getc(fp) == 'd') && y < doublesCount; y++){
*(arrayAll+y) = malloc(sizeof(double) * 5);
if(fscanf(fp, "%lf %lf %lf", *(arrayAll + y)+1, *(arrayAll+y)+2, *(arrayAll+y)) != 3)
return -1;
*(*(arrayAll+y)+3) = sqrt(*(*(arrayAll+y)) + *(*(arrayAll+y)+1));
if(*(*(arrayAll + y)) == 0)
*(*(arrayAll+y)+4) = 0;
else
*(*(arrayAll+y)+4) = (*(*(arrayAll+y)+1) / *(*(arrayAll+y)));
while(getc(fp) != '\n')
;
}
fclose(fp);
return doublesCount;
}
void printDouble(int doubleNumber, int doublesCount, double **arrayAll, char option){
if(doubleNumber <= 0 || doubleNumber >= doublesCount)
puts("Invalid double!");
else if(option == 'a'){
printf("one: %f\ntwo: %f\nthree: %f\nfour: %f\nfive: %f\n",
*(*(arrayAll+doubleNumber-1) + 0), *(*(arrayAll+doubleNumber-1) + 1),
*(*(arrayAll+doubleNumber-1) + 2), *(*(arrayAll+doubleNumber-1) + 3),
*(*(arrayAll+doubleNumber-1) + 4));
}
else if(option == 'f')
printf("four: %f\n", *(*(arrayAll+doubleNumber-1)+4));
return;
}
int doubleCmp(const void *dOne, const void *dTwo){
double *doubleOne, *doubleTwo;
doubleOne = (double *)dOne;
doubleTwo = (double *)dTwo;
printf("%p\n", doubleOne);
printf("initial + 1 = %p\n", doubleOne + 1);
printf("initial + 2 = %p\n", doubleOne + 2);
printf("initial + 3 = %p\n", doubleOne + 3);
printf("initial + 4 = %p\n", doubleOne + 4);
printf("%f\n\n", *doubleOne);
if((*doubleTwo) < (*doubleOne)){
/*printf("%f comes before %f\n", *doubleOne, *doubleTwo);*/
return -1;
}
else if((*doubleTwo) > (*doubleOne)){
/*printf("%f comes before %f\n", *doubleTwo, *doubleOne);*/
return 1;
}
else{
/*printf("%p is equal to %p\n", *doubleOne, *doubleTwo); */
return 0;
}
}
我加入了一些 printf 语句(我知道这是不好的做法，但 DDD 不会让我在调用它时继续执行我的比较函数).以下是我所知道的:
I threw in some printf statements (bad practice I know, but DDD will not let me proceed through my comparison function when it's called). Here's what I know:
(在本次运行中)第一组中的第一个双精度(以及相关联的第一双精度组)的地址是 0x2041250.第一组中第五个双精度值(我希望对数组进行排序的那个)的地址是 0x2042310.令人震惊，因为对于应该只有 32 字节远的东西来说，这增加了相当多的地址.
(In this run) the address of the first double in the first group (and associatively, the first group of doubles) is 0x2041250. The address of the fifth double (the one I'm looking to sort the array by) in the first group is 0x2042310. Shocking, because that's quite an increase in address for something that should only be 32 bytes away.
通常这会让我相信填充动态数组的方法可能需要修复，但我可以使用打印函数打印每一组双打就好了.
Normally that would convince me that maybe the method that populates the dynamic array needs to be fixed, but I can print every single group of doubles using a print function just fine.
更奇怪的是比较函数中的 printf 语句.Qsort 从我的二维数组中的第一个双精度 * 开始，它与第一个双精度的地址具有相同的值.这一切都很好，但是当我编写 printf 语句以查看它们在处理算术方面的作用时，程序产生了
What's even weirder are the printf statements inside the comparison function. Qsort starts with the first double * in my 2D array and it has the same value as the address of the first double. That's all well and good, but when I wrote printf statements to see what they do address arithmetic wise, the program yielded
(initial 指起始地址，0x2041250)初始 + 1 = 0x2041258//没问题初始 + 2 = 0x2041260//什么initial + 3 = 0x2041268//打扰一下?初始 + 4 = 0x2041270//;_;
(initial refers to the initial address, 0x2041250) initial + 1 = 0x2041258 //Fine initial + 2 = 0x2041260 //What initial + 3 = 0x2041268 //Excuse me? initial + 4 = 0x2041270 //;_;
然后最重要的是，取消引用指针，作为空指针传入但转换为双 *，(预期)产生 0.000000.
And then to top it off, dereferencing the pointer, passed in as a void pointer but casted as double *, (expectedly) yields 0.000000.
我无法理解这里发生了什么.有任何想法吗?
I can't begin to understand what's happening here. Any ideas?
推荐答案
这是对您的代码进行了大量修改的版本.我已经修改了输入代码，以便在主输入期间一次读取一行(我没有修复行计数循环；事实上，我会摆脱它，并在进行时计数).我使用 rewind() 函数来保存关闭和重新打开文件.我修改了代码，以便为清楚起见使用下标表示法.我以 XX.YY 格式生成随机数据，因此打印格式为 %6.2f 以适应这种情况.
Here's a rather heavily modified version of your code. I've revised the input code to read a line at a time during the main input (the line counting loop I didn't fix; I would get rid of it, in fact, and count as I went). I use the rewind() function to save closing and reopening the file. I revise the code so it uses subscript notation for clarity. I generated random data in the format XX.YY, so the print formats are %6.2f to accommodate that.
关键的变化是在 doubleCmp() 函数中.qsort() 传递给它的值是指向 'array of 5 double' 的指针(或指向 double 的指针的指针).这解决了大部分问题；其余的很多代码都是特殊的或古怪的，但都是可行的.
The crucial change is in the doubleCmp() function. The values passed to it by qsort() are pointer to 'array of 5 double' (or pointer to pointer to double). This fixes most of the problems; a lot of the rest of the code is idiosyncratic or eccentric but workable.
代码包括我的诊断打印.
The code includes my diagnostic printing.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int getAllDoubles(char *, double ***);
void printDouble(int, int, double **, char);
int doubleCmp(const void *, const void *);
int main(void)
{
double **arrayAll;
char *fileName = "doubles.dat";
int doublesCount = getAllDoubles(fileName, &arrayAll);
printf("%d doubles successfully copied\n", doublesCount);
if (doublesCount <= 0)
return 1;
for (int i = 0; i < doublesCount; i++)
printDouble(i, doublesCount, arrayAll, 'a');
double *tp = &arrayAll[doublesCount-1][4];
printf("The last double is at %p and is %6.2f\n", tp, *tp);
printf("The first double * is at %p\n", &arrayAll[0]);
printDouble(1, doublesCount, arrayAll, 'f');
printf("The first quaternary double is %6.2f and it's at %p\n", arrayAll[0][4], &arrayAll[0][4]);
qsort(arrayAll, doublesCount, sizeof(double *), doubleCmp);
for (int i = 0; i < doublesCount; i++)
printDouble(i, doublesCount, arrayAll, 'a');
return 0;
}
int getAllDoubles(char *filename, double ***arrayAllPtr)
{
FILE *fp;
int doublesCount = 0;
double * *arrayAll;
char c;
if ((fp = fopen(filename, "r")) == NULL)
return -1;
while ((c = getc(fp)) != EOF)
{
if (c == 'd')
doublesCount++;
}
rewind(fp);
arrayAll = *arrayAllPtr = malloc(sizeof(double *) * doublesCount);
if (arrayAll == 0)
return -1;
char line[1024];
for (int y = 0; y < doublesCount && fgets(line, sizeof(line), fp) != 0; y++)
{
arrayAll[y] = malloc(sizeof(double) * 5);
if (arrayAll[y] == 0)
return -1; // Leak
if (sscanf(line, "d %lf %lf %lf", &arrayAll[y][1], &arrayAll[y][2], &arrayAll[y][0]) != 3)
return -1; // Leak
arrayAll[y][3] = sqrt(arrayAll[y][0] + arrayAll[y][1]);
if (arrayAll[y][0] == 0)
arrayAll[y][4] = 0;
else
arrayAll[y][4] = arrayAll[y][1] / arrayAll[y][0];
}
fclose(fp);
return doublesCount;
}
void printDouble(int doubleNumber, int doublesCount, double **arrayAll, char option)
{
if (doubleNumber < 0 || doubleNumber >= doublesCount)
puts("Invalid double!");
else if (option == 'a')
{
printf("%2d: %6.2f: %6.2f: %6.2f: %6.2f: %6.2f\n", doubleNumber+1,
arrayAll[doubleNumber][0], arrayAll[doubleNumber][1],
arrayAll[doubleNumber][2], arrayAll[doubleNumber][3],
arrayAll[doubleNumber][4]);
}
else if (option == 'f')
printf("four: %6.2f\n", arrayAll[doubleNumber][4]);
}
int doubleCmp(const void *dOne, const void *dTwo)
{
double * const *d1 = dOne;
double * const *d2 = dTwo;
double const *doubleOne = *d1;
double const *doubleTwo = *d2;
printf("d1: ");
printf("[0] = %6.2f; ", doubleOne[0]);
printf("[1] = %6.2f; ", doubleOne[1]);
printf("[2] = %6.2f; ", doubleOne[2]);
printf("[3] = %6.2f; ", doubleOne[3]);
printf("[4] = %6.2f\n", doubleOne[4]);
printf("d2: ");
printf("[0] = %6.2f; ", doubleTwo[0]);
printf("[1] = %6.2f; ", doubleTwo[1]);
printf("[2] = %6.2f; ", doubleTwo[2]);
printf("[3] = %6.2f; ", doubleTwo[3]);
printf("[4] = %6.2f\n", doubleTwo[4]);
if (doubleTwo[0] < doubleOne[0])
{
/*printf("%f comes before %f\n", *doubleOne, *doubleTwo);*/
return -1;
}
else if (doubleTwo[0] > doubleOne[0])
{
/*printf("%f comes before %f\n", *doubleTwo, *doubleOne);*/
return 1;
}
else
{
/*printf("%p is equal to %p\n", *doubleOne, *doubleTwo); */
return 0;
}
}
鉴于此示例数据集:
d 6.81 28.48 7.66
d 91.05 54.31 73.96
d 82.08 74.93 87.39
d 80.08 47.27 3.34
d 84.93 61.37 91.59
d 43.38 78.85 22.71
d 95.65 41.39 13.98
d 19.24 4.89 10.38
d 3.99 79.47 12.93
d 30.10 6.41 82.50
我从程序运行中得到的输出是:
the output I got from a run of the program was:
10 doubles successfully copied
1: 7.66: 6.81: 28.48: 3.80: 0.89
2: 73.96: 91.05: 54.31: 12.85: 1.23
3: 87.39: 82.08: 74.93: 13.02: 0.94
4: 3.34: 80.08: 47.27: 9.13: 23.98
5: 91.59: 84.93: 61.37: 13.29: 0.93
6: 22.71: 43.38: 78.85: 8.13: 1.91
7: 13.98: 95.65: 41.39: 10.47: 6.84
8: 10.38: 19.24: 4.89: 5.44: 1.85
9: 12.93: 3.99: 79.47: 4.11: 0.31
10: 82.50: 30.10: 6.41: 10.61: 0.36
The last double is at 0x7fc86b403e50 and is 0.36
The first double * is at 0x7fc86b403a20
four: 1.23
The first quaternary double is 0.89 and it's at 0x7fc86b403a90
d1: [0] = 7.66; [1] = 6.81; [2] = 28.48; [3] = 3.80; [4] = 0.89
d2: [0] = 22.71; [1] = 43.38; [2] = 78.85; [3] = 8.13; [4] = 1.91
d1: [0] = 22.71; [1] = 43.38; [2] = 78.85; [3] = 8.13; [4] = 1.91
d2: [0] = 82.50; [1] = 30.10; [2] = 6.41; [3] = 10.61; [4] = 0.36
d1: [0] = 73.96; [1] = 91.05; [2] = 54.31; [3] = 12.85; [4] = 1.23
d2: [0] = 22.71; [1] = 43.38; [2] = 78.85; [3] = 8.13; [4] = 1.91
d1: [0] = 87.39; [1] = 82.08; [2] = 74.93; [3] = 13.02; [4] = 0.94
d2: [0] = 22.71; [1] = 43.38; [2] = 78.85; [3] = 8.13; [4] = 1.91
d1: [0] = 3.34; [1] = 80.08; [2] = 47.27; [3] = 9.13; [4] = 23.98
d2: [0] = 22.71; [1] = 43.38; [2] = 78.85; [3] = 8.13; [4] = 1.91
d1: [0] = 82.50; [1] = 30.10; [2] = 6.41; [3] = 10.61; [4] = 0.36
d2: [0] = 22.71; [1] = 43.38; [2] = 78.85; [3] = 8.13; [4] = 1.91
d1: [0] = 91.59; [1] = 84.93; [2] = 61.37; [3] = 13.29; [4] = 0.93
d2: [0] = 22.71; [1] = 43.38; [2] = 78.85; [3] = 8.13; [4] = 1.91
d1: [0] = 7.66; [1] = 6.81; [2] = 28.48; [3] = 3.80; [4] = 0.89
d2: [0] = 22.71; [1] = 43.38; [2] = 78.85; [3] = 8.13; [4] = 1.91
d1: [0] = 12.93; [1] = 3.99; [2] = 79.47; [3] = 4.11; [4] = 0.31
d2: [0] = 22.71; [1] = 43.38; [2] = 78.85; [3] = 8.13; [4] = 1.91
d1: [0] = 10.38; [1] = 19.24; [2] = 4.89; [3] = 5.44; [4] = 1.85
d2: [0] = 22.71; [1] = 43.38; [2] = 78.85; [3] = 8.13; [4] = 1.91
d1: [0] = 13.98; [1] = 95.65; [2] = 41.39; [3] = 10.47; [4] = 6.84
d2: [0] = 22.71; [1] = 43.38; [2] = 78.85; [3] = 8.13; [4] = 1.91
d1: [0] = 7.66; [1] = 6.81; [2] = 28.48; [3] = 3.80; [4] = 0.89
d2: [0] = 22.71; [1] = 43.38; [2] = 78.85; [3] = 8.13; [4] = 1.91
d1: [0] = 91.59; [1] = 84.93; [2] = 61.37; [3] = 13.29; [4] = 0.93
d2: [0] = 73.96; [1] = 91.05; [2] = 54.31; [3] = 12.85; [4] = 1.23
d1: [0] = 73.96; [1] = 91.05; [2] = 54.31; [3] = 12.85; [4] = 1.23
d2: [0] = 87.39; [1] = 82.08; [2] = 74.93; [3] = 13.02; [4] = 0.94
d1: [0] = 91.59; [1] = 84.93; [2] = 61.37; [3] = 13.29; [4] = 0.93
d2: [0] = 87.39; [1] = 82.08; [2] = 74.93; [3] = 13.02; [4] = 0.94
d1: [0] = 73.96; [1] = 91.05; [2] = 54.31; [3] = 12.85; [4] = 1.23
d2: [0] = 82.50; [1] = 30.10; [2] = 6.41; [3] = 10.61; [4] = 0.36
d1: [0] = 87.39; [1] = 82.08; [2] = 74.93; [3] = 13.02; [4] = 0.94
d2: [0] = 82.50; [1] = 30.10; [2] = 6.41; [3] = 10.61; [4] = 0.36
d1: [0] = 7.66; [1] = 6.81; [2] = 28.48; [3] = 3.80; [4] = 0.89
d2: [0] = 13.98; [1] = 95.65; [2] = 41.39; [3] = 10.47; [4] = 6.84
d1: [0] = 7.66; [1] = 6.81; [2] = 28.48; [3] = 3.80; [4] = 0.89
d2: [0] = 10.38; [1] = 19.24; [2] = 4.89; [3] = 5.44; [4] = 1.85
d1: [0] = 13.98; [1] = 95.65; [2] = 41.39; [3] = 10.47; [4] = 6.84
d2: [0] = 10.38; [1] = 19.24; [2] = 4.89; [3] = 5.44; [4] = 1.85
d1: [0] = 7.66; [1] = 6.81; [2] = 28.48; [3] = 3.80; [4] = 0.89
d2: [0] = 12.93; [1] = 3.99; [2] = 79.47; [3] = 4.11; [4] = 0.31
d1: [0] = 10.38; [1] = 19.24; [2] = 4.89; [3] = 5.44; [4] = 1.85
d2: [0] = 12.93; [1] = 3.99; [2] = 79.47; [3] = 4.11; [4] = 0.31
d1: [0] = 13.98; [1] = 95.65; [2] = 41.39; [3] = 10.47; [4] = 6.84
d2: [0] = 12.93; [1] = 3.99; [2] = 79.47; [3] = 4.11; [4] = 0.31
d1: [0] = 7.66; [1] = 6.81; [2] = 28.48; [3] = 3.80; [4] = 0.89
d2: [0] = 3.34; [1] = 80.08; [2] = 47.27; [3] = 9.13; [4] = 23.98
1: 91.59: 84.93: 61.37: 13.29: 0.93
2: 87.39: 82.08: 74.93: 13.02: 0.94
3: 82.50: 30.10: 6.41: 10.61: 0.36
4: 73.96: 91.05: 54.31: 12.85: 1.23
5: 22.71: 43.38: 78.85: 8.13: 1.91
6: 13.98: 95.65: 41.39: 10.47: 6.84
7: 12.93: 3.99: 79.47: 4.11: 0.31
8: 10.38: 19.24: 4.89: 5.44: 1.85
9: 7.66: 6.81: 28.48: 3.80: 0.89
10: 3.34: 80.08: 47.27: 9.13: 23.98
您可以从 doubleCmp() 中的诊断中看到它能够打印出它应该比较的数据行.输出数据在第 1 列中按正确(降序)顺序排列.
You can see from the diagnostics in doubleCmp() that it is able to print out the rows of data it is supposed to compare. The output data is in the correct (descending) order in column 1.
在 DoubleCmp 的顶部添加更改后，它开始工作，但我真的不知道为什么.
After just adding the change at the top in DoubleCmp, it started working, though I can't really figure out why.
在您执行此操作的前十几次左右时，考虑起来很棘手.之后，它变得更容易，或多或少是自动的.
The first dozen or so times you do this, it is tricky to think about. After that, it gets easier and more or less automatic.
让我们考虑一个更简单的排序示例:
Let's consider a simpler sorting example:
int array[] = { 3, 9, 12, 1, 36, -2, 0 };
enum { ARRAY_SIZE = sizeof(array) / sizeof(array[0]) };
qsort(array, ARRAY_SIZE, sizeof(array[0]), int_compare);
现在，我们知道int_compare()的签名必须是:
Now, we know that the signature of int_compare() must be:
int int_compare(void const *v1, void const *v2)
{
...
}
但是那些空指针指向什么?答案是它们指向数组的一个元素，而且是整数数组，所以底层类型是int *.
but what are those void pointers pointing at? The answer is that they point to an element of the array, and it is an array of integers, so the underlying type is int *.
int int_compare(void const *v1, void const *v2)
{
int const *ip1 = v1;
int const *ip2 = v2;
if (*ip1 < *ip2)
return -1;
else if (*ip1 > *ip2)
return +1;
else
return 0;
}
或者，由于我们正在处理简单的值，我们可以使用:
Or, since we're dealing with simple values, we could use:
int int_compare(void const *v1, void const *v2)
{
int i1 = *(int *)v1;
int i2 = *(int *)v2;
if (i1 < i2)
return -1;
else if (i1 > i2)
return +1;
else
return 0;
}
这种组织对于比较器有几个优点.第一个是无论数组中的值如何，它都能正常工作.有时，您会看到人们建议使用诸如 return i1 - i2; 之类的捷径，但是如果数组中的值足够大，则会遇到算术溢出问题；无论数组中的值如何，显示的代码都能正常工作.第二个是它很容易概括.如果这是比较结构数组的元素，则可以在前两个比较字段相同时添加额外条件:
There are a couple of advantages to this organization for the comparator. The first is that it works correctly regardless of the values in the array. Sometimes, you'll see people suggesting a short cut such as return i1 - i2;, but this runs into problems with arithmetic overflow if the values in the array are big enough; the code shown works correctly regardless of the values in the array. The second is that it generalizes fairly easily. If this was comparing elements of an array of structures, you could add extra criteria when the first two compared fields are the same:
int int_compare(void const *v1, void const *v2)
{
struct dohickey const *ip1 = v1;
struct dohickey const *ip2 = v2;
if (ip1->member1 < ip2->member1)
return -1;
else if (ip1->member1 > ip2->member1)
return +1;
else if (ip1->member2 < ip2->member2)
return -1;
else if (ip1->member2 > ip2->member2)
return +1;
else
return 0;
}
冲洗并重复用于区分数组中两个值的尽可能多的字段.
Rinse and repeat for as many fields as are used to distinguish two values in the array.
回到您的问题，您传递给 qsort() 的是一个指向 double 的指针"的数组，其中每个指向 double 的指针 指向包含 5 个 double 值的数组的开头.
Coming back to your problem, what you're passing to qsort() is an array of 'pointers to double', where each pointer to double points to the start of an array of 5 double values.
当排序处理int 数组"时，比较器接收到两个指向int"值的指针.当排序处理指向double的指针数组"时，比较器接收两个指向double的指针的指针".通常，当排序正在处理类型 X 的数组"时，比较器会收到两个指向 类型 X 的指针"值.
When the sort was processing an 'array of int', the comparator received two 'pointer to int' values. When the sort is processing an 'array of pointer to double', the comparator receives two 'pointer to pointer to double'. Generally, when the sort is processing an 'array of type X', the comparator receives two 'pointer to type X' values.
冒着让您感到困惑的风险，我还要提到您所拥有的不是真正的二维数组".这是声明使用:
At the risk of confusing you, I'll also mention that what you have is not a 'true 2-dimensional array'. That is declared using:
double array_2d[NROWS][NCOLS];
你可以通过调用来排序:
You'd sort that by calling:
qsort(array_2d, NROWS, sizeof(array_2d[0]), array_2d_cmp);
与:
int array_2d_cmp(void const *v1, void const *v2)
{
double (*a1)[NCOLS] = (double (*)[NCOLS])v1; // Cast away const cares
double (*a2)[NCOLS] = (double (*)[NCOLS])v2; // Cast away const cares
for (int i = 0; i < NCOLS)
{
if ((*a1)[i] < (*a2)[i])
return -1;
else if ((*a1)[i] > (*a2)[i])
return +1;
}
return 0;
}
qsort()的演示
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
enum { NROWS = 5, NCOLS = 7 };
static void dump_int_array_1d(char const *tag, size_t n, int a[n])
{
printf("%-8s", tag);
for (size_t i = 0; i < n; i++)
printf(" %3d", a[i]);
putchar('\n');
}
static void dump_double_array_2d(char const *tag, char const *fmt, size_t rows, size_t cols, double a[rows][cols])
{
printf("%s: (%zdx%zd)\n", tag, rows, cols);
for (size_t i = 0; i < rows; i++)
{
for (size_t j = 0; j < cols; j++)
printf(fmt, a[i][j]);
putchar('\n');
}
}
static int array_2d_cmp(void const *v1, void const *v2)
{
double (*a1)[NCOLS] = (double (*)[NCOLS])v1;
double (*a2)[NCOLS] = (double (*)[NCOLS])v2;
//double const (* const a1)[NCOLS] = v1;
//double const (* const a2)[NCOLS] = v2;
//typedef double (*DoubleArray)[NCOLS];
//DoubleArray const a1 = v1;
//DoubleArray const a2 = v2;
for (int i = 0; i < NCOLS; i++)
{
if ((*a1)[i] < (*a2)[i])
return -1;
else if ((*a1)[i] > (*a2)[i])
return +1;
}
return 0;
}
static void sort_2d_array_double(void)
{
double array_2d[NROWS][NCOLS];
for (int row = 0; row < NROWS; row++)
{
for (int col = 0; col < NCOLS; col++)
{
int value = rand() % 10000;
array_2d[row][col] = value / 100.0;
}
}
/* Ensure there are some duplicates */
array_2d[3][0] = array_2d[1][0];
array_2d[4][0] = array_2d[0][0];
array_2d[4][1] = array_2d[0][1];
dump_double_array_2d("Before", "%6.2f", NROWS, NCOLS, array_2d);
qsort(array_2d, NROWS, sizeof(array_2d[0]), array_2d_cmp);
dump_double_array_2d("After", "%6.2f", NROWS, NCOLS, array_2d);
}
typedef int (*Comparator)(void const *v1, void const *v2);
static void sort_1d_array_int(Comparator comp_func)
{
int array[] = { 3, 9, 12, 1, 36, -2, 0 };
enum { ARRAY_SIZE = sizeof(array) / sizeof(array[0]) };
dump_int_array_1d("Before:", ARRAY_SIZE, array);
qsort(array, ARRAY_SIZE, sizeof(array[0]), comp_func);
dump_int_array_1d("After:", ARRAY_SIZE, array);
}
static int int_compare1(void const *v1, void const *v2)
{
int const *ip1 = v1;
int const *ip2 = v2;
if (*ip1 < *ip2)
return -1;
else if (*ip1 > *ip2)
return +1;
else
return 0;
}
static int int_compare2(void const *v1, void const *v2)
{
int i1 = *(int *)v1;
int i2 = *(int *)v2;
if (i1 < i2)
return -1;
else if (i1 > i2)
return +1;
else
return 0;
}
int main(void)
{
srand(time(0));
sort_2d_array_double();
sort_1d_array_int(int_compare1);
sort_1d_array_int(int_compare2);
return 0;
}
这篇关于我的 Qsort 比较函数在内存中导致奇怪的东西的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
