我的Qsort比较函数在内存中引起奇怪的东西
为了习惯动态创建二维数组，我想创建一个可以按每个数组中的第五个成员排序的数组。 该数组是一组双打的多维数组。 每组持有五个双打。 最后两个双打是根据我写的一些随机表达式基于前三个计算的。 数组与从文件中读取的双打组数一样多。 当我写这篇文章的时候，我得到了非常随机的结果。
#include #include #include #include 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 = 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", *doubleTwo, *doubleOne);*/ return 1; } else{ /*printf("%p is equal to %p\n", *doubleOne, *doubleTwo); */ return 0; } } 我扔了一些printf语句（我知道不好的做法，但DDD不会让我在调用时通过我的比较函数）。 这就是我所知道的：
（在此运行中）第一组中的第一个double的地址（以及关联的第一组双精度数）是0x2041250。 第一组中第五个双精度数（我想要对数组进行排序）的地址是0x2042310。 令人震惊的是，因为对于那些应该只有32个字节的东西，地址的增加相当大。
通常，这会让我相信，填充动态数组的方法可能需要修复，但我可以使用打印function打印每一组双打。
更奇怪的是比较函数中的printf语句。 Qsort从我的2D数组中的第一个double *开始，它与第一个double的地址具有相同的值。 这一切都很好，但是当我编写printf语句以了解它们的算术运算方式时，该程序就产生了
（initial是指初始地址，0x2041250）initial + 1 = 0x2041258 // Fine initial + 2 = 0x2041260 //什么是初始值+ 3 = 0x2041268 //对不起？ initial + 4 = 0x2041270 //; _;
然后最重要的是，取消引用指针，作为void指针传入但是作为double *，（预期）产生0.000000。
我无法开始了解这里发生了什么。 有任何想法吗？
这是一个相当严重修改的代码版本。 我修改了输入代码，在主输入期间一次读取一行（行计数循环我没有修复;事实上，我会摆脱它，并按我的方式计算）。 我使用rewind()函数来保存关闭并重新打开文件。 我修改了代码，因此为了清晰起见使用下标符号。 我以XX.YY格式生成随机数据，因此打印格式为%6.2f以适应这种情况。
关键的变化在于doubleCmp()函数。 qsort()传递给它的值是指向’5 of double的数组’（或指向double的指针）的指针。 这解决了大多数问题; 很多代码的其余部分都是特殊的或古怪但可行的。
代码包括我的诊断打印。
#include #include #include #include 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
我从一个程序运行中得到的输出是：
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列中以正确（降序）顺序排列。
为什么doubleCmp()有变化？
刚刚在DoubleCmp的顶部添加更改后，它开始工作，但我无法弄清楚原因。
你执行此操作的前十几次，考虑起来很棘手。 在那之后，它变得更容易，或多或少自动化。
让我们考虑一个更简单的排序示例：
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()的签名必须是：
int int_compare(void const *v1, void const *v2) { ... }
但那些无效指针指向的是什么？ 答案是它们指向数组的一个元素，它是一个整数数组，因此底层类型是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; }
或者，由于我们处理简单的值，我们可以使用：
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; ，但如果数组中的值足够大，则会遇到算术溢出问题; 无论数组中的值如何，显示的代码都能正常工作。 第二是它相当容易推广。 如果这是比较结构数组的元素，则可以在前两个比较字段相同时添加额外条件：
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; }
冲洗并重复用于区分arrays中两个值的字段。
回到你的问题，你传递给qsort()是一个’指向double qsort() ‘的数组，其中每个指向double指针指向一个包含5个double值的数组的开头。
当排序处理’ int数组’时，比较器接收到两个’指向int ‘值的指针。 当排序处理’指向double的指针数组’时，比较器接收两个’指向double的指针’。 通常，当排序处理’ X型数组’时，比较器接收两个’指向X型的指针’值。
冒着让你感到困惑的风险，我还会提到你所拥有的并不是一个“真正的二维数组”。 宣布使用：
double array_2d[NROWS][NCOLS];
你可以通过调用来排序：
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 #include #include 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; }
只有当文件中的第一个字符为'd' ，才会执行此for循环，如果后续字符与'd'不同，则它将退出
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') ; }