堆排序的任何类型的元件不工作 [英] Heapsort for any type of elements doesn't work
问题描述
现在的任务是（仅使用C code）写堆排序为未知类型的数组中的元素，但我的code不起作用。对于下面的数字输出-100 -4 7 0 33 -3 67 1 5 44'我还试图用同样的code仅INT输入和它的工作完美。所以我觉得这个问题是在将其更改为任何类型的输入。
The task was to write heapsort for unknown type of elements in array (using only C code), but my code doesn't work. FOr the following numbers output is '-100 7 -4 0 33 -3 67 1 5 44' I also tried to use the same code for int input only and it worked perfectly. So I think the problem is in changing it to any type of input.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <memory.h>
typedef int typeEl;
int compare(const void* a, const void* b)
{
return (*(typeEl*)a - *(typeEl*)b);
}
void swap(void* a, void* b, size_t sizeOfElem) {
void* tmp = calloc(1,sizeOfElem);
memcpy(tmp, a, sizeOfElem);
memcpy(a, b, sizeOfElem);
memcpy(b, tmp, sizeOfElem);
}
void heapify (int pos, int n, void* arr, size_t sizeOfElem, int (*comp)(const void* c, const void* d)) {
while (2 * pos + 1 < n) {
int t = 2 * pos +1;
if (2 * pos + 2 < n && ((char *)arr + (2*pos+2)*sizeOfElem) >= ((char *)arr + t*sizeOfElem))
{
t = 2 * pos + 2;
}
if (comp((void *) ((char *)arr + pos*sizeOfElem), ((char *)arr + t*sizeOfElem))<0) {
swap((void *) ((char *)arr + pos*sizeOfElem), (void *) ((char *)arr + t*sizeOfElem), sizeOfElem);
pos = t;
}
else break;
}
}
void heap_make(int n, void* arr, size_t sizeOfElem)
{
for (int i = n - 1; i >= 0; i--)
{
heapify(i, n, arr, sizeOfElem, compare );
}
}
void heap_sort(int n, void* arr, size_t sizeOfElem)
{
heap_make(n, arr, sizeOfElem);
while(n>0)
{
swap((void *) ((char *)arr), (void *) ((char *)arr + (n-1)*sizeOfElem), sizeOfElem);;
n--;
heapify(0,n, arr, sizeOfElem, compare);
}
}
int main() {
int n;
int m[10] = {1,-3,5,-100,7,33,44,67,-4, 0};
heap_sort(10, m, sizeof(int));
for (n=0; n<10; n++)
printf ("%d ",m[n]);
return 0;
}
任何人都可以提出建议？ THX的帮助！
Anyone can advise? Thx for the help!
推荐答案
它可以是很难去code别人的code - 尤其是当你在做各种复杂的索引等。我有一个一个heapify躺在附近（从早期的答案旧副本 - http://stackoverflow.com/a/19749300/1967396 ），我修改它适用于任何类型 - 并包括一个完整的排序
It can be very hard to decode someone else's code - especially when you are doing all kinds of complicated indexing etc. I had an old copy of a heapify lying around (from an earlier answer - http://stackoverflow.com/a/19749300/1967396 ) and I modified it to work for any type - and to include a full sort.
这并不能完全回答这个问题：为什么你的code不工作 - 但它确实告诉你，你可能要执行一些简单的技巧，当你试图回答这个问题。通常情况下，更可读的code，就越容易调试。
This doesn't completely answer the question "why is your code not working" - but it does show you some simple techniques you might want to implement as you try to answer the question. Typically, the more readable your code, the easier it is to debug.
需要注意的是，为了提高可读性，我介绍了一些额外的变量（和code附加线） - childLeft 和 childRight 肯定是有用的;此外，您还可以索引的元素，一旦你已经建立了自己的指针的数据类型 - 因为你有一个的typedef 在你的code开始，我简化了一些东西通过做
Note that, in order to improve readability, I introduced a couple of extra variables (and additional lines of code) - childLeft and childRight are definitely useful; also, you can index elements once you have established a data type for their pointer - since you had a typedef at the start of your code, I simplified some things by doing
typeEl *array;
之后，我可以用指数数组
after which I could index the array with
array[pos];
这是更为可读的（并因此不易出错）比
which is much more readable (and thus less prone to errors) than
*((void *) ((char *)arr + pos*sizeOfElem))
我还定义了在数组方面，而且在需要调换两种元素的指数掉期：
void swap(typeEl *arr, int i, int j)
这又使得code相当多的可读性（另请注意，我没有做释放calloc ）。
反正 - 这里是code：
Anyway - here is the code:
#include <stdio.h>
// define the type of the array that will be sorted:
typedef double typeEl;
void buildHeap(typeEl array[], int n);
void heapify(typeEl array[], int n, int i);
void heapsort(typeEl array[], int n);
void swap(typeEl array[], int indexA, int indexB);
void printTree(void);
int compare(typeEl a, typeEl b);
typeEl* TREE; // global variable used for printing the entire tree
int main(int argc, char *argv[])
{
typeEl heapArray[] = {1,-3,5,-100,7,33,44,67,-4, 0};
//{0, 1, 2, 3, 4, 5, 6 , 7, 8 ,9 ,10 , 11, 12, 13 ,14 ,15};
int n = sizeof(heapArray)/sizeof(typeEl);
TREE = heapArray;
printf("initial tree:\n");
printTree();
heapsort(heapArray, n);
printf("after heapify\n");
printTree();
printf("as a sorted array:\n");
for(int ii = 0; ii < n; ii++) printf("%d ", (int)heapArray[ii]);
printf("\n");
return 0;
}
void printTree(void)
{
// lazy way to print the entire tree...
typeEl* array = TREE;
printf(" %3d\n ", (int)array[0]);
printf(" %3d %3d\n", (int)array[1], (int)array[2]);
printf(" %3d %3d %3d %3d\n", (int)array[3], (int)(int)array[4], (int)array[5], (int)array[6]);
printf(" %3d %3d %3d\n", (int)array[7], (int)array[8], (int)array[9]);
printf("\n");
}
void heapsort(typeEl array[], int n) {
int i;
buildHeap(array, n);
for(i = 1; i < n; i++) {
buildHeap(array + i, n - i);
}
}
void buildHeap(typeEl array[], int n)
{
// change starting condition
int i = n/2;
while(i > 0) heapify(array, n,--i);
}
void heapify(typeEl array[], int n, int i)
{
// mark nodes initially as -1 to distinguish from "valid" zero
int childLeft = -1, childRight = -1;
int largest = i;
// see if we have valid child nodes:
if( 2 * i + 1 < n ) childLeft = 2 * i + 1;
if( 2 * i + 2 < n ) childRight = 2 * i + 2;
// see if any nodes are invalid now:
if(childLeft < 0 && childRight < 0) return;
if(childLeft < 0) childLeft = childRight; // can't happen, ever.
if(childRight < 0) childRight = childLeft;
// printf("child left [%i] = %i child right [%i] = %i\n", childLeft, array[childLeft], childRight, array[childRight]);
if (compare(array[childLeft], array[i] )) largest = childLeft;
if (compare(array[childRight] , array[largest])) largest = childRight;
if(largest != i)
{
swap(array, i,largest);
heapify(array, n, largest);
}
}
void swap(typeEl array[], int indexA, int indexB)
{
// printf("swap [%i] %i with [%i] %i\n", indexA, array[indexA], indexB, array[indexB]);
typeEl temp = array[indexA];
array[indexA] = array[indexB];
array[indexB] = temp;
}
int compare(typeEl a, typeEl b) {
return (a - b>0)?1:0;
}
示例输出：
initial tree:
1
-3 5
-100 7 33 44
67 -4 0
after heapify
67
44 33
7 5 1 0
-3 -4 -100
as a sorted array:
67 44 33 7 5 1 0 -3 -4 -100
正如你可以看到它是高排序 - 到 - 低。很明显，你可以通过简单地改变改变了比的功能。
这篇关于堆排序的任何类型的元件不工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
