这是我的代码（抱歉，它很长，但有很多重复的代码）。
{Description}使用伪随机生成的数字数组对algortihm测试程序进行排序。用户可以指定数组长度，最小和最大元素，重复值的最小数量。用户还可以选择要测试的阵列数。
1 /*=============================================================================
2 |
3 | Assignment: Program 12
4 |
5 | Author: Tomas Giedraitis
6 | Study group: VU MIF INFO, 1st group
7 | Contacts: [email protected]
8 | Class: Programming Basics
9 | Date: December 13th, 2017
10 |
11 | Language: GNU C (using gcc on Lenovo Y50-70, OS: Arch Linux x86_64)
12 | Version: 0.0
13 | To Compile: gcc -Wall -g -std=c11 pratybos12.c -o pratybos12
14 |
15 +-----------------------------------------------------------------------------
16 |
17 | Description: Sorting algortihm testing program using pseudo randomly
18 | generated number array. User can specify array length,
19 | its min and max elements, the least number of repeating
20 | values. User can also choose how many arrays to be tested.
21 |
22 | Input: Command line input by user
23 |
24 | Output: Prompt messages, validation errors and final results
25 | are displayed one per line to the standard output.
26 | The output is each algorithm's each iteration, with
27 | comparison and assignment counts, and also processor
28 | clock times and average completion time, in seconds.
29 | Finally, the average data of each algorithm is presented.
30 | At the end, the algorithms are sorted from best to worst
31 | by their average time.
32 |
33 | Version
34 | updates: Currently this is the intial version
35 |
36 +===========================================================================*/
37
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <time.h>
41
42 #include "dbg.h"
43
44 #include "helpers.h"
45 #include "test_algorithm.h"
46
47 #include "bubble_sort_a.h"
48 #include "bubble_sort_b.h"
49 #include "bubble_sort_c.h"
50 #include "bubble_sort_d.h"
51 #include "bubble_sort_e.h"
52 #include "bubble_sort_e_and_f.h"
53 #include "bubble_sort_f.h"
54 #include "bubble_sort_b_and_c.h"
55 #include "bubble_sort_b_and_e.h"
56 #include "bubble_sort_b_and_f.h"
57 #include "bubble_sort_c_and_e.h"
58 #include "bubble_sort_c_and_f.h"
59 #include "bubble_sort_b_and_e_and_f.h"
60 #include "bubble_sort_b_and_c_and_e_and_f.h"
61 #include "insertion_sort.h"
62 #include "quicksort_pivot_first.h"
63 #include "selection_sort.h"
64 #include "top_down_merge_sort.h"
65
66 #define MAX_ITER 100
67 #define MAX_ALGO 100
68
69
70 typedef struct {
71 char* pointerName;
72 int pointerMemory;
73 } PointerStats;
74
75 typedef struct {
76 PointerStats* memJournal;
77 int JournalPointerCount;
78 int memUsed;
79 int memUsedByJournal;
80 } MemoryStats;
81
82
83 typedef struct {
84 int no;
85 int is_sorted;
86 int comp_count;
87 int assign_count;
88 double clocks_total;
89 double time_spent;
90 } Iteration;
91
92 typedef struct {
93 char* type;
94 char* complexity;
95 int iter_count;
96 int rank;
97 int avg_comp;
98 int avg_assign;
99 double avg_clocks;
100 double avg_time;
101 Iteration* iterations[MAX_ITER];
102 } Algorithm;
103
104 typedef struct {
105 char* date;
106 char* arch;
107 char* compiler;
108 Algorithm* algorithms[MAX_ALGO];
109 } Results;
110
111 // a typedef creates a fake type, in this
112 // case for a sort function pointer
113 typedef int* (*sort_pointer)(int* target, int size);
114
115 // function pointer to a quicksort function
116 typedef int* (*quicksort_pointer)(int* target, int first, int last);
117
118 // function pointer to a mergesort function
119 typedef void (*mergesort_pointer)(int* target, int* working_array, int size);
120
121
122 void filldata(int* data, int size, int min, int max, int repeat);
123 void test_sort( int* data, int size, sort_pointer func, Algorithm* Algo, int no);
124 void test_quicksort( int* data, int size, quicksort_pointer func, Algorithm* Algo, int no);
125 void test_mergesort( int* data, int size, mergesort_pointer func, Algorithm* Algo, int no);
126 void print_algo(Algorithm* Algo);
127 void calculate_average(Algorithm* Algo);
128 Algorithm** rank_algorithms(Algorithm** target, int first, int last);
129
130 MemoryStats memoryStats;
131
132 int array_count;
133
134 int main(int argc, char* argv[])
135 {
136 srand(time(NULL));
137
138 Results* Res = malloc(sizeof(Results));
139
140 Res->date = "2017-12-16";
141 Res->arch = "Arch Linux x86_64";
142 Res->compiler = "gcc";
143
144 // creating algorithm structures
145 Algorithm* Algo1 = malloc(sizeof(Algorithm));
146 Algo1->type = "bubble_sort_a";
147 Algo1->complexity = "O (n^2)";
148
149 Algorithm* Algo2 = malloc(sizeof(Algorithm));
150 Algo2->type = "bubble_sort_b";
151 Algo2->complexity = "O (n^2)";
152
153 Algorithm* Algo3 = malloc(sizeof(Algorithm));
154 Algo3->type = "bubble_sort_c";
155 Algo3->complexity = "O (n^2)";
156
157 Algorithm* Algo4 = malloc(sizeof(Algorithm));
158 Algo4->type = "bubble_sort_d";
159 Algo4->complexity = "O (n^2)";
160
161 Algorithm* Algo5 = malloc(sizeof(Algorithm));
162 Algo5->type = "bubble_sort_e";
163 Algo5->complexity = "O (n^2)";
164
165 Algorithm* Algo6 = malloc(sizeof(Algorithm));
166 Algo6->type = "bubble_sort_f";
167 Algo6->complexity = "O (n^2)";
168
169 Algorithm* Algo7 = malloc(sizeof(Algorithm));
170 Algo7->type = "bubble_sort_b_and_c";
171 Algo7->complexity = "O (n^2)";
172
173 Algorithm* Algo8 = malloc(sizeof(Algorithm));
174 Algo8->type = "bubble_sort_b_and_e";
175 Algo8->complexity = "O (n^2)";
176
177 Algorithm* Algo9 = malloc(sizeof(Algorithm));
178 Algo9->type = "bubble_sort_b_and_f";
179 Algo9->complexity = "O (n^2)";
180
181 Algorithm* Algo10 = malloc(sizeof(Algorithm));
182 Algo10->type = "bubble_sort_c_and_e";
183 Algo10->complexity = "O (n^2)";
184
185 Algorithm* Algo11 = malloc(sizeof(Algorithm));
186 Algo11->type = "bubble_sort_c_and_f";
187 Algo11->complexity = "O (n^2)";
188
189 Algorithm* Algo12 = malloc(sizeof(Algorithm));
190 Algo12->type = "bubble_sort_e_and_f";
191 Algo12->complexity = "O (n^2)";
192
193 Algorithm* Algo13 = malloc(sizeof(Algorithm));
194 Algo13->type = "bubble_sort_b_and_e_and_f";
195 Algo13->complexity = "O (n^2)";
196
197 Algorithm* Algo14 = malloc(sizeof(Algorithm));
198 Algo14->type = "bubble_sort_b_and_c_and_e_and_f";
199 Algo14->complexity = "O (n^2)";
200
201 Algorithm* Algo15 = malloc(sizeof(Algorithm));
202 Algo15->type = "quicksort";
203 Algo15->complexity = "O (n logn n)";
204
205 Algorithm* Algo16 = malloc(sizeof(Algorithm));
206 Algo16->type = "insertion_sort";
207 Algo16->complexity = "O (2n)";
208
209 Algorithm* Algo17 = malloc(sizeof(Algorithm));
210 Algo17->type = "selection_sort";
211 Algo17->complexity = "O (2n)";
212
213 Algorithm* Algo18 = malloc(sizeof(Algorithm));
214 Algo18->type = "top down merge sort";
215 Algo18->complexity = "O (n log n)";
216
217 Res->algorithms[0] = Algo1;
218 Res->algorithms[1] = Algo2;
219 Res->algorithms[2] = Algo3;
220 Res->algorithms[3] = Algo4;
221 Res->algorithms[4] = Algo5;
222 Res->algorithms[5] = Algo6;
223 Res->algorithms[6] = Algo7;
224 Res->algorithms[7] = Algo8;
225 Res->algorithms[8] = Algo9;
226 Res->algorithms[9] = Algo10;
227 Res->algorithms[10] = Algo11;
228 Res->algorithms[11] = Algo12;
229 Res->algorithms[12] = Algo13;
230 Res->algorithms[13] = Algo14;
231 Res->algorithms[14] = Algo15;
232 Res->algorithms[15] = Algo16;
233 Res->algorithms[16] = Algo17;
234 Res->algorithms[17] = Algo18;
235
236 memoryStats.memJournal = malloc(10 * sizeof(int));
237
238 memoryStats.memUsedByJournal = 10;
239
240 memoryStats.JournalPointerCount = 0;
241
242 printf("Mem used total: %d\n", memoryStats.memUsed);
243
244 int size;
245 int min;
246 int max;
247 int repeat;
248
249 array_count = get_pos_num("How many arrays would you like to test? > ", 0);
250 size = get_pos_num("What is the size of each array? > ", 0);
251 min = get_pos_num("What is the minimum number in each array? > ", 0);
252 max = get_pos_num("What is the maximum number in each array? > ", 0);
253
254 while (1) {
255 printf("How many repeating values there will be AT LEAST? > ");
256 if (scanf("%d", &repeat) == 1 && repeat >= 0
257 && repeat <= (max - min + 1) && getchar() == '\n') {
258 break;
259 } else {
260 while (getchar() != '\n')
261 ;
262 printf("Please enter a positive integer or zero, which is not "
263 "greater than the "
264 "size of the array\n");
265 }
266 }
267
268 for (int i = 0; i < array_count; i++) {
269 int* data = malloc(size * sizeof(int));
270
271 filldata(data, size, min, max, repeat);
272 if (data == NULL)
273 die("Atminties problema");
274
275 printf("i: %d", i);
276 print_array(data, size, "Your generated numbers:");
277 //---------------------------USING FUNCTION POINTERS-----------------//
278
279 test_sort(data, size, &bubble_sort_a, Algo1, i + 1);
280 test_sort(data, size, &bubble_sort_b, Algo2, i + 1);
281 test_sort(data, size, &bubble_sort_c, Algo3, i + 1);
282 test_sort(data, size, &bubble_sort_d, Algo4, i + 1);
283 test_sort(data, size, &bubble_sort_e, Algo5, i + 1);
284 test_sort(data, size, &bubble_sort_f, Algo6, i + 1);
285 test_sort(data, size, &bubble_sort_b_and_c, Algo7, i + 1);
286 test_sort(data, size, &bubble_sort_b_and_e, Algo8, i + 1);
287 test_sort(data, size, &bubble_sort_b_and_f, Algo9, i + 1);
288 test_sort(data, size, &bubble_sort_c_and_e, Algo10, i + 1);
289 test_sort(data, size, &bubble_sort_c_and_f, Algo11, i + 1);
290 test_sort(data, size, &bubble_sort_e_and_f, Algo12, i + 1);
291 test_sort(data, size, &bubble_sort_b_and_e_and_f, Algo13, i + 1);
292 test_sort(data, size, &bubble_sort_b_and_c_and_e_and_f, Algo14, i + 1);
293
294 test_sort(data, size, &bubble_sort_c_and_f, Algo15, i + 1);
295 test_sort(data, size, &bubble_sort_e_and_f, Algo16, i + 1);
296 test_sort(data, size, &bubble_sort_b_and_e_and_f, Algo17, i + 1);
297 test_sort(data, size, &bubble_sort_b_and_c_and_e_and_f, Algo18, i + 1);
298
299
300 free(data);
301 }
302
303 calculate_average(Algo1);
304 calculate_average(Algo2);
305 calculate_average(Algo3);
306 calculate_average(Algo4);
307 calculate_average(Algo5);
308 calculate_average(Algo6);
309 calculate_average(Algo7);
310 calculate_average(Algo8);
311 calculate_average(Algo9);
312 calculate_average(Algo10);
313 calculate_average(Algo11);
314 calculate_average(Algo12);
315 calculate_average(Algo13);
316 calculate_average(Algo14);
317 calculate_average(Algo15);
318 calculate_average(Algo16);
319 calculate_average(Algo17);
320 calculate_average(Algo18);
321
322
323 for (int i = 0; i < 18; i++) {
324 print_algo(Res->algorithms[i]);
325 }
326
327
328 Algorithm** target = malloc(18 * sizeof(Algorithm));
329
330 target[0] = Algo1;
331 target[1] = Algo2;
332 target[2] = Algo3;
333 target[3] = Algo4;
334 target[4] = Algo5;
335 target[5] = Algo6;
336 target[6] = Algo7;
337 target[7] = Algo8;
338 target[8] = Algo9;
339 target[9] = Algo10;
340 target[10] = Algo11;
341 target[11] = Algo12;
342 target[12] = Algo13;
343 target[13] = Algo14;
344 target[14] = Algo15;
345 target[15] = Algo16;
346 target[16] = Algo17;
347 target[17] = Algo18;
348
349 target = rank_algorithms(target, 0, 17);
350
351 printf("Fastest algorithms (ranking):\n");
352 printf("=============================\n");
353
354 for (int i = 0; i < 18; i++) {
355 printf("%d. ", i + 1);
356 printf("%s\n", target[i]->type);
357 printf("Average time: %f\n", target[i]->avg_time);
358 printf("---------------------------------\n");
359 }
360
361 printf("================================\n");
362 printf("Date: %s\n", Res->date);
363 printf("Architecture: %s\n", Res->arch);
364 printf("Compiler: %s\n", Res->compiler);
365 printf("================================\n");
366
367 printf("Mem used total: %d\n", memoryStats.memUsed);
368
369
370 free(Res);
371
372
373 for (int i = 0; i < array_count; i++) {
374 free(Algo1->iterations[i]);
375 }
376 free(Algo1);
377
378 for (int i = 0; i < array_count; i++) {
379 free(Algo2->iterations[i]);
380 }
381 free(Algo2);
382
383 for (int i = 0; i < array_count; i++) {
384 free(Algo3->iterations[i]);
385 }
386 free(Algo3);
387
388 for (int i = 0; i < array_count; i++) {
389 free(Algo4->iterations[i]);
390 }
391 free(Algo4);
392
393 for (int i = 0; i < array_count; i++) {
394 free(Algo5->iterations[i]);
395 }
396 free(Algo5);
397
398 for (int i = 0; i < array_count; i++) {
399 free(Algo6->iterations[i]);
400 }
401 free(Algo6);
402
403 for (int i = 0; i < array_count; i++) {
404 free(Algo7->iterations[i]);
405 }
406 free(Algo7);
407
408 for (int i = 0; i < array_count; i++) {
409 free(Algo8->iterations[i]);
410 }
411 free(Algo8);
412
413 for (int i = 0; i < array_count; i++) {
414 free(Algo9->iterations[i]);
415 }
416 free(Algo9);
417
418 for (int i = 0; i < array_count; i++) {
419 free(Algo10->iterations[i]);
420 }
421 free(Algo10);
422
423 for (int i = 0; i < array_count; i++) {
424 free(Algo11->iterations[i]);
425 }
426 free(Algo11);
427
428 for (int i = 0; i < array_count; i++) {
429 free(Algo12->iterations[i]);
430 }
431 free(Algo12);
432
433 for (int i = 0; i < array_count; i++) {
434 free(Algo13->iterations[i]);
435 }
436 free(Algo13);
437
438 for (int i = 0; i < array_count; i++) {
439 free(Algo14->iterations[i]);
440 }
441 free(Algo14);
442
443 for (int i = 0; i < array_count; i++) {
444 free(Algo15->iterations[i]);
445 }
446 free(Algo15);
447
448 for (int i = 0; i < array_count; i++) {
449 free(Algo16->iterations[i]);
450 }
451 free(Algo16);
452
453 for (int i = 0; i < array_count; i++) {
454 free(Algo17->iterations[i]);
455 }
456 free(Algo17);
457
458 for (int i = 0; i < array_count; i++) {
459 free(Algo18->iterations[i]);
460 }
461 free(Algo18);
462
463 free(target);
464 free(memoryStats.memJournal);
465 }
466
467
468 void filldata(int* data, int size, int min, int max, int repeat)
469 {
470 int i;
471
472 for (i = 0; i < size; i++) {
473 data[i] = min + rand() % (max - min + 1);
474 }
475
476 if (repeat > 1) {
477 int repeat_value = min + rand() % (max - min + 1);
478
479 int indexes[repeat];
480
481 int x;
482
483 // Non-duplicate number generation
484
485 i = 0;
486 while (i < repeat) {
487 int index = rand() % size;
488
489 for (x = 0; x < i; x++) {
490 if (indexes[x] == index) {
491 break;
492 }
493 }
494 if (x == i) {
495 indexes[i++] = index;
496 }
497 }
498
499 for (i = 0; i < repeat; i++) {
500 data[indexes[i]] = repeat_value;
501 }
502 }
503 }
504
505
506 void test_sort(int* data, int size, sort_pointer func, Algorithm* Algo, int no)
507 {
508
509 count_ncomp = 0;
510 count_assign = 0;
511
512 begin = clock();
513
514 int* target = NULL;
515 target = malloc(size * sizeof(int));
516 if (!target)
517 die("Memory error.");
518
519 memcpy(target, data, size * sizeof(int));
520
521 Iteration* Iter = malloc(sizeof(Iteration));
522 if (Iter == NULL) {
523 exit(1);
524 }
525 Iter->no = no;
526
527 if (is_sorted(func(target, size), size)) {
528 end = clock();
529 clocks = (double)(end - begin);
530 time_spent = clocks / CLOCKS_PER_SEC;
531
532 Iter->is_sorted = 1;
533 Iter->comp_count = count_ncomp;
534 Iter->assign_count = count_assign;
535 Iter->clocks_total = clocks;
536 Iter->time_spent = time_spent;
537 } else {
538 Iter->is_sorted = 0;
539
540 };
541
542 Algo->iterations[no - 1] = Iter;
543
544 if (target == NULL) {
545 debug("Target is NULL");
546 }
547
548 free(target);
549 }
550
551
552 void print_algo(Algorithm* Algo)
553 {
554
555 printf("Algorithm type: %s\n", Algo->type);
556 printf("Time complexity: %s\n", Algo->complexity);
557 printf("----------------------------------\n");
558 for (int i = 0; i < array_count; i++) {
559 if (!Algo->iterations[i]->is_sorted) {
560 printf("Not sorted");
561 } else {
562 printf("no: %d\n", Algo->iterations[i]->no);
563 printf("is_sorted: True\n");
564 printf("comp_count: %d\n", Algo->iterations[i]->comp_count);
565 printf("assign count: %d\n", Algo->iterations[i]->assign_count);
566 printf("clocks total: %f\n", Algo->iterations[i]->clocks_total);
567 printf("time spent: %f\n", Algo->iterations[i]->time_spent);
568 }
569 printf("----------------------------------\n");
570 }
571 printf("Iteration count: %d\n", Algo->iter_count);
572 printf("Average compare count: %d\n", Algo->avg_comp);
573 printf("Average assign count: %d\n", Algo->avg_assign);
574 printf("Average clocks: %f\n", Algo->avg_clocks);
575 printf("Average time spent: %f\n", Algo->avg_time);
576
577 printf("===================================\n");
578 }
579
580 void calculate_average(Algorithm* Algo)
581 {
582 int sum_comp = 0;
583 int sum_assign = 0;
584 double sum_clocks = 0;
585 double sum_time = 0;
586 int sorted_count = array_count;
587
588 for (int i = 0; i < array_count; i++) {
589
590 debug("is sorted %d", Algo->iterations[i]->is_sorted);
591 debug("Array count: %d", i);
592
593 if (!Algo->iterations[i]->is_sorted) {
594 sorted_count--;
595 } else {
596 sum_comp += Algo->iterations[i]->comp_count;
597 sum_assign += Algo->iterations[i]->assign_count;
598 sum_clocks += Algo->iterations[i]->clocks_total;
599 sum_time += Algo->iterations[i]->time_spent;
600 }
601 }
602 if (sorted_count > 0) {
603 Algo->avg_comp = sum_comp / sorted_count;
604 Algo->avg_assign = sum_assign / sorted_count;
605 Algo->avg_clocks = (double)(sum_clocks / sorted_count);
606 Algo->avg_time = (double)(sum_time / sorted_count);
607 Algo->iter_count = sorted_count;
608 }
609 }
610
611 Algorithm** rank_algorithms(Algorithm** target, int first, int last)
612 {
613
614 Algorithm* temp;
615 int pivot, j, i;
616
617 if (first < last) {
618 pivot = first;
619 i = first;
620 j = last;
621
622 while (i < j) {
623 while (
624 target[i]->avg_time <= target[pivot]->avg_time && i < last) {
625 i++;
626 }
627 while (target[j]->avg_time > target[pivot]->avg_time) {
628 j--;
629 }
630 if (i < j) {
631 temp = target[i];
632 target[i] = target[j];
633 target[j] = temp;
634 }
635 }
636
637 temp = target[pivot];
638 target[pivot] = target[j];
639 target[j] = temp;
640
641 rank_algorithms(target, first, j - 1);
642 rank_algorithms(target, j + 1, last);
643 }
644 return target;
645 }
646
我能成功做什么（运行程序）：
How many arrays would you like to test? > 100
What is the size of each array? > 10
What is the minimum number in each array? > 1
What is the maximum number in each array? > 10
How many repeating values there will be AT LEAST? > 0
我做不到的事：
How many arrays would you like to test? > 1000
What is the size of each array? > 10
What is the minimum number in each array? > 1
What is the maximum number in each array? > 10
How many repeating values there will be AT LEAST? > 0
问题是当有1000个阵列要测试时（而不是100个）。这是我得到的同样错误：
DEBUG pratybos12.c:590: is sorted 1
DEBUG pratybos12.c:591: Array count: 919
==5798== Invalid read of size 4
==5798== at 0x10A646: calculate_average (pratybos12.c:590)
==5798== by 0x1096F5: main (pratybos12.c:313)
==5798== Address 0x2d2d2d2d2d2d2d31 is not stack'd, malloc'd or (recently) free'd
==5798==
==5798==
==5798== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==5798== General Protection Fault
==5798== at 0x10A646: calculate_average (pratybos12.c:590)
==5798== by 0x1096F5: main (pratybos12.c:313)
问题是，如何开始调试它，即问题可能出在哪里。
一些注意事项：（1）当我运行100个数组（第一种情况）时，Valgrind报告所有内存都已成功释放，不会发生泄漏。
（2）第300行我有“双重免费或贪污错误”：
300 free(data);
但我通过将MALLOC_CHECK_设置为0来关闭它。
Algorithm.iterations的大小是MAX_ITER，这是100.然后你访问Algorithm.iterations元素高达1000。这是未定义的行为。Algorithm** target = malloc(18 * sizeof(Algorithm));肯定是错的。 target的类型应该是Algorithm *。